Prove every subset of countable set is either finite or else countable

[zenterix]

Homework Statement

Theorem: Every subset of a countable set is either finite or else countable.

Relevant Equations

The proof in the book I am reading is as follows

Let $A$ be a subset of a countable set. Assume $A$ is not finite; then it will be shown that $A$ is countable. An easy argument shows that one can assume without loss of generality that $A$ is a subset of $\mathbb{N}$.

Now define a function $f:\mathbb{N}\to A$ inductively as follows:

$f(1)=$ the least element of $A$ (that exists by the well-ordering principle)

and then if $f(1),...,f(n)$ have been defined, let $f(n+1)$ be the least element of $A \backslash \{f(1),...,f(n)\}$. (The least element again exists by the well-ordering principle, and the fact that $A$ is not finite.) It is now left to the reader to verify that $f$ is one-to-one and onto. Thus, $A$ is equivalent to $\mathbb{N}$.

There are a lot of steps left out of this proof. Here is my proof with hopefully all the steps. I would like to know if it is correct

Let $A$ be a countable set. Then $A$ is either finite or countably infinite.

Case 1: $A$ is finite.

There is a bijection $f$ from $A$ onto $\{1,...,n\}$.

Let $S\subseteq A$. Then $g:S\to f(S)$ is a bijection, and since every subset of $\{1,...,n\}$ is finite then $S$ is also finite.

Case 2: $A$ is countably infinite.

Since there is a bijection between $A$ and $\mathbb{N}$ (call it $f$) then

Claim 1: there is a bijection between $B\subseteq A$ and a subset of $\mathbb{N}$.

Proof 1: Define $g:B\to f(B)$ such that $g(b)=f(b)$ for $b\in B$ where $f(B)\subseteq\mathbb{N}$. $g$ is a bijection (I won't prove this here so the post isn't too long). $\blacksquare$

Here is the "easy argument" cited in the book's proof: if we show that every subset of $\mathbb{N}$ is countable then every $B\subseteq A$ is countable too because if there is a bijection $f_1:f(B)\to\mathbb{N}$ and a bijection $f_2:B\to f(B)$ (which we've already obtained above) then there is a bijection $f_3:B\to\mathbb{N}$ defined $f_3=f_1\circ f_2$, and thus $B$ is countable.

Claim 2: Every subset of $\mathbb{N}$ is countable

Proof 2: Let $S\subseteq\mathbb{N}$. If $S$ is finite then by definition it is countable.

If $S$ is infinite then consider the function $f$ defined inductively as follows

$S$ has a least element (by well-ordering principle) $s_1$. Define $f(1)=s_1$.

Assume $f(1), ..., f(n)$ have been defined.

Define $f(n+1)=$ least element of $S\backslash \{f(1),...,f(n)\}$

Claim 3: $f$ is a bijection from $\mathbb{N}$ onto $S$

If we accept claim 3 then we have shown that $S$ is countably infinite, and thus countable and proof 2 is finished.

Proof 3: Suppose $f(n_1)=f(n_2)$.

This means that the least element of $S\backslash \{f(1),...,f(n_1-1)\}$ equals the least element of $S\backslash\{f(1),...,f(n_2-1)\}$.

Suppose $n_1>n_2$. Then, the least element of $S\backslash \{f(1),...,f(n_2), ...,f(n_1-1)\}$ equals the least element of $S\backslash\{f(1),...,f(n_2-1)\}=f(n_2)$.

Thus, $f(n_2) \in S\backslash\{f(1),...,f(n_2)\}$.

But this contradicts the definition of a set difference.

Thus, by contradiction we have proved that $n_1\leq n_2$.

With an analogous argument we can show that it cannot be that $n_2>n_1$ and so we can conclude that $n_1=n_2$.

Thus $f$ is injective.

Now suppose $n\in S$.

There are $n-1$ natural numbers smaller than $n$.

Thus, there are at most $n-1$ natural numbers $k$ such that $f(k)<n$.

Suppose there are $m$ such numbers.

Then $f(m)=$ least element of $S\backslash \{f(1),...,f(m-1)\}$

and since $\forall\ x\in S\backslash\{f(1),...,f(m-1)\}\implies x\geq n$

then $f(m)=n$.

Thus $f$ is surjective.

Thus, $f$ is bijective. $\blacksquare$

 

[PeroK]

I don't think you need case 1. This is how I would start.

I think we need a name for the set. Let $S$ be a countable set and $A \subseteq S$. It is enough to show that if $A$ is not finite, then $A$ is countable.

As $S$ is countable, there is a bijection $f: S \to \mathbb N$. If we restrict $f$ to $A$, then this is a bijection from $A$ to $f(A)$, which is a subset of $\mathbb N$. Note that $A$ is countable iff $f(A)$ is countable. [That, I suggest, is a separate proof, if necessary.] Therefore, it is enough to show that every subset of $\mathbb N$ is countable.