Proposition:
Each subset of the natural numbers is finite or countable.
Proof:
Let $X \subset \omega$.
First case: $X$ is bounded. That means that $(\exists k \in \omega)(\forall y \in X) y \leq k$. Then $X \subset k+1$ and $X$, as a subset of a finite subset, is finite .
Second case: $X$ is not bounded, i.e. $(\forall k \in \omega) (\exists y \in X) k<y$.
Then for all $k \in \omega$, $\min(X-(k+1))$ is defined. We define the recursively the function $f: \omega \to X$
$$ f(0)= \text{ the smallest element of }X=\min X\\f(n+1)=\text{the smallest element of X that is greater than } f(n)=\min \{ X-(f(n)+1)\}$$
From the definition of $f$ we have that $f(n+1)>f(n)$
, i.e. $f$ is strictly increasing and so $1-1$.
It suffices to show that $f$ is injective.
Could you explain me how we conclude that for all $k \in \omega$, $\min (X-(k+1))$ is defined?
Also at the definition of $f(n+1)$ why do we add $1$ to $f(n)$ ?
Best Answer
In this case, $X-k$ is the set $X\setminus \{0,1,\ldots,k\}$, so $\min(X-(k+1))$ is the minimum element on $X$ without considering $0,\ldots,k+1$.
$f$ is well defined because, since $X$ is unbounded, $X-(k+1)$ is non-empty for every $k$.
In the definition of $f(n+1)$, you add $1$ to $f(n)$ to guarantee that $f$ is strictly increasing, i.e., you remove the possibility of $f(n)$ being the minimum.