continuum hypothesis, axiom of constructibility, continuum problem, axiom of determinateness, constructibility, determinateness, axiom, set theory, descriptive, Ackermann, continuum

Back to title page.

Trying to prove the continuum hypothesis, Cantor developed his
**theory of transfinite ordinal numbers**. The origin of this
concept was described in Section 2.1.
The idea behind is simple enough (to explain, but hard to
discover).

Counting a set means bringing of some very strong order among
its members. After the counting of a finite set x is completed,
its members are allocated in a linear order: x_{1}, x_{2},
..., x_{n}, where x_{1} is the first member, and
x_{n} is the last member of x (under this particular
ordering). If we select any non-empty subset y of x, then y also
contains both the first and the last members (under the same
ordering of x).

But infinite sets cannot be ordered in this way. How strong can be the orderings that can be introduced on infinite sets? For example, consider the "natural" ordering of the set w of all natural numbers. If you separate a non-empty subset y of w, then you can definitely find the first (i.e. the least) member of y, but for an infinite y you will not find the last element. Can each infinite set be ordered at least in this way?

The precise framework is as follows. The relation R is called
a **well-ordering** of the set x, iff:

a) R is irreflexive on x: uRu is impossible for u in x.

b) R is transitive on x: uRv & vRz -> uRz for all u, v, z in x.

c) each non-empty subset of x contains (under R) a minimum member:

Ay(~(y=o) & y<=x -> Eu(u in y & Av(v in y -> u=v V uRv))).

Let us take any two different members u, v of x. Apply c) for
y={u, v}. If u is minimum of y, then uRv, and if v is minimum,
then vRu, i.e. each well ordering is a **linear ordering**
(but the converse is not true).

Can all infinite sets be well ordered, or some cannot? We know already that Zermelo proved in 1904 that a positive answer to this question is equivalent to the axiom of choice.

For counting of finite sets people have invented natural numbers: 1, 2, 3, 4, ... In set theory, traditionally, these numbers are represented by the following sets:

0 = o (the empty set), 1 = {0}, 2 = {0, 1}, 3 = {0,1,2}, ....

I.e. the number n+1 is represented by nU{n}. In the previous section we introduced a single formula expressing "x is a natural number".

For counting of infinite sets Cantor invented his transfinite ordinal numbers:

w (the first transfinite number - follows after natural numbers),

w+1 - follows immediately after w,

w+2 - follows immediately after w+1,

...

w*2=w+w - follows after all w+n (n - natural number),

w*2+1 - follows immediately after w*2,

...

w*3=w*2+w - follows after all w*2+n (n - natural number),

...

w^{2}=w*w - follows after all w*n (n - natural
number),

...

w^{w} - follows after all w^{n} (n - natural
number),

...

e_{0} (epsilon 0) - follows after all expressions
built of w and natural numbers by addition, multiplication and
exponentiation,

...

etc.

How to define these numbers by a single formula? Let us follow
the same von Neumann's idea (simplified by R. Robinson, Goedel
and Bernays), and let us call a set x an **ordinal number**,
iff:

a) x is a transitive set, i.e. AuAv(u in v in x -> u in x),

b) x is well ordered by the membership relation "in".

This definition differs from our definition of natural numbers in just one point: double well ordering is replaced by "simple" well ordering.

**Exercise 2.19.** a) Verify (using the axiom of
regularity) that the second part of the ordinal number definition
can be replaced by "x is **linearly** ordered the
membership relation **in**". Do you like a definition of
ordinal numbers depending on the axiom of regularity?

b) Write a formula expressing "x is ordinal number". How many characters does it contain?

This formula defines the class of all ordinal numbers (or simply, ordinals), that is denoted traditionally by On. The relation b<c for ordinals b, c is defined simply as "b in c".

Let us prove that

b in c & c is ordinal -> b is ordinal,

i.e. that an ordinal (as a set) consists only of ordinals. We must verify that b is a transitive set, well ordered by "in".

Transitivity. Suppose, u in v in b. Since v in b in c -> v in c (c is transitive), we have: u in v in c. Hence, u also is in c. Now, since u, v, b are all members of c, and "in" is an ordering of c, then u in v in b -> u in b. Q. E. D.

Well-ordering. Since c is transitive, b is subset of c, hence, "in" is ordering on b. Each non-empty subset of b is also subset of c, i.e. it contains a minimum member under "in". Q. E. D.

Thus, for each ordinal c: c = {b | b<c} - a generalization of n = {0, 1, 2, ..., n-1}.

**Exercise 2.20.** Verify that:

