- #1

Fredrik

Staff Emeritus

Science Advisor

Gold Member

- 10,851

- 413

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Fredrik
- Start date

- #1

Fredrik

Staff Emeritus

Science Advisor

Gold Member

- 10,851

- 413

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

- #2

dx

Homework Helper

Gold Member

- 2,011

- 18

- #3

dx

Homework Helper

Gold Member

- 2,011

- 18

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

Fredrik

Staff Emeritus

Science Advisor

Gold Member

- 10,851

- 413

- #5

dx

Homework Helper

Gold Member

- 2,011

- 18

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

- 2,123

- 79

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.

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

Fredrik

Staff Emeritus

Science Advisor

Gold Member

- 10,851

- 413

- #8

Fredrik

Staff Emeritus

Science Advisor

Gold Member

- 10,851

- 413

[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

- 2,123

- 79

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

Landau

Science Advisor

- 905

- 0

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

I don't see how Fredrik would be implicitly using the well-ordening theorem. Could you please elaborate?

- #11

- 2,123

- 79

@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 allequivalent.

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

Landau

Science Advisor

- 905

- 0

- #13

- 2,123

- 79

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 i

- #14

Landau

Science Advisor

- 905

- 0

Yes, but I guess I'm missing your point (or maybe your point of your point).However, my real point was that, as you say; AC, ZL and WOT are all set theoretically equivalent. Therefore, logically one being true iimpliesthat 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.)

- #15

- 2,123

- 79

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

Landau

Science Advisor

- 905

- 0

Besides, I think Fredrik's question is as clear as it can get. Whatever the context, it can't be misinterpreted.

- #17

- 2,123

- 79

logicalreason, 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.

Share: