# Naive Set Theory: Number Systems

## Integers

The natural numbers have the addition operation defined for them, but not subtraction. The closest thing to subtraction they have going for them is the cancellation law of addition, which states that if $a + b = a + c$, then $b = c$. Nobody has told us we can't define subtraction in some way, though, so let's give it the old college try. As a first attempt, let's define $- : \mathbb{N}^- \rightarrow \mathbb{N}$ as

$$a - b = c \text{ such that } b + c = a$$

where $\mathbb{N}^- = \{ (a, b) \in \mathbb{N} \times \mathbb{N} : a \geq b \}$.

At first blush, this looks like a success. We can now makes sense of an equation like $5-2=3$. However, the fact that the natural numbers are not closed under subtraction is a real setback. The natural numbers are closed under addition and multiplication, so why not subtraction? From our familiarity with more powerful number systems, such as the integers, we know that the subtraction of a greater number from a smaller number results in a "negative" number, which is somehow less than $0$. However, the von Neumann construction of $\mathbb{N}$ implies that asking for a number less than $0$ is like asking for a set that is contained within the empty set - by definition, it simply doesn't exist. In fact, it doesn't even make sense philosophically to ask about such a thing.

We could view this as the end of the road and conclude that only the natural numbers make sense. But where's the fight in that? After all, the natural numbers were themselves constructed out of nothing but the empty set and a successor function. So instead of rolling over like a bunch of cowards, we'll take a page from von Neumann and construct ourselves a new set of numbers. This new set of numbers will be like the natural numbers, but it will be closed under subtraction.

The new numbers we construct should have all of the desirable properties of the natural numbers plus the concept of negative numbers and a closed subtraction operator. Both aspects must be present - it would not be useful to invent numbers capable of subtraction at the expense of addition, multiplication, or some very useful algebraic property concerning their uses.

We saw that for every $(a, b) \in \mathbb{N} \times \mathbb{N}$ where $a > b$, the element $(b, a)$ is not in $\mathbb{N}^-$. We can venture to define a negative number as the ordered pair $(b, a)$ when $a > b$. For example, we see that the ordered pair $(4, 1)$ corresponds to $3$, so $(1, 4)$ would correspond to negative $3$, which we could write as $-3$. However, this construction poses a problem, as $(4, 1)$ is identical to $(5, 2)$, $(6, 3)$, and an infinite number of similar pairs.

The solution is then to define the integers in terms of equivalence classes of ordered pairs in $\mathbb{N} \times \mathbb{N}$. Thus, the integer $3$ will be equal to the set containing $(3, 0), (4, 1), (5, 2)$, and so on. However, we need to clarify how exactly a given ordered pair may be determined to be equivalent (or not) to another. We might suggest that $(a, b) \sim (c, d)$ if $a - b = c - d$, but because the subtraction operation is only defined when the result is non-negative, the equivalence class is broken for the exact situation we built it to fix in the first place. But despair not, for this pothole is easy to avoid. Just define equivalence in terms of addition instead, under which $\mathbb{N}$ is safely closed. Adding $b$ and $d$ to both sides, we instead say that $(a , b) \sim (c, d)$ if and only if $a + d = c + b$.

Putting it all together, we define the integers, denoted as $\mathbb{Z}$, as the quotient set of $\mathbb{N} \times \mathbb{N}$ under $\sim$, where $(a, b) \sim (c, d)$ if and only if $a + d = b + c$. Formally,

$$\mathbb{Z} = ( \mathbb{N} \times \mathbb{N} ) \; / \sim$$

where

$$(a, b) \sim (c, d) \text{ iff } a + d = c + b.$$

Given this definition, the equivalence class $\{ (a, b) : (a,b) \sim (1,0) \}$ is in $\mathbb{Z}$, and its members are $(1,0)$, $(2, 1)$, $(3, 2)$, and so on. And just as we abbreviate $\{\varnothing\}$ as $1$ when talking about natural numbers, so too can we abbreviate the foregoing equivalence class as $1$.

However, we now have conflict of notation. The symbol $1$ cannot be equal to both $\{ \varnothing\} \in \mathbb{N}$ and $\{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a,b) \sim (1,0) \} \in \mathbb{Z}$. Thankfully, in almost all cases outside of discussions of the specific construction of $\mathbb{Z}$ from $\mathbb{N}$, the context should make clear whether the natural number or the integer is intended.

Nevertheless, because we are in fact presently interested in constructing $\mathbb{Z}$ from $\mathbb{N}$, and there is indeed a meaningful set-theoretic difference between the natural number $1$ and the integer $1$, we will mark numerals with subscripts $\mathbb{N}$ or $\mathbb{Z}$ when necessary to dispel any ambiguity. To illustrate, here are the closest few integers around $0_{\mathbb{Z}}:$

$$\begin{matrix} -2_{\mathbb{Z}} & = & \{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a, b) \sim (0_{\mathbb{N}}, 2_{\mathbb{N}}) \} \\ -1_{\mathbb{Z}} & = & \{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a, b) \sim (0_{\mathbb{N}}, 1_{\mathbb{N}}) \} \\ \phantom{-}0_{\mathbb{Z}} & = & \{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a, b) \sim (0_{\mathbb{N}}, 0_{\mathbb{N}}) \} \\ \phantom{-}1_{\mathbb{Z}} & = & \{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a, b) \sim (1_{\mathbb{N}}, 0_{\mathbb{N}}) \} \\ \phantom{-}2_{\mathbb{Z}} & = & \{ (a, b) \in \mathbb{N} \times \mathbb{N} : (a, b) \sim (2_{\mathbb{N}}, 0_{\mathbb{N}}) \} \\ \end{matrix}$$

