Register to reply 
Zorn's lemma <==> Axiom of choice 
Share this thread: 
#1
Mar2410, 06:57 AM

Emeritus
Sci Advisor
PF Gold
P: 9,543

Where can I find the proof of the claim that Zorn's lemma is equivalent to the Axiom of choice?



#2
Mar2410, 07:09 AM

HW Helper
PF Gold
P: 1,961

Page 42 of "Mathematical Physics" by Robert Geroch has a proof of Zorn's lemma assuming the Axiom of Choice.



#3
Mar2410, 07:13 AM

HW Helper
PF Gold
P: 1,961




#4
Mar2410, 10:46 AM

Emeritus
Sci Advisor
PF Gold
P: 9,543

Zorn's lemma <==> Axiom of choice
Thanks. That looks like a really nice book. What he says on page 42 is an interesting comment, but it doesn't prove that the axiom of choice implies Zorn's lemma. (He isn't even using the axiom of choice).



#5
Mar2410, 11:38 AM

HW Helper
PF Gold
P: 1,961

Oh, sorry. I thought the "keep going, on and on" thing was equivalent to the axiom of choice. Looking at the wikipedia page on Zorn's lemma, it seems that the axiom of choice is implicitly used in defining the function which picks out an upper bound for each of the totally ordered sets that were constructed in the argument.



#6
Mar2410, 05:48 PM

P: 2,504

It seems Zorn considered his proposal (1935) more of an axiom than a theorem. His lemma is set theoretically equivalent to AC, but it's actually easier to "prove" AC from ZL then the reverse.
http://publish.uwo.ca/~jbell/Axiom%2...and%20Zorn.pdf EDIT: It turns out that a number of accepted mathematical statements are equivalent to AC. 


#7
Mar2410, 08:33 PM

Emeritus
Sci Advisor
PF Gold
P: 9,543

Thanks guys. After reading both Geroch and Wikipedia, I now have a pretty good idea about why AC implies ZL. (Geroch assumes AC and "not ZL" and constructs a "set" with more members than any set can have. This contradiction proves the implication). The article about AC and ZL says that the converse is much easier to prove, and includes a proof. I'll read it tomorrow. Too tired now.



#8
Mar2510, 10:01 AM

Emeritus
Sci Advisor
PF Gold
P: 9,543

I read the first proof of "ZL implies AC". The argument goes like this (I think): Consider [itex]\{A_ii\in I\}[/itex], with all the [itex]A_i[/itex] nonempty. Now define
[tex]\mathcal P=\Big\{f:J\rightarrow \bigcup_{i\in I}A_iJ\subset I, f(i)=A_i\text{ for all } i\in J\Big\}[/tex] and define a partial order on [itex]\mathcal P[/itex] by saying that [itex]f\leq g[/itex] if [itex]J_f\subset J_g[/itex] (where these last two sets are the domains of the functions f and g). Every totally ordered subset has an upper bound. (Just take the union of all domains of all the functions in the totally ordered subset. The result will be the domain of one of those functions, and that function is an upper bound for the subset). Now ZL asserts that [itex]\mathcal P[/itex] has a maximal element [itex]f_1[/itex] with domain [itex]I_1[/itex], and it's not hard to see that [itex]I_1=I[/itex]. (If not, we can find [itex]f\in\mathcal P[/itex] such that [itex]f_1\leq f[/itex] and [itex]f_1\neq f[/itex]). 


#9
Mar2710, 02:12 PM

P: 2,504

You can prove a number of results regarding ZL, AC, and other equivalences using the wellordering theorem (which is implicit in your proof). This theorem states that for any nonempty set there is a binary relation under which it is wellordered.



#10
Mar2710, 04:17 PM

Sci Advisor
P: 905

@Fredrik: that looks about right (I was searching for the word 'chain', but you used 'totally ordered subset' :P).
A proof of the converse that I learned, uses a lemma ("Hartog's Lemma"), which asserts "For every set X there is a wellordering (L_X,≤) such that there is no injective function from L_X to X". The proof of this lemma does not require AC or Zorn (of course, although naively you could think it says about the same). The idea of the proof is then as follows. Let (P,≤) be a poset in which every chain has an upper bound, and assume P has NO maximal element. Then, using the Axiom of Choice, we can show that in that case for every wellordered set L there is an embedding of L into P. This is a contradiction with Hartogs’ Lemma. If you're interested, I can give the proof, but maybe you don't like this approach. @SW VandeCarr: The wellordening theorem, ZL, AC, and e.g. the "Principle of Cardinal Comparability" (for any sets A and B we have A<=B or B<=A), are in fact all equivalent. I don't see how Fredrik would be implicitly using the wellordening theorem. Could you please elaborate? 


#11
Mar2710, 04:57 PM

P: 2,504




#12
Mar2810, 12:49 PM

Sci Advisor
P: 905

Yes, you are mistaking. In a typical proof using Zorn's Lemma, you have to show that every chain has an upper bound. Often the partial order is just set inclusion with function restriction: pairs (f,A) where f is a function with domain A, (f,A)<= (g,B) iff A is contained in B and the restriction of g to A equals f. In this case, a chain is a set of pairs (f_i,A_i) which are all comparable; it has as upper bound (h,X), where X is the union of all sets in the chain, and h is the (unique) function whose restricition to A_i equals f_i. This is just basic stuff about functions and sets, and has nothing to do with the wellordening theorem.



#13
Mar3110, 03:18 PM

P: 2,504




#14
Mar3110, 03:54 PM

Sci Advisor
P: 905




#15
Mar3110, 05:21 PM

P: 2,504

http://scienceblogs.com/goodmath/200...t_the_we_1.php 


#16
Mar3110, 05:37 PM

Sci Advisor
P: 905

I'm still not following. We agree that AC, ZL, and the WOT are all logically equivalent. Why, then, would the WOT be more fundamental than the others, or why should we regard AC and ZL as consequences of the WOT? Surely there's no logical reason, or are you talking about philosophy?
Besides, I think Fredrik's question is as clear as it can get. Whatever the context, it can't be misinterpreted. 


#17
Apr110, 03:40 AM

P: 2,504

http://books.google.com/books?id=TCI...d%20ZF&f=false. 


Register to reply 
Related Discussions  
Zorn's Lemma Problem  Calculus & Beyond Homework  6  
Zorn's Lemma Problem  Calculus & Beyond Homework  4  
Some questions on axiom of choice and zorn's lemma.  Set Theory, Logic, Probability, Statistics  0  
Zorn's lemma problem  Calculus & Beyond Homework  15  
Zorn's lemma without the axiom of choice  Set Theory, Logic, Probability, Statistics  26 