The first n horses and the second n horses have an overlap of n-1 horses that are all the same color. So first and the last horse have to be the same color.
You need to make this more explicit, to expose the hidden assumption:
Take a horse from the overlap, which is the same color as the first horse and the same color as the last horse, so by transitivity, the first and last horse are the same color.
But why can you take a horse from the overlap? You can if the overlap is non-empty. Is the overlap non-empty? It has n-1 horses, so it is non-empty if n-1 > 0. Is n-1 > 0? It is if n > 1. Is n > 1? No, we want the proof to cover the case where n=1.
But why can you take a horse from the overlap? You can if the overlap is non-empty. Is the overlap non-empty? It has n-1 horses, so it is non-empty if n-1 > 0. Is n-1 > 0? It is if n > 1. Is n > 1? No, we want the proof to cover the case where n=1.
That’s exactly what I was trying to get them to understand.
Do you think that they couldn’t, and that’s why they started arguing with me on irrelevant grounds?
And the point that I am trying to get you to understand, is that you do not need special rule to always check P(2) when making a proof by induction, in this case where the induction fails at P(1) → P(2), carefully trying to prove the induction step will cause you to realize this. More generally you cannot rigorously prove that for all integers n > 0, P(n) → P(n+1) if it is not true, and in particular if P(1) does not imply P(2).
More generally you cannot rigorously prove that for all integers n > 0, P(n) → P(n+1) if it is not true, and in particular if P(1) does not imply P(2).
Sorry, I can’t figure out what you mean here. Of course you can’t rigorously prove something that’s not true.
I have a feeling that our conversation boils down to the following:
Me: There exists a case where induction fails at n=2.
You: For all cases, if induction doesn’t fail at n=2, doesn’t mean induction doesn’t fail. Conversely, if induction fails, it doesn’t mean it fails at n=2. You have to carefully look at why and where it fails instead of defaulting to “it works at n=2, therefore it works.”
Is that correct, or am I misinterpreting?
Anyways, let’s suppose you’re making a valid point. Do you think that my interlocutors were arguing this very point? Or do you think they were arguing to put me back in my place, like TheOtherDave suggests, or that there was a similar human issue that had nothing to do with the actual argument?
To butt in, I doubt your interlocutors were attempting to argue this point; they seem like they were having more fundamental issues. But your original argument does seem to be a bit confused.
Induction fails here because the inductive step fails at n=2. The inductive step happens to be true for n>2, but it is not true in general, hence the induction is invalid. The point is, rather than “you have to check n=2” or something similar, all that’s going on here is that you have to check that your inductive step is actually valid. Which here means checking that you didn’t sneak in any assumptions about n being sufficiently large. What’s missing is not additional parts to the induction beyond base case and inductive step, what’s missing is part of the proof of the inductive step.
Of course you can’t rigorously prove something that’s not true.
Your hindsight is accurate, but more than just recognizing the claim as true when presented to you, I am trying to get you to take it seriously and actively make use of it, by trying to rigorously prove things rather than produce sloppy verbal arguments that feel like a proof, which is possible to do for things that aren’t true.
For all cases, if induction doesn’t fail at n=2, doesn’t mean induction doesn’t fail. Conversely, if induction fails, it doesn’t mean it fails at n=2. You have to carefully look at why and where it fails instead of defaulting to “it works at n=2, therefore it works.”
This is accurate, and related, but not the entire point. Distinguish between a proof by mathematical induction and the process of attempting to produce a proof by mathematical induction. One possible result of attempting to produce a proof is a proof. Another possible result is the identification of some difficulty in the proof that is the basis of an insight that induction isn’t the right approach or, as in the colored horses examples, that the thing you are trying to prove is not actually true.
The point is that if you are properly attempting to produce a proof, which includes noticing difficulties that imply that the claim you are trying to prove is not actually true, you will either produce a valid proof or identify why your approach fails to provide a proof.
Do you think that my interlocutors were arguing this very point? Or do you think they were arguing to put me back in my place, like TheOtherDave suggests, or that there was a similar human issue that had nothing to do with the actual argument?
No, your interlocutors were not arguing this point. Their performance, as reported by you, was horribly irrational. But you should apply as much scrutiny to your own beliefs and arguments as to your interlocutors.
The case of two horses is special here because the sets 1..n and 2..n+1 don’t overlap if n+1 = 2, and not because of some fundamental property of every induction hypothesis, but that—along with some arbitrary large n, and maybe the next case if I’m using any parity tricks—is one of the first cases I’d check when verifying a proof by induction.
The case of P(n) → P(n+1) (i.e., the second part of the induction argument) that fails is n=1. (In other words n+1 = 2).
The second part of the induction argument must begin (i.e., include n >= n0) at the value n0 that you have proven in the first part to be true from 1 to n0. In this case n0 = 1, so you must begin the induction at n = 1.
You’re right, of course. I was trying to describe the flaw in the set-overlap assumption without actually going through an inductive step, on the assumption that that would be clearer, but in retrospect my phrasing muddled that.
You need to make this more explicit, to expose the hidden assumption:
Take a horse from the overlap, which is the same color as the first horse and the same color as the last horse, so by transitivity, the first and last horse are the same color.
But why can you take a horse from the overlap? You can if the overlap is non-empty. Is the overlap non-empty? It has n-1 horses, so it is non-empty if n-1 > 0. Is n-1 > 0? It is if n > 1. Is n > 1? No, we want the proof to cover the case where n=1.
That’s exactly what I was trying to get them to understand.
Do you think that they couldn’t, and that’s why they started arguing with me on irrelevant grounds?
And the point that I am trying to get you to understand, is that you do not need special rule to always check P(2) when making a proof by induction, in this case where the induction fails at P(1) → P(2), carefully trying to prove the induction step will cause you to realize this. More generally you cannot rigorously prove that for all integers n > 0, P(n) → P(n+1) if it is not true, and in particular if P(1) does not imply P(2).
Sorry, I can’t figure out what you mean here. Of course you can’t rigorously prove something that’s not true.
I have a feeling that our conversation boils down to the following:
Me: There exists a case where induction fails at n=2.
You: For all cases, if induction doesn’t fail at n=2, doesn’t mean induction doesn’t fail. Conversely, if induction fails, it doesn’t mean it fails at n=2. You have to carefully look at why and where it fails instead of defaulting to “it works at n=2, therefore it works.”
Is that correct, or am I misinterpreting?
Anyways, let’s suppose you’re making a valid point. Do you think that my interlocutors were arguing this very point? Or do you think they were arguing to put me back in my place, like TheOtherDave suggests, or that there was a similar human issue that had nothing to do with the actual argument?
To butt in, I doubt your interlocutors were attempting to argue this point; they seem like they were having more fundamental issues. But your original argument does seem to be a bit confused.
Induction fails here because the inductive step fails at n=2. The inductive step happens to be true for n>2, but it is not true in general, hence the induction is invalid. The point is, rather than “you have to check n=2” or something similar, all that’s going on here is that you have to check that your inductive step is actually valid. Which here means checking that you didn’t sneak in any assumptions about n being sufficiently large. What’s missing is not additional parts to the induction beyond base case and inductive step, what’s missing is part of the proof of the inductive step.
Your hindsight is accurate, but more than just recognizing the claim as true when presented to you, I am trying to get you to take it seriously and actively make use of it, by trying to rigorously prove things rather than produce sloppy verbal arguments that feel like a proof, which is possible to do for things that aren’t true.
This is accurate, and related, but not the entire point. Distinguish between a proof by mathematical induction and the process of attempting to produce a proof by mathematical induction. One possible result of attempting to produce a proof is a proof. Another possible result is the identification of some difficulty in the proof that is the basis of an insight that induction isn’t the right approach or, as in the colored horses examples, that the thing you are trying to prove is not actually true.
The point is that if you are properly attempting to produce a proof, which includes noticing difficulties that imply that the claim you are trying to prove is not actually true, you will either produce a valid proof or identify why your approach fails to provide a proof.
No, your interlocutors were not arguing this point. Their performance, as reported by you, was horribly irrational. But you should apply as much scrutiny to your own beliefs and arguments as to your interlocutors.
The case of two horses is special here because the sets 1..n and 2..n+1 don’t overlap if n+1 = 2, and not because of some fundamental property of every induction hypothesis, but that—along with some arbitrary large n, and maybe the next case if I’m using any parity tricks—is one of the first cases I’d check when verifying a proof by induction.
The case of P(n) → P(n+1) (i.e., the second part of the induction argument) that fails is n=1. (In other words n+1 = 2).
The second part of the induction argument must begin (i.e., include n >= n0) at the value n0 that you have proven in the first part to be true from 1 to n0. In this case n0 = 1, so you must begin the induction at n = 1.
I have edited my comment to avoid this confusion.
You’re right, of course. I was trying to describe the flaw in the set-overlap assumption without actually going through an inductive step, on the assumption that that would be clearer, but in retrospect my phrasing muddled that.
I’ll see if I can fix that.