a) If b is ordinal, then bU{b} also is ordinal (moreover, it is the least ordinal greater than b). Traditionally, bU{b} is denoted by b+1.

b) Each non-empty class of ordinals contains a minimum member (the intersection of all ordinals of the class). Thus, On is well ordered by "<".

c) If x is a set of ordinals, then Ux also is ordinal (moreover, it is the least upper bound of x).

Hence, On is proper class. Indeed, if On=x, then Ux is the least upper bound of On, but Ux+1 is an ordinal greater than Ux. This is the first published paradox of set theory (Burali-Forti published it in 1897).

An ordinal b is called **successor ordinal**, iff b=c+1 for
some c. All the other ordinals are called **limit ordinals**.
The least limit ordinal is 0 (zero, or empty set). The second
limit ordinal is w (the set of all natural numbers).

**Exercise 2.21.** Verify that:

a) The second limit ordinal is w. I.e. verify that w is ordinal, and if n<w, then n is a natural number.

b) If b is limit ordinal, then b=Ub.

Now we can prove easily the

**Principle of Transfinite Induction.** Let A be a class of
ordinals such that: a) 0 in A, b) if b in A, then b+1 in A, c) if
x<=A, then Ux in A. Then A=On.

This is a generalization of the well known principle of mathematical induction.

**Proof.** If A is not On, then let b be the least ordinal
not in A. Of course, b is not 0. If b=c+1, then c in A, and b in
A. If b is a limit ordinal, then all c<b are in A, i.e.
b<=A, and Ub in A. But Ub=b. Q.E.D.

**Exercise 2.22.** Prove the **theorem of transfinite
induction**: if the class G is a function, then there is a
function F such that domain (F) = On, and for all b in On: F(b) =
G(F|b). By F|b we denote the restriction of the function F to the
domain b, i.e.

F|b = {(u, v) | u in b & (u, v) in F}.

The function G serves here as the recursion step: if we know already the values F(c) for all c<b (i.e. the values of the function F|b), then G "calculates" F(b).

Like as natural numbers allow counting of finite sets, ordinal numbers allow "counting" of arbitrary well ordered sets:

**Exercise 2.23.** Let x is a set well ordered by some
relation r. Prove that there exists a unique ordinal b such that
the structure (x, r) is isomorphic to the structure (b, <).
(Hint: use transfinite recursion to build a "counting"
function from On onto x).

For finite sets, ordering and counting are identical operations (in the sense that all well orderings of a finite set are isomorphic to a unique natural number). For infinite sets, the situation is more complicated. For example, w, w+2 and w*2 are different ordinals, but they can be used only for ordering of countable sets:

0, 1, 2, 3, ..., n, ... (the set of all natural numbers ordered according to w),

2, 3, ..., n, ..., 0, 1 (the same set ordered according to w+2),

0, 2, 4, ..., 2n, ..., 1, 3, 5, ..., 2n+1, ... (the same set ordered according to w*2).

Even w^{w} and e_{0} (epsilon 0, see above)
allow ordering only of countable sets. Which of these ordinals
should we use for "counting of countable sets"? Of
course, the least one - w.

This example justifies the following definition. Let us say
that an ordinal b is a **cardinal number**, iff there is no
one-to-one correspondence between b and an ordinal less than b.
It would be natural to use cardinal numbers for
"counting" of members of infinite sets. You could
verify easily that all natural numbers are cardinals, and that w
is the least infinite cardinal. But beyond w - are there more
cardinals?

**Exercise 2.24.** a) Use the axiom of choice and
diagonalization to prove the famous Cantor's theorem: There is no
one-to-one correspondence between the set x and the power-set
P(x).

b) Use the axiom of choice and transfinite recursion to prove the famous theorem by Zermelo: any set can be well ordered. (Hint: use transfinite recursion to build a "counting" function from On onto x).

Hence, if you have a cardinal k, then build the power-set
P(k), build a well ordering of it, and take the least ordinal k_{1}
isomorphic to this ordering of P(k). Then k_{1} will be a
cardinal greater than k.

But this result can be proved **without using the axiom of
choice**, i.e. in the theory ZF. The idea comes from the 1915
paper by F. Hartogs: let us prove that for each cardinal k the
class of all ordinals having one-to-one correspondence with k is
a set. Hence, since On is a proper class, there exist cardinals
greater than k. The following proof is adapted from Mendelson [1997]:

