Hacker News new | past | comments | ask | show | jobs | submit login

It's simpler than that -- the "proof" of the inductive step is just incorrect. It wouldn't be a theorem in a sound logical system.



Potentially. However, I believe the inductive step is correct. I could be wrong though.

ie. If you assume S(2) is true, lets prove S(3), consider a set of 3 people, {a, b, c}.

apply S(2) to {a, b} are therefore the same age, apply S(2)_ to {b, c} are therefore the same age, this implies a.age == b.age == c.age, there for S(3) is true. The inductive step is done.

Thats what I thought made this a mind bender.


Right, it proves S(2)->S(3), but induction asks you to prove S(n)->S(n+1) for n in general, and not just for some n. The inductive proof doesn't work for S(1)->S(2), so it clearly can't work for the more general n->n+1.


The inductive step is fine, but it only works for n >= 2. The issue is a disconnect with the base case n = 1.

However, if it were possible to prove the case n = 2, we would have a valid inductive proof for n >= 2.


> it only works for n >= 2

Right, so it doesn't work -- either it's a correct proof of a non-sequitur ("true for n implies true for n+1, provided n meets some criteria"), or an incorrect proof of an inductive step ("true for n implies true for n+1").

Because it's claimed to be proof by induction, it's meant to be the latter -- the person doing the proving claimed to have proven the inductive step, and their proof of it was incorrect.


“True for n implies true for n+1, provided n >= 2” is a perfectly good inductive step.

However, it must be coupled with a base case >= 2, which isn’t the case here. The only base case proven is 1.

See also “Induction basis other than 0 or 1” [0].

[0] https://en.wikipedia.org/wiki/Mathematical_induction#Inducti...


Sure, their mistaken proof of the n->n+1 implication could be taken for what it does prove, and such a theorem could be used in other circumstances to prove different things, but that doesn't really bear on any of the claims in the original context.

Nobody was trying or claiming to be doing any other kind of induction. They said they had the base case and the inductive step, and they were clear about the base case and the inductive step. Their proof of the base case was correct, and their proof of the inductive step did not prove what they said it did. It doesn't matter what it did prove.


I think a better characterization of the fallacy is that it is indeed a non-sequitur, but it hides the "provided n meets some criteria" by bamboozling you with "arbitrarily chosen" elements from a set of n+1 so that you might fail to spot where you need 3 elements in a set that potentially has a cardinality of 2.


I believe so yeh.


> Thats what I thought made this a mind bender.

I don't know if I'd call it a mind bender, but it does demonstrate that if one holds that all groupings of two individuals must be uniform with regard to an attribute A, then it follows that any grouping of individuals must be uniform with regard to A.

A simple proof by contradiction:

1) Assume some group of more than 2 individuals is not uniform with regard to A

2) There must be at least one pair of individuals for which attribute A differs

3) Create a subgrouping of one of those pairs

4) Now we have a grouping of 2 individuals which is non-uniform with regard to A

5) But we originally held that all groupings of 2 individuals must be uniform with regard to A

6) Contradiction! Hence a non-uniform grouping with regard to A is impossible, Q.E.D.


What cf-d-ycom wrote is a perfectly accurate description, it seems to me.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: