0
$\begingroup$

I wish to prove the result suggested in the title without induction on the cardinality of set. Here is my approach:

Let $S$ be a finite nonempty totally ordered set, i.e. $S=\lbrace x_{1},x_{2},\ldots,x_{n}\rbrace$, where $n$ is an arbitrary positive integer. For the purpose of contradiction, assume that $S$ does not have a maximum. Thus, for each $x_{i_{1}}\in S$, there exists some $x_{i_{2}}\in S$ such that $x_{i_{1}}<x_{i_{2}}$. Similarly, for $x_{i_{2}}$ there exists some $x_{i_{3}}\in S$ such that $x_{i_{2}}<x_{i_{3}}$. Continuing in this fashion we get $x_{i_{1}}<x_{i_{2}}<x_{i_{3}}<\cdots<x_{i_{n}}<\cdots$, which implies that $S$ is infinite, a contradiction.

I am very doubtful about the validity of the above argument. Could you please point out if and why it is wrong?

$\endgroup$
5
  • 2
    $\begingroup$ Seems fine to me but in essence you are still performing induction, now over the minimal number of elements that $S$ must contain (i.e. you are showing that $\lvert S\rvert\ge n$ for every $n\in\mathbb N$). $\endgroup$
    – Maximilian Janisch
    Commented Jun 13 at 11:11
  • 2
    $\begingroup$ "Continuing in this fashion [...]" is using induction (informally). What makes you think the argument is incorrect though? $\endgroup$
    – Tim Seifert
    Commented Jun 13 at 11:11
  • $\begingroup$ @TimSeifert Just a feeling, as a newbie it did not seem rigorous enough. $\endgroup$
    – Arian
    Commented Jun 13 at 11:15
  • 1
    $\begingroup$ Well, to make it more rigorous, you may want to make the induction you are informally performing more explicit. In particular, try to formulate exactly, what statement you are inducting over. But the argument itself is perfectly fine as is $\endgroup$
    – Tim Seifert
    Commented Jun 13 at 11:21
  • 1
    $\begingroup$ Another approach, which is constructive, is a variant of the algorithm called online bubble sort: (1) Mark $x_1$ as your current favorite, $x’$. (2) Successively for each $i \in \{2, \ldots, n\}$, if $x’ < x_i$, then update your favorite. (3) Now, since $<$ is a total order, $x’=\max_<\{x_1, \ldots, x_n\}$. $\endgroup$
    – Paul Tanenbaum
    Commented Jun 13 at 13:11

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .