0
$\begingroup$

enter image description here

I'm claiming that this proof is using the fact that $u < m+1$, which isn't valid. Because for any finite set of positive integers $K$, $\sup K = \max K$. Which means that it would be impossible for the supremum of a set of positive integers to be less than another integer in the same set. That is, the number $m$ in the author's proof must be the next integer less than the supremum.

Proof

Firstly, for all $k \in K$, $k \leq \max K$. So $\max K$ is an upperbound for $K$.

Now, let $v \in \mathbb{R}$ be any number less than $\max K$. Define $\epsilon = \max K - v >0$. Choose $s_\epsilon = \frac{\max K+v}{2}$. Then

$$\max K - \epsilon = v < \frac{\max K+v}{2} = s_\epsilon $$

Proving that $\sup K = \max K$. That means the author's supremum $u$ in the proof is the maximum integer of the nonempty set $\mathbb{N}$. Subtracting $1$ from $u$ would provide the next lowest integer. There would indeed exist $m \in \mathbb{N}$ s.t. $u -1 < m$ but that $m$ would have to equal $\max{\mathbb{N}}$. So, in conclusion, $u \nless m +1$.

Please let me know what you think.

$\endgroup$
7
  • $\begingroup$ "finite set of positive integers" -> which finite set of integers are you objecting to in the proof? The proof only mentions $\mathbb{N}$. $\endgroup$
    – Clement C.
    Nov 6, 2017 at 17:50
  • $\begingroup$ this proof by contradiction ! $\endgroup$
    – Hamada Al
    Nov 6, 2017 at 17:52
  • $\begingroup$ Yes, but it never assumes $\mathbb{N}$ is finite. It actually uses the fact that it's not finite to derive a contradiction... $\endgroup$
    – Clement C.
    Nov 6, 2017 at 17:53
  • $\begingroup$ That's another part which seems wrong to me. The first assumption the author uses is that $\mathbb{N}$ is bounded by $x$. Is that not synonymous with finite on the integers? $\endgroup$
    – Zduff
    Nov 6, 2017 at 17:54
  • 1
    $\begingroup$ It implicitly implies it, and this is why the author can derive a contradiction at the end. Assume $P$ ("$\mathbb{N}$ has an upper bound in $\mathbb{R}"$). Show, using the properties of $\mathbb{N}$ (in particular, it is not finite) that this leads to a contradiction. $\endgroup$
    – Clement C.
    Nov 6, 2017 at 17:56

1 Answer 1

4
$\begingroup$

The proof in the book is a proof by contradiction. As such, it contains a sequence of false statements. False statements in the proof include:

  1. $n \leq x$ for all $n \in \mathbb N$;
  2. $x$ is an upper bound of $\mathbb N$;
  3. the non-empty set $\mathbb N$ has a supremum $u \in \mathbb R$;
  4. there exists $m \in \mathbb N$ such that $u - 1 < m$ and $u$ is the supremum of $\mathbb N$;
  5. there exists $m$ such that $u < m+1,$ $m+1\in\mathbb N,$ and $u$ is the supremum of $\mathbb N$.

The idea of a proof by contradiction is that by the time we get to the last false statement, we know it is false. As you correctly observed, it is impossible that $u < m+1,$ given the way $u$ and $m$ were constructed. But in the proof, all of the false statements (including the last one) were shown to be consequences of the first false statement. Now that we know the last statement is false, we know the first statement also is false. Since the first statement was the negation of the thing we wanted to prove, we know the thing we wanted to prove is true.

$\endgroup$
2
  • $\begingroup$ Thank you for the clarification! I was getting seriously confused about how the whole contradiction process works, seeing as sometimes you can spot some falsehood during an author's proof. $\endgroup$
    – Zduff
    Nov 6, 2017 at 22:12
  • $\begingroup$ Wonderful explanation of proof by contradiction or reductio ad absurdum. $\endgroup$
    – Paramanand Singh
    Nov 7, 2017 at 3:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .