3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Crostul May 12 '15 at 21:19
  • $\begingroup$ I think you should do induction on the size of $A$. $\endgroup$ – Gregory Grant May 12 '15 at 21:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dc3rd May 12 '15 at 21:27
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.