First let us consider all relations on k. Such relations are subsets of k x k, i.e. they are members of P(k x k). You can write easily a formula expressing "r is well ordering of k". Hence, by an appropriate separation axiom C21 the class of all well orderings of k is a set z<=P(k x k). From our Exercise 2.23 we know that for each r in z there exists a unique ordinal b such that (k, r) is isomorphic to (b, <). This correspondence can be expressed as a formula F(r, b). Now we can apply an appropriate replacement axiom C25, and conclude that the image F"z is a set. But F"z is exactly the class of all ordinals having one-to-one correspondence with k. Q.E.D.

Thus we have proved in ZF (i.e. without the axiom of choice)
that for each cardinal k there are cardinals greater than k. The
first infinite cardinal w (the set of all natural numbers) is
denoted traditionally also by aleph_{0}. This cardinal
"measures" the cardinality of countable sets. The first
uncountable cardinal is denoted by aleph_{1}, the second
uncountable cardinal - by aleph_{2}, etc. After all aleph_{n}
(n - natural number) follows the cardinal aleph_{w },
etc.

**Exercise 2.25.** a) Verify that aleph_{w}=U{aleph_{n}
| n in w}.

b) Prove that generally, if x is a set of cardinals, then Ux is a cardinal.

Having these results we can define aleph_{b} for each
ordinal b:

aleph_{0} = w,

aleph_{b+1} = the least cardinal greater than aleph_{b},

aleph_{b} = U{aleph_{c} | c<b} for a limit
ordinal b.

**Exercise 2.26.** Verify that "all cardinals are
alephs", i.e. if k is a cardinal, then k = aleph_{b}
for some ordinal b.

Thus we have a somewhat modernized version of Cantor's apparatus for counting infinite sets, which he developed trying to prove the continuum hypothesis. Each well ordered infinite set is in one-to-one correspondence with some aleph. If we adopt the axiom of choice, then each set can be well-ordered, and we can extend the above assertion: each infinite set is in one-to-one correspondence with some aleph.

Having Cantor's "aleph-scale", what could we say about the continuum hypothesis? If we adopt the axiom of choice, then the set of all real numbers can be well-ordered, i.e. it is in one-to-one correspondence with some cardinal c. But this cardinal must be somewhere on our 'aleph-scale":

Eb c = aleph_{b}.

We know already that b>0. The continuum hypothesis asserts
that each infinite set of real numbers is either countable, or
its cardinality is equal to c. Hence, on the
"aleph-scale" there are no cardinals between aleph_{0
}and c, i.e. c = aleph_{1}. Thus, to prove the
continuum hypothesis we must establish a one-to-one
correspondence between two fixed sets - the set of all real
numbers, and aleph_{1}. Of course, this conclusion
strengthened Cantor's trust in a forthcoming solution of the
continuum problem...

But the only (small!) success came as late as in 1905 when J.
Koenig proved his remarkable theorem (for details see Jech [1971]), and concluded from it
that c is not aleph_{w} (etc. c is not aleph_{w*2},
not aleph_{w*3}, ..., not aleph_{w*w}, etc. not
aleph_{b} for all countable limit ordinals b).

**J.Koenig.** Zum Kontinuum-Problem. "Math.
Annalen", 1905, Vol.60, pp.177-180

That is almost all we know today. Nobody has succeeded in
proving that c is not aleph_{2}, not aleph_{3}
etc.

We know today the cause of these difficulties...

The first step of the solution is due to Kurt Goedel who proved in 1938 that one can assume in ZF the axiom of choice (AC) and the continuum hypothesis (CH) safely: if the theory ZF is consistent, then so is ZF+AC+CH (i.e. ZFC+CH).

**K.Goedel.** The consistency of the axiom of choice and of
the generalized continuum hypothesis. "Acad. U. S. A.",
1938, Vol 24, pp.556-557.

I.e., if we could derive a contradiction from AC and/or CH, then we could derive a contradiction already from the axioms of ZF. The consistency conjecture of a theory T is denoted traditionally by Con(T). In these terms Goedel's result is put as follows:

Con(ZF) -> Con(ZF+AC+CH).

It should be noted that Goedel proved not only the "safety" of CH. He proved simultaneously - and by the same method - the "safety" of the "black magic" - the axiom of choice! You can criticize AC as impossible or false, but as means of theoretical reasoning it is as safe as are the axioms of ZF!

Goedel's method could be derived from an idea by D. Hilbert, published in 1925:

**D. Hilbert.** Ueber das Unendliche. "Math.
Annalen", 1925, Vol. 95, pp. 161-190.

