24
$\begingroup$

Can somebody give a clear explanation why this is incorrect? thank you

Theorem 1: All positive integers are equal.

Proof: We show that any two positive integers are equal, from which the result follows. We do this by induction on the maximum of the two numbers. Let $P(n)$ be the statement “if $r$ and $s$ are positive integers and $\max \{ r, s \} = n$ then $r = s$.”

Clearly $P(1)$ is true. Suppose that $P(n)$ is true and let $r$ and $s$ be positive integers whose maximum is $n + 1$. Then $\max \{ r − 1, s − 1 \} = n$. By the inductive hypothesis, $r − 1 = s − 1$ and hence $r = s$. Thus $P(n + 1)$ is true.

The result is now proved by mathematical induction.

$\endgroup$
4
  • 1
    $\begingroup$ But clearly $P(2)$ is not true. $\endgroup$ May 15, 2017 at 7:25
  • 10
    $\begingroup$ To be completely clear, your proof of $P(n+1)$ fails when $n=1$, $r=2$, $s=1$. ($s-1$ fails to be a positive integer). $\endgroup$ May 15, 2017 at 7:27
  • 14
    $\begingroup$ The false assumption is that $r-1$ and $s-1$ must be positive, Since they are not guaranteed to be positive, you cannot say "By the inductive hypothesis....." $\endgroup$ May 15, 2017 at 8:09
  • 26
    $\begingroup$ It is false because it only works with horses. math.stackexchange.com/questions/428151/… $\endgroup$
    – Carsten S
    May 15, 2017 at 9:47

5 Answers 5

63
$\begingroup$

There's nothing wrong with the other answers already posted, but I'd like to step back and address a slightly broader question: if presented with this argument, how would you find the flaw?

Well, if the proof worked then it would establish P(1) and then P(2) and then P(3) and so on. If it doesn't, then one of these steps must fail. Here are two ways we can identify where it goes wrong. All of them are useful heuristics when tracking down bugs in proofs.

1. If it fails, it probably fails early. Let's look at the steps in order. P(1) is certainly correct, so what about the transition from P(1) to P(2) -- the first application of the inductive step? Let's plug in some specific numbers and see what happens: r=1,s=2 perhaps. Then r-1,s-1 are 0,1 ... and, aha, this doesn't fit our inductive hypothesis.

2. Compare doubful things against what we know is actually true. So, P(n) says that all positive integers up to n are equal. That's true for n=1 but false for n=2. So, again, this tells us to focus on n=2 and see what happens.

So, to recap, here are some general principles.

  • When an inductive proof fails, it usually fails "early". So try looking at small simple cases.
  • In particular, the very first actual inductive step is especially likely to be wrong. More generally, look at "edge cases".
  • If you can't immediately see the flaw in the reasoning, try out a concrete example.
  • Compare what the proof says should be true with what you know by other means is true. Look for the first point at which the proof jumps from something you believe is true to something you believe is false.
$\endgroup$
3
  • 2
    $\begingroup$ It's a bold claim that if an inductive proof fails, it usually does it early. But in this case nobody has to assume it, because it's obvious, that this induction must fail in the case P(2). In general I would say, if an inductive proof fails, we can hope, it fails early. $\endgroup$ May 16, 2017 at 11:43
  • $\begingroup$ @ÉdesIstvánGergely I'm often worried (as stupid as it sounds) there's a really big integer with properties completely different from all the other integers and it ends up breaking all inductive proofs. Like a number no ones looked at yet that's both odd and even $\endgroup$
    – Jam
    May 16, 2017 at 22:22
  • 2
    $\begingroup$ There is, but it's not that big. $\endgroup$ May 16, 2017 at 23:06
56
$\begingroup$

You state that $\max(r-1, s-1)=n\implies r-1=s-1$ by the inductive hypothesis. But the inductive hypothesis requires the two numbers to be positive integers, which would fail if either of $r$ or $s$ are $1$.

$\endgroup$
1
  • $\begingroup$ Best answer. To the point, no beating around the bush. It's that simple. $\endgroup$ May 16, 2017 at 11:59
5
$\begingroup$

Becase $P(n)\Rightarrow P(n+1)$ is not true for $n=1$.

It should be true for all natural $n$.

$\endgroup$
10
  • 5
    $\begingroup$ I feel like "explaining in detail" would include explaining why the provided proof of $P(n)\Rightarrow P(n+1)$ is wrong (i.e. why it fails for $n=1$). $\endgroup$
    – Wojowu
    May 15, 2017 at 11:50
  • $\begingroup$ @Wojowu Because we can not prove $P(2)$ by the arcadeboy's reasoning. Try it! $\endgroup$ May 15, 2017 at 13:33
  • 5
    $\begingroup$ I know why it's wrong, I'm just pointing out a complete answer should include that. $\endgroup$
    – Wojowu
    May 15, 2017 at 13:33
  • 1
    $\begingroup$ I'm not sure what I am supposed to say. It's vacuously true. $\endgroup$
    – Wojowu
    May 15, 2017 at 13:39
  • 4
    $\begingroup$ @user275313 The stated proof of $P(2)\implies P(3)$ is flawed, but the statement $P(2)\implies P(3)$ itself is true. $\endgroup$ May 15, 2017 at 18:25
0
$\begingroup$

I'll try a little more detailed answer. The proof's loophole is in this sentence:

Then $\max \{ r − 1, s − 1 \} = n$. By the inductive hypothesis, $r − 1 = s − 1$ and hence $r = s$.

For $P(n+1)$ we have to look at a "completely fresh set" of $r$ and $s$. We only know that $r, ~ s \in \mathbb{N}$, which doesn't mean $(r-1), ~ (s-1) \in \mathbb{N}$ as well. So your sentence considers only one (specifically (2.) below) of three different cases:

  1. $r = s = 1 \\ \Rightarrow \text{This case is not relevant, because there is no } n \in \mathbb{N} \text{ with } n+1=max \left \{ r, s \right \}$
  2. $r, ~ s \geq 2 \\ \Rightarrow (r-1), ~ (s-1) \geq 1 \\ \Rightarrow r, ~ s \in \mathbb{N} \\ \Rightarrow \text{You're allowed to use } P(n)$
  3. $r = 1, s \neq 1$ or $r \neq 1, s = 1$

You will never be able to prove (3.). Therefore you'll never complete the induction step.

$\endgroup$
-1
$\begingroup$

A very simple definition of mathematical induction can be found here

which states that it has two basic steps,defining the base case and then proving the induction step.


Base case: is to prove the given statement for the first element of the given set (set of positive integers in this case) "if r and s are positive integers and max{r,s}=n then r=s" for the base case, let r=s= 1 then max(1,1)=1 which is true


Now consider the induction step. Induction step: is to prove that, if the statement is assumed to be true for any one natural number, then it must be true for the next natural number as well. So if P(n) (which means max(r,s) = n ) is true then P(n+1) (which is max(r+1,s+1)=n+1 ) should also be true

$\endgroup$
1
  • $\begingroup$ I don't think this post addresses the fallacy in the question. This is just a definition of induction (which the question clearly understands). The point of the question is to find the flaw in the logic. $\endgroup$
    – Jam
    May 16, 2017 at 22:18

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