2.1  The Integers as Classes of Pairs

Chapter 1 built the natural numbers as the set $\omega$, with its $0$, $+$, $\cdot$ and $<$, and proved the laws of arithmetic, the order and well-ordering from the axioms for sets. From this chapter on, $\mathbb{N}$ means that set (Corollary 1.7.3 and the citing rule of Section 1.7). In $\mathbb{N}$ the equation $5+x=3$ has no solution: $5\le 5+x$ for every $x\in \mathbb{N}$ by Proposition 1.6.3 (a), while $3<5$ by the same result, as $5=3+2$ with $2\ne 0$. So $5+x=3$ would give $5\le 3<5$, hence $5<5$, which Theorem 1.6.1 (a) rules out. This section builds a larger set $\mathbb{Z}$, out of $\mathbb{N}$ alone, with the one tool of Sets, Relations, and Cardinality, Section 2.5: the quotient of a set by an equivalence relation.

2.1.1. What we use about the natural numbers

Every fact about $\mathbb{N}$ in this section and the next is one of the following results of Chapter 1, and each is cited where a proof uses it. The defining equation $n+0=n$ and the evaluation of numeral sums and comparisons such as $2+3=5$ and $0\ne 2$ rest on Definition 1.5.1 and Theorem 1.6.1 and are not cited each time.

• Defining equations (Definition 1.5.1): $n+0=n$, $m+\mathrm{S}(n)=\mathrm{S}(m+n)$ and $n\cdot 0=0$, and the numerals $0:=\mathrm{\varnothing }$, $1$, $2$, …, with $n+1=\mathrm{S}(n)$.
• Laws of arithmetic (Theorem 1.5.3): $+$ and $\cdot$ are commutative and associative, $\cdot$ distributes over $+$, and $0+n=n$, $1\cdot n=n$, $0\cdot n=0$.
• Cancellation (Proposition 1.6.3 (b), (f)): $m+k=n+k$ gives $m=n$; and $mk=nk$ with $k\ne 0$ gives $m=n$.
• Order (Theorem 1.6.1 (a)): $<$ is a strict total order, so for all $m,n$ exactly one of $m<n$, $m=n$, $n<m$ holds, and $<$ is transitive and irreflexive.
• Order and addition (Proposition 1.6.3 (a)): $m\le n$ if and only if $n=m+j$ for some $j\in \mathbb{N}$; and $m<n$ if and only if $n=m+j$ for some $j\ne 0$. Adding preserves $<$ (Proposition 1.6.3 (c)).
• Small facts and well-ordering: $0<1$ (Theorem 1.6.1 (d)); no $k$ satisfies $n<k<\mathrm{S}(n)$ (Theorem 1.6.1 (b)); every non-empty subset of $\mathbb{N}$ has a least element (Theorem 1.6.2).

That is the whole list for now. Nothing about the integers or the rationals of school enters a proof: from here on they are the sets this chapter builds, and their familiar properties become theorems.

2.1.2. A naive attempt

The school picture of an integer is “a natural number with a sign”: $+3$, $-2$, $0$. It is tempting to take that literally and let an integer be a pair $(s,n)$ with a sign $s\in \{0,1\}$ (read $0$ as “plus” and $1$ as “minus”) and a size $n\in \mathbb{N}$. Two things go wrong at once.

First, zero gets two names, $(0,0)$ and $(1,0)$: a “plus zero” and a “minus zero”. Either both stay, and every theorem must treat them as the same, or one is banned, and every definition must check that it never produces the banned one.

Second, addition needs cases. Adding $+m$ and $-n$ should give $+(m-n)$ when $n\le m$ and $-(n-m)$ when $m<n$, where $m-n$ is the subtraction of Proposition 1.6.3 (a), defined on $\mathbb{N}$ only when $n\le m$. There are four sign patterns for a sum, and two of them split again by the order of the sizes. A proof that addition is associative would split by the signs of all three terms and then by the order of their sizes, and every case would subtract in $\mathbb{N}$ in its own direction.

The trouble in both is the same: the definition performs a subtraction that $\mathbb{N}$ can only do one way round. The construction below never performs it. It records the subtraction as a pair, and lets an equivalence relation decide when two recorded subtractions should count as equal.

2.1.3. Pairs that record a difference

Think of a pair $(a,b)\in \mathbb{N}\times \mathbb{N}$ as a note saying “$a$ minus $b$”, to be computed later or never. The note $(3,5)$ is legitimate even though $3-5$ is not a natural number. Many notes say the same thing: $(3,5)$, $(0,2)$ and $(10,12)$ all describe “two less than nothing”, which school calls $-2$.

When do two notes $(a,b)$ and $(c,d)$ describe the same thing? School would write $a-b=c-d$, and then add $b+d$ to both sides to get $a+d=b+c$. That last equation is the one we keep, because it uses only addition, which $\mathbb{N}$ has for all inputs. The computation with minus signs is a heuristic, borrowed from school to find the definition; the definition does not depend on it.

An integer is a difference you have not computed yet.

In words: two pairs are related when their cross sums agree, the first coordinate of each added to the second coordinate of the other. The relation is a subset of $(\mathbb{N}\times \mathbb{N})\times (\mathbb{N}\times \mathbb{N})$, described by a property (Sets, Relations, and Cardinality, Definition 1.3.3, Sets, Relations, and Cardinality, Definition 1.3.2). An integer is one whole class: the set of all pairs that record the same difference. The notation $[(a,b)]$ is the class notation $[x]$ of Sets, Relations, and Cardinality, Definition 2.5.2 with $x=(a,b)$; no new bracket is introduced.