Namely, if you are continuously failing in **building** of
sets with cardinalities between aleph_{0} and c, then you
may try to prove that there are no "**constructible**"
sets having this property. I.e. maybe, such sets do exist, but
they cannot be **constructed**? Maybe, this kind of proof will
be easier than a 100% proof of the continuum hypothesis?

**Goedel's operations** (version of Jech [1971])

G_{1}(u, v) = {u, v} (pairing),

G_{2}(u, v) = u - v (difference of sets),

G_{3}(u, v) = u x v (product of sets),

G_{4}(u) = domain (u),

G_{5}(u) = {(t_{1}, t_{2}) | t_{1},
t_{2} in u & t_{1} in t_{2} }
("in" projected on u),

G_{6}(u) = {(t_{1}, t_{2}, t_{3})
| (t_{2}, t_{3}, t_{1}) in u },

G_{7}(u) = {(t_{1}, t_{2}, t_{3})
| (t_{3}, t_{2}, t_{1}) in u },

G_{8}(u) = {(t_{1}, t_{2}, t_{3})
| (t_{1}, t_{3}, t_{2}) in u } (enable
permutations).

Here, (t_{1}, t_{2}, t_{3}) is
defined, of course, as ((t_{1}, t_{2}), t_{3}).
How could we define the class of all sets that can be built
"from nothing" by means of Goedel's operations?

closure (u) = {t | t in u, or t can be built from members of u by means of a finite superposition of Goedel's operations }

Let us define (by transfinite recursion) the following
sequence of sets {L_{b} | b in On}:

L_{0} = o;

L_{b} = U{L_{c} | c<b } for a limit ordinal
b,

L_{b+1} = {u | u<=L_{b} & u in closure
(L_{b}U{L_{b}} }.

The second rule of this definition does not create new sets,
it only collects all sets that have been created so far. The only
creative rule is the third one: members of L_{b+1} are
built from members of L_{b} and L_{b} itself by
means of finite superpositions of Goedel's operations. The
addition of "L_{b} itself" is necessary, since
L_{b} is closed under Goedel's operations.

The class L = U{L_{b} | b in On} is called the **constructible
universe**, and its members are called **constructible sets**
(i.e. sets that can be built "from nothing" by means of
Goedel's operations. It appears that L contains all ordinals,
i.e. it is a proper class.

Goedel proved two theorems that are equivalent to the following (proofs can be found, for example, in Jech [1971]);

1) ZF proves: if all sets were constructible, then AC and CH were true.

2) In L, all axioms of ZF are true, i.e. if ZF is consistent, then so is ZF+ "all sets are constructible".

Hence, we can add the axiom of choice and continuum hypothesis
to ZF as axioms safely. And we **cannot hope to disprove the
continuum hypothesis** in ZFC.

Traditionally, V=L is used as a shortcut for the statement "all sets are constructible". Using this shortcut, the above Goedel's theorems can be put as follows:

1) ZF + V=L -> AC & CH.

2) Con(ZF) -> Con(ZF + V=L).

Hence, Con(ZF) -> Con(ZF+AC+CH), or, if you like it better
- Con(ZF) -> Con(ZFC+CH), or Con(ZF) -> Con(ZFC + c=aleph_{1}).

Unlike to the "radical" AC having rich and even fantastic, incredible and even "impossible" consequences, the continuum hypothesis as an axiom of set theory would be a poor axiom - due to its poor consequences. But unexpectedly, it appears that the Goedel's "technical" statement V=L is even richer than AC!

At first glance, Goedel's collection of set operations introduced above seems accidental. But the following result shows that this is not the case:

