Proof verification: a non-empty finite simply ordered set has a largest element

Question

Let $A$ be a non-empty finite simply ordered set. Show that $A$ has a largest element

---

My Attempted Proof:

Since $A$ is finite, there exists a bijection of a subset of $\mathbb{Z_+}$ with $A$.

$$\text{i.e.} \ \exists f \ \ \text{ such that } \ \ f : [1, ..., n] \to A$$

where $f$ is bijective. Since $f$ is bijective we can show $A$ has a largest element in the following way.

Put $f(1) = a_1$ where $A_1 \in A$. Let $\alpha = a_1$

1. Let $f(m) = a_m$ where $a_m \in A$ and $1 \leq m < n-1$. If $a_m > a_1$ then $\alpha = a_m$

2. Now take $f(m+1) = a_{m+1}$ where $a_{m+1} \in A$ and $2 \leq m+1 \leq n$. If $a_{m+1} > a_m$, then let $\alpha = a_{m+1}$

Repeat $1$ and $2$ above for increasing $m$ until $m+1 =n$. Then $\alpha$ is the largest element of $A$ as desired $\square$.

---

Is this proof correct or incorrect? If it is correct, how rigorous is it? If it is incorrect, please can you give a reason why it is incorrect (I'm trying to spot flaws in my logic and arguments as best as possible, so any criticism helps).

Answer 1

Hint: Use induction on the size of the set $A$.

Base Case: $|A|=1$ is trivial.

Inductive Step: Assume every ordered set of cardinality equal to (or less than) $n$ has a maximum. We seek to show that every ordered set of cardinality equal to $n+1$ has a maximum. (continue from here)

---

You have proven the following:

Let $ X $ be a set. If $ X $ is finite, then there exists a total order in $ X $ and for each total order in $ X $, every nonempty subset of $ X $ has a least element and a greatest element.

What is interesting is that a converse also holds, and gives a characterization for the notion of finiteness:

Let $ X $ be a set. If there exists a total order in $ X $ such that every nonempty subset of $ X $ has a least element and a greatest element, then $ X $ is finite.

Answer 2

You think like a programmer. What you wrote is an algorithm, not a proof. In this case the intuition of the algorithm is clear, but in general proving that an algorithm achieves precisely what you want it to do is no easy task.

A formal proof would be achieved (as is almost always the case with natural numbers) by induction.

Answer 3

I think that the proof is OK, but you can make it much briefer. For example, using induction, as @Takase have suggested.

The statement is obvious if $A$ has one element. If $A$ have more elements then take any $a\in A$. Let $A'=\{a'\in A:a'>a\}$. Note that $a\notin A$. If $A'$ is empty you are done, because $a$ is the largest element. Otherwise, since $A'$ has less many elements than $A$, you can apply induction to find the largest element in $A'$.