# Let $A$ be a finite simply ordered set.

Show that $A$ has a largest element. [Hint: Proceed by induction on cardinality of $A$]

Attempt:

According to the assumption my set $A$ is finite and simply ordered so that would mean $A = \{A_1, A_2,.....A_n\}$ where $n$ is the cardinality of my set $A$

Skipping over the test case of induction, let me just go to assuming that the statement is true for $n = k$ , thus $A_k$ is the largest element

Consider the set $B = \{A_1, A_2,.......A_k, A_{k+1}\}$ with the same assumptions of finitness and simply ordered. If we take $A\cup B = \{A_1,A_2,...A_k, A_{k+1}\}$ we once again have a finite set in which order matters, but now $A_{k+1}$ is the largest element, therefore the set $A$ had a largest element.

I'm still poor at writing these proofs, so I'll ask is there anything correct about my write up?

• You didn't say why $A_{k+1}$ is the largest element. It is not necessary that the largest element of $A$ should be different from the largest element of $B$. – Crostul May 12 '15 at 21:19
• I think you should do induction on the size of $A$. – Gregory Grant May 12 '15 at 21:20

## 3 Answers

You shouldn't assume $A_{k+1}$ is the largest element of $B$. Rather, by induction, you may assume that $\{A_1,\dots,A_k\}$ has a largest element, say $A_i$. Then look at two cases: $A_{k+1}>A_i$ in which case $A_{k+1}$ is the largest element of $\{A_1,\dots,A_{k+1}\}$; and $A_{k+1}<A_i$, in which case $A_i$ is the largest element.

• Ok. I get exactly what you wrote, but it just doesn't seem like it is sufficient to conclude that there is a largest element. I mean it covers all of the cases I suppose. But I feel that it is missing something, perhaps it's me not knowing when something is proven from when it is. – dc3rd May 12 '15 at 21:27

Consider $A'= \{ A_1, \dots, A_{n-1} \}$. $A'$ has $n-1$ elements and is simply ordered, so you can apply induction hypothesis, and say that $A'$ has a largest element. Let $\bar{a}$ be the largest element of $A'$.

Since $A$ is simply ordered, there are two cases:

1. If $A_n \ge \bar{a}$, then $A_n$ is the largest element of $A$.

2. If $A_n < \bar{a}$, then $\bar{a}$ is the largest element of $A$.

In any case, $A$ has a largest element and this concludes the proof.

Naming elements of $A$ in some way is not necessary and may be misleading.

The basis of induction is clear, so assume we know the statement for sets with $n\ge1$ elements and suppose $|A|=n+1$.

Pick an element $a\in A$. If $a$ is the largest element of $A$, we are done. Otherwise there is $b\in A\setminus\{a\}$ such that $b\not\le a$; since $A$ is simply ordered, $a<b$. Pick the largest element $c$ in $A\setminus\{a\}$, which exists by the induction hypothesis. Then $c$ is also the largest element of $A$, because $a<b\le c$.