Using the bracket notation for equivalence classes saves us some writing:

$$\begin{matrix} -2_{\mathbb{Z}} & = & [(0_{\mathbb{N}}, 2_{\mathbb{N}})] \\ -1_{\mathbb{Z}} & = & [(0_{\mathbb{N}}, 1_{\mathbb{N}})] \\ \phantom{-}0_{\mathbb{Z}} & = & [(0_{\mathbb{N}}, 0_{\mathbb{N}})] \\ \phantom{-}1_{\mathbb{Z}} & = & [(1_{\mathbb{N}}, 0_{\mathbb{N}})] \\ \phantom{-}2_{\mathbb{Z}} & = & [(2_{\mathbb{N}}, 0_{\mathbb{N}})] \\ \end{matrix}$$

The familiar arithmetic and ordering properties of the integers are defined and proven in the problems below. Further analysis of the natural numbers and the integers themselves is left to the field of number theory.

## Problems

1. Verify that the relation $\sim$ in the definition of $\mathbb{Z}$ in fact forms an equivalence relation.

We show that $\sim$ satisfies the three properties of equivalence relations:

1. Reflexivity: Let $(a, b) \in \mathbb{N} \times \mathbb{N}$. Then $a + b = a + b$, so $(a, b) \sim (a, b)$.

2. Symmetry: Let $(a, b), (c, d) \in \mathbb{N} \times \mathbb{N}$ such that $(a, b) \sim (c, d)$. Then $a + d = c + b$. By definition of equality, $c + b = a + d$. Therefore $(c, d) \sim (a, b)$.

3. Transitivity: Let $(a, b), (c, d), (e, f) \in \mathbb{N} \times \mathbb{N}$ such that $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$. Then

$a + d = c + b \text{ and} \\ c + f = e + d.$

Adding $f$ to both sides of the first equation and $b$ to both sides of the second gives us

$a + d + f = c + b + f \text{ and} \\ c + f + b = e + d + b.$

Transitivity on $\mathbb{N}$ then gives us

$a + d + f = e + d + b. \\$

The cancellation law on $\mathbb{N}$ simplifies the equation to

$a + f = e + b. \\$

From which we confirm that $(a, b) = (e, f)$ as desired.

2. Show that $0_{\mathbb{Z}} \neq 1_{\mathbb{Z}}$.

Proof by contradiction. Suppose $0_{\mathbb{Z}} = 1_{\mathbb{Z}}$. Then $[(0_{\mathbb{N}}, 0_{\mathbb{N}})] = [(1_{\mathbb{N}}, 0_{\mathbb{N}})]$, so $(0_{\mathbb{N}}, 0_{\mathbb{N}}) \sim (1_{\mathbb{N}}, 0_{\mathbb{N}})$. By definition of $\sim$, this means that $1_{\mathbb{N}} + 0_{\mathbb{N}} = 0_{\mathbb{N}} + 0_{\mathbb{N}}$. However, this is a contradiction, as $1_{\mathbb{N}} \neq 0_{\mathbb{N}}$. Therefore $0_{\mathbb{Z}} \neq 1_{\mathbb{Z}}$.

3. Define the addition operation on the integers as

$$+ : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$$

where

$$[(a_{\mathbb{N}},b_{\mathbb{N}})] + [(c_{\mathbb{N}}, d_{\mathbb{N}})] = [(a_{\mathbb{N}} + c_{\mathbb{N}}, b_{\mathbb{N}} + d_{\mathbb{N}})].$$

Show that the choice of ordered pair from each equivalence class does not matter. Namely, show that if $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ that $(a + c, b + d) \sim (a' + c', b' + d')$ for all $a,b,c,d,a',b',c',d' \in \mathbb{N}$.

If $(a, b) \sim (a', b')$, then $a + b' = a' + b$. Likewise, if $(c, d) \sim (c', d')$, then $c + d' = c' + d$. Adding the two equations together gives us

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

Therefore $(a + c, b + d) \sim (a' + c', b' + d')$

4. Compute the following and simply the ordered pair to the appropriate integer numeral:

1. $[(3_{\mathbb{N}}, 1_{\mathbb{N}})] + [(10_{\mathbb{N}}, 4_{\mathbb{N}})]$

2. $[(10_{\mathbb{N}}, 4_{\mathbb{N}})] + [(3_{\mathbb{N}}, 1_{\mathbb{N}})]$

3. $[(1_{\mathbb{N}}, 3_{\mathbb{N}})] + [(10_{\mathbb{N}}, 4_{\mathbb{N}})]$

4. $[(4_{\mathbb{N}}, 10_{\mathbb{N}})] + [(1_{\mathbb{N}}, 3_{\mathbb{N}})]$

1. $[(3_{\mathbb{N}}, 1_{\mathbb{N}})] + [(10_{\mathbb{N}}, 4_{\mathbb{N}})] = [(3_{\mathbb{N}} + 10_{\mathbb{N}}, 1_{\mathbb{N}} + 4_{\mathbb{N}} )] = [(13_{\mathbb{N}}, 5_{\mathbb{N}})] = 8_{\mathbb{Z}}$

2. $[(10_{\mathbb{N}}, 4_{\mathbb{N}})] + [(3_{\mathbb{N}}, 1_{\mathbb{N}})] = [(10_{\mathbb{N}} + 3_{\mathbb{N}}, 4_{\mathbb{N}} + 1_{\mathbb{N}} )] = [(13_{\mathbb{N}}, 5_{\mathbb{N}})] = 8_{\mathbb{Z}}$

3. $[(1_{\mathbb{N}}, 3_{\mathbb{N}})] + [(10_{\mathbb{N}}, 4_{\mathbb{N}})] = [(1_{\mathbb{N}} + 10_{\mathbb{N}}, 3_{\mathbb{N}} + 4_{\mathbb{N}})] = [(11_{\mathbb{N}}, 7_{\mathbb{N}})] = 4_{\mathbb{Z}}$

4. $[(4_{\mathbb{N}}, 10_{\mathbb{N}})] + [(1_{\mathbb{N}}, 3_{\mathbb{N}})] = [(4_{\mathbb{N}} + 1_{\mathbb{N}}, 10_{\mathbb{N}} + 3_{\mathbb{N}})] = [(5_{\mathbb{N}}, 13_{\mathbb{N}})] = -8_{\mathbb{Z}}$

5. Additive Identity: Show that $0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$ is the additive identity in $\mathbb{Z}$. Namely, show that for all $a \in \mathbb{Z}$ that $a + 0_{\mathbb{Z}} = a$.

Let $a = [(x_{\mathbb{N}}, y_{\mathbb{N}})]$. By definition, $0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$. Summing the two together gives us

$a + 0_{\mathbb{Z}} = [(x_{\mathbb{N}}, y_{\mathbb{N}})] + [(0_{\mathbb{N}}, 0_{\mathbb{N}})] \\ a + 0_{\mathbb{Z}} = [(x_{\mathbb{N}} + 0_{\mathbb{N}}, y_{\mathbb{N}} + 0_{\mathbb{N}})] \\ a + 0_{\mathbb{Z}} = [(x_{\mathbb{N}}, y_{\mathbb{N}})] \\ a + 0_{\mathbb{Z}} = a \\$

6. Additive Inverse: Show that for every $a \in \mathbb{Z}$ there exists a number $b$ such that $a + b = 0_{\mathbb{Z}}$, and furthermore that $b = -a$. Show also that $-0_{\mathbb{Z}} = 0_{\mathbb{Z}}$.

Let $a \in \mathbb{Z}$. Then we can represent $a$ as an equivalence class $a = [(x, y)]$, where $x,y \in \mathbb{N}$. By definition, the equivalence class $-a = [(y, x)]$ is also in $\mathbb{Z}$. Let $b = -a$. Then

$a + b = a + (-a) \\ a + b = [(x, y)] + [(y, x)] \\ a + b = [(x + y, y + x)] \\ a + b = [(x + y, x + y)] \\ a + b = [(0, 0)] \\ a + b = 0_{\mathbb{Z}}$

Thus $-a$ is the additive inverse of $a$.

Observe that $0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$. By definition of a negative number, $-0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$, therefore $-0_{\mathbb{Z}} = 0_{\mathbb{Z}}$.

7. Commutativity of Addition: Show that $a + b = b + a$ for all $a, b \in \mathbb{Z}$.

Let $a = [(x_{\mathbb{N}}, y_{\mathbb{N}})]$ and let $b = [(z_{\mathbb{N}}, w_{\mathbb{N}})]$. Then

$a + b = [(x_{\mathbb{N}}, y_{\mathbb{N}})] + [(z_{\mathbb{N}}, w_{\mathbb{N}})] \\ a + b = [(x_{\mathbb{N}} + z_{\mathbb{N}}, y_{\mathbb{N}} + w_{\mathbb{N}})] \\ a + b = [(z_{\mathbb{N}} + x_{\mathbb{N}}, w_{\mathbb{N}} + y_{\mathbb{N}})] \\ a + b = [(z_{\mathbb{N}}, w_{\mathbb{N}})] + [(x_{\mathbb{N}}, y_{\mathbb{N}})] \\ a + b = b + a \\$

8. Associativity of Addition: Prove that $(a + b) + c = a + (b + c)$ for all $a, b, c \in \mathbb{Z}$.

Let $a = [( m, n )]$, $b = [( p, q )]$, and $c = [( r, s )]$, where $m,n,p,q,r,s \in \mathbb{N}$. Then

$(a + b) + c = \left( [( m, n )] + [( p, q )] \right) + [( r, s )] \\ (a + b) + c = [( m + p, n + q )] + [( r, s )] \\ (a + b) + c = [( (m + p) + r, (n + q) + s )] \\ (a + b) + c = [( m + (p + r), n + ( q + s ) )] \\ (a + b) + c = [( m, n )] + [ ( p + r , q + s ) )] \\ (a + b) + c = [( m, n )] + \left( [ ( p, q ) ] + [ ( r, s ) ] \right) \\ (a + b) + c = a + ( b + c ) \\$

9. Cancellation Law: Give two proofs for the fact that for all $a, b, c \in \mathbb{Z}$, if $a + b = a + c$, then $b = c$. In one proof, use the corresponding cancellation law in $\mathbb{N}$; in the second proof, only use other arithmetic facts about $\mathbb{Z}$ (i.e. do not use the natural numbers.)

Proof 1: Let $a = [(x, y)]$, $b = [(u, v)]$, and $c = [(p, q)]$. Then

$a + b = [(x, y)] + [(u, v)] \\ a + b = [(x + v, u + y)] \\$

and

$a + c = [(x, y)] + [(p, q)] \\ a + c = [(x + q, p + y)] \\$

