Talk:Zorn's lemma

Is it possible to think of any actual example that does'nt sound like:

An eigenspace E is transmorphicly Interpredentional to A Smetinon Eilder arraingement. See there's an example!

Suppose there's a hand full of apples and some oranges.. How does this thing apply?  :)

It's easy to provide trivial examples, but those will just leave people wondering "What's the big deal?" As long as we're dealing with finite sets, Zorn's Lemma is pretty much trivial, so you have to go to infinite-set examples to understand why it's not so simple. I'll have a stab at it, using arm-wrestling as an analogy. First off, let's look at the idea of a 'partially ordered set'.

If you have two people (call them Andy & Bob, or A & B), and one's much stronger than the other, he'll never lose. We'll denote this with the '≤' symbol: if I write 'A ≤ B', it means 'B will never lose to A'.

As a special case, note that you can't really lose against yourself, so we'll declare that 'A≤A' is always true. Note also that if A can never lose against B, and B can never lose against A, then they *have* to be the same person - that is, if B≤A & A≤B, A=B.

Next, note that if C is conclusively stronger than B, and B is conclusively stronger than A, then C is conclusively stronger than A. That is, if we have A≤B and B≤C then we also have A≤C.

But what happens if two people are of similar strength? Sometimes A will beat B, and sometimes B will beat A, depending on who's having a good day. In this case, we can't be sure how to rank the two against one another. In other words, neither 'A≤B' or 'B≤A' is true.

Between them, this gives us what's called a "partially ordered set". It's "ordered" in the sense that if C reliably beats B, and B reliably beats A, then C reliably beats A. The ordering is "partial" in the sense that there can be pairs of similar strength, where you can't convincingly rank one over the other.

For example: let's suppose Andy and Bob are adults of similar strength, Clark and Dana are Kryptonians - stronger than any human, but closely-matched against one another - and Eve and Francis are small children who'll always lose against an adult. This gives us a partial ordering - we know that Clark will always beat Bob, for instance, but we don't know whether Eve will always beat Francis.

Next, let's look at 'totally ordered'. A subset is 'totally ordered' if every possible pairing from that subset has one person conclusively stronger than the other. For instance, if we consider just Andy, Clark, and Eve, we know what the outcome will be for any two of them - there's enough separation to leave the result in no doubt.

Next, the 'upper bound' bit. For any given subset of people, an 'upper bound' is someone who can reliably beat them all. Sometimes you can find an upper bound within that subset (for instance, if you're looking at Andy, Eve, and Francis, Andy is an upper bound).

But sometimes you have to go outside it. For instance, if your subset is Andy, Bob, and Francis, Andy can't reliably beat Bob and vice versa. Instead, you have to pick Clark or Dana as 'upper bounds', since they *can* reliably beat any of these three.

A 'maximal element' then translates to "somebody who nobody else can reliably beat". In this case, both Clark and Dana are maximal elements; while each can be beaten by the other, it doesn't happen reliably. Zorn's Lemma says that if arm-wrestling works as we've described it among a certain set of people, and if every subset with enough separation between its members to make their ranking clear has somebody who can beat all its members, then there is somebody in the set who can't be reliably beaten by anybody else.

To see why those conditions are required, let's see what happens if we break them.

To break the requirement that the set be partially ordered, think about rock-paper-scissors. Paper reliably beats rock, scissors beat paper, rock beats scissors. Whatever you pick of those three, I can pick something that will reliably beat it; there is no 'maximal element'.

To break the requirement that every totally-ordered set has an upper limit: suppose we have an infinite number of people, named Andy1, Andy2, Andy3, ... and suppose that each Andy is stronger than anybody with a lower number. Look at the subset of Andys who have even numbers. This is totally-ordered (you can always find the stronger of two Andys by comparing numbers), but it doesn't have an upper bound - no matter how strong an Andy you pick, there's an even-numbered Andy just above who'll beat him. And this set has no 'maximal element'.

Hope this makes it slightly more understandable. (If anybody wants to nitpick this example, BTW, feel free.) --Calair 04:57, 11 Nov 2004 (UTC)

---

Is it possible to construct a vector space without a basis in ZF?

No. It is consistent with ZF that there exists such a vector space, but you can't actually construct one. (I'm assuming ZF is consistent, of course.) --Zundark, 2001 Dec 31

