# 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 orderingon 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 orderingis a partial ordering such that for any , either or .A

partially ordered set(or justposet) is a set together with an assigned partial ordering. Similarly, we havetotally 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
maximumof S is an such that for any we have .- The
minimumof S is an such that for any we have .- A
maximal elementof S is an such that for any , if then .- A
minimal elementof 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

noetherianif 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

chainin 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..