A game on the universe of sets

D. I. Saveliev

Izvestiya. Mathematics , Tome 72 (2008) no. 3, pp. 581-625.

Résumé

Working in set theory without the axiom of regularity, we consider a two-person game on the universe of sets. In this game, the players choose in turn an element of a given set, an element of this element and so on. A player wins if he leaves his opponent no possibility of making a move, that is, if he has chosen the empty set. Winning sets (those admitting a winning strategy for one of the players) form a natural hierarchy with levels indexed by ordinals (in the finite case, the ordinal indicates the shortest length of a winning strategy). We show that the class of hereditarily winning sets is an inner model containing all well-founded sets and that each of the four possible relations between the universe, the class of hereditarily winning sets, and the class of well-founded sets is consistent. As far as the class of winning sets is concerned, either it is equal to the whole universe, or many of the axioms of set theory cannot hold on this class. Somewhat surprisingly, this does not apply to the axiom of regularity: we show that the failure of this axiom is consistent with its relativization to winning sets. We then establish more subtle properties of winning non-well-founded sets. We describe all classes of ordinals for which the following is consistent: winning sets without minimal elements (in the sense of membership) occur exactly at the levels indexed by the ordinals of this class. In particular, we show that if an even level of the hierarchy of winning sets contains a set without minimal elements, then all higher levels contain such sets. We show that the failure of the axiom of regularity implies that all odd levels contain sets without minimal elements, but it is consistent with the absence of such sets at all even levels as well as with their appearance at an arbitrary even non-limit or countable-cofinal level. To obtain consistency results, we propose a new method for obtaining models with non-well-founded sets. Finally, we study how long this game can be in the general case. Although there are plays of any finite length, we show that the game ends very quickly for almost all (in the sense of a certain natural probability) hereditarily finite well-founded sets after either one or three moves. It follows that the first player wins almost always. This result and those on winning sets without minimal elements reveal a fundamental difference between odd- and even-winning sets: the latter are rarer and more complicated.

Bibliographie

[1] D. I. Saveliev, “A report on a game on the universe of sets”, Math. Notes, 81:5–6 (2007), 716–719 ; arXiv: math.LO/0612636 | DOI | MR

[2] A. Lévy, Basic set theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin–New York, 1979 | MR | Zbl

[3] T. Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003 | MR | Zbl

[4] J. R. Shoenfield, “The axioms of set theory”, Handbook of mathematical logic, Part B, Set theory, Studies in Logic and Foundations of Math., 90, ed. J. Barwise, North-Holland, Amsterdam, 1977 | MR | Zbl

[5] G. Boolos, “The iterative conception of set”, Philosophy, 68:8 (1971), 215–231 | DOI

[6] P. Maddy, “Believing the axioms. I, II”, J. Symbolic Logic, 53:2 (1988), 481–511 | DOI | MR | Zbl

[7] D. I. Saveliev, Choice and regularity: common consequences in logic, arXiv: 0709.2979

[8] E. Zermelo, “Über Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre”, Fund. Math., 16 (1930), 29–47 | Zbl

[9] E. Mendelson, “The axiom of Fundierung and the axiom of choice”, Arch. Math. Logic, 4:3–4 (1958), 65–70 | DOI | MR | Zbl

[10] L. Rieger, “A contribution to Gödel's axiomatic set theory. I”, Czechoslovak Math. J., 7(82) (1957), 323–357 | MR | Zbl

[11] P. Aczel, Non-well-founded sets, CSLI Lecture Notes, 14, Center for the Study of Language and Information, Stanford, CA, 1988 | MR | Zbl

[12] G. d'Agostino, Modal logic and non-well-founded set theory: translation, bisimulation, interpolation, Dissertation Series, 4, Institute for Logic, Language, and Computation, Amsterdam, 1998

[13] M. Forti, F. Honsell, “Set theory with free construction principles”, Ann. Sc. Norm. Super. Pisa Cl. Sci. (4), 10:3 (1983), 493–522 | MR | Zbl

[14] J. Barwise, L. Moss, Vicious circle. On the mathematics of non-wellfounded phenomena, CSLI Lecture Notes, 60, Center for the Study of Language and Informations, Stanford, CA, 1996 | MR | Zbl

[15] A. Rieger, “An argument for Finsler–Aczel set theory”, Mind, 109:434 (2000), 241–253 | DOI | MR

[16] M. V. Marshall, M. G. Schwarze, “Rank in set theory without foundation”, Arch. Math. Logic, 38:6 (1999), 387–393 | DOI | MR | Zbl

[17] D. I. Saveliev, A note on singular cardinals in set theory without choice, arXiv: 0709.2436

[18] D. Mirimanoff, “Les antinomies de Russell et de Burali-Forti et le problème fondamental de la théorie des ensembles”, Enseign. Math., 19 (1917), 37–52 | Zbl

[19] D. Mirimanoff, “Remarques sur la théorie des ensembles et les antinomies cantoriennes. I”, Enseign. Math., 19 (1917), 209–217 | Zbl

[20] T. E. Forster, Set theory with a universal set. Exploring an untyped universe, Oxford Logic Guides, 31, The Clarendon Press, London; Oxford University Press, New York, 1995 | MR | Zbl

[21] E. Zermelo, “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels”, Proc. 5th Intern. Congress of Math. (Cambridge, 1912), 2, Cambridge University Press, Cambridge, 1913, 501–504 | Zbl

[22] Yu. V. Glebskii, D. I. Kogan, M. I. Liogon'kii, V. A. Talanov, “Range and degree of realizability of formulas in the restricted predicate calculus”, Cybernetics and Systems Analysis, 5:2 (1969), 142–154 | DOI

[23] A. Blass, Y. Gurevich, Strong extension axioms and Shelah's zero-one law for choiceless polynomial time, MSR-TR-2001-68, 1–96

[24] M. Gitik, “All uncountable cardinals can be singular”, Israel J. Math., 35:1–2 (1980), 61–88 | DOI | MR | Zbl