Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-06T04:13:16.379Z Has data issue: false hasContentIssue false

The relative expressive power of some logics extending first-order logic

Published online by Cambridge University Press:  12 March 2014

John Cowles*
Affiliation:
University of Wyoming, Laramie, Wyoming 82071

Extract

In recent years there has been a proliferation of logics which extend first-order logic, e.g., logics with infinite sentences, logics with cardinal quantifiers such as “there exist infinitely many…” and “there exist uncountably many…”, and a weak second-order logic with variables and quantifiers for finite sets of individuals. It is well known that first-order logic has a limited ability to express many of the concepts studied by mathematicians, e.g., the concept of a wellordering. However, first-order logic, being among the simplest logics with applications to mathematics, does have an extensively developed and well understood model theory. On the other hand, full second-order logic has all the expressive power needed to do mathematics, but has an unworkable model theory. Indeed, the search for a logic with a semantics complex enough to say something, yet at the same time simple enough to say something about, accounts for the proliferation of logics mentioned above. In this paper, a number of proposed strengthenings of first-order logic are examined with respect to their relative expressive power, i.e., given two logics, what concepts can be expressed in one but not the other?

For the most part, the notation is standard. Most of the notation is either explained in the text or can be found in the book [2] of Chang and Keisler. Some notational conventions used throughout the text are listed below: the empty set is denoted by ∅.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1979

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]Bell, J. L. and Slomson, A. B., Models and ultraproducts: An introduction, North-Holland, Amsterdam, 1969.Google Scholar
[2]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[3]Cohen, P. J., Decision procedures for real and p-adic fields, Stanford University, 1967, mimeographed.Google Scholar
[4]Cowles, J. R., Abstract logic and extensions of first order logic, Ph.D. Thesis, The Pennsylvania State University, University Park, 1975Google Scholar
[5]Jacobson, N., Lectures in abstract algebra, vol. III, Theory of fields and Galois theory, Van Nostrand, Princeton, 1964.Google Scholar
[6]Jensen, F. V., On completeness in cardinality logics, Bulletin de l'Académie Polòǹaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 23 (1975), pp. 117122.Google Scholar
[7]Kreisel, G. and Krivine, J. L., Elements of mathematical logic, Model theory, North-Holland, Amsterdam, 1971.Google Scholar
[8]Kuratowski, C., Les types d'ordre définissables et les ensembles boreliens, Fundamenta Mahematicae, vol. 28 (1937), pp. 97100.CrossRefGoogle Scholar
[9]Kuratowski, K. and Mostowski, A., Set theory, North-Holland, Amsterdam, 1968.Google Scholar
[10]Magidor, M. and Malitz, J., Compact extensions of L(Q), Part la, Annals of Mathematical Logic, vol. 11 (1977), pp. 217261.CrossRefGoogle Scholar
[11]Nadel, M. and Stavi, J., L∞λ-equivalence, isomorphism and potential isomorphism (to appear).Google Scholar
[12]Sacks, G. E., Saturated model theory, Benjamin, Reading, Massachusetts, 1972.Google Scholar
[13]van der Waerden, B. L., Modern algebra. I, Ungar, New York, 1964.Google Scholar