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.