Mixing
Questions on “All Horse are the Same Color†Proof by Complete Induction
Clash Royale CLAN TAG#URR8PPP
up vote
26
down vote
favorite
I'm bugged by the following that's summarized on p. 109 of this PDF.
False theorem: All horses are the same color.
Proof by induction:
$fbox$P(n)$ is the statement: In every set of horses of size $n$, all $n$ horses are the same color.$
$fboxBase Case or $P(1)$:$ One horse is the same color as itself. This is true by inspection.
$fboxInduction Step:$ Assume $P(k)$ for some $k geq 1$.
$fboxProof of $P(k + 1) :$$
Since $H_1, H_2, ... , H_n$ is a set of $n$ horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
Since $H_2, H_3, ... , H_n+1$ is also a set of $n$ horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.
Therefore, all $n +1$ horses in $H_1, H_2, H_3, ... , H_n , H_n+1$ are the same color. QED.
The issue the instructor was trying to point out is clearly valid. For the case $n = 1$, there is only $H_1$. So this case says nothing about possible overlapping elements of each set of $(n + 1)$, for instance $H_2$ in the above proof.
But it was proposed in the class discussion that this was the only problem. Had you been able to prove $P(2)$ true, then a proof of the above format would have been fine.
My interpretation is that yes, you could prove all horses are the same color, if you can prove that any set of two horses will be the same color. But this format would not work.
Why not? The problem I see is that the above proof is for the existence of at least one particular pair of sets of horses of sizes $n$ and $n + 1$, such that in each set, all horses are the same color. Particularly when the set of size $n$ is a subset of the set of size $n + 1$. In order to prove the induction step, don't you need to prove that sets of sizes $n$ and $n + 1$, do not necessarily contain the same, overlapping elements?
You could prove that any horse can be added to a set of 2 horses. Take the last two, and they must be the same color, and so on. Wwhatever color the first two happen to be, all other horses must thus be the same color.
Am I misinterpreting the example, or am I making a logical error? Thanks in advance.
discrete-mathematics induction fake-proofs
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
asked Jun 24 '13 at 8:53
MVTC
2671310
add a comment |Â
up vote
26
down vote
favorite
I'm bugged by the following that's summarized on p. 109 of this PDF.
False theorem: All horses are the same color.
Proof by induction:
$fbox$P(n)$ is the statement: In every set of horses of size $n$, all $n$ horses are the same color.$
$fboxBase Case or $P(1)$:$ One horse is the same color as itself. This is true by inspection.
$fboxInduction Step:$ Assume $P(k)$ for some $k geq 1$.
$fboxProof of $P(k + 1) :$$
Since $H_1, H_2, ... , H_n$ is a set of $n$ horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
Since $H_2, H_3, ... , H_n+1$ is also a set of $n$ horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.
Therefore, all $n +1$ horses in $H_1, H_2, H_3, ... , H_n , H_n+1$ are the same color. QED.
The issue the instructor was trying to point out is clearly valid. For the case $n = 1$, there is only $H_1$. So this case says nothing about possible overlapping elements of each set of $(n + 1)$, for instance $H_2$ in the above proof.
But it was proposed in the class discussion that this was the only problem. Had you been able to prove $P(2)$ true, then a proof of the above format would have been fine.
My interpretation is that yes, you could prove all horses are the same color, if you can prove that any set of two horses will be the same color. But this format would not work.
Why not? The problem I see is that the above proof is for the existence of at least one particular pair of sets of horses of sizes $n$ and $n + 1$, such that in each set, all horses are the same color. Particularly when the set of size $n$ is a subset of the set of size $n + 1$. In order to prove the induction step, don't you need to prove that sets of sizes $n$ and $n + 1$, do not necessarily contain the same, overlapping elements?
You could prove that any horse can be added to a set of 2 horses. Take the last two, and they must be the same color, and so on. Wwhatever color the first two happen to be, all other horses must thus be the same color.
Am I misinterpreting the example, or am I making a logical error? Thanks in advance.
discrete-mathematics induction fake-proofs
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
asked Jun 24 '13 at 8:53
MVTC
2671310
2
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00
add a comment |Â
up vote
26
down vote
favorite
up vote
26
down vote
favorite
I'm bugged by the following that's summarized on p. 109 of this PDF.
False theorem: All horses are the same color.
Proof by induction:
$fbox$P(n)$ is the statement: In every set of horses of size $n$, all $n$ horses are the same color.$
$fboxBase Case or $P(1)$:$ One horse is the same color as itself. This is true by inspection.
$fboxInduction Step:$ Assume $P(k)$ for some $k geq 1$.
$fboxProof of $P(k + 1) :$$
Since $H_1, H_2, ... , H_n$ is a set of $n$ horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
Since $H_2, H_3, ... , H_n+1$ is also a set of $n$ horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.
Therefore, all $n +1$ horses in $H_1, H_2, H_3, ... , H_n , H_n+1$ are the same color. QED.
The issue the instructor was trying to point out is clearly valid. For the case $n = 1$, there is only $H_1$. So this case says nothing about possible overlapping elements of each set of $(n + 1)$, for instance $H_2$ in the above proof.
But it was proposed in the class discussion that this was the only problem. Had you been able to prove $P(2)$ true, then a proof of the above format would have been fine.
My interpretation is that yes, you could prove all horses are the same color, if you can prove that any set of two horses will be the same color. But this format would not work.
Why not? The problem I see is that the above proof is for the existence of at least one particular pair of sets of horses of sizes $n$ and $n + 1$, such that in each set, all horses are the same color. Particularly when the set of size $n$ is a subset of the set of size $n + 1$. In order to prove the induction step, don't you need to prove that sets of sizes $n$ and $n + 1$, do not necessarily contain the same, overlapping elements?
You could prove that any horse can be added to a set of 2 horses. Take the last two, and they must be the same color, and so on. Wwhatever color the first two happen to be, all other horses must thus be the same color.
Am I misinterpreting the example, or am I making a logical error? Thanks in advance.
discrete-mathematics induction fake-proofs
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
asked Jun 24 '13 at 8:53
MVTC
2671310
I'm bugged by the following that's summarized on p. 109 of this PDF.
False theorem: All horses are the same color.
Proof by induction:
$fbox$P(n)$ is the statement: In every set of horses of size $n$, all $n$ horses are the same color.$
$fboxBase Case or $P(1)$:$ One horse is the same color as itself. This is true by inspection.
$fboxInduction Step:$ Assume $P(k)$ for some $k geq 1$.
$fboxProof of $P(k + 1) :$$
Since $H_1, H_2, ... , H_n$ is a set of $n$ horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
Since $H_2, H_3, ... , H_n+1$ is also a set of $n$ horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.
Therefore, all $n +1$ horses in $H_1, H_2, H_3, ... , H_n , H_n+1$ are the same color. QED.
The issue the instructor was trying to point out is clearly valid. For the case $n = 1$, there is only $H_1$. So this case says nothing about possible overlapping elements of each set of $(n + 1)$, for instance $H_2$ in the above proof.
But it was proposed in the class discussion that this was the only problem. Had you been able to prove $P(2)$ true, then a proof of the above format would have been fine.
My interpretation is that yes, you could prove all horses are the same color, if you can prove that any set of two horses will be the same color. But this format would not work.
Why not? The problem I see is that the above proof is for the existence of at least one particular pair of sets of horses of sizes $n$ and $n + 1$, such that in each set, all horses are the same color. Particularly when the set of size $n$ is a subset of the set of size $n + 1$. In order to prove the induction step, don't you need to prove that sets of sizes $n$ and $n + 1$, do not necessarily contain the same, overlapping elements?
You could prove that any horse can be added to a set of 2 horses. Take the last two, and they must be the same color, and so on. Wwhatever color the first two happen to be, all other horses must thus be the same color.
Am I misinterpreting the example, or am I making a logical error? Thanks in advance.
discrete-mathematics induction fake-proofs
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
asked Jun 24 '13 at 8:53
MVTC
2671310
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
edited Dec 25 '17 at 2:07
Greek - Area 51 Proposal
2,98346697
2,98346697
asked Jun 24 '13 at 8:53
MVTC
2671310
asked Jun 24 '13 at 8:53
MVTC
2671310
asked Jun 24 '13 at 8:53
MVTC
2671310
2671310
2
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00
add a comment |Â
2
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00
2
2
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00
add a comment |Â
6 Answers
6
active
oldest
votes
up vote
50
down vote
accepted
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.
We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=h_1,h_2,dots,h_n+1$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets
$$H_0=h_1,dots,h_nquadtextandquad H_1=h_2,dots,h_n+1;.$$
Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color.
Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.
Now if $nge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_n+1$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.
There is absolutely nothing wrong with that argument — provided that $nge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.
The argument fails only when $n=1$. In that case it fails because the sets $H_0=h_1$ and $H_1=h_2$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $nge 2$, so the sets $H_0$ and $H_1$ would overlap.
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
add a comment |Â
up vote
10
down vote
I'm not sure I understand fully your doubt, but the actual problem with that, and many other examples of bogus inductive proofs out there, is that when you take the two sets
$$h_1,...,h_n;,;;h_2,...,h_n,h_n+1$$
each of size $,n,$ and thus, by the Ind. Hypothesis, formed of horses of the same color, the leap to deduce all the horses altogether have the same color requires that the intersection of both sets above is not empty, something you can't prove (because it is false!) if $,n=2,$
Thus, if we had the claim "every two horse whatsoever are of the same color", then we could prove "all the horses are of the same color"
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
 |Â
