Definition:Chain (Order Theory)

From ProofWiki
Jump to navigation Jump to search

This page is about Chain in the context of Order Theory. For other uses, see Chain.


Let $\struct {S, \preceq}$ be an ordered set.

A chain in $S$ is a totally ordered subset of $S$.

Thus a totally ordered set is itself a chain in its own right.

Chain of Sets

An important special case of a chain is where the ordering in question is the subset relation:

Let $S$ be a set.

Let $\powerset S$ be its power set.

Let $N \subseteq \powerset S$ be a subset of $\powerset S$.

Then $N$ is a chain (of sets) if and only if:

$\forall X, Y \in N: X \subseteq Y$ or $Y \subseteq X$


Let $T$ be a chain in $S$.

Let $T$ be finite and non-empty.

The length of the chain $T$ is its cardinality minus $1$.

Also defined as

Some sources use the term chain to mean the same thing as totally ordered set.

While this is perfectly valid, as there is no source of confusion here, such usage is surprisingly uncommon.

Also see