Why does the principle of mathematical induction work for integers?

Question

I took a course on the foundations of mathematics a while ago and we went through the construction of the natural numbers and then the integers. We did prove the principle of mathematical induction (PMI) on the natural numbers in the course, through the Peano axioms, but then we also used PMI for some proofs involving non-negative integers. I do see intuitivly why induction also would work on the non-negative integers, because they are exactly the natural numbers, but I cant find a formal argument/ proof for why you can do it when $\mathbb{N}$ and $\mathbb{Z}$ actually are different set-theoretically. I remember my teacher saying something about a canonical inclusion map from $\mathbb{N}$ to $\mathbb{Z}$, which made PMI and some other properties of natural numbers "carry over" to the non-negative integers, but I don't know.

Answer 1

The "canonical inclusion map" from a set $A$ to a set $B$, where $A \subset B$, is the map that takes each element of $A$ to itself, but considered as an element of $B$, i.e. $\iota: A \hookrightarrow B$, $\iota(x) = x$.

Depending on how you've constructed $\mathbb{Z}$, we could also use this notation to represent the mapping of natural numbers to their equivalent object embedded in the integers. For example, if you've created the integers as equivalence classes of pairs of integers, then for $n \in \mathbb{N}$ we can say $\iota(n) = [(n, 0)]$ is the embedding.

In this form, the canonical mapping acts as an isomorphism between the two sets. All of the operations that are defined in both sets are preserved by the mapping, so for example $\iota(m + n) = \iota(m) + \iota(n)$, and $\iota(succ(n)) = succ(\iota(n))$ where $succ$ is the successor operation, and is defined on $\mathbb{Z}$ such that $succ([a, b]) = [succ(a), b]$.

Because of this, the principle of induction also passes through - in other words, if you have a unitary predicate $\varphi$ on integers such that $\varphi(0)$ and $\varphi(n) \implies \varphi(succ(n))$ are both true, then we can translate that to the natural numbers by saying that $P(n) = \varphi(\iota(n))$, and then because we can prove $P(n)$ true for all natural numbers we also have that $\varphi$ is true for all non-negative integers.

Answer 2

I understand your confusion: when it comes to the natural numbers, there is a clear starting point for the induction. But there seems to be no such starting point for the integers.

Well, there are a couple of things we can do. First, we can take $0$ as a starting point after all, but show that besides to 'typical' $P(n) \to P(n+1)$ inductive step to hold, we also show that $P(n) \to P(n-1)$ holds. Thus, you get 2 'domino chains': one from $0$ going up to cover all positive integers, and one from $0$ going down to cover all negative integers, and together all integers are covered.

Another approach is to 'line' up all integers so that it does have a starting point. For example, we can do:

$0,1,-1,2,-2, ...$

So here the inductive base is $0$ again, but instead of showing $P(n) \to P(n+1)$, we show that for every number in this sequence: if that number has property $P$, then the next number in this sequence has property $P$ as well. More formally, for this sequence that would amount to showing that $P(n) \to P(-n)$ for any positive $n$, as well as $P(n) \to P(-n + 1)$ for any non-positive $n$

And there are many other ways to make this work. Indeed, mathematically you can show that induction works whenever you have a binary relation defined over some set of objects such that that relation is well-founded, and there are many ways to define a well-founded relation over a set. Indeed, it is not the nature of the set of objects itself that determines whether induction 'works' or not, but it is the nature of the binary relation as defined over that set. So, as I just demonstrated, given a set alone, you are still free to come up with some binary relation to make induction work. Of course, some will be more useful than others in terms of being able to help you prove the inductive step.