If some class M is a model of ZF (i.e. all axioms of ZF are true on M), and if M contains all ordinals, then M>=L (i.e. M contains all Goedel's constructible sets).

For details, see Jech [1971]. Hence, in a sense, the sets that can be built "from nothing" by using Goedel's "technical" operations, form the minimum universe of sets for which all axioms of ZF are true. And hence, Goedel's collection of operations is not accidental at all. In some other books on set theory you can find different collections of operations that generate the same constructible universe L.

**Open problem?** Let us consider any finite collection s
of absolute (see Jech [1971])
operations, and let us define the class L(s) as above. We know
already that if L(s) were a model of ZF containing all ordinals,
then L(s)>=L. But, maybe, under these conditions, L(s)=L?

Goedel's result of 1938 did not contradict the Cantor's
opinion (Cantor died in 1918) that the continuum hypothesis
"must be" provable. But some 25 years later - in 1963 Paul
Cohen invented a new method (the famous **method of forcing**),
which allowed to prove that

Con(ZF) -> Con(ZFC + c=aleph_{2}),

Con(ZF) -> Con(ZFC + c=aleph_{3}),

...

Con(ZF) -> Con(ZFC + c=aleph_{b+1}),

for any finite or countable ordinal b. Hence, you can adopt safely as an axiom any of the following assertions:

c=aleph_{1}, c=aleph_{2},
c=aleph_{3}, ...

and even (a joke by N.N. Luzin, see Keldysh [1974]) that c=aleph_{17}.

Some facts about this second turning point in the history of mathematical logic from Infinite Ink: The Continuum Hypothesis by Nancy McGough:

April 2, 1934 | Cohen, Paul born |

April, 1963 | Cohen circulated notes about independence of CH |

May 3, 1963 | Cohen lectured on independence of CH |

**P.J. Cohen.** The Independence of the Continuum
Hypothesis. "Proc. Nat. Acad. Sci. U. S. A.", 1963,
vol. 50, pp.1143-1148.

**P.J. Cohen.** The Independence of the Continuum
Hypothesis. II."Proc. Nat. Acad. Sci. U. S. A." 1964,
vol. 51, pp. 105-110.

Cohen's method of forcing allows proving also that the axiom of choice (of course!) can not be derived from the (normal!) axioms of ZF. Cohen proved this in a very strong form:

Con(ZF) -> Con(ZF + Q),

where Q asserts the following: there is a countable set x consisting of unordered pairs (members of these pairs being sets of real numbers) such that there are no selection functions for x. Hence, the axioms of ZF alone cannot prove the existence of a selection function even for a countable set of pairs!

Platonist interpretation of Cohen's results: click here.

My formalist interpretation. We have proved (in ZFC) that
there is an ordinal b such that c=aleph_{b}, but we
(using our axioms of ZFC) are not able to "calculate"
the exact unique value of b. Does it mean that our axioms do not
conform to the "world of sets"? To avoid a dead-end, I
propose better to think that **our axioms simply are not perfect**,
so let us "simply" try to improve them - ignoring the
mystical "world of sets". And it appears that we can
have here different (even contradictory!), yet very exciting
development scenarios.

The first scenario - let us adopt V=L as an axiom of set
theory and call it the **axiom of constructibility**. I.e. let
us assume that there are only constructible sets in the
"world of sets", and let us work in the theory ZF+V=L.
As an axiom, V=L is very powerful: it implies the axiom of choice
and allows proving of the continuum hypothesis. It allows solving
also of some other problems that have been proved undecidable for
ZFC (for a detailed account - see Devlin
[1977]). Let us consider one of them - the problem formulated
by M.
Suslin (1894 - 1919, the paper was published in 1920).

**Suslin's problem.** Let (p, <) be a linearly ordered
set such that:

a) p does not contain neither minimum, nor maximum members.

b) p is dense (i.e. if x, y in p and x<y, then there is z in p such that x<z<y).

c) p is complete (i.e. each bounded non-empty subset of p has (in p) the least upper bound and the greatest lower bound.

d) Every set of non-intersecting intervals of p is finite or countable.

The set of all real numbers possesses these properties. Suslin conjectured that every ordered set (p, <) having the properties (a, b, c, d) must be isomorphic to the set of all real numbers (Suslin's hypothesis - SH).

**Exercise 2.27.** Show (in ZFC) that SH is equivalent with
the following assertion: every linearly ordered set (p, <)
possessing the properties (a, b, c, d) contains a countable dense
subset.

Suslins's problem possess the "taste" of the continuum problem: it seems involved in "the very nature" of the real number system, and hence, if our axioms are perfect, it "must be" solved.

But this is not the case - Suslin's problem is undecidable for ZFC:

Con(ZF) -> Con(ZFC+SH),

Con(ZF) -> Con(ZFC+~SH).

The first result was proved by R. Solovay and S. Tennenbaum [1971], the second one - by R. Jensen [1968]. Jensen proved that the axiom of constructibility allows disproving SH, i.e. we can derive from V=L the existence of a linearly ordered set (p, <) that possesses the properties (a, b, c, d), but is not isomorphic to the set of all real numbers (see a version of this proof in Jech [1971]).

Thus, a very natural problem that "must be" solved by a perfect axiom system of set theory, is undecidable for ZFC, but can be solved in ZF+V=L. Hence, ZF+V=L is a "better" set theory than ZFC?

One of the most beautiful proofs in ZF+V=L is due to Dana Scott: if V=L, then the so-called measurable cardinals do not exist:

**D.Scott.** Measurable cardinals and constructible sets.
"Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom.
Phys.", 1961, vol. 9, pp.521-524 (see Jech [1971])

Goedel never believed in V=L as a possible axiom of set theory. So do most people today. Maybe, they do not like V=L as a very long formula? If you wish, verify that the full form of V=L in the language of set theory contains thousands of characters (I did this work in 1975 by using a mainframe computer).

**Open problem?** As we know from the exercise 2.14, the
full (i.e. comprehension) form of the infinity axiom is longer
than "it should be". But it can be replaced by a much
shorter (non-comprehension) axiom. How short can be made a
replacement of V=L?

The second argument against V=L as an axiom: it is not an "obvious" assertion about sets - "why" should all sets be constructible? Ask in ZF or in ZFC: how many constructible sets of natural numbers exist? Or (it is the same): how many constructible real numbers exist? In ZF+V=L, there are only constructible real numbers, i.e. there are uncountably many constructible real numbers. On the other hand, according to an unpublished result of Azriel Levy from 1963 (see Mostowski [1969]):

Con(ZF)->Con(ZFC+CH+"the set of all constructible real numbers is countable")

I.e. you may think safely also that there are only countably many constructible real numbers.

But why couldn't we investigate the consequences of all sets
being constructible? Is ZF+V=L a perfect set theory? Maybe, it
also contains its own "anomalies"? For example, in
ZF+V=L we can prove not only (as in ZFC) that each set can be
well ordered, but even more - that **there is a definable well
ordering of the class of all sets. **I.e. there is a (proper
class) function F: On->V such that AxEb(b in On &
F(b)=x)). Thus, F enumerates all sets using ordinals as numbers.