We expand $a + b = a + c$ to

$[(x + v, u + y)] = [(x + q, p + y)] \\$

By definition of $\sim$, we see that

$(x + v) + (p + y) = (x + q) + (u + y) \\ x + (v + (p + y)) = x + (q + (u + y)) \\ v + (p + y) = q + (u + y) \\ (v + p) + y = (q + u) + y \\ v + p = q + u \\ q + u = v + p \\ u + q = p + v \\$

By definition of $\sim$, we conclude that $(u, v) \sim (p, q)$ and therefore that $b = c$.

Proof 2: Simply add $-a$ to both sides:

$a + b = a + c \\ -a + (a + b) = -a + (a + c) \\ (-a + a) + b = (-a + a) + c \\ 0 + b = 0 + c \\ b = c \\$

10. Define the subtraction operation on the integers as

$$- : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$$

where

$$\left[ \left( a_{\mathbb{N}}, b_{\mathbb{N}} \right) \right] - \left[ \left( c_{\mathbb{N}}, d_{\mathbb{N}} \right) \right] = \left[ \left( a_{\mathbb{N}}, b_{\mathbb{N}} \right) \right] + \left[ \left( d_{\mathbb{N}}, c_{\mathbb{N}} \right) \right]$$

If $a - b = c$, then $c$ is called the difference between $a$ and $b$.

Compute the following differences and simplify the result from equivalence class form to integer numeral form:

1. $[(5_{\mathbb{N}},1_{\mathbb{N}})] - [(3_{\mathbb{N}},1_{\mathbb{N}})]$

2. $[(10_{\mathbb{N}},3_{\mathbb{N}})] - [(19_{\mathbb{N}},15_{\mathbb{N}})]$

3. $[(0_{\mathbb{N}},3_{\mathbb{N}})] - [(2_{\mathbb{N}},5_{\mathbb{N}})]$

4. $[(4_{\mathbb{N}},3_{\mathbb{N}})] - [(2_{\mathbb{N}},1_{\mathbb{N}})]$

1. $[(5_{\mathbb{N}}, 1_{\mathbb{N}})] - [(3_{\mathbb{N}}, 1_{\mathbb{N}})] = [(5_{\mathbb{N}}, 1_{\mathbb{N}}]) + [(1_{\mathbb{N}}, 3_{\mathbb{N}})] = [(5_{\mathbb{N}} + 1_{\mathbb{N}}, 1_{\mathbb{N}} + 3_{\mathbb{N}})] = [(6_{\mathbb{N}}, 4_{\mathbb{N}})] = 2_{\mathbb{Z}}$

2. $[(10_{\mathbb{N}}, 3_{\mathbb{N}})] - [(19_{\mathbb{N}}, 15_{\mathbb{N}})] = [(10_{\mathbb{N}}, 3_{\mathbb{N}})] + [(15_{\mathbb{N}}, 19_{\mathbb{N}})] = [(10_{\mathbb{N}} + 15_{\mathbb{N}}, 3_{\mathbb{N}} + 19_{\mathbb{N}})] = [(25_{\mathbb{N}}, 22_{\mathbb{N}})] = 3_{\mathbb{Z}}$

3. $[(0_{\mathbb{N}}, 3_{\mathbb{N}})] - [(2_{\mathbb{N}}, 5_{\mathbb{N}})] = [(0_{\mathbb{N}}, 3_{\mathbb{N}})] + [(5_{\mathbb{N}}, 2_{\mathbb{N}})] = [(0_{\mathbb{N}} + 5_{\mathbb{N}}, 3_{\mathbb{N}} + 2_{\mathbb{N}})] = [(5_{\mathbb{N}}, 5_{\mathbb{N}})] = 0_{\mathbb{Z}}$

4. $[(4_{\mathbb{N}}, 3_{\mathbb{N}})] - [(2_{\mathbb{N}}, 1_{\mathbb{N}})] = [(4_{\mathbb{N}}, 3_{\mathbb{N}})] + [(1_{\mathbb{N}}, 2_{\mathbb{N}})] = [(4_{\mathbb{N}} + 1_{\mathbb{N}}, 3_{\mathbb{N}} + 2_{\mathbb{N}})] + [(5_{\mathbb{N}}, 5_{\mathbb{N}})] = 0_{\mathbb{Z}}$

11. Show that $a + (-b) = a - b$.

Let $a = [(x, y)]$ and $b = [(u, v)]$. By definition, $-b = [(v, u)]$. Then

$a + (-b) = [(x, y)] + [(v, u)] \\ a + (-b) = [(x, y)] - [(u, v)] \\ a + (-b) = a - b \\$

12. Define the multiplication operation the integers as

$$\cdot : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$$

where

$$[(a_{\mathbb{N}}, b_{\mathbb{N}})] \cdot [(c_{\mathbb{N}}, d_{\mathbb{N}})] = [( (a_{\mathbb{N}} \cdot c_{\mathbb{N}}) + (b_{\mathbb{N}} \cdot d_{\mathbb{N}}), (a_{\mathbb{N}} \cdot d_{\mathbb{N}}) + (b_{\mathbb{N}} \cdot c_{\mathbb{N}}))]$$

1. Derive this definition of multiplication by writing the equivalence classes as "differences" of natural numbers.

2. Show that the choice of ordered pair from each equivalence class does not matter. Namely, show that if $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ that $( (a \cdot c) + (b \cdot d), (a \cdot d) + (b \cdot c) ) \sim ( (a' \cdot c') + (b' \cdot d'), (a' \cdot d') + (b' \cdot c') )$ for all $a,b,c,d,a',b',c',d' \in \mathbb{N}$.

