Positive Integer

Successor Set

Definition 6.1. A set $X \subseteq \mathbb{R}$ is said to be a successor set 
(i) if $1 \in X$,
(ii) if $n \in X$, then $n+1 \in X$.

실수 집합 $\mathbb{R}$은 그 자체로 successor set이기 때문에,(A9, A1) 위와 같이 정의한 successor set은 적어도 하나는 존재한다고 말할 수 있다. 

Lemma 6.2

Lemma 6.2. If $\mathcal{A}$ is any nonempty collection of successor sets, then $\cap \mathcal{A}$ is a successor set.

Proof. Since $1$ is in every succerssor set, $1 \in \cap \mathcal{A}$. Let $n \in \cap \mathcal{A}$. Then $n \in A, \forall A \in \mathcal{A}$. Then $n + 1$ is also in any $A$ in $\mathcal{A}$ by definition 6.1. Thus $\cap \mathcal{A}$ is a successor set. $\blacksquare$

Positive Integer

Definition 6.3. The set $\mathbb{P}$ of positive integers is the intersection of the family of all successor sets.

위 lemma에 의해 $P$는 successor set이고, intersection의 정의상 집합 간의 포함 관계에 대하여 successor set들 중smallest set임이 분명하다. 

Mathematical Induction

Theorem 6.4. Suppose that for each positive integer $n$, we have a statement $S(n)$. Suppose also that
(i) $S(1)$ is true.
(ii) If $S(n)$ is true, then $S(n + 1)$ is true. Then $S(n)$ is true for every positive integer $n$.

Proof. Let $T = \{ n \in \mathbb{P} \, | \, S(n) \text{ is true} \}$. Then by the assumption, $T$ is a successor set. Then $\mathbb{P} \subset T$ and clearly $T \subset \mathbb{P}$. Thus $T = P$. $\blacksquare$

Theorem 6.5

Theorem 6.5. If $n$ is a positive integer, then $n ≥ 1$.

Proof. We will use mathematical induction. Let $S(n)$ be the statement which is $n \geq 1$. Note that $S(1)$ is clearly true. If $S(k)$ is true, then $k \geq 1$. Note that $k - 1 \in P$ or $k = 1$ by definition 4.1. If $k = 1$, then $k \in P$ by theorem 4.2. If $k - 1 \in P$, $(k - 1) + 1 = k \in P$. Thus $k \in P$, and $$k = k + 1 - 1 \in P \\ \Longrightarrow k + 1 > 1 \Longrightarrow k + 1 \geq 1.$$ Thus $S(n)$ is true for all positive integer $n$. $\blacksquare$

Theorem 6.6

Theorem 6.6.  If $m,n \in \mathbb{P}$, then $m + n \in \mathbb{P}$.

Proof. Let $S(n)$ be the statement which is $m+n \in \mathbb{P}$. Since $m \in \mathbb{P}$, clearly $m+1 \in \mathbb{P}$ by the definition 6.1, so $S(1)$ is true. If $S(n)$ is true, that is, $m+n \in \mathbb{P}$, then $m+n+1 \in \mathbb{P}$ by the definition 6.1, so $S(n+1)$ is true. Then by mathematical induction, $S(n)$ is true for all positive integers. $\blacksquare$

Lemma 6.7

Lemma 6.7. If $n \in \mathbb{P}$, then either $n − 1 = 0$ or $n − 1 \in \mathbb{P}$.

Proof. Let $G = \{ n \in \mathbb{P} \, | \, n - 1 = 0 \text{ or } n - 1 \in \mathbb{P} \}$. We will show that $G = \mathbb{P}$. Clearly $G \subset \mathbb{P}$. Note that $1 \in G$. If $n \in G$, then $(n+1) - 1 = n \neq 0$ and $n \in \mathbb{P}$. Thus $n+1 \in G$, so $G$ is a successor set. Since $\mathbb{P}$ is the smallest successor set, $\mathbb{P} \subset G$, so $G = \mathbb{P}$. $\blacksquare$

