
 Agnishom
 Real Member

Colored Horses
Theorem If A is a set of horses, then all the horses in A have the same color. Proof Let S be the statement, "If A is the set of n horses, then all the horses in A are of the same color." Clearly S is a statement concerning positive integers. (1) S is true for n = 1. Rephrased, it tells that "If A is a set of 1 horse, then all the horses in A have the same color." Obviously, this is true. (2) If S is true for n = k, then S is true for n = k + 1. The horses can be numbered from 1 to k + 1. For the sake of convention, let this be already done. Removing Horse #1, we are left with k horses. We are already assured that a set of k horses have the horses colored in a similar way. Therefore, Color of Horse #2 = Color of Horse #3 = Color of Horse #4 = ... =Color of Horse #(k+1) On the Other hand and with the same arguments, removing Horse #(k+1) would yield: Color of Horse #1 = Color of Horse #2 = Color of Horse #3 = ... =Color of Horse #k Therefore, Color of Horse #1 = Color of Horse #2 = Color of Horse #3 =....=Color of Horse #(k+1). So S is true for n = k + 1, given that S is true for n = k Invoking the principle of induction, (1) and (2) proves S is true for all positive integers. Therefore, the Theorem is true. Q.E.D.Corollary All the horses in the universe are of the same color. Proof Let A be the set of all horses in the Universe. Therefore, by the Theorem, all the horses in the universe are of the same color. Source: Dots and Lines by Richard J. Trudeau
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.' 'God exists because Mathematics is consistent, and the devil exists because we cannot prove it' 'Who are you to judge everything?' Alokananda
Re: Colored Horses
(2) If S is true for n = k, then S is true for n = k + 1.
The horses can be numbered from 1 to k + 1.
I think that the flaw in the argument is that you have to start by assuming that it is true for n=k then show that it follows that it is true for n=k+1.
The statement "The horses can be numbered from 1 to k + 1" means that you are cheating by assuming that the statement is true for n=k+1 and then "proving" that it is true for n=k+1
The horses can only be numbered from 1 to k. So when you add the k+1st horse it can of course be different.
For the sake of convention, let this be already done. Removing Horse #1, we are left with k horses.
So here, we are only left with k1 horses. We now have to add two horses to get to k+1 One of these is the same color, but the other might not be.
(At least that is what I think. I wonder what the more experienced MIF users think of this problem.)
Re: Colored Horses
I have thought of another idea for what is wrong:
Are we saying that the hypothesis is true for all sets of horses of that size of of just one particular horse set size?
There is a big difference between "I have one set of one horse which is the same color as itself" to "All pairwise comparisons of pairs of horses have the same color".
Take the basis case n=1. If we take the first statement to be the interpretation then it is true because we are only comparing the horse with itself.
However it is nonsense in the second interpretation: If all pairs of sets of horses with n=1 have to be the same color for the basis case to be true then the basis case is not true.
Are we trying to argue to get from n=1 to n=2 that given that a horse is the same color as itself then if we look at the set containing both horses take away one horse it is the same as itself therefore n=2 works?
There is an inconsistent phrase in the theorem of "the" set of horses as compared to "a" set of horses. This is a big difference. Either n=1 just has to represent one isolated set of one horse, or it has to represent every set including every pairwise comparison between two sets to be valid, otherwise the inductive step will not be valid.
I think that the case for n=1 probably is supposed to be that each horse however chosen is the same color as itself. However the n=2 case would be that any pair of horses however chosen are the same color. We obviously cannot get from n=1 to n=2 so there has to be a flaw. If we have two horses {horse1, horse2} then remove n=1 of them we get {horse1} or {horse2} either way the inductive step from n=1 to n=2 will not be proven. The fact that the hypothesis holds for the sets individually does not tell us anything about the pairwise comparison between the two horses. If we number the set from 1 to (21) then this is 1 to 1 ie horse1. If we number them from 2 to 2 then this is horse2. Of course if we could prove the hypothesis for the case n=2 then we would have proven it for all n because if we can arbitarily choose any pair and show that they have the same color then all horses are the same color. So yes my revised answer would be that we cannot get from n=1 to n=2. This assumes the interpretation that we are taking ANY pair of horses for n=2 and not just one isolated set. (If it is an isolated set then all of the n=k to n=k+1 steps are flawed, because we are always taking in a new horse that we don't know anything about.) The inductive step could be said to work from n=2 to n=3 because each pair is covered by the n=2 case, but if you go through the inductive step for n=1 to n=2 then of course it is nonsense, because there is no overlap between the one size smaller subsets of {horse1, horse2}.
Last edited by SteveB (20130502 05:31:53)
 Agnishom
 Real Member

Re: Colored Horses
I think that the flaw in the argument is that you have to start by assuming that it is true for n=k then show that it follows that it is true for n=k+1.
The statement "The horses can be numbered from 1 to k + 1" means that you are cheating by assuming that the statement is true for n=k+1 and then "proving" that it is true for n=k+1
The horses can only be numbered from 1 to k. So when you add the k+1st horse it can of course be different.
We know there are k + 1 horses, we can number them from 1 to k+1 always, even if they are not of the same color
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.' 'God exists because Mathematics is consistent, and the devil exists because we cannot prove it' 'Who are you to judge everything?' Alokananda
Re: Colored Horses
Yes I agree with you there. My first post was not really the point where the argument fails.
The problem is not where we take an arbitrary set of size k + 1, but rather the point in my second post.
The inductive step only works if we can argue it on the basis of overlap between smaller subsets.
Take the case where k = 2, since k + 1 is 3 we have {horse1, horse2, horse3} and we could argue that if we have already proven the case where n = 2 then the two subsets {horse1, horse2} and {horse2, horse3} are the same color because they are sets of size 2 which contain horses of the same color.
However now let k = 1, since k + 1 is 2 we have {horse1, horse2} the subsets chosen by the inductive step are {horse1} and {horse2} these do not overlap so we cannot conclude that the horses are the same color. The fact that the size 1 sets are the same color as themselves is not enough.
So my revised answer is that the inductive step does not work for k = 1 to get us from the case n = 1 to n = 2. (In other words we cannot jump from saying that every horse is the same color as itself to saying that any pair of horses are the same color. Obviously if we did find that every pair of horses were the same color, then all of the other cases would follow. So yes I agree the fact that a set of size k + 1 is taken does not necessarily mean that the inductive step does not work, and my answer in post #2 was not correct. At the time I had not read the pseudo proof carefully and perhaps rushed my answer a bit. There are a few minor things about the alleged proof which are not very good style.)
 bob bundy
 Moderator
Re: Colored Horses
hi Agnishom,
I just don't think the induction step proves anything. The k=1 case is fine.
Why not? Well if you have a set of n similarly coloured horses, the induction step requires that you show that adding another horse gives n + 1 similarly coloured horses. Clearly this does not happen.
Here's a contrasting example which I believe is valid.
Supposing a child has a large collection of red bricks.
The child might form the following hypothesis:
In any set of n bricks from my collection, all will have the same colour.
Proof by induction:
(i) Make a set of one one brick. Is it the same as all the other bricks in the set. Yes, because it is the only one.
(ii) Assume I have a set of n bricks, all having the same colour. I add one more brick to the set. The first n bricks were all red, because of the axiom " a child has a large collection of red bricks." The new brick is red, because of the axiom " a child has a large collection of red bricks."
Therefore all n+1 bricks are red => the set of n+1 bricks are all of the same colour.
Proof complete.
Now can someone explain a much bigger puzzle? Why did I bother with this proof?
Bob
You cannot teach a man anything; you can only help him find it within himself..........Galileo Galilei
 Nehushtan
 Power Member
Re: Colored Horses
The flaw in the argument is that the inductive step assumes n ≥ 2. In order to remove one horse from a set of n horses and still have at least one horse left over*, you clearly must have n ≥ 2.
You have shown that the statement S is true for n = 1. You have not shown that it’s true for n = 2. In order for the inductive proof to work, you must show that S is true for n = 2 as well – which you can’t because S isn’t true for n = 2.
*The inductive argument compares the colour of Horse #1 and of Horse #k+1 with the colour of the intermediate horses #2, …, #k. The inductive proof assumes that there is at least one intermediate horse.
Last edited by Nehushtan (20130503 02:34:00)
134 books currently added on Goodreads
Re: Colored Horses
bob bundy wrote:hi Agnishom,
I just don't think the induction step proves anything. The k=1 case is fine.
Why not? Well if you have a set of n similarly coloured horses, the induction step requires that you show that adding another horse gives n + 1 similarly coloured horses. Clearly this does not happen.
Here's a contrasting example which I believe is valid.
Supposing a child has a large collection of red bricks.
The child might form the following hypothesis:
In any set of n bricks from my collection, all will have the same colour.
Proof by induction:
(i) Make a set of one one brick. Is it the same as all the other bricks in the set. Yes, because it is the only one.
(ii) Assume I have a set of n bricks, all having the same colour. I add one more brick to the set. The first n bricks were all red, because of the axiom " a child has a large collection of red bricks." The new brick is red, because of the axiom " a child has a large collection of red bricks."
Therefore all n+1 bricks are red => the set of n+1 bricks are all of the same colour.
Proof complete.
Now can someone explain a much bigger puzzle? Why did I bother with this proof?
Bob
Hi Bob
The statement is that every n horses are if the same colour, not a particular set of n horses.
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 Agnishom
 Real Member

Re: Colored Horses
I like SteveB's disproof in #5. Thanks to Nehushtan
Bob Bundy, I am not getting your point. My induction step shows that adding 1 preserves the property.
Last edited by Agnishom (20130503 00:39:28)
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.' 'God exists because Mathematics is consistent, and the devil exists because we cannot prove it' 'Who are you to judge everything?' Alokananda
Re: Colored Horses
Agnishom wrote:I like SteveB's disproof in #5. Thanks to Nehushtan Bob Bundy, I am not getting your point. My induction step shows that adding 1 preserves the property.
Thanks Nehushtan, that was a much clearer explanation than mine. Basically it amounted to the same thing that the case where k=1 does not allow the inductive step to work, because an intermediate horse is needed otherwise we end up with two equations without a horse color on the other side of the equation, because if the set only has two horses in it then removing one leaves just one, and of course the equation needs something on both sides, and the horses from 2 to k are nonexistent.
About the Bob Bundy point: anonimnystefy has answered this already, in that Bob has (perhaps like me in my first post) not read the theorem very well and has interpreted it in a way where the set under consideration is just a particular set (which could be thought of as being added to by one element each time one is added to n) rather than ANY set of that size picked from the set of all horses. I realised after studying the question more closely and thinking about it for longer, that it could not possibly be this problem that was being intended by the author of the book. If it were that problem then it would be the inductive step that fails and in every case it would fail because if we are adding a new horse from an outside source from which the theorem is not anything to do with. However this is as I mentioned earlier not a correct interpretation of the problem, and as far as I know, does not lead to anything particularly remarkable. It does however show that human error can occur both in producing a new mathematical idea, as well as spotting the correct flaw (as I managed to get wrong in my post #2 when I jumped to the wrong conclusion regarding the flaw). Also communicating the idea well can cause problems as I managed to show in my next post on when I had realised what the flaw was in my head, but did not explain it very well.
To go back to the original problem though: The inductive step does work for k = 2 and all k > 2 as well. However if we cannot get from case n=1 to case n=2 using the inductive step (which we can't) then this does not make any difference because the case where n=3 can only be proven by induction if the n=2 case is proven. The case n=2 really should be proven as a separate case (another basis case), but common sense tells us that we cannot literally go through an infinite number of horses to show this for every horse set of size 2. In mathematics a property of the mathematics might give us some way of proving something for an infinite set, but obviously equal horse color is not likely to have such a property. If it were a real maths problem that we were trying to solve and the inductive step was not valid for k=1 (but was for k>1) then we would try to solve this case as a special case unless of course there was some other way round the problem.
Re: Colored Horses
This reminds me of the prisoner who was told "You will be executed one day this week but NOT if you tell us which day it will be" So he says (like your k and k+1) "Well I WIIL be executed one day this week Today is Sunday, so that means BEFORE next Saturday So if they leave it til Saturday, that is too late  for early Saturday morn I will KNOW it is "today" and they will not do it if I KNOW the day! Similarly they cannot do it on Friday Similarly Thursday So they CANNOT DO It
But Wednesday the jailer knocks on the door and says "It's today and you did not tell me!"
 Agnishom
 Real Member

Re: Colored Horses
But the jailer was already told that it will be a day this week
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.' 'God exists because Mathematics is consistent, and the devil exists because we cannot prove it' 'Who are you to judge everything?' Alokananda
 bob bundy
 Moderator
Re: Colored Horses
Mrwhy wrote:This reminds me of the prisoner who was told "You will be executed one day this week but NOT if you tell us which day it will be"
That sounds a lot like this one:
http://www.mathisfunforum.com/viewtopic.php?id=17556
Bob
You cannot teach a man anything; you can only help him find it within himself..........Galileo Galilei
Re: Colored Horses
The limit operator is just an excuse for doing something you know you can't. “It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman “Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