show 15 more comments
up vote
0
down vote
There is a more basic problem here : induction is irrelevant to the proof.
$P(2)$ is, by itself, a formalization of the statement that all horses are the same color. There is no reason to prove $P(2)$ to prove $P(3)$ to prove ... $P(n)$ and conclude from this chain of implications that all horses are the same color; one would try to prove $P(2)$ and in case of success, summarize that as "all horses have the same color".
If proving $P(n)$ were of interest for some reason, it can be derived in one step from $P(2)$, with no need for an induction.
The size of the set of horses is usually ignored in presentations of this argument and ones like it. But if there are $n$ horses in the universe, $P(k)$ is an empty statement for $k>n$, and is true regardless of the truth value $P(n)$. This shows that $P(n)$ is logically stronger than $P(n+1)$, and that the inductive step from $P(n) $ to $P(n+1)$ is vacuous for large $n$.
answered Jun 25 '13 at 5:21
zyx
31k33697
add a comment |Â
up vote
0
down vote
As you pointed out, $P(1)$ is trivially true. And you are trying to prove $$P(n)implies P(n+1)$$ to finish the proof. But It's clear that $P(1)$ does NOT implies $P(2)$. Thus the statement $$P(n)implies P(n+1)$$ is not true. And this is where your proof falls.
answered Jul 31 at 5:49
Le Anh Dung
740317
add a comment |Â
up vote
-1
down vote
I just had a student come to me with this problem. I am not a mathematician by trade, so this was the first I'd heard of it. (It's a very good problem that forces the student to understand the method!)
My natural inclination was to negate that which was supposedly proven ("all horses are the same color"), and take the "contrapositive" of the entire inductive chain, and see if we do necessarily contradict the base case. (In other words, the inductive argument supposedly gives $P(1) Rightarrow P(2) Rightarrow cdotsRightarrow P$; I wanted to see if $neg P Rightarrow cdots Rightarrow neg P(2) Rightarrow neg P(1) $.)
So, right off the bat, the negation of "all horses are the same color" is "there exists horse A and horse B such that A is a different color than B". From that, you immediately see that $P(1)$ is unsuitable base case because $neg P(2)$ means "in a set of 2 horses, the two hoses are different colors". That does not contradict anything about $P(1)$ (which of course is logically unimpeachable).
What also comes out in the above line of reasoning confirms what @zyx said: induction is irrelevant to the statement being proven. At every step, the condition that the statement be false hinges on the existence of two different horses having different colors. So, if you had somehow shown $P(2)$ to be true, game over.
answered Jul 1 '16 at 22:03
user3337629
592
add a comment |Â
up vote
-2
down vote
Just want to add a quick summary.
The proof is "almost" perfect. It simply fails on n=1.
Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.
If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.
answered Aug 15 '16 at 9:49
J. Chang
7701614
add a comment |Â
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
50
down vote
accepted
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.
We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=h_1,h_2,dots,h_n+1$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets
$$H_0=h_1,dots,h_nquadtextandquad H_1=h_2,dots,h_n+1;.$$
Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color.
Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.
Now if $nge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_n+1$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.
There is absolutely nothing wrong with that argument — provided that $nge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.
The argument fails only when $n=1$. In that case it fails because the sets $H_0=h_1$ and $H_1=h_2$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $nge 2$, so the sets $H_0$ and $H_1$ would overlap.
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
add a comment |Â
up vote
50
down vote
accepted
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.
We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=h_1,h_2,dots,h_n+1$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets
$$H_0=h_1,dots,h_nquadtextandquad H_1=h_2,dots,h_n+1;.$$
Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color.
Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.
Now if $nge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_n+1$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.
There is absolutely nothing wrong with that argument — provided that $nge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.
The argument fails only when $n=1$. In that case it fails because the sets $H_0=h_1$ and $H_1=h_2$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $nge 2$, so the sets $H_0$ and $H_1$ would overlap.
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
add a comment |Â
up vote
50
down vote
accepted
up vote
50
down vote
accepted
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.
We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=h_1,h_2,dots,h_n+1$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets
$$H_0=h_1,dots,h_nquadtextandquad H_1=h_2,dots,h_n+1;.$$
Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color.
Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.
Now if $nge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_n+1$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.
There is absolutely nothing wrong with that argument — provided that $nge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.
The argument fails only when $n=1$. In that case it fails because the sets $H_0=h_1$ and $H_1=h_2$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $nge 2$, so the sets $H_0$ and $H_1$ would overlap.
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.
We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=h_1,h_2,dots,h_n+1$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets
$$H_0=h_1,dots,h_nquadtextandquad H_1=h_2,dots,h_n+1;.$$
Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color.
Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.
Now if $nge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_n+1$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.
There is absolutely nothing wrong with that argument — provided that $nge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.
The argument fails only when $n=1$. In that case it fails because the sets $H_0=h_1$ and $H_1=h_2$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $nge 2$, so the sets $H_0$ and $H_1$ would overlap.
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
answered Jun 24 '13 at 20:41
Brian M. Scott
448k39492879
448k39492879
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
add a comment |Â
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
2
2
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Very clear explanation of the part that was confusing to the OP -- good work understanding what the OP's confusion was!
– ShreevatsaR
Jun 25 '13 at 6:12
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
Excellent explanation. I think this must have cleared up completely any doubt the OP could have had. +1
– DonAntonio
Jun 25 '13 at 6:15
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
@DonAntonio: Thanks, and to ShreevatsaR as well.
– Brian M. Scott
Jun 25 '13 at 6:18
add a comment |Â
up vote
10
down vote
I'm not sure I understand fully your doubt, but the actual problem with that, and many other examples of bogus inductive proofs out there, is that when you take the two sets
$$h_1,...,h_n;,;;h_2,...,h_n,h_n+1$$
each of size $,n,$ and thus, by the Ind. Hypothesis, formed of horses of the same color, the leap to deduce all the horses altogether have the same color requires that the intersection of both sets above is not empty, something you can't prove (because it is false!) if $,n=2,$
Thus, if we had the claim "every two horse whatsoever are of the same color", then we could prove "all the horses are of the same color"
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
 |Â
show 15 more comments
up vote
10
down vote
I'm not sure I understand fully your doubt, but the actual problem with that, and many other examples of bogus inductive proofs out there, is that when you take the two sets
$$h_1,...,h_n;,;;h_2,...,h_n,h_n+1$$
each of size $,n,$ and thus, by the Ind. Hypothesis, formed of horses of the same color, the leap to deduce all the horses altogether have the same color requires that the intersection of both sets above is not empty, something you can't prove (because it is false!) if $,n=2,$
Thus, if we had the claim "every two horse whatsoever are of the same color", then we could prove "all the horses are of the same color"
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
 |Â
show 15 more comments
up vote
10
down vote
up vote
10
down vote
I'm not sure I understand fully your doubt, but the actual problem with that, and many other examples of bogus inductive proofs out there, is that when you take the two sets
$$h_1,...,h_n;,;;h_2,...,h_n,h_n+1$$
each of size $,n,$ and thus, by the Ind. Hypothesis, formed of horses of the same color, the leap to deduce all the horses altogether have the same color requires that the intersection of both sets above is not empty, something you can't prove (because it is false!) if $,n=2,$
Thus, if we had the claim "every two horse whatsoever are of the same color", then we could prove "all the horses are of the same color"
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
I'm not sure I understand fully your doubt, but the actual problem with that, and many other examples of bogus inductive proofs out there, is that when you take the two sets
$$h_1,...,h_n;,;;h_2,...,h_n,h_n+1$$
each of size $,n,$ and thus, by the Ind. Hypothesis, formed of horses of the same color, the leap to deduce all the horses altogether have the same color requires that the intersection of both sets above is not empty, something you can't prove (because it is false!) if $,n=2,$
Thus, if we had the claim "every two horse whatsoever are of the same color", then we could prove "all the horses are of the same color"
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
answered Jun 24 '13 at 9:06
DonAntonio
172k1483217
172k1483217
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
 |Â
show 15 more comments
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
$n=1$, maybe, since otherwise they share $h_2$.
– Arthur
Jun 24 '13 at 9:16
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
No, for $,n=1,$ it works trivially. For $,n=2,$ we have the huge problem: each of the sets $,h_1;,;h_2;$ have all the horses of the same color, then (this is the bogus part) also $,h_1,h_2,$ has horses of the same color. From this impasse the whole thing crumbles down in this case.
– DonAntonio
Jun 24 '13 at 9:30
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
@DonAntonio, what is meant is that it works if you have P(2) as a base case. Then, you have the same setup where you prove that for an arb. n >= 2, p(n) -> p(n+1). Then for the first n, n = 2, P(n) gives h1, h2 p(n+1) gives h1, h2, h3, and they share h2... My issue was that p(n+1) could also be h4, h5, h6, of which this proof doesn't address, but I guess after more thinking, it is obvious, that you add any element whatsoever to a set of 2, and it must be the same color, so all must be the same color. I just don't know how acceptable it would be without something more to it.
– MVTC
Jun 24 '13 at 10:10
1
1
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
But the above is assuming you could use and prove P(2) as a base case, which you can't.
– MVTC
Jun 24 '13 at 10:17
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
@DonAntonio I mean where you say "the intersection of both sets above is not empty, something you can't prove (because it is false!) if $n=2$." Here $n$ should be equal to $1$, otherwise the intersection contains $h_2$. That is what I meant. In the case $n=1$, you have two sets of uniform horses with empty intersection, thus you cannot go through with the induction step.
– Arthur
Jun 24 '13 at 10:24
 |Â
