5 ms·

The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.

na85 5y ago
But why would anyone assume that n horses, for arbitrary n, are the same color? That's absurd. Anyone who's ever seen a field with horses in it would trivially know that this is a faulty assumption to make. You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic.
- mannerheim 5y ago
  So it's worth noting that the inductive hypothesis isn't false for all values of n - namely, it is true for n = 0,1. But beyond that, in mathematical logic, for p -> q, you can still prove this to be true, even if p is false. In fact, if you can prove p is always false, p -> q is 'vacuously true' - it's true because you can never come up with an example of 'p and not q'. So mathematically, there's no problem with assuming an induction hypothesis that's actually false here. The real problem occurs is that the result doesn't follow from the assumption because the induction step of the 'proof' sneakily assumes that n >= 3, i.e., the induction step simply doesn't work for the n = 2 case.
- ajuc 5y ago
  > But why would anyone assume that n horses, for arbitrary n, are the same color? because that's how inductive proofs work. You assume something is true for N and show that this implies that it's also true for N+1. This combined with base case (for example for N=1) proves that it's true for all N >= 1. The assumption is just a tool used to check if you can prove the implication, the real "meat" of the proof is in the implication. Are you aware of proofs by contradiction? A: "assume N is the largest natural number". If that's true then there shouldn't be any natural numbers larger than N, but we can create N+1 and show it's larger AND natural, so assumption A leads to contradiction, so there is no such thing as the largest natural number. We used false assumption in our proof, but the proof was correct. It's a similar idea with inductive proofs - you make an assumption and see where it leads you. You don't use the assumption for the proof, you use the implication A(N)=> A(N+1) for the proof, the assumption A is just a way to see if you can prove the implication. > You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic. The logic isn't actually circular, your coconut analogy is wrong. Correct analogy would be: "when we assume N coconuts can migrate we can formally show that it implies N+1 coconuts can migrate" + "we can show that 1 coconut can migrate". You only need these 2 facts to prove all coconuts can migrate.
  - na85 5y ago
    >because that's how inductive proofs work. Well, anyone who's seen a field of horses knows that "assume any set of n horses has the same color" is not valid. So if what you say is true, then that implies the entire field of inductive reasoning is horse shit. But I don't think that's the case, so something's missing.
    - ajuc 5y ago
      What is missing is understanding that in math the sentence "if X = 3 then 2 * X = 6" is true even when X = 5. For the proof to work the implication must be true, not the assumption.
      - na85 5y ago
        But you're not trying to prove X = 3 and starting out by assuming X = 3. There wasn't even an attempt to disprove the assumption in TFA.
        ajuc 5y ago
        > But you're not trying to prove X = 3 and starting out by assuming X = 3. No, you're trying to prove for all N>=1: A(N) is true and start by proving that IF A(N) is true THEN A(N+1) is true This implication can be true even if A(N) is false, and your final proof will only use the implication, not the assumption used when proving that implication. Assumptions in math proofs can have scopes. For example in many proofs you split the domain into subsets and prove that something is true assuming X>=0 and X<0 separately. Naively you would say that we cannot assume X>=0 and then assume X<0 in the same proof because that's a contradicion. But these assumptions were used in different scopes so there's no contradiction.
        na85 5y ago
        We're talking past each other. I give up.
    - 5y ago
phkahler 5y ago
>> The inductive step assumes the hypothesis is true for n You don't get to assume the thing you're trying to prove is true as a part of the proof that it's true. The only time we assume something like that is in a proof by contradiction, where the contradiction implies either an error in our logic, or an error in the assumptions.
- deleted 5y ago
  [deleted]
- mannerheim 5y ago
  An inductive proof has two steps: 1) Prove H(0) 2) Prove that if H(n), then H(n+1) Then, by the axiom of induction, this is proven for all positive integer values of n. Because if those two conditions hold, we would have H(0) is true H(1) is true because H(0) -> H(1) ((2) with n=0) and H(0) H(2) is true because H(1) -> H(2) ((2) with n=1) and H(1) and so on. The assumption isn't what's being proven, it's proving the inductive hypothesis for the next integer.
  - phkahler 5y ago
    Yes, I was being dumb. As the article says there is a problem talking about equality among members of a set with size 1. So saying "all the horses in a set of size 1 are the same color" begs the question "same as what?" and that's where the real problem is, and the difficulty in pinning down that kind of thing is why I'm not a mathematician ;-)
    - mannerheim 5y ago
      There are several 'mathematical' ways you could phrase it (glossing over how to define the colour of a horse): 1) In a set of horses with size n, if horses A and B being both members of this set implies horse A has the same colour as horse B, then all horses in the set have the same colour. 2) In a set of horses with size n, and let f be a function on this set that produces each horse's colour. Then all horses in this set have the same colour if and only if the codomain of f on this set has size 1. You could probably prove these are equivalent definitions.

