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.
