Definition:Chain (Order Theory)

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

Definition

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.

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

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.

Results about chains in the context of order theory can be found here.