3.3 Integers from equivalence classes

The natural numbers are not enough for every algebraic problem. A simple equation such as

$$1 = x + 2$$

has no solution in $N$. So if we want subtraction to become possible in a systematic way, we need a larger number system.

A rigorous construction does not introduce negative numbers by intuition alone. Instead, we construct the integers from objects we already understand well, namely pairs of natural numbers.

The new objects must preserve natural-number arithmetic while allowing every subtraction. A pair can record a proposed difference even when that difference is unavailable in $N$; identifying equivalent records will make that proposal into a number.

The guiding idea

A pair $(a,b)$ is meant to represent the formal difference

$$a-b.$$

From that viewpoint, different pairs can represent the same intended integer. For example,

$$(3,1), \quad (5,3), \quad (8,6)$$

all suggest the same difference, namely $2$.

So the integer should not be the ordered pair itself. It should be the whole equivalence class of pairs that encode the same difference.

The relation on $N^2$

Definition 3.3.1

(The equivalence relation for the integers)

Work in the set $N^2$ of ordered pairs of natural numbers.

Define a relation $\sim_Z$ by

$$(a,b) \sim_Z (c,d) \quad \Longleftrightarrow \quad a+d=b+c.$$

The integers are defined to be the equivalence classes of this relation.

The equation $a+d=b+c$ is exactly what we would expect if $(a,b)$ and $(c,d)$ are both meant to represent the same formal difference:

$$a-b=c-d.$$

Indeed, rearranging this equality gives precisely $a+d=b+c$.

This rearrangement motivates the definition; it is not yet a calculation inside the new $Z$. The actual test $a+d=b+c$ uses only addition in $N$, where every term is already defined. The equivalence proof below therefore uses natural-number laws, without assuming the integer subtraction we are constructing.

Why this relation is the right one

Theorem 3.3.2

(The relation really is an equivalence relation)

The relation $\sim_Z$ on $N^2$ is reflexive, symmetric, and transitive, so it is an equivalence relation.

Reflexivity, symmetry, and transitivity ensure that these classes form a quotient set; each step uses only natural-number arithmetic.

Proof: $\sim_Z$ is an equivalence relation

For reflexivity, every pair satisfies

$$a+b=b+a,$$

so $(a,b)\sim_Z(a,b)$.

For symmetry, if $(a,b)\sim_Z(c,d)$, then $a+d=b+c$. The same equality can be read backwards as $c+b=d+a$, so $(c,d)\sim_Z(a,b)$.

For transitivity, suppose

$$(a,b)\sim_Z(c,d) \quad \text{and} \quad (c,d)\sim_Z(e,f).$$

Then

$$a+d=b+c, \qquad c+f=d+e.$$

Adding these equalities and cancelling $c+d$ on both sides gives

$$a+f=b+e,$$

which means $(a,b)\sim_Z(e,f)$.

What an integer now is

Definition 3.3.3

(Integers as quotient classes)

Let $X=N^2$. The set of integers is

$$\mathbf{Z} = X/{\sim_Z}.$$

For a pair $(a,b) \in N^2$, its equivalence class is written

$$[(a,b)] = \{(c,d)\in N^2 : (c,d)\sim_Z(a,b)\}.$$

So an integer is not one pair, but an entire class of equivalent pairs.

This construction explains how the familiar numbers reappear:

• $[(0,0)]$ behaves like $0$;
• $[(1,0)]$ behaves like $1$;
• $[(0,1)]$ behaves like $-1$;
• more generally, $[(n,0)]$ gives the usual natural number $n$.

Embedding the natural numbers

The natural numbers are still present inside the integers. They are not lost; they are reinterpreted.

Worked example 3.3.4

(How $N$ sits inside $Z$)

Define a map from $N$ to $Z$ by

$$n \longmapsto [(n,0)].$$

Under this map,

$$0 \mapsto [(0,0)], \qquad 1 \mapsto [(1,0)], \qquad 2 \mapsto [(2,0)].$$

So the old natural numbers appear inside the new system as particular equivalence classes.

Two distinct steps are involved. Forming $N^2$ supplies records for differences; taking the quotient identifies records intended to describe the same result. The map $n\mapsto[(n,0)]$ is what preserves the old natural numbers. Its injectivity and compatibility with arithmetic will be checked once the new operations have been defined. A quotient alone does not guarantee an embedding.

Natural order from positive differences

The comparison of coordinates uses order in $N$, which can be recovered from the arithmetic already proved. Put $N^+=N\setminus\{0\}$ and define

$$a\lt b\quad\Longleftrightarrow\quad b=a+k\text{ for some }k\in N^+.$$

A sum with a nonzero natural summand is nonzero: write $k=S(k')$, and use $l+k=S(l+k')\ne0$. For any $a,b\in N$, at least one of

$$a=b,\qquad b=a+k\ (k\in N^+),\qquad a=b+k\ (k\in N^+)$$

holds. To prove this, induct on $a$ with a statement about every $b$. For $a=0$, either $b=0$ or $b=0+b$ with $b\in N^+$. For the successor step, $b=0$ gives $b\lt S(a)$. Otherwise the predecessor theorem writes $b=S(c)$. Apply the induction hypothesis to $a,c$. Equality is preserved by $S$, and a positive difference is preserved because $c=a+k$ implies $S(c)=S(a+k)=S(a)+k$; the other direction is identical.

The possibilities are mutually exclusive. Equality together with a positive difference would give $a+0=a+k$, hence $k=0$ by cancellation. Differences in both directions would give $a=a+(k+l)$ and hence $k+l=0$, contradicting the nonzero-sum fact. Thus natural order has trichotomy. Adding positive differences proves transitivity. Adding the same $t$ preserves a difference; conversely, $b+t=(a+t)+k=(a+k)+t$ implies $b=a+k$ by cancellation. These are the natural order properties used to define signs below.

Positive, negative, and zero

The important point is that sign is not attached to one chosen pair, but to the entire class.

• an integer is positive when it has representatives $(a,b)$ with $a\gt b$;
• it is negative when it has representatives with $a$ less than $b$;
• it is zero when it has representatives with $a=b$.

Because these properties must not depend on the chosen representative, one also has to check that sign is well defined on equivalence classes.

Proof: sign is well-defined

Suppose $(a,b)\sim_Z(c,d)$, so $a+d=b+c$. If $a\gt b$, write $a=b+k$ for some positive $k\in N$. Substitution gives $(b+k)+d=b+c$, and natural-number cancellation gives $c=d+k$, so $c\gt d$. Exchanging the coordinates gives the corresponding statement for negative classes; if $a=b$, then the relation gives $c=d$. Thus positivity, negativity, and zero are properties of the class.

Canonical signed representatives

Natural trichotomy also gives a simpler representative of every class. If $a=b$, then $[(a,b)]=[(0,0)]$. If $a=b+k$ with $k\in N^+$, the cross-sum test gives $[(a,b)]=[(k,0)]$; if $b=a+k$, it gives $[(a,b)]=[(0,k)]$. The positive increment $k$ is unique by natural-number cancellation. Hence each nonzero integer has exactly one of these positive or negative canonical forms.

Arithmetic on equivalence classes

To turn the quotient set into a number system, we still need operations. Addition is defined by

$$[(a,b)] + [(c,d)] := [(a+c,b+d)].$$

This definition matches the formal-difference intuition:

$$(a-b)+(c-d)=(a+c)-(b+d).$$

The next step is to check that such definitions are well defined, meaning they do not depend on the representatives chosen.

Proof: integer addition is well-defined

If $(a,b)\sim_Z(a',b')$ and $(c,d)\sim_Z(c',d')$, then

$$a+b'=b+a', \qquad c+d'=d+c'.$$

Adding these equalities and rearranging in $N$ gives

$$(a+c)+(b'+d')=(b+d)+(a'+c').$$

This is exactly $(a+c,b+d)\sim_Z(a'+c',b'+d')$, so the addition formula descends from pairs to integer classes.

Zero, negation, and the subtraction equation

Write $0_Z=[(0,0)]$. The addition formula gives $[(a,b)]+0_Z=[(a,b)]$. Define negation by reversing the coordinates:

$$-[(a,b)]:=[(b,a)].$$

This is independent of representatives. If $a+b'=b+a'$, then the same equality, read in reverse, is $b+a'=a+b'$, so $(b,a)\sim_Z(b',a')$. Moreover,

$$[(a,b)]+[(b,a)]=[(a+b,b+a)]=[(0,0)],$$

where the last equality uses commutativity in $N$. Thus negation supplies an additive inverse, and reversing twice gives $-(-x)=x$.

Define $x-y:=x+(-y)$. Since addition and negation are well-defined, subtraction is well-defined too, and its formula is

