Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-22T17:07:14.193Z Has data issue: false hasContentIssue false
  • English
  • Français

Quine's ‘limits of decision’

Published online by Cambridge University Press:  12 March 2014

William C. Purdy
William C. Purdy*
Affiliation:
Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY13244-4100, E-mail: wcpurdy@ecs.syr.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

In a 1969 paper, Quine coined the term ‘limits of decision”. This term evidently refers to limits on the logical vocabulary of a logic, beyond which satisfiability is no longer decidable. In the same paper, Quine showed that not only monadic formulas, but homogeneous k -adic formulas for arbitrary k lie on the decidable side of the limits of decision. But the precise location of the limits of decision has remained an open question. The present paper answers that question. It addresses the question of decidability of those sublogics of first-order logic that are defined in terms of their logical vocabularies. A complete answer is obtained, thus locating exactly Quine's limits of decision.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 4 , December 1999 , pp. 1439 - 1466
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Andrews, Peter B., An introduction to mathematical logic and type theory, Academic Press, Orlando, 1986.Google Scholar
[2]Barnes, Donald W. and Mack, John M., An algebraic introduction to mathematical logic, Springer-Verlag, New York, 1975.CrossRefGoogle Scholar
[3]Dreben, B. and Goldfarb, W. D., The decision problem: Solvable classes of quantificational formulas, Addison-Wesley Publishing Company, Reading, 1979.Google Scholar
[4]Ebbinghaus, H. D. and Flum, J., Finite model theory, Springer-Verlag, New York, 1995.Google Scholar
[5]Ebbinghaus, H. D., Flum, J., and Thomas, W., Mathematical logic, Springer-Verlag, New York, 1984.Google Scholar
[6]Enderton, Herbert B., A mathematical introduction to logic, Academic Press, New York, 1972.Google Scholar
[7]Hintikka, Jaakko, Surface information and depth information, Information and inference (Hintikka, J. and Suppes, P., editors), 1970, pp. 263–297.CrossRefGoogle Scholar
[8]Hintikka, Jaakko, Logic, language-games and information, Clarendon Press, Oxford, 1973.Google Scholar
[9]Lewis, Harry R., Unsolvable classes of quantificational formulas, Addison-Wesley Publishing Company, Reading, 1979.Google Scholar
[10]Lewis, Harry R. and Papadimitriou, Christos H., Elements of the theory of computation, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1981.Google Scholar
[11]Noah, Aris, Predicate-functors and the limits of decidability in logic, Notre Dame Journal of Formal Logic, vol. 21 (1980), pp. 701–707.CrossRefGoogle Scholar
[12]Noah, Aris, Quine's version of term logic and its relation to TFL, Appendix E in Fred Sommers: The logic of natural language, Clarendon Press, Oxford, 1982.Google Scholar
[13]Papadimitriou, Christos H. and Steiglitz, Kenneth, Combinatorial optimization, Prentice- Hall, Inc., Englewood Cliffs, New Jersey, 1982.Google Scholar
[14]Purdy, W. C., Surrogate variables in natural language, Proceedings of the workshop on variable-free semantics, University of Osnabrueck, September 12–13, 1996, to appear.Google Scholar
[15]Purdy, W. C., Decidability of fluted logic with identity, Notre Dame Journal of Formal Logic, vol. 37 (1996), pp. 84–104.CrossRefGoogle Scholar
[16]Purdy, W. C., Fluted formulas and the limits of decidability, this Journal, vol. 61 (1996), pp. 608–620, This as well as other papers by the author cited here can be obtained by ftp from http://www.ecs.syr.edu/~wcpurdy.Google Scholar
[17]Quine, W. V., On the limits of decision, Proceedings of the 14th International Congress of Philosophy, vol. III, University of Vienna, 1969, Also in , W. V. Quine Theories and Things, Harvard University Press, Cambridge, 1981, 157–163.Google Scholar
[18]Quine, W. V., Variables explained away, Proceedings of the American Philosophical Society, vol. 104 (1960), pp. 343–347.Google Scholar
[19]Quine, W. V., The ways of paradox and other essays, Harvard University Press, Cambridge, 1976, Enlarged Edition.Google Scholar
[20]Quine, W. V., Predicate functors revisited, this Journal, vol. 46 (1981), pp. 649–652.Google Scholar
[21]Quine, W. V., Methods of logic, Harvard University Press, Cambridge, 1982, Fourth Edition.Google Scholar
[22]Rantala, Veikko, Constituents, Jaakko Hintikka (Bogdan, Radu J., editor), D. Reidel Publishing Company, Dordrecht, 1987, pp. 43–76.CrossRefGoogle Scholar