Proposition:
Suppose $R$ is a total order on a set $A$. Prove that every finite,
nonempty set $B \subseteq A$ has an $R$-smallest element.
My attempt:
Cardinality of the set, say $A$, will be denoted as $|A|$.
By induction.
Base case:
Take $B = \{b\}$ such that $b \in A$. $b$ is the $R$-smallest element of $B$.
Induction step:
Suppose for all sets with $n$ elements, there will be smallest element.
Consider arbitrary set $B \subseteq A$ such that $|B| = n + 1$.
Take arbitrary $b \in B$.
Let $B' = B \setminus \{b\}$. By inductive hypothesis, $B'$ has $R$-smallest element. Let's call it $c$.
Now consider set $B$.
Suppose $cRb$. Then $c$ is the smallest element of $B$.
Suppose $bRc$. Take arbitrary $y \in B$. We know that $cRy$. By transitivity we have $bRy$. $y$ was arbitrary, hence $b$ is the smallest element of $B$.
Suppose that $\lnot bRc$ and $\lnot cRb$. This is impossible, because $R$ is a total order on $A$.
Therefore, either $c$ or $b$ will be the smallest element of $B$.
$\Box$
Is it correct?
Best Answer
Yes, that’s a pretty good solid proof.