Hence, in ZF+V=L the set of all real numbers can be well ordered as well. But some people think that well ordering contradicts "the very nature" of real numbers - because of the extreme density and completeness of the natural ordering of these numbers. The assertion "real numbers cannot be well ordered" would be a poor axiom, but it could serve as a constraint that some people would use for selecting "better" axioms of set theory. Perhaps, these people would prefer another exciting alternative - the

This is an alternative scenario of developing set theory proposed in 1962 by Jan Mycielski and Hugo Steinhaus. The axiom of determinateness contradicts V=L and the axiom of choice.

**J.Mycielski, H.Steinhaus.** A mathematical axiom
contradicting the axiom of choice. "Bull. Acad. Polon. Sci.
Ser. Sci. Math. Astronom. Phys.", 1962, vol. 10, pp. 1-3

So, let us explain AD. Its terminology is based on infinite games proposed in 1953 by David Gale and F.M.Stewart:

**D.Gale, F.M.Stewart.** Infinite games with perfect
information. "Ann. Math. Studies", Princeton, 1953,
vol.28, pp.254-266

Let x is any set of real numbers. Let us associate with x the
following (infinite) **game** G_{x}. The first move:
player 1 specifies a binary digit (0 or 1) d_{1}, after
this, player 2 specifies a digit d_{2}. The second move:
player 1 specifies d_{3}, and player 2 specifies d_{4}.
Etc. Playing in this way ad infinitum (or so) some real number r
(0<=r<=1) is specified:

r = 0.d_{1}d_{2}d_{3}d_{4}...

If r belongs to x, then let us say that the player 1 **wins**
the game. Otherwise (i.e., if r is not in x), let us say that the
player 2 wins.

What could be called a **strategy** in this kind of games?
Of course, it is a function that associates with each finite
sequence of binary digits (the previous replies of the opposite
player) a single binary digit (the next move). If the player 1 is
using the strategy s, then the game will evolve in the following
way:

d_{1} = s(o) (o - the empty sequence),

d_{2} - reply of the player 2,

d_{3} = s(d_{2}),

d_{4} - reply of the player 2,

d_{5} = s(d_{2}, d_{4}),

...

Let us call the strategy s a **winning strategy for the
player 1 **in the game G_{x}, iff for any sequence d_{2},
d_{4}, d_{6}, d_{8}, ... (i.e. for **any**
sequence of replies of the player 2) the number

0.s(o)d_{2}s(d_{2})d_{4}s(d_{2},d_{4})d_{6}...

belongs to the set x. The definition of winning strategies for the player 2 is similar.

The set x is called a **determined set** iff for the game G_{x}
there exists either a winning strategy for the player 1, or a
winning strategy for the player 2.

**Exercise 2.28**. a) Show in ZF that if x is a finite or
countable set of real numbers, then the player 2 has a winning
strategy. Hence, all **countable sets are determined**.
In ZF we can prove determinateness also of many uncountable sets
of real numbers (see Kanovei
[1984] or Kleinberg [1977]).