1. The integer $[(a_{\mathbb{N}}, b_{\mathbb{N}})]$ is what we would like $a_{\mathbb{N}} - b_{\mathbb{N}}$ to represent. If we do some algebra with this aspirational representation, we get the following:

$(a_{\mathbb{N}} - b_{\mathbb{N}}) \cdot (c_{\mathbb{N}} - d_{\mathbb{N}}) = a_{\mathbb{N}} \cdot c_{\mathbb{N}} - a_{\mathbb{N}} \cdot d_{\mathbb{N}} - b_{\mathbb{N}} \cdot c_{\mathbb{N}} + b_{\mathbb{N}} \cdot d_{\mathbb{N}} \\ (a_{\mathbb{N}} - b_{\mathbb{N}}) \cdot (c_{\mathbb{N}} - d_{\mathbb{N}}) = a_{\mathbb{N}} \cdot c_{\mathbb{N}} + b_{\mathbb{N}} \cdot d_{\mathbb{N}} - a_{\mathbb{N}} \cdot d_{\mathbb{N}} - b_{\mathbb{N}} \cdot c_{\mathbb{N}} \\ (a_{\mathbb{N}} - b_{\mathbb{N}}) \cdot (c_{\mathbb{N}} - d_{\mathbb{N}}) = a_{\mathbb{N}} \cdot c_{\mathbb{N}} + b_{\mathbb{N}} \cdot d_{\mathbb{N}} - \left( a_{\mathbb{N}} \cdot d_{\mathbb{N}} + b_{\mathbb{N}} \cdot c_{\mathbb{N}} \right) \\ (a_{\mathbb{N}} - b_{\mathbb{N}}) \cdot (c_{\mathbb{N}} - d_{\mathbb{N}}) = [ \left( \left(a_{\mathbb{N}} \cdot c_{\mathbb{N}} \right) + \left( b_{\mathbb{N}} \cdot d_{\mathbb{N}} \right) , \left( a_{\mathbb{N}} \cdot d_{\mathbb{N}}\right) + \left( b_{\mathbb{N}} \cdot c_{\mathbb{N}} \right) \right)] \\$

