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

  • $\begingroup$ A slight correction: the bijection $f$ exists because $A$ is finite and non-empty. $\endgroup$ – chelivery Dec 19 '16 at 16:03
  • $\begingroup$ @chelivery The empty set is vacuously a function with empty domain (in set theory). $\endgroup$ – Alberto Takase Dec 19 '16 at 16:29
  • $\begingroup$ @AlbertoTakase Look at how OP is defining $f$'s domain, though. In the context of this problem it's a valid clarification, as the argument wouldn't hold with an emply domain. $\endgroup$ – chelivery Dec 19 '16 at 16:36
  • $\begingroup$ @chelivery Right. OP should take your advice because more clarity in proofs is always a good thing. I simply wanted to point out that the empty set is a bijection from the empty set to the empty set. I did not take OP's domain into account. $\endgroup$ – Alberto Takase Dec 19 '16 at 16:46

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.

  • $\begingroup$ This induction ultimately has a kind of "algorithm" embedded in it which is analogous to what the OP was trying to do, but it is cleaner, less hand-wavy, and strictly formal. $\endgroup$ – chelivery Dec 19 '16 at 15:59

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.

  • $\begingroup$ Okay thanks for your criticism. Can you pinpoint exactly what makes my attempted proof an algorithm instead of an actual proof? Where does one draw the line between having repetitive steps in a proof and it being an algorithm? $\endgroup$ – Perturbative Dec 19 '16 at 16:36
  • $\begingroup$ Basically, the only way to do "repetitive" formally is induction. Every time a proof has a "and so on", or "dots", it means that induction is actually required. $\endgroup$ – Martin Argerami Dec 19 '16 at 16:43

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.