$$[(a,b)]-[(c,d)]=[(a+d,b+c)].$$

This recovers the motivating formal rule $(a-b)-(c-d)=(a+d)-(b+c)$ using operations that now exist on classes. For $A=[(a,b)]$ and $B=[(c,d)]$, the class $x=A-B$ satisfies

$$x+B=[(a+d+c,b+c+d)]=[(a,b)]=A.$$

The cross-sum equality in the middle uses only associativity and commutativity in $N$. Every subtraction equation therefore has an integer solution. In particular, the opening equation is solved by $x=[(0,1)]$, since

$$[(0,1)]+[(2,0)]=[(2,1)]=[(1,0)].$$

A concrete class calculation

Worked example 3.3.5

(Recognizing one integer through several representatives)

Consider the class $[(2,5)]$.

Since

$$2+4 = 5+1,$$

we have

$$(2,5)\sim_Z(1,4).$$

Likewise,

$$2+7 = 5+4,$$

so

$$(2,5)\sim_Z(4,7).$$

All of these pairs represent the same integer, namely the one we would usually think of as $-3$.

Explore what a representative can change

Changing a representative changes its coordinates while preserving the cross-sum relation. The class remains fixed even when neither coordinate does.

The important lesson is that equality in $Z$ is not componentwise equality of pairs. It is equality of equivalence classes. Two very different looking pairs can be the same integer if the cross-sum condition $a+d=b+c$ holds.

Multiplication

The formal-difference interpretation suggests how multiplication must combine the coordinates:

$$(a-b)(c-d)=ac+bd-(ad+bc).$$

So the product is defined by

$$[(a,b)]\cdot[(c,d)] := [(ac+bd,ad+bc)].$$

Theorem 3.3.6

(The multiplication formula must be well-defined)

If $(a,b)\sim_Z(a',b')$ and $(c,d)\sim_Z(c',d')$, then

$$(ac+bd,ad+bc)\sim_Z(a'c'+b'd',a'd'+b'c').$$

Therefore the product class does not depend on the representatives chosen.

Proof: integer multiplication is well-defined

Assume the hypotheses

$$a+b'=b+a', \qquad c+d'=d+c'.$$

To prove that the two proposed product representatives are equivalent, the definition of $\sim_Z$ asks us to show

$$(ac+bd)+(a'd'+b'c')=(ad+bc)+(a'c'+b'd').$$

First change only the representative of the first factor. Multiplying $a+b'=b+a'$ by $c$ and by $d$ gives

$$ac+b'c=bc+a'c, \qquad ad+b'd=bd+a'd.$$

Therefore, using only associativity and commutativity of addition in $N$,

$$\begin{aligned} (ac+bd)+(a'd+b'c) &=(ac+b'c)+(bd+a'd)\\ &=(bc+a'c)+(ad+b'd)\\ &=(ad+bc)+(a'c+b'd). \end{aligned}$$

This proves equivalence with the product formed from $(a',b')$ and $(c,d)$. Now keep $(a',b')$ fixed and apply $c+d'=d+c'$, multiplying by $a'$ and $b'$; the same natural-number rearrangement proves equivalence with the product formed from $(c',d')$. Transitivity gives the claimed output equivalence. No subtraction or integer multiplication is used in this proof.

Arithmetic laws inherited from N

The quotient operations inherit their laws from natural-number arithmetic. For example, addition associativity is checked by expanding representatives:

$$([(a,b)]+[(c,d)])+[(e,f)] =[(a+c+e,b+d+f)] =[(a,b)]+([(c,d)]+[(e,f)]).$$

The two displayed representatives are equal by associativity in $N$. The same representative expansion, using commutativity and distributivity in $N$, proves commutativity and associativity of integer addition and multiplication and the distributive laws. This is a transport argument: once well-definedness is known, each natural-number identity can be applied coordinatewise to the formulas on classes.

The canonical embedding also preserves the operations: $[(n,0)]+[(m,0)]=[(n+m,0)]$ and $[(n,0)]\cdot[(m,0)]=[(n\cdot m,0)]$. It is injective because $[(n,0)]=[(m,0)]$ gives $n+0=0+m$, hence $n=m$ in $N$.

