All natural numbers are equal.
$begingroup$
I saw the following "theorem" and its "proof".
I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand.
Theorem: All natural numbers are equal.
Let $a, b in mathbb{N}$, then a=b.
Proof by induction.
Let $m=max{a, b}$. We will prove that the theorem holds for all $min mathbb{N}$.
If $m=1$, then $max{a,b}=1$, so $a=b=1$.
Now assume that it holds for $m=k$ for some number $k$.
Now let $max{a, b}=k+1$. Then $max{a-1, b-1}=k$ and thus by assumption $a-1=b-1$, so $a=b$.
Therefore, the proof is complete.
induction fake-proofs
$endgroup$
|
show 1 more comment
$begingroup$
I saw the following "theorem" and its "proof".
I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand.
Theorem: All natural numbers are equal.
Let $a, b in mathbb{N}$, then a=b.
Proof by induction.
Let $m=max{a, b}$. We will prove that the theorem holds for all $min mathbb{N}$.
If $m=1$, then $max{a,b}=1$, so $a=b=1$.
Now assume that it holds for $m=k$ for some number $k$.
Now let $max{a, b}=k+1$. Then $max{a-1, b-1}=k$ and thus by assumption $a-1=b-1$, so $a=b$.
Therefore, the proof is complete.
induction fake-proofs
$endgroup$
4
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
5
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
11
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
6
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
3
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01
|
show 1 more comment
$begingroup$
I saw the following "theorem" and its "proof".
I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand.
Theorem: All natural numbers are equal.
Let $a, b in mathbb{N}$, then a=b.
Proof by induction.
Let $m=max{a, b}$. We will prove that the theorem holds for all $min mathbb{N}$.
If $m=1$, then $max{a,b}=1$, so $a=b=1$.
Now assume that it holds for $m=k$ for some number $k$.
Now let $max{a, b}=k+1$. Then $max{a-1, b-1}=k$ and thus by assumption $a-1=b-1$, so $a=b$.
Therefore, the proof is complete.
induction fake-proofs
$endgroup$
I saw the following "theorem" and its "proof".
I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand.
Theorem: All natural numbers are equal.
Let $a, b in mathbb{N}$, then a=b.
Proof by induction.
Let $m=max{a, b}$. We will prove that the theorem holds for all $min mathbb{N}$.
If $m=1$, then $max{a,b}=1$, so $a=b=1$.
Now assume that it holds for $m=k$ for some number $k$.
Now let $max{a, b}=k+1$. Then $max{a-1, b-1}=k$ and thus by assumption $a-1=b-1$, so $a=b$.
Therefore, the proof is complete.
induction fake-proofs
induction fake-proofs
edited Mar 27 '13 at 14:43
Community♦
1
1
asked Mar 27 '13 at 1:17
SnowSnow
872820
872820
4
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
5
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
11
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
6
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
3
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01
|
show 1 more comment
4
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
5
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
11
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
6
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
3
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01
4
4
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
5
5
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
11
11
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
6
6
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
3
3
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01
|
show 1 more comment
11 Answers
11
active
oldest
votes
$begingroup$
The error lies in the fact that when decreasing $1$ you may get out of the set $mathbb{N}$ - and indeed, $max{1,2}=max{0,1}+1$, but $0 ne 1$, and $0notin mathbb{N}$ as you defined it.
$endgroup$
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
add a comment |
$begingroup$
The problem starts with this sentence:
Now assume that it holds for $m = k$ for some number $k$.
Assume that what holds for some $k$? What is the it that is to be assumed holds?
If $max(a, b) = k$, it means that either
- $a = k cap 1 le b lt k$; or
- $b = k cap 1 le a lt k$; or
- $a = b = k$.
In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:
- $max(a, b) = k implies a = b = k$
So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.
Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.
For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.
The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.
One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.
$endgroup$
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
add a comment |
$begingroup$
Hint:
The smallest case where your "theorem" is obviously wrong is the set ${1,2}$. Now check every step of the "proof" with this example. What goes wrong?
$endgroup$
add a comment |
$begingroup$
It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as:
$$forall a, forall ble a,a = b = max{a,b}$$
which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as,
$$forall (a,b)in mathbb{N}timesmathbb{N}, a = b = max{a,b} $$
which would require us to impose an ordering on $mathbb{N} times mathbb{N}$ and induct along this ordering, it is written as:
$$forall m, m = max{a,b}, m = a = b$$
Which hides the quantifiers on $a$ and $b$ (namely, ex. $forall a,b le m$).
$endgroup$
add a comment |
$begingroup$
One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = max{1,2}$ and $1 = max{0,1}$.
$endgroup$
add a comment |
$begingroup$
Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.
This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).
$endgroup$
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
add a comment |
$begingroup$
Hint $ $ Here is a constructive viewpoint. We use $,0,$ vs. $,1,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $rm a= b !iff! a!-!1 = b!-!1!iff! a!-!2 = b!-!2!iffcdots:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $rm:n = 0:$ or $rm: 0 = n,:$ not in a single base case $rm: 0 = 0.:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $,0 = 0,$ (or $1 =1$ using $rm,n=1,$ as base case). If that were true, then the equality test would indeed always return true.
$endgroup$
add a comment |
$begingroup$
"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related
$endgroup$
add a comment |
$begingroup$
If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !
$endgroup$
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
add a comment |
$begingroup$
If $m=2$ then, following your demonstration we have $m=max{a,b}Rightarrow max{a-1,b-1}=1Rightarrow a-1=b-1Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $aneq b$ it just won't work.
$endgroup$
add a comment |
$begingroup$
the first assumption was $m=k$ or $max(a,b)=k$, but the theory is letting $max(a,b)=k+1$ meaning "$max(a,b)=max(a,b)+1$" which drives the proof wrong!
$endgroup$
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
add a comment |
protected by T. Bongers Dec 14 '18 at 16:39
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
11 Answers
11
active
oldest
votes
11 Answers
11
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The error lies in the fact that when decreasing $1$ you may get out of the set $mathbb{N}$ - and indeed, $max{1,2}=max{0,1}+1$, but $0 ne 1$, and $0notin mathbb{N}$ as you defined it.
$endgroup$
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
add a comment |
$begingroup$
The error lies in the fact that when decreasing $1$ you may get out of the set $mathbb{N}$ - and indeed, $max{1,2}=max{0,1}+1$, but $0 ne 1$, and $0notin mathbb{N}$ as you defined it.
$endgroup$
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
add a comment |
$begingroup$
The error lies in the fact that when decreasing $1$ you may get out of the set $mathbb{N}$ - and indeed, $max{1,2}=max{0,1}+1$, but $0 ne 1$, and $0notin mathbb{N}$ as you defined it.
$endgroup$
The error lies in the fact that when decreasing $1$ you may get out of the set $mathbb{N}$ - and indeed, $max{1,2}=max{0,1}+1$, but $0 ne 1$, and $0notin mathbb{N}$ as you defined it.
answered Mar 27 '13 at 1:20
Alfonso FernandezAlfonso Fernandez
3,46221421
3,46221421
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
add a comment |
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
$begingroup$
But what would be wrong, if the proof did not target N but Z ?! Then the proof would still not be right & it would be possible to decrease 1...
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:38
24
24
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
@LucianDepold if the numbers were in $mathbb{Z}$, you wouldn't be able to provide a base case...
$endgroup$
– Alfonso Fernandez
Mar 27 '13 at 15:45
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
you are right !
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:47
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
$begingroup$
All of this is false. You can make a minor modification to the "proof" which leaves it just as obtuse, but avoids this issue. For instance, suppose it says `Now let $max(a+1,b+1) = k+1$. Then $max(a, b) = k$, and by the assumption, $a = b$. Look, even shorter!
$endgroup$
– Kaz
Mar 28 '13 at 1:11
8
8
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
$begingroup$
@Kaz That's still the same mistake: you can't assume that two natural numbers can be written as $a+1,b+1$ where $a,b$ are natural. Namely, it fails for $(a+1,b+1)=(1,2)$.
$endgroup$
– Alfonso Fernandez
Mar 28 '13 at 2:15
add a comment |
$begingroup$
The problem starts with this sentence:
Now assume that it holds for $m = k$ for some number $k$.
Assume that what holds for some $k$? What is the it that is to be assumed holds?
If $max(a, b) = k$, it means that either
- $a = k cap 1 le b lt k$; or
- $b = k cap 1 le a lt k$; or
- $a = b = k$.
In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:
- $max(a, b) = k implies a = b = k$
So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.
Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.
For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.
The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.
One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.
$endgroup$
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
add a comment |
$begingroup$
The problem starts with this sentence:
Now assume that it holds for $m = k$ for some number $k$.
Assume that what holds for some $k$? What is the it that is to be assumed holds?
If $max(a, b) = k$, it means that either
- $a = k cap 1 le b lt k$; or
- $b = k cap 1 le a lt k$; or
- $a = b = k$.
In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:
- $max(a, b) = k implies a = b = k$
So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.
Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.
For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.
The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.
One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.
$endgroup$
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
add a comment |
$begingroup$
The problem starts with this sentence:
Now assume that it holds for $m = k$ for some number $k$.
Assume that what holds for some $k$? What is the it that is to be assumed holds?
If $max(a, b) = k$, it means that either
- $a = k cap 1 le b lt k$; or
- $b = k cap 1 le a lt k$; or
- $a = b = k$.
In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:
- $max(a, b) = k implies a = b = k$
So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.
Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.
For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.
The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.
One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.
$endgroup$
The problem starts with this sentence:
Now assume that it holds for $m = k$ for some number $k$.
Assume that what holds for some $k$? What is the it that is to be assumed holds?
If $max(a, b) = k$, it means that either
- $a = k cap 1 le b lt k$; or
- $b = k cap 1 le a lt k$; or
- $a = b = k$.
In the special case $k = 1$, the first two cases are ruled out, but they are not ruled out when $k > 1$. So what the proof is assuming true for any $k$ is just the third case:
- $max(a, b) = k implies a = b = k$
So this is basically a case of incomplete case analysis: conveniently ignoring cases in the general truth, because they do not occur in the base case, and simply proceeding from the base case via induction without further considering the missing cases.
Another issue with the proof is that it only argues for the equality of the variables $a = b$. This conclusion does not permit us to believe that all numbers are equal. For that, it would be necessary to prove something like $a = a - 1$, for any $a$, which then connects with the base case $a = 1$. To goal of the proof should be to show that any two arbitrarily chosen natural numbers $a$ and $b$ are equal. But in the proof, $a$ and $b$ are anything but independent of each other, or of the parameter $k$.
For the proof to even try to show that the numbers are equal, what it requires us to believe is not simply that $a = b = k$ for an arbitrary $k$, but in fact that literally the original base relation holds for arbitrary $k$. Namely that $max(a, b) = k implies a = b = 1$ just like in the base case where $k = m = 1$. This is actually the it which is to be assumed. But of course, that just begs the question! If we simply assume that all numbers are equal to 1, then of course they are all equal, Q.E.D.
The proof obfuscates its poor logic by actually not stating it, and alluding to it via the pronoun it which has no clear antecedent. It makes an overture which hints at an inductive structure (base case, inductive step) and hopes that the reader's mind will somehow blunder in trying to connect the pieces.
One more flaw is this use of $a$ and $b$ as distractors to obfuscate vacuous truths. In induction along a single discrete variable, we have some logical proposition $P(n)$ which we show to be true for some base cases, for example showing that $P(1)$ is true. Then we show that the inductive hypothesis is true: namely $P(k)implies P(k + 1)$. The statement $P$ consists of some equation which involves only functions of $k$, and no other independent variables. If symbols other than $k$ appear, they are either constants, or functions of $k$ (dependent variables). In our proof, the variables $a$ and $b$ are such functions of $k$. In fact, it is assumed that $a = b = k$. So $max(a, b) = k$ really means $max(k, k) = k$, and $a = b$ just means $k = k$.
edited Mar 28 '13 at 1:17
answered Mar 27 '13 at 2:47
KazKaz
6,24311328
6,24311328
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
add a comment |
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
$begingroup$
+1, very good explanation. The second case should be $b = k cap 1 le a lt k$.
$endgroup$
– Leo
Mar 27 '13 at 14:26
2
2
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
I don't agree. What the induction step is assuming is that whenever $a,binBbb N$ and $max(a,b)=k$ then (it has been proven that) $a=b$. Now to prove the same for $a',b'inBbb n$ with $max(a',b')=k+1$, it tries to apply the indiction hypothesis for $a=a'-1$ and $b=b'-1$. There is no case analysis. The only error is that the proof forgets the necessary check of the condition $a,binBbb N$ of the induction hypothesis, which of cours cannot be ensured.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:01
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
$begingroup$
@MarcVanLeeuwen Ha, I was just revising the answer as you wrote your comment. The poor case analysis is a flaw, but not really the smoking gun.
$endgroup$
– Kaz
Mar 27 '13 at 18:37
2
2
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
$begingroup$
This deserves more upvotes!!!
$endgroup$
– Pedro Tamaroff♦
Mar 28 '13 at 5:34
1
1
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
$begingroup$
This answer is not particularly relevant. What was assumed in the induction step ("assume that it holds for m=k") was the following: for all integers $a,b$ with $max(a,b) = k$, $a = b$. This is completely fine; no cases were ignored; there was no assumed equality between $a$ and $b$. The error was then concluding from this that for all $a, b$ with $max(a,b) = k+1$, $a = b$, which does not follow, because $a-1, b-1$ could lie outside the natural numbers, as has already been explained by the top answer.
$endgroup$
– 6005
Jul 19 '15 at 16:53
add a comment |
$begingroup$
Hint:
The smallest case where your "theorem" is obviously wrong is the set ${1,2}$. Now check every step of the "proof" with this example. What goes wrong?
$endgroup$
add a comment |
$begingroup$
Hint:
The smallest case where your "theorem" is obviously wrong is the set ${1,2}$. Now check every step of the "proof" with this example. What goes wrong?
$endgroup$
add a comment |
$begingroup$
Hint:
The smallest case where your "theorem" is obviously wrong is the set ${1,2}$. Now check every step of the "proof" with this example. What goes wrong?
$endgroup$
Hint:
The smallest case where your "theorem" is obviously wrong is the set ${1,2}$. Now check every step of the "proof" with this example. What goes wrong?
edited Mar 27 '13 at 1:47
answered Mar 27 '13 at 1:20
azimutazimut
16.4k1051100
16.4k1051100
add a comment |
add a comment |
$begingroup$
It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as:
$$forall a, forall ble a,a = b = max{a,b}$$
which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as,
$$forall (a,b)in mathbb{N}timesmathbb{N}, a = b = max{a,b} $$
which would require us to impose an ordering on $mathbb{N} times mathbb{N}$ and induct along this ordering, it is written as:
$$forall m, m = max{a,b}, m = a = b$$
Which hides the quantifiers on $a$ and $b$ (namely, ex. $forall a,b le m$).
$endgroup$
add a comment |
$begingroup$
It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as:
$$forall a, forall ble a,a = b = max{a,b}$$
which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as,
$$forall (a,b)in mathbb{N}timesmathbb{N}, a = b = max{a,b} $$
which would require us to impose an ordering on $mathbb{N} times mathbb{N}$ and induct along this ordering, it is written as:
$$forall m, m = max{a,b}, m = a = b$$
Which hides the quantifiers on $a$ and $b$ (namely, ex. $forall a,b le m$).
$endgroup$
add a comment |
$begingroup$
It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as:
$$forall a, forall ble a,a = b = max{a,b}$$
which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as,
$$forall (a,b)in mathbb{N}timesmathbb{N}, a = b = max{a,b} $$
which would require us to impose an ordering on $mathbb{N} times mathbb{N}$ and induct along this ordering, it is written as:
$$forall m, m = max{a,b}, m = a = b$$
Which hides the quantifiers on $a$ and $b$ (namely, ex. $forall a,b le m$).
$endgroup$
It's true that $a-1$ and $b-1$ may not be in the naturals, but what this fact is really getting at is that you don't have enough initial conditions. The argument is phrased to hide this. Instead of writing the claim as:
$$forall a, forall ble a,a = b = max{a,b}$$
which shows that we have to induct over $a$, and then within this, induct over $b$, or perhaps as,
$$forall (a,b)in mathbb{N}timesmathbb{N}, a = b = max{a,b} $$
which would require us to impose an ordering on $mathbb{N} times mathbb{N}$ and induct along this ordering, it is written as:
$$forall m, m = max{a,b}, m = a = b$$
Which hides the quantifiers on $a$ and $b$ (namely, ex. $forall a,b le m$).
answered Mar 27 '13 at 1:49
LukeLuke
1513
1513
add a comment |
add a comment |
$begingroup$
One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = max{1,2}$ and $1 = max{0,1}$.
$endgroup$
add a comment |
$begingroup$
One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = max{1,2}$ and $1 = max{0,1}$.
$endgroup$
add a comment |
$begingroup$
One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = max{1,2}$ and $1 = max{0,1}$.
$endgroup$
One obvious problem is that $a-1$ or $b-1$ might be zero. So for $m = 2 $ you have for example $2 = max{1,2}$ and $1 = max{0,1}$.
answered Mar 27 '13 at 1:21
ThomasThomas
35.5k1056116
35.5k1056116
add a comment |
add a comment |
$begingroup$
Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.
This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).
$endgroup$
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
add a comment |
$begingroup$
Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.
This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).
$endgroup$
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
add a comment |
$begingroup$
Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.
This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).
$endgroup$
Sneaky induction proofs always fail in the same way (or at least all the ones I've seen do): the induction step doesn't apply to the base case. When you say, "assume the theorem holds for $m$", you naturally think of $m$ as arbitrary, and hence moderately large. But $m$ is any natural number, so you have to check all of them.
This is very similar to the inductive every horse is the same color proof (in fact, it's probably just the same "proof" reworded in terms of natural numbers). In that proof, there is the same fallacy: the induction step does not apply to the base case (if you take two distinct $2 - 1$ element subsets of a $2$ element set, they do not intersect).
answered Mar 27 '13 at 7:23
asmeurerasmeurer
5,86742443
5,86742443
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
add a comment |
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
1
1
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
$begingroup$
No, in this proof every instance of the induction step fails, as the lesser of $a,b$ can always be $1$, no matter what value $max(a,b)$ has. And antyway saying "the induction step doesn't apply to the base case" is not precise, as the base case and the induction step are disjoint (and almost in all correct induction proofs the induction step must use somewhere that this is not the base case). You mean the smallest instance of the induction step, just beyond the base case.
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 18:14
add a comment |
$begingroup$
Hint $ $ Here is a constructive viewpoint. We use $,0,$ vs. $,1,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $rm a= b !iff! a!-!1 = b!-!1!iff! a!-!2 = b!-!2!iffcdots:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $rm:n = 0:$ or $rm: 0 = n,:$ not in a single base case $rm: 0 = 0.:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $,0 = 0,$ (or $1 =1$ using $rm,n=1,$ as base case). If that were true, then the equality test would indeed always return true.
$endgroup$
add a comment |
$begingroup$
Hint $ $ Here is a constructive viewpoint. We use $,0,$ vs. $,1,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $rm a= b !iff! a!-!1 = b!-!1!iff! a!-!2 = b!-!2!iffcdots:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $rm:n = 0:$ or $rm: 0 = n,:$ not in a single base case $rm: 0 = 0.:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $,0 = 0,$ (or $1 =1$ using $rm,n=1,$ as base case). If that were true, then the equality test would indeed always return true.
$endgroup$
add a comment |
$begingroup$
Hint $ $ Here is a constructive viewpoint. We use $,0,$ vs. $,1,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $rm a= b !iff! a!-!1 = b!-!1!iff! a!-!2 = b!-!2!iffcdots:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $rm:n = 0:$ or $rm: 0 = n,:$ not in a single base case $rm: 0 = 0.:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $,0 = 0,$ (or $1 =1$ using $rm,n=1,$ as base case). If that were true, then the equality test would indeed always return true.
$endgroup$
Hint $ $ Here is a constructive viewpoint. We use $,0,$ vs. $,1,$ as base case. Suppose we have a natural number computer that has no subtraction operation, but does have a decrement operation. Then we can reduce equality testing of naturals to zero testing, by implementing a recursive algorithm that continually decrements both numbers $rm a= b !iff! a!-!1 = b!-!1!iff! a!-!2 = b!-!2!iffcdots:$ till we reach the "base" case where one is zero; then we test if the other is zero using the zero-test operation. Notice that the algorithm terminates in "base" cases of the form $rm:n = 0:$ or $rm: 0 = n,:$ not in a single base case $rm: 0 = 0.:$ The given "proof" can be viewed as an implementation of this algorithm, presuming that the recursion always terminates in the single base case $,0 = 0,$ (or $1 =1$ using $rm,n=1,$ as base case). If that were true, then the equality test would indeed always return true.
answered Mar 27 '13 at 2:14
Math GemsMath Gems
17k11938
17k11938
add a comment |
add a comment |
$begingroup$
"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related
$endgroup$
add a comment |
$begingroup$
"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related
$endgroup$
add a comment |
$begingroup$
"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related
$endgroup$
"Then max{a−1,b−1}=k and thus by assumption a−1=b−1"
This seems to be the problem in the explanation
By which assumption should these be equal?
The only prior statement that talks about the arguments to max{ } being equal is when k = 1, and that is a specific case and not for any general value
Also, this might be related
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Mar 27 '13 at 4:24
user13267user13267
2301418
2301418
add a comment |
add a comment |
$begingroup$
If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !
$endgroup$
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
add a comment |
$begingroup$
If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !
$endgroup$
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
add a comment |
$begingroup$
If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !
$endgroup$
If all natural numbers were equal, then for $m=1$, $a=b=1$ but for $m=2$ there have to be some numbers that are greater than $1$! Therefore not all numbers are equal! The induction itself uses natural numbers, that differ from each other. $m=1$ differs from the value $m=2$ ! And with that we try to prove that they don't differ !
edited May 8 '13 at 12:01
answered Mar 27 '13 at 8:39
Lucian DepoldLucian Depold
1195
1195
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
add a comment |
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
3
3
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
The question was not if all natural numbers are equal, but why the given proof for this (obviously wrong) statement is incorrect.
$endgroup$
– azimut
Mar 27 '13 at 15:26
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
$begingroup$
yes i know. the the induction step from m=1 to m=2 contains already the contradiction, i wanted to point that out
$endgroup$
– Lucian Depold
Mar 27 '13 at 15:29
add a comment |
$begingroup$
If $m=2$ then, following your demonstration we have $m=max{a,b}Rightarrow max{a-1,b-1}=1Rightarrow a-1=b-1Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $aneq b$ it just won't work.
$endgroup$
add a comment |
$begingroup$
If $m=2$ then, following your demonstration we have $m=max{a,b}Rightarrow max{a-1,b-1}=1Rightarrow a-1=b-1Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $aneq b$ it just won't work.
$endgroup$
add a comment |
$begingroup$
If $m=2$ then, following your demonstration we have $m=max{a,b}Rightarrow max{a-1,b-1}=1Rightarrow a-1=b-1Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $aneq b$ it just won't work.
$endgroup$
If $m=2$ then, following your demonstration we have $m=max{a,b}Rightarrow max{a-1,b-1}=1Rightarrow a-1=b-1Rightarrow a=b=2$. So $a$ and $b$ MOST be equal 2. So in general this will only works when $a=b$. That's the error, when $aneq b$ it just won't work.
answered Mar 27 '13 at 15:39
rimanriman
11
11
add a comment |
add a comment |
$begingroup$
the first assumption was $m=k$ or $max(a,b)=k$, but the theory is letting $max(a,b)=k+1$ meaning "$max(a,b)=max(a,b)+1$" which drives the proof wrong!
$endgroup$
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
add a comment |
$begingroup$
the first assumption was $m=k$ or $max(a,b)=k$, but the theory is letting $max(a,b)=k+1$ meaning "$max(a,b)=max(a,b)+1$" which drives the proof wrong!
$endgroup$
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
add a comment |
$begingroup$
the first assumption was $m=k$ or $max(a,b)=k$, but the theory is letting $max(a,b)=k+1$ meaning "$max(a,b)=max(a,b)+1$" which drives the proof wrong!
$endgroup$
the first assumption was $m=k$ or $max(a,b)=k$, but the theory is letting $max(a,b)=k+1$ meaning "$max(a,b)=max(a,b)+1$" which drives the proof wrong!
edited Mar 27 '13 at 16:31
robjohn♦
267k27308632
267k27308632
answered Mar 27 '13 at 11:57
messmess
1
1
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
add a comment |
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
$begingroup$
The theory does contradict the assumption: we proceed by induction. And the assumption is the privious step, not an assumption in the next step.
$endgroup$
– awllower
Mar 27 '13 at 12:19
add a comment |
protected by T. Bongers Dec 14 '18 at 16:39
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
4
$begingroup$
To use m = 1 is a bad idea, since this is a one case scenario (there's only one natural in the set {1}). If k > 1, then, after max {a,b} = k, why do you assume that a - 1 = b - 1?
$endgroup$
– Francisco Presencia
Mar 27 '13 at 5:36
5
$begingroup$
Just a comment on the form: since your theorem does not mention $m$, it is pointless to say the theorem holds for all $m$. What you mean is "Proof by induction on $max(a,b)$". In general it is good to always let "by induction" be followed by "on [something]".
$endgroup$
– Marc van Leeuwen
Mar 27 '13 at 9:03
11
$begingroup$
All natural numbers are equal, but some natural numbers are more equal than others.
$endgroup$
– Asaf Karagila♦
Mar 27 '13 at 13:27
6
$begingroup$
...but some numbers are more equal than others.
$endgroup$
– knutole
Mar 27 '13 at 13:50
3
$begingroup$
en.wikipedia.org/wiki/All_horses_are_the_same_color has a similar idea for where it goes wrong that may be useful here.
$endgroup$
– JB King
Mar 27 '13 at 18:01