Mixing
Why is complete strong induction a valid proof method?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I recently learned about complete strong induction. I am familiar with both strong induction and ordinary induction and make sense. But what particularly confuses me is why we do not to explicit the base cases for complete induction. They seem crucial for modus ponens to work and thus, actually show the stand alone proposition $p(n)$ to be true.
The claim for complete induction seems to be the following:
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
These are my thoughts:
In induction we actually do two things (to show $ P(n) $ for all $ n in mathbb N$) :
- show P(0)
- show implication $ P(n-1) implies P(n) $
or for strong induction
- show P(0)
- show implication $ forall m, m < n, P(m) implies P(n) $
However, in complete induction we only show:
- $ forall m, m < n, P(m) implies P(n) $
now that I’ve thought of it more carefully, what bothers me is that in the inductive step we actually only show an implication is true, not that $P(n)$ is true. Intuitively, $P(n)$ ends up true because of Modus Ponens (MP), which forcibly requires checking some set of base cases, say $P(0)$.
What concerns me is the following: ff we show $ forall m, m < n, P(m) implies P(n) $ then we shown the implication is true, and not necessarily anything else. If $n=0$ then $ forall m, m < n, P(m) implies P(n) $ is False. So sure, the implication is (vacuously) true, but that doesn’t necessarily say $P(0)$ is true stand alone (which is what induction ultimately cares about!).
My assumption is that the claim the wikipedia article does is that (somehow) whatever proof for $ forall m, m < n, P(m) implies P(n) $ that we have must also be a stand alone proof for $P(0)$. I guess I could abstractly believe that’s true (mostly on faith), but it seems rather odd to me. I’ve never seen False implies $P(n)$ implies $P(n)$. It’s nearly like the truth table for implication is built so that if you only know the antecedent is False, then you can’t decide if the consequent is true. Which makes sense. A false starting point should intuitively get you no where or get you everywhere (by principle of explosion).
So my question is, whats going on? Is it just that the proof for $ forall m, m < n, P(m) implies P(n) $ can also be plugged in for a proof for $P(0)$ and then $P(0)$ is true? Or am I missing something?
I have a feeling that this being so abstract makes it hard to be believable and a concrete example of how $ forall m, m < n, P(m) implies P(n) $ automagically makes $P(0)$ (the base cases) true would be really valuable.
Another useful source:
https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction
proof-verification logic induction proof-explanation
asked 1 hour ago
Charlie Parker
1,0381128
add a comment |Â
up vote
2
down vote
favorite
I recently learned about complete strong induction. I am familiar with both strong induction and ordinary induction and make sense. But what particularly confuses me is why we do not to explicit the base cases for complete induction. They seem crucial for modus ponens to work and thus, actually show the stand alone proposition $p(n)$ to be true.
The claim for complete induction seems to be the following:
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
These are my thoughts:
In induction we actually do two things (to show $ P(n) $ for all $ n in mathbb N$) :
- show P(0)
- show implication $ P(n-1) implies P(n) $
or for strong induction
- show P(0)
- show implication $ forall m, m < n, P(m) implies P(n) $
However, in complete induction we only show:
- $ forall m, m < n, P(m) implies P(n) $
now that I’ve thought of it more carefully, what bothers me is that in the inductive step we actually only show an implication is true, not that $P(n)$ is true. Intuitively, $P(n)$ ends up true because of Modus Ponens (MP), which forcibly requires checking some set of base cases, say $P(0)$.
What concerns me is the following: ff we show $ forall m, m < n, P(m) implies P(n) $ then we shown the implication is true, and not necessarily anything else. If $n=0$ then $ forall m, m < n, P(m) implies P(n) $ is False. So sure, the implication is (vacuously) true, but that doesn’t necessarily say $P(0)$ is true stand alone (which is what induction ultimately cares about!).
My assumption is that the claim the wikipedia article does is that (somehow) whatever proof for $ forall m, m < n, P(m) implies P(n) $ that we have must also be a stand alone proof for $P(0)$. I guess I could abstractly believe that’s true (mostly on faith), but it seems rather odd to me. I’ve never seen False implies $P(n)$ implies $P(n)$. It’s nearly like the truth table for implication is built so that if you only know the antecedent is False, then you can’t decide if the consequent is true. Which makes sense. A false starting point should intuitively get you no where or get you everywhere (by principle of explosion).
So my question is, whats going on? Is it just that the proof for $ forall m, m < n, P(m) implies P(n) $ can also be plugged in for a proof for $P(0)$ and then $P(0)$ is true? Or am I missing something?
I have a feeling that this being so abstract makes it hard to be believable and a concrete example of how $ forall m, m < n, P(m) implies P(n) $ automagically makes $P(0)$ (the base cases) true would be really valuable.
Another useful source:
https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction
proof-verification logic induction proof-explanation
asked 1 hour ago
Charlie Parker
1,0381128
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
1
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I recently learned about complete strong induction. I am familiar with both strong induction and ordinary induction and make sense. But what particularly confuses me is why we do not to explicit the base cases for complete induction. They seem crucial for modus ponens to work and thus, actually show the stand alone proposition $p(n)$ to be true.
The claim for complete induction seems to be the following:
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
These are my thoughts:
In induction we actually do two things (to show $ P(n) $ for all $ n in mathbb N$) :
- show P(0)
- show implication $ P(n-1) implies P(n) $
or for strong induction
- show P(0)
- show implication $ forall m, m < n, P(m) implies P(n) $
However, in complete induction we only show:
- $ forall m, m < n, P(m) implies P(n) $
now that I’ve thought of it more carefully, what bothers me is that in the inductive step we actually only show an implication is true, not that $P(n)$ is true. Intuitively, $P(n)$ ends up true because of Modus Ponens (MP), which forcibly requires checking some set of base cases, say $P(0)$.
What concerns me is the following: ff we show $ forall m, m < n, P(m) implies P(n) $ then we shown the implication is true, and not necessarily anything else. If $n=0$ then $ forall m, m < n, P(m) implies P(n) $ is False. So sure, the implication is (vacuously) true, but that doesn’t necessarily say $P(0)$ is true stand alone (which is what induction ultimately cares about!).
My assumption is that the claim the wikipedia article does is that (somehow) whatever proof for $ forall m, m < n, P(m) implies P(n) $ that we have must also be a stand alone proof for $P(0)$. I guess I could abstractly believe that’s true (mostly on faith), but it seems rather odd to me. I’ve never seen False implies $P(n)$ implies $P(n)$. It’s nearly like the truth table for implication is built so that if you only know the antecedent is False, then you can’t decide if the consequent is true. Which makes sense. A false starting point should intuitively get you no where or get you everywhere (by principle of explosion).
So my question is, whats going on? Is it just that the proof for $ forall m, m < n, P(m) implies P(n) $ can also be plugged in for a proof for $P(0)$ and then $P(0)$ is true? Or am I missing something?
I have a feeling that this being so abstract makes it hard to be believable and a concrete example of how $ forall m, m < n, P(m) implies P(n) $ automagically makes $P(0)$ (the base cases) true would be really valuable.
Another useful source:
https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction
proof-verification logic induction proof-explanation
asked 1 hour ago
Charlie Parker
1,0381128
I recently learned about complete strong induction. I am familiar with both strong induction and ordinary induction and make sense. But what particularly confuses me is why we do not to explicit the base cases for complete induction. They seem crucial for modus ponens to work and thus, actually show the stand alone proposition $p(n)$ to be true.
The claim for complete induction seems to be the following:
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
These are my thoughts:
In induction we actually do two things (to show $ P(n) $ for all $ n in mathbb N$) :
- show P(0)
- show implication $ P(n-1) implies P(n) $
or for strong induction
- show P(0)
- show implication $ forall m, m < n, P(m) implies P(n) $
However, in complete induction we only show:
- $ forall m, m < n, P(m) implies P(n) $
now that I’ve thought of it more carefully, what bothers me is that in the inductive step we actually only show an implication is true, not that $P(n)$ is true. Intuitively, $P(n)$ ends up true because of Modus Ponens (MP), which forcibly requires checking some set of base cases, say $P(0)$.
What concerns me is the following: ff we show $ forall m, m < n, P(m) implies P(n) $ then we shown the implication is true, and not necessarily anything else. If $n=0$ then $ forall m, m < n, P(m) implies P(n) $ is False. So sure, the implication is (vacuously) true, but that doesn’t necessarily say $P(0)$ is true stand alone (which is what induction ultimately cares about!).
My assumption is that the claim the wikipedia article does is that (somehow) whatever proof for $ forall m, m < n, P(m) implies P(n) $ that we have must also be a stand alone proof for $P(0)$. I guess I could abstractly believe that’s true (mostly on faith), but it seems rather odd to me. I’ve never seen False implies $P(n)$ implies $P(n)$. It’s nearly like the truth table for implication is built so that if you only know the antecedent is False, then you can’t decide if the consequent is true. Which makes sense. A false starting point should intuitively get you no where or get you everywhere (by principle of explosion).
So my question is, whats going on? Is it just that the proof for $ forall m, m < n, P(m) implies P(n) $ can also be plugged in for a proof for $P(0)$ and then $P(0)$ is true? Or am I missing something?
I have a feeling that this being so abstract makes it hard to be believable and a concrete example of how $ forall m, m < n, P(m) implies P(n) $ automagically makes $P(0)$ (the base cases) true would be really valuable.
Another useful source:
https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction
proof-verification logic induction proof-explanation
proof-verification logic induction proof-explanation
asked 1 hour ago
Charlie Parker
1,0381128
asked 1 hour ago
Charlie Parker
1,0381128
edited 1 hour ago
asked 1 hour ago
Charlie Parker
1,0381128
asked 1 hour ago
Charlie Parker
1,0381128
asked 1 hour ago
Charlie Parker
1,0381128
1,0381128
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
1
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago
add a comment |Â
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
1
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
1
1
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
4
down vote
A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.
$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$
Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.
answered 1 hour ago
Bill Dubuque
203k29188612
add a comment |Â
up vote
2
down vote
You did not describe strong induction correctly; there's a quantifier missing. The second step should be:
$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$
So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:
- Since $P(0)$ holds, $P(1)$ holds, by $(1)$.
- Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.
- Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.
And so on…
answered 1 hour ago
José Carlos Santos
128k17102189
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
 |Â
show 5 more comments
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$
You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$
So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$
You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)
answered 20 mins ago
David K
49.9k340111
add a comment |Â
up vote
0
down vote
"But what particularly confuses me is why we do not to explicit the base cases for complete induction."
Short answer. You do explicitly prove the base cases. You misunderstood the description. You absolutely DO have to prove the base cases.
"I am familiar with both strong induction and ordinary induction"
Complete Strong induction is just another name for strong induction. These are two methods of induction. Not three. There is nothing new here that you do not already know.
Weak induction:
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$. Prove P(m+1).
(Complete) Strong induction
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$ and $P(k)$ for $0 le k le m$. Prove $P(m+1)$.
Notice that both say "assume" something. They do not mean "this is true and we don't need to prove it"; they both mean "we will assume for now; for actual cases we will prove the base case $m=0$ and once we prove this induction step will we use it repeatedly to get it true for any specific case"
==== looooong repetitvie answer below =====
(from https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction)
one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; (emphasis mine)
In other words you assume $P(0), P(1), P(2),...... P(m)$. Why do you assume them? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(0), P(1), P(2)...... P(m)$.
... and further....
by contrast, the basic form (weak induction) only assumes P(m). (empahsis mine)
THe assumption in both these description refer to a base case that must be done later.
In weak induction you assume $P(m)$. Why do you assume $P(m)$? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(m)$.
(frome https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction)
Of course you do (need to prove base cases).
Well, nothing I can really add to that.
Okay, it's confusingly written in both your sources but you are citing the description of the inductive step part of the proof only. BOTH strong and weak induction MUST have a base case and neither of your cites claim they don't.
Compare the descriptions of the weak and strong induction steps (via my paraphrasing).
Weak induction: Assuming $P(m)$ is true, we show that $P(m)implies P(m+1)$.
Well, how do we know $P(m)$ is true? Well, via the base case step. Assuming nothing we showed $P(0)$ was true. This doesn't say "We don't need to prove $P(0)$". Quite the opposite. It assumes we either have or will prove in our Base Case. But that was a different part of the proof. In describing the induction step we are assuming the base case has or will be done else where.
Complete Strong Induction: Assuming for all $0le k le m$ that $P(m)$
is true we show that $forall k le m: P(m)implies P(m+1)$.
Well, how do we know $forall k le m: P(m)$ is true? Well, .... cut and paste argument above....
The only difference in Complete Strong Induction (which is another term for "Strong Induction" which you claim to understand) is in the induction step assumption. The base case(s) step in both are exactly the same and absolutely essential. And NO-ONE is claiming they are not.
answered 44 mins ago
fleablood
63.1k22679
add a comment |Â
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:
$$P(m) text holds for any m<0 tag1$$
So, if you have shown that:
$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$
then in particular you have shown that:
$$text if P(m) text holds for any m<0, text then P(0) tag2'$$
and so we get
$$P(0)$$
by Modus Ponens on $(1)$ and $(2')$
So, there is indeed no need to prove an explicit base case.
That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!
In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.
answered 14 secs ago
Bram28
55.9k33983
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.
$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$
Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.
answered 1 hour ago
Bill Dubuque
203k29188612
add a comment |Â
up vote
4
down vote
A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.
$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$
Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.
answered 1 hour ago
Bill Dubuque
203k29188612
add a comment |Â
up vote
4
down vote
up vote
4
down vote
A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.
$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$
Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.
answered 1 hour ago
Bill Dubuque
203k29188612
A valid proof by complete induction includes a uniform proof for all $k$ of the inferences listed below. As such it include a (vacuous) proof of the base case $color#c00,P(0).,$ Examine the schema carefully to see it.
$qquadqquadqquad beginalign
Rightarrow,color#c00 P(0)\
P(0)Rightarrow, P(1)\
P(0),P(1)Rightarrow, P(2)\
vdotsqquad \
P(0),P(1),ldots,P(k-1),Rightarrow,P(k)\
endalign$
Remark $ $ Its contrapositive form (infinite descent) is clearer: if given a counterexample $lnot P(n)$ we can prove there exists a smaller counterexample $lnot P(k), k < n,,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $,Bbb N,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal one ("minimal criminal"), contra the proof yields a smaller one.
answered 1 hour ago
Bill Dubuque
203k29188612
edited 31 mins ago
answered 1 hour ago
Bill Dubuque
203k29188612
answered 1 hour ago
Bill Dubuque
203k29188612
answered 1 hour ago
Bill Dubuque
203k29188612
203k29188612
add a comment |Â
add a comment |Â
up vote
2
down vote
You did not describe strong induction correctly; there's a quantifier missing. The second step should be:
$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$
So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:
- Since $P(0)$ holds, $P(1)$ holds, by $(1)$.
- Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.
- Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.
And so on…
answered 1 hour ago
José Carlos Santos
128k17102189
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
 |Â
show 5 more comments
up vote
2
down vote
You did not describe strong induction correctly; there's a quantifier missing. The second step should be:
$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$
So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:
- Since $P(0)$ holds, $P(1)$ holds, by $(1)$.
- Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.
- Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.
And so on…
answered 1 hour ago
José Carlos Santos
128k17102189
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
 |Â
show 5 more comments
up vote
2
down vote
up vote
2
down vote
You did not describe strong induction correctly; there's a quantifier missing. The second step should be:
$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$
So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:
- Since $P(0)$ holds, $P(1)$ holds, by $(1)$.
- Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.
- Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.
And so on…
answered 1 hour ago
José Carlos Santos
128k17102189
You did not describe strong induction correctly; there's a quantifier missing. The second step should be:
$$bigl((forall min0,1,2,ldots,n-1):P(m)bigr)implies P(n).tag1$$
So, you prove that if $P(0)$, $P(1)$, …, $P(n-1)$, then $P(n)$ holds too. Why should this work? Suppose that you have proved $P(0)$ and also that $(1)$ holds. Then:
- Since $P(0)$ holds, $P(1)$ holds, by $(1)$.
- Since $P(0)$ and $P(1)$ hold, $P(2)$ holds, by $(1)$.
- Since $P(0)$, $P(1)$, and $P(2)$ hold, $P(3)$ holds, by $(1)$.
And so on…
answered 1 hour ago
José Carlos Santos
128k17102189
answered 1 hour ago
José Carlos Santos
128k17102189
answered 1 hour ago
José Carlos Santos
128k17102189
answered 1 hour ago
José Carlos Santos
128k17102189
128k17102189
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
 |Â
show 5 more comments
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
doesn't change anything about my confusion because I was always assuming $m<n$ meant $forall m, m<n$, since $n$ was a free variable. I've fixed it I guess.
– Charlie Parker
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
@CharlieParker And what about what I wrote after that, explaining why strong induction works?
– José Carlos Santos
1 hour ago
1
1
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
But we do need to show $P(0)$. You wrote that yourself. You wrote that the first step of strong induction is “show $P(0)â€Â.
– José Carlos Santos
1 hour ago
1
1
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
"the whole point is that complete strong induction does NOT need to show P(0)" Where in either of you sources was that stated?. "Thats my question. Why don't we need to show P(0)?" Who says you don't?
– fleablood
39 mins ago
 |Â
show 5 more comments
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$
You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$
So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$
You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)
answered 20 mins ago
David K
49.9k340111
add a comment |Â
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$
You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$
So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$
You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)
answered 20 mins ago
David K
49.9k340111
add a comment |Â
up vote
0
down vote
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$
You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$
So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$
You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)
answered 20 mins ago
David K
49.9k340111
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
It's not clear exactly how one ought to interpret "$P(m), m<n implies P(n)$",
but I think we have agreed that the following formula
(shown in the answer by José Carlos Santos)
represents the induction step according to the article:
$$((forall min0,1,2,ldots,n-1) P(m))implies P(n).$$
You seem to be looking at this and saying that for the case $n = 0,$
it is equivalent to $$bot implies P(n),$$
using $bot$ as a symbol for something that is always false.
This implication is vacuously true.
But in fact, a statement of the form
$$ (forall min emptyset) P(m) $$
is also vacuously true. That is, it is true because there is no value of $m$ that can make it false.
This may be a little more obvious if you write it this way:
$$ (forall m)(m in emptyset implies P(m)). $$
So what the induction step of complete induction actually says in the case $n = 0$ is that
$$topimplies P(0),$$
where $top$ is always true. If you prove that $topimplies P(0),$ you have proved $P(0).$
You might question whether the Wikipedia article does a good job of explaining itself, and I would sympathize. It's only an encyclopedia article, however;
a self-evident justification for everything may be too much too ask.
(Useful inline citations for details such as this are not too much to ask, however, and there is a notice at the top of that section of the article requesting them.)
answered 20 mins ago
David K
49.9k340111
answered 20 mins ago
David K
49.9k340111
answered 20 mins ago
David K
49.9k340111
answered 20 mins ago
David K
49.9k340111
49.9k340111
add a comment |Â
add a comment |Â
up vote
0
down vote
"But what particularly confuses me is why we do not to explicit the base cases for complete induction."
Short answer. You do explicitly prove the base cases. You misunderstood the description. You absolutely DO have to prove the base cases.
"I am familiar with both strong induction and ordinary induction"
Complete Strong induction is just another name for strong induction. These are two methods of induction. Not three. There is nothing new here that you do not already know.
Weak induction:
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$. Prove P(m+1).
(Complete) Strong induction
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$ and $P(k)$ for $0 le k le m$. Prove $P(m+1)$.
Notice that both say "assume" something. They do not mean "this is true and we don't need to prove it"; they both mean "we will assume for now; for actual cases we will prove the base case $m=0$ and once we prove this induction step will we use it repeatedly to get it true for any specific case"
==== looooong repetitvie answer below =====
(from https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction)
one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; (emphasis mine)
In other words you assume $P(0), P(1), P(2),...... P(m)$. Why do you assume them? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(0), P(1), P(2)...... P(m)$.
... and further....
by contrast, the basic form (weak induction) only assumes P(m). (empahsis mine)
THe assumption in both these description refer to a base case that must be done later.
In weak induction you assume $P(m)$. Why do you assume $P(m)$? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(m)$.
(frome https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction)
Of course you do (need to prove base cases).
Well, nothing I can really add to that.
Okay, it's confusingly written in both your sources but you are citing the description of the inductive step part of the proof only. BOTH strong and weak induction MUST have a base case and neither of your cites claim they don't.
Compare the descriptions of the weak and strong induction steps (via my paraphrasing).
Weak induction: Assuming $P(m)$ is true, we show that $P(m)implies P(m+1)$.
Well, how do we know $P(m)$ is true? Well, via the base case step. Assuming nothing we showed $P(0)$ was true. This doesn't say "We don't need to prove $P(0)$". Quite the opposite. It assumes we either have or will prove in our Base Case. But that was a different part of the proof. In describing the induction step we are assuming the base case has or will be done else where.
Complete Strong Induction: Assuming for all $0le k le m$ that $P(m)$
is true we show that $forall k le m: P(m)implies P(m+1)$.
Well, how do we know $forall k le m: P(m)$ is true? Well, .... cut and paste argument above....
The only difference in Complete Strong Induction (which is another term for "Strong Induction" which you claim to understand) is in the induction step assumption. The base case(s) step in both are exactly the same and absolutely essential. And NO-ONE is claiming they are not.
answered 44 mins ago
fleablood
63.1k22679
add a comment |Â
up vote
0
down vote
"But what particularly confuses me is why we do not to explicit the base cases for complete induction."
Short answer. You do explicitly prove the base cases. You misunderstood the description. You absolutely DO have to prove the base cases.
"I am familiar with both strong induction and ordinary induction"
Complete Strong induction is just another name for strong induction. These are two methods of induction. Not three. There is nothing new here that you do not already know.
Weak induction:
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$. Prove P(m+1).
(Complete) Strong induction
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$ and $P(k)$ for $0 le k le m$. Prove $P(m+1)$.
Notice that both say "assume" something. They do not mean "this is true and we don't need to prove it"; they both mean "we will assume for now; for actual cases we will prove the base case $m=0$ and once we prove this induction step will we use it repeatedly to get it true for any specific case"
==== looooong repetitvie answer below =====
(from https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction)
one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; (emphasis mine)
In other words you assume $P(0), P(1), P(2),...... P(m)$. Why do you assume them? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(0), P(1), P(2)...... P(m)$.
... and further....
by contrast, the basic form (weak induction) only assumes P(m). (empahsis mine)
THe assumption in both these description refer to a base case that must be done later.
In weak induction you assume $P(m)$. Why do you assume $P(m)$? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(m)$.
(frome https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction)
Of course you do (need to prove base cases).
Well, nothing I can really add to that.
Okay, it's confusingly written in both your sources but you are citing the description of the inductive step part of the proof only. BOTH strong and weak induction MUST have a base case and neither of your cites claim they don't.
Compare the descriptions of the weak and strong induction steps (via my paraphrasing).
Weak induction: Assuming $P(m)$ is true, we show that $P(m)implies P(m+1)$.
Well, how do we know $P(m)$ is true? Well, via the base case step. Assuming nothing we showed $P(0)$ was true. This doesn't say "We don't need to prove $P(0)$". Quite the opposite. It assumes we either have or will prove in our Base Case. But that was a different part of the proof. In describing the induction step we are assuming the base case has or will be done else where.
Complete Strong Induction: Assuming for all $0le k le m$ that $P(m)$
is true we show that $forall k le m: P(m)implies P(m+1)$.
Well, how do we know $forall k le m: P(m)$ is true? Well, .... cut and paste argument above....
The only difference in Complete Strong Induction (which is another term for "Strong Induction" which you claim to understand) is in the induction step assumption. The base case(s) step in both are exactly the same and absolutely essential. And NO-ONE is claiming they are not.
answered 44 mins ago
fleablood
63.1k22679
add a comment |Â
up vote
0
down vote
up vote
0
down vote
"But what particularly confuses me is why we do not to explicit the base cases for complete induction."
Short answer. You do explicitly prove the base cases. You misunderstood the description. You absolutely DO have to prove the base cases.
"I am familiar with both strong induction and ordinary induction"
Complete Strong induction is just another name for strong induction. These are two methods of induction. Not three. There is nothing new here that you do not already know.
Weak induction:
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$. Prove P(m+1).
(Complete) Strong induction
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$ and $P(k)$ for $0 le k le m$. Prove $P(m+1)$.
Notice that both say "assume" something. They do not mean "this is true and we don't need to prove it"; they both mean "we will assume for now; for actual cases we will prove the base case $m=0$ and once we prove this induction step will we use it repeatedly to get it true for any specific case"
==== looooong repetitvie answer below =====
(from https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction)
one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; (emphasis mine)
In other words you assume $P(0), P(1), P(2),...... P(m)$. Why do you assume them? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(0), P(1), P(2)...... P(m)$.
... and further....
by contrast, the basic form (weak induction) only assumes P(m). (empahsis mine)
THe assumption in both these description refer to a base case that must be done later.
In weak induction you assume $P(m)$. Why do you assume $P(m)$? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(m)$.
(frome https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction)
Of course you do (need to prove base cases).
Well, nothing I can really add to that.
Okay, it's confusingly written in both your sources but you are citing the description of the inductive step part of the proof only. BOTH strong and weak induction MUST have a base case and neither of your cites claim they don't.
Compare the descriptions of the weak and strong induction steps (via my paraphrasing).
Weak induction: Assuming $P(m)$ is true, we show that $P(m)implies P(m+1)$.
Well, how do we know $P(m)$ is true? Well, via the base case step. Assuming nothing we showed $P(0)$ was true. This doesn't say "We don't need to prove $P(0)$". Quite the opposite. It assumes we either have or will prove in our Base Case. But that was a different part of the proof. In describing the induction step we are assuming the base case has or will be done else where.
Complete Strong Induction: Assuming for all $0le k le m$ that $P(m)$
is true we show that $forall k le m: P(m)implies P(m+1)$.
Well, how do we know $forall k le m: P(m)$ is true? Well, .... cut and paste argument above....
The only difference in Complete Strong Induction (which is another term for "Strong Induction" which you claim to understand) is in the induction step assumption. The base case(s) step in both are exactly the same and absolutely essential. And NO-ONE is claiming they are not.
answered 44 mins ago
fleablood
63.1k22679
"But what particularly confuses me is why we do not to explicit the base cases for complete induction."
Short answer. You do explicitly prove the base cases. You misunderstood the description. You absolutely DO have to prove the base cases.
"I am familiar with both strong induction and ordinary induction"
Complete Strong induction is just another name for strong induction. These are two methods of induction. Not three. There is nothing new here that you do not already know.
Weak induction:
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$. Prove P(m+1).
(Complete) Strong induction
1) Base step: Prove $P(0)$.
2) Induction step: Assume $P(m)$ and $P(k)$ for $0 le k le m$. Prove $P(m+1)$.
Notice that both say "assume" something. They do not mean "this is true and we don't need to prove it"; they both mean "we will assume for now; for actual cases we will prove the base case $m=0$ and once we prove this induction step will we use it repeatedly to get it true for any specific case"
==== looooong repetitvie answer below =====
(from https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction)
one proves the statement P(m + 1) under the assumption that P(n) holds for all natural n less than m + 1; (emphasis mine)
In other words you assume $P(0), P(1), P(2),...... P(m)$. Why do you assume them? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(0), P(1), P(2)...... P(m)$.
... and further....
by contrast, the basic form (weak induction) only assumes P(m). (empahsis mine)
THe assumption in both these description refer to a base case that must be done later.
In weak induction you assume $P(m)$. Why do you assume $P(m)$? Because you did a base case with $m =0$. And once you prove this step you will repeat it to get up $m$ and thus you will know $P(m)$.
(frome https://www.quora.com/Why-dont-you-need-to-prove-base-cases-for-complete-strong-induction)
Of course you do (need to prove base cases).
Well, nothing I can really add to that.
Okay, it's confusingly written in both your sources but you are citing the description of the inductive step part of the proof only. BOTH strong and weak induction MUST have a base case and neither of your cites claim they don't.
Compare the descriptions of the weak and strong induction steps (via my paraphrasing).
Weak induction: Assuming $P(m)$ is true, we show that $P(m)implies P(m+1)$.
Well, how do we know $P(m)$ is true? Well, via the base case step. Assuming nothing we showed $P(0)$ was true. This doesn't say "We don't need to prove $P(0)$". Quite the opposite. It assumes we either have or will prove in our Base Case. But that was a different part of the proof. In describing the induction step we are assuming the base case has or will be done else where.
Complete Strong Induction: Assuming for all $0le k le m$ that $P(m)$
is true we show that $forall k le m: P(m)implies P(m+1)$.
Well, how do we know $forall k le m: P(m)$ is true? Well, .... cut and paste argument above....
The only difference in Complete Strong Induction (which is another term for "Strong Induction" which you claim to understand) is in the induction step assumption. The base case(s) step in both are exactly the same and absolutely essential. And NO-ONE is claiming they are not.
answered 44 mins ago
fleablood
63.1k22679
edited 5 mins ago
answered 44 mins ago
fleablood
63.1k22679
answered 44 mins ago
fleablood
63.1k22679
answered 44 mins ago
fleablood
63.1k22679
63.1k22679
add a comment |Â
add a comment |Â
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:
$$P(m) text holds for any m<0 tag1$$
So, if you have shown that:
$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$
then in particular you have shown that:
$$text if P(m) text holds for any m<0, text then P(0) tag2'$$
and so we get
$$P(0)$$
by Modus Ponens on $(1)$ and $(2')$
So, there is indeed no need to prove an explicit base case.
That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!
In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.
answered 14 secs ago
Bram28
55.9k33983
add a comment |Â
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:
$$P(m) text holds for any m<0 tag1$$
So, if you have shown that:
$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$
then in particular you have shown that:
$$text if P(m) text holds for any m<0, text then P(0) tag2'$$
and so we get
$$P(0)$$
by Modus Ponens on $(1)$ and $(2')$
So, there is indeed no need to prove an explicit base case.
That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!
In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.
answered 14 secs ago
Bram28
55.9k33983
add a comment |Â
up vote
0
down vote
up vote
0
down vote
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:
$$P(m) text holds for any m<0 tag1$$
So, if you have shown that:
$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$
then in particular you have shown that:
$$text if P(m) text holds for any m<0, text then P(0) tag2'$$
and so we get
$$P(0)$$
by Modus Ponens on $(1)$ and $(2')$
So, there is indeed no need to prove an explicit base case.
That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!
In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.
answered 14 secs ago
Bram28
55.9k33983
if we show $ P(m), m<n implies P(n) $ then somehow that must mean that $P(0)$ is true (or $P(b)$ is true for some set of base cases $b in BaseCases$)
Right, that's exactly correct: if there is nothing smaller than $0$ (as is the case for the natural numbers) then it is vacuously true that:
$$P(m) text holds for any m<0 tag1$$
So, if you have shown that:
$$textfor any n: text if P(m) text holds for any m<n, text then P(n) tag2$$
then in particular you have shown that:
$$text if P(m) text holds for any m<0, text then P(0) tag2'$$
and so we get
$$P(0)$$
by Modus Ponens on $(1)$ and $(2')$
So, there is indeed no need to prove an explicit base case.
That said, think about how in practice you would actually prove $(2)$. Probably, you would be able to show $P(n)$ based on the assumption that there actually are $m<n$ for which we can show that if they all have property $P(m)$, then $P(n)$. But for the edge case of $n=0$, there are no such $m<n$ ... so ... you need to show $P(0)$ by itself!
In other words, in practice, you often do have to treat the base cases as special cases that you prove as base cases after all.
answered 14 secs ago
Bram28
55.9k33983
answered 14 secs ago
Bram28
55.9k33983
answered 14 secs ago
Bram28
55.9k33983
answered 14 secs ago
Bram28
55.9k33983
55.9k33983
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2948715%2fwhy-is-complete-strong-induction-a-valid-proof-method%23new-answer', 'question_page');
);
Post as a guest
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
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
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
" I am familiar with both strong induction and ordinary induction" Complete strong induction is strong induction.
– fleablood
1 hour ago
@fleablood yea, of course because of $P(m), m<n$, but I'd never seen before that the base cases were "automatically true" given a correct inductive step. As far as I've seen it must be show they are true, because of the Modus Ponens (MP) argument I sketched in my question.
– Charlie Parker
1 hour ago
1
Your statement "If n=0 then $P(m),m<nimplies P(n)$ is false" is incorrect (when interpreted properly); in fact, $P(m),m<0implies P(0)$ vacuously true (since there can't be a counterexample).
– Noah Schweber
1 hour ago
the whole point is that complete strong induction does NOT need to show $P(0)$. Thats my question. Why don't we need to show $P(0)$? I understand modus ponens (MP). If we have P(0) then we can get the next proposition if we have $ P(0) implies P(1) $ shown true (by the inductive step). My question is if we have the inductive step, why do we have the base case automatically?
– Charlie Parker
1 hour ago
Can you give us an example of a "complete strong induction proof" that you've seen? Because your doubts seem (given your description of CSE) to be wholly justified, which makes me think that perhaps your understanding of CSE ("the whole point is that...") might be flawed.
– John Hughes
1 hour ago