Building the Integers

We are already one leg up on the ancient Greeks, as we have a 0 in our natural numbers. However, it turns out that we need some more numbers to be able to answer questions like “If I have $3, and I spend $4, how much money do I have?” (answer: “$1 in debt”, of course).

There are several ways to construct the integers. The technique used here will also come in handy later: imagine they exist, figure out how they would look, and then formalize. So, assume that there is an answer for “I have \(X\) things, and I spend \(Y\) things. How much do I have left?” Call this answer \(A(X, Y)\). Intuitively, imagine it to be \(X-Y\). What properties will it have?

• If \(X+W=Y+Z\), then \(X-Y=Z-W\), or \(A(X,Y)=A(Z,W)\).
• \((X-Y)+(Z-W)=(X+Z)-(Y+W)\) or \(A(X, Y)+A(Z, W)=A(X+Z, Y+W)\)
• \((X-Y)(Z-W)=(XZ+YW)-(XW+YZ)\) or \(A(X,Y)A(Z,W)=A(XZ+YW,XW+YZ)\)

In order to formalize this, another powerful technique is helpful – equivalence classes. Take the collection of all pairs of natural numbers \((X, Y)\).

Definition: \((X,Y)\tilde (Z,W)\) (read as “\((X,Y)\) is equivalent to \((Z,W)\)) if \(X+W=Z+Y\).

In order for a definition of a relation to be a proper equivalence, three things need to be proven: reflectivity, symmetry and transitivity.

Reflectivity: this means each thing should be equivalent to itself. Indeed, \((X,Y)~(X,Y)\) because \(X+Y=X+Y\).

Symmetry: if one thing is equivalent to another, then the other thing should be equivalent to the first thing. Indeed, if \((X,Y)~(Z,W)\) then \(X+W=Z+Y\), but then \(Z+Y=X+W\), and so \((Z,W)~(X,Y)\).

Transititivity: Assume \((X,Y)~(Z,W)\) and \((Z,W)~(U,V)\). Then \((X,Y)~(U,V)\), or \(X+V=Y+U\). We know that \(X+W=Y+Z\) and \(Z+V=U+W\). Adding both sides, we get \(X+W+Z+V=Y+Z+U+W\). Using the commutative law, \(X+V+W+Z=Y+U+W+Z\). Now, use the eliminative property of addition, and get \(X+V=Y+U\).

The other part of the technique is moving from the set of “things” to the set of “equivalence classes of things”.

Define an equivalence class as “all elements that are equivalent to a given element”

Formally: \([(X,Y)]={(Z,W): (Z,W)~(X,Y)}\).

TODO [Issue #4]: Show that \((X,Y)~(Z,W)\) iff \([(X,Y)]=[(Z,W)]\).

The set of the integers: \(\mathbb{Z}={[(X,Y)]: X,Y\in \mathbb{N}}\). Just like the natural numbers, the integers need operations.

In order to inspire the definition, again informally view \((X,Y)\) as \(X-Y\). So \(X-Y+Z-W=(X+Z)-(Y+W)\), and \((X-Y)(Z-W)=(XZ+YW)-(XW+YZ)\).

Formally:

\[[(X,Y)]+[(Z,W)]=[(X+Z,Y+W)]\]

For this definition to make sense, the following theorem is needed:

Theorem: If \((X,Y)~(X',Y')\) and \((Z,W)~(Z',W')\) then \((X+Y,Z+W)~(X'+Y',Z'+W')\).

Proof:

\[X+Y'=X'+Y\]

\[Z+W'=Z'+W\]

Adding the equalities:

\[X+Y'+Z+W'=Z'+W+X'+Y\]

Rearrange:

\[X+Z+Y'+W'=X'+Z'+Y+W\]

Which is the definition of \((X+Y,Z+W)~(X'+Y',Z'+W')\).

Because of this theorem, it does not matter which elements of the equivalence class are used to define addition, and so the definition of addition makes sense.

Define multiplication by \([(X,Y)][(Z,W)]=[(XZ+YW,XW+YZ)]\)

Exercise: Prove that this definition makes sense. Hint [Issue #5]: Follow the same steps as the proof above – write down the equivalences. This time, how about multiplying them?

Note that \([(X,0)]+[(Y,0)]=[(X+Y,0)]\) and \([(X,0)][(Y,0)]=[(XY,0)]\). Also note that if \(X\neq Y\), it is not the case that \((X,0)~(Y,0)\), and so \([(X,0)]\neq [(Y,0)]\).

Therefore, the function \(i:\mathbb{N}\to\mathbb{Z}\) preserves uniqueness, addition and multiplication. Functions that preserve uniquenes and structure are called “embeddings”. It is often convenient, and perfectly safe, to consider the embedding as an identity, and confuse \(n\) and \([(n,0)]\).

Note \([(X,Y)]+[(Y,X)]=[(X+Y,Y+X)]=[(0,0)]=e(0)\). Define $-[(X,Y)]=[(Y,X)]$, and the equality above can be written as:

\[a+(-a)=0\]

The integers with addition and multiplication are called a ring for satisfying the following axioms:

• \(a+0=a\)
• \(a+(b+c)=(a+b)+c\)
• \(a+b=b+a\)
• For every \(a\) there is a \(-a such that :math:`a+(-a)=0\)
• \(a1=a\)
• \(a(bc)=(ab)c\)
• \(ab=ba\)
• \(a(b+c)=ab+ac\)

(Notice that above we wrote \(0\) and \(1\) for \(e(0)\) and \(e(1)\)).

Define \(a-b=a+(-b)\), and any two integers can be subtracted.

Note that for every \(X\) and \(Y\), either \(Y>X\) in which case there is an number \(n\) such that \(X=Y+n\) or \(X+0=Y+n\), which means \([(X,Y)]=[(n,0)]\), either \(Y>X\) in which case there is an nteger \(n\) such that \(Y=X+n\) or \(n+X=0+Y\), which means \([(X,Y)]=[(0,n)]=-[(n,0)]\), \(X=Y\) which means \([(X,Y)]=[(0,0)]\).

In other words, for every integer, \(z\), either \(z=n\), \(z=-n\) or \(z=0\), with \(n\) a non-zero natural number.

This our structure theorem for the integers: every integer is either a natural number or the inverse of a negative number.