Let $A$ be a nonempty subset of $\Bbb N$ without a greatest element. Then there exists a unique, strictly increasing, and surjective mapping $f:\Bbb N \to A$.
In my textbook, the author said that this theorem is very important since many other theorems regarding the countability depend on it. Although the author presented a clear proof, I also roll the sleeve and give it a shot.
Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!
My attempt:
Let $\bar a =\min A$ and $U(a)$ be the set of strictly upper bounds of $a$. We define $g:A \to A$ by $g(a)=\min U(a)$. It follows that $a < g(a)$ for all $a \in A$.
Notice that $A$ has no greatest element, then $U(a) \neq \emptyset$ for all $a \in A$. Thus $\min U(a)$ and consequently $g(a)$ do exist for all $a \in A \subseteq \Bbb N$ by the fact that $\Bbb N$ is well-ordered with respect to $<$.
By recursion theorem, there exists a mapping $f:\Bbb N \to A$ such that $f_0=\bar a$ and $f_{n+1}=g(f_n)$.
- $f$ is strictly increasing
Since $f_{n+1}=g(f_n)=\min U(f_n) > f_n$ for all $n \in \Bbb N$, $f_{k_1}<f_{k_1+1}<f_{k_1+2}<\cdots<f_{k_2}$ for all $k_1 < k_2$. Hence $f$ is strictly increasing.
- $f$ is surjective
Assume the contrary that $f$ is not surjective, then $B=\{a \in A \mid a \notin \operatorname{ran}f\} \neq \emptyset$ and $\bar b=\min B$. Thus $\bar b$ does exits by the fact that $\emptyset \neq B \subseteq \Bbb N$ and $\Bbb N$ is well-ordered with respect to $<$. It follows that $\bar b \neq \bar a$ by the definition of $f$ that $\bar a = f_0 \in \operatorname{ran}f$. Let $b_0 = \max\{a \in A \mid a < \bar b\}$.
a. $b_0$ well-defined
Since $\bar b \neq \bar a$ and $\bar a =\min A$, $\bar a < \bar b$ and consequently $\bar a \in \{a \in A \mid a < \bar b\}$. Thus $\{a \in A \mid a < \bar b\} \neq \emptyset$ and consequently $b_0 = \max\{a \in A \mid a < \bar b\}$ does exists. It follows that $b_0 \in \operatorname{ran}f$ and $b_0 = f_k$ for some $k \in \Bbb N$.
b. $g(b_0)=\bar b$
We have $b_0=\max\{a\in A\mid a< \bar b\}$, then $b_0<\bar b$ and $(a <\bar b \implies a\le b_0)$.
For all $b_0 < a$, then either $a < \bar b$ or $\bar b \le a$. If $a < \bar b \implies a \leq b_0 \implies b_0 \not < a \implies a < \bar b$ is impossible. Thus $b_0<\bar b$ and $(b_0<a \implies \bar b \leq a)$. This implies $\bar b=\min\{a\in A\mid b_0< a\}$ $=\min U(b_0)=g(b_0)$. To sum up, $g(b_0)=\bar b$.
We have $g(b_0)=\bar b \iff g(f_k) = \bar b \iff f_{k+1} =\bar b$. It follows that $\bar b \in \operatorname{ran}f$ and consequently $\bar b \notin B$. This contradicts the fact that $\bar b=\min B$.
Hence $f$ is surjective.
- $f$ is unique
Assume the contrary that there exists $f' \neq f$ that satisfies required conditions. Let $C=\{n \in \Bbb N \mid {f'}_n \neq f_n\} \neq \emptyset$ and $m =\min C$. It follows that ${f'}_n = f_n$ for all $n<m$. We can safely assume that $f_m<{f'}_m$.
Since $f_m \in A$ and $f'$ is surjective, then ${f'}_k=f_m$ for some $k \in \Bbb N$. Thus $f_m<{f'}_m \implies {f'}_k=f_m<{f'}_m \implies {f'}_k<{f'}_m \implies k<m$ [since $f'$ is strictly increasing] $\implies f_k = {f'}_k = f_m \implies f_k=f_m \implies k=m$ [since $f$ is strictly increasing]. This contradicts the fact that $k<m$. Hence there does not exist $f' \neq f$ that satisfies required conditions. Thus $f$ is unique.
Update: I added a screenshot here.
Best Answer
Your proof looks fine but I think there must be any other easier proof. First notice that in the mapping no two distinct elements of $\Bbb N$ can be mapped to one element of $A$ because it contradicts to strict increment of the mapping, so the mapping we seek to find is injective and surjective i.e. bijective. For constructing such a bijection we rearrange the terms of $A$ in numerical order from small to large. Surely the bijection is simply the same counting the elements of $A$. For example if $A$ contains even numbers we rearrange them as following $$\{2,4,6,8,10,\cdots\}$$and the bijection is $$n\to 2n$$this bijection is unique. If not i.e. if there exists one more such counting of elements of $A$, then this means that we can swap two elements of $A$ to each other and the arrangement still remains strictly increasing. But this is impossible since we can't rearrange a set in two different way such that the elements form a numerical order which completes our proof.