How to formulate an induction principle for the set of all integers?

Question

I am getting introduced to mathematical induction, and I am trying to formulate induction principles for various domains. I have been asked to "give an induction principle for the integers." As an example, the standard (weak) induction principle for the natural numbers is:

"If 0 is P and, if a natural number n is P, then its successor (i.e. n+1) is also P, then all natural numbers are P."

I'm uncertain about this one because there's not an obvious base case for the integers (since minus infinity is not a number, we can't let that be the base case). My intuition is telling me that the solution will require a strong principle of induction to get around there not being an identifiable smallest element. Can anyone help?

Answer 1

There are many possible approaches for proving a statement about the integers using induction. A straightforward approach is to run the induction twice: once for the positive integers, and once for the negative integers.

Suppose that $P[x]$ is some statement about the number $x$. To prove that $P[n]$ is a true statement for all integers $n$,

1. prove that $P[n_0]$ is true for some fixed integer $n_0$ (it might be easiest to take $n_0 = 0$, but the actual value of $n_0$ is irrelevant—you just need some base case);
2. prove that if $P[n]$ is true for some integer $n$, then $P[n+1]$ must also be true; and
3. prove that if $P[n]$ is true for some integer $n$, then $P[n-1]$ must also be true.

If you take $n_0 = 0$, then step (2) amounts to showing that $P[n]$ holds for all positive integers $n$, and step (3) amounts to showing that $P[n]$ holds for all negative integers $n$.

Unfortunately, there isn't really an easier way of applying induction to the integers—any approach is essentially going to have to consist of these three steps, or something which is entirely equivalent. The difficulty (in this case) is that the natural numbers are well ordered, while the integers are not. If one wants to prove a statement about the naturals using induction, there is a smallest natural number which can be taken as the base case. In the integers, there is no smallest integer, hence the induction has to be done in "both directions" (the positive direction and the negative direction).

Answer 2

I think the way to do it is to use $0$ as the base case and prove that the statement is true for $n+1$ if and only if it is true for $n$. This would prove all positive integers. It would also prove it for all negative integers since $0$ implies $-1$ implies $-2$...

The fact that this form of induction works can be verified by normal induction. Here is the proof that the statement holds for all nonpositive integers:

For the given statement S, convert it to a statement S' that holds for $n$ if and only if S holds for $-n$.

Base case: Since S is true for $0$, S' is true for $0$.

Inductive step: Since S is true for $-n$ if it is true for $1-n$, S' is true for $n$ if it is true for $n-1$. Thus proved.

There are other ways of defining induction on the integers, like choosing a bijection between $\mathbb{Z}$ and $\mathbb{N}$. Here are two ways that are less useful than the previous way, but are still useful given a base case.

• S$(-n)$ is true if S$(n)$ is true and $n$ is positive, and S$(-n+1)$ is true if S$(n)$ is true and $n$ is negative.
• S$(n+1)$ and S$(-n)$ are true if S$(n)$ is true and $n$ is positive.

The first method works by using a bijection, and the second method works by proving it for positive integers and using that to prove it for negative integers.

Answer 3

A useless answer: Assume that you want to show that a proposition $P(k)$ is true for every integer $k$.

1. Chose any bijection $\varphi: \mathbb N\to \mathbb Z$ and define $Q(n)=P(\varphi(n))$ for every $n$ in $\mathbb N$.
2. Prove that $Q(n)$ is true for every $n$ in $\mathbb N$ by (standard) mathematical induction.

Since $\varphi$ is surjective, $P(k)$ is true for every $k$ in $\mathbb Z$.