What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for granted as a proof rule, or can it be derived from more foundational axioms?
Similarly, can the principle of induction over well-founded sets be derived from something more foundational, or does it have to be assumed to be a valid inference rule?
Best Answer
One point of view is that "the natural numbers satisfy induction" is part of what we mean when we're talking about the natural numbers; that is, part of the definition of "the natural numbers" should be "those things that satisfy induction." This is just a slightly more sophisticated version of "the natural numbers are what you get when you start with $1$, then add $1$ to it, then add $1$ to it, then..."
If someone tells you that badgers are white, 200 feet tall, and glow in the dark, they're not even wrong about badgers: whatever they mean by badger, it isn't what you mean by badger. Similarly, if someone tells you that the natural numbers don't satisfy induction and also include $-3$ and $\frac{5}{7}$, then they're not even wrong about the natural numbers: whatever they mean by natural number, it isn't what you mean by natural number.
People think of axioms as laws you have to follow or true things you have to assume and I think neither of these perspectives is correct. It's more accurate to think of axioms as a way to agree that we're talking about the same thing.