Lemma of anger
The lemma of Zorn , also known as the lemma of Kuratowski-Zorn or Zorn's lemma , is a theorem of set theory , more precisely, of Zermelo-Fraenkel set theory , which includes the axiom of choice . It says that every inductively ordered set has at least one maximal element .
The lemma is named after the German-American mathematician Max Zorn , who discovered it in 1933 (independent of the discovery by Kuratowski in 1922.), and is related to Hausdorff's maximum chain theorem from 1914.
The attribution to Zorn was already in the edition of the set theory by Bourbaki (as the theorem of Zorn, written by Claude Chevalley , who knew Zorn from his time with Emil Artin in Hamburg in the early 1930s), the term Lemma was used in a publication by John W. Tukey (1940). There were various other authors (besides the aforementioned Hausdorff and Kuratowski) who published maximum principles that followed from the axiom of choice or the well-order theorem (such as Salomon Bochner 1928, RL Moore 1932). However, Zorn first suspected (in his 1935 paper) that the axiom of choice, the well-order theorem, and Zorn's lemma (which he called the maximum principle) are equivalent, and announced a proof in a follow-up paper that never appeared.
Zorn's lemma states:
- A semi-ordered set in which every chain has an upper bound contains at least one maximal element .
- A semi-ordered set is given . This means that the order relation must be transitive , reflexive and antisymmetric .
- We now consider special subsets of , which have the following property: For all it always holds or . Such subsets are called chains or totally ordered .
- For these special subsets (and only for these) it is now additionally required that they have an upper bound in . This means: for every chain of exists one , so that holds for all . Note that it does not have to be in.
- The statement of the lemma of Zorn reads: The set has a maximum element . This means: There is an element for which there is no larger element in . So it always follows from .
- For the empty semi-ordered set, the empty chain has no element as an upper bound.
- For a non-empty semi-ordered set, the empty chain has every element as an upper bound.
The special thing about Zorn's lemma is that one comes from comparatively weak statements about very special subsets of to a rather strong statement about the set itself.
Like the well-order theorem , Zorn's lemma is equivalent to the axiom of choice ; In other words , one of these three theorems, together with the Zermelo-Fraenkel set theory, can prove the other two. Zorn's lemma is used in many important proofs, for example for
- the theorem that every vector space has a basis (and even every linearly independent set is contained in a suitable basis),
- the Hahn-Banach theorem in functional analysis , according to which linear functionals can be continued,
- Tychonoff's theorem that every product of compact spaces in the product topology is itself compact,
- the proposition that each ring with 1, which is not the zero ring , is a maximal ideal has (or there even every real Ideal in a maximal ideal located),
- Ernst Steinitz's theorem that every body has an algebraic closure .
An example of the application
As a typical application of Zorn's lemma, we prove that every ring with 1 that is not the zero ring has a maximal ideal. The set consists of all (mutual) ideals in that do not contain the 1. This set is not empty (it contains the zero ideal, since it is assumed) and semi-ordered with respect to the set inclusion. If we can find a maximum element of this set, then we are done, because that is an ideal that is genuinely contained in and every greater ideal does not lie in , i.e. contains the 1 and thus as an ideal also every element of , i.e. H. there is no greater ideal genuinely contained in it.
To anger Lemma apply, we take a non-empty totally ordered subset of , and must demonstrate that it has an upper bound, that is an ideal in there that all ideals in includes, but unevenly is (otherwise it would not ). We choose as the union of all elements of . Then it is not empty, because it contains at least one ideal as an element, which in turn is contained in as a subset. is an ideal, because there are and elements of , then there are ideals in , so that there is in and in . Since it is totally ordered, one of the two ideals lies in the other; we can assume that it is contained in without restriction . Then and both are in , so lie and for each in also and in and therefore in . So is actually an ideal of . Since none of the ideals lying in contains the 1, neither does the 1, so lies in . Thus there is an upper bound of .
Since the conditions for Zorn's lemma are met, we get the existence of a maximal element in , and that is a maximal ideal of .
This proof requires the premise that the ring has a 1. Without that it would not be feasible and in fact the claim would be false. An example of a ring with no maximal ideal (and no 1) is with multiplication for all . In this ring, ideals are identical with (additive) subgroups and for each real subgroup the factor group is divisible just like the starting group , consequently not finitely generated , thus has a non-trivial real (e.g. cyclic ) subgroup, and this returns as Archetype a containing, genuine ideal.
Equivalence of axiom of choice and lemma of Zorn
Finally we sketch the equivalence between Zorn's lemma and the axiom of choice.
Inference of Zorn's lemma from the axiom of choice
Suppose the lemma was wrong. Then there would be a semi-ordered set in which every totally ordered subset would have an upper bound, but each element would still have a really larger one (there would be no maximal element in ). For each totally ordered subset we now define an element that is larger than each element in by taking an upper bound of and placing it on an element that is even greater than this bound. In order to be able to define this as a function, we need the axiom of choice (because we do not say which upper bound and which larger element we take).
With this function we then determine elements in . This sequence gets really long: the indices are not just all natural numbers, but all ordinals . This sequence is too long for the set , because there are more ordinals than there can be elements in any set, and so we get a contradiction.
The we define by transfinite induction : For each ordinal set, we
This is possible because they are totally ordered through this construction.
Conclusion of the axiom of choice from Zorn's lemma
Let be an arbitrary set of nonempty sets. Then there would have to be a selection function , ie a function that assigns an element of to every set (it applies to all ).
Now consider those functions which are a selection function of a (finite) subset of . The set of these partial selection functions is semi-ordered:
For applies if and only if and on the domain of are equal and this is really contained in the domain of .
This partial order also creates chains in . If one combines all domains of definition of the functions in a chain , one can construct a function on this union with for any one that is defined on . This is an upper bound of , so according to Zorn's lemma it has at least one maximal element .
If one were not defined, one could be constructed that has the properties of and at the same time maps to any element of . But then it would not be maximal, a contradiction.
So it has to be completely defined and is therefore a selection function of .
- BA Efimov: Anger lemma . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
- ^ Zorn, quoted in Paul J. Campbell, The origin of Zorn's lemma, Historia Mathematica, Volume 5, 1978, pp. 77-89
- ↑ The first publication by Zorn was in 1935: Zorn, A remark on method in transfinite algebra, Bulletin AMS, Volume 41, 1935, pp. 667-670, Project Euclid .
- ↑ Kuratowski, Une méthode d´élimination des nombres transfinis des raisonnements mathématiques, Fundamenta Mathematicae, Volume 3, 1922, pp. 76-108
- ↑ Hausdorff, Fundamentals of Set Theory, 1914
- ^ Tukey, Convergence and uniformity in topology, Annals of Mathematical Studies 2, Princeton University Press 1940
- ^ Bochner, continuation of Riemann surfaces, Mathematische Annalen, Volume 98, 1928, pp. 406-421
- ^ Moore, Foundations of point set theory, American Mathematical Society 1932