Zorn's lemma <=> Axiom of choice

In summary, the conversation discusses the relationship between Zorn's lemma and the Axiom of Choice. It is mentioned that page 42 of "Mathematical Physics" by Robert Geroch contains a proof of Zorn's lemma assuming the Axiom of Choice. There is also a discussion about whether AC implies ZL or vice versa. It is stated that a number of accepted mathematical statements are equivalent to AC. The conversation also mentions Hartog's Lemma and the well-ordering theorem as being related to these concepts. Finally, it is concluded that AC, ZL, and the well-ordering theorem are all set theoretically equivalent.
  • #1
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,877
422
Where can I find the proof of the claim that Zorn's lemma is equivalent to the Axiom of choice?
 
Physics news on Phys.org
  • #2
Page 42 of "Mathematical Physics" by Robert Geroch has a proof of Zorn's lemma assuming the Axiom of Choice.
 
  • #3
http://books.google.co.uk/books?id=wp2A7ZBUwDgC&lpg=PR1&ots=pre4weZ3Bo&dq=Mathematical%20Physics%20geroch&pg=PA42#v=onepage&q=&f=false [Broken]
 
Last edited by a moderator:
  • #4
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
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.
 
Last edited:
  • #6
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%20of%20Choice%20and%20Zorn.pdf [Broken]

EDIT: It turns out that a number of accepted mathematical statements are equivalent to AC.
 
Last edited by a moderator:
  • #7
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
I read the first proof of "ZL implies AC". The argument goes like this (I think): Consider [itex]\{A_i|i\in I\}[/itex], with all the [itex]A_i[/itex] non-empty. Now define

[tex]\mathcal P=\Big\{f:J\rightarrow \bigcup_{i\in I}A_i|J\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
You can prove a number of results regarding ZL, AC, and other equivalences using the well-ordering theorem (which is implicit in your proof). This theorem states that for any nonempty set there is a binary relation under which it is well-ordered.
 
Last edited:
  • #10
@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 well-ordering (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 well-ordered 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 well-ordening 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 well-ordening theorem. Could you please elaborate?
 
  • #11
Landau said:
@SW VandeCarr: The well-ordening 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 well-ordening theorem. Could you please elaborate?

I may be mistaken, but the well ordering theorem would seem to be implicit in any proof that requires the identification of a minimal or maximal element.
 
Last edited:
  • #12
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 well-ordening theorem.
 
  • #13
Landau said:
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 well-ordening theorem.

OK. I would argue that the comparability of pairs is a consequence of the well-ordering theorem (WOT). However, my real point was that, as you say; AC, ZL and WOT are all set theoretically equivalent. Therefore, logically one being true iimplies that the others are true. If one were false, the others would be false. (I'm using "true" in the sense: If P and Q, then P->Q.)
 
  • #14
SW VandeCarr said:
However, my real point was that, as you say; AC, ZL and WOT are all set theoretically equivalent. Therefore, logically one being true iimplies that the others are true. If one were false, the others would be false. (I'm using "true" in the sense: If P and Q, then P->Q.)
Yes, but I guess I'm missing your point (or maybe your point of your point).
 
  • #15
Landau said:
Yes, but I guess I'm missing your point (or maybe your point of your point).

I was simply putting some context around Fredrik's question,which was narrowly posed. It can be argued that WOT is more fundamental than AC or ZL. The important fact, IMHO is not that you can prove AC from ZL but that there is a larger set of propositions that are all based on the the assumption of a R(a,b) such that a set is well ordered.

http://scienceblogs.com/goodmath/2007/06/why_choice_is_important_the_we_1.php [Broken]
 
Last edited by a moderator:
  • #16
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
Landau said:
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.

Saying Frederik's question was narrowly posed was not a criticism. Also, I admit "more fundamental" is not a precise statement. I mean that the well ordering of the rational numbers can be proven within ZF, without C. To prove the well ordering of the reals you need AC, but AC can be proven from WOT. WOT could just as well be an axiom of ZF. However, I do have a question about this and will post a new thread.

http://books.google.com/books?id=TC...nepage&q=well ordering theorem and ZF&f=false.
 

1. What is Zorn's lemma and how is it related to the Axiom of Choice?

Zorn's lemma is a mathematical principle that states that if a partially ordered set satisfies a certain condition, then it must contain a maximal element. This lemma is closely related to the Axiom of Choice, as it can be used to prove the existence of a choice function for any collection of non-empty sets.

2. How does Zorn's lemma lead to the Axiom of Choice?

Zorn's lemma provides a way to prove the Axiom of Choice by showing that any collection of non-empty sets has a choice function. This is done by constructing a partially ordered set where each element corresponds to a choice function and using Zorn's lemma to show that there must be a maximal element, which is the desired choice function.

3. Why is the Axiom of Choice controversial?

The Axiom of Choice is controversial because it allows for the creation of sets that cannot be explicitly constructed or defined. This can lead to counterintuitive results and paradoxes, and some mathematicians argue that it goes against the foundational principles of mathematics.

4. Can Zorn's lemma be used to prove other mathematical theorems?

Yes, Zorn's lemma can be used to prove other theorems in mathematics, particularly in the fields of topology, set theory, and functional analysis. It has also been used to prove the existence of solutions to various optimization problems.

5. Are there any alternative principles to the Axiom of Choice?

Yes, there are several alternative principles that have been proposed as substitutes for the Axiom of Choice, such as the Axiom of Determinacy and the Axiom of Global Choice. These principles aim to avoid some of the counterintuitive consequences of the Axiom of Choice while still allowing for the creation of choice functions for collections of sets.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
435
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
392
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Back
Top