Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T15:41:17.705Z Has data issue: false hasContentIssue false
  • English
  • Français

Countable structures, Ehrenfeucht strategies, and Wadge reductions

Published online by Cambridge University Press:  12 March 2014

Tom Linton
Tom Linton*
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706
*
Department of Mathematics, California Institute of Technology, Pasadena, California 91125.
Get access Rights & Permissions [Opens in a new window]

Abstract

For countable structures and , let abbreviate the statement that every sentence true in also holds in . One can define a back and forth game between the structures and that determines whether . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω sentence, then there are countably infinite models and such that ⊨ θ, ⊨ ¬θ, and . For countable languages ℒ there is a natural way to view ℒ structúres with universe ω as a topological space, Xℒ. Let [] = { ∊ Xℒ∣ ≅ } denote the isomorphism class of . Let and be countably infinite nonisomorphic ℒ structures, and let C ⊆ ωω be any subset. Our main result states that if , then there is a continuous function f: ωω → Xℒ with the property that x ∊ C ⇒ f(x) ∊ [] and x ∉ C ⇒ f(x) ∊ f(x) ∈ []. In fact, for α ≤ 3, the continuous function f can be defined from the relation.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 56 , Issue 4 , December 1991 , pp. 1325 - 1348
Copyright
Copyright © Association for Symbolic Logic 1991

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]Addison, J. W., The method of alternating chains, The theory of models (proceedings of the 1963 international symposium at Berkeley), North-Holland, Amsterdam, 1965, pp. 1–16.Google Scholar
[2]Addison, J. W., Some problems in hierarchy theory, Recursive function theory, Proceedings of Symposia in Pure Mathematics, vol. 5, American Mathematical Society, Providence, Rhode Island, 1962, pp. 123–130.CrossRefGoogle Scholar
[3]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[4]Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49 (1961), pp. 129–141.CrossRefGoogle Scholar
[5]Friedman, H. and Stanley, L., A Borel reducibility theory for classes of countable structures, this Journal, vol. 54 (1989), pp. 894–914.Google Scholar
[6]John, T., Strategies for Borel games, Ph.D. Thesis, University of California, Berkeley, California, 1981.Google Scholar
[7]Keisler, H. J., Theory of models with generalized atomic formulas, this Journal, vol. 25 (1960), pp. 1–26.Google Scholar
[8]Keisler, H. J., Finite approximations of infinitely long formulas, The theory of models (proceedings of the 1963 international symposium at Berkeley), North-Holland, Amsterdam, 1965, pp. 158–169.Google Scholar
[9]Linton, T. J., Partial isomorphisms and continuous reductions with games, Ph.D. Thesis, University of Wisconsin, Madison, Wisconsin, 1991.Google Scholar
[10]López-Escobar, E. G. K., An interpolation theorem for denumerably long formulas, Fundamenta Mathematicae, vol. 57 (1965), pp. 253–272.CrossRefGoogle Scholar
[11]Louveau, A., Some results in the Wadge hierarchy of Borel sets, Cabel seminar 79–81, Lecture Notes in Mathematics, vol. 1019, Springer-Verlag, New York, 1983, pp. 28–55.CrossRefGoogle Scholar
[12]Louveau, A. and Saint-Raymond, J., The strength of Borel Wadge determinacy, Cabal seminar 81–85, Lecture Notes in Mathematics, vol. 1333, Springer-Verlag, New York, 1988, pp. 1–30.CrossRefGoogle Scholar
[13]Louveau, A. and Saint-Raymond, J., Borel classes and closed games: Wadge-type and Hurewicz-type results, Transactions of the American Mathematical Society, vol. 304 (1987), pp. 431–467.CrossRefGoogle Scholar
[14]Martin, D., Borel determinancy, Annals of Mathematics, ser. 2, vol. 102 (1975), pp. 363–371.CrossRefGoogle Scholar
[15]Miller, A., On the Borel classification of the isomorphism class of a countable model, Notre Dame Journal of Formal Logic, vol. 24(1983), pp: 22–34.CrossRefGoogle Scholar
[16]Miller, D. E., The invariant separation principle, Transactions of the American Mathematical Society, vol. 242 (1978), pp. 185–204.Google Scholar
[17]Moschovakis, Y., Descriptive set theory, North-Holland, Amsterdam, 1980.Google Scholar
[18]Mostowski, A., On absolute properties of relations, this Journal, vol. 12 (1947), pp. 33–42.Google Scholar
[19]Mostowski, A. and Ehrenfeucht, A., A compact space of models of first order theories, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 9 (1961), pp. 369–373.Google Scholar
[20]Scott, D., Invariant Borel sets, Fundamenta Mathematicae, vol. 56 (1964), pp. 117–128.CrossRefGoogle Scholar
[21]Van Wesep, R., Wadge degrees and descriptive set theory, Cabal seminar 76–77, Lecture Notes in Mathematics, vol. 689, Springer-Verlag, New York, 1978, pp. 151–170.CrossRefGoogle Scholar
[22]Vaught, R., Invariant sets in topology and logic, Fundamenta Mathematicae, vol. 82 (1974), pp. 269–294.CrossRefGoogle Scholar
[23]Wadge, W., Reducibility and determinateness on the Boire space, Ph.D. thesis, University of California, Berkeley, California, 1984.Google Scholar
[24]Wadge, W., Degrees of complexity of subsets of the Baire space, Notices of the American Mathematical Society, vol. 19 (1972), pp. A–714-A-715 (abstract 72T-E91).Google Scholar