Quaternion

2014-01-27T23:40:14Z

128.111.159.205: /* Multiplication of basis elements */

{{For|the film by Hollis Frampton|Zorns Lemma (film)}}

'''Zorn's lemma''', also known as the '''Kuratowski–Zorn lemma''', is a proposition of [[set theory]] that states:

<blockquote>
Suppose a [[partially ordered set]] ''P'' has the property that every [[Total order|chain]] (i.e. [[Total order|totally ordered]] [[subset]]) has an [[upper bound]] in ''P''. Then the set ''P'' contains at least one [[maximal element]].
</blockquote>

It is named after the [[mathematician]]s [[Max August Zorn|Max Zorn]] and [[Kazimierz Kuratowski]].

The terms are defined as follows. Suppose (''P'',≤) is a [[partially ordered set]]. A subset ''T'' is ''totally ordered'' if for any ''s'', ''t'' in ''T'' we have ''s'' ≤ ''t'' or ''t'' ≤ ''s''. Such a set ''T'' has an ''upper bound'' ''u'' in ''P'' if ''t'' ≤ ''u'' for all ''t'' in ''T''. Note that ''u'' is an element of ''P'' but need not be an element of ''T''. An element ''m'' of ''P'' is called a ''maximal element'' (or ''non-dominated'') if there is no element ''x'' in ''P'' for which ''m'' < ''x''.

Note that ''P'' is not required to be non-empty.
However, the empty set is a chain (trivially), hence is required to have an upper bound, thus exhibiting at least one element of ''P''.
An equivalent formulation of the lemma is therefore:

<blockquote>
Suppose a non-empty partially ordered set ''P'' has the property that every non-empty chain has an upper bound in ''P''. Then the set ''P'' contains at least one maximal element.
</blockquote>

The distinction may seem subtle, but proofs involving Zorn's lemma often involve taking a union of some sort to produce an upper bound.
The case of an empty chain, hence empty union is a boundary case that is easily overlooked.

Zorn's lemma is equivalent to the [[well-ordering theorem]] and the [[axiom of choice]], in the sense that any one of them, together with the [[Zermelo–Fraenkel axioms]] of [[set theory]], is sufficient to prove the others. It occurs in the proofs of several theorems of crucial importance, for instance the [[Hahn–Banach theorem]] in [[functional analysis]], the theorem that every [[vector space]] has a [[basis (linear algebra)|basis]], [[Tychonoff's theorem]] in [[topology]] stating that every product of [[compact space]]s is compact, and the theorems in [[abstract algebra]] that every nonzero [[ring (algebra)|ring]] has a [[maximal ideal]] and that every [[field (mathematics)|field]] has an [[algebraic closure]].

==An example application==
We will go over a typical application of Zorn's lemma: the proof that every nontrivial ring ''R'' with [[Unital ring|unity]] contains a [[maximal ideal]]. The set ''P'' here consists of all (two-sided) [[ideal (ring theory)|ideal]]s in ''R'' except ''R'' itself, which is not empty since it contains at least the trivial ideal {0}. This set is partially ordered by [[subset|set inclusion]]. We are done if we can find a maximal element in ''P''. The ideal ''R'' was excluded because maximal ideals by definition are not equal to ''R''.

We want to apply Zorn's lemma, and so we take a non-empty totally ordered subset ''T'' of ''P'' and have to show that ''T'' has an upper bound, i.e. that there exists an ideal ''I'' ⊆ ''R'' which is bigger than all members of ''T'' but still smaller than ''R'' (otherwise it would not be in ''P''). We take ''I'' to be the [[union (set theory)|union]] of all the ideals in ''T''. Because ''T'' contains at least one element, and that element contains at least 0, the union ''I'' contains at least 0 and is not empty. Now to prove that ''I'' is an ideal: if ''a'' and ''b'' are elements of ''I'', then there exist two ideals ''J'', ''K'' ∈ ''T'' such that ''a'' is an element of ''J'' and ''b'' is an element of ''K''. Since ''T'' is totally ordered, we know that ''J'' ⊆ ''K'' or ''K'' ⊆ ''J''. In the first case, both ''a'' and ''b'' are members of the ideal ''K'', therefore their sum ''a'' + ''b'' is a member of ''K'', which shows that ''a'' + ''b'' is a member of ''I''. In the second case, both ''a'' and ''b'' are members of the ideal ''J'', and we conclude similarly that ''a'' + ''b'' ∈ ''I''. Furthermore, if ''r'' ∈ ''R'', then ''ar'' and ''ra'' are elements of ''J'' and hence elements of ''I''. We have shown that ''I'' is an ideal in ''R''.