na85 5y ago

But why would anyone assume that n horses, for arbitrary n, are the same color? That's absurd. Anyone who's ever seen a field with horses in it would trivially know that this is a faulty assumption to make. You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic.

mannerheim 5y ago
So it's worth noting that the inductive hypothesis isn't false for all values of n - namely, it is true for n = 0,1. But beyond that, in mathematical logic, for p -> q, you can still prove this to be true, even if p is false. In fact, if you can prove p is always false, p -> q is 'vacuously true' - it's true because you can never come up with an example of 'p and not q'. So mathematically, there's no problem with assuming an induction hypothesis that's actually false here. The real problem occurs is that the result doesn't follow from the assumption because the induction step of the 'proof' sneakily assumes that n >= 3, i.e., the induction step simply doesn't work for the n = 2 case.
ajuc 5y ago
> But why would anyone assume that n horses, for arbitrary n, are the same color? because that's how inductive proofs work. You assume something is true for N and show that this implies that it's also true for N+1. This combined with base case (for example for N=1) proves that it's true for all N >= 1. The assumption is just a tool used to check if you can prove the implication, the real "meat" of the proof is in the implication. Are you aware of proofs by contradiction? A: "assume N is the largest natural number". If that's true then there shouldn't be any natural numbers larger than N, but we can create N+1 and show it's larger AND natural, so assumption A leads to contradiction, so there is no such thing as the largest natural number. We used false assumption in our proof, but the proof was correct. It's a similar idea with inductive proofs - you make an assumption and see where it leads you. You don't use the assumption for the proof, you use the implication A(N)=> A(N+1) for the proof, the assumption A is just a way to see if you can prove the implication. > You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic. The logic isn't actually circular, your coconut analogy is wrong. Correct analogy would be: "when we assume N coconuts can migrate we can formally show that it implies N+1 coconuts can migrate" + "we can show that 1 coconut can migrate". You only need these 2 facts to prove all coconuts can migrate.
- na85 5y ago
  >because that's how inductive proofs work. Well, anyone who's seen a field of horses knows that "assume any set of n horses has the same color" is not valid. So if what you say is true, then that implies the entire field of inductive reasoning is horse shit. But I don't think that's the case, so something's missing.
  - ajuc 5y ago
    What is missing is understanding that in math the sentence "if X = 3 then 2 * X = 6" is true even when X = 5. For the proof to work the implication must be true, not the assumption.
    - na85 5y ago
      But you're not trying to prove X = 3 and starting out by assuming X = 3. There wasn't even an attempt to disprove the assumption in TFA.
      - ajuc 5y ago
        > But you're not trying to prove X = 3 and starting out by assuming X = 3. No, you're trying to prove for all N>=1: A(N) is true and start by proving that IF A(N) is true THEN A(N+1) is true This implication can be true even if A(N) is false, and your final proof will only use the implication, not the assumption used when proving that implication. Assumptions in math proofs can have scopes. For example in many proofs you split the domain into subsets and prove that something is true assuming X>=0 and X<0 separately. Naively you would say that we cannot assume X>=0 and then assume X<0 in the same proof because that's a contradicion. But these assumptions were used in different scopes so there's no contradiction.
        na85 5y ago
        We're talking past each other. I give up.
  - 5y ago

phkahler 5y ago

>> The inductive step assumes the hypothesis is true for n You don't get to assume the thing you're trying to prove is true as a part of the proof that it's true. The only time we assume something like that is in a proof by contradiction, where the contradiction implies either an error in our logic, or an error in the assumptions.

deleted 5y ago
[deleted]
mannerheim 5y ago
An inductive proof has two steps: 1) Prove H(0) 2) Prove that if H(n), then H(n+1) Then, by the axiom of induction, this is proven for all positive integer values of n. Because if those two conditions hold, we would have H(0) is true H(1) is true because H(0) -> H(1) ((2) with n=0) and H(0) H(2) is true because H(1) -> H(2) ((2) with n=1) and H(1) and so on. The assumption isn't what's being proven, it's proving the inductive hypothesis for the next integer.
- phkahler 5y ago
  Yes, I was being dumb. As the article says there is a problem talking about equality among members of a set with size 1. So saying "all the horses in a set of size 1 are the same color" begs the question "same as what?" and that's where the real problem is, and the difficulty in pinning down that kind of thing is why I'm not a mathematician ;-)
  - mannerheim 5y ago
    There are several 'mathematical' ways you could phrase it (glossing over how to define the colour of a horse): 1) In a set of horses with size n, if horses A and B being both members of this set implies horse A has the same colour as horse B, then all horses in the set have the same colour. 2) In a set of horses with size n, and let f be a function on this set that produces each horse's colour. Then all horses in this set have the same colour if and only if the codomain of f on this set has size 1. You could probably prove these are equivalent definitions.