b) Using the **axiom of choice**, show that there exist **undetermined
sets** of real numbers.

Since the existence of undetermined sets was never proven without the axiom of choice, some people think that the assertion

"every set of real numbers is determined"

(the axiom of determinateness, or AD) is consistent with the axioms of ZF.

**Open problem.** Prove or disprove, that Con(ZF) ->
Con(ZF+AD). Of course, Con(ZF) -> Con(ZF+~AD), since AD
contradicts V=L.

One more argument in favor of AD is its representation by using an infinite sequence of quantifiers (see Kanovei [1984]):

Ea_{0}Aa_{1}Ea_{2}...
((a_{0}, a_{1}, a_{2}, ...) in x) v Aa_{0}Ea_{1}Aa_{2}...
~((a_{0}, a_{1}, a_{2}, ...) in x).

The first part of this "formula" asserts the existence of a winning strategy for the player 1, the second part - the existence of a winning strategy for the player 2. Rewrite the second part in the following way:

Ea_{0}Aa_{1}Ea_{2}...
((a_{0}, a_{1}, a_{2}, ...) in x) v ~Ea_{0}Aa_{1}Ea_{2}...
((a_{0}, a_{1}, a_{2}, ...) in x),

and you will have ... the law of the excluded middle. If you do not wish to reject the law of the excluded middle, you "must" simply accept AD as "obvious".

**J.Mycielski.** On the axiom of determinateness.
"Fund. Math.", 1964, vol.53, pp.205-224

**Exercise 2.29**. In the traditional formulation of AD
sequences of natural numbers are used instead of real numbers.
Instead of specifying binary digits the players specify natural
numbers. And the determinateness is postulated for every set of
sequences of natural numbers. In the above paper, J.Mycielski
denotes this traditional form of AD by AD_{w}. The above
"binary" form of AD he denotes by AD_{2}. Prove
in ZF that AD_{2} and AD_{w} are equivalent (or
see the paper).

But the main argument in favor of AD is its extreme power, and the "regularity" of the set theory ZF+AD. First, AD contradicts the axiom of choice (AC) in its full form, but it retains the most useful parts of AC necessary to build a normal system of real numbers:

**Exercise 2.29**. a) Prove in ZF+AD the so-called
countable axiom of choice (AC_{w}), i.e. prove the
existence of choice functions for countable collections of
non-empty sets of real numbers.

b) Using AC_{w} prove that every infinite set of real
numbers contains a countable subset.

c) Using AC_{w} prove that the union of a countable
collection of countable sets of real numbers is countable.

J.Mycielski and S.Swierczkowski proved in 1964 that in ZF+AD every set of real numbers is Lebesgue-measurable. (In ZFC, using the axiom of choice we can "construct" a non-measurable set of real numbers - the well-known example of G.Vitali.)

**J.Mycielski, S.Swierczkowski.** On the Lebesgue
measurability and the axiom of determinateness. "Fund.
Math.", 1964, vol. 54, pp.67-71

In ZF+AD the **continuum hypothesis can be proved** in its
initial form: an infinite set of real numbers is either
countable, or it is equivalent to the entire continuum (i.e. the
set of all real numbers). This result follows easily from a
theorem about infinite games proved in 1964 by Morton Davis:

**M.Davis**. Infinite games of perfect information.
"Ann. Math. Studies", 1964, vol. 52, Princeton,
pp.85-101

In ZD+AD, the continuum cannot be well ordered (one can prove
that any well-ordered set of real numbers is finite or
countable). Hence, if c is the cardinality of the continuum, then
(of course) c>aleph_{0}, but (in ZF+AD) c is**
incompatible** with all the other alephs.

**Open problem?** How short can be made a replacement of
AD?

**Summary. **ZF+AD seems to be a kind of Miss World among
set theories.

Thus, both scenarios (axiom of constructibility and axiom of determinateness) have produced already a plentiful collection of beautiful and interesting results. These two set theories are at least as "good" as the traditional set theory, but they contradict each other, therefore we cannot speak here about the convergence to some unique "world of sets". And the Platonist "world of sets" possess some features of a mirage: it seems promising large amounts of water in the middle of a desert, but it does not keep the promise as you try to follow the vision.