Now comes the heart of the proof: why is ''I'' smaller than ''R''? The crucial observation is that an ideal is equal to ''R'' [[if and only if]] it contains 1. (It is clear that if it is equal to ''R'', then it must contain 1; on the other hand, if it contains 1 and ''r'' is an arbitrary element of ''R'', then ''r1'' = ''r'' is an element of the ideal, and so the ideal is equal to ''R''.) So, if ''I'' were equal to ''R'', then it would contain 1, and that means one of the members of ''T'' would contain 1 and would thus be equal to ''R'' – but we explicitly excluded ''R'' from ''P''.

The condition of Zorn's lemma has been checked, and we thus get a maximal element in ''P'', in other words a maximal ideal in ''R''.

Note that the proof depends on the fact that our ring ''R'' has a multiplicative unit 1. Without this, the proof wouldn't work and indeed the statement would be false. For example, the ring with <math>\Q</math> as additive group and trivial multiplication (i. e. <math>a b=0</math> for all <math>a,b</math>) has no maximal ideal (and of course no 1): Its ideals are precisely the additive subgroups. The [[factor group]] <math>\Q/A</math> by a proper subgroup <math>A</math> is a [[divisible group]], hence certainly not [[finitely generated abelian group|finitely generated]], hence has a proper non-trivial subgroup, which gives rise to a subgroup and ideal containing <math>A</math>.

== Sketch of the proof of Zorn's lemma (from the axiom of choice)==
A sketch of the proof of Zorn's lemma follows. Suppose the lemma is false. Then there exists a partially ordered set, or poset, ''P'' such that every totally ordered subset has an upper bound, and every element has a bigger one. For every totally ordered subset ''T'' we may then define a bigger element ''b''(''T''), because ''T'' has an upper bound, and that upper bound has a bigger element. To actually define the [[function (mathematics)|function]] ''b'', we need to employ the axiom of choice.

Using the function ''b'', we are going to define elements ''a''0 < ''a''1 < ''a''2 < ''a''3 < ... in ''P''. This sequence is '''really long''': the indices are not just the [[natural number]]s, but all [[ordinal number|ordinal]]s. In fact, the sequence is too long for the set ''P''; there are too many ordinals (a [[proper class]]), more than there are elements in any set, and the set ''P'' will be exhausted before long and then we will run into the desired contradiction.

