SI242: What makes the integers different? Induction!

Not all ring can be ordered!

there is no "<" relation for the boolean ring that satisfies the axioms of an ordered ring.

Assume (by way of contradiction) that "<" is a relation that satisifies the order axioms for the boolean ring.

1: 0 < 1 [] 2: 0 + 1 < 1 + 1 [Axiom (iv) of ordering axioms applied to line 1 (adding 1 to both sides)] 3: 1 < 1 + 1 [Additive identity on line 2] 4: 1 < 0 [-1 = 1 in the boolean ring]

Lines 1 and 4 both being true contradicts the Trichotemy Law (), so our assumption that there is a "<" for the boolean ring is false.

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 axiom
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

that is non-trivial,
where multiplication is commutative,
with a total ordering, and
in which the induction property holds

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$. The predicate $P(\cdot)$ we are trying to prove is: $$ \underbrace{x \lt 1 \Rightarrow x = 0}_{P(x)} $$

Base case, prove $P(0)$. $P(0)$ is $$0 \lt 1 \Rightarrow 0 = 0$$ which holds because the left-hand side is true by and the right-hand side is true by the reflexivity of equality.
Inductive case, prove $P(x) \Rightarrow P(x+1)$, i.e. prove: $ \left( x \lt 1 \Rightarrow x = 0\right) \Rightarrow \left((x+1) \lt 1 \Rightarrow (x+1) = 0\right) $
We will split this up into the two cases $x < 1$ and $\neg(x < 1)$.
1: x < 1 => x = 0 [Assumption A] CASE x < 1: 3: x = 0 [Modus ponens with 1 and the fact that we are case x < 1] 4: x + 1 = 1 [subst into 0+1 = 0+1 using line 3, and additive identity] 5: ~(x + 1 < 1) [Ordered ring axiom i] 6: ~(x + 1 < 1) | x + 1 = 0 [Or introduction] 7: x + 1 < 1 => x + 1 = 0 [Implication rewriting] CASE ~(x < 1) 10: x = 1 | 1 < x [Total order axiom, then implication rewrite ~(x < 1) => (x = 1 | 1 < x), Modus ponens] 11: 0 < 1 [] 12: x = 1 => 0 < x [Assume x = 1, subst of equal into 11 to deduce 0 < x, close assumption] 13: 1 < x => 0 < x [Assume 1 < x, transivity axiom with 11 to deduce 0 < x, close assumption] 14: (x = 1 | 1 < x) => 0 < x [(A => C) & (B => C) => (A|B => C) is a tautology] 15: 0 < x [Modus ponens on 14 and 10] 16: 1 < x + 1 [By axiom (iv) of ring order we can add 1 to both sides] 17: ~(x + 1 < 1) [Assume x+1 < 1 then by transitivity with 16, 1 < 1 which is a contradiction] 18: ~(x + 1 < 1) | x + 1 = 0 [Or introduction on 1] 19: x + 1 < 1 => x + 1 = 0 [Implication rewriting]
So closing assumption A gives $ \left( x \lt 1 \Rightarrow x = 0\right) \Rightarrow \left((x+1) \lt 1 \Rightarrow (x+1) = 0\right)$ since $\left((x+1) \lt 1 \Rightarrow (x+1) = 0\right)$ holds in both cases.

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 (a note for the interested)

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

Christopher W Brown

News flash: $0 \lt 1$!

Not all ring can be ordered!

What makes the integers different?

Induction!

Consequences of induction - mind the gap

Our more familiar kind of induction - Strong induction (a note for the interested)