FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Zorn's lemma

Zorn's lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...

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. In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. ...

If the axiom of choice is assumed, then Zorn's lemma is a theorem. In mathematics, the axiom of choice, or AC, is an axiom of set theory. ...


It is named after the mathematician Max Zorn. Max August Zorn (June 6, 1906 in Krefeld, Germany - March 9, 1993 in Bloomington, Indiana, USA) was a German-born American mathematician. ...


The terms are defined as follows. Suppose (P,≤) is the partially ordered set. A subset T is totally ordered if for any s, tT we have either st or ts. Such a set T has an upper bound uP if tu for all tT. Note that u is an element of P but need not be an element of T. A maximal element of P is an element mP such that the only element xP with xm is x = m itself.


Like the well-ordering theorem, Zorn's lemma is equivalent to the axiom of choice, in the sense that either one together with the Zermelo-Fraenkel axioms of set theory is sufficient to prove the other. 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, Tychonoff's theorem in topology stating that every product of compact spaces is compact, and the theorems in abstract algebra that every ring has a maximal ideal and that every field has an algebraic closure. The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ... In mathematics, the axiom of choice, or AC, is an axiom of set theory. ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, the Hahn-Banach theorem is a central tool in functional analysis. ... Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ... In mathematics, a vector space (or linear space) is a collection of objects (known as vectors) which may be scaled and added; all linear combinations of vectors are themselves vectors. ... In linear algebra, a basis is a minimum set of vectors that, when combined, can address every vector in a given space. ... In mathematics, Tychonoffs theorem states that the product of any collection of compact topological spaces is compact. ... Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with spatial properties preserved under bicontinuous deformation (stretching without tearing or gluing); these are the topological invariants. ... In mathematics, a subset of Euclidean space Rn is called compact if it is closed and bounded. ... Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... In mathematics, more specifically in ring theory a maximal ideal is a special kind of ideal which is in some sense maximal, that is not contained in any other non-trivial ideal of the ring. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... In mathematics, particularly abstract algebra, an algebraic closure of a field K is an algebraic extension of K that is algebraically closed. ...

Contents

[edit]

An example application

We will go over a typical application of Zorn's lemma: the proof that every ring R contains a maximal ideal. The set P here consists of all (two-sided) ideals in R, except R itself. This set is partially ordered by 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. In mathematics, more specifically in ring theory a maximal ideal is a special kind of ideal which is in some sense maximal, that is not contained in any other non-trivial ideal of the ring. ... In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ...


We want to apply Zorn's lemma, and so we take a totally ordered subset T of P and have to show that T has an upper bound, i.e. that there exists an ideal IR 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 of all the ideals in T. I is an ideal: if a and b are elements of I, then there exist two ideals J, KT such that a is an element of J and b is an element of K. Since T is totally ordered, we know that JK or KJ. 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 + bI. Furthermore, if rR, then ar and ra are elements of J and hence elements of I. We have shown that I is an ideal in R. In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...


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.

[edit]

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 b, we need to employ the axiom of choice. Partial plot of a function f. ...


Using the function b, we are going to define elements a0 < a1 < a2 < a3 < ... in P. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set P; there are too many ordinals, 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. In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ... Ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ...


The a's are defined by transfinite induction: we pick a0 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 aw = b({av: v < w}). Because the av are totally ordered, this works just fine. Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. ...


This proof shows that actually a slightly stronger version of Zorn's lemma is true:

If P is a poset in which every well-ordered 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.
[edit]

In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, a well-order (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. ...

History

Zorn's lemma was first discovered by K. Kuratowski in 1922 who derived it from the Hausdorff maximal principle, and independently by Max Zorn in 1935. Kazimierz Kuratowski (born February 2, 1896, Warsaw, died June 18, 1980, Warsaw) was a Polish mathematician. ... 1922 (MCMXXII) was a common year starting on Sunday (see link for calendar). ... The Hausdorff maximal principle, (also called the Hausdorff maximality theorem) formulated and proved by Felix Hausdorff in 1914, is an alternate and earlier formulation of Zorns lemma and therefore also equivalent to the axiom of choice. ... Max August Zorn (June 6, 1906 in Krefeld, Germany - March 9, 1993 in Bloomington, Indiana, USA) was a German-born American mathematician. ... 1935 (MCMXXXV) was a common year starting on Tuesday (link will take you to calendar). ...

[edit]

References

  • Set Theory for the Working Mathematician. Ciesielski, Krzysztof. Cambridge University Press, 1997. ISBN 0-521-59465-0
[edit]

External links

  • Zorn's Lemma at ProvenMath contains a formal proof down to the finest detail of the equivalence of AC and Zorn's Lemma.

  Results from FactBites:
 
Zorn's lemma - Wikipedia, the free encyclopedia (833 words)
Zorn's lemma, also known as the Kuratowski-Zorn lemma, is a theorem of set theory that states:
Like the well-ordering theorem, Zorn's lemma is equivalent to the axiom of choice, in the sense that either one together with the Zermelo-Fraenkel axioms of set theory is sufficient to prove the other.
We want to apply Zorn's lemma, and so we take a totally ordered subset T of P and have to show that T has an upper bound, i.e.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m