Woensdag 10 november 2004
Vanaf half 11 is er koffie en chocola in de
||Wim Veldman (RU)
||The problem of the determinacy of infinite games from an intuitionistic
point of view
||11:00 - 12:00
||CK N4 (N3045)
be a subset of Baire space N
, that is, the set of
all infinite sequences α(0), α(1), ... of natural numbers.
We define the game for A
There are two players I, II, who together build an element of N
player I chooses α(0), player II chooses α(1),
player I chooses α(2), and so on.
Player I wins if α belongs to A
, and player II wins if α
does not belong to A
The set A
is called determinate
if either player I or player II
has a winning strategy
, that is, a method to ensure that he will always
win the game.
The problem which subsets of N
are determinate came up in the
1930's in discussion between Polish mathematicians and has a fascinating
history. In 1964, Jan Mycielski proposed to take the statement that all subsets
are determinate as an axiom of set theory and an alternative
to E. Zermelo's Axiom of Choice.
Taking Brouwer's intuitionistic standpoint, we re-examine the problem of
the determinacy of subsets of N
and also of subsets of certain
subspaces of N
, for instance Cantor space
, the set of all
α in N
that assume no other values than 0,1.
If one understands the disjunction occurring in the classical notion of
determinacy constructively, even finite games are not always determinate.
We suggest a different intuitionistic notion of determinacy and prove
that every subset of Cantor space is determinate in the proposed sense.
In Cantor space both player I and player II have two alternative possibilities
for each move. More generally, every subset of a space where player II has,
for each one of his moves, no more than a finite number of alternative
possibilities, is determinate according to our definition.
If we allow player II to have countably many alternatives for only one of his
moves, there are non-determinate subsets of the space.