2. If $(a, b) \sim (a', b')$, then $a + b' = a' + b$ and $[(a, b)] = [(a', b')]. Likewise, if$(c, d) \sim (c', d')$, then$c + d' = c' + d$and$[(c, d)] = [(c', d')]$. Multiplying the two respective pairs of equivalence classes together gives us$ [(a, b)] \cdot [(c, d)] = [(a \cdot c + b \cdot d, a \cdot d + c \cdot b)] \\ [(a', b')] \cdot [(c', d')] = [(a' \cdot c' + b' \cdot d', a' \cdot d' + c' \cdot b')] \\ $From the definition of$\sim$, this means that$ a \cdot c + b \cdot d = a \cdot d + c \cdot b \\ a' \cdot c' + b' \cdot d' = a' \cdot d' + c' \cdot b' \\ $Adding the two equations together gives us (a \cdot c + b \cdot d) + (a' \cdot d' + c' \cdot b') = (a \cdot d + c \cdot b) + (a' \cdot c' + b' \cdot d') \\ This then implies by definition of$\sim$that$ [(a \cdot c + b \cdot d, a \cdot d + c \cdot b)] \sim [(a' \cdot c' + b' \cdot d', a' \cdot d' + c' \cdot b')] \\ $Finally, by definition of multiplication, we concluse that$ [(a, b)] \cdot [(c, d)] \sim [(a', b')] \cdot [(c', d')] \\ $Therefore, the choice of ordered pair from each equivalence class has no effect on the outcome of the multiplication operation. 13. Calculate$[(4_{\mathbb{N}}, 1_{\mathbb{N}})] \cdot [(2_{\mathbb{N}}, 7_{\mathbb{N}})]$and simplify the result to integer numeral form.$[(4_{\mathbb{N}}, 1_{\mathbb{N}})] \cdot [(2_{\mathbb{N}}, 7_{\mathbb{N}})] = [\left( \left( 4_{\mathbb{N}} \cdot 2_{\mathbb{N}} \right) + \left(1_{\mathbb{N}} \cdot 7_{\mathbb{N}} \right), \left( 4_{\mathbb{N}} \cdot 7_{\mathbb{N}} \right) + \left( 1_{\mathbb{N}} \cdot 2_{\mathbb{N}} \right) \right) ] \\ [(4_{\mathbb{N}}, 1_{\mathbb{N}})] \cdot [(2_{\mathbb{N}}, 7_{\mathbb{N}})] = [\left( 8_{\mathbb{N}} + 7_{\mathbb{N}} , 28_{\mathbb{N}} + 2_{\mathbb{N}} \right) ] \\ [(4_{\mathbb{N}}, 1_{\mathbb{N}})] \cdot [(2_{\mathbb{N}}, 7_{\mathbb{N}})] = [\left( 15_{\mathbb{N}}, 30_{\mathbb{N}} \right) ] \\ [(4_{\mathbb{N}}, 1_{\mathbb{N}})] \cdot [(2_{\mathbb{N}}, 7_{\mathbb{N}})] = -15_{\mathbb{Z}} \\ $14. Multiplicative Identity: Show that$a \cdot 1_{\mathbb{Z}} = a$for all$a \in \mathbb{Z}$. Let$a = [(x, y)]$where$x,y \in \mathbb{N}$. By definition,$1_{\mathbb{Z}} = [(1_{\mathbb{N}}, 0_{\mathbb{N}})]$. Multiplying the two gives us$ a \cdot 1_{\mathbb{Z}} = [(x, y)] \cdot [(1_{\mathbb{N}}, 0_{\mathbb{N}})] \\ a \cdot 1_{\mathbb{Z}} = [((x \cdot 1_{\mathbb{N}}) + (y \cdot 0_{\mathbb{N}}), (x \cdot 0_{\mathbb{N}}) + (y \cdot 1_{\mathbb{N}}))] \\ a \cdot 1_{\mathbb{Z}} = [(x + 0, 0 + y)] \\ a \cdot 1_{\mathbb{Z}} = [(x, y)] \\ a \cdot 1_{\mathbb{Z}} = a \\ $15. Show that$a \cdot 0_{\mathbb{Z}} = 0_{\mathbb{Z}}$for all$a \in \mathbb{Z}$. Let$a = [(x, y)]$, where$x, y \in \mathbb{N}$. Then$ a \cdot 0_{\mathbb{Z}} = [(x, y)] \cdot [(0_{\mathbb{N}}, 0_{\mathbb{N}})] \\ a \cdot 0_{\mathbb{Z}} = [(x \cdot 0_{\mathbb{N}} + y \cdot 0_{\mathbb{N}}, x \cdot 0_{\mathbb{N}} + y \cdot 0_{\mathbb{N}})] \\ a \cdot 0_{\mathbb{Z}} = [(0_{\mathbb{N}} + 0_{\mathbb{N}}, 0_{\mathbb{N}} + 0_{\mathbb{N}})] \\ a \cdot 0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})] \\ a \cdot 0_{\mathbb{Z}} = 0_{\mathbb{Z}} \\ $16. Show that$-(-a) = a$Let$a = [(x, y)]$. By definition,$-a = [(y, x)]$, and once again$-(-a) = [(x,y)]$. Thus$-(-a) = a$. 17. Show that$-1 \cdot a = -a$. Let$a = [(x, y)]$, where$x, y \in \mathbb{N}$. Then$ -1 \cdot a = [(0,1)] \cdot [(x, y)] \\ -1 \cdot a = [( (0 \cdot x) + (1 \cdot y),(0 \cdot y) + (1 \cdot x) )] \\ -1 \cdot a = [( 0 + y, 0 + x )] \\ -1 \cdot a = [( y, x )] \\ -1 \cdot a = -a \\ $18. Commutativity of Multiplication: Show that$a \cdot b = b \cdot a$. Let$a = [(x, y)]$and$b = [(u, v)]$, where$x,y,u,v \in \mathbb{N}$. Then$ a \cdot b = [(x,y)] \cdot [(u,v)] \\ a \cdot b = [( (x \cdot u) + (y \cdot v), (x \cdot v) + (y \cdot u) )] \\ a \cdot b = [( (u \cdot x) + (v \cdot y), (v \cdot x) + (u \cdot y) )] \\ a \cdot b = [(u,v)] \cdot [(x,y)] \\ a \cdot b = b \cdot a \\ $19. Associativity of Multiplication: Show that$a \cdot ( b \cdot c ) = (a \cdot b) \cdot c$. You can probably sense where this is going by now... Let$a = [(x, y)]$,$b = [(u, v)]$, and$c = [(p,q)]$, where$x,y,u,v,p,q \in \mathbb{N}$. Then$ \begin{array}{lcl} a \cdot ( b \cdot c ) & = & [(x, y)] \cdot ([(u, v)] \cdot [(p,q)] ) \\ a \cdot ( b \cdot c ) & = & [(x, y)] \cdot [( u \cdot p + v \cdot q, u \cdot q + v \cdot p )] \\ a \cdot ( b \cdot c ) & = & [( x \cdot (u \cdot p + v \cdot q) + y \cdot ( u \cdot q + v \cdot p ) , \\ \, & \, & \, x \cdot (u \cdot q + v \cdot p) + y \cdot (u \cdot p + v \cdot q) )] \\ a \cdot ( b \cdot c ) & = & [( x \cdot (u \cdot p) + x \cdot(v \cdot q) + y \cdot (u \cdot q) + y \cdot (v \cdot p ) , \\ \, & \, & \, x \cdot (u \cdot q) + x \cdot (v \cdot p) + y \cdot (u \cdot p) + y \cdot (v \cdot q) )] \\ a \cdot ( b \cdot c ) & = & [( (x \cdot u) \cdot p + (x \cdot v) \cdot q + (y \cdot u) \cdot q + (y \cdot v) \cdot p , \\ \, & \, & \, (x \cdot u) \cdot q + (x \cdot v) \cdot p + (y \cdot u) \cdot p + (y \cdot v) \cdot q )] \\ a \cdot ( b \cdot c ) & = & [( (x \cdot u + y \cdot v) \cdot p + (x \cdot v + y \cdot u) \cdot q, \\ \, & \, & \, (x \cdot u + y \cdot v) \cdot q + (x \cdot v + y \cdot u) \cdot p )] \\ a \cdot ( b \cdot c ) & = & [( x \cdot u + y \cdot v , x \cdot v + y \cdot u )] \cdot [(p,q)] \\ a \cdot ( b \cdot c ) & = & \left( [(x, y)] \cdot [(u,v)] \right) \cdot [(p,q)] \\ a \cdot ( b \cdot c ) & = & \left( a \cdot b \right) \cdot c \\ \end{array} $20. Distributive Law: Show that$a \cdot (b + c) = a \cdot b + a \cdot c$. Let$a = [(x, y)]$,$b=[(u, v)]$, and$c=[(p, q)]$, where$x,y,u,v,p,q \in \mathbb{N}$. Then$ a \cdot ( b + c ) = [(x, y)] \cdot ( [(u, v)] + [(p, q)] ) \\ a \cdot ( b + c ) = [(x, y)] \cdot [(u + p, v + q)] \\ a \cdot ( b + c ) = [( x \cdot (u + p) + y \cdot (v + q), x \cdot(v + q) + y \cdot (u + p) )] \\ a \cdot ( b + c ) = [( x \cdot u + x \cdot p + y \cdot v + y \cdot q, x \cdot v + x \cdot q + y \cdot u + y \cdot p )] \\ a \cdot ( b + c ) = [( x \cdot u + y \cdot v + x \cdot p + y \cdot q, x \cdot v + y \cdot u + x \cdot q + y \cdot p )] \\ a \cdot ( b + c ) = [(x \cdot u + y \cdot v, x \cdot v + y \cdot u)] + [(x \cdot p + y \cdot q, x \cdot q + y \cdot p)] \\ a \cdot ( b + c ) = [(x, y)] \cdot [(u, v)] + [(x, y)] \cdot [(p, q)] \\ a \cdot ( b + c ) = a \cdot b + a \cdot c \\ $21. Define the ordering$<$on$\mathbb{Z}$as $$[(a,b)] < [(c,d)] \text{ iff } a + d < c + b,$$ where$a,b,c,d \in \mathbb{N}$. Prove that$<$is in fact an order relation. 1. Comparability: Let$[(a, b)], [(c, d)] \in \mathbb{Z}$, where$[(a, b)] \neq [(c, d)]$. Then by comparability on$\mathbb{N}$, either$a + d < c + b$or$c + b < a + d$. Therefore either$[(a, b)] < [(c, d)]$or$[(c, d)] < [(a, b)]$. 2. Nonreflexivity: Let$[(a, b)] \in \mathbb{Z}$. If$[(a, b)] < [(a, b)]$, then$a + b < a + b$. But this violates nonreflexivity on$\mathbb{N}$. Thus for no$x \in \mathbb{Z}$is it true that$x < x$. 3. Transitivity: Assume$x, y, z \in \mathbb{Z}$, and that$x < y$and$y < z$. Let$x = [(a, b)]$,$y = [(c, d)]$, and$z = [(e, f)]$, where$a,b,c,d,e,f \in \mathbb{N}$. Then we see that$a + d < c + b$and$c + f < e + d$. Adding$f$to both sides of the first inequality and$b$to both sides of the second gives us$a + d + f < c + b + f$and$c + f + b < e + d + b$. By transitivity on$\mathbb{N}$, we see that$a + d + f < e + d + b$Applying the cancellation law on$\mathbb{N}$gives us the desired result:$a + f < e + b$Therefore$x < z$. 22. The sign of an integer is its status as either a positive or negative number: 1. The positive integers are all integers of the form$a_{\mathbb{Z}} = [(a_{\mathbb{N}}, 0_{\mathbb{N}})]$, where$a_{\mathbb{N}} > 0_{\mathbb{N}}$. Show an integer is positive if and only if it is greater than zero. 2. The negative integers are all integers of the form$a_{\mathbb{Z}} = [(0_{\mathbb{N}}, a_{\mathbb{N}})]$, where$a_{\mathbb{N}} > 0_{\mathbb{N}}$. Show that an integer is negative if and only if it is less than zero. 3. Show that$0_{\mathbb{Z}}$is neither positive nor negative. 1. Let$a_{\mathbb{Z}}$be positive such that$a_{\mathbb{Z}} = [(a_{\mathbb{N}}, 0_{\mathbb{N}})]$, where$a_{\mathbb{N}} > 0_{\mathbb{N}}$. Recall that$0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$. By using the definition of the order relation on$\mathbb{Z}$, we see that$0_{\mathbb{N}} + 0_{\mathbb{N}} < a_{\mathbb{N}} + 0_{\mathbb{N}}$, and that therefore$0_{\mathbb{Z}} < a_{\mathbb{Z}}$. Conversely, let$a_{\mathbb{Z}} = [(x_{\mathbb{N}}, y_{\mathbb{N}})]$and assume that$0_{\mathbb{Z}} < a_{\mathbb{Z}}$. By the definition of the order relation on$\mathbb{Z}$,$0_{\mathbb{N}} + y_{\mathbb{N}} < x_{\mathbb{N}} + 0_{\mathbb{N}}$, so$y_{\mathbb{N}} < x_{\mathbb{N}}$. Therefore there exists a nonzero$a_{\mathbb{N}}$such that$y_{\mathbb{N}} + a_{\mathbb{N}} = x_{\mathbb{N}}$. Then$x_{\mathbb{N}} + 0_{\mathbb{N}} = a_{\mathbb{N}} + y_{\mathbb{N}}$, and therefore$[(x_{\mathbb{N}}, y_{\mathbb{N}})] = [(a_{\mathbb{N}}, 0_{\mathbb{N}})]$. Thus$a_{\mathbb{Z}}$is positive. 2. Let$a_{\mathbb{Z}}$be negative such that$a_{\mathbb{Z}} = [(0_{\mathbb{N}}, a_{\mathbb{N}})]$, where$a_{\mathbb{N}} > 0_{\mathbb{N}}$. Recall that$0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$. By using the definition of the order relation on$\mathbb{Z}$, we see that$0_{\mathbb{N}} + a_{\mathbb{N}} < 0_{\mathbb{N}} + 0_{\mathbb{N}}$, and that therefore$a_{\mathbb{Z}} < 0_{\mathbb{Z}}$. Conversely, let$a_{\mathbb{Z}} = [(x_{\mathbb{N}}, y_{\mathbb{N}})]$and assume that$a_{\mathbb{Z}} < 0_{\mathbb{Z}}$. By the definition of the order relation on$\mathbb{Z}$,$x_{\mathbb{N}} + 0_{\mathbb{N}} < 0_{\mathbb{N}} + y_{\mathbb{N}}$, so$x_{\mathbb{N}} < y_{\mathbb{N}}$. Therefore there exists a nonzero$a_{\mathbb{N}}$such that$x_{\mathbb{N}} + a_{\mathbb{N}} = y_{\mathbb{N}}$. Then$x_{\mathbb{N}} + a_{\mathbb{N}} = 0_{\mathbb{N}} + y_{\mathbb{N}}$, and therefore$[(x_{\mathbb{N}}, y_{\mathbb{N}})] = [(0_{\mathbb{N}}, a_{\mathbb{N}})]$. Thus$a_{\mathbb{Z}}$is negative. 3. Recall that$0_{\mathbb{Z}} = [(0_{\mathbb{N}}, 0_{\mathbb{N}})]$. Note that$0_{\mathbb{Z}}$cannot be positive, as that would imply that$0_{\mathbb{N}}$is nonzero, which is a contradiction. Likewise,$0_{\mathbb{Z}}$cannot be negative, as that would also imply that$0_{\mathbb{N}}$is nonzero, which is a contradiction. 23. The non-negative integers$0, 1, 2, \ldots \in \mathbb{Z}$are quite similar to the natural numbers$0, 1, 2, \ldots \in \mathbb{N}$. Addition and multiplication work the same for both sets, as do the ordering properties. We often don't strictly distinguish between integers and natural numbers in practice, and in fact plenty of mathematicians would insist that$\mathbb{N} \subset \mathbb{Z}$, despite the fact that this is clearly not the case based on our construction of them here. But if the two sets do behave identically (which they do), is there really a meaningful difference? Should there be a difference? The first step towards a solution to this issue is to properly identify what the issue is in the first place. The issue comes in two parts. The first part is descriptive: there's a subset of$\mathbb{Z}$that behaves exactly like$\mathbb{N}$, and the fact that they're not actually the same set bothers us. The second part is prescriptive: we shouldn't make a distinction between either set in the first place. Mathematics involves formalizing our ideas into rigorous logical statements. We need to formalize the concept of "the distinction between these sets is formally of no consequence." Thus we will build a bridge between the two sets that will allow us to conclude that any statement proven about one set is therefore true of the other set. Such a bridge is called an embedding. An embedding is an injective function that maps one set into another such that properties in one set are preserved as properties in the other. This definition is not precise, as different fields of mathematics have their own particular meaning for the term. Nevertheless, the heart of the idea is consistent, and we present here the canonical embedding of$\mathbb{N}$into$\mathbb{Z}$. Let$E : \mathbb{N} \rightarrow{M}$be a function such that$E(a_{\mathbb{N}}) = [(a_{\mathbb{N}}, 0)]$. Prove that$E$is an embedding of$(\mathbb{N}, +, \cdot, <)$into$(\mathbb{Z}, +, \cdot, <)$. Namely, prove that 1. Injectivity:$E$is injective. 2. Addition is preserved:$E(x + y) = E(x) + E(y) \\$3. Multiplication is preserved:$E(x \cdot y) = E(x) \cdot E(y) \\$4. Order is preserved:$x < y \Longleftrightarrow E(x) < E(y) \\$1.$E$is injective if$E(a) = E(b)$implies that$a = b$. Assume$E(a) = E(b)$. Then$[(a, 0)] = [(b, 0)]$. Therefore$a + 0 = b + 0$, which simplifies to$a = b$as desired. 2.$E(x + y) = [(x + y, 0)] \\ E(x + y) = [(x + y, 0 + 0)] \\ E(x + y) = [(x, 0)] + [(y, 0)] \\ E(x + y) = E(x) + E(y) \\ $3.$ E(x \cdot y) = [(x \cdot y, 0)] \\ E(x \cdot y) = [((x \cdot y) + (0 \cdot 0), (0 \cdot 0) + (0 \cdot 0))] \\ E(x \cdot y) = [(x, 0)] \cdot [(y, 0)] \\ E(x \cdot y) = E(x) \cdot E(y) \\$4.$\implies$Assume$x < y$. Then$x + 0 < y + 0$, and thus$[(x, 0)] < [(y, 0)]$, and therefore$E(x) < E(y)$.$\impliedby$Assume$E(x) < E(y)$. Then$[(x, 0)] < [(y, 0)]$, so$x + 0 < y + 0$, and therefore$x < y$. 24. Using the above definition of the embedding function$E : \mathbb{N} \rightarrow \mathbb{Z}$, show that$E(a) - E(b) = [(a, b)]$for all$a, b \in \mathbb{N}$.$ E(a) - E(b) = [(a, 0)] - [(b, 0)] \\ E(a) - E(b) = [(a, 0)] + [(0, b)] \\ E(a) - E(b) = [(a + 0, 0 + b)] \\ E(a) - E(b) = [(a, b)] \\ \$