Each subset of the natural numbers is finite or countable

[evinda]

Hello! (Smile)

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 remains 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)$ ?

 

[Valkarie]

For the first question, if $X$ is not bounded, then for any natural number $k$, there must exist an element greater than $k$ in $X$. This means that $\min(X-(k+1))$ will always be defined since there must be an element greater than $k+1$ in $X$.For the second question, we add $1$ to $f(n)$ in the definition of $f(n+1)$ because we want to find the smallest element of $X$ that is greater than $f(n)$. By adding $1$ to $f(n)$, we can ensure that this element is greater than $f(n)$, since $f(n+1) > f(n)$ by definition.