2

I’m not sure if this is a redundant question.

How does one prove that induction works? Is it axiomatic? Do we simply assume that applying the theory mathematical induction “works”?

I understand how induction is used to solve problems, but I’m not sure what a proof that the process of induction “works” would even look like.

(I mean “works” in the sense that coming up with the inductive hypothesis, doing the inductive step, etc. means that a statement is true for all natural numbers.)

Ethan
  • 372
  • 1
    It is logic. If I know a statement is true for a certain value, and I show that for any arbitrary value, the statement holds for that value plus 1, the statement must hold for ALL values after a given value where the statement is proven true (this is the importance of the base step) – Alborz Nov 15 '22 at 02:52
  • 2
    Someone else may be able to provide a more detailed answer (or a MSE link to one), but the short answer is that there is an "axiom of induction" in the Peano axioms of the natural numbers. It says that if $A$ is a set of natural numbers containing $0$ such that $n \in A \implies n+1 \in A$, then $A = \mathbb N$. – Ethan Martin Nov 15 '22 at 02:53
  • 2
    @Alborz Why is that logic? Why should we know we are going to get every possible number simply by taking a base case and successively taking it for every successor. How do we know there aren't natural numbers between one value and the value plus 1. How do we know there aren't natural numbers that are larger than all successors and are never met. Or how do we know there aren't some numbers that are "parellel" to the successors and a never satisfied. I feel like you are begging the question and missing the OPs point. – fleablood Nov 15 '22 at 05:14
  • 1
    It depends on your construction of the natural numbers but it is either axiomatic, by definition, or a provable by axiom that is equivalent to it. Intuitively the whole point of the natural numbers is that you can count them and that if you start at the beginning and keep going, any number that can exist will eventually be counted. Any construction will somehow incorporate that (although exactly how thye formalize it can be ingenious). And that's essentially induction. If a property always applies to a successor, it applies to any as we can eventually count to it. – fleablood Nov 15 '22 at 05:20

1 Answers1

3

In Peano's axioms defining the natural numbers, one of those axioms defines induction. In the axioms, we have established that something labelled $0$ is a natural number, and introduced an operation $S$ such that if $a$ is a natural number, then $Sa$ is also a natural number.

Then in one formulation of the axiom, we say that if $K$ is a set such that:

  1. $0 \in K$

  2. $a \in K \implies Sa \in K$

then $K$ contains all natural numbers.

This looks a little different from the way induction is normally taught, but it will start to feel a bit more familiar when we say that $S$, the "successor" function, essentially adds one to a number, i.e. $Sa = a + 1$. Then if we have a set $K$ that is defined by a predicate $P$, i.e. $K = \{a : P(a)\}$, then notice that applying the axiom of induction to $K$ means that first we have to prove that $0 \in K$, i.e. $P(0)$ is true; then, we have to prove that $a \in K \implies Sa \in K$, or in other words $P(a) \implies P(a + 1)$. Then, having done so, we know that $K$ contains all natural numbers, and so $P(a)$ is true for all natural numbers.

Interestingly, that means that $\mathbb{N}$ is in fact defined by virtue of being the "smallest" set that contains all natural numbers.

ConMan
  • 24,300