0

in "All horses have the same color" problem, we figured out that P(2) is not correct. obviously it is a easy job to check a case like P(2). but what is the guarantee that in the rest of the induction questions, we don't need to check each item?

maybe we face another problem same as this problem (not this "All horses have the same color" problem) and the mistake was hidden in n=44 for example.

we cannot find that case easily. then what should we do?

How we can be sure that our base case is right? and after falling first domino, all the other dominoes will be fallen? we use induction because we don't want to check all of them.

sorry for my bad English writing.

Mohammad Mehdi Sarfejoo
  • 135
  • 5
    The issue is that the proof that $P(n) \implies P(n+1)$ has a hidden assumption that $n \ge 2$. You start with assuming we have $n + 1$ horses (which we can validly conclude has at least $2$ horses, but we'll actually need $3$), take away one, and get a collection of $n$ horses, then take away a different one, and get a collection of $n$ horses. Then, we tacitly (and wrongly) assume that these two collections have a third horse in common, so that we can conclude that both collections are all of the same colour. The lesson: make sure your induction step works for all $n$, not just most $n$. – Theo Bendit Nov 11 '22 at 01:19
  • 1
    Link for those who have not heard about this https://en.wikipedia.org/wiki/All_horses_are_the_same_color – Henry Nov 11 '22 at 01:40
  • @TheoBendit *make sure your induction step works for all n, not just most n.* exactly this is my question. in this problem, our induction step did not work for n=2. what if in my next problem, the induction step does not work for n=65 !? we cannot check that for all n. – Mohammad Mehdi Sarfejoo Nov 11 '22 at 02:34
  • 1
    @MohammadMehdiSarfejoo It's baked into the logic. There's an unfounded and (occasionally) false assertion that the two collections of $n$ horses have some overlap. If they do have overlap, then the induction step works fine. If they don't, then there's no way to conclude that all the $n + 1$ horses have the same colour. This makes that step an unproven (and false) assertion. This is what you need to look for (in any false proof, induction or not) to see how it breaks down. This one's mistake is just camouflaged better than most. – Theo Bendit Nov 11 '22 at 02:49
  • 1
    @MohammadMehdiSarfejoo And in fact if you could prove $n=2$ as a base case -- that is, any two horses are the same color -- then you could prove by induction that any larger set of horses was the same color, because for $n\geq2$ any set of $n+1$ horses, even for $n=65,$ has two overlapping subsets of $n$ horses. – David K Nov 11 '22 at 02:54
  • 1
    Many years ago, I formalized this argument on a computer. This makes the erroneous assumption very clear. Perhaps it can help. – Dan Doel Nov 11 '22 at 02:56
  • 1
    see https://www.fortfreedom.org/b19.htm The original essay appeared in a book my parents had, published about 1963... Especially: Theorem 2. Alexander the Great did not exist and he had an infinite number of limbs. – Will Jagy Nov 11 '22 at 02:58
  • @DavidK actually I mentioned n=65 for another problem except this problem. I want to say that if we face another problem =(not this "All horses have the same color" problem) and then there is another mistake like this which is hidden in for example n=65, then how can we find it? – Mohammad Mehdi Sarfejoo Nov 11 '22 at 03:11
  • @DanDoel Thank you so much Dan. – Mohammad Mehdi Sarfejoo Nov 11 '22 at 03:12
  • @WillJagy Thank you so much Will. – Mohammad Mehdi Sarfejoo Nov 11 '22 at 03:12
  • 1
    You have to examine the logic of the argument. There must be a clear way to show that it does work for all cases that it is claimed to work for. If the logic for all cases is not airtight, there is no proof. But you can only ask this question usefully about a particular proof. There is no single formula that you can apply to every proof and know whether it is valid. – David K Nov 11 '22 at 03:25
  • @DavidK but if there is a hidden assumption in the proof, it can lead us to that particular integer n which is the cause of mistake? right? – Mohammad Mehdi Sarfejoo Nov 11 '22 at 03:31
  • Keep in mind that an attempted proof can be invalid even though the theorem is true. In cases where the theorem is false (like the color of the horses), a flaw in the proof may point toward a particular $n$ where the inductive step doesn't work. In this case it's $n=1.$ In an attempted proof of some other theorem the inductive step could be false for every value of $n.$ As Tolstoy said, "All valid proofs by induction resemble each other, but each invalid proof by induction is invalid in its own way." – David K Nov 11 '22 at 04:53
  • (Tolstoy didn't actually say that, of course.) – David K Nov 11 '22 at 04:53
  • Actually, the base case $n=1$ is already problematic , although it is technically correct. If we only have one horse , we cannot really compare horses (only the horse to itself). A different colour can only occur, if we have a second horse. Considering this, we can conclude that we actually have to begin with $n=2$ and this case turns out to be false. – Peter Nov 13 '22 at 09:24
  • The lesson might be that the laziness (holding the base case as trivial as possible) can be dangerous (if one is careless later). Usually , the induction step is anyway much more difficult then the base case, so it can pay out to check some small cases. Cases were the induction step fails late occur extrmely rarely in practice , but as pointed out, careful analysis of the induction step will reveal them. – Peter Nov 13 '22 at 09:31

1 Answers1

1

As noted in the comments above, if you carefully check the logic of the proof, you can find any hidden assumptions. But proofs are written by people, who are capable of self-delusion (see, e.g., [1]). Thus it is also a good idea to check $n=2,3,4$ rather than just one base case, even though this is not logically necessary. Indeed, I would recommend checking a few cases before starting the general induction proof.

Knuth (who certainly works hard to check the logic of his proofs) famously remarked once, when sharing some code:

"Beware of bugs in the above code; I have only proved it correct, not tried it." https://en.wikiquote.org/wiki/Donald_Knuth

[1] From https://www.math.columbia.edu/~woit/wordpress/?p=10560 : " As discussed here a couple months ago, Peter Scholze and Jakob Stix believe they have found a serious problem with Mochizuki’s claimed proof of the abc conjecture, and traveled to Kyoto in March to discuss it with him."

[2] https://www.quantamagazine.org/titans-of-mathematics-clash-over-epic-proof-of-abc-conjecture-20180920/

Yuval Peres
  • 21,955
  • you mean (in any problem) if there is a hidden assumption in the proof, it can lead us to that particular integer n which is the cause of mistake? you know why I'm asking this? because I'm worry about some type of questions and problems in which I've specified a base case (like n=1) and then the proof will be wrong and false for some n like for example n=12 ! it is difficult to find and I cannot check all of those numbers. As a result, I am always worried that I may choose a wrong base case. – Mohammad Mehdi Sarfejoo Nov 11 '22 at 03:28