How foundational is the theory of mathematical induction? 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.)
 A: 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:

*

*$0 \in K$


*$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.