Lemma 6.8

Lemma 6.8. If $m, n \in P$ and $m < n$, then $n ‒ m \in \mathbb{P}$.

Proof. Let $S(m)$ be the statement which is $n - m \in \mathbb{P}$. By the assumption, $1 < n$. Then by Lemma 6.7, either $n-1 = 0$ or $n-1 \in \mathbb{P}$. Since $1 < n$, $n-1$ cannot equal to $0$, so $n-1 \in \mathbb{P}$, which means that $S(1)$ is true. 
Suppose that $S(m)$ is true, i.e., $n - m \in \mathbb{P}$ for the positive integers $n, m$ such that $n > m$. If $m+1 < n$, then $n - 1 \in \mathbb{P}$ because $n -1$ cannot equal to $0$, so $n - 1 \in \mathbb{P}$ by Lemma 6.7. Since $m < n - 1$ and $S(m)$ is true, $n-1 - m = n - (m + 1) \in \mathbb{P}$. Thus $S(m+1)$ is also true. By mathematical induction, $S(m)$ is true for all positive integers. $\blacksquare$

Lemma 6.9

Lemma 6.9. Let $n$ be a positive integer. No positive integer $m$ satisfies the inequality $n < m < n + 1$.

Proof. Suppose that $\exists m \in \mathbb{P}$ such that $n < m < n+1$. Then $m - n \in \mathbb{P}$ by Lemma 6.8. But $m < n + 1$, so $m - n < 1$ which is a contradiction by Theorem 6.5. Thus there is no positive integer $m$ such that $n < m < n+1$. $\blacksquare$

Well-Ordering Theorem

Theorem 6.10. If $X$ is a nonempty subset of the positive integers, then $X$ contains a least element; that is, there exists $a \in X$ such that $a ≤ x$ for all $x \in X$.

Proof. Let $S(n)$ be the statement: "If $n \in X$, then $X$ contains a least element."
If $1 \in X$, then $1$ is the least element of $X$ by Theorem 6.5. 
Suppose that $S(n)$ is true and $n+1 \in X$. Since $n \in X \cup \{ n \}$, $X \cup \{ n \}$ has the least element $l$. If $l \in X$, then $l \leq x$ and $\leq n < n+1$ for all $x \in X$, so $l$ is the least element of $X$. If $l \notin X$, then $n = l$ because $l \in X \cup \{ n \}$. Then $n \leq x$ and $n < n+1$ \for all $x \in X$, so $n$ is the least element of $X$. Thus, $X$ always has the least element by mathematical induction. $\blacksquare$

Theorem 6.11

Theorem 6.11. The set of positive integers is not bounded above.

Proof. Suppose that $\mathbb{P}$ is bounded above. Then $\mathbb{P}$ has the least upper bound $a$ by A13. Then $a-1$ is not an upper bound for $\mathbb{P}$, so $\exists n \in \mathbb{P}$ such that $a-1 < n$. But $a < n+1$, which is a contradiction. Thus $\mathbb{P}$ is not bounded above. $\blacksquare$

Corollary 6.12

Corollary 6.12. The set of real numbers is Archimedean ordered;
(1) If $a$ and $b$ are positive real numbers, there exists a positive integer $n$ such that $a < nb$.
(2) If $\varepsilon$ is a positive real number, there exists a positive integer $N$ such that $\frac{1}{N} < \varepsilon$.

Proof. (1) Suppose that there does not exist a positive integer $n$ such that $a < nb$. Then $\forall n \in \mathbb{P}, a \geq nb$. Then $n \leq \frac{a}{n}, \forall n \in \mathbb{P}$, which means that $\mathbb{P}$ is bounded above, but it is a contradiction by Theorem 6.11. Thus there exists a positive integer $n$ such that $a < nb$. 
(2) In (1), take $a = 1$ and $b = \varepsilon$. Then $\exists N \in \mathbb{P}$ such that $1 < N \varepsilon \iff \frac{1}{N} < \varepsilon.$ $\blacksquare$