Natural Numbers
1. Definitions
Definition
Given two sets \(A\) and \(B\) and a function \(\phi : A \rightarrow B\) mapping elements of \(A\) to \(B\),
- We say that \(\phi\) is 1 to 1 (sometimes written 1-1) or injective when for all \(a,a' \in A\), \(\phi(a) = \phi(a')\) implies \(a = a'\). In other words, no two elements of \(A\) map to the same element of \(B\).
- We say that \(\phi\) is onto or surjective when for every \(b \in B\), there is some \(a \in A\) such that \(\phi(a) = b\). In other words, every \(b \in B\) is mapped to by something in \(A\).
- We say that \(\phi\) is a bijection when it is both 1-1 and onto.
Bijections are nice because they can be inverted: If \(\phi : A \rightarrow B\) is a bijection, let \(\phi^{-1}(b)\) be defined to equal the \(a\) such that \(\phi(a) = b\). Because \(\phi\) is surjective, there must always be such an \(a\), and because it's injective, there can be only one.
2. “Practical” Definition of the Natural Numbers
Definition
The Natural Numbers \(\mathbb N\) are defined (for our purposes) as the intersection of all sets of real numbers which contain \(1\) and are closed under adding \(1\). In other words, a real number \(n\) belongs to \(\mathbb N\) if and only if \(n\) belongs to every set \(E \subset {\mathbb R}\) having the property that \(1 \in E\) and \(x+1 \in E\) for every \(x \in E\) (note that \(\in\) means simply “is in”).
Observe: The set \({\mathbb N}\) itself contains one, is closed under adding \(1\), and is contained in any other set that has those same properties. It is the “smallest” such set.
To see why: Let's say a set \(E\) is inductive when \(1 \in E\) and when every \(x \in E\) has the property that \(x + 1 \in E\) too. Then \({\mathbb N}\) is the intersection of all inductive subsets of \({\mathbb R}\). Since \(1\) is in every inductive set, \(1 \in {\mathbb N}\). Similarly, for any number \(x \in {\mathbb N}\), \(x\) belongs to every inductive set; because they're all inductive, \(x+1\) belongs to every inductive set, too. Thus \(x+1 \in {\mathbb N}\). So \({\mathbb N}\) is also an inductive set. Every single element of \({\mathbb N}\) belongs to every inductive subset of \({\mathbb R}\), so \({\mathbb N}\) is a subset of every inductive set.
3. Proofs by Induction
Theorem (Subtracting 1)
Suppose \(k \in {\mathbb N}\) is not equal to \(1\). Then \(k - 1 \in {\mathbb N}\) as well.
Proof
Consider the set \(E := {\mathbb N} \setminus \{k\}\) for some \(k \neq 1\) belonging to \({\mathbb N}\). Suppose that \(k - 1\) is not a natural number. I claim that this would mean that \(E\) contains \(1\) and \(E\) is closed under adding \(1\).
- \(1 \in E\) because \(k \neq 1\) by assumption on \(k\) and because \(1 \in E\).
- If \(n \in E\), then \(n\) is a natural number not equal to \(k\). The number \(n+1\) is also a natural number. But is \(n+1\) in the set \(E\)? The only way that \(n+1\) might not belong to \(E\) is if \(n+1 = k\), since all natural numbers except \(k\) belong to \(E\). But if \(n+1 = k\), this would mean that \(n = k-1\). We already decided that \(n\) is a natural number; and we're still considering what happens under the assumption that \(k-1 \not \in {\mathbb N}\), so under this assumption, it must turn out that \(n+1 \neq k\) after all. Since \(n+1 \neq k\), \(n+1 \in E\) and thus \(E\) must be inductive. But now we have an inescapable problem: If \(k-1 \not \in {\mathbb N}\), then the set \(E := {\mathbb N} \setminus \{k\}\) is inductive and consequently \({\mathbb N} \subset E\). That isn't possible, because \(k \in N\) and \(k \not \in E\). Thus the assumption that \(k-1 \not \in {\mathbb N}\) must have been false.
Theorem (One is the smallest natural number)
The smallest natural number is \(1\), i.e., if \(k \in {\mathbb N}\), then \(k \geq 1\).
Proof
Theorem (There are no natural numbers between \(k\) and \(k+1\))
If \(k \in {\mathbb N}\), then there are no natural numbers strictly between \(k\) and \(k+1\).
Proof
Start by considering \(k = 1\). Consider the set \(E := \{1\} \cup \{x \in {\mathbb R} \ : \ x \geq 2\}\). We claim that \(E\) is inductive. Clearly \(1 \in E\). Suppose that \(x \in E\). If \(x = 1\), then \(x+1 = 2\) which is also in \(E\) because \(2 \geq 2\). If \(x \neq 1\), then it must be that \(x \geq 2\), so \(x+1 \geq 2+1 \geq 2+0 = 2\) since \(1 > 0\). Thus \(x+1 \in E\). Since \(E\) is inductive, it contains all natural numbers. Since \(E\) contains no numbers strictly between \(1\) and \(2\), there can be no natural numbers between \(1\) and \(2\).
In general, let \(S\) be the set of natural numbers \(k\) for which there are no other natural numbers \(\ell\) with \(k < \ell < k +1\). We already showed that \(1 \in S\). Suppose that \(k \in S\). We will see that \(k+1 \in S\) as well. Why? Because if it weren't so, there would be a natural number \(\ell\) with \(k+1 < \ell < k+2\). Subtracting \(1\) gives \(k < \ell - 1 < k+1\). We know that \(\ell\) can't equal \(1\) because \(\ell > k+1 \geq 1 + 1 > 1\). So that means \(\ell-1 \in {\mathbb N}\), which would violate the fact that \(k \in S\). Therefore the assumption that \(k+1 \not \in S\) must be wrong. Thus \(S\) must be inductive and therefore must contain all natural numbers. This means that there is
never a natural number between \(k\) and \(k+1\) when \(k \in {\mathbb N}\).
4. Finite Sets and Bijections
Definition
The set \(\{1,\ldots,N\}\) is defined to consist of all natural numbers \(k\) such that \(1 \leq k \leq N\).
Theorem
There does not exist a bijection between \(\{1,\ldots,N\}\) and any of its proper subsets (i.e., subsets which contain not all of \(\{1,\ldots,N\}\)).
Proof
Let \(S\) be the set of natural numbers \(N\) for which \(\{1,\ldots,N\}\) cannot be put in bijection with a proper subset. The natural number \(k\) must belong to \(S\), since \(\{1,\ldots,1\}\) is the set of all natural numbers \(k\) such that \(1 \leq k \leq 1\). In other words, it's just the set \(\{1\}\). The only proper subset of \(\{1\}\) is the empty set, and \(\{1\}\) can't be mapped bijectively onto \(\emptyset\) because there's nothing in \(\emptyset\) for \(1\) to map to.
Now suppose \(N \in S\). Consider the situation of \(N+1\). Suppose that there is some proper subset \(X\) of \(\{1,\ldots,N+1\}\) and some one-to-one and onto function \(\phi : \{1,\ldots,N+1\} \rightarrow X\). Because \(X\) is proper, there is some \(\ell \in \{1,\ldots,N+1\}\) which does not belong to \(X\).
If \(\ell = N+1\), this means that \(X \subset \{1,\ldots,N\}\) because there are no natural numbers strictly between \(N\) and \(N+1\). So \(\phi\) is a bjiection from \(\{1,\ldots,N+1\}\) into \(\{1,\ldots,N\}\). This means that \(\phi\) is one-to-one on the smaller set \(\{1,\ldots,N\}\). Because no bijection exists from \(\{1,\ldots,N\}\) to a proper subset, this implies that \(\phi\) maps \(\{1,\ldots,N\}\) onto \(\{1,\ldots,N\}\). But then we have a problem because \(\phi(N+1)\) has to belong to \(\{1,\ldots,N\}\) as well, but some other \(k \in \{1,\ldots,N\}\) has the same property, meaning \(\phi(k) = \phi(N+1)\) and consequently \(\phi\) isn't one-to-one.
Now suppose \(\ell \neq N+1\). This means that \(\phi(a) = N+1\) for some \(a \in \{1,\ldots,N+1\}\). Let \(w := \phi(N+1)\) as well. Define
\[ \tilde \phi(x) := \begin{cases} \phi(x) & \text{if } x \neq a,N+1 \\
w & \text{if } x = a \\ N+1 & \text{if } x = N+1. \end{cases}\]
The map \(\tilde \phi\) must be injective: if \(\tilde \phi(u) = \tilde \phi(v)\) then either \(\tilde \phi(u) = \tilde \phi(v) = w\), in which case \(u = v = a\) (because \(\phi(x) = w\) can only happen when \(x = N+1\) by injectivity of \(\phi\)), \(\tilde \phi(u) = \tilde \phi(v) = N+1\), in which case \(u = v = N+1\), or \(\tilde \phi(u) = \phi(u) = \phi(v) = \tilde \phi(v)\), in which case \(u=v\) by injectivity of \(\phi\). Let \(E\) be the image of \(\{1,\ldots,N\}\), i.e., the set of numbers \(\phi \phi(n)\) for \(n \in \{1,\ldots,N\}\). The function \(\tilde \phi\) is one-to-one on \(\{1,\ldots,N\}\) and so must be bijective with \(E\) on that set. However, \(E\) cannot contain \(N+1\) (because \(\tilde \phi(N+1) = N+1\) so \(\tilde \phi(x) \neq N+1\) when \(x \neq N+1\)), so \(E \subset \{1,\ldots,N\}\). Once again, we already know that \(E\) cannot be a proper subset of \(\{1,\ldots,N\}\), so it must be the whole thing. But if \(\tilde \phi(\{1,\ldots,N\}) = \{1,\ldots,N\}\) and \(\tilde \phi(N+1) = N+1\), then necessarily \(\tilde \phi(\{1,\ldots,N+1\}) = \{1,\ldots,N+1\}\). But this is impossible, because we know that there must be some value of \(\ell \in \{1,\ldots,N+1\}\) such that \(\phi\) never equals \(\ell\). This means \(\tilde \phi\) couldn't possibly ever equal \(\ell\), either (because \(\ell \neq w,N+1\), so if \(\tilde \phi(x) = \ell\), it would mean \(\phi(x) = \ell\) too). Therefore the original set \(X\) must not exist, and consequently no bijections from \(\{1,\ldots,N+1\}\) into a proper subset can exist. This means that \({\mathbb N} \subset S\) and the theorem must be true.
Important
For infinite sets, it's quite easy for the set to be in bijection with a proper subset. For example, the map \(\phi : {\mathbb N} \rightarrow {\mathbb N} \setminus \{1\}\) given by \(\phi(N) := N+1\) is exactly such a bjiection. This is the idea behind the “Hilbert Hotel.”