Zorn's lemma

A lemma in set theory: if a set S is partially ordered and if each subset for which every pair of elements is related by exactly one of the relationships “less than,” “equal to,” or “greater than” has an upper bound in S, then S contains at least one element for which there is no greater element in S

Zorn's lemma is a form of the axiom of choice which is technically very useful for proving existence theorems. For instance, it follows directly from Zorn's lemma that every ring has a maximal ideal and every vector space has a basis (algebraic, that is, Hamel basis). In some subfields of mathematics, arguments of this pattern are so common that they are referred to as zornification or zornication.

To rephrase BelDion's statement above a little: In a poset, if every chain has an upper bound, then the entire poset has a maximal element.

Some Polish mathematicians refer to this lemma as the Kuratowski-Zorn lemma, to properly credit its first appearance, in a paper of Kazimierz Kuratowski. For more information see Set theory for the working mathematician by Krzyzstof Ciesielski (London Mathematical Society student texts, Cambridge University Press).

In set theory, a statement (equivalent to the Axiom of Choice) which asserts that: If S is any non-empty partially ordered set in which every chain has an upper bound, then S has a maximal element.

It should be noted that Zorn's lemma states that under the given conditions S will have a maximal element, it does not say how many maximal elements S may have. A maximal element in a poset is an element such that if any other element is greater than or equal to it, it must in fact be equal to it. A chain in a poset consists of a sub-poset in which every element is comparable.

--back to combinatorics--