What makes the integers different?

We've looked at rings, i.e. number systems in which we can "do" arithmetic. We've looked at non-trivial rings, i.e. rings that actually contain a non-zero element. And we've looked at rings with total orders, i.e. rings with a "<" operator that is compatible with $+$ and $*$ in the ring. Some properties, like $x*0=0$ are consequences simply of being a ring. Some properties, like $0 \neq 1$ are consequences of being a non-trivial ring. Some properties, like $0 \lt x \Rightarrow -x \lt 0$, are properties of being a ring with a total order.

Ultimately, though, I want you to understand the integers better, and the integers aren't the only non-trivial rings with total orders. In fact, both the rational numbers and real numbers fall into this category. So what makes the integers different? From our experience, one thing that differentiates the integers from rationals and reals is that there is no integer between 0 and 1 ... while there are infinitely many rational and real numbers between 0 and 1. And of course this isn't just about 0 and 1. There is a gap between each successive integer, and that's different ... so we need a new axiom that that accounts for those kinds of differences between the integers and other non-trivial totally ordered rings.

Induction!

It turns out that what's different about the integers is that induction works. Below is the axiom that induction holds. It looks a little be different than what we covered before. That was called strong induction, and this is weak induction. They are actually equivalent. This version is appropriate for introducing as an axiom (it's simpler to state), the other version is what we will have in mind when we prove things (it's simpler to use).
    induction
  1. Given a non-trivial ring with a total oder, the (weak) induction property is: If $P(\cdot)$ is a predicate on the ring and
    • $P(0)$, and
    • for all non-negative $n$, $P(n) \Rightarrow P(n+1)$
    then $P(n)$ holds for all for all non-negative $n$.
Notice that induction only really deals directly with non-negative numbers (i.e. with $\mathbb{N}$ rather than $\mathbb{Z}$). That's fine, since the negative numbers are just the additive inverses of the positive numbers. So we can study negatives by studying positives.

A ring is called the integers.
Although we won't prove it here, there is only one ring with all these properties. So what we think of as "the integers" is unique.

Consequences of induction - mind the gap

We noted before that one way the integers are different than rationals and reals is that there is nothing in between 0 and 1. Let's see if the induction property allows us to prove that!

(Gap theorem) For any non-negative integer $x$, $x \lt 1 \Rightarrow x = 0$.
Note: Read this as "the only non-negative integer less than 1 is 0.
We prove this by induction on $x$. When $x=0$, both the left and right sides of $x \lt 1 \Rightarrow x = 0$ are true, so the implication is satisfied. We assume (inductive hypothesis) that $x \lt 1 \Rightarrow x = 0$ holds, and we will prove: \begin{equation} (x+1) \lt 1 \Rightarrow (x+1) = 0\ \ \ \ \ \ (*) \end{equation} If $x \lt 1$ then the inductive hypothesis tells us that $x=0$, so $(*)$ is $1 \lt 1 \Rightarrow 1 = 0$, which is true because the left-hand side is false.
If $x \nless 1$, then either $x = 1$ or $1 \lt x$. In either case, $0 \lt x$ so $1 \lt x+1$, which means $(*)$ holds because the left-hand side is false.
Closing the assumption, we get $ \left(x \lt 1 \Rightarrow x = 0\right) \Rightarrow \left( (x+1) \lt 1 \Rightarrow (x+1) = 0 \right) $. So we deduce the theorem holds for all non-negative $x$.

As a direct result of this, we get the following:

(Gaps everywhere) For any integers $x$ and $k$, if $x \lt k$, then $x = k-1$ or $x \lt k-1$.
Assume $x \lt k$. Suppose by way of contradiction $x = k-1$ or $x \lt k-1$ is false. Then $k-1 \lt x$. Let $d = -(k-1)$, and add $d$ to both sides of both $k-1 \lt x$ and the assumption $x \lt k$. We get $0 \lt x-d$ and $x-d \lt 1$. But this contradicts the Gap theorem. So $x = k-1$ or $x \lt k-1$.

Note: The above proof makes an interesting step. It says:
Suppose by way of contradiction $x = k-1$ or $x \lt k-1$ is false. Then $k-1 \lt x$.
Can you show why $x = k-1$ or $x \lt k-1$ being false implies $k-1 \lt x$?

Our more familiar kind of induction - Strong induction

I realize the previous inductive proof looks a little bit different than what we are used to. From now on, we will return to what we are used to, as I think it is easier to use. It is in fact equivalent to the induction property above. If you want to know why, I offer the discussion below.

First of all the above inductive proof uses "weak induction" rather than "strong induction", and second it goes from $n$ to $n+1$ instead from $\lt n$ to $n$. To contrast, if $P$ is the predicate we are trying to show holds for all $\mathbb{N}$:
weak induction: with $n \geq 0$, assume $P(n)$, then show $P(n+1)$
strong induction: with $n > 0$, assume $P(k)$ for all $0 \leq k \lt n$, then show $P(n)$
The differences are less than you might think since, thanks to the "Gaps everywhere" theorem, $k \lt n$ is the same as $k \leq n-1$. So if we let $n' = n-1$ and rewrite to highlight simliarities:
weak induction: with $n \geq 0$, assume $P(k)$ for $0\leq k=n$, then show $P(n+1)$
strong induction: with $n' \geq 0$, assume $P(k)$ for all $0 \leq k \leq n'$, then show $P(n'+1)$
Finally, if we make a new predicate $Q$ such that $Q(m) \Leftrightarrow \forall k[ 0\leq k \leq m \Rightarrow P(k)]$ then we have:
weak induction: with $n \geq 0$, assume $P(k)$ for $0\leq k=n$, then show $P(n+1)$
strong induction: with $n' \geq 0$, assume $Q(k)$ for $0\leq k=n'$, then show $Q(n'+1)$

Consequences of induction - another link in the chain

Let's use our familiar strong induction to prove another property of the integers, namely that for any positive $k$, $k$ is the same as $k$ copies of 1 all added together. We'll actually prove this for any non-negative $k$, or (equivalently), for any $k \in \mathbb{N}$.

(Generating Positive Integers) Every non-negative integer $k$ is equal to the sum of 0 and $k$ ones - i.e. $0 \underbrace{+ 1 + 1 + \cdots + 1}_{k \text{ copies of } +1}$.
We proceed by induction on $k$. If $k=0$ then $k$ is 0 plus zero 1s. If $k>0$, then $k-1$ greater than or equal to zero by the Gap Theorem, and $k-1 \lt k$, so by the inductive hypothesis, $k-1$ is equal to $0$ plus $k-1$ 1s. So we get $$ k-1 + 1 = \underbrace{0+1+\cdots+1}_{=k-1\text{ by inductive hyp.}}+1 = k $$ and deduce that every non-negative integer $k$ can be written this way.

So we have proved that all positive integers are generated from zero by adding 1s, and of course all negative integers are generated from zero by adding -1s (can you prove that?). Notice that the Generating Positive Integers theorem also tells us that if you keep subtracting 1 (adding -1) from a positive number you eventually arrive at zero!
Christopher W Brown