Some Results on Posets
In this article we have two goals in mind:
- to introduce the idea of noetherian posets, and
- to state Zorn’s lemma and give some examples.
The latter is of utmost importance in diverse areas of mathematics.
Definition.
A partial ordering on a set S is a relation ≤ on S × S, satisfying the following.
- (Reflexive) For any
, we have
.
- (Transitive) For any
, if
and
, then
.
- (Anti-symmetric) For any
, if
and
, then
.
A total ordering is a partial ordering such that for any
, either
or
.
A partially ordered set (or just poset) is a set together with an assigned partial ordering. Similarly, we have totally ordered sets.
Given a partially ordered set , for
, we write:
if
and
;
if
;
if
.
Examples
- The set of real numbers (or rational numbers, or integers) forms a totally ordered set under the usual arithmetic ordering.
- If X is a set, let P(X) be the collection of all subsets of X. This forms a partially ordered set under inclusion. If X has more than one element, P(X) is not totally ordered.
- Any subset T of a partially ordered set S gives a partially ordered set. If S is totally ordered, so is T.
Lemma 1 (Duality).
If
is a poset, then so is
.
Proof.
Easy exercise. ♦
Duality allows us to cut our work by half in a lot of cases.
Bounds
Let be a poset.
Definition.
- The maximum of S is an
such that for any
we have
.
- The minimum of S is an
such that for any
we have
.
- A maximal element of S is an
such that for any
, if
then
.
- A minimal element of S is an
such that for any
, if
then
.
The naming is a little confusing, but one must differentiate between the maximum of a set and the maximal elements of a set. In the poset below, S has three maximal elements but no maximum.
For example, let X = {a, b, c} and let S be the following subsets of P(X) under inclusion.
The following properties are obvious.
Lemma 2.
- The maximum (resp. minimum) of a poset is unique if it exists.
- If the maximum (resp. minimum) of a poset exists, it is the unique maximal (resp. minimal) element.
Proof
Easy exercise. ♦
Exercise
Suppose S has a unique maximal element . Must
be the maximum of S?
Finally, for a subset T of an ordered set S, we define the following.
Definition.
An upper bound (resp. lower bound) of T in S is an
satisfying: for all
, we have
(resp.
).
Clearly, upper and lower bounds are not unique in general. E.g. for under the arithmetic ordering, the subset T of even integers has no upper or lower bound. The subset T’ of squares has lower bounds 0, -1, -2, … but no upper bound.
Noetherian Sets
This will be used a few times in our study of commutative algebra.
Definition.
A poset S is said to be noetherian if every non-empty subset T of S has a minimal element (in T).
It is easy to see that every finite poset S is noetherian.
- Let
be any non-empty subset. Pick
. If
is a minimal element of T we are done; otherwise there exists
,
. Again if
is a minimal element of T we are done; otherwise we repeat. The process terminates since T is finite because we cannot have
in T. Thus T has a minimal element.
Examples
- The set
of positive integers under ≤ is noetherian.
- The set
is noetherian, where
if
and
.
- The set
is noetherian, where we take
to mean
.
Note that examples 2 and 3 are not totally ordered. The key property of noetherian sets is the following.
Theorem (Noetherian Induction).
Let T be a subset of a noetherian poset S satisfying the following.
- If
is such that
, then
.
Then T = S.
Note
To paraphrase the condition in words: if T contains all elements of S smaller than x, then it must contain x itself.
Proof
If ,
is non-empty so it has a minimal element x. By minimality, any
with
cannot lie in U so
. But by the given condition this means
, which is a contradiction. ♦
Here is an equivalent way of expressing the noetherian property.
Proposition 1.
A poset S is noetherian if and only if the following hold.
- For any sequence of elements
in S, there is an n such that
.
Proof
(⇒) Suppose S is noetherian and are elements of S. The set
thus has a minimal element
. Since we have
, equality must hold by minimality.
(⇐) Suppose S is not noetherian; let be a non-empty subset with no minimal element. Pick
; it is not minimal, so we can find
with
. Again since
is not minimal we can find
with
. Repeat to obtain an infinitely decreasing sequence. ♦
Zorn’s Lemma
Finally we have the following critical result.
Theorem (Zorn’s Lemma).
Let S be a poset. A chain in S is a subset which is totally ordered. Suppose S is a poset such that every chain
has an upper bound in S.
Then S has a maximal element.
A typical application of Zorn’s lemma is the following.
Proposition 2.
Every vector space V over a field k has a basis.
Note
This looks like an intuitively obvious result, but try finding a basis for the ℝ-space of all real functions . Using Zorn’s lemma, one can show that a basis exists but describing it does not seem possible. Generally, results that require Zorn’s lemma are of this nature: they claim existence of certain objects or constructions without exhibiting them explicitly. Some of these are rather unnerving, like the Banach-Tarski paradox.
Proof
Let be the set of all linearly independent subsets of V. We define a partial order on
by inclusion, i.e. for
,
if and only if
. Next, we claim that every chain
has an upper bound.
Let ; we need to show that D is a linearly independent subset of V, so that
is an upper bound of
. Suppose
For each , we have
for some
. But
, being a chain, is totally ordered so without loss of generality, we assume
for all
. This means
; since
is linearly independent, we have
.
Now apply Zorn’s lemma and we see that has a maximal element C. We claim that a maximal linearly independent subset of V must span V. If not, we can find
outside the span of C. This means
is linearly independent, thus contradicting the maximality of C. ♦
Zorn’s lemma holds vacuously when S is empty. However, in many applications of the lemma, constructing an upper bound for a chain
requires T to be non-empty. In such instances, we will mentally replace Zorn’s lemma with the following equivalent version.
- If S is a non-empty poset such that every non-empty chain in S has an upper bound in S, then S has a maximal element..