3 ms·

The basic principle of induction is to prove k+1 in terms of k. If we can show it's true for k=1, then it's true for all k>1 as well. But assuming that it's tru

The basic principle of induction is to prove k+1 in terms of k. If we can show it's true for k=1, then it's true for all k>1 as well. But assuming that it's true for k is a basic part of inductive proofs. It's like falling dominoes. You show the first domino falls; you show that, if the previous domino falls, the next domino will also fall; and thus all the dominoes fall. The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, which invalidates the generalization that the induction depends on. The steps obscure an extra predicate on the generalization, so that it's not fully general. If the proof (of some other property) didn't have that hidden predicate, or something like it, it would be fine. The problem really is that far down.

raverbashing 6y ago
I know how induction works, believe it or not > in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, Yes and those are steps 7 and 8, not step 9. Because that "proof" is already wrong. It comes from a wrong premise, surely, but that's already wrong at this time This is why I'm calling BS on step 9 being the fallacy there. > Step 5: Let G be an arbitrary group of k+1 people > Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age (Right conclusion from wrong premises) > The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, 7 and 8 doesn't work for any k > 1, it's not "for all" it's "for any". That's why this is so ridiculous Step 9 fails for k<=1 and k=2 and that's it. So yeah the induction doesn't work, but it's not only because of step 9, it's because of 7/8 (which are just erroneous conclusions of a false premise)
- tsimionescu 6y ago
  Why is step 7 wrong? If all groups of k people had the same age, then everyone in G except P would have had the same age. That is a true proposition ('false => true' is true). The greater point of the excersise is to show a failure mode of an inductive proof. If the property hadn't been so clearly false, it may have been harder to spot the actual mistake ; the excersise is meant to prepare you for those other cases.
  - raverbashing 6y ago
    > If all groups of k people had the same age, then everyone in G except P would have had the same age. That is a true proposition ('false => true' is true) The logical formula is right but the premise is wrong. But 7 is considering both. It's like saying "Person P had 1Mi dollars and got 10% interest last year then now Person P has 1100k dollars". But Person P didn't. The interest calculation is correct, but the premise is wrong. > The greater point of the excersise is to show a failure mode of an inductive proof. I see that, but the fact that the other steps are not contributing to the solution makes it harder to argue that the mistake is there. Because that statement needs a qualifier, but it is "not wrong" per se (it's not even affirming anything, it's just saying "pick the person you haven't picked (from a group that might not have anyone else to pick, fair enough) But everything derived from a false premise can be false. That's how we get the proofs by contradiction, right? We keep going down the wrong path until it obviously blows up Or we could just prove this whole problem false with a set of two people in Canada with different ages (counterexample to Step 5). Case closed.
    - tsimionescu 6y ago
      > It's like saying "Person P had 1Mi dollars and got 10% interest last year then now Person P has 1100k dollars". But Person P didn't. The interest calculation is correct, but the premise is wrong. No it is not like that. It is like saying "IF person P had 1Mi dollars and got 10% interest last year THEN now Person P would have 1100k dollars". This statement is true regardless of how much money person P has today. That is how steps 5-8 work: they are true regardless of the truth of the antecedent ('in every group of k people, everyone has the same age'). Finding 2 people in Canada of the same age would NOT prove step 5 wrong (though it would show it to be pointless, of course). Probably a much more interesting problem would have found a less obviously wrong premise to demonstrate this with. I'd love to find a way to build a similar argument for Fermat's last theorem or some other non-trivial observation.

raverbashing 6y ago

I know how induction works, believe it or not > in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, Yes and those are steps 7 and 8, not step 9. Because that "proof" is already wrong. It comes from a wrong premise, surely, but that's already wrong at this time This is why I'm calling BS on step 9 being the fallacy there. > Step 5: Let G be an arbitrary group of k+1 people > Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age (Right conclusion from wrong premises) > The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, 7 and 8 doesn't work for any k > 1, it's not "for all" it's "for any". That's why this is so ridiculous Step 9 fails for k<=1 and k=2 and that's it. So yeah the induction doesn't work, but it's not only because of step 9, it's because of 7/8 (which are just erroneous conclusions of a false premise)

tsimionescu 6y ago
Why is step 7 wrong? If all groups of k people had the same age, then everyone in G except P would have had the same age. That is a true proposition ('false => true' is true). The greater point of the excersise is to show a failure mode of an inductive proof. If the property hadn't been so clearly false, it may have been harder to spot the actual mistake ; the excersise is meant to prepare you for those other cases.
- raverbashing 6y ago
  > If all groups of k people had the same age, then everyone in G except P would have had the same age. That is a true proposition ('false => true' is true) The logical formula is right but the premise is wrong. But 7 is considering both. It's like saying "Person P had 1Mi dollars and got 10% interest last year then now Person P has 1100k dollars". But Person P didn't. The interest calculation is correct, but the premise is wrong. > The greater point of the excersise is to show a failure mode of an inductive proof. I see that, but the fact that the other steps are not contributing to the solution makes it harder to argue that the mistake is there. Because that statement needs a qualifier, but it is "not wrong" per se (it's not even affirming anything, it's just saying "pick the person you haven't picked (from a group that might not have anyone else to pick, fair enough) But everything derived from a false premise can be false. That's how we get the proofs by contradiction, right? We keep going down the wrong path until it obviously blows up Or we could just prove this whole problem false with a set of two people in Canada with different ages (counterexample to Step 5). Case closed.
  - tsimionescu 6y ago
    > It's like saying "Person P had 1Mi dollars and got 10% interest last year then now Person P has 1100k dollars". But Person P didn't. The interest calculation is correct, but the premise is wrong. No it is not like that. It is like saying "IF person P had 1Mi dollars and got 10% interest last year THEN now Person P would have 1100k dollars". This statement is true regardless of how much money person P has today. That is how steps 5-8 work: they are true regardless of the truth of the antecedent ('in every group of k people, everyone has the same age'). Finding 2 people in Canada of the same age would NOT prove step 5 wrong (though it would show it to be pointless, of course). Probably a much more interesting problem would have found a less obviously wrong premise to demonstrate this with. I'd love to find a way to build a similar argument for Fermat's last theorem or some other non-trivial observation.