Hacker News Reader

Hacker News

Comment by thwd | Hacker News Reader

Parent Full thread

thwd

> We will show, by induction, that [for all sets] of n horses, every horse in [each] set has the same color.

> Now [assume that] for all sets of n horses, every horse in [each] set has the same color.

QED.

This is just tautology. No further analysis needed, really.

(If your proof includes your hypothesis as an assumption, then it must be a proof by contradiction.)

EDIT: Before you refute, read again carefully. The assumption _is_ the hypothesis. It is not existentially quantified or set in the base case. It is the entire, universally quantified hypothesis.

View on HN

This is how induction proof work. You prove that something is true for a base (n = 1) case then you prove that if it is true for n it has to be true for n + 1. Therefore it is true for any n.

The flaw is that the second part of the proof requires n >= 2

I understand and agree but read carefully. The assumption _is_ the (entire) hypothesis. It is not existentially quantified or set in the base-case. It is the entire hypothesis.

You should read “n” as “some arbitrary n” in the quote you posted. It’s not an assumption for all n.

edit: sorry, you’re right that the wording is a bit sloppy. The “n” in the first quote is “for all n” and the n in the second quote is “some specific n” or “some arbitrary n”. They’re not meant to be the same statement. I don’t think it’s a very carefully written article.

The assumption that the case holds for n while the goal is to show the case holds for n+1. It is not well worded to make clear the intent of making an assumption about modal possibility. However, to see it as begging the question requires imposing a statement of modal necessity that simply isn't there.

I thought the same thing as you at first, but you need to read more carefully.

The proof is showing that it is true for n=1, and then showing that if it is true for n (the part where we "suppose it is") then it is true for n+1, proving by induction that it is true for all n >= 1.

Yet, that assumption is not needed for the proof and can simply be removed. I think OP just wanted to say "what follows is the proof for the induction step".

Proof by inductions often involve showing that Pn implies Pn+1. That is, that a statement's truth for n implies it's truth for n+1. That's what's being done here, and it's a perfectly valid part of this type of proof.

Reply on news.ycombinator.com