Induction without a base case [duplicate]
$begingroup$
This question already has an answer here:
What is the purpose of the first test in an inductive proof?
9 answers
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
induction
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
$endgroup$
marked as duplicate by Ilmari Karonen, hardmath, user63181, TMM, Nick Peterson Jan 5 '14 at 17:39
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
show 1 more comment
$begingroup$
This question already has an answer here:
What is the purpose of the first test in an inductive proof?
9 answers
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
induction
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
$endgroup$
marked as duplicate by Ilmari Karonen, hardmath, user63181, TMM, Nick Peterson Jan 5 '14 at 17:39
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
1
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
4
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
3
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43
|
show 1 more comment
$begingroup$
This question already has an answer here:
What is the purpose of the first test in an inductive proof?
9 answers
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
induction
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
$endgroup$
This question already has an answer here:
What is the purpose of the first test in an inductive proof?
9 answers
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
This question already has an answer here:
What is the purpose of the first test in an inductive proof?
9 answers
induction
induction
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
edited Apr 12 '14 at 22:17
user111584
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
asked Jan 5 '14 at 13:29
PranksterPrankster
318314
318314
marked as duplicate by Ilmari Karonen, hardmath, user63181, TMM, Nick Peterson Jan 5 '14 at 17:39
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Ilmari Karonen, hardmath, user63181, TMM, Nick Peterson Jan 5 '14 at 17:39
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
1
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
4
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
3
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43
|
show 1 more comment
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
1
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
4
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
3
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
1
1
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
4
4
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
3
3
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43
|
show 1 more comment
8 Answers
8
active
oldest
votes
$begingroup$
Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $kin mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
$endgroup$
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
add a comment |
$begingroup$
$$1+2+3+dots+n=frac{n(n+1)}2+pi$$
$$1+2+4+dots+2^{n-1}=2^n$$
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
(False) Theorem. Let $P$ be literally any property of elements of $mathbb N$. Then every element of $mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $mathbb N$ consist of elements with property $P$. Suppose $nge 1$ and all elements of subsets of $mathbb N$ with $n$ elements satisfy $P$. Let $Ssubsetmathbb N$ have $n+1$ elements, and pick any $xin S$. Since $S'=Ssetminus{x}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $yin S'$. Then $(S'setminus{y})cup{x}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.
edited Sep 28 '15 at 3:59
Andreas
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
$endgroup$
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
add a comment |
$begingroup$
Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.
Then what?
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be a false statement, for each $n$. Then $P(k) implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
$endgroup$
add a comment |
$begingroup$
Suppose we want to show $n=n+1$ where $nin mathbb{N}$. Now suppose the statement holds for some $n$
$$n=n+1$$
then we want to show $$n+1=n+1+1$$
which is easily true since $(n+1)+1=n+1$.Suppose we want to show for all $nin mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$
$$n+1<n$$
then $$n+1+1=(n+1)+1<n+1$$
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be the statement "$2^{aleph_0}=n+aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
$endgroup$
add a comment |
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $kin mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
$endgroup$
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
add a comment |
$begingroup$
Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $kin mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
$endgroup$
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
add a comment |
$begingroup$
Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $kin mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
$endgroup$
Suppose we want to prove $n=n+1$ for all (positive) integers $n$. We omit the base case. The induction hypothesis is $k=k+1$ for some $kin mathbb N$. Adding $1$ to both sides gives $k+1=k+1+1$, or $(k+1)=(k+1)+1$, which is the statement to be proven for $n=k+1$. Thus, we have completed the induction step, but there is no base for which this is true, so the statement won't have to be true too.
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
edited Oct 5 '14 at 16:31
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
answered Jan 5 '14 at 13:33
RagnarRagnar
5,9821120
5,9821120
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
add a comment |
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
1
1
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
$begingroup$
Just realise, if $P(k)$ is true, i.e. $k=k+1$, then $P(k+1)=P(k)=$true. Even induction itself get messed up...
$endgroup$
– peterwhy
Jan 5 '14 at 20:15
add a comment |
$begingroup$
$$1+2+3+dots+n=frac{n(n+1)}2+pi$$
$$1+2+4+dots+2^{n-1}=2^n$$
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
$$1+2+3+dots+n=frac{n(n+1)}2+pi$$
$$1+2+4+dots+2^{n-1}=2^n$$
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
$$1+2+3+dots+n=frac{n(n+1)}2+pi$$
$$1+2+4+dots+2^{n-1}=2^n$$
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
$endgroup$
$$1+2+3+dots+n=frac{n(n+1)}2+pi$$
$$1+2+4+dots+2^{n-1}=2^n$$
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
edited Jan 6 '14 at 0:15
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
answered Jan 5 '14 at 13:39
bofbof
52.3k558121
52.3k558121
add a comment |
add a comment |
$begingroup$
(False) Theorem. Let $P$ be literally any property of elements of $mathbb N$. Then every element of $mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $mathbb N$ consist of elements with property $P$. Suppose $nge 1$ and all elements of subsets of $mathbb N$ with $n$ elements satisfy $P$. Let $Ssubsetmathbb N$ have $n+1$ elements, and pick any $xin S$. Since $S'=Ssetminus{x}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $yin S'$. Then $(S'setminus{y})cup{x}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.
edited Sep 28 '15 at 3:59
Andreas
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
$endgroup$
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
add a comment |
$begingroup$
(False) Theorem. Let $P$ be literally any property of elements of $mathbb N$. Then every element of $mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $mathbb N$ consist of elements with property $P$. Suppose $nge 1$ and all elements of subsets of $mathbb N$ with $n$ elements satisfy $P$. Let $Ssubsetmathbb N$ have $n+1$ elements, and pick any $xin S$. Since $S'=Ssetminus{x}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $yin S'$. Then $(S'setminus{y})cup{x}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.
edited Sep 28 '15 at 3:59
Andreas
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
$endgroup$
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
add a comment |
$begingroup$
(False) Theorem. Let $P$ be literally any property of elements of $mathbb N$. Then every element of $mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $mathbb N$ consist of elements with property $P$. Suppose $nge 1$ and all elements of subsets of $mathbb N$ with $n$ elements satisfy $P$. Let $Ssubsetmathbb N$ have $n+1$ elements, and pick any $xin S$. Since $S'=Ssetminus{x}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $yin S'$. Then $(S'setminus{y})cup{x}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.
edited Sep 28 '15 at 3:59
Andreas
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
$endgroup$
(False) Theorem. Let $P$ be literally any property of elements of $mathbb N$. Then every element of $mathbb N$ has property $P$.
Proof. This is true if all nonempty finite subsets of $mathbb N$ consist of elements with property $P$. Suppose $nge 1$ and all elements of subsets of $mathbb N$ with $n$ elements satisfy $P$. Let $Ssubsetmathbb N$ have $n+1$ elements, and pick any $xin S$. Since $S'=Ssetminus{x}$ has $n$ elements, all members of $S'$ satisfy $P$. Moreover, since $n=|S'|>0$ there exists $yin S'$. Then $(S'setminus{y})cup{x}$ has $n$ elements, so $x$ has property $P$ as well. q.e.d.
edited Sep 28 '15 at 3:59
Andreas
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
edited Sep 28 '15 at 3:59
Andreas
1034
edited Sep 28 '15 at 3:59
Andreas
1034
edited Sep 28 '15 at 3:59
Andreas
1034
1034
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
answered Jan 5 '14 at 13:57
Karl KronenfeldKarl Kronenfeld
4,39511425
4,39511425
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
add a comment |
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
$begingroup$
This should not be labelled as a theorem.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 14:32
2
2
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
@AlešBizjak Did you, for a second, think it is true? My point being, the only reason why I shouldn't call it a theorem is that it would potentially mislead readers.
$endgroup$
– Karl Kronenfeld
Jan 5 '14 at 15:44
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
$begingroup$
No, I didn't think it was true and that is my point. Statements that are not true should not be called "Theorem" in a serious answer, especially since the question is about statements which are not true.
$endgroup$
– Aleš Bizjak
Jan 5 '14 at 16:07
add a comment |
$begingroup$
Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.
Then what?
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.
Then what?
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.
Then what?
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
$endgroup$
Let $P(n)$ be the statement "$1=2$". Assume $P(k)$ is true, hence $1=2$. By assumption, $1=2$, so $P(k+1)$ is true.
Then what?
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
answered Jan 5 '14 at 14:19
peterwhypeterwhy
12k21229
12k21229
add a comment |
add a comment |
$begingroup$
Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.
$endgroup$
add a comment |
$begingroup$
Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.
$endgroup$
add a comment |
$begingroup$
Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.
$endgroup$
Simply let $P(n)$ be the statement that $n=n+1$. Suppose this is true for some positive integer $k$. Then $k=k+1$, so $k+1=k+1+1$, and we also have $P(k+1)$.
answered Jan 5 '14 at 13:35
user111584
add a comment |
add a comment |
$begingroup$
Let $P(n)$ be a false statement, for each $n$. Then $P(k) implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be a false statement, for each $n$. Then $P(k) implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be a false statement, for each $n$. Then $P(k) implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
$endgroup$
Let $P(n)$ be a false statement, for each $n$. Then $P(k) implies P(k+1)$ vacuously, because a false statement implies any other, but certainly $P(0)$ is false.
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
answered Jan 5 '14 at 15:48
Ben MillwoodBen Millwood
11.3k32049
11.3k32049
add a comment |
add a comment |
$begingroup$
Suppose we want to show $n=n+1$ where $nin mathbb{N}$. Now suppose the statement holds for some $n$
$$n=n+1$$
then we want to show $$n+1=n+1+1$$
which is easily true since $(n+1)+1=n+1$.Suppose we want to show for all $nin mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$
$$n+1<n$$
then $$n+1+1=(n+1)+1<n+1$$
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
$endgroup$
add a comment |
$begingroup$
Suppose we want to show $n=n+1$ where $nin mathbb{N}$. Now suppose the statement holds for some $n$
$$n=n+1$$
then we want to show $$n+1=n+1+1$$
which is easily true since $(n+1)+1=n+1$.Suppose we want to show for all $nin mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$
$$n+1<n$$
then $$n+1+1=(n+1)+1<n+1$$
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
$endgroup$
add a comment |
$begingroup$
Suppose we want to show $n=n+1$ where $nin mathbb{N}$. Now suppose the statement holds for some $n$
$$n=n+1$$
then we want to show $$n+1=n+1+1$$
which is easily true since $(n+1)+1=n+1$.Suppose we want to show for all $nin mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$
$$n+1<n$$
then $$n+1+1=(n+1)+1<n+1$$
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
$endgroup$
Suppose we want to show $n=n+1$ where $nin mathbb{N}$. Now suppose the statement holds for some $n$
$$n=n+1$$
then we want to show $$n+1=n+1+1$$
which is easily true since $(n+1)+1=n+1$.Suppose we want to show for all $nin mathbb{N}^+$, $n+1<n$. Now suppose the statement holds for some $n$
$$n+1<n$$
then $$n+1+1=(n+1)+1<n+1$$
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
answered Jan 5 '14 at 13:41
KuaiKuai
1,130610
1,130610
add a comment |
add a comment |
$begingroup$
Let $P(n)$ be the statement "$2^{aleph_0}=n+aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be the statement "$2^{aleph_0}=n+aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
$endgroup$
add a comment |
$begingroup$
Let $P(n)$ be the statement "$2^{aleph_0}=n+aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
$endgroup$
Let $P(n)$ be the statement "$2^{aleph_0}=n+aleph_1$"(Continuum Hypothesis). The inductive step itself works but it gives nothing. We are not able to check (in the theory $ZFC$) the statement $P(0)$ is false or true.
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
answered Jan 5 '14 at 17:27
GeorgeGeorge
1,238713
1,238713
add a comment |
add a comment |
$begingroup$
It would be better if you included the problem to be inducted on.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
$begingroup$
Also, try looking at backward induction.
$endgroup$
– Torsten Hĕrculĕ Cärlemän
Jan 5 '14 at 13:32
1
$begingroup$
Any statement which is false for all integers works.
$endgroup$
– DanielV
Jan 5 '14 at 14:26
4
$begingroup$
All horses are the same colour.
$endgroup$
– Katriel
Jan 5 '14 at 16:42
3
$begingroup$
@katrielalex: That comes to mind, but is not an example. The base case (one horse) works, but the first instance of the induction step fails.
$endgroup$
– Marc van Leeuwen
Jan 5 '14 at 17:43