Talk:Zorn's lemma/Archive 1

Untitled

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)

I've always chuckled at the saying "Zorn's lemma is neither." Jhinra (talk) 07:10, 5 February 2008 (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)

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)

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)

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)

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)

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)

I just reverted changes that replaced Zorn with Kuratowski-Zorn in the example application (but nowhere else). This is as per the discussion above: everyone calls it Zorn's lemma, the rest of the article uses Zorn's lemma, and the correct attribution is given at the beginning of the text. Magidin 18:33, 27 April 2007 (UTC)

Worth pointing out that Kuratowski's Lemma is subtly different. I just found this in Steven A. Gaal's "Point Set Topology": "It is fair to point out that Kuratowski's Lemma is not only simple in form ("each chain of a partially ordered set is contained in some maximal chain") but was also published considerably earlier ..." So whether it's correct to equate this to ZL is dubious. --Matt Westwood 06:27, 22 February 2012 (UTC)

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)

If it's confusing, how about adding commas to make it "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"? Randomity 23:15, 8 June 2007 (UTC)

I think the commas are a good idea and I've added them. My only concern with them is that someone might take the parenthetical to be part of the definition of "partially ordered set". Possibly remove the first comma, leaving the second? --Trovatore 23:26, 8 June 2007 (UTC)

The commas are incorrect: they do change the meaning of the sentence. With commas, the sentence asserts that every partially ordered set has the property mentioned; this is not true. The original version, without commas, was correct but difficult to parse. How about splitting the statement into two sentences? For example: "Suppose a partially ordered set has the property that every chain (i.e. totally ordered subset) has an upper bound. Then the set contains at least one maximal element." Jowa fan (talk) 03:51, 9 November 2010 (UTC)

Hmm? No, it doesn't mean that at all, with the commas. The commas create a restrictive clause in this case. --Trovatore (talk) 04:11, 9 November 2010 (UTC)

Just the same your version does seem clearer. --Trovatore (talk) 04:17, 9 November 2010 (UTC)

Cardinal comparability