Well-definedness. Sets, Relations, and Cardinality, Definition 2.5.4 is stated for an equivalence relation. Until $\sim$ is shown to be one, the definition of $\mathbb{Z}$ is a plan, not a definition. The next proposition supplies the missing check, and it is placed directly after the definition for that reason.

An integer is a set of pairs. It is not a natural number with a sign, and it is not a pair. Sets, Relations, and Cardinality, Chapter 1 adopted the convention that a pair is not a number (after Sets, Relations, and Cardinality, Definition 1.3.1), and on $\omega$ that became a theorem, Proposition 1.4.3. The same care is needed here: $[(0,2)]$ is the set $\{(0,2),(1,3),(2,4),\dots \}$, and the school $-2$ is what those pairs have in common. The construction takes “what they have in common” to be the set of them.

The answer to the prompt is the last line of (Eq3). It is tempting to “subtract $c+d$ from both sides” at the end. In $\mathbb{N}$ the difference $n-m$ of Proposition 1.6.3 (a) exists only when $m\le n$. Here it does exist, since $c+d\le (a+f)+(c+d)$ and $c+d\le (b+e)+(c+d)$ by the same result and commutativity, but only after that check; and reading off $((a+f)+(c+d))-(c+d)=a+f$ uses the uniqueness in (a), which is itself proved by cancellation. Cancellation removes $c+d$ directly, and it holds for all $k$, with no size check.

So $\mathbb{Z}=(\mathbb{N}\times \mathbb{N})/\sim$ is now defined, and by Sets, Relations, and Cardinality, Theorem 2.5.1 its elements partition $\mathbb{N}\times \mathbb{N}$: every pair lies in exactly one integer, and $[(a,b)]=[(c,d)]$ if and only if $a+d=b+c$.

2.1.4. Pictures of classes

The quarter plane $\mathbb{N}\times \mathbb{N}$ is a grid of lattice points, and the classes are easy to see in it.

The picture shows the three classes as three diagonals: $[(3,5)]$ solid with filled dots, $[(0,0)]$ dashed with open dots, $[(4,1)]$ dotted with squares. Every pair lies in exactly one class (Sets, Relations, and Cardinality, Theorem 2.5.1), so no two of these diagonals share a lattice point; after the normal form below we see that every class is a diagonal of this kind, so every lattice point lies on exactly one of them. The class $[(0,0)]$ is the degenerate case: it is the integer zero, and it is the only class whose line passes through the origin.

A non-example by minimal change. Replace the sums in the definition by products: on $\mathbb{N}\times \mathbb{N}$, let $(a,b)\approx (c,d)$ mean $ad=bc$. This is still reflexive ($ab=ba$) and symmetric ($ad=bc$ gives $cb=da$), both by commutativity of $\cdot$ (Theorem 1.5.3 (f)). It is not transitive: $$(1,1)\approx (0,0),(0,0)\approx (2,1),\text{but}(1,1)\not\approx (2,1),$$ since $1\cdot 0=1\cdot 0$, $0\cdot 1=0\cdot 2$ and $1\cdot 1\ne 1\cdot 2$. The clause that fails is (Eq3), and the line of the proof above that has no counterpart is cancellation. Additive cancellation holds for every $k$; multiplicative cancellation (Proposition 1.6.3 (f)) needs $k\ne 0$, and the pair $(0,0)$ supplies a middle factor that is $0$. When Section 2.4 builds fractions with this product relation, it excludes zero second coordinates for exactly this reason.

2.1.5. Why this definition

Why cross sums. “$a-b=c-d$” cannot be the definition, because $a-b$ is defined in $\mathbb{N}$ only when $b\le a$. The cross-sum equation $a+d=b+c$ says the same thing whenever both differences exist, and it makes sense for every two pairs.

Why whole classes. Each class has a simplest pair, one with a coordinate $0$, as the next proposition shows. One could define $\mathbb{Z}$ as the set of these simplest pairs instead. But then the sum of $(3,0)$ and $(0,5)$ would have to be brought back to a simplest pair, $(0,2)$, by a subtraction in $\mathbb{N}$ in the right direction: the case analysis of the naive attempt returns. With classes, any representatives may be combined, and the equivalence relation absorbs the bookkeeping. The price is the check of the next section: a definition through representatives must not depend on which ones were used.

The degenerate class and the name. The class of $(0,0)$ is the diagonal; it will be the zero of $\mathbb{Z}$. The word “integer” is Latin for “whole” or “untouched”, a number not broken into fractions; Section 2.4 builds those.

The first result about the new set says that each class has exactly one simplest name.

So every integer has a normal form: it is $[(n,0)]$ for a unique $n\in \mathbb{N}$, or $[(0,n)]$ for a unique $n\in \mathbb{N}$ with $n\ne 0$. In the picture, every class is a diagonal: $(x,y)\sim (n,0)$ means $x+0=y+n$, that is, $x=y+n$, and $(x,y)\sim (0,n)$ means $x+n=y+0$, that is, $y=x+n$ (Definition 1.5.1 (a)), so $$[(n,0)]=\{(y+n,y):y\in \mathbb{N}\}\text{and}[(0,n)]=\{(x,x+n):x\in \mathbb{N}\}.$$ The normal form is where the class’s diagonal meets an axis. The next section reads $[(n,0)]$ as the natural number $n$ and $[(0,n)]$ as its negative; this is how the description of Sets, Relations, and Cardinality, Section 2.1, “an integer is a natural number or the negative of one”, becomes a theorem about the constructed $\mathbb{Z}$.

The set $\mathbb{Z}$ exists, and each element has a simplest name. It has no arithmetic yet. The next section defines the sum and product of two integers by formulas on representatives, and the warning above is the question it must answer for each formula.

2.1.6. Exercises

A. Check your understanding

B. Practice

C. Going deeper