Further reading about AD (it's worth to do!):

For people reading in Russian: the book by V.Kanovei [1984].

For people reading in English: the book by E.Kleinberg [1977].

For both: Handbook of Mathematical Logic edited by J.Barwise [1977].

Wilhelm Ackermann's approach to set theory differs from the Zermelo's approach. Zermelo and Fraenkel adopt those kinds of comprehension axioms that correspond to set construction principles used in real mathematics. Some 50 years later, Ackermann proposed one elegant principle instead (see the axiom A4 below):

**W.Ackermann.** Zur Axiomatik der Mengenlehre. "Math.
Annalen", 1956, Vol. 131, pp. 336-345.

The language of Ackermann's set theory differs from the standard language of set theory in two points:

a) Classes are allowed as values of variables (in the standard language only sets are allowed),

b) A constant V denoting the class of all sets is introduced. The assertion "x is a set" is expressed as "x in V".

Ackermann adopts the following axioms:

A1. **Axiom of Extensionality**

Az(z in x <-> z in y) -> x=y.

A2. **Class Construction Axiom Schema**

ExAy(y in x <-> y in V & F(y, z1, ..., zn),

where F is any formula that does not contain x as a free variable. This seems to be the full comprehension schema, but note that x is here a class, not a set! The second feature to be noted: members of x are sets, i.e. you cannot build classes containing proper classes as members.

A3. **Completeness Axiom** for V

y in x & x in V -> y in V;

y<=x & x in V -> y in V.

I.e. members of sets are sets, and subclasses of sets are sets also. The second part is similar to Zermelo's separation axiom schema.

A4. **Ackermann's Axiom Schema**

z_{1}, ..., z_{n} in V & Ay(F(y, z_{1},
..., z_{n}) -> y in V) -> Ex(x in V & Ay(y in x
<-> F(y, z_{1}, ..., z_{n})),

a where the formula F does not contain V, and does not contain x as a free variable.

For n=0 we have simply:

Ay(F(y) -> y in V) -> Ex(x in V & Ay(y in x <-> F(y)).

This axiom is dealing with the problem: when does a
comprehension axiom define a set? It always defines a class, but
when does it define a set? Ackermann's axiom gives an elegant
answer to this question: a formula F(y) defines a set, when F
does not contain V (of course!), and when you can **prove**
that F is satisfied only by sets!

A5. **Axiom of Regularity** (for sets only)

x in V & Ey(y in x) -> Ey(y in x & Az(z in x -> ~(z in y))).

Let us denote this set theory by A. If needed, the axiom of choice can be added to A.

How to compare such different theories as A and ZF? The
language of A allows to express many things that the language of
ZF does not - mainly because that variables of A range over sets
and classes, but variables of ZF - only over sets. Only if you
take a formula F of A that does not contain V, and restrict all
quantifiers in F to the domain V (i.e. replace any sub-formula
EuG(u) by a formula Eu(u in V & G(u)), and any sub-formula
AuG(u) by a formula Au(u in V -> G(u))), then you obtain a
statement within competencies of ZF. Let us denote this
restriction of the formula F by F^{V}.

**Levy-Reinhardt's theorem.** For all closed formulas F
from the language of ZF: ZF proves F, iff A proves F^{V}.

**A.Levy.** On Ackermann's set theory. "J. Symb.
Logic", 1959, Vol. 24, pp. 154-166 (if A proves F^{V},
then ZF proves F).

**W.Reinhardt.** Ackermann's set theory equals ZF.
"Ann. of Math. Logic", 1970, Vol. 2, pp. 189-249 (if ZF
proves F, then A proves F^{V}).

**Exercise 2.30**. Prove the simpler part of Reinhardt's
result, i.e. prove in A the following comprehension axioms of ZF:
separation, pairing, union, power-set, and infinity. Do not try
to prove the replacement axiom schema - this is possible, but
could appear too complicated.

One of the popular arguments against ZF (or ZFC) as the "right" set theory says that the axioms of ZF have been chosen "ad hoc". But Levy-Reinhardt's theorem shows that the real contents of these "ad hoc" axioms are not accidental - they equal the contents of a radically different set theory - Ackermann's theory A.

If axioms of ZF are considered as accidentally chosen, then so should be considered the "engineering" principles used in Turing machines. But the equivalence proofs of all the numerous radically different formal concepts of algorithm show that the real contents of Turing's principles are not accidental. This fact is expressed in the famous Church's thesis: the informal concept of algorithm (or computability) is equivalent to the numerous (mutually equivalent) formal concepts of algorithm.

Perhaps, now a similar "Church's thesis for set theories" could be formulated: comprehension axioms of ZF are maximal in the sense that no more powerful consistent set of comprehension axioms is possible? Is this an open problem? Is this true at all?

continuum hypothesis, axiom of constructibility, continuum problem, axiom of determinateness, constructibility, determinateness, axiom, set theory, descriptive, Ackermann, continuum

Back to title page.