The ''ai'' are defined by [[transfinite recursion]]: we pick ''a''0 in ''P'' arbitrary (this is possible, since ''P'' contains an upper bound for the empty set and is thus not empty) and for any other ordinal ''w'' we set ''a''''w'' = ''b''({''a''''v'': ''v'' < ''w''}). Because the ''a''''v'' are totally ordered, this is a well-founded definition.

This proof shows that actually a slightly stronger version of Zorn's lemma is true:
{{Quote|If ''P'' is a [[poset]] in which every [[well-order]]ed subset has an upper bound, and if ''x'' is any element of ''P'', then ''P'' has a maximal element that is greater than or equal to ''x''. That is, there is a maximal element which is comparable to ''x''.}}

==History==
The [[Hausdorff maximal principle]] is an early statement similar to Zorn's lemma.

[[Kazimierz Kuratowski|K. Kuratowski]] proved in 1922<ref>{{cite journal |first=Casimir |last=Kuratowski |title=Une méthode d'élimination des nombres transfinis des raisonnements mathématiques |trans-title=A method of disposing of transfinite numbers of mathematical reasoning |journal=[[Fundamenta Mathematicae]] |volume=3 |issue= |year=1922 |pages=76–108 |url=http://matwbn.icm.edu.pl/ksiazki/fm/fm3/fm3114.pdf |format=pdf |accessdate=2013-04-24 |language=French}}</ref> a version of the lemma close to its modern formulation (it applied to sets ordered by inclusion and closed under unions of well-ordered chains). Essentially the same formulation (weakened by using arbitrary chains, not just well-ordered) was independently given by [[Max August Zorn|Max Zorn]] in 1935,<ref>{{cite journal |first=Max |last=Zorn |title=A remark on method in transfinite algebra |journal=Bulletin of the American Mathematical Society |volume=41 |year=1935 |issue=10 |pages=667–670 |doi=10.1090/S0002-9904-1935-06166-X }}</ref> who proposed it as a new [[axiom]] of set theory replacing the well-ordering theorem, exhibited some of its applications in algebra, and promised to show its equivalence with the axiom of choice in another paper, which never appeared.

The name "Zorn's lemma" appears to be due to [[John Tukey]], who used it in his book ''Convergence and Uniformity in Topology'' in 1940. [[Bourbaki]]'s ''Théorie des Ensembles'' of 1939 refers to a similar maximal principle as "le théorème de Zorn".<ref>{{harvnb|Campbell|1978|p=82}}.</ref> The name "[[:pl:lemat Kuratowskiego-Zorna|Kuratowski–Zorn lemma]]" prevails in Poland and Russia.

{{Portal|Mathematics}}

==Equivalent forms of Zorn's lemma==
Zorn's lemma is equivalent (in [[Zermelo–Fraenkel set theory|ZF]]) to three main results:
# [[Hausdorff maximal principle]]
# [[Axiom of choice]]
# [[Well-ordering theorem]].

Moreover, Zorn's lemma (or one of its equivalent forms) implies some major results in other mathematical areas. For example,
# Banach's extension theorem which is used to prove one of the most fundamental results in functional analysis, the [[Hahn–Banach theorem]]
# Every vector space has a [[Hamel basis]], a result from linear algebra (to which it is equivalent<ref>{{cite journal
|last = Blass
|first = Andreas
|year = 1984
|title = Existence of bases implies the Axiom of Choice
|journal=Contemp. Math.
|volume = 31
|pages = 31–33
|ref=blass
}}</ref>)
# Every commutative unital ring has a [[maximal ideal]], a result from ring theory
# [[Tychonoff's theorem]] in topology (to which it is also equivalent<ref>{{cite journal
|last = Kelley
|first = John L.
|year = 1950
|title= The Tychonoff product theorem implies the axiom of choice
| journal= Fundamenta mathematica
| volume = 37
| pages = 75–76
| ref=kelley
}}</ref>)

In this sense, we see how Zorn's lemma can be seen as a powerful tool, especially in the sense of unified mathematics{{Clarify|date=June 2011}}.

== Notes ==
<references/>

==References==
* {{cite journal
| last = Campbell
| first = Paul J.
|date=February 1978
| title = The Origin of ‘Zorn's Lemma’
| journal = Historia Mathematica
| volume = 5
| issue = 1
| pages = 77–89
| doi = 10.1016/0315-0860(78)90136-2
| ref = harv
}}
*{{cite book |title=Set Theory for the Working Mathematician |last=Ciesielski |first=Krzysztof |location= |publisher=Cambridge University Press |year=1997 |isbn=0-521-59465-0 }}

==External links==
*[http://www.apronus.com/provenmath/choice.htm Zorn's Lemma at ProvenMath] contains a formal proof down to the finest detail of the equivalence of the axiom of choice and Zorn's Lemma.
*[http://us.metamath.org/mpegif/zorn.html Zorn's Lemma] at [[Metamath]] is another formal proof. ([http://us.metamath.org/mpeuni/zorn.html Unicode version] for recent browsers.)

{{DEFAULTSORT:Zorn's Lemma}}
[[Category:Axiom of choice]]
[[Category:Order theory]]
[[Category:Lemmas]]

formulasearchengine - User contributions [en]

Quaternion