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: x1, x2, ..., xn, where x1 is the first member, and xn 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),
...
w2=w*w - follows after all w*n (n - natural number),
...
ww - follows after all wn (n - natural number),
...
e0 (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 ww and e0 (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 k1 isomorphic to this ordering of P(k). Then k1 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 aleph0. This cardinal "measures" the cardinality of countable sets. The first uncountable cardinal is denoted by aleph1, the second uncountable cardinal - by aleph2, etc. After all alephn (n - natural number) follows the cardinal alephw , etc.
Exercise 2.25. a) Verify that alephw=U{alephn | 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 alephb for each ordinal b:
aleph0 = w,
alephb+1 = the least cardinal greater than alephb,
alephb = U{alephc | 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 = alephb 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 = alephb.
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 aleph0 and c, i.e. c = aleph1. 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 aleph1. 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 alephw (etc. c is not alephw*2, not alephw*3, ..., not alephw*w, etc. not alephb 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 aleph2, not aleph3 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 aleph0 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])
G1(u, v) = {u, v} (pairing),
G2(u, v) = u - v (difference of sets),
G3(u, v) = u x v (product of sets),
G4(u) = domain (u),
G5(u) = {(t1, t2) | t1, t2 in u & t1 in t2 } ("in" projected on u),
G6(u) = {(t1, t2, t3) | (t2, t3, t1) in u },
G7(u) = {(t1, t2, t3) | (t3, t2, t1) in u },
G8(u) = {(t1, t2, t3) | (t1, t3, t2) in u } (enable permutations).
Here, (t1, t2, t3) is defined, of course, as ((t1, t2), t3). 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 {Lb | b in On}:
L0 = o;
Lb = U{Lc | c<b } for a limit ordinal b,
Lb+1 = {u | u<=Lb & u in closure (LbU{Lb} }.
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 Lb+1 are built from members of Lb and Lb itself by means of finite superpositions of Goedel's operations. The addition of "Lb itself" is necessary, since Lb is closed under Goedel's operations.
The class L = U{Lb | 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=aleph1).
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=aleph2),
Con(ZF) -> Con(ZFC + c=aleph3),
...
Con(ZF) -> Con(ZFC + c=alephb+1),
for any finite or countable ordinal b. Hence, you can adopt safely as an axiom any of the following assertions:
c=aleph1, c=aleph2, c=aleph3, ...
and even (a joke by N.N. Luzin, see Keldysh [1974]) that c=aleph17.
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=alephb, 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 Gx. The first move: player 1 specifies a binary digit (0 or 1) d1, after this, player 2 specifies a digit d2. The second move: player 1 specifies d3, and player 2 specifies d4. Etc. Playing in this way ad infinitum (or so) some real number r (0<=r<=1) is specified:
r = 0.d1d2d3d4...
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:
d1 = s(o) (o - the empty sequence),
d2 - reply of the player 2,
d3 = s(d2),
d4 - reply of the player 2,
d5 = s(d2, d4),
...
Let us call the strategy s a winning strategy for the player 1 in the game Gx, iff for any sequence d2, d4, d6, d8, ... (i.e. for any sequence of replies of the player 2) the number
0.s(o)d2s(d2)d4s(d2,d4)d6...
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 Gx 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]):
Ea0Aa1Ea2... ((a0, a1, a2, ...) in x) v Aa0Ea1Aa2... ~((a0, a1, a2, ...) 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:
Ea0Aa1Ea2... ((a0, a1, a2, ...) in x) v�~Ea0Aa1Ea2... ((a0, a1, a2, ...) 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 ADw. The above "binary" form of AD he denotes by AD2. Prove in ZF that AD2 and ADw 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 (ACw), i.e. prove the existence of choice functions for countable collections of non-empty sets of real numbers.
b) Using ACw prove that every infinite set of real numbers contains a countable subset.
c) Using ACw 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>aleph0, 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
z1, ..., zn in V & Ay(F(y, z1, ..., zn) -> y in V) -> Ex(x in V & Ay(y in x <-> F(y, z1, ..., zn)),
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 FV.
Levy-Reinhardt's theorem. For all closed formulas F from the language of ZF: ZF proves F, iff A proves FV.
A.Levy. On Ackermann's set theory. "J. Symb. Logic", 1959, Vol. 24, pp. 154-166 (if A proves FV, 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 FV).
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.