The multiplicative identity is $1_Z=[(1,0)]$, since the product formula gives $[(a,b)]\cdot[(1,0)]=[(a,b)]$. The additive identity and inverses proved above give $y-x=0_Z$ if and only if $y=x$: add $x$ to both sides for the forward implication, and use $x+(-x)=0_Z$ for the reverse. Additive inverses are unique: if $x+v=x+w=0_Z$, then $v=v+(x+w)=(v+x)+w=w$. The sum of $x-y$ and $y-x$ is zero, so this uniqueness gives $x-y=-(y-x)$. These identities justify comparisons through differences without appealing to the signed-number notation being constructed.

The order on Z

Define the integer order by

$$x\lt y\quad\Longleftrightarrow\quad y-x\text{ is positive},$$

where $y-x$ means $y+(-x)$. The signed representative result gives trichotomy: for every $x,y$, exactly one of $y-x$ is positive, zero, or negative, so exactly one of $x\lt y$, $x=y$, or $y\lt x$ holds.

The order is transitive. If $x\lt y$ and $y\lt z$, then $y-x$ and $z-y$ are positive. Their sum is positive by the signed representative calculation, and

$$(z-y)+(y-x)=z-x$$

by the already established ring laws; hence $x\lt z$. It is translation invariant because

$$(y+t)-(x+t)=y-x,$$

so $x\lt y$ exactly when $x+t\lt y+t$. Finally, if $0\lt x$ and $0\lt y$, their canonical signed representatives are $[(k,0)]$ and $[(\ell,0)]$ with positive natural $k,\ell$; the multiplication formula gives $[(k\cdot\ell,0)]$, which is positive because positive natural factors have positive product. Thus positive products preserve positivity in $Z$ before the rational construction uses the ordered integer system.

For $t\gt0$, if $x\lt y$, distributivity gives $ty-tx=t(y-x)\gt0$, so $tx\lt ty$. Conversely, if $tx\lt ty$, trichotomy rules out $x=y$ and $y\lt x$ (the latter would give $ty\lt tx$). Therefore multiplication by a positive integer preserves and reflects strict inequalities.

$Z$ has no zero divisors

Two nonzero integers have canonical representatives $[(k,0)]$ or $[(0,k)]$ with $k\in N^+$, as proved above.

The multiplication formula reduces their product to $[(k\cdot\ell,0)]$ when the signs agree and $[(0,k\cdot\ell)]$ when they differ. Since positive natural numbers have nonzero product, the product is not zero. Therefore $x\ne0$ and $y\ne0$ imply $x\cdot y\ne0$ in $Z$. This fact is established here before the construction of $Q$ uses cancellation in $Z$.

Indeed, if $d\ne0$ and $dx=dy$, distributivity gives $d(x-y)=0$. The absence of zero divisors forces $x-y=0$, hence $x=y$. This is multiplicative cancellation in $Z$.

Common mistakes

Common mistake

(The integer is not the pair)

The pair $(a,b)$ is only a representative. The actual integer is the entire equivalence class $[(a,b)]$.

Common mistake

(Different representatives can describe the same number)

Pairs such as $(3,1)$ and $(5,3)$ are not different integers. They belong to the same class because they encode the same difference.

Quick checks

Quick check

(Are $(2,0)$ and $(5,3)$ equivalent under $\sim_Z$?)

Apply the rule $a+d=b+c$ directly.

Solution · Answer

Yes. We compute

$$2+3=0+5,$$

so $(2,0)\sim_Z(5,3)$.

Quick check

(Which class should represent the integer $-1$?)

Use the idea that the pair records a formal difference.

Solution · Answer

The class $[(0,1)]$ represents $-1$, because the formal difference is $0-1$. Any equivalent pair such as $(2,3)$ represents the same integer.

Quick check

(Why do we need equivalence classes instead of just using raw ordered pairs?)

Answer in one careful sentence.

Solution · Answer

We need equivalence classes because many different ordered pairs encode the same formal difference, and the integer must identify all of those representatives as one object.

Exercises

Quick check

(Show that $[(4,1)] = [(7,4)]$, and decide whether the class is positive, negative, or zero.)

Check equivalence first, then interpret the sign from a representative.

Solution · Guided solution

We compute

$$4+4 = 1+7,$$

so $(4,1)\sim_Z(7,4)$, which means

$$[(4,1)] = [(7,4)].$$

Since $4\gt 1$, the class is positive. In ordinary notation, it represents the integer $3$.

Read this first

This note depends on the language of equivalence relations from 2.2 Functions and relations and continues into 3.4 Rationals and well-defined operations.