Proof that all natural numbers can be compared with each other from Halmos' "Naive Set Theory"

85 Views Asked by At

I'm having a hard time understanding a proof from "Naive Set Theory" by Paul Halmos.

First of all, Halmos defines $\mathbb{N}$ as an intersection of all inductive subsets of any inductive set $I$. ($I$ is inductive if $\varnothing \in I$ and $x \in I \Rightarrow x\cup \{ x \} \in I$). He then proceeds to proof that $\cap \{ A \subseteq I \ | \ A$ is inductive $\}$ doesn't depend on the choice of $I$, that is, $\mathbb{N}$ is well-defined. He also denotes $\varnothing$ by $0$ and $n \cup \{n \}$ by $n^{+}$ in the context of $\mathbb{N}$

Now, what I don't understand is the following proof ($p.51$ of the book):

Two natural numbers $m$ and $n$ are comparable is $m \in n, \ n \in m,$ or $m = n$. Any two natural numbers are comparable.

Proof: For any $n \in \mathbb{N}$, $S(n) = \{ m \in \mathbb{N} \ | \ m$ and $n$ are comparable $\}$. Then $S = \{ n \in \mathbb{N} \ | \ S(n) = \mathbb{N} \}$

The proof is by induction. First, we show that $0 \in S$ ( $ \Leftrightarrow S(0) = \mathbb{N}$). Clearly $0 \in S(0)$ (as $0 = 0$). If $m \in S(o)$, then it's either $0 \in m$ or $0 = m$. In the latter case, $0 \in m^{+}$, so $m^{+} \in S(0)$. In the former case, $0 \in m\cup \{ m \} = m^{+}$ as $0 \in m$. So, by induction, $S(0) = \mathbb{N}$, and $0 \in S$.

Now, assume that $n \in S$. That is, $S(n) = \mathbb{N}$. We now need to prove that $n^{+} \in S$, that is, $S(n^{+}) = \mathbb{N}$. Clearly, $0 \in S(n^{+})$ (as $n^{+} \in S(0)$). Now, assume $m \in S(n^{+})$. It follows that $m \in n^{+} , \ n^{+} \in m$ (in which case $n^{+} \in m^{+}$) , or $m = n^{+}$ (in which case $n^{+} \in m^{+}$). In the first case, it's either $m = n$, or $m \in n$. If $m = n$, we're done. If $m \neq n$, then $m \in n$.

The last case splits according to the behavior of $m^{+}$ and $n$: since $m^{+} \in S(n)$, we must have either $n \in m^{+}, \ n = m^{+},$ or $m^{+} \in n$.

What I don't understand is the bold-faced part in the last paragraph. Why we have $m^{+} \in S(n)$ then?

1

There are 1 best solutions below

0
On BEST ANSWER

Note that we're ultimately trying to prove that for any $n$, $S(n) = \Bbb N$. We do this by induction. So, in this induction step, we assume that $S(n) = \Bbb N$, and we try to show that $S(n^+) = \Bbb N$.

This is, in turn, done by its own induction, assuming that $m \in S(n^+)$ and deducing that $m^+\in S(n^+)$. But remember that $S(n) = \Bbb N$ is the induction hypothesis of the "outer" induction, and therefore also assumed true. That's why we have $m^+ \in S(n)$.