The reason being, if you could construct such a vector space and prove that it doesn't have a basis, then you would have proven that the axiom of choice must be wrong. But the axiom of choice is independent of ZF and therefore can't be proven wrong from within ZF. --AxelBoldt

Perhaps some clarification is in order. The question is open to interpretation. The negative answer might leave the impression that all of the vector spaces that might have no basis if we take the negation of AC are weird things that cannot be constructed. As I understand it, there are vector spaces that can be clearly pointed out, and whose existence is independent of AC, that might not have a basis. In fact among them are vector spaces that come up all the time in analysis. The things that can't be constructed are the basis sets that must exist if we do take AC. Or am I confused? Josh Cherry 16:10, 19 Oct 2003 (UTC)

The sort of thing: with AC you can show that the reals have a basis as a vector space over the rationals.

Charles Matthews 16:13, 19 Oct 2003 (UTC)

---

Zorn's Lemma gives rise to the worst maths joke ever:

What is yellow and equivalent to the axiom of choise? Zorn's Lemon.

• groan* ... -- Tarquin

Equal worst. What's purple and commutative? Charles Matthews 08:27, 28 Oct 2004 (UTC)

An Abelian grape, of course. Stan 13:52, 28 Oct 2004 (UTC)

(Hah, made ya link!) :-) Stan 13:52, 28 Oct 2004 (UTC)

---

Generally in Wikipedia one writes "Smith's theorem" and the like with a lower-case "t". Therefore "Zorn's lemma" with a lower-case "l" is appropriate. I have changed the capitals to lower case in the text and moved the page back to the version with the lower-case "l" in the title. Michael Hardy 00:00, 10 Nov 2003 (UTC)

Axiomatic or not?

The lead seems a little confused, in that it says Zorn is equivalent to axiom of choice, so then why is it a theorem? Probably just need to say it's conventional practice to use AoC as the axiom and derive Zorn from it. Is there a deeper reason, like AoC being simpler? Is there any advantage to making Zorn the axiom? Stan 18:41, 13 Oct 2004 (UTC)

Yes, probably. There's kind of a long history to all this though. Transfinite induction at one point would have been the preferred way to do things, but depends on having the ordinals. So those who wanted to ban the ordinals ... well, as I say, a long story. Basically people in grad school after 1955 were probably given Zorn, just because it gets results quickly, unless they were specialist logicians. It's all a can of worms as far as I'm concerned. The only reason for not assuming both AC and Zorn is a view of foundations that is too bossy, as far as I'm concerned. Charles Matthews 19:57, 13 Oct 2004 (UTC)

Within the context of an axiom system, it may be that two propositions P and Q are equivalent, but neither P nor [not P] follows from the axioms. In that case, either P or Q could be added as a new axiom, and the other would then be a theorem. The canons of mathematical logic leave the choice optional, as far as I know. Perhaps that is a deficiency in logic as now understood. Similarly, which of two characterizations of a mathematical object should be chosen to be "the definition" may be optional. Michael Hardy 20:24, 13 Oct 2004 (UTC)

The axiom of choice was considered more intuitively obvious than zorn's lemma. Also one should be careful when asserting that either could be taken as an axiom equally well, because they may only be equivalent on the assumptions of parts of ZF. That this is an issue can be shown by considering the two statements:

1) T is consistent. 2) There is a model of T.

These statements are equivalent (Gödel's completeness theorem. However the proof involves the power set . This means if we try to do model theory on fragments of ZF not containing Power set we can get into a muddle by assuming 1) implies 2) in this more limited setting. Barnaby dawson 17:48, 18 Feb 2005 (UTC)

Movie?

Zorn's Lemma is also the title of an experimental film by director Hollis Frampton, who currently does not rate an entry in Wikipedia. IMDB Record (http://www.imdb.com/title/tt0131149/) - 61.51.69.24 11:55, 21 Apr 2005 (UTC)