Careless Mathematical Induction Fallacy
$begingroup$
This fallacy is given in Bartle's Introduction to Real Analysis (page 15) and I am trying to figure out where the problem is in the "fake proof".
Here we are using $mathbb{N} = {1,2,3 dots } $
If $n in mathbb{N}$ and if $max (p,q) = n $ for $p,q in mathbb{N}$, then $p=q$
The base case $n=1$ does check out. If $max (p,q) = 1$, then we do have that $p=q$ since $p,q in mathbb{N}$.
Then we assume the statement is true for $k ge 1$ and we want to prove the statement is true for $k+1$.
Suppose $max (p,q) = k+1$. Then we have $max (p-1, q-1) = k$. Thus, we have $p-1 = q-1 implies p=q $ $tag*{$square$}$
Obviously this is an absurd statement, as this is not true in general. It is clear that the base case is correct, so the flaw must be somewhere in the induction step.
My only guess is that it stems from saying $max(p-1,q-1) = k$ and that somehow we have a subtle violation going on. I would like to be able to clearly see the violation. Any help would be greatly appreciated.
induction fake-proofs
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
$endgroup$
add a comment |
$begingroup$
This fallacy is given in Bartle's Introduction to Real Analysis (page 15) and I am trying to figure out where the problem is in the "fake proof".
Here we are using $mathbb{N} = {1,2,3 dots } $
If $n in mathbb{N}$ and if $max (p,q) = n $ for $p,q in mathbb{N}$, then $p=q$
The base case $n=1$ does check out. If $max (p,q) = 1$, then we do have that $p=q$ since $p,q in mathbb{N}$.
Then we assume the statement is true for $k ge 1$ and we want to prove the statement is true for $k+1$.
Suppose $max (p,q) = k+1$. Then we have $max (p-1, q-1) = k$. Thus, we have $p-1 = q-1 implies p=q $ $tag*{$square$}$
Obviously this is an absurd statement, as this is not true in general. It is clear that the base case is correct, so the flaw must be somewhere in the induction step.
My only guess is that it stems from saying $max(p-1,q-1) = k$ and that somehow we have a subtle violation going on. I would like to be able to clearly see the violation. Any help would be greatly appreciated.
induction fake-proofs
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
$endgroup$
6
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
1
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35
add a comment |
$begingroup$
This fallacy is given in Bartle's Introduction to Real Analysis (page 15) and I am trying to figure out where the problem is in the "fake proof".
Here we are using $mathbb{N} = {1,2,3 dots } $
If $n in mathbb{N}$ and if $max (p,q) = n $ for $p,q in mathbb{N}$, then $p=q$
The base case $n=1$ does check out. If $max (p,q) = 1$, then we do have that $p=q$ since $p,q in mathbb{N}$.
Then we assume the statement is true for $k ge 1$ and we want to prove the statement is true for $k+1$.
Suppose $max (p,q) = k+1$. Then we have $max (p-1, q-1) = k$. Thus, we have $p-1 = q-1 implies p=q $ $tag*{$square$}$
Obviously this is an absurd statement, as this is not true in general. It is clear that the base case is correct, so the flaw must be somewhere in the induction step.
My only guess is that it stems from saying $max(p-1,q-1) = k$ and that somehow we have a subtle violation going on. I would like to be able to clearly see the violation. Any help would be greatly appreciated.
induction fake-proofs
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
$endgroup$
This fallacy is given in Bartle's Introduction to Real Analysis (page 15) and I am trying to figure out where the problem is in the "fake proof".
Here we are using $mathbb{N} = {1,2,3 dots } $
If $n in mathbb{N}$ and if $max (p,q) = n $ for $p,q in mathbb{N}$, then $p=q$
The base case $n=1$ does check out. If $max (p,q) = 1$, then we do have that $p=q$ since $p,q in mathbb{N}$.
Then we assume the statement is true for $k ge 1$ and we want to prove the statement is true for $k+1$.
Suppose $max (p,q) = k+1$. Then we have $max (p-1, q-1) = k$. Thus, we have $p-1 = q-1 implies p=q $ $tag*{$square$}$
Obviously this is an absurd statement, as this is not true in general. It is clear that the base case is correct, so the flaw must be somewhere in the induction step.
My only guess is that it stems from saying $max(p-1,q-1) = k$ and that somehow we have a subtle violation going on. I would like to be able to clearly see the violation. Any help would be greatly appreciated.
induction fake-proofs
induction fake-proofs
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
edited Jan 26 at 23:02
WaveX
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
asked Jan 26 at 22:52
WaveXWaveX
2,5822722
2,5822722
6
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
1
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35
add a comment |
6
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
1
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35
6
6
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
1
1
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The problem is that $p-1,q-1$ might not be in $mathbb N$. For instance, consider $max (1,2)=2$ . The induction would direct us to look at $max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.
answered Jan 26 at 22:55
lulululu
40.7k24879
$endgroup$
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3088884%2fcareless-mathematical-induction-fallacy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The problem is that $p-1,q-1$ might not be in $mathbb N$. For instance, consider $max (1,2)=2$ . The induction would direct us to look at $max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.
answered Jan 26 at 22:55
lulululu
40.7k24879
$endgroup$
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
add a comment |
$begingroup$
The problem is that $p-1,q-1$ might not be in $mathbb N$. For instance, consider $max (1,2)=2$ . The induction would direct us to look at $max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.
answered Jan 26 at 22:55
lulululu
40.7k24879
$endgroup$
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
add a comment |
$begingroup$
The problem is that $p-1,q-1$ might not be in $mathbb N$. For instance, consider $max (1,2)=2$ . The induction would direct us to look at $max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.
answered Jan 26 at 22:55
lulululu
40.7k24879
$endgroup$
The problem is that $p-1,q-1$ might not be in $mathbb N$. For instance, consider $max (1,2)=2$ . The induction would direct us to look at $max(0,1)=1$ but that was not covered in the base case.
Note: if we considered $0$ as a natural number then the base case is false as presented (since $max (0,1)=1$ is a counterexample). Of course, we could consider the base case $n=0$ and that would still be correct.
answered Jan 26 at 22:55
lulululu
40.7k24879
answered Jan 26 at 22:55
lulululu
40.7k24879
answered Jan 26 at 22:55
lulululu
40.7k24879
answered Jan 26 at 22:55
lulululu
40.7k24879
40.7k24879
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
add a comment |
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
$begingroup$
Going by the logic this approach would also work if we did include $0$ in our definition of $mathbb{N}$. Then we would be looking at $max (-1,0)$ and once again we fall out of $mathbb{N}$, am I correct?
$endgroup$
– WaveX
Jan 26 at 22:58
2
2
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
Exactly right. We'd have $max (a,b)=0implies a=b=0$ but you couldn't do the induction, as the example $max (0,1)=1$ demonstrates.
$endgroup$
– lulu
Jan 26 at 22:58
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
$begingroup$
For what it's worth, this is a nice pattern to know. Basically all absurd fake proofs by induction rely on the 1->2 step being invalid by virtue of something wrong happening when you plug 1 in.
$endgroup$
– R..
Jan 27 at 3:07
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3088884%2fcareless-mathematical-induction-fallacy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
$begingroup$
Why can you take $p-1,q-1$? They might not be natural numbers. For instance, $max (1,2)=2$.
$endgroup$
– lulu
Jan 26 at 22:54
1
$begingroup$
This depends on whether you include $0$ in $mathbf N$ or not.
$endgroup$
– Bernard
Jan 26 at 22:55
$begingroup$
Lulu's answer below is excellent; I just want to point out that the tactic they used is exactly the right way to identify errors in induction proofs - instead of thinking about arbitrary choices of $n$, think specifically about the first few steps. Usually, if an induction proof is going to break down, it'll break down dramatically and clearly in those early steps.
$endgroup$
– Reese
Jan 27 at 2:22
$begingroup$
I'd add to the comment by @Reese that the place to look for an error in an induction proof is the smallest numbers where the alleged conclusion is wrong. In the case at hand, that would be where $n=2$ and ${p,q}={1,2}$.
$endgroup$
– Andreas Blass
Jan 27 at 4:15
$begingroup$
@WaveX: $Bbb N$ conventionally includes $0$. $Bbb N$ with $0$ removed is noted $Bbb N^*$.
$endgroup$
– fgrieu
Jan 27 at 8:35