Zorn's Lemma
   HOME

TheInfoList



OR:

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
. It states that a partially ordered set containing
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...
s for every chain (that is, every totally ordered
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
) necessarily contains at least one maximal element. The lemma was proved (assuming the axiom of choice) by Kazimierz Kuratowski in 1922 and independently by Max Zorn in 1935. It occurs in the proofs of several theorems of crucial importance, for instance the Hahn–Banach theorem in
functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (for example, Inner product space#Definition, inner product, Norm (mathematics ...
, the theorem that every
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
has a basis, Tychonoff's theorem in
topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
stating that every product of compact spaces is compact, and the theorems in
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
that in a ring with identity every proper ideal is contained in a maximal ideal and that every field has an algebraic closure. Zorn's lemma is equivalent to the well-ordering theorem and also to the axiom of choice, in the sense that within ZF ( Zermelo–Fraenkel set theory without the axiom of choice) any one of the three is sufficient to prove the other two. An earlier formulation of Zorn's lemma is the Hausdorff maximal principle which states that every totally ordered subset of a given partially ordered set is contained in a maximal totally ordered subset of that partially ordered set.


Motivation

To prove the existence of a mathematical object that can be viewed as a maximal element in some partially ordered set in some way, one can try proving the existence of such an object by assuming there is no maximal element and using transfinite induction and the assumptions of the situation to get a contradiction. Zorn's lemma tidies up the conditions a situation needs to satisfy in order for such an argument to work and enables mathematicians to not have to repeat the transfinite induction argument by hand each time, but just check the conditions of Zorn's lemma.


Statement of the lemma

Preliminary notions: * A set ''P'' equipped with a binary relation ≤ that is reflexive ( for every ''x''), antisymmetric (if both and hold, then ), and transitive (if and then ) is said to be (partially) ordered by ≤. Given two elements ''x'' and ''y'' of ''P'' with ''x'' ≤ ''y'', ''y'' is said to be greater than or equal to ''x''. The word "partial" is meant to indicate that not every pair of elements of a partially ordered set is required to be comparable under the order relation, that is, in a partially ordered set ''P'' with order relation ≤ there may be elements ''x'' and ''y'' with neither ''x'' ≤ ''y'' nor ''y'' ≤ ''x''. An ordered set in which every pair of elements is comparable is called totally ordered. * Every subset ''S'' of a partially ordered set ''P'' can itself be seen as partially ordered by restricting the order relation inherited from ''P'' to ''S''. A subset ''S'' of a partially ordered set ''P'' is called a chain (in ''P'') if it is totally ordered in the inherited order. * An element ''m'' of a partially ordered set ''P'' with order relation ≤ is maximal (with respect to ≤) if there is no other element of ''P'' greater than ''m'', that is, there is no ''s'' in ''P'' with ''s'' ≠ ''m'' and ''m'' ≤ ''s''. Depending on the order relation, a partially ordered set may have any number of maximal elements. However, a totally ordered set can have at most one maximal element. * Given a subset ''S'' of a partially ordered set ''P'', an element ''u'' of ''P'' is an
upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...
of ''S'' if it is greater than or equal to every element of ''S''. Here, ''S'' is not required to be a chain, and ''u'' is required to be comparable to every element of ''S'' but need not itself be an element of ''S''. Zorn's lemma can then be stated as: In fact, property (1) is redundant, since property (2) says, in particular, that the empty chain has an upper bound in P, implying P is nonempty. However, in practice, one often checks (1) and then verifies (2) only for nonempty chains, since the case of the empty chain is taken care by (1). In the terminology of Bourbaki, a partially ordered set is called inductive if each chain has an upper bound in the set (in particular, the set is then nonempty). Then the lemma can be stated as: For some applications, the following variant may be useful. Indeed, let Q = \ with the partial ordering from P. Then, for a chain in Q, an upper bound in P is in Q and so Q satisfies the hypothesis of Zorn's lemma and a maximal element in Q is a maximal element in P as well.


Example applications


Every vector space has a basis

Zorn's lemma can be used to show that every
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
''V'' has a basis. If ''V'' = , then the empty set is a basis for ''V''. Now, suppose that ''V'' ≠ . Let ''P'' be the set consisting of all linearly independent subsets of ''V''. Since ''V'' is not the zero vector space, there exists a nonzero element v of ''V'', so ''P'' contains the linearly independent subset . Furthermore, ''P'' is partially ordered by set inclusion (see inclusion order). Finding a maximal linearly independent subset of ''V'' is the same as finding a maximal element in ''P''. To apply Zorn's lemma, take a chain ''T'' in ''P'' (that is, ''T'' is a subset of ''P'' that is totally ordered). If ''T'' is the empty set, then is an upper bound for ''T'' in ''P''. Suppose then that ''T'' is non-empty. We need to show that ''T'' has an upper bound, that is, there exists a linearly independent subset ''B'' of ''V'' containing all the members of ''T''. Take ''B'' to be the union of all the sets in ''T''. We wish to show that ''B'' is an upper bound for ''T'' in ''P''. To do this, it suffices to show that ''B'' is a linearly independent subset of ''V''. Suppose otherwise, that ''B'' is not linearly independent. Then there exists vectors v1, v2, ..., vk ∈ ''B'' and scalars ''a''1, ''a''2, ..., ''a''k, not all zero, such that :a_1\mathbf_1 + a_2\mathbf_2 + \cdots + a_k\mathbf_k = \mathbf. Since ''B'' is the union of all the sets in ''T'', there are some sets ''S''1, ''S''2, ..., ''S''k ∈ ''T'' such that vi ∈ ''S''i for every ''i'' = 1, 2, ..., ''k''. As ''T'' is totally ordered, one of the sets ''S''1, ''S''2, ..., ''S''k must contain the others, so there is some set ''S''i that contains all of v1, v2, ..., vk. This tells us there is a linearly dependent set of vectors in ''S''i, contradicting that ''S''i is linearly independent (because it is a member of ''P''). The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in ''P'', in other words a maximal linearly independent subset ''B'' of ''V''. Finally, we show that ''B'' is indeed a basis of ''V''. It suffices to show that ''B'' is a spanning set of ''V''. Suppose for the sake of contradiction that ''B'' is not spanning. Then there exists some v ∈ ''V'' not covered by the span of ''B''. This says that ''B'' ∪ is a linearly independent subset of ''V'' that is larger than ''B'', contradicting the maximality of ''B''. Therefore, ''B'' is a spanning set of ''V'', and thus, a basis of ''V''.


Every nontrivial ring with unity contains a maximal ideal

Zorn's lemma can be used to show that every nontrivial ring ''R'' with unity contains a maximal ideal. Let ''P'' be the set consisting of all ''proper'' ideals in ''R'' (that is, all ideals in ''R'' except ''R'' itself). Since ''R'' is non-trivial, the set ''P'' contains the trivial ideal . Furthermore, ''P'' is partially ordered by set inclusion. Finding a maximal ideal in ''R'' is the same as finding a maximal element in ''P''. To apply Zorn's lemma, take a chain ''T'' in ''P''. If ''T'' is empty, then the trivial ideal is an upper bound for ''T'' in ''P''. Assume then that ''T'' is non-empty. It is necessary to show that ''T'' has an upper bound, that is, there exists an ideal ''I'' ⊆ ''R'' containing all the members of ''T'' but still smaller than ''R'' (otherwise it would not be a proper ideal, so it is not in ''P''). Take ''I'' to be the union of all the ideals in ''T''. We wish to show that ''I'' is an upper bound for ''T'' in ''P''. We will first show that ''I'' is an ideal of ''R''. For ''I'' to be an ideal, it must satisfy three conditions: # ''I'' is a nonempty subset of ''R'', # For every ''x'', ''y'' ∈ ''I'', the sum ''x'' + ''y'' is in ''I'', # For every ''r'' ∈ ''R'' and every ''x'' ∈ ''I'', the product ''rx'' is in ''I''. #1 - ''I'' is a nonempty subset of ''R''. 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. Every element of ''T'' is a subset of ''R'', so the union ''I'' only consists of elements in ''R''. #2 - For every ''x'', ''y'' ∈ ''I'', the sum ''x'' + ''y'' is in ''I''. Suppose ''x'' and ''y'' are elements of ''I''. Then there exist two ideals ''J'', ''K'' ∈ ''T'' such that ''x'' is an element of ''J'' and ''y'' is an element of ''K''. Since ''T'' is totally ordered, we know that ''J'' ⊆ ''K'' or ''K'' ⊆ ''J''. Without loss of generality, assume the first case. Both ''x'' and ''y'' are members of the ideal ''K'', therefore their sum ''x'' + ''y'' is a member of ''K'', which shows that ''x'' + ''y'' is a member of ''I''. #3 - For every ''r'' ∈ ''R'' and every ''x'' ∈ ''I'', the product ''rx'' is in ''I''. Suppose ''x'' is an element of ''I''. Then there exists an ideal ''J'' ∈ ''T'' such that ''x'' is in ''J''. If ''r'' ∈ ''R'', then ''rx'' is an element of ''J'' and hence an element of ''I''. Thus, ''I'' is an ideal in ''R''. Now, we show that ''I'' is a ''proper'' ideal. An ideal is equal to ''R'' if and only if it contains 1. (It is clear that if it is ''R'' then it contains 1; on the other hand, if it contains 1 and ''r'' is an arbitrary element of ''R'', then ''r''1 = ''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 ''R'' is explicitly excluded from ''P''. The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in ''P'', in other words a maximal ideal in ''R''.


Proof sketch

A sketch of the proof of Zorn's lemma follows, assuming the axiom of choice. 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 that for every element in ''P'' there is another element bigger than it. 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 ''b'', we need to employ the axiom of choice (explicitly: let B(T) = \ , that is, the set of upper bounds for ''T''. The axiom of choice furnishes b: b(T) \in B(T) ). Using the function ''b'', we are going to define elements ''a''0 < ''a''1 < ''a''2 < ''a''3 < ... < aω < aω+1 <…, in ''P''. This uncountable sequence is really long: the indices are not just the
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s, but all ordinals. 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 (in other words, given any set of ordinals, there exists a larger ordinal), 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''(). Because the ''a''''v'' are totally ordered, this is a well-founded definition. The above proof can be formulated without explicitly referring to ordinals by considering the initial segments as subsets of ''P''. Such sets can be easily characterized as well-ordered chains ''S'' ⊆ ''P'' where each ''x'' ∈ ''S'' satisfies ''x'' = ''b''(). Contradiction is reached by noting that we can always find a "next" initial segment either by taking the union of all such ''S'' (corresponding to the limit ordinal case) or by appending ''b''(''S'') to the "last" ''S'' (corresponding to the successor ordinal case). This proof shows that actually a slightly stronger version of Zorn's lemma is true: Alternatively, one can use the same proof for the Hausdorff maximal principle. This is the proof given for example in Halmos' '' Naive Set Theory'' or in below. Finally, the Bourbaki–Witt theorem can also be used to give a proof.


Proof

The basic idea of the proof is to reduce the proof to proving the following weak form of Zorn's lemma: (Note that, strictly speaking, (1) is redundant since (2) implies the empty set is in F.) Note the above is a weak form of Zorn's lemma since Zorn's lemma says in particular that any set of subsets satisfying the above (1) and (2) has a maximal element ((3) is not needed). The point is that, conversely, Zorn's lemma follows from this weak form. Indeed, let F be the set of all chains in P. Then it satisfies all of the above properties (it is nonempty since the empty subset is a chain.) Thus, by the above weak form, we find a maximal element C in F; i.e., a maximal chain in P. By the hypothesis of Zorn's lemma, C has an upper bound x in P. Then this x is a maximal element since if y \ge x, then \widetilde = C \cup \ is larger than or equal to C and so \widetilde = C. Thus, y = x. The proof of the weak form is given in Hausdorff maximal principle#Proof. Indeed, the existence of a maximal chain is exactly the assertion of the Hausdorff maximal principle. The same proof also shows the following equivalent variant of Zorn's lemma: Indeed, trivially, Zorn's lemma implies the above lemma. Conversely, the above lemma implies the aforementioned weak form of Zorn's lemma, since a union gives a least upper bound.


Zorn's lemma implies the axiom of choice

A proof that Zorn's lemma implies the axiom of choice illustrates a typical application of Zorn's lemma. (The structure of the proof is exactly the same as the one for the Hahn–Banach theorem.) Given a set X of nonempty sets and its union U := \bigcup X (which exists by the
axiom of union An axiom, postulate, or assumption is a statement (logic), statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that whi ...
), we want to show there is a function :f : X \to U such that f(S) \in S for each S \in X. For that end, consider the set :P = \. It is partially ordered by extension; i.e., f \le g if and only if f is the restriction of g. If f_i : X_i \to U is a chain in P, then we can define the function f on the union X' = \cup_i X_i by setting f(x) = f_i(x) when x \in X_i. This is well-defined since if i < j, then f_i is the restriction of f_j. The function f is also an element of P and is a common extension of all f_i's. Thus, we have shown that each chain in P has an upper bound in P. Hence, by Zorn's lemma, there is a maximal element f in P that is defined on some X' \subset X. We want to show X' = X. Suppose otherwise; then there is a set S \in X - X'. As S is nonempty, it contains an element s. We can then extend f to a function g by setting g, _ = f and g(S) = s. (Note this step does not need the axiom of choice.) The function g is in P and f < g, a contradiction to the maximality of f. \square Essentially the same proof also shows that Zorn's lemma implies the well-ordering theorem: take P to be the set of all well-ordered subsets of a given set X and then shows a maximal element of P is X.


History

The Hausdorff maximal principle is an early statement similar to Zorn's lemma. Kazimierz Kuratowski proved in 1922 a version of the lemma close to its modern formulation (it applies 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 Zorn in 1935, 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 John Wilder Tukey (; June 16, 1915 – July 26, 2000) was an American mathematician and statistician, best known for the development of the fast Fourier Transform (FFT) algorithm and box plot. The Tukey range test, the Tukey lambda distributi ...
, 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". The name " Kuratowski–Zorn lemma" prevails in Poland and Russia.


Equivalent forms of Zorn's lemma

Zorn's lemma is equivalent (in ZF) to three main results: # Hausdorff maximal principle # Axiom of choice # Well-ordering theorem. A well-known joke alluding to this equivalency (which may defy human intuition) is attributed to Jerry Bona: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" Zorn's lemma is also equivalent to the strong completeness theorem of first-order logic. 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 basis, a result from linear algebra (to which it is equivalent). In particular, the real numbers, as a vector space over the rational numbers, possess a Hamel basis. # Every commutative unital ring has a maximal ideal, a result from ring theory known as Krull's theorem, to which Zorn's lemma is equivalent # Tychonoff's theorem in topology (to which it is also equivalent) # Every proper filter is contained in an ultrafilter, a result that yields the completeness theorem of first-order logic In this sense, Zorn's lemma is a powerful tool, applicable to many areas of mathematics.


Analogs under weakenings of the axiom of choice

A weakened form of Zorn's lemma can be proven from ZF + DC (Zermelo–Fraenkel set theory with the axiom of choice replaced by the
axiom of dependent choice In mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. T ...
). Zorn's lemma can be expressed straightforwardly by observing that the set having no maximal element would be equivalent to stating that the set's ordering relation would be entire, which would allow us to apply the axiom of dependent choice to construct a countable chain. As a result, any partially ordered set with exclusively finite chains must have a maximal element. More generally, strengthening the axiom of dependent choice to higher ordinals allows us to generalize the statement in the previous paragraph to higher cardinalities. In the limit where we allow arbitrarily large ordinals, we recover the proof of the full Zorn's lemma using the axiom of choice in the preceding section.


In popular culture

The 1970 film '' Zorns Lemma'' is named after the lemma. The lemma was referenced on ''
The Simpsons ''The Simpsons'' is an American animated sitcom created by Matt Groening and developed by Groening, James L. Brooks and Sam Simon for the Fox Broadcasting Company. It is a Satire (film and television), satirical depiction of American life ...
'' in the episode " Bart's New Friend".


See also

* * Chain-complete partial order – a partially ordered set in which every chain has a least upper bound * * * Teichmüller–Tukey lemma (sometimes named Tukey's lemma) * Bourbaki–Witt theorem – a choiceless fixed-point theorem that can be combined with choice to prove Zorn's lemma


Notes


References

* * * * * *


Further reading


The Zorn Identity
at the n-category cafe.


External links

*

contains a formal proof down to the finest detail of the equivalence of the axiom of choice and Zorn's Lemma.

at Metamath is another formal proof.
Unicode version
for recent browsers.) {{DEFAULTSORT:Zorn's Lemma Axiom of choice Lemmas in set theory Order theory