Proof of Greatest Element of a Finite Family in a Totally Ordered Set

By the definition of a tuple, an $n$-tuple in $A$ is a map from $[n]$ to $A$ with components written $c_{k}$; we use this identification throughout.

For a natural number $n$ let $P(n)$ be the assertion: for every $c\in A^{n}$ with components $c_{k}$ there exists $j\in[n]$ such that $c_{k}\le c_{j}$ for every $k\in[n]$, where $[n]$ is the initial segment determined by $n$, that is, the set of natural numbers $k$ with $1\le k\le n$. We prove $P(n)$ for every $n$ by induction. Throughout we use the order properties of the natural numbers recorded in Properties of the Order on the Natural Numbers, and the fact that $\le$ on $A$, being a total order, is reflexive, antisymmetric and transitive and compares any two elements.

Base case. Let $n=1$ and let $c\in A^{1}$. If $k\in[1]$ then $1\le k$ and $k\le 1$, so $k=1$ by claim 2 of Properties of the Order on the Natural Numbers; hence $[1]=\{1\}$. Take $j=1$: for every $k\in[1]$ we have $c_{k}=c_{1}\le c_{1}=c_{j}$ by reflexivity. So $P(1)$ holds.

Induction step. Assume $P(n)$ and let $c\in A^{S(n)}$, where $S$ is the successor map of Natural Numbers. We first record two facts about indices.

(i) $[n]\subseteq[S(n)]$. Indeed, if $k\in[n]$ then $1\le k$ and $k\le n$; and $n<S(n)$ by claim 5 of Properties of the Order on the Natural Numbers, hence $n\le S(n)$ and then $k\le S(n)$ by claim 1 of that lemma.

(ii) If $k\in[S(n)]$ and $k\ne S(n)$, then $k\in[n]$. Indeed $k\le S(n)$ and $k\ne S(n)$ give $k\le n$ by claim 5 of Properties of the Order on the Natural Numbers, and $1\le k$ by claim 4.

Let $c'\in A^{n}$ be the restriction of $c$ to $[n]$, which is defined by (i). By $P(n)$ applied to $c'$ there is $j'\in[n]$ with $c'_{k}\le c'_{j'}$, that is $c_{k}\le c_{j'}$, for every $k\in[n]$. Since $\le$ on $A$ compares any two elements, either $c_{j'}\le c_{S(n)}$ or $c_{S(n)}\le c_{j'}$.

Case 1: $c_{j'}\le c_{S(n)}$. Put $j=S(n)$, which lies in $[S(n)]$ since $1\le S(n)$ and $S(n)\le S(n)$. Let $k\in[S(n)]$. If $k=S(n)$ then $c_{k}\le c_{j}$ by reflexivity. Otherwise $k\in[n]$ by (ii), so $c_{k}\le c_{j'}$ and $c_{j'}\le c_{S(n)}=c_{j}$, whence $c_{k}\le c_{j}$ by transitivity.

Case 2: $c_{S(n)}\le c_{j'}$. Put $j=j'$, which lies in $[S(n)]$ by (i). Let $k\in[S(n)]$. If $k=S(n)$ then $c_{k}=c_{S(n)}\le c_{j'}=c_{j}$. Otherwise $k\in[n]$ by (ii), and then $c_{k}\le c_{j'}=c_{j}$.

In both cases $P(S(n))$ holds. By induction, $P(n)$ holds for every natural number $n$.