[Apronus Home] [ProvenMath] [Set Theory]
play piano online
Play Piano Online

AXIOM OF CHOICE AND ITS EQUIVALENTS

Axiom of choice (AC)
If I,Y are sets, A:I->Y and /\(x:-I) A(x) != O then
there exists a function f:I->u(Y) such that /\(x:-I) f(x):-A(x).

Axiom of choice (AC')
If X is a set, I = P(X)\{O} then
there exists a function f:I->X such that /\(A:-I) f(A):-A.

Well-ordering principle (WO)
If X is a set then there exists E c XxX such that
(X,E) is a well ordered set.

Definition S.AC.1 - Chain.
Let (X,E) be a partially ordered set.
Let LcE.
L is a chain in (X,E) if and only if /\(x,y:-L) xEy or yEx.

Definition S.AC.2 - Maximal element.
Let (X,E) be a partially ordered set.
Let m:-X.
m is a maximal element in (X,E) if and only if 
/\(x:-X) mEx => x = m.

Definition S.AC.3
Let (X,E) be a partially ordered set. 
L is a maximal chain in (X,E) if and only if
for every chain K c X 
if L c K then K = L. 

Hausdorff's maximal principle (HMP)
If (X,E) is a partially ordered set then 
there is a maximal chain in (X,E).

Zorn's Lemma (ZL)
If (X,E) is a partially ordered set such that
for every chain LcP, there is a y:-X such that /\(x:-L) xEy 
then there is a maximal element in (X,E).

Theorem S.AC.4
If we assume Axioms ZF1, ZF2, ZF3, ZF4, ZF5, ZF6
then AC, AC', WO, HMP and ZL are equivalent.

Proof
Assume (AC).
Take any set X. Let I = P(X)\{O}.
Let A:I->I such that /\(B:-I) A(B) = B.
Notice that u(I) = X.
By (AC) there exist a function f:I->X such that
/\(B:-I) f(B):-A(B). But /\(B:-I) A(B) = B.
Thus /\(B:-I) f(B):-B.
We have shown (AC')

Assume(AC').
Let I = P(X)\{O}.
By (AC') we have f:I->X such that /\(A:-I) A:-f(A).

Let AcX.
We will write that (A,E) is f-ordered if and only if
(A,E) is a well ordered set and 
/\(x:-A) f(X\{y:-A|yEx and x!=y}) = x.

We will show that
If (A,E) is f-ordered and (B,F) is f-ordered 
then 
(A c B and E c F and A is an initial segment of B) 
or 
(B c A and F c E and B is an initial segment of A).

Let H =
{x:-A | {y:-A | yEx and x!=y} != {y:-B | yFx and x!=y}}.
Assume to the contrary that H != O.
Since (A,E) is well ordered we have t:-H such that
/\(x:-H) tEx.
Let D = {y:-A|yEt and y!=t}.
We will prove that D is an initial segment of (B,F).

Take any d:-D.
Take any b:-B such that bFd.
Since dEt and d!=t, !(d:-H).
Thus {y:-A | yEd and y!=d} = {y:-B | yFd and y!=d}.
Thus d:-B and it shows that DcB.
If b = d then b:-D and then OK.
If b != d then b:-{y:-B | yFd and y!=d} = {y:-A | yEd and y!=d}
and then b:-A and bEd. By transitivity bEt and b!=t.
Then b:-D.
We have shown that D is an initial segment of (B,F).

It is true that (B=D or D!=B)

Assume that B = D.
We have just shown that 
if we take d:-D and b:-B such that bFd then bEd.
Then BcA and FcE and B is an initial segment of A.

Assume that B != D.
Then by Theorem S.O.8
there is a z:-B such that
D = {y:-B | yFz and y!=z}.
Since (B,F) is f-ordered, f(X\D)=z.
But (A,E) is also f-ordered. Thus f(X\D)=t.
So z = t.
Thus {y:-A | yEt and y!=t} = {y:-B | yFt and y!=t}.
So !(t:-H). Contradiction.
Thus /\(a:-A) {y:-A | yEa and y!=a} = {y:-B | yFa and y!=a}.
So AcB and EcF and A is an initial segment of B.

We have shown that 
If (A,E) is f-ordered and (B,F) is f-ordered 
then (A c B and E c F) or (B c A and F c E).

Notice that 
if (A,E) and (A,F) are well ordered set and EcF
then E=F.
So, If (A,E) and (A,F) are f-ordered then E=F.

Let K = {A:-P(X)|\/(EcAxA) (A,E) is f-ordered}.
Let M:K->P(AxA) and 
M(A)=E if and only if (A,E) is f-ordered.
Let C = u(K). And R = u(M(K)).
We will  show that
(1) C != O,
(2) (C,R) is f-ordered,
(3) C = X.

(1)
Let q = f(X).
({q},{(q,q)}) is f-ordered. Thus q:-C.

(2)
Take any x,y,z:-C.
We have x:-A1:-K, y:-A2:-K, z:-A3:-K.
{A1, A2, A3} is a chain in (K,c).
Let A = A1uA2uA3. It is obvious that A:-K.
Let E = M(A).
Thus (A,E) is a well ordered and x,y,z:-A.
So xEx,
if xEy and yEz then xEz,
and xEy and yEx then x=y.
Recall that EcR.
Thus (C,R) is a partially ordered set.

Take any W c C such that W != O.
Take any x:-W. There is a A:-K such that x:-A.
Let E = M(A).
Let V = W n A.
There is r:-V such that /\(v:-V) rEv.
Take any w:-W. 
There is a B:-K such that w:-B.
Let F = M(B).
If A is an initial segment of B 
then rFw by Theorem S.O.7.

And then rRw because FcR.
If B is an initial segment of A
then w:-V and rEw. 
And then rRw because EcR.
Since w:-W was arbitrarily chosen
and WcC was arbitrarily chosen, 
we have proved that 
/\(W) (WcC and W!=O => \/(r:-W)/\(w:-W) rRw).
Thus (C,R) is a well ordered set.

Now, to complete (2) 
we have to prove that (C,R) is f-ordered.

Take any x:-C.
We have to show that f(X\{y:-C | yRx and x!=y}) = x.
There is a A:-K such that x:-A.
Let E = M(A).
We will show that {y:-C | yRx and x!=y} = {y:-A | yEx and x!=y}.
Take any y:-C such that yRx and x!=y.
There is a B:-K such that y:-B.
Let F = M(B). Since FcR, yFx.
If A is an initial segment of B 
then y:-A and yEx because x:-A.
If B is an initial segment of A
then it is obvious then yEx and y:-A.
Thus y:-A and yEx and y != x.
So {y:-C | yRx and x!=y} c {y:-A | yEx and x!=y}.
And it is now obvious that
{y:-C | yRx and x!=y} = {y:-A | yEx and x!=y}.
Recall that A is f-ordered.
Thus 
x = f(X\{y:-A | yEx and x!=y}) = f(X\{y:-C | yRx and x!=y}).
We have proved (2).

(3)
Assume to the contrary that C != X.
Let G = X\C.
Let g = f(G).
Let C'=C u {g}.
Let R' = R u {(x,y):-XxX | x:-C' and y = g }.
It is obvious that (C',R') is a well ordered set.
f(X\{y:-C'|yR'g and y!=g}) = f(X\C) = g.
Thus (C',R') is a f-ordered set.
Thus C':-K and C'c C. Contradiction.
We have shown that C = X.

We have shown that (X,R) is a well ordered set.
Thus (WO) is shown.

Assume (WO)
We will show (HMP).
Let (X,E) be a partially ordered set.
By (WO) we have WcXxX such that 
(X,W) is a well ordered set.
We have m:-X such that /\(x:-X) mWx.
By Recursion Principle we have a function 
f:X->X such that
(1) f(m) = m,
            
           / x if {x} u {f(z)|zWx, z!=x} is a chain in (X,E),
(2) f(x)= {
           \ m otherwise.
		   
Let L = f(X).
Notice that m:-L.
We will show that L is a chain in (X,E).
Take any y1,y2:-L.
If y1 = m and y2 = m there is no problem.
If y1 = m and y2 != m then f(y2) = y2. 
Then by (2) {y2} u {f(z)|zWy2 and z!=y2} is a chain in (X,E).
Since f(m)=m, m:-{f(z)|zWx, z!=x}.
Thus y1Ey2 or y2Ey1.
If y1 != m and y2 != m then f(y1)=y1 and f(y2)=y2.
If y1 = y2 there is no problem.
Assume that y1Wy2.
Then by (2) {y2} u {f(z)|zWy2 and z!=y2} is a chain in (X,E).
y2 = f(y2) :- {f(z)|zWy2 and z!=y2}. 
Thus y1Ey2 or y2Ey1.
We have shown that L is a chain in (X,E).

We will show that L is a maximal chain in (X,E).
Take any chain K such that L c K.
Assume to the contrary that L != K.
We have k:-K and !(k:-L).
Thus f(k) = m.
Since m:-L, k!=m.
Thus {k} u {f(z)|zWk and z!=k} is not a chain in (X,E).
Thus there is a z:-X such that 
there is nither f(z)Ek nor kEf(z).
But f(z):-LcK. Contradiction.
Thus L = K.
We have shown that L is a maximal chain in (X,E).
Thus (HMP) is shown.

Assume (HPM)
We will show (LZ).
Let (X,E) be a partally oredred set such that
for every chain L in (X,E) 
there is y:-X such that /\(x:-L) xEy.

Let K be a maximal chain in (X,E).
Such a chain exists by (HPM).
We have z:-X such that /\(x:-K) xEz.
Take any q:-X such that zEq.
By transitivity K u {q} is a chain.
Thus K u {q} = K.
So q:-K. Thus qEz.
Thus q = z.
We have shown that z is a maximal element in (X,E).
Thus (LZ) is shown.

Assume (LZ)
We will show (AC).
Let I,Y be sets, A:I->Y and /\(x:-I) A(x) != O.
Let Z = 
{h:-Ixu(Y)|h is a function and /\(x,y)((x,y):-h => y:-A(x))}.
(Z,c) is a partially ordered set.
Take any chain L c Z.
Let g = u(L).
By Theorem S.C.14 g is a function.
Take any (x,y):-g. 
We have h:-L such that (x,y):-h. Thus y:-A(x).
So g:-Z.
Then every chain in (Z,c) is bounded.
By (LZ) we have f:-Z such that /\(h:-Z) f c h => h=f.
We will show that f:I->u(Y).
Assume to the contrary that that there is a p:-I  
such that /\(y:-u(Y)) !(p,y):-f.
Since A(p) != O, we have q:-A(p).
Let h = f u {(p,q)}. Thus f c h and h:-Z.
So f = h. Thus f:X->u(Y) and
/\(x:-X) f(x):-A(x).
(AC) is shown.    

[Apronus Home] [Contact Page] [ProvenMath Notation]