show 15 more comments
up vote
0
down vote
There is a more basic problem here : induction is irrelevant to the proof.
$P(2)$ is, by itself, a formalization of the statement that all horses are the same color. There is no reason to prove $P(2)$ to prove $P(3)$ to prove ... $P(n)$ and conclude from this chain of implications that all horses are the same color; one would try to prove $P(2)$ and in case of success, summarize that as "all horses have the same color".
If proving $P(n)$ were of interest for some reason, it can be derived in one step from $P(2)$, with no need for an induction.
The size of the set of horses is usually ignored in presentations of this argument and ones like it. But if there are $n$ horses in the universe, $P(k)$ is an empty statement for $k>n$, and is true regardless of the truth value $P(n)$. This shows that $P(n)$ is logically stronger than $P(n+1)$, and that the inductive step from $P(n) $ to $P(n+1)$ is vacuous for large $n$.
answered Jun 25 '13 at 5:21
zyx
31k33697
add a comment |Â
up vote
0
down vote
There is a more basic problem here : induction is irrelevant to the proof.
$P(2)$ is, by itself, a formalization of the statement that all horses are the same color. There is no reason to prove $P(2)$ to prove $P(3)$ to prove ... $P(n)$ and conclude from this chain of implications that all horses are the same color; one would try to prove $P(2)$ and in case of success, summarize that as "all horses have the same color".
If proving $P(n)$ were of interest for some reason, it can be derived in one step from $P(2)$, with no need for an induction.
The size of the set of horses is usually ignored in presentations of this argument and ones like it. But if there are $n$ horses in the universe, $P(k)$ is an empty statement for $k>n$, and is true regardless of the truth value $P(n)$. This shows that $P(n)$ is logically stronger than $P(n+1)$, and that the inductive step from $P(n) $ to $P(n+1)$ is vacuous for large $n$.
answered Jun 25 '13 at 5:21
zyx
31k33697
add a comment |Â
up vote
0
down vote
up vote
0
down vote
There is a more basic problem here : induction is irrelevant to the proof.
$P(2)$ is, by itself, a formalization of the statement that all horses are the same color. There is no reason to prove $P(2)$ to prove $P(3)$ to prove ... $P(n)$ and conclude from this chain of implications that all horses are the same color; one would try to prove $P(2)$ and in case of success, summarize that as "all horses have the same color".
If proving $P(n)$ were of interest for some reason, it can be derived in one step from $P(2)$, with no need for an induction.
The size of the set of horses is usually ignored in presentations of this argument and ones like it. But if there are $n$ horses in the universe, $P(k)$ is an empty statement for $k>n$, and is true regardless of the truth value $P(n)$. This shows that $P(n)$ is logically stronger than $P(n+1)$, and that the inductive step from $P(n) $ to $P(n+1)$ is vacuous for large $n$.
answered Jun 25 '13 at 5:21
zyx
31k33697
There is a more basic problem here : induction is irrelevant to the proof.
$P(2)$ is, by itself, a formalization of the statement that all horses are the same color. There is no reason to prove $P(2)$ to prove $P(3)$ to prove ... $P(n)$ and conclude from this chain of implications that all horses are the same color; one would try to prove $P(2)$ and in case of success, summarize that as "all horses have the same color".
If proving $P(n)$ were of interest for some reason, it can be derived in one step from $P(2)$, with no need for an induction.
The size of the set of horses is usually ignored in presentations of this argument and ones like it. But if there are $n$ horses in the universe, $P(k)$ is an empty statement for $k>n$, and is true regardless of the truth value $P(n)$. This shows that $P(n)$ is logically stronger than $P(n+1)$, and that the inductive step from $P(n) $ to $P(n+1)$ is vacuous for large $n$.
answered Jun 25 '13 at 5:21
zyx
31k33697
answered Jun 25 '13 at 5:21
zyx
31k33697
answered Jun 25 '13 at 5:21
zyx
31k33697
answered Jun 25 '13 at 5:21
zyx
31k33697
31k33697
add a comment |Â
add a comment |Â
up vote
0
down vote
As you pointed out, $P(1)$ is trivially true. And you are trying to prove $$P(n)implies P(n+1)$$ to finish the proof. But It's clear that $P(1)$ does NOT implies $P(2)$. Thus the statement $$P(n)implies P(n+1)$$ is not true. And this is where your proof falls.
answered Jul 31 at 5:49
Le Anh Dung
740317
add a comment |Â
up vote
0
down vote
As you pointed out, $P(1)$ is trivially true. And you are trying to prove $$P(n)implies P(n+1)$$ to finish the proof. But It's clear that $P(1)$ does NOT implies $P(2)$. Thus the statement $$P(n)implies P(n+1)$$ is not true. And this is where your proof falls.
answered Jul 31 at 5:49
Le Anh Dung
740317
add a comment |Â
up vote
0
down vote
up vote
0
down vote
As you pointed out, $P(1)$ is trivially true. And you are trying to prove $$P(n)implies P(n+1)$$ to finish the proof. But It's clear that $P(1)$ does NOT implies $P(2)$. Thus the statement $$P(n)implies P(n+1)$$ is not true. And this is where your proof falls.
answered Jul 31 at 5:49
Le Anh Dung
740317
As you pointed out, $P(1)$ is trivially true. And you are trying to prove $$P(n)implies P(n+1)$$ to finish the proof. But It's clear that $P(1)$ does NOT implies $P(2)$. Thus the statement $$P(n)implies P(n+1)$$ is not true. And this is where your proof falls.
answered Jul 31 at 5:49
Le Anh Dung
740317
answered Jul 31 at 5:49
Le Anh Dung
740317
answered Jul 31 at 5:49
Le Anh Dung
740317
answered Jul 31 at 5:49
Le Anh Dung
740317
740317
add a comment |Â
add a comment |Â
up vote
-1
down vote
I just had a student come to me with this problem. I am not a mathematician by trade, so this was the first I'd heard of it. (It's a very good problem that forces the student to understand the method!)
My natural inclination was to negate that which was supposedly proven ("all horses are the same color"), and take the "contrapositive" of the entire inductive chain, and see if we do necessarily contradict the base case. (In other words, the inductive argument supposedly gives $P(1) Rightarrow P(2) Rightarrow cdotsRightarrow P$; I wanted to see if $neg P Rightarrow cdots Rightarrow neg P(2) Rightarrow neg P(1) $.)
So, right off the bat, the negation of "all horses are the same color" is "there exists horse A and horse B such that A is a different color than B". From that, you immediately see that $P(1)$ is unsuitable base case because $neg P(2)$ means "in a set of 2 horses, the two hoses are different colors". That does not contradict anything about $P(1)$ (which of course is logically unimpeachable).
What also comes out in the above line of reasoning confirms what @zyx said: induction is irrelevant to the statement being proven. At every step, the condition that the statement be false hinges on the existence of two different horses having different colors. So, if you had somehow shown $P(2)$ to be true, game over.
answered Jul 1 '16 at 22:03
user3337629
592
add a comment |Â
up vote
-1
down vote
I just had a student come to me with this problem. I am not a mathematician by trade, so this was the first I'd heard of it. (It's a very good problem that forces the student to understand the method!)
My natural inclination was to negate that which was supposedly proven ("all horses are the same color"), and take the "contrapositive" of the entire inductive chain, and see if we do necessarily contradict the base case. (In other words, the inductive argument supposedly gives $P(1) Rightarrow P(2) Rightarrow cdotsRightarrow P$; I wanted to see if $neg P Rightarrow cdots Rightarrow neg P(2) Rightarrow neg P(1) $.)
So, right off the bat, the negation of "all horses are the same color" is "there exists horse A and horse B such that A is a different color than B". From that, you immediately see that $P(1)$ is unsuitable base case because $neg P(2)$ means "in a set of 2 horses, the two hoses are different colors". That does not contradict anything about $P(1)$ (which of course is logically unimpeachable).
What also comes out in the above line of reasoning confirms what @zyx said: induction is irrelevant to the statement being proven. At every step, the condition that the statement be false hinges on the existence of two different horses having different colors. So, if you had somehow shown $P(2)$ to be true, game over.
answered Jul 1 '16 at 22:03
user3337629
592
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
I just had a student come to me with this problem. I am not a mathematician by trade, so this was the first I'd heard of it. (It's a very good problem that forces the student to understand the method!)
My natural inclination was to negate that which was supposedly proven ("all horses are the same color"), and take the "contrapositive" of the entire inductive chain, and see if we do necessarily contradict the base case. (In other words, the inductive argument supposedly gives $P(1) Rightarrow P(2) Rightarrow cdotsRightarrow P$; I wanted to see if $neg P Rightarrow cdots Rightarrow neg P(2) Rightarrow neg P(1) $.)
So, right off the bat, the negation of "all horses are the same color" is "there exists horse A and horse B such that A is a different color than B". From that, you immediately see that $P(1)$ is unsuitable base case because $neg P(2)$ means "in a set of 2 horses, the two hoses are different colors". That does not contradict anything about $P(1)$ (which of course is logically unimpeachable).
What also comes out in the above line of reasoning confirms what @zyx said: induction is irrelevant to the statement being proven. At every step, the condition that the statement be false hinges on the existence of two different horses having different colors. So, if you had somehow shown $P(2)$ to be true, game over.
answered Jul 1 '16 at 22:03
user3337629
592
I just had a student come to me with this problem. I am not a mathematician by trade, so this was the first I'd heard of it. (It's a very good problem that forces the student to understand the method!)
My natural inclination was to negate that which was supposedly proven ("all horses are the same color"), and take the "contrapositive" of the entire inductive chain, and see if we do necessarily contradict the base case. (In other words, the inductive argument supposedly gives $P(1) Rightarrow P(2) Rightarrow cdotsRightarrow P$; I wanted to see if $neg P Rightarrow cdots Rightarrow neg P(2) Rightarrow neg P(1) $.)
So, right off the bat, the negation of "all horses are the same color" is "there exists horse A and horse B such that A is a different color than B". From that, you immediately see that $P(1)$ is unsuitable base case because $neg P(2)$ means "in a set of 2 horses, the two hoses are different colors". That does not contradict anything about $P(1)$ (which of course is logically unimpeachable).
What also comes out in the above line of reasoning confirms what @zyx said: induction is irrelevant to the statement being proven. At every step, the condition that the statement be false hinges on the existence of two different horses having different colors. So, if you had somehow shown $P(2)$ to be true, game over.
answered Jul 1 '16 at 22:03
user3337629
592
edited Jul 1 '16 at 22:18
answered Jul 1 '16 at 22:03
user3337629
592
answered Jul 1 '16 at 22:03
user3337629
592
answered Jul 1 '16 at 22:03
user3337629
592
592
add a comment |Â
add a comment |Â
up vote
-2
down vote
Just want to add a quick summary.
The proof is "almost" perfect. It simply fails on n=1.
Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.
If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.
answered Aug 15 '16 at 9:49
J. Chang
7701614
add a comment |Â
up vote
-2
down vote
Just want to add a quick summary.
The proof is "almost" perfect. It simply fails on n=1.
Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.
If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.
answered Aug 15 '16 at 9:49
J. Chang
7701614
add a comment |Â
up vote
-2
down vote
up vote
-2
down vote
Just want to add a quick summary.
The proof is "almost" perfect. It simply fails on n=1.
Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.
If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.
answered Aug 15 '16 at 9:49
J. Chang
7701614
Just want to add a quick summary.
The proof is "almost" perfect. It simply fails on n=1.
Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.
If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.
answered Aug 15 '16 at 9:49
J. Chang
7701614
answered Aug 15 '16 at 9:49
J. Chang
7701614
answered Aug 15 '16 at 9:49
J. Chang
7701614
answered Aug 15 '16 at 9:49
J. Chang
7701614
7701614
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%2f428151%2fquestions-on-all-horse-are-the-same-color-proof-by-complete-induction%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
2
P(1) is obviously false by inspection. Many single horses are of more than one colour -- they're called piebalds or skewbalds.
– Mike Scott
May 15 '17 at 20:00