Finite Totally Ordered Set is Well-Ordered

From ProofWiki
Jump to navigation Jump to search


Every finite totally ordered set is well-ordered.


Let $\struct {S, \preceq}$ be a finite totally ordered set.

Aiming for a contradiction, suppose $\preceq$ is not a well-founded relation.

From Infinite Sequence Property of Well-Founded Relation, $\struct {S, \preceq}$ is well-founded if and only if there is no infinite sequence $\sequence {a_n}$ of elements of $S$ such that $\forall n \in \N: a_{n + 1} \prec a_n$.

Let us construct such an infinite sequence.

Then at least some of the terms would be repeated in that sequence.

So there would be, for example:

$s_i \preceq s_j \preceq s_k \preceq s_i$

and $\preceq$ would therefore not be transitive and so not a totally ordered set.

From this contradiction it follows that $\preceq$ is well-founded.

The result follows from the definition of well-ordered set.