2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Maybe I'm missing something but isn't one supposed to also proof that if $n-1$ is $P$ then $n$ is $P$? $\endgroup$
    – Hersh
    Commented Oct 6, 2022 at 15:49
  • $\begingroup$ Maybe require two parts for the induction step: if an integer is P, then both its successor and predecessor are P? $\endgroup$
    – JonathanZ
    Commented Oct 6, 2022 at 15:57
  • 4
    $\begingroup$ Is this a fundamental logic question or a practical one? In practice there are some obvious choices such as proving $n \in P \Longleftrightarrow n+1 \in P$ or $n \in P \Longrightarrow n \pm 1 \in P$ or $n \in P \Longrightarrow -n,n+1 \in P$. For the base case you can then take any element, except in the third case $n = 0$ probably works best; otherwise you have to adjust. Or you could also just count off the integers in an arbitrary way... $\endgroup$
    – Klaus
    Commented Oct 6, 2022 at 15:58

3 Answers 3

6
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ It says “all integers”. What about the negative? $\endgroup$ Commented Oct 6, 2022 at 15:51
  • 5
    $\begingroup$ @insipidintegrator Note that the technique here states that $P[n]$ is true if and only if $P[n+1]$ is true. The "if" part is standard induction, while the "only if" part deals with the negative integers. (I just edited the answer to rewrite the abbreviation "iff" as "if and only if"). $\endgroup$
    – Xander Henderson
    Commented Oct 6, 2022 at 16:11
  • 1
    $\begingroup$ Brilliant. That makes total sense. My induction principle, then, will be: If 0 is P and an integer n is P if and only if its successor (i.e. n + 1) is P, then all integers are P. Does that seem right ? $\endgroup$
    – Dan Öz
    Commented Oct 7, 2022 at 9:36
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .