Naive Set Theory: The Natural Numbers
Ordering the Natural Numbers
So far we have constructed the natural numbers and defined and proven some properties about arithmetic functions on them. Now we define an ordering for the natural numbers.
A natural number $a$ is less than another natural number $b$ if $a \in b$. Using our formal definition of order relations, we define the ordering on $\mathbb{N}$ as
$$< \, \, = \{ (a,b) : a, b \in \mathbb{N} \text{ and } a \in b \}$$
Recall that every natural number is constructed out of von Neumann ordinals, such that $n+1 = \{0, \ldots, n\}$. For example, $3 = \{0, 1, 2\}$. How convenient for implementing a less-than relationship! The numbers $0$, $1$, and $2$ are all elements of $3$, but $3$ is not itself an element of $3$, and nothing greater than $3$ is an element of $3$.
Problems
Show that $a \in b$ if and only if $a^+ \in b^+$.
$\implies$: Proof by induction. Let $S = \{ n \in \mathbb{N} : m^+ \in n^+ \text{ for all } m \in n \}$.
Base case: $0 \in S$, as there are no elements in $0$, so all of their successors are in $0^+=1$.
Inductive step: Assume $k \in S$. We must show that if $m \in k^+$, then $m^+ \in k^{++}$. Assume $m \in k^+$. Then $m \in k \cup \{k\}$, so either $m \in k$ or $m = k$. If $m \in k$, then by the inductive hypothesis $m^+ \in k^+$. Because $k^+ \subseteq k^{++}$, we have $m^+ \in k^{++}$. Alternatively, if $m = k$, then $m^+ = k^+$. Because $k^+ \in k^{++}$, it follows that $m^+ \in k^{++}$.
In either case, $m^+ \in k^{++}$, therefore $k^+ \in S$, and the result follows by induction.
$\impliedby:$ Assume $m^+ \in n^+$. By definition, $n^+ = n \cup \{n\}$. Therefore either $m^+ \in n$ or $m^+ = \{n\}$. If $m^+ \in n$, then by transitivity $m^+ \subset n$. Since $m \in m^+$, it follows that $m \in n$. Alternatively, if $m^+ = n$, we again notice that $m \in m^+$, so $m \in n$.
Prove that no natural number is a member of itself.
There is a secret answer to this question - no set is a member of itself. While this property of sets comes from more rigorous study of sets, we can prove it for this particular instance.
Proof by induction. Let $S = \{ n \in \mathbb{N} : n \notin n \}$. Clearly $0 = \varnothing \in S$, since the empty set has no elements. Then assume $k \in S$. Then $k \notin k$. By the previous proof, we conclude that $k^+ \notin k^+$, therefore $k^+ \in S$. Thus the result follows by induction.
Show that $0$ is either equal to or an element of every natural number.
Proof by induction. Let $S = \{ n \in \mathbb{N} : 0 = n \text{ or } 0 \in n \}$
Base case: Clearly $0=0$, so $0 \in S$.
Inductive step: Assume $n \in S$. Then $0 \in n$ or $0 = n$. In either case, it follows that $0 \in n \cup \{n\} = n^+$. Thus the result follows by induction.
Trichotomy Law: Prove that for any two natural numbers $a$ and $b$, only one of the three statements is true:
-
$a \in b$
-
$a = b$
-
$b \in a$
In order to show that exactly one of the statements is always true, we will first show that at most one can be true and then show that at least than one must be true.
At most one is true: If $a = b$, then the fact that no set is an element of itself precludes both $a \in b$ and $b \in a$. Alternatively, if $a \in b$, then by the same logic $a \neq b$. Likewise, it is not true that $b \in a$, which would imply that $a \in b \in a$, which in turn implies $a \in a$ by transitivity, which is a contradiction. An identical argument holds for $b \in a$ that precludes the other two options.
At least one is true: Proof by induction. Let $S = \{ a \in \mathbb{N} : \text{for all } b \in \mathbb{N}, a \in b \text{ or } a = b \text{ or } b \in a \}$.
Base case: Let $a = 0$. When $b = 0$, we have $a = b$, and when $b \neq 0$, we have by the above proof $a \in b$. Thus $0 \in S$.
Inductive case: Assume $k \in S$. Then exactly one of the conditions holds. If $b \in k$, then $b \in k^+$ by transitivity. If instead $b = k$, then $b^+ = k^+$. Lastly, if $k \in b$, then by the preceding proof, $k^+ \in b^+$, and thus either $k^+ \in b$ or $ k^+ = b$. In each case, at least one condition is true, so $k^+ \in S$, and the result follows by induction.
-
Prove that the ordering of $\mathbb{N}$ defined above in fact meets the requirements for an order relation.
In order to qualify as an order relation, a relation must meet the three requirements of comparability, nonreflexivity, and transitivity.
-
Comparability: Let $a, b \in \mathbb{N}$ such that $a \neq b$. By trichotomy, either $a \in b$ or $b \in a$. If $a \in b$, then $a < b$. Conversely, if $b \in a$, then $b < a$.
-
Nonreflexivity: By the second proof above, no natural number is an element of itself, so there is no $a \in \mathbb{N}$ such that $ a < a$.
-
Transitivity: Let $a, b, c \in \mathbb{N}$ such that $a < b$ and $b < c$. By definition of the order relation, $a \in b$ and $b \in c$. Likewise, if $b \in c$, then by transitivity $b \subset c$. Therefore $a \in c$, so $a < c$.
-
Cancellation Law: Prove that $a < b$ if and only if $a + c < b + c$ for all $a, b, c \in \mathbb{N}$.
$\implies$: Proof by induction. Let $S = \{ n \in \mathbb{N} : a + n \in b + n \text{ where } m < n \in \mathbb{N} \}$.
Base case: Because $m + 0 = 0$ and $n + 0 = 0$, we have $m + 0 \in n + 0$, so $0 \in S$.
Inductive case: Assume $n \in S$. Then $a + n < b + n$. Then by the definition of the order relation, $a + n \in b + n$. By transitivity, $(a + n)^+ \in (b + n)^+$, which simplifies to $a + n^+ \in b + n^+$. Therefore $n^+ \in S$, and the result follows by induction.
$\impliedby$: Assume $a + c < b + c$. Then $a + c \in b + c$. By trichotomy, $a \neq b$, as otherwise $a + c \in a + c$. Likewise, $b \notin a$, as otherwise by the forward proof this implies $b + c \in a +c$. Thus the only option left is $a \in b$.
Cancellation Law: Prove that $a < b$ if and only if $a \cdot c = b \cdot c$ for all $c \neq 0 \in \mathbb{N}$.
$\implies$: Assume $a < b$. Proof by induction. Let $S = \{ n \in \mathbb{N} : a \cdot n^+ < b \cdot n^+ \text{ for all nonzero} $c \in \mathbb{N}\}$.
Base case: By definition, $0^+ = 1$. Then $a \cdot 1 = a$, and $b \cdot 1 = b$. Thus $a \cdot 0^+ < b \cdot 0^+$, so $0 \in S$.
Inductive step: Assume $n \in S$. Then $a \cdot n^+ < b \cdot n^+$. By definition of multiplication, $a \cdot n^{++} = (a \cdot n^+) + a$. By applying the addition cancellation law and the inductive hypothesis, we see that $(a \cdot n^+) + a < (b \cdot n^+) + a$. Applying the law again shows $(b \cdot n^+) + a < (b \cdot n^+) + b$. By transitivity on $<$, we conclude that $(a \cdot n^+) + a < (b \cdot n^+) + b$, and thus that $a \cdot n^{++} < b \cdot n^{++}$. Therefore $n^+ \in S$, and the result follows by induction.
$\impliedby$: Assume $a \cdot c < b \cdot c$. By trichotomy, $a \neq b$, as otherwise $a \cdot c \in a \cdot c$. Likewise, it cannot be true that $b < a$, as otherwise by the forward proof $b \cdot c < a \cdot c$, which again implies $a \cdot c \in a \cdot c$. Thus the only option left is $a < b$.
Prove that if $x < y$, then there exists some nonzero $z$ such that $x + z = y$.
Proof by induction. Let $A = \{ x \in \mathbb{N} : \text{for all } y \in \mathbb{N} \text{ where } x < y, \text{ there exists a nonzero} z \in \mathbb{N} \text{ such that } x + z = y \}$.
Base case: Consider $0$ and the set of all $y \in \mathbb{N}$ such that $0 < y$. Clearly $y$ is nonzero. Note that $0 + y = y$, therefore $0 \in A$.
Inductive step: Assume $x \in A$. Consider $x^+$ and number $z \in \mathbb{N}$ such that $x^+ < z$. Because $x \in x^+$, $x < x^+$. By transitivity, $x < z$. By the inductive hypothesis, there exists some nonzero $y \in \mathbb{Z}$ such that $x + y = z$. Observe that $y \neq 1$, as otherwise $x^+ = m$, which is a contradiction. Therefore $y$ is at least $2$. As a result, we can write $y$ in the form $y = p^{++}$, where $p \in \mathbb{N}$. Therefore $x + p^{++} = m$. We can rewrite this equality as $x^+ + p^+ = m$ and then conclude that $x^+ \in A$.
The result follows by induction.