Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. RAN. Ser. Mat., 2008, Volume 72, Issue 3, Pages 175–224 (Mi izv2601)

A game on the universe of sets

D. I. Saveliev

M. V. Lomonosov Moscow State University

Abstract: 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.

DOI: https://doi.org/10.4213/im2601

Full text: PDF file (1115 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2008, 72:3, 581–625

Bibliographic databases:

UDC: 510.322.2+510.325.2+510.327+510.336
MSC: 03E30, 03C55, 03E25, 03E35, 03E45, 03E55, 03E65, 91A05, 91A43, 91A44

Citation: D. I. Saveliev, “A game on the universe of sets”, Izv. RAN. Ser. Mat., 72:3 (2008), 175–224; Izv. Math., 72:3 (2008), 581–625

Citation in format AMSBIB
\Bibitem{Sav08}
\by D.~I.~Saveliev
\paper A game on the universe of sets
\jour Izv. RAN. Ser. Mat.
\yr 2008
\vol 72
\issue 3
\pages 175--224
\mathnet{http://mi.mathnet.ru/izv2601}
\crossref{https://doi.org/10.4213/im2601}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2432757}
\zmath{https://zbmath.org/?q=an:1145.03027}
\elib{https://elibrary.ru/item.asp?id=20358635}
\transl
\jour Izv. Math.
\yr 2008
\vol 72
\issue 3
\pages 581--625
\crossref{https://doi.org/10.1070/IM2008v072n03ABEH002412}
\elib{https://elibrary.ru/item.asp?id=13579389}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-48749100370}