Naive Set Theory: The Natural Numbers

Arithmetic


The previous section constructed the set of natural numbers, $\mathbb{N}$. This section will define some of the standard arithmetic on $\mathbb{N}$ by way of manipulating the von Neumann ordinals.

Addition

Define the addition operation on $\mathbb{N}$ as $+ : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ where

$$+(a, b) = \left\{ \begin{array}{cl} a & b = 0 \\ (+(a, n))^+& b = n^+, \text{ where } n \in \mathbb{N} \end{array} \right.$$

The notation here is positively byzantine, but we can break it down. The addition function, $+$, takes in two natural numbers and produces a single natural number. The case for when $b=0$ is simple enough - just return $a$. The second case is tricky because it is defined recursively. It says that if $b$ is equal to the successor of some other natural number $n$, then the addition function $+$ returns the successor of the sum of $a$ with that other element $n$. Since we're not sadists here, we will dispense with the Feynman algorithm and illustrate with an example.

Consider the case of $+(5, b)$, starting with $b=0$. The first case shows that $+(5,0) = 5$. How about when $b=1$? We can see that $1$ is the successor of $0$, so $1 = n^+$ means that $n = 0$. Therefore we compute $+(5, 0)=5$, then take its successor. $(+(5,0))^+ = 5^+ = 6$. Thus we see that $+(5,1) = 6$, as we might expect. Repeating this process again shows that that $+(5, 2) = 7$.

Remember that binary operations of the form $\circ : A^- \rightarrow A$ are not written like usual functions as $\circ(a,b)$ but instead in the more familiar algebraic format of $a \circ b$. As such, we can relieve ourselves of the burden of writing ghastly inscriptions like $+(5,2)$ once we have sufficiently hashed out their construction from more functions.

It is important to note that we have only defined the addition operation for $\mathbb{N}$. We have not demonstrated any properties of it, such as the fact that $a + b = b + a$. These properties must be shown to follow from the definition, and the chief way to demonstrate these properties is via induction. However, once you prove these familiar properties in the exercises, you can feel free to use facts like $(1+2)+3=1+(3+2)=6$.

Note on Addition: You may have noticed that the addition function is defined recursively (i.e. that it is defined in terms of itself). A more rigorous treatment of set theory will demand that this function be proven to exist in the first place. The Recursion Theorem on the Natural Numbers allows us to safely assume the existence of recursively defined functions, such as the one here for addition.


Problems

  1. Prove that $a + b^+ = (a + b)^+$.

    The proof here is really a matter of interpreting the definition and alternative notation of the $+$ operator.

    $a + b^+ = +(a,b^+) \\ a + b^+ = (+(a,b))^+ \\ a + b^+ = (a + b)^+ \\$

    Show Answer
  2. Show that $0 + n = n$ for all $n \in \mathbb{N}$.

    Note: The fact that $n + 0 = n$ for all $n \in \mathbb{N}$ follows directly from the definition of addition. The statement $0 + n = n$ does not.

    We'll walk through this first proof by induction with extra caution. Subsequent proofs can then be accorded less exposition.

    Proof by induction. Let $S$ be the set of natural numbers $n$ such that $0 + n = n$. Formally, let $S = \{ n \in \mathbb{N} : 0 + n = n \}$. By using the Principle of Mathematical Induction, if we show that $S$ is an inductive subset of $\mathbb{N}$, we will show that in fact $S = \mathbb{N}$.

    First we must establish that $S$ is a subset of $\mathbb{N}$. This is true by our definition of $S$.

    Next we must establish that $\mathbb{N}$ is an inductive set. To do this we must show that $0 \in S$ and that $a \in S$ implies $a^+ \in S$.

    To fulfill the first condition, we show that $0 + 0 = 0$. This fact follows directly from the first case in the definition of the addition operator, namely that $a + 0 = a$ for all $a \in \mathbb{N}$. Letting $a = 0$, we see that $0 + 0 = 0$.

    To fulfill the second condition, we show that $a \in S$ implies that $a^+ \in S$. Assume that $n \in S$. By the definition of $S$, we see that $0 + n = n$. Taking the successor of both sides shows that $(0 + n)^+ = n^+$. By the equivalence proved in the previous problem, $(0 + n)^+ = 0 + n^+$. Therefore $0 + n^+ = n^+$. Therefore $n^+ \in S$. Thus $S$ in an inductive subset of $\mathbb{N}$, which by the principle of mathematical induction proves that $S = \mathbb{N}$. Therefore $0 + n = n$ for all $n \in \mathbb{N}$.

    Show Answer
  3. Prove that $a^+ + b = a + b^+$ for all $a, b \in \mathbb{N}$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : b^+ + n = b + n^+ \text{ for all } b \in \mathbb{N} \}$.

    Base case: By the definition of addition, $b^+ + 0 = b^+$. Likewise, $b + 0^+ = b + 1 = +(b, 1) = (+(b,0))^+ = b^+$. Therefore $b^+ + 0 = b + 0^+$.

    Inductive step: Assume that $b^+ + k = b + k^+$ for all $k \in \{0, \ldots, n\}$. Then $(b^+ + n)^+ = (b + n^+)^+$. By applying the identity $(a + b)^+ = a + b^+$ (as proven in an earlier exercise) to both sides, we see that $b^+ + n^+ = b + n^{++}$. Therefore $b^+ + n = b + n^+$ implies $b^+ + n^+ = b + n^{++}$.

    Therefore, by the Principle of Mathematical Induction, $S = \mathbb{N}$, and $a^+ + b = a + b^+$ for all $a, b \in \mathbb{N}$.

    Show Answer
  4. Show $a + 1 = a^+$.

    $ a + 1 = a + 0^+ \\ a + 1 = a^+ + 0 \\ a + 1 = a^+ \\ $

    Show Answer
  5. Commutativity of Addition: Prove that $a + b = b + a$ for all $a, b \in \mathbb{N}$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : n + b = b + n \text{ for all } b \in \mathbb{N} \}$.

    Base case: Let $n = 0$ and let $b \in \mathbb{N}$. By the definition of addition, $b + 0 = b$. Likewise by the above proof, $0 + b = b$. Thus $0 + b = b + 0$.

    Inductive step: Assume $n + b = b + n$ for all $a \in \{0, \ldots, n\}$. Then

    $n + b = b + n \\ (n + b)^+ = (b + n)^+ \\ n + b^+ = b + n^+ \\ n^+ + b = b + n^+ \\ $

    The last step follows as a result of exercise 4 above. Therefore, by the Principle of Mathematical Induction, $S = \mathbb{N}$, and $a + b = b + a$ for all $a, b \in \mathbb{N}$.

    Show Answer
  6. Associativity of Addition: Prove that $(a + b) + c = a + (b + c)$.

    Note: Remember that the notation $(a \circ b) \circ c$ is translates back into standard function notation as $\circ(\circ(a, b), c)$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : (a + b) + n = a + (b + n) \}$.

    Base case: Let $n = 0$. Then by the definition of addition, $(a + b) + 0 = a + b$. Likewise by the definition of addition, $b = b + 0$, so $a + b = a + (b + 0)$. Thus $(a + b) + 0 = a + (b + 0)$, and therefore $0 \in S$.

    Inductive step: Assume $n \in S$. Then

    $ (a + b) + n = a + (b + n) \\ ((a + b) + n)^+ = (a + (b + n))^+ \\ (a + b) + n^+ = a + (b + n)^+ \\ (a + b) + n^+ = a + (b + n^+) \\ $

    Thus we have $n \in S$ implies $n^+ \in S$. By induction, $S = \mathbb{N}$. Thus we have shown that addition on the natural numbers is associative.

    Show Answer
  7. Cancellation Law: Prove that if $b + a = c + a$, then $b = c$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : a + n = b + n \text{implies} $a = b$ \text{ where } a, b \in \mathbb{N} \}$

    Base case: We see that $a + 0 = a$, and $b + 0 = b$, thus if $a + 0 = b + 0$, it follows that $ a = b$. Therefore $0 \in \mathbb{N}.

    Inductive step: Assume $n \in S$, and assume that $a + n^+ = b + n^+$. Then

    $ a + n^+ = b + n^+ \\ (a + n)^+ = (b + n)^+ \\ a + n = b + n \\ a = b \\ $

    Therefore $n^+ \in S$, so the result follows by induction.

    Show Answer
  8. Create a definition for the multiplication operation on the natural numbers $\cdot : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. The output multiplication operation is also called the product of its two inputs. Write out the products of $3$ with the first four natural numbers to show it working.

    Hint: Channel your elementary school education in multiplication. Recursively define multiplication in terms of addition.

    Define the multiplication operation $\cdot : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ as:

    $$ \cdot(a, b) : \left\{ \begin{array}{cl} 0 & b = 0 \\ +(a, \cdot(a, n)) & b = n^+ \text{ where } n \in \mathbb{N} \\ \end{array} \right. $$

    Here are the calculations for the first four products of $3$:

    • $3 \cdot 0 = 0$ by definition.

    • $ 3 \cdot 1 = \cdot(3,1) \\ 3 \cdot 1 = +(3, \cdot(3, 0)) \\ 3 \cdot 1 = +(3, 0) \\ 3 \cdot 1 = 3 \\ $

    • $ 3 \cdot 2 = \cdot(3,2) \\ 3 \cdot 2 = +(3, \cdot(3, 1)) \\ 3 \cdot 2 = +(3, 3) \\ 3 \cdot 2 = 6 \\ $

    • $ 3 \cdot 3 = \cdot(3,3) \\ 3 \cdot 3 = +(3, \cdot(3, 2)) \\ 3 \cdot 3 = +(3, 6) \\ 3 \cdot 3 = 9 \\ $

    Show Answer
  9. Prove that $0 \cdot n = 0$ for all $n \in \mathbb{N}$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : 0 \cdot n = 0 \}$.

    Base case: Let $n = 0$. By definition of multiplication, $0 \cdot 0 = 0$.

    Inductive step: Assume $n \in S$. Then

    $ 0 \cdot n^+ = \cdot(0, n^+) \\ 0 \cdot n^+ = +(0, \cdot(0, n)) \\ 0 \cdot n^+ = +(0, 0) \\ 0 \cdot n^+ = 0 \\ $

    Thus $n^+ \in S$, and the result follows by induction.

    Show Answer
  10. Prove that for $a, b \in \mathbb{N}$, if $a \cdot b = 0$, then either $a = 0$ or $b = 0$, or both.

    If you tried proving that if either $a$ or $b$ is zero then their product is zero, then you proved the wrong implication. The question here is whether the reverse implication is true. Namely, if $a \cdot b = 0$, must it be true that at least one of $a$ or $b$ is $0$? Or could it be the case that there are two nonzero numbers whose product is still somehow zero? We show that at least one of them must be zero.

    Proof by contradiction. Let $a, b \in \mathbb{N}$ such that $a \cdot b = 0$, and assume that $a \neq 0$ and $b \neq 0$. Since both $a$ and $b$ are nonzero, they must be the successors to some other numbers, call them $p$ and $q$, so that $a = p^+$ and $b = q^+$. Then

    $ a \cdot b = 0 \\ p^+ \cdot q^+ = 0 \\ (p^+ \cdot q) + p^+ = 0 \\ ((p^+ \cdot q) + p)^+ = 0 \\ $

    But this is a contradiction, because $0$ is not the successor to any natural number. Therefore it cannot be the case that both $a$ and $b$ are nonzero.

    Show Answer
  11. Distributive Law: Prove that $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$

    Base case: Let $n = 0$. Then $a \cdot (b + 0) = a \cdot b$, and $(a \cdot b) + (a \cdot 0) = (a \cdot b) + 0 = a \cdot b$. Thus $0 \in S$

    Inductive step: Suppose $k \in S$. Then

    $ a \cdot (b + k^+) = a \cdot (b + k)^+ \\ a \cdot (b + k^+) = (a \cdot (b + k)) + a \\ a \cdot (b + k^+) = ((a \cdot b) + (a \cdot k)) + a \\ a \cdot (b + k^+) = (a \cdot b) + ((a \cdot k) + a) \\ a \cdot (b + k^+) = (a \cdot b) + (a \cdot k^+) \\ $

    Thus $k \in S$ implies $k^+ \in S$, so the result follows by induction.

    Show Answer
  12. Associativity of Multiplication: Prove $a \cdot (b \cdot c) = (a \cdot b) \cdot c$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : a \cdot (b \cdot n) = (a \cdot b) \cdot n \}$.

    Base case: Let $n = 0$. Then $a \cdot (b \cdot 0) = a \cdot 0 = 0$, and $(a \cdot b) \cdot 0 = 0$, so $0 \in S$.

    Inductive step: Suppose $k \in S$. Then

    $ a \cdot (b \cdot k^+) = a \cdot ( (b \cdot k) + b ) \\ a \cdot (b \cdot k^+) = (a \cdot (b \cdot k)) + (a \cdot b) \\ a \cdot (b \cdot k^+) = ((a \cdot b) \cdot k) + (a \cdot b) \\ a \cdot (b \cdot k^+) = (a \cdot b) \cdot k^+ \\ $

    Thus $k \in S$ implies $k^+ \in S$, so the result follows by induction.

    Show Answer
  13. Prove that $a^+ \cdot b = (a \cdot b) + b$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : a^+ \cdot n = (a \cdot n) + n \}$

    Base case: Let $n = 0$. Then $a^+ \cdot 0 = 0$, and $(a \cdot 0) + 0 = a \cdot 0 = 0$, so $a^+ \cdot 0 = (a \cdot 0) + 0$, therefore $0 \in S$.

    Inductive step: Assume $k \in S$. Then

    $ a^+ \cdot k^+ = a^+ + (a^+ \cdot k) \\ a^+ \cdot k^+ = a^+ + ((a \cdot k) + k) \\ a^+ \cdot k^+ = a^+ + (k + (a \cdot k)) \\ a^+ \cdot k^+ = (a^+ + k) + (a \cdot k) \\ a^+ \cdot k^+ = (a + k^+) + (a \cdot k) \\ a^+ \cdot k^+ = (k^+ + a) + (a \cdot k) \\ a^+ \cdot k^+ = k^+ + (a + (a \cdot k)) \\ a^+ \cdot k^+ = k^+ + (a \cdot k^+) \\ a^+ \cdot k^+ = (a \cdot k^+) + k^+ \\ $

    Thus $k \in S$ implies $k^+ \in S$, so the result follows by induction.

    Show Answer
  14. Commutativity of Multiplication: Prove that $a \cdot b = b \cdot a$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : a \cdot n = n \cdot a \}$

    Base case: Let $n = 0$. Then $a \cdot 0 = 0$, and $0 \cdot a = 0$, so $0 \in S$.

    Inductive step: Assume $k \in S$. Then

    $ a \cdot k^+ = a + (a \cdot k) \\ a \cdot k^+ = a + (k \cdot a) \\ a \cdot k^+ = (k \cdot a) + a \\ a \cdot k^+ = k^+ \cdot a \\ $

    Thus the result follows by induction.

    Show Answer
  15. Multiplicative Identity: Prove that $n \cdot 1 = n$ for all $n \in \mathbb{N}$.

    $ n \cdot 1 = n + (n \cdot 0) \\ n \cdot 1 = n + 0 \\ n \cdot 1 = n \\ $

    Show Answer
  16. Disprove the following statement: If $a \cdot b = a \cdot c$, then $b = c$.

    Let $a = 0$, $b = 1$, and $c = 2$. Then $a \cdot b = 0 \cdot 1 = 0$ and $a \cdot c = 0 \cdot 2 = 0$. Therefore $a \cdot b = a \cdot c$, but $b \neq c$.

    Show Answer
  17. Cancellation Law: Prove that if $a \neq 0$, and $a \cdot b = a \cdot c$, then $b = c$.

    Proof by induction. Let $S = \{ n \in \mathbb{N} : n^+ \cdot b = n^+ \cdot c \implies b = c \text{ for all } b, c \in \mathbb{N} \}$

    Base case: Let $n = 0$, and assume $n^+ \cdot b = n^+ \cdot c$. Then $n^+ \cdot b = 1 \cdot b = b$, and $n^+ \cdot c = 1 \cdot c = c$. Therefore $b = c$.

    Inductive case: Assume $n \in S$. To determine if $n^+ \in S$, we assume $n^{++} \cdot b = n^{++} \cdot c$ and check that this implies $b = c$. Then

    $ n^{++} \cdot b = n^{++} \cdot c \\ b + ( n^+ \cdot b ) = c + ( n^+ \cdot c ) \\ b + ( n^+ \cdot b ) = c + ( n^+ \cdot b ) \\ b = c \\ $

    Thus $n^+ \in S$ and the result follows by induction.

    Show Answer