Do you mean you went through the proof and verified it, or falsified it?
As I understand it, it goes something like this:
…
You have a set of n horses.
Assume a set of n horses are the same color.
Now you also have a set of n+1 horses.
Set 1: (1, 2, 3, … n)
Set 2: (2, 3, 4, … n+1)
Referring back to the assumption, both sets have n horses in them, Set 2 is just incremented forward one, therefore, Set 2’s horses are all one color, and Set 1’s horses are all one color.
Finally, Set 1 and Set 2 always overlap, therefore that the color of all Set 1 and Set 2’s horses are the same.
…
So, if you hold the ‘all horses in a set of size n horses are the same color’ assumption as an actually valid assertion, for the sake of argument…
This does logically hold for Set 1 and Set 2 … but only in isolation, not compared to each other.
The problem is that the sets do not actually always overlap.
If n = 1, and n + 1 = 2, then:
Set 1 = ( 1 )
Set 2 = ( 2 )
No overlap.
Thus the attempted induction falls apart.
Set 1’s horse 1 could be brown, Set 2’s horse 2 could be … fucking purple… each set contains only one distinct color, that part is true, but the final assertion that both sets always overlap is false, so when you increment to:
Set 1 = ( 1, 2 )
Set 2 = ( 2, 3 )
We now do not have necessarily have the same colored horse 2 in each set, Set 1’s horse 1 and 2 would be brown, Set 2’s horse 2 and 3 would be purple.
…
I may be getting this wrong in some way, it’s been almost 20 years since I last did set theory / mathematical proof type coursework.
Yep this is the exact issue. This problem comes up frequently in a first discrete math or formal mathematics course in universities, as an example of how subtle mistakes can arise in induction.
I did do this proof by induction back in the day, but now looking at the article I am clueless.
Do you mean you went through the proof and verified it, or falsified it?
As I understand it, it goes something like this:
…
You have a set of n horses.
Assume a set of n horses are the same color.
Now you also have a set of n+1 horses.
Set 1: (1, 2, 3, … n)
Set 2: (2, 3, 4, … n+1)
Referring back to the assumption, both sets have n horses in them, Set 2 is just incremented forward one, therefore, Set 2’s horses are all one color, and Set 1’s horses are all one color.
Finally, Set 1 and Set 2 always overlap, therefore that the color of all Set 1 and Set 2’s horses are the same.
…
So, if you hold the ‘all horses in a set of size n horses are the same color’ assumption as an actually valid assertion, for the sake of argument…
This does logically hold for Set 1 and Set 2 … but only in isolation, not compared to each other.
The problem is that the sets do not actually always overlap.
If n = 1, and n + 1 = 2, then:
Set 1 = ( 1 )
Set 2 = ( 2 )
No overlap.
Thus the attempted induction falls apart.
Set 1’s horse 1 could be brown, Set 2’s horse 2 could be … fucking purple… each set contains only one distinct color, that part is true, but the final assertion that both sets always overlap is false, so when you increment to:
Set 1 = ( 1, 2 )
Set 2 = ( 2, 3 )
We now do not have necessarily have the same colored horse 2 in each set, Set 1’s horse 1 and 2 would be brown, Set 2’s horse 2 and 3 would be purple.
…
I may be getting this wrong in some way, it’s been almost 20 years since I last did set theory / mathematical proof type coursework.
Yep this is the exact issue. This problem comes up frequently in a first discrete math or formal mathematics course in universities, as an example of how subtle mistakes can arise in induction.