Why is there a redirect from Cardinal comparability theorem to Zorn's lemma, and then the Cardinal comparability theorem isn't even mentioned here? The Cardinal comparability theorem deserves an article on its own (I know, it has been shown to be equivalent to Zorn's lemma, but nevertheless). By the way, I don´t know how to undo a redirect.Arfst 16:13, 15 June 2007 (UTC)

Good catch. I've retargeted the redirect to point to trichotomy (mathematics). --Trovatore 21:00, 15 June 2007 (UTC)

Definition of maximal element seems wrong

Maybe I am missing something, but the current description of maximal element in the article:

A maximal element of $P$ is an element $m$ in $P$ such that for any element $x$ in $P$, $x\leq m$

seems wrong to me. If this would be right, then in fact maximal elements would be unique. That condition is stronger than the one given in the article maximal element, which I consider correct. I am going to wait for a while for opinions/complaints before correcting the article. --zeycus 10:54, 17 June 2007 (UTC)

I agree. It should be $\lnot m\leq x$. -- Dominus 14:09, 17 June 2007 (UTC)

I think I fixed it in the definition (but it should be $m\not <x$). — Arthur Rubin | (talk) 15:29, 17 June 2007 (UTC)

Sorry if I jumped the gun here, but it is one of my specialties. — Arthur Rubin | (talk) 15:30, 17 June 2007 (UTC)

No problem, you fixed it just as I would have done it. --zeycus 8:54, 18 June 2007 (UTC)

Chevalley

An anonymous editor has twice added discussion of Chevalley to the lead of the "History" section, which then read:

Zorn's lemma was first proved by K. Kuratowski in 1922 who derived it from the Hausdorff maximal principle, but no one paid attention. In particular, Chevalley knew nothing of Kuratowski's work when he recommended that Zorn employ an unpublished theorem of Chevalley's to simplify a proof in a manuscript by Zorn. The revised manuscript was published as Zorn (1935), and this time the mathematics community sat up and paid attention, whence the name "Zorn's Lemma."

This has twice been reverted; no reason was given.

However, it is likely inaccurate, since it contradicts Zorn's own account, as given on pages 83–85 of Paul J. Campbell, The Origin of “Zorn's Lemma”, Historia Mathematica 5 (1978), pp. 77–89. Zorn did his work in 1933, Chevalley in 1936, after the publication of Zorn 1935. Chevalley's work was published as Bourbaki in 1939. It seems that Chevalley got the principle from Zorn, and not the other way around. (Also see the chart on page 78.)

-- Dominus 14:09, 14 November 2007 (UTC)

it may also be worth mentioning that the Bourbaki version of Zorn's lemma in Théorie des Ensembles (1939) is actually attributed to Zorn; it is called "le théorème de Zorn". -- Dominus 14:31, 14 November 2007 (UTC)

Correction of the sketch of proof?

The proof sets a_w = b({a_v: v < w}), i.e. equal to the upper bound. But it should be that a_w is chosen among the members that are larger than the upper bound. While an upper bound is allowed to be larger than any member of the set in question, it has no obligation to do so. PerezTerron (talk) 07:08, 28 January 2008 (UTC)

b(T) was defined to be something larger than an upper bound of T, so it does work. (Or seems to, to me, anyway...) — Arthur Rubin | (talk) 07:22, 28 January 2008 (UTC)

Zornification

Is there a place to mention the convenience term "Zornification" (an application of Zorn's Lemma)? Is has become quite common. 89.139.82.136 (talk) 11:18, 4 March 2008 (UTC)

It has? — Carl (CBM · talk) 18:23, 16 May 2009 (UTC)

Not really quite common, at least not in contemporary literature, but also not quite unknown: 11 English-language hits on Google Scholar. I guess it might be used more in informal contexts, though. This e2 node is enlightening as to what it could mean, but not as to its actual usage. —JAO • T • C 18:57, 16 May 2009 (UTC)

never heard in my life... if it really exists, it has to be a jargon of some small minority, therefore I'd be glad to be politically uncorrect, and censore the term --pma (talk) 21:09, 12 November 2009 (UTC)

A Google Books search finds it in texts by Thomas Hungerford, Kaplansky, and Halmos, so it appears to be in use by well-known, important authors. I think this weighs heavily against removing it. —Dominus (talk) 14:26, 13 November 2009 (UTC)

Kuratowski Zorn?

The page currently says the result is sometimes called the Kuratowski-Zorn lemma. Is that true? I have never heard it called that ever. -- Walt Pohl (talk) 20:50, 1 October 2009 (UTC)

[1] [2] It is tempting to conclude that the usage is mostly confined to Polish writers. —Dominus (talk) 05:34, 2 October 2009 (UTC)

the whole soviet block (zone after the Second War) calls it Kuratowski-Zorn. --Roman 195.95.144.249 (talk) 11:26, 7 December 2011 (UTC)

Applications

It should be very nice to add a list (not exhaustive, of course) of applications in various topics of mathematics (set theory, ordered structures, algebra, topology, functional analysis, measure theory,.....) with links to wiki articles. --pma (talk) 21:14, 12 November 2009 (UTC)

Kuratowski sits over there

“ There is an unverifiable anecdote that relates that Kuratowski was once attending a conference at which Zorn was a speaker. During his talk, Zorn referred to Zorn's lemma, and then paused and said—“Zorn is me, and over there sits Professor Kuratowski, who proved it first.” ” — Benedetto, John J.; Czaja, Wojciech. Integration and Modern Analysis. p. 78. as found on books.google [3]

Similar citation in the sample chapter (PDF, page 10 of 12) of unknown book in MAA.

Is it worth adding to the article...? --CiaPan (talk) 10:53, 3 February 2010 (UTC)

Seems strange; we would be providing a citation that states that the anectode is unverifiable. Sounds like verifying unverifiability... Magidin (talk) 16:01, 3 February 2010 (UTC)

What is verifiable, and reliably sourced, is that the anecdote exists. —Dominus (talk) 17:43, 3 February 2010 (UTC)

That's right. However, the anecdote belongs rather to maths folklore and Zorn's biography (as it shows what fair man he was) and not to the lemma's history. That's why I wonder whether we should add it here.
BTW, if we decide to add it, should it be under 'History' or rather in a separate section (and what would be the section name)? --CiaPan (talk) 11:00, 4 February 2010 (UTC)

Restrict to non-empty sets?

Should the statement of the theorem be, "Every non-empty partially ordered set, in which every non-empty chain has an upper bound, contains at least one maximal element"? Benja (talk) 23:22, 1 July 2010 (UTC)

Well, every element is an upper bound for the empty chain (assuming your definitions allow for an empty chain), so you don't need the second "nonempty". The first one is a reasonable point — I'm not sure whether it's standard or not to require partially ordered sets to be nonempty; I guess it could go either way depending on whether you want it to be a structure (structures are typically required to have nonempty universe). --Trovatore (talk) 23:31, 1 July 2010 (UTC)

Actually, it turns out you don't need either, but this has caused confusion before: the article used to have the first "non-empty", but it was

• removed by Chinju on 14 October 2007 with the argument "If every chain has an upper bound, then the empty set, being a chain, has an upper bound, and thus the poset is nonempty",
• added back by an anonymous user on 12 November 2007 without argument, and
• removed again by CBM on 12 November 2007 with the argument that "the empty set, being a chain, will have an upper bound, and thus it is not necessary to explicitly assume the poset is nonempty".

I was under the misapprehension that the upper bound needed to be in the subset, which of course it doesn't. In any case, thanks for the answer! Benja (talk) 23:44, 1 July 2010 (UTC)

Equivalent Forms of ZL

The current version of article says:

The simplest way to prove the equivalence is to use a cyclic proof. That is, we prove a cycle of implications as follows:

Axiom of Choice $\Rightarrow$ Well-Ordering $\Rightarrow$ Hausdorff $\Rightarrow$ Zorn's Lemma $\Rightarrow$ Axiom of Choice

Is there any reason why this order is chosen in the proof (which is not sketched here)? I would go precisely in the opposite direction (both ZL=>WO and WO=>AC seem to be very natural and easy to me, ZL<=>PM seems to be relatively straightforward, the only tricky part is AC=>ZL; especially if we want to avoid transfinite induction).--Kompik (talk) 14:43, 8 November 2010 (UTC)

Aside here: I've never understood why people want to avoid transfinite induction. In fact the uses of Zorn's lemma in algebra often strike me as really unintuitive; many times there's a simple and natural induction (using a wellordering) that shows much better what's really going on. --Trovatore (talk) 20:01, 17 November 2010 (UTC)

I would agree with you on that. I find transfinite induction very useful. However, some textbooks (I remember Halmos, but for sure you can find more) give a prove of ZL without transfinite induction, since ordinals are defined only later. --Kompik (talk) 15:03, 20 November 2010 (UTC)

Just to make a little clearer what I want to say. I do not claim that this type of cycle is substantially simpler that the one given in the article - depending on what type of the proof you choose. But claiming that something is the simplest way to prove this equivalence seems to me to be an overstatement. --Kompik (talk) 09:20, 17 November 2010 (UTC)

I've removed the factoid. As you say, there are several ways of proving the equivalence, of similar complexity, and without giving more details of the proof it was not actually conveying any useful information.—Emil J. 11:17, 17 November 2010 (UTC)

Upper bound or least upper bound?

The existence of upper bounds don't guarantee the existence of least upper bounds, and the proof I know requires that the poset is chain complete, i.e. each totally ordered subset has a least upper bound (not just an upper bound). — Preceding unsigned comment added by 131.111.248.243 (talk) 14:20, 10 October 2012 (UTC)

The standard proof (whose sketch is even included in the article) does not use this stronger assumption.—Emil J. 15:19, 10 October 2012 (UTC)