Hacker News Reader

Hacker News

Comment by coldtea | Hacker News Reader

Parent Full thread

coldtea

Isn't it Step 4, which uses as a premise what the whole thing is supposed to prove?

"in every group of k people, everyone has the same age"

You can't use your conclusion in your assumption!

View on HN

Please take a look at the principle of induction that is explained on that page.

In short: You fix k and assume that S(k) holds. If you can show that this always implies that S(k+1) holds, all you need is a base case (e.g. S(1) being true) to "recursively" prove that S(n) holds for all n >= 1 (or whatever your base case was).

Here the fault is that the induction step (proving S(k+1) from S(k)) requires k >= 2 but only specifically S(1) was proven.

That's the way induction works. Assume the statement is true for n Deduce that it then must be true for n+1 Prove it for n=1 Now it's proven for every n

No, not quite, the conclusion is that given a group of k people where all people have the same age, then a group of k+1 people also must have the same age. Since we know that in a group of 1 all k people have the same age, then if the proof held then a group of 2 people would have the same as well, then 3, etc. This is a common tactic in induction, you make an assumption, prove that if true it implies a general result, and then give an explicit case where the assumption holds, proving the general result.

You're right if we were speaking normal English, but "assuming" doesn't mean the same thing in math jargon. In math, you would say, "Assuming A, then B", to mean, "If A is true, then B is true."

It's way more confusing than simply "If A, then B", and I'm not sure why the wording hasn't fallen out of favor, but that's what it is.

In what way is that different from 'normal English'?

You might want to read the section "A Brief Review of the Principle of Induction".

This is easier to understand in constructive type theory. You can't pattern match on `k` to recur, but you can pattern match on `succ(k)` to recur on `k`.

Even when doing classic logic, I start with my constructive intuition and the sprinkle in the continuation-passing-style spooky magic when needed to get back the classical craziness.

Everyone should learn constructive first.

Reply on news.ycombinator.com