# 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 $x\in S$, we have $x\le x$.
• (Transitive) For any $x, y, z\in S$, if $x\le y$ and $y\le z$, then $x\le z$.
• (Anti-symmetric) For any $x, y\in S$, if $x\le y$ and $y\le x$, then $x=y$.

total ordering is a partial ordering such that for any $x,y \in S$, either $x\le y$ or $y\le x$.

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 $(S, \le)$, for $x,y\in S$, we write:

• $x < y$ if $x\le y$ and $x\ne y$;
• $x\ge y$ if $y \le x$;
• $x > y$ if $y < x$.

## Examples

1. The set of real numbers (or rational numbers, or integers) forms a totally ordered set under the usual arithmetic ordering.
2. 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.
3. 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 $(S, \le)$ is a poset, then so is $(S, \ge)$.

Proof.

Easy exercise. ♦

Duality allows us to cut our work by half in a lot of cases.

# Bounds

Let $(S, \le)$ be a poset.

Definition.

• The maximum of S is an $m_1 \in S$ such that for any $x\in S$ we have $x\le m_1$.
• The minimum of S is an $m_0 \in S$ such that for any $x\in S$ we have $x \ge m_0$.
• maximal element of S is an $m\in S$ such that for any $x\in S$, if $x \ge m$ then $x=m$.
• minimal element of S is an $m'\in S$ such that for any $x\in S$, if $x \le m'$ then $x=m'$.

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 = {abc} 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 $m_1$. Must $m_1$ 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 $x\in S$ satisfying: for all $y\in T$, we have $y\le x$ (resp. $y \ge x$).

Clearly, upper and lower bounds are not unique in general. E.g. for $S = \mathbb Z$ 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 $T\subseteq S$ be any non-empty subset. Pick $x_0 \in T$. If $x_0$ is a minimal element of T we are done; otherwise there exists $x_1 \in T$, $x_1 < x_0$. Again if $x_1$ is a minimal element of T we are done; otherwise we repeat. The process terminates since T is finite because we cannot have $x_0 > x_1 > \ldots$ in T. Thus T has a minimal element.

Examples

1. The set $\mathbb N$ of positive integers under ≤ is noetherian.
2. The set $\mathbb N \times \mathbb N$ is noetherian, where $(m, n) \le (m', n')$ if $m\le m'$ and $n \le n'$.
3. The set $\mathbb N$ is noetherian, where we take $m\le n$ to mean $m|n$.

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 $x\in S$ is such that $(y \in S, y < x \implies y \in T)$, then $x\in T$.

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 $T\ne S$, $U = S - T$ is non-empty so it has a minimal element x. By minimality, any $y\in S$ with $y < x$ cannot lie in U so $y\in T$. But by the given condition this means $x\in T$, 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 $x_1 \ge x_2 \ge \ldots$ in S, there is an n such that $x_n = x_{n+1} = x_{n+2} = \ldots$.

Proof

(⇒) Suppose S is noetherian and $x_1 \ge x_2 \ge \ldots$ are elements of S. The set $\{x_n : n=1,2,\ldots\}$ thus has a minimal element $x_n$. Since we have $x_n \ge x_{n+1} \ge \ldots$, equality must hold by minimality.

(⇐) Suppose S is not noetherian; let $T\subseteq S$ be a non-empty subset with no minimal element. Pick $x_1 \in T$; it is not minimal, so we can find $x_2 \in T$ with $x_2 < x_1$. Again since $x_2\in T$ is not minimal we can find $x_3 \in T$ with $x_3 < x_2$. 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 $T\subseteq S$ 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 $f:\mathbb R\to \mathbb R$. 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 $\Sigma$ be the set of all linearly independent subsets of V. We define a partial order on $\Sigma$ by inclusion, i.e. for $C, D \in \Sigma$, $C\le D$ if and only if $C\subseteq D$. Next, we claim that every chain $\Sigma' \subseteq \Sigma$ has an upper bound.

Let $D =\cup_{C \in \Sigma'} C$; we need to show that D is a linearly independent subset of V, so that $D\in \Sigma$ is an upper bound of $\Sigma'$. Suppose

$\alpha_1 v_1 + \ldots + \alpha_n v_n = 0, \quad v_1, \ldots, v_n \in D, \alpha_1, \ldots, \alpha_n \in k.$

For each $i=1, \ldots, n$, we have $v_i \in C_i$ for some $C_i \in \Sigma'$. But $\Sigma'$, being a chain, is totally ordered so without loss of generality, we assume $C_1 \supseteq C_i$ for all $1 \le i \le n$. This means $v_1, \ldots, v_n \in C_1$; since $C_1$ is linearly independent, we have $\alpha_1 = \ldots = \alpha_n = 0$.

Now apply Zorn’s lemma and we see that $\Sigma$ has a maximal element C. We claim that a maximal linearly independent subset of V must span V. If not, we can find $v\in V$ outside the span of C. This means $C \cup \{v\}$ 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 $T\subseteq S$ 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..

This entry was posted in Advanced Algebra and tagged , , , , . Bookmark the permalink.