Hacker News Reader

Comment by rp1 | Hacker News Reader

This brings up an interesting problem with inductive arguments I’ve never thought of: how does one prove a base case is a sufficient starting point for induction? In the horse example, we know there can be groups of multi-colored horses so our intuition guides us to a counter example, but it seems like a detail like that could easily be overlooked for something more complicated.

View on HN

You have to find the minimal case where the inductive invariant is valid. In this case when the horses are separated into two groups, A and B, the assumption is that their intersection is non-empty (A ∩ B ≠ ∅). Because only in the case where the intersection is non-empty can we apply transitivity of equality to conclude that their union (A ⋃ B) satisfies what we are trying to prove. But as the article argues this fails for a very simple counter-example where A and B are non-empty but their intersection is empty.

Sorry, this answer is confusing. The base case just needs to have the property you want to prove. The induction step does all of the heavy lifting to go from n to n+1. In this case, the induction step fails, because it cannot go from 1 to 2. Simple as that.

Edit: I removed the wrong. It’s just confusing.

Where exactly is my error?

In your first sentence. What is the inductive invariant you are talking about?

See https://news.ycombinator.com/item?id=29445794.

You explain how the induction step works. That step from n to n + 1 only works for n > 1. But 2 is not a proper base case. 3 is neither. Actually, the only potential base cases are 0 or 1.

So the proper explanation why this argument doesn’t work is that the potential base cases are not covered by the induction step. And not that “the real base case is 2”.

Actually, now that I have explained the argument I realize it has nothing to do with induction. The logic of the argument is unrelated to induction, it's simply about functions that take constant values on some sets and what is required to extend a function to a larger set and conclude that it is constant on the larger set.

Your argument still explains the induction step. In the end, P[n] => P[n+1] is just a statement that has “nothing to do with induction” once it is formed.

You have obviously the right intuition about induction, but I think you are confused about its exact nature.

We'll have to agree to disagree then.

You prove "n+1=>n" instead of "n=>n+1"

I don't think so but we can agree to disagree.

In your induction you start by "Consider a set of n+1 horse" then conclude "By the inductive hypothesis, all of the n remaining horses are the same color".

You did the induction in the wrong direction.

"We can agree to disagree" is not a valid mathematical in my opinion. At least one of us is wrong (and maybe we are both wrong).

Well, in this case, you are wrong ;-)

Any example is a base case that is sufficient for starting an inductive truth, as long as it is covered in your inductive rule.

The actual error is is a logic error in the proof of the inductive rules that takes a logical step that only holds for n>=2 but doesn't acknowledge that condition. If that logical step is done properly and the condition made explicit, it is clear that a base case of n=1 won't prove anything with that inductive rule that only applies to n>=2.

You don't have to. See my top level comment. In short, you have to strengthen your goal in order to have a strong enough inductive hypothesis to prove anything. E.g., instead of "picking a base case" that's sufficient, you work the base case into the goal, like n >= 2 -> P(n). Then you do the base case as part of a branch in the inductive step, without using your inductive hypothesis.

You can't, you just make assumptions with imperfect information. https://plato.stanford.edu/entries/goedel-incompleteness/

Reply on news.ycombinator.com