Talk:Zorn's lemma

From Wikipedia, the free encyclopedia

Contents 1 Axiomatic or not? 2 Movie? 3 Most useful? 4 maximal elements not unique 5 Kuratowski 6 Incomplete sentence?

The sketch of the proof may be too sketchy as it is not clear why the set P is exhausted.

---

Is it possible to think of any actual example that doesn't 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 choice? 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)

[edit] 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)

Well, but there's no clear intuitive motivation for "assuming Zorn", whereas there is for AC. I think most of us who believe Zorn's lemma is true, believe it because we believe AC is true, and ZL is provable from AC. That's a clear reason to consider ZL a theorem rather than an axiom. --Trovatore 17:23, 15 July 2005 (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)

[edit] 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 - 61.51.69.24 11:55, 21 Apr 2005 (UTC)

[edit] Most useful?

I've removed the claim that "Zorn's lemma is probably the most useful of the equivalents of the axiom of choice". That's a style question. Personally I essentially never use Zorn's lemma; I use the well-ordering principle and do a transfinite induction. --Trovatore 17:18, 15 July 2005 (UTC)

But Bourbaki led people to do the exact opposite, and that was more than half a century ago ... no need to learn transfinite induction, or even what an ordinal is. That was all quite deliberate and slanted. It is however true that if you ask where AC is hard to avoid in some or other form in graduate courses, say in functional analysis or proving algebraic closures exist, Zorn is pretty useful. Charles Matthews 20:03, 15 July 2005 (UTC)

So maybe there should be a note that Zorn's lemma was the preferred form in the style bourbachique. But I've never understood why people are afraid of transfinite induction, which I find very natural and intuitive, and even has a considerably more "constructive" feel to it than ZL. --Trovatore 20:07, 15 July 2005 (UTC)

[edit] maximal elements not unique

I just reverted an anon edit that claimed maximal elements are unique. That's not so. For an element to be maximal, it just has to be not less than any other element; it doesn't have to be greater than or equal to any other element. --Trovatore 23:27, 8 November 2005 (UTC)

For a simple example of this, take a set S with members A, B, and C, where A≤A, A≤B, A≤C, B≤B, and C≤C. S is partially ordered, every chain has an upper bound (since the only non-trivial chains are {A, B, ≤} and {A, C, ≤}, bounded respectively by B & C), and it contains two maximal elements, B & C. --Calair 23:51, 8 November 2005 (UTC)

[edit] Kuratowski

I have just reverted some changes that seemed to be trying to give additional credit to Kuratowski. While I think that's admirable (I was the person who added Kuratowski to the page in the first place, several months ago) I don't think the changes made in this case were good ones.

The changes added a redundant discussion of the discovery of the lemma, noting that Kuratowski disovered it in 1922 and Zorn in 1935. But this was already noted at the bottom of the article.

Another change changed the section title "Proof of Zorn's lemma" to "Proof of the Kuratowski-Zorn lemma". This would be fine if the article itself were titled "Kuratowski-Zorn Lemma", but it is not. The nomenclature should be consistent; if the article is "Zorn's Lemma", then that is what it should call the lemma. I would not object to moving the article to "Kuratowski-Zorn Lemma".

-- Dominus 23:54, 20 April 2006 (UTC)

Hm, I think I would object to such a move. "Zorn's lemma" is the common name. Besides, there's probably a reason it's the common name; did Kuratowski fail to publish it, perhaps? Remember the "Columbus principle": It's not who discovers something first, but rather who discovers it last. --Trovatore 01:30, 22 April 2006 (UTC)

I'm not arguing in favor of renaming it; I agree that the common name is "Zorn's Lemma". FYI,Kuratowski did indeed publish in 1922, thirteen years ahead of Zorn. -- Dominus 05:15, 22 April 2006 (UTC)

FYI: Ciesielski says (p.53): "M. Zorn proved this lemma in 1935 and published it in Bulletin AMS. The same theorem was proved in 1922 by K. Kuratowski and published in Fundamenta Mathematicae. This priority for this theorem belongs without any doubt to Kuratowski. However, in essentially all published sources the name Zorn is associated with this theorem and it seems that the battle for historical justice has been lost." -- Dominus

Aha: Fundamenta Mathematicae is the Journal of the Institute of Mathematics of the Polish Academy of Sciences. So there's your "reason": Kuratowski published in French in a Polish journal; Zorn in English in an American one. -- Dominus 05:24, 22 April 2006 (UTC)

So the story I heard recently is that Zorn explicitly acknowledged Kuratowski in the paper, and was apparently a bit embarrassed at having the lemma named after him. Kuratowski, for his part, apparently thought it was essentially due to Hausdorff (it's a trivial corollary of the Hausdorff maximal principle). My feeling is, everyone knows what Zorn's lemma is; historical accuracy in naming can go whistle. The article should try to get credit right in the text, but not in the name. --Trovatore 18:12, 13 May 2006 (UTC)

I agree. -- Dominus 16:37, 15 May 2006 (UTC)

[edit] Incomplete sentence?

The initial definition, "Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element," seems to be missing a word. Should the word "that" be added between "upper bound" and "contains"? If so, please add it. (I know too little about mathematics/set theory for me to feel comfortable changing anything in this article, although that sentence appears to have had the word "that" mistakenly omitted by its author.)

I don't think this is a mistake - it looks grammatically correct to me. The structure is parallel to this sentence:

"Any city in which every household has a telephone contains at least one phone exchange".

For 'any', substitute 'every' (which is equivalent in meaning here); for 'city', substitute 'non-empty partially ordered set'; for 'every household has a telephone', substitute 'every chain has an upper bound'; and for 'phone exchange' substitute 'maximal element'. --Calair 03:01, 16 June 2006 (UTC)

I agree it is not a mistake. Following the suggestion above would make the statement incorrect. -- Dominus 16:19, 16 June 2006 (UTC)