Our cookies follow Google AdSense policy.

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.3Let (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.4If we assume Axioms ZF1, ZF2, ZF3, ZF4, ZF5, ZF6 then AC, AC', WO, HMP and ZL are equivalent.ProofAssume (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.