Naive Set Theory: Number Systems

Integers


Motivation: Subtraction

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.

Axiomatic Definition of the Integers

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.

But before we go about constructing anything, we need to formalize the properties we want our new set of numbers to end up with. We now state the axioms of the integers.

The integers are the set, denoted by $\mathbb{Z}$, that has the following properties:

  • $\mathbb{Z}$ is closed under the addition operation, $+ : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$, which has the following properties:

    • Associativity of addition: For all $a, b, c \in \mathbb{Z}$, $a + (b + a) = (a + b) + c$.
    • Commutativity of addition: For all $a, b \in \mathbb{Z}$, $a + b = b + a$.
    • Additive identity: There exists an element $0 \in \mathbb{Z}$ such that $a + 0 = a$ for all $a \in \mathbb{Z}$.
    • Additive inverse: For all $a \in \mathbb{Z}$, there exists an element $-a$ such that $a + (-a) = 0$.
  • $\mathbb{Z}$ is closed under the multiplication operations, $\cdot : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$, which has the following properties:

    • Associativity of multiplication: For all $a, b, c \in \mathbb{Z}$, $a \cdot (b \cdot c) = (a \cdot b) \cdot c$.
    • Commutativity of multiplication: For all $a, b \in \mathbb{Z}$, $a \cdot b = b \cdot a$.
    • Multiplicative identity: There exists an element $1 \in \mathbb{Z}$ such that $a \cdot 1 = a$ for all $a \in \mathbb{Z}$.
  • Distributive property: $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ for all $a, b, c \in \mathbb{Z}$

  • $\mathbb{Z}$ algebraically contains* $\mathbb{N}$:

    • $\mathbb{N} \subset \mathbb{Z}$.
    • Addition on $\mathbb{N}$ is the restriction of addition on $\mathbb{Z}$ to $\mathbb{N}$.
    • Multiplication on $\mathbb{N}$ is the restriction of multiplication on $\mathbb{Z}$ to $\mathbb{N}$.
  • There exists a total order relation $<$ on $\mathbb{Z}$ with the following properties:

    • Terminology: If $0 < a$, then $a$ is called positive. If $a < 0$, then $a$ is called negative$. $0$ is neither positive nor negative.
    • Addition of positives is positive: For all positive $a, b \in \mathbb{Z}$, $a + b > 0$.
    • Multiplication of positives is positive: For all positive $a, b \in \mathbb{Z}$, $a \cdot b > 0$.

* The use of the word "contains" here is important. In our set theoretic construction, $\mathbb{N}$ will not, in fact, be a subset of $\mathbb{Z}$. However, the important fact is that $\mathbb{Z}$ will contain an embedding of $\mathbb{N}$, which is a copy of $\mathbb{N}$ that behaves exactly like $\mathbb{N}$ by adhering to the same algebraic and ordering properties. Since these two "copies" of $\mathbb{N}$ behave identically, it is a matter of philosophy whether there is any meaningful mathematical difference between them beyond their constructions. This embedding is left as a later exercise. In general, $\mathbb{N}$ is treated as a subset of $\mathbb{Z}$.

Construction

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$.

Notation

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 set theoretic 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. In fact, the idea that there is any meaningful difference at all is one you're not likely to find outside of set theory.

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 axiomatic arithmetic and ordering properties for this construction of the integers are 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.

    Show Answer
  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}}$.

    Show Answer
  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')$

    Show Answer
  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}}$

    Show Answer
  5. 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 ) \\ $

    Show Answer
  6. 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 \\ $

    Show Answer
  7. 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 \\ $

    Show Answer
  8. 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}}$.

    Show Answer
  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 \\ $

    Show Answer
  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}}$

    Show Answer
  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 \\ $

    Show Answer
  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 conclude 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.

    Show Answer
  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}} \\ $

    Show Answer
  14. 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} $

    Show Answer
  15. 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 \\ $

    Show Answer
  16. 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 \\ $

    Show Answer
  17. 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}} \\ $

    Show Answer
  18. Show that $-(-a) = a$

    Let $a = [(x, y)]$. By definition, $-a = [(y, x)]$, and once again $-(-a) = [(x,y)]$. Thus $-(-a) = a$.

    Show Answer
  19. 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 \\ $

    Show Answer
  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 \\ $

    Show Answer
  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$.

    Show Answer
  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.

    Show Answer
  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$.

    Show Answer
  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)] \\ $

    Show Answer