- #1
zenterix
- 702
- 84
- 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##