Constructing Number Sets
In this post, we'll continue our work on sets, focusing on building important number sets and endowing them with arithmetic properties.
Binary Operations
A binary operation on a set \(A\) is a function \(A\times A\to A\)
The main binary operations we'll be concerned with are addition, subtraction, multiplication, division. Since binary operations have two inputs, we can write them in infix notation. For example, \(+(a,b)\) can be written more cleanly as \(a+b\).
For a binary operation \(\star\) on \(A\), what sorts of properties could \(\star\) have? Here are a few:
| Name |
Formula |
Description |
| Commutativity |
\(\forall a,b,\;a\star b=b\star a\) |
Swapping inputs doesn't change the output. |
| Associativity |
\(\forall a,b,c,\;(a\star b)\star c=a\star(b\star c)\) |
Order of evaluating operations doesn't change output. |
| Identity |
\(\exists e\forall a,\;a\star e=e\star a=a\) |
There exists an identity element. |
| Invertibility |
\(\forall a\exists b,\;a\star b=b\star a=e\) |
There is an inverse for all elements. |
| Distributivity |
\(\forall a,b,c,\;a\star(b+c)=a\star b+a\star c\) |
The operation distributes over addition. |
Natural Numbers
We've covered the development of the natural numbers and some of their basic properties in the previous post. In this post, we'll continue that development with the introduction of addition and multiplication.
Consider the following two rules for addition on the naturals:
- \(0+x=x\) for all \(x\in\bbN\)
- \(S(a)+b=S(a+b)\) for all \(a,b\in\bbN\)
There exists a unique function \(+:\bbN\times\bbN\to\bbN\) satisfying these rules.
Let's first prove uniqueness. Suppose \(+_1\) and \(+_2\) are two binary operations that satisfy the two rules. Suppose there exists some \(a,b\) such that \(a+_1b\neq a+_2b\). By the well-ordering principle, let \(n\in\bbN\) be the smallest natural such that there exists \(b\in\bbN\) with \(n+_1b\neq n+_2b\).
\(n\neq0\) since \(0+_1b=b=0+_2b\) by the first rule. So, \(n=S(m)\) for some \(m\in\bbN\), and by minimality, \(m+_1S(b)=m+_2S(b)\). But, $$S(m)+_1b=S(m+_1b)=S(m+_2b)=S(m)+_2b$$This is a contradiction, proving uniqueness.
For existence, we'll construct a set similar to the construction of \(Y\) in
the Cantor-Schroeder-Bernstein theorem. Let \(H_0\) be the set map that sends \(X\) to \(((0,X),X)\). Let \(X_0\) be the set given by replacement of \(\bbN\) by \(H_0\). Let \(H\) be the set map that sends sets of the form \(((X,Y),Z)\) for naturals \(X,Y,Z\) to \(((S(X),Y),S(Z))\) (and sends everything else to \(\varnothing\)). For each \(n\in\bbN\), let \(X_{S(n)}=H(X_n)\). By the principle of mathematical induction, \(X_n\) is defined for all \(n\in\bbN\). Thus, by replacement, there exists a set \(\{X_0,X_1,\ldots\}\). Let $$+=\bigcup\{X_0,X_1,\ldots\}$$Since each \(X_0\) is a binary relation on \(\bbN\times\bbN,\bbN\), so is \(+\). I claim that \(+\) is a binary operation that satisfies the two conditions.
- \(+\) is a binary operation: By the principle of mathematical induction, all elements of \(X_n\) are of the form \(((n,a),b)\) for naturals \(a,b\). Also by the principle of mathematical induction, for each \(n,m\in\bbN\), there is exactly one element in \(X_n\) of the form \(((a,m),b)\) for \(a,b\in\bbN\). These two statements combined give us the desired result.
- \(0+n=n\) for all \(n\in\bbN\): \(((0,n),n)\in X_0\) for all \(n\in\bbN\), and \(X_0\subset +\).
- \(S(a)+b=S(a+b)\) for all \(a,b\in\bbN\): \(((a,b),a+b)\in X_a\), so \(((S(a),b),S(a+b))\in X_{S(a)}\) and \(X_{S(a)}\subset +\).
This theorem implies that we can view the two rules \(0+x=x\) and \(S(a)+b=S(a+b)\) as fully characterizing addition on the natural numbers. This makes reasoning on them a bit more nice than actually dealing with the function itself (which as you saw in the proof, is quite messy).
So what properties does addition have? For starters, \(1+k=S(k)\) for any natural \(k\), since $$1+k=S(0)+k=S(0+k)=S(k)$$More importantly,
\(\;0\) is an identity element of \(\bbN\).
By rule \(1\), \(0+x=x\) for all \(x\in\bbN\). So all we need to show is that \(x+0=x\) for all \(x\in\bbN\). Assume this isn't the case, and let \(i\in\bbN\) by the smallest natural such that \(i+0\neq i\) by the well-ordering principle. \(i\neq0\) since \(0+0=0\) by rule \(1\). So, let \(k\in\bbN\) such that \(S(k)=i\). Then, \(k+0=k\), and $$S(k)+0=S(k+0)=S(k)$$This prove that \(0\) is an additive identity.
For all \(a,b,c\in\bbN\), \(a+(b+c)=(a+b)+c\).
Proof by induction. If \(a=0\), then $$0+(b+c)=b+c=(0+b)+c$$If the statement holds for \(a\), then $$S(a)+(b+c)=S(a+(b+c))=S((a+b)+c)=S(a+b)+c=(S(a)+b)+c$$
Since addition is associative, we don't need to specify order of operations in a sequence of additions. I.e., we can just write \(a+b+c\).
For all \(a,b\in\bbN\), \(a+b=b+a\).
Proof by induction on \(a\). If \(a=0\), the claim holds since \(0\) is the identity. If \(a=1\), observe that \(1+0=0+1\) and for any \(b\) such that \(1+b=b+1\), $$S(b)+1=1+b+1=1+1+b=1+S(b)$$So, by induction, the claim is true for \(a=1\). And if the claim is true for some \(a\), then $$S(a)+b=1+a+b=1+b+a=b+1+a=b+S(a)$$By induction, we are done.
For all \(a,b,c\in\bbN\), if \(a+c=b+c\), then \(a=b\)
Proof by induction on \(c\). $$a=a+0=b+0=b$$Assume that for all \(a,b\in\bbN\), \(a+c=b+c\) implies \(a+b\). Now, consider \(x,y\in\bbN\) such that \(x+S(c)=y+S(c)\). Thus, $$S(x+c)=x+S(c)=y+S(c)=S(y+c)$$Since \(S\) is injective, \(x+c=y+c\), so \(x=y\).
For all \(a,b\in\bbN\), \(a+b\geq a\), and \(a+b=a\) iff \(b=0\).
First, we show \(a+b\geq a\) by induction on \(b\). We have \(a+0=a\geq a\), and if \(a+b\geq a\), then $$a+S(b)=S(a+b)>a+b\geq a$$
This theorem also implies that \(0\) is the only identity element and that \(a+b\geq\max(a,b)\) by commutativity. Now that we have the basic properties of addition established, we introduce multiplication.
There exists a unique binary operation \(\cdot\) on the naturals with the following properties
- \(0\cdot b=0\) for all \(b\in\bbN\)
- \(S(a)\cdot b=b+(a\cdot b)\)
First, we show uniqueness. Suppose \(\cdot_1,\cdot_2\) are two different binary operations that both satisfy the properties. By the well-ordering principle (WOP), there exists a smallest \(a\in\bbN\) such that there exists \(x\in\bbN\) with \(a\cdot_1x\neq a\cdot_2x\). \(a\neq0\) since rule \(1\) forces $$0\cdot_1x=0\cdot_2x=0$$So, there exists \(k\in\bbN\) such that \(S(k)=a\). Thus, $$S(k)\cdot_1b=b+(k\cdot_1b)=b+(k\cdot_2b)=S(k)\cdot_2b$$This proves uniqueness
For existence, let $$X_0=\{((0,b),0)\mid b\in\bbN\}$$(this notation implies replacement is being used), and let $$X_{S(k)}=\{((S(k),b),b+x)\mid ((k,b),x)\in X_k\}$$Let \(\cdot=\bigcup\{X_n\mid n\in\bbN\}\). I claim that this is a binary operation satisfying the properties.
- \(\cdot\) is a binary operation: Same reasoning as in the corresponding proof for addition.
- \(0\cdot b=0\): \(((0,b),0)\in X_0\subset\cdot\), which implies the property.
- \(S(a)\cdot b=b+a\cdot b\): If \(((a,b),k)\in X_a\), then \(((S(a),b),b+k)\in X_{S(a)}\).
Not a particularly enlightening proof, but the consequence of it is important: the two rules provided fully characterize multiplication on the naturals, and we'll use them to prove all of the important properties of multiplication.
For all \(b\in\bbN\), $$0\cdot b=b\cdot 0=0$$$$1\cdot b=b\cdot 1=b$$
Suppose there exists some \(x\) such that \(x\cdot 0\neq0\). Let \(b\) be the smallest such natural. \(b\neq0\) since \(0\cdot0=0\). So, \(b=S(a)\) for some \(a\in\bbN\). And, $$S(a)\cdot0=0+a\cdot0=0$$
For the identity proof, $$1\cdot b=b+0\cdot b=b$$$$0\cdot 1=0$$$$S(b)\cdot 1=1+b\cdot 1=1+b=S(b)$$and thus we are done by induction.
For all \(a,b\), \(a\cdot b=b\cdot a\)
Proof by induction on \(a\). $$0\cdot b=b\cdot0=0$$$$S(a)\cdot b=b+a\cdot b=b+b\cdot a$$Suppose there exists some \(b\) for which \(b+b\cdot a\neq b\cdot S(a)\). Let \(b\) be minimal. \(b\neq0\) since \(0+0\cdot a=0\) and \(0\cdot S(a)=0\). And, if \(b=S(k)\), we have $$S(k)+S(k)\cdot a=1+k+a+k\cdot a=S(a)+k\cdot S(a)=S(k)\cdot S(a)$$Thus, \(b+b\cdot a=b\cdot S(a)\), and the proof is complete.
For all \(a,b,c\), \(c\cdot(a+b)=c\cdot a+c\cdot b\)
Proof by induction on \(c\). $$0\cdot(a+b)=0=0\cdot a+0\cdot b$$$$S(c)\cdot(a+b)=a+b+c\cdot(a+b)=a+c\cdot a+b+c\cdot b=S(c)\cdot a+S(c)\cdot b$$
For all \(a,b,c\), either \(c=0\) or \(a\cdot c=b\cdot c\) implies \(a=b\)
Proof by induction on \(c\). If \(c=0\), it is trivially true. If \(c=1\), $$a=a\cdot1=b\cdot1=b$$Assume that for all \(a,b\in\bbN\), \(a\cdot c=b\cdot c\) implies \(a=b\). Let \(x,y\in\bbN\) such that \(x\cdot S(c)=y\cdot S(c)\). Then, $$x+x\cdot c=x\cdot S(c)=y\cdot S(c)=y+y\cdot c$$Thus, since addition is injective, \(x=y\).
For all \(a,b,c\in\bbN\), \(a\cdot(b\cdot c)=(a\cdot b)\cdot c\)
Proof by induction on \(a\). $$(0\cdot b)\cdot c=0\cdot c=0=0\cdot(b\cdot c)$$$$(S(a)\cdot b)\cdot c=(b+a\cdot b)\cdot c=b\cdot c+(a\cdot b)\cdot c=b\cdot c+a\cdot(b\cdot c)=S(a)\cdot(b\cdot c)$$
With these results, we now have addition and multiplication with the properties we are familiar with. The rest of the number systems we will build will build on this (and thus will be a bit less tedious).
Integers
Now that we have the natural numbers, we can build the integers. The integers are special because they are the smallest group that extends the addition of the natural numbers. We'll understand more properly what this means in a technical sense, but for now, let's define what a group (and related algebraic structures) is!
A
group is a set \(S\) with a binary operation \(\star\) with the following properties:
- \(S\) has a identity over \(\star\).
- \(\star\) is associative.
- \(S\) has inverses over \(\star\)
A
ring is a set \(S\) with two binary operations, \(+,\cdot\), with the following properties:
- \(S\) is a group under \(+\)
- \(+\) is commutative
- \(S\) has a identity element for \(\cdot\)
- \(\cdot\) is associative
- \(\cdot\) is distributive
A field is a ring \(S,+,\cdot\) with the following properties:
- \(\cdot\) is commutative
- \(S\) has inverses over \(\cdot\) for all elements besides the additive identity
The study of these structures and others are far too large of a task for this post: see a text on abstract algebra for a proper lesson. For now, we construct the integers.
Consider the equivalence relation on \(\bbN\times\bbN\) given by \((a,b)\sim(c,d)\) iff \(a+d=b+c\). This is an equivalence relation because
- Reflexivity:\(\;(a,b)\sim(a,b)\) since \(a+b=b+a\)
- Symmetry:\(\;(a,b)\sim(c,d)\) implies \(a+d=b+c\), so \(c+b=d+a\) and thus \((c,d)\sim(a,b)\)
- Transitivity:$$(a,b)\sim(c,d)\wedge(c,d)\sim(e,f)$$implies$$a+d=b+c\wedge c+f=d+e$$$$a+c+d+f=b+c+d+e$$By injectivity, \(a+f=b+e\) and thus \((a,b)\sim(e,f)\)
Thus, we define \(\bbZ\) as the partition associated with \(\sim\), notated as \(\bbN\times\bbN/\sim\).
The intuition behind the definition is as follows: we view \((a,b)\) as a nickname for \(a-b\). However, that's redundant, as \((1,0)\) and \((2,1)\) represent the same number. To rectify this, we make two pairs equivalent if \(a-b=c-d\), or simply in terms of addition, \(a+d=b+c\). We don't have negation yet, so everything must be phrased in terms of addition and multiplication.
For some additional notation, we write \([(a,b)]\) to represent the element of \(\bbZ\) that contains \((a,b)\).
For any \(a,b,c\in\bbN\), if \([(a,c)]=[(b,c)]\) or \([(c,a)]=[(c,b)]\), then \(a=b\).
If \([(a,c)]=[(b,c)]\), then \(a+c=c+b\), which by addition being injective implies that \(a=b\). If \([(c,a)]=[(c,b)]\), then \(c+b=a+c\), which by addition being injective implies \(a=b\).
This theorem implies that the function \(\bbN\to\bbZ\) given by \(x\mapsto[(x,0)]\) is injective. The function is known as the canonical embedding of the naturals into the integers. By canonical embedding, we mean that it is the standard choice of injection \(\bbN\to\bbZ\), so much so that we call \([(x,0)]\) just \(x\). Under this interpretation, \(\bbN\subset\bbZ\). Now, let's see that \(\bbN\neq\bbZ\)
For all \(x\in\bbN\), \([(0,S(x))]\neq y\) for all \(y\in\bbN\).
Suppose there exists some \(y\in\bbN\) such that \([(y,0)]=[(0,S(x))]\). Then, \(y+S(x)=S(y+x)=0+0\), a contradiction.
Integers of this form, which we will call negative numbers, have some nice properties with respect to addition.
For any \([(a,b)]\in\bbZ\), we define \(-[(a,b)]\), the negation of \([(a,b)]\), as \([(b,a)]\). It is evident by definition that \(--[(a,b)]=[(a,b)]\), so the negation is its own inverse.
This definition is well defined since for any \([(a,b)]=[(c,d)]\), \(a+d=b+c\), which implies \(b+c=a+d\) and thus \([(b,a)]=[(d,c)]\). I claim that all integers are in \(\bbN\), or are the negation of some non-zero natural number.
All integers \([(a,b)]\) are equal to \([(x,0)]\) or \([(0,x)]\) for some \(x\in\bbN\).
Let \(b\in\bbN\). Proof by induction on \(a\). If \(a=0\), then \([(0,b)]=[(0,b)]\). For the inductive case, there are two possibilities:
- There exists \(x\in\bbN\) such that \([(a,b)]=[(0,x)]\). If \(x=0\), then \(a=b\), so \(S(a)+0=b+1\) and thus \([(S(a),b)]=[(1,0)]\). If \(x=S(k)\) for some \(k\in\bbN\), then since \(a+S(k)=b\), \(S(a)+k=b\), so \([(S(a),b)]=[(0,k)]\).
- There exists \(x\in\bbN\) such that \([(a,b)]=[(x,0)]\): Then \(a=b+x\), so \(S(a)=b+S(x)\). Thus, \([(S(a),b)]=[(S(x),0)]\).
Thus, all integers are either \(0\), a non-zero natural number, or the negation of a non-zero natural number. We call non-zero natural numbers positive integers, negations of non-zero natural numbers negative integers.
So, all integers can be written as \(k\) or \(-k\) for some \(k\in\bbN\) (with \(-0=0\) by definition.) Moreover, \(--k=k\) as we saw earlier. To see why this is useful, let's understand how addition is defined.
Let \(+\) be the following binary operation on \(\bbZ\):$$[(a,b)]+[(c,d)]=[(a+c,b+d)]$$This operation is well-defined.
By well defined, we mean that the definition of the function produces the same answer regardless of which \((a,b)\) and \((c,d)\) we choose to represent their class. More precisely, we want to show that if \([(a_1,b_1)]=[(a_2,b_2)]\) and \([(c_1,d_1)]=[(c_2,d_2)]\), then $$[(a_1+c_1,b_1+d_1)]=[(a_2+c_2,b_2+d_2)]$$This is true iff $$a_1+c_1+b_2+d_2=a_2+c_2+b_1+d_1$$But, our givens imply that \(a_1+b_2=a_2+b_1\) and \(c_1+d_2=d_1+c_2\), so we are done.
This definition of addition is a binary operation since it is well-defined by definition. Now, we list a series of important properties of integers.
\(\;\)Subtraction is the following binary operation: \([(a,b)]-[(c,d)]\) is the integer \([(a,b)]+(-[(c,d)])\).
\([(a,b)]-[(a,b)]=[(a,b)]+(-[(a,b)])=0\) for all \([(a,b)]\in\bbZ\). \(0\) is the identity element of \(\bbZ\) for addition, and there are no others.
$$[(a,b)]+(-[(a,b)])=[(a,b)]+[(b,a)]=[(a+b,a+b)]=[(0,0)]$$$$[(a,b)]+[(0,0)]=[(0,0)]+[(a,b)]=[(a,b)]$$$$([(a,b)]+[(c,d)])-[(a,b)]=[(c,d)]$$
Consider the relation on \(\bbZ\) given by \([(a,b)]\leq[(c,d)]\) iff \([(a,b)]-[(c,d)]\in\bbN\). This relation is an order on \(\bbZ\), and orders the naturals by the natural order.
Let's first show that this relation is an order.
- Reflexivity: \(\;[(a,b)]-[(a,b)]=[(a+b,a+b)]=0\)
- Anti-symmetry: If \([(a,b)]-[(c,d)]=[(a+d,b+c)]=[(k,0)]\) and \([(c,d)]-[(a,b)]=[(c+b,d+a)]=[(x,0)]\) for \(x,k\in\bbN\), then $$[(x+k,0)]=[(x,0)]+[(k,0)]=[(a+d,b+c)]+[(c+b,a+d)]=[(0,0)]$$Thus, \(x+k=0\), which implies that \(x,k=0\).
- Transitivity: If \([(a,b)]-[(c,d)]=[(x,0)]\) and \([(c,d)]-[(e,f)]=[(y,0)]\) for \(x,y\in\bbN\), then $$[(a,b)]-[(e,f)]=[(a+f,b+e)]=[(a+f+c+d,b+e+c+d)]$$$$=([(a,b)]-[(c,d)])+([(c,d)]-[(e,f)])=x+y\in\bbN$$
- Trichotomy: By integer forms, \([(a,b)]-[(c,d)]=[(a-c,b-d)]\) is either of the form \([(x,0)]\) or \([(0,x)]\). In the first case, \([a,b]\geq[(c,d)]\) by definition. In the second, $$[(c,d)]-[(a,b)]=-([(a,b)]-[(c,d)])=-[(0,x)]=[(x,0)]$$And thus \([(c,d)]\geq[(a,b)]\)
To see that this order is the same as the natural numbers order when comparing natural numbers, let \(x,y\in\bbN\), I claim that \([(x,0)]\leq[(y,0)]\) iff \(x\leq y\). Observe that \([(y,0)]-[(x,0)]=[(y,x)]\). If there exists \(k\in\bbN\) such that \([(y,x)]=[(k,0)]\), then \(y=x+k\), which implies that \(y\geq x\). If there exists \(l\in\bbN\) such that \([(y,x)]=[(0,k)]\), then \(x=y+k\), which implies that \(x\geq y\).
For any \(a,b\in\bbN\), \(a\leq b\) iff \([(a,0)]\leq[(b,0)]\).
If \([(a,0)]\leq[(b,0)]\), then \([(b,a)]=[(x,0)]\) for some \(x\in\bbN\). Thus, \(b=a+x\). Since addition respects order on the naturals, \(a\leq b\). A symmetric argument shows that if \([(a,0)]\geq[(b,0)]\), \(a\geq b\). By antisymmetry, we are done.
For all \([(a,b)],\;[(c,d)]\in\bbZ\), $$[(a,b)]+[(c,d)]=[(c,d)]+[(a,b)]$$
$$[(a,b)]+[(c,d)]=[(a+c,b+d)]=[(c+a,d+b)]=[(c,d)]+[(a,b)]$$
For all \([(a,b)],\;[(c,d)],\;[(e,f)]\in\bbZ\), $$[(a,b)]+([(c,d)]+[(e,f)])=([(a,b)]+[(c,d)])+[(e,f)]$$
$$[(a,b)]+([(c,d)]+[(e,f)])=[(a+(c+e),b+(d+f))]=[((a+c)+e,(b+d)+f)]=([(a,b)]+[(c,d)])+[(e,f)]$$
If \([(a,b)]\leq[(c,d)]\) and \([(e,f)]\leq[(g,h)]\), $$[(a,b)]+[(e,f)]\leq[(c,d)]+[(g,h)]$$
$$[(c,d)]+[(g,h)]-[(a,b)]-[(e,f)]=[(c-a,d-b)]+[(g-e,h-f)]$$By the givens, \([(c-a,d-b)],[(g-e,h-f)]\in\bbN\), so $$[(c-a,d-b)]+[(g-e,h-f)]\in\bbN$$
These properties establish all of the behavior we expect from integer addition. Now, we define multiplication.
Define \(\cdot\) be the binary operation on \(\bbZ\) that is defined by $$[(a,b)]\cdot[(c,d)]=[(a\cdot c+b\cdot d,b\cdot c+a\cdot d)]$$This operation is well-defined on \(\bbZ\).
Let \(a_1,a_2,b_1,b_2,c_1,c_2,d_1,d_2\in\bbN\) such that \([(a_1,b_1)]=[(a_2,b_2)]\) and \([(c_1,d_1)]=[(c_2,d_2)]\). Then \(a_1+b_2=a_2+b_1\) and \(c_1+d_2=d_1+c_2\). We want to show $$a_1\cdot c_1+b_1\cdot d_1+b_2\cdot c_2+a_2\cdot d_2=a_2\cdot c_2+b_2\cdot d_2+b_1\cdot c_1+a_1\cdot d_1$$Observe that $$a_1c_1+b_1d_1+b_2c_2+a_2d_2+(a_2c_1+b_2c_1+a_2d_1+b_2d_1)$$$$=(a_1+b_2)c_1+(a_2+b_1)d_1+a_2(c_1+d_2)+b_2(c_2+d_1)$$$$=(b_1+a_2)c_1+(b_2+a_1)d_1+a_2(c_2+d_1)+b_2(c_1+d_2)$$$$=a_2c_2+b_2d_2+b_1c_1+a_1d_1+(a_2c_1+b_2c_1+a_2d_1+b_2d_1)$$Since addition on the naturals is injective, we are done.
The intuition behind this definition is that \((a-b)(c-d)=ac+bd-bc-ad\). Now, we prove the important properties about multiplication.
For all \([(a,b)],[(c,d)]\in\bbZ\), \([(a,b)]\cdot[(c,d)]=[(c,d)]\cdot[(a,b)]\)
$$[(a,b)]\cdot[(c,d)]=[(ac+bd,bc+ad)]=[(ca+db,cb+da)]=[(c,d)]\cdot[(a,b)]$$
For all \([(a,b)],[(c,d)],[(e,f)]\in\bbZ\),$$[(a,b)]\cdot([(c,d)]\cdot[(e,f)])=([(a,b)]\cdot[(c,d)])\cdot[(e,f)]$$
$$[(a,b)]\cdot([(c,d)]\cdot[(e,f)])=[(ace+adf+bcf+bde,acf+ade+bce+bdf)]=([(a,b)]\cdot[(c,d)])\cdot[(e,f)]$$
For all \([(a,b)],[(c,d)],[(e,f)]\in\bbZ\),$$[(a,b)]\cdot([(c,d)]+[(e,f)])=[(a,b)]\cdot[(c,d)]+[(a,b)]\cdot[(e,f)]$$
$$[(a,b)]\cdot([(c,d)]+[(e,f)])=[(ac+ae+bd+bf,ad+af+bc+be)]$$$$=[(ac+bd,ad+bc)]+[(ae+bf,af+be)]$$$$=[(a,b)]\cdot[(c,d)]+[(a,b)]\cdot[(e,f)]$$
Like with the naturals, if \([(e,f)]\neq0\) and \([(a,b)]\cdot[(e,f)]=[(c,d)]\cdot[(e,f)]\), then \([(a,b)]=[(c,d)]\).
By integer forms, there are two cases to consider:
- There exists \(x\in\bbN\), \([(e,f)]=[(S(x),0)]\): The given equality implies $$(a+d)\cdot S(x)=(b+c)\cdot S(x)$$Since multiplication is almost injective on the naturals, we have \(a+d=b+c\).
- There exists \(x\in\bbN\), \([(e,f)]=[(0,S(x))]\): The given equality implies $$(b+c)\cdot S(x)=(a+d)\cdot S(x)$$Since multiplication is almost injective on the naturals, \(a+d=b+c\).
\(1\) is the only identity element of \(\cdot\)
First, for all \([(a,b)]\in\bbZ\), $$[(a,b)]\cdot[(1,0)]=[(a\cdot 1+b\cdot 0,a\cdot 0+b\cdot 1)]=[(a,b)]$$And, for all \([(c,d)]\), if \([(a,b)]=[(ac+bd,ad+bc)]\), then $$a+ad+bc=b+ac+bd$$$$a(d+1)+bc=ac+b(d+1)$$Letting \(a=0,b=1\), this becomes \(c=d+1\). Thus, \([(1,0)]=[(c,d)]\).
For any \(a,b\in\bbN\), \([(a,0)]\cdot[(b,0)]=[(a\cdot b,0)]\).
$$[(a,0)]\cdot[(b,0)]=[(ab+0\cdot0,a\cdot 0+b\cdot0)]=[(a\cdot b,0)]$$
For any \([(a,b)],[(c,d)]\in\bbZ\), if \([(a,b)]\cdot[(c,d)]=0\), then \([(a,b)]=0\) or \([(c,d)]=0\).
If the given equality holds, we have \(ac+bd=ad+bc\). If \([(c,d)]\neq0\), \(c\neq d\). Without loss of generality, \(c\lt d\), so since integer order is the same as the natural order, there exists \(x\in\bbN\) such that \(c+S(x)=d\). So, $$ac+bc+b\cdot S(x)=ac+bc+a\cdot S(x)$$By injectivity of addition and multiplication almost being injective, we have \(a=b\) and thus \([(a,b)]=0\).
If \(x\in\bbN\) and \([(a,b)]\geq[(c,d)]\), \(x\cdot[(a,b)]\geq x\cdot[(c,d)]\). The converse is also true when \(x\neq0\).
Since \(x\cdot[(y,z)]=[(yx,zx)]\), we want to show that given \([(a-c,b-d)]=k\) for some \(k\in\bbN\), \([(xa-xc,xb-xd)]\) is also natural. But, we know $$[(xa-xc,xb-xd)]=[(x(a-c),x(b-d))]=x\cdot[(a-c,b-d)]=x\cdot k$$And since the product of natural numbers is natural, we are done. For the converse, if \(x\cdot[(a-c,b-d)]\in\bbN\), observe that if \([(a-c,b-d)]=[(0,S(k))]\) for some \(k\in\bbN\), then \(x\cdot[(0,S(k))]=[(0,x\cdot S(k))]\). Since \(\bbZ\) is an integral domain, \(x\cdot S(k)\neq0\), and thus, \([(0,x\cdot S(k))]\lt0\), a contradiction. Thus, \([(a-c,b-d)]\geq0\) and we are done.
This shows all of the important properties of \(\bbZ\). In particular, we have established that \(\bbZ\) is a ring, \(\bbN\subset\bbZ\), and that the addition and multiplication of the naturals in the integers is the same as the one we defined for the naturals.