Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T03:12:08.729Z Has data issue: false hasContentIssue false
  • English
  • Français

Barwise: Infinitary Logic and Admissible Sets

Published online by Cambridge University Press:  15 January 2014

H. Jerome Keisler  and
Julia F. Knight
H. Jerome Keisler
Affiliation:
Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison Wi 53706, U.S.A.E-mail: , [email protected]
Julia F. Knight
Affiliation:
Department of Mathematics, University of Notre Dame, 255 Hurley Hall, Notre Dame in 46556, U.S.A.E-mail: , [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46] (see also the papers [47], [48]), and that of Platek [58], at Stanford, on admissible sets.

Barwise's work on infinitary logic and admissible sets is described in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.

Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.

§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 10 , Issue 1 , March 2004 , pp. 4 - 36
Copyright
Copyright © Association for Symbolic Logic 2004

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] Adamson, A., Admissible sets and the saturation of structures, Queen's Mathematical Preprint, no. 1977–4, 1977.Google Scholar
[2] Arana, A., Ph.D. thesis , University of Notre Dame, 2003.Google Scholar
[3] Ash, C. J. and Knight, J. F., Computable structures and the hyperarithmetical hierarchy, Elsevier, 2000.Google Scholar
[4] Barwise, K. J., Infinitary logic and admissible sets, Ph.D. thesis , Stanford University, 1967.Google Scholar
[5] Barwise, K. J., Implicit definability and compactness in infinitary languages, The syntax and semantics of infinitary languages (Barwise, K. J., editor), Springer-Verlag, 1968, pp. 1–35.Google Scholar
[6] Barwise, K. J., Applications of strict predicates to infinitary logic, The Journal of Symbolic Logic, vol. 34 (1969), pp. 409–432.Google Scholar
[7] Barwise, K. J., Infinitary logic and admissible sets, The Journal of Symbolic Logic, vol. 34 (1969), pp. 226–252.Google Scholar
[8] Barwise, K. J., Infinitary methods in the model theory of set theory, Logic colloquium '69 (Gandy, R. O. and Yates, C. M., editors), 1969, pp. 63–66.Google Scholar
[9] Barwise, K. J., The hanf number of second order logic, The Journal of Symbolic Logic, vol. 37 (1972), pp. 588–594.Google Scholar
[10] Barwise, K. J., Back and forth through infinitary logic, Studies in model theory (Morley, M. D., editor), Mathematical Association of America, 1973, pp. 5–34.Google Scholar
[11] Barwise, K. J., Admissible sets and the interaction of model theory, recursion theory, and set theory, Proceedings of the international congress of mathematicians (Fenstad, J. E. and Hinman, P. G., editors), vol. II, 1974, pp. 229–234.Google Scholar
[12] Barwise, K. J., Admissible sets over models of set theory, Generalized recursion theory (Fenstad, J. E. and Hinman, P. G., editors), North-Holland, 1974, pp. 97–122.Google Scholar
[13] Barwise, K. J., Admissible sets and structures, Springer-Verlag, 1975.Google Scholar
[14] Barwise, K. J., On Moschovakis' closure ordinals, The Journal of Symbolic Logic, vol. 42 (1977), pp. 292–298.Google Scholar
[15] Barwise, K. J., Monotone quantifiers and admissible sets, Generalized recursion theory II (Fenstad, J. E., Gandy, R. O., and Sacks, G. E., editors), North-Holland, 1978, pp. 1–38.Google Scholar
[16] Barwise, K. J., The right things for the right reasons, Kreiseliana: About and around Georg Kreisel (Odifreddi, P., editor), Peters, 1996, pp. 15–23.Google Scholar
[17] Barwise, K. J. and Eklof, P. C., Lefschetz's principle, Journal of Algebra, vol. 13 (1969), pp. 554–570.Google Scholar
[18] Barwise, K. J., Infinitary properties of Abelian torsion groups, Annals of Mathematical Logic, vol. 2 (1970), pp. 25–68.Google Scholar
[19] Barwise, K. J., Gandy, R. O., and Moschovakis, Y. N., The next admissible set, The Journal of Symbolic Logic, vol. 36 (1971), pp. 108–120.Google Scholar
[20] Barwise, K. J., Kaufmann, M., and Makkai, M., Stationary logic, Annals of Mathematical Logic, vol. 13 (1978), pp. 171–224.Google Scholar
[21] Barwise, K. J. and Kunen, K., Hanf numbers for fragments of L∞ω , Israel Journal of Mathematics, vol. 10 (1971), pp. 306–320.Google Scholar
[22] Barwise, K. J. and Moschovakis, Y. N., Global inductive definability, The Journal of Symbolic Logic, vol. 43 (1978), pp. 521–534.CrossRefGoogle Scholar
[23] Barwise, K. J. and Schlipf, J. S., On recursively saturated models of arithmetic, Model theory and algebra (Saracino, D. H. and Weispfenning, V. B., editors), Springer-Verlag, 1973, pp. 42–55.Google Scholar
[24] Barwise, K. J., An introduction to recursively saturated and resplendent models, The Journal of Symbolic Logic, vol. 41 (1976), pp. 531–536.Google Scholar
[25] Barwise, K. J. and Van Bentham, J. , Interpolation, preservation, and pebble games, The Journal of Symbolic Logic, vol. 64 (1999), pp. 881–903.Google Scholar
[26] Chang, C. C., Some remarks on the model theory of infinitary languages, The syntax and semantics of infinitary languages (Barwise, K. J., editor), Springer-Verlag, 1968, pp. 36–63.Google Scholar
[27] Chang, C. C. and Keisler, H. J., Model theory, third ed., North-Holland, 1990.Google Scholar
[28] Feferman, S. and Kreisel, G., Persistent and invariant formulas relative to theories of higher order, Bulletin of the American Mathematical Society, vol. 72 (1966), pp. 480–485.Google Scholar
[29] Friedman, H. and Jensen, R., Note on admissible ordinals, The syntax and semantics of infinitary languages (Barwise, K. J., editor), Springer-Verlag, 1968, pp. 77–79.CrossRefGoogle Scholar
[30] Hanf, W., Incompactness in languages with infinitely long expressions, Fundamenta Mathematicae, vol. 53 (1964), pp. 309–324.Google Scholar
[31] Harrison, J., Recursive pseudo well-orderings, Ph.D. thesis , Stanford University, 1966.Google Scholar
[32] Harrison, J., Recursive pseudo well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
[33] Hella, L., Kolaitis, P. G., and Luosto, K., Almost everywhere equivalence of logics in finite model theory, this Bulletin, vol. 12 (1996), pp. 422–443.Google Scholar
[34] Henkin, L., The completeness of the first-order predicate calculus, The Journal of Symbolic Logic, vol. 14 (1949), pp. 159–166.Google Scholar
[35] Henkin, L., A generalization of the concept of ω-consistency, The Journal of Symbolic Logic, vol. 19 (1954), pp. 183–196.Google Scholar
[36] Henkin, L., A generalization of the concept of ω-completeness, The Journal of Symbolic Logic, vol. 22 (1957), pp. 1–14.Google Scholar
[37] Karp, C., Languages with expressions of infinite length, Ph.D. thesis , University of Southern California, 1959.Google Scholar
[38] Keisler, H. J., Model theory for infinitary logic, North-Holland, 1971.Google Scholar
[39] Kleene, S. C., On the forms of the predicates in the theory of constructive ordinals, II, American Journal of Mathematics, vol. 77 (1955), pp. 405–428.Google Scholar
[40] Kreisel, G., Set-theoretic problems suggested by the notion of potential totality, Infinitistic methods, Pergamon, 1961, pp. 103–140.Google Scholar
[41] Kreisel, G. and Sacks, G., Metarecursive sets, The Journal of Symbolic Logic, vol. 30 (1965), pp. 318–338.Google Scholar
[42] Kripke, S., Transfinite recursions on admissible ordinals, I and II, The Journal of Symbolic Logic, vol. 29 (1964), pp. 161–162.Google Scholar
[43] Lempp, S. and Lerman, M., A general framework for priority arguments, this Bulletin, vol. 1 (1995), pp. 189–201.Google Scholar
[44] Levy, A., A hierarchy of formulas in set theory, Memoirs of the Americal Mathematical Society, vol. 57, American Mathematical Society, 1965.Google Scholar
[45] Lipschitz, L. and Nadel, M., The additive structure of models of arithmetic, Proceedings of the American Mathematical Society, vol. 68 (1978), pp. 331–336.Google Scholar
[46] Lopez-Escobar, E. K., Infinitely long formulas with countable quantifier degrees, Ph.D. thesis , University of California, Berkeley, 1964.Google Scholar
[47] Lopez-Escobar, E. K., An interpolation theorem for denumer ably long sentences, Fundamenta Mathematicae, vol. 57 (1965), pp. 253–272.Google Scholar
[48] Lopez-Escobar, E. K., On definable well-orderings, Fundamenta Mathematicae, vol. 59 (1966), pp. 13–21 and 299–300.CrossRefGoogle Scholar
[49] Makkai, M., An application of a method of Smullyan to logics on admissible sets, Bulletin of the Polish Academy of Sciences, vol. 17 (1969), pp. 341–346.Google Scholar
[50] Makkai, M., An example concerning Scott heights, The Journal of Symbolic Logic, vol. 46 (1981), pp. 301–318.Google Scholar
[51] Morley, M., Omitting classes of elements, The theory of models (Addison, J., Henkin, L., and Tarski, A., editors), North-Holland, 1965, pp. 263–273.Google Scholar
[52] Morley, M., The Hanf number for ω-logic (abstract), The Journal of Symbolic Logic, vol. 32 (1967), p. 437.Google Scholar
[53] Morozov, A. S., Functional trees and automorphisms of models, Algebra and Logic, vol. 32 (1993), pp. 28–38.Google Scholar
[54] Moschovakis, Y. N., Elementary induction on abstract structures, North-Holland, 1974.Google Scholar
[55] Nadel, M. E., Scott sentences for admissible sets, Annals of Mathematical Logic, vol. 7 (1974), pp. 267–294.Google Scholar
[56] Nadel, M. E., ℒω1ω and admissible fragments, Model-theoretic logics (Barwise, K. J. and Feferman, S., editors), Springer-Verlag, 1985, pp. 271–316.Google Scholar
[57] Orey, S., On ω-consistency and related properties, The Journal of Symbolic Logic, vol. 21 (1956), pp. 246–252.Google Scholar
[58] Platek, R., Foundations of recursion theory, Ph.D. thesis, Stanford University, 1966.Google Scholar
[59] Ressayre, J.-P., Models with compactness properties relative to an admissible language, Annals of Mathematical Logic, vol. 11 (1977), pp. 31–55.Google Scholar
[60] Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, 1967.Google Scholar
[61] Sacks, G. E., Metarecrusively enumerable sets and admissible ordinals, Bulletin of the American Mathematical Society, vol. 72 (1966), pp. 59–64.Google Scholar
[62] Schlipf, J., A guide to the identification of admissible sets above structures, Annals of Mathematical Logic, vol. 12 (1977), pp. 151–192.Google Scholar
[63] Schlipf, J., Model theory and recursive saturation, The Journal of Symbolic Logic, vol. 43 (1978), pp. 183–206.CrossRefGoogle Scholar
[64] Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, The theory of models (Addison, J., Henkin, L., and Tarski, A., editors), North-Holland, 1965, pp. 329–341.Google Scholar
[65] Takeuti, G., Recursive functions and arithmetical functions of ordinal numbers, Logic, methodology and philosophy of science (Bar-Hillel, Y., editor), North-Holland, 1965, pp. 179–196.Google Scholar
[66] Tugue, T., On the partial recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 16 (1964), pp. 1–31.Google Scholar
[67] Vaught, R., Denumerable models of complete theories, Infinitistic methods, Pergamon, 1961, pp. 303–321.Google Scholar