Wednesday, June 5, 2013

Simple and full induction

A followup on the previous post.

Simple induction: F1 is G, F2 is G, ..., Fn is G, so probably: Fn+1 is G.

Full induction: F1 is G, F2 is G, ..., Fn is G, so probably: Fk is G for all k.

Intuitively, simple induction seems to be always the better inference than full induction. Indeed, in cases where there are rare exceptions that didn't occur for Fk where kn, simple induction typically gives the right answer but full induction gives the wrong answer. Moreover, the conclusion of the full induction is logically stronger (modulo the existence of Fn+1), so it seems clear that simple induction is the better inference.

But no! Let's say that I, Jon and Trent (and a number of others!) entered a raffle held for a charity where there is only one prize. That Jon and Trent didn't win is some weak evidence that nobody won the raffle—namely, that the charity raffle was crooked. So we do have some evidence for the full inductive conclusion. But that Jon and Trent didn't win is also some evidence that I won. This is true even if we admit the possibility that nobody won, as long as we insist that it is certain that there is only one prize, and hence at most one person won. For P(Jon and Trent didn't win | I won) = 1, but P(Jon and Trent didn't win | I didn't win) < 1, and so that they didn't win supports that I won.

On Bayesian grounds, if the existence of all the Fk is in the background, that F1 is G, F2 is G, ..., Fn is G will never be evidence against that all the Fk are G, and in contingent regular cases will be evidence for the universal claim. But it could well be evidence against that Fn+1 is G.

No comments: