How does one perform induction on integers in both directions?

Question

On a recent assignment, I had a question where I had to prove a certain statement to be true for all $n\in\mathbb{Z}$. The format of my proof looked like this:

• Statement is true when $n=0$
• "Assume statement is true for some $k\in\mathbb{Z}$"
• Statement must be true for $k+1$
• Statement must be true for $k-1$

My professor said the logic is flawed because of my second bullet point above. She says that since mathematical induction relies on the well-ordering principle and since $\mathbb{Z}$ has no least or greatest element, that using induction is invalid.

Instead, she says my argument should be structured like this:

• Statement is true when $n=0$
• "Assume statement is true for some integer $k\geq0$"
• Statement must be true for $k+1$
• "Assume statement is true for some integer $k\leq0$"
• Statement must be true for $k-1$

I am failing to understand where my logic fails and why I need to split the assumptions like she is suggesting. Could someone explain why relying on the well-ordering principle makes the structure of my proof logically unsound?

Answer 1

You are correct. You don't even need to start with $n=0$, you can start at any integer.

To prove that your approach is correct, see that if you have proven your version of the induction step, you have automatically proven your teacher's version of the induction step. This in turn then lets you reach your teacher's conclusion step, which is also your conclusion step.

Your teacher is saying that you need to induct on the positive integers and the negative integers separately. While this is closer to standard (natural number) induction, and also a correct method of proof, it is not necessary.

(Of course, there is the theoretical possibility that there are statements which can only be proven in the direction $k\implies k+1$ for positive $k$ and $k\implies k-1$ for negative $k$, and in those very special cases, your teacher's version of induction will actually lead to a proof, while your induction will fail to reach a conclusion, since you can't get a proof for your induction step. I am not fluent enough in this area of logic to know whether such cases can ever exist, but if they do, then that's a point to your teacher. But if your proof in this particular instance is indeed correct, then I would have no issues calling it a proof by induction.)

Answer 2

If your professor says that induction on the integers is invalid, your professor is wrong.

Induction arguments can be used on any ordered set where the ordering is well-founded. Although it's true that the usual $<$ relation is not well-founded on the integers, we can consider the relation $$a\prec b$$ that means $$|a| < |b|.$$ This relation is well-founded on the integers.

Your induction argument can be put in terms of this well-founded $\prec$ relation: you've shown that if the statement fails for some integer $n$, it must also fail for some integer $m\prec n$. Or, in terms of the usual $<$, if it fails for $n$ it must fail for some $m$ with $|m|<|n|$. Since this process can't repeat forever, it must end at $0$, and since you proved that the statement doesn't fail at $0$, it can't fail anywhere.

Answer 3

You are in fact doing two separate inductions - one upwards and one downwards. Each relies on a well-ordered set with a minimum element and a maximum element respectively.

The union of the two sets is $\mathbb Z$, which has no maximum or minimum element. But you are not doing induction on $\mathbb Z$, rather you are covering $\mathbb Z$ with two sets on which induction is possible.

Answer 4

I think perhaps what your teacher was concerned about how you have phrased your logic: If we write $P(m)$ for the statement for an integer $m\in \mathbb Z$, and you wish to show that $P(m)$ is true for all $m \in \mathbb Z$, then you can show this by establishing the following three statements:

1. P(k) is true for some $k \in\mathbb Z$,
2. if $P(m)$ is true, then $P(m-1)$ is true,
3. if $P(m)$ is true, then $P(m+1)$ is true.

In your final two bullet points, I think your teacher's concern was that you need to make clear that the statement is "$P(k)$ true implies $P(k+1)$ is true", and similarly that "$P(k)$ true implies $P(k-1)$ true".

Given 1,2, and 3 above, then it follows by ordinary induction using $1$ and $3$ that $P(m)$ is true for all $m \geq k$. Similarly using $1$ and $2$, it follows that $P(m)$ is true for all $m \leq k$.

Answer 5

If a poset $P$ is order-isomorphic to $\Bbb N$, then one can perform induction on $P$. Let $\phi: \Bbb N \to P$ be such an isomorphism, then we use $\phi(0)$ as the base case and $\phi(n)\implies\phi(n+1)$ as the inductive step.

It's easy to construct the isomorphisms for both $\Bbb Z_{\geq k}$ and $\Bbb Z_{\leq k}$ so that your version of induction is perfectly valid; just take $n\mapsto n-k$ and $n\mapsto k-n$. Since $\Bbb Z_{\geq k}\cup\Bbb Z_{\leq k} = \Bbb Z$, the result holds for all integers.

Answer 6

I'd say carry on thinking for yourself and ignore the professor.

Your construction is a very trivial and perfectly valid corollary of the one she needs to use twice (once as normally stated and the second time as also a very trivial and perfectly valid corollary of the first).

The remarks concerning the well ordering principle are more misleading than useful.

Answer 7

Any nonempty set $A$ of integers which contains $k+1$ and $k-1$ whenever it contains $k$ is the entire set of integers. So yes, you can do induction over all the integers.

But it's not often done that way. It seems more frequent to:

• Prove the the statement for all nonnegative integers, possibly by induction
• Reduce the negative case to the nonnegative case

For example, I'm teaching discrete mathematics from a textbook that proves the theorem “every integer is either even or odd” this way:

---

Lemma 1: For all integers $n$, if $n$ is even or odd, then $n+1$ is even or odd.

Lemma 2: For all integers $n$, $n$ is even if and only if $|n|$ is even, and $n$ is odd if and only if $|n|$ is odd.

The proofs are left to the reader.

Proposition: All natural numbers are either even or odd.

Proof: By induction on $n$. The base case $n=0$ is apparent by the definition of even. For the inductive case, suppose $k$ is either even or odd. By Lemma 1, $k+1$ is either even or odd. So by induction all natural numbers are either even or odd. QED.

Theorem: All integers are either even or odd.

Proof: Consider an integer $x$. If $x \geq 0$, the proposition already shows that $x$ is either even or odd. If $x < 0$, the proposition shows that $|x|$ is either even or odd. By Lemma 2, $x$ is either even or odd. QED

---

To me, this is more readable than going forwards and backwards at the same time. When people read a lot of induction proofs, they expect them to follow an idiomatic pattern, and this follows that pattern. Also, reducing the negative case to a nonnegative one is a pretty standard trick.

Answer 8

Let's look at induction on the natural numbers. You can prove $P(k)$ for any $k \in \mathbb{N}$ if you can prove:

1. $P(0)$ is true
2. For all $n \ge 0$, $P(n) \rightarrow $P(n+1)$.

This works works, intuitively, because a proof of $P(k)$ either follows directly from (1) if $k = 0$, or indirectly from (2) if $k > 0$. (That is, the proof of $P(k)$ follows from the proof of $P(k-1)$ which follows from the proof of $P(k-2)$, ..., which follows from the proof of $P(1)$, which follows from the proof of $P(0)$, which is already established.

For integers, though, you have stated that you can prove $P(k)$ for any $k \in \mathbb{Z}$ if you can prove

1. $P(0)$ is true
2. There exists $n \in \mathbb{Z}$ for which $P(k)$ is true
3. For all $k \in \mathbb{Z}$, $P(k) \rightarrow P(k+1)$
4. For all $k \in \mathbb{Z}$, $P(k) \rightarrow P(k-1)$

Now, how do we prove $P(57)$? Do we prove $P(56)$ is true, or do we prove $P(58)$ is true? Either one seems sufficient, but one either leads to a circular argument or spirals off towards infinity. The problem is that nothing forces you to reduce your proof of $P(k)$ to the established proof that $P(0)$ is true. That's because you haven't explicitly tied your argument that induction works for integers to a well-ordering of the integers. That's easy to fix, though. It turns out that (2) is insufficient; not just any assumption will work. It also turns out that (3) and (4) are overly broad. You don't need to assume (3) holds for all integers, only the positive integers. Likewise, (4) need only hold for the negative integers.

So we can reformulate our inductive principle over the integers to

1. $P(0)$ is true
2. For all $k \ge 0 \in \mathbb{Z}$, $P(k) \rightarrow P(k+1)$
3. For all $k \le 0 \in \mathbb{Z}$, $P(k) \rightarrow P(k-1)$

(Note that in the case of positive integers, this reduces exactly to induction over natural numbers.)

Now, our proof that $P(57)$ is true necessarily follows from a proof that $P(56)$ is true and (2), while a proof that $P(-57)$ is true follows from $P(-55)$ and (3). For any $k \ne 0$, exactly one of (2) or (3) can be used to connect the truth of $P(k)$ to the truth of $P(0)$. We won't, for example, use $P(-58)$ to prove $P(-57)$, because even if we could, it doesn't help us get close to $P(0)$, and it prevents us from immediately turning around and using $P(-57)$ to prove the truth of $P(-58)$.

Answer 9

Here is a (quotient-)inductive definition of the integers whose natural induction principle is the exact induction principle you used. Inlining:

data ℤ : Type where
  zero : ℤ
  suc pre : ℤ -> ℤ
  s-p : ∀ i → suc (pre i) ≡ i
  p-s : ∀ i → pre (suc i) ≡ i
  squash : isSet ℤ

It is the type simultaneously generated by the first three 'constructors' ($\mathsf{zero}$, $\mathsf{suc}$ and $\mathsf{pre}$) and quotiented by the other three rules. So, $ℤ$ is given by the rules:

• $ℤ$ contains a value $\mathsf{zero}$, representing $0$
• If $i$ is a value of $ℤ$, then so is $\mathsf{suc}\ i$, representing $i+1$
• If $i$ is a value of $ℤ$, then so is $\mathsf{pre}\ i$, representing $i-1$
• $\mathsf{suc}\ (\mathsf{pre}\ i) = i$
• $\mathsf{pre}\ (\mathsf{suc}\ i) = i$
• Don't worry about $\mathsf{squash}$

Then, the natural induction principle says that for a predicate $P : ℤ → \mathsf{Prop}$, to prove $∀i. P(i)$ we need to show:

• $P(0)$
• $∀ i. P(i) → P(\mathsf{suc}\ i)$
• $∀ i. P(i) → P(\mathsf{pre}\ i)$

Conditions induced by the equations are automatically satisfied by $P$ being valued in propositions.

In the computation based system I'm using in the linked file, these conditions are not really redundant. The actual members of the type might be represented as $\mathsf{pre}\ (\mathsf{suc}\ \mathsf{zero})$. Even though this value is formally equal to $\mathsf{zero}$, the recursive process witnessing the induction will actually produce $Pp\ (Ps\ Pz)$ as the witness of $P(\mathsf{pre}\ (\mathsf{suc}\ \mathsf{zero}))$, although this is equivalent to $Pz : P(\mathsf{zero})$.

Quotient-inductive definitions like these are a relatively new idea in type theory (the system I'm using, where inductive definitions are bread and butter). But actually, the usual way you'd define $ℤ$ there without quotients would admit almost the same induction. It'd actually be easier because they are more normalized, and you'd only need to show that $P(i) → P(\mathsf{pre}\ i)$ for non-positive $i$, and that $P(i) → P(\mathsf{suc}\ i)$ for non-negative $i$. So I doubt any type theorist in recent memory would quibble about your induction.

Unfortunately, based on questions/answers that crop up here, it seems like the general conception of induction is pretty antiquated in educational environments (at least in my opinion).

Also, I'd take umbrage in the idea that induction is based on the well-ordering principle, because I don't believe in the latter, even for all inductively defined types. It is easy enough to well-order the integers, though.

Answer 10

Your method is valid because

• your bullet points 1, 2, and 3 are a standard induction proof of "$P(n)$ holds for all non-negative integers"
• your bullet points 1, 2, and 4 are a standard induction proof of "$P(-n)$ holds for all non-negative integers"