Need some guidance for a proof of countable sets
Hi
I am proving that any subset of a countable set is also countable.
I will show my work here. Let set A be countable. We have as one of the cases, where A is an empty set , but by definition its finite and hence countable.
So I am not going to consider the empty subset of A as its trivial. So there are
two cases
Case 1) A is a finite set.
Let $\displaystyle A=\{a_1,a_2,\cdots,a_n\}$ and let
$\displaystyle B\subseteq A$
then $\displaystyle B=\{b_1,b_2,\cdots, b_m\}$
where $\displaystyle m\leqslant n$ and
$\displaystyle b_i \in A \;\; \forall \; i$
Then its clear that there exists a bijection from B to {1,2,..m} for some m in N
Hence B is finite and countable
Case 2) A is inifnite
Let $\displaystyle B\subseteq A$
Since A is infinite , $\displaystyle A \thicksim N$ so there exists a bijection from A to N. Hence there exists a bijection from N to A.
$\displaystyle f:N\rightarrow A$
Since $\displaystyle B\subseteq A$ ,
$\displaystyle \forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon$
$\displaystyle f(n_1)=b$
Now we define a function
$\displaystyle g:N\rightarrow B$
from above arguments, its clear that g is onto. I have to prove that B is also countable, so it could mean that B is either finite or infinite or empty. So how
do I proceed now ? I have checked some proofs of this theorem online and I had
trouble understanding it , so I decided to post the question.
thanks
Re: Need some guidance for a proof of countable sets
Quote:
Originally Posted by
issacnewton
Hi
I am proving that any subset of a countable set is also countable.
I will show my work here. Let set A be countable. We have as one of the cases, where A is an empty set , but by definition its finite and hence countable.
So I am not going to consider the empty subset of A as its trivial. So there are
two cases
Case 1) A is a finite set.
Let $\displaystyle A=\{a_1,a_2,\cdots,a_n\}$ and let
$\displaystyle B\subseteq A$
then $\displaystyle B=\{b_1,b_2,\cdots, b_m\}$
where $\displaystyle m\leqslant n$ and
$\displaystyle b_i \in A \;\; \forall \; i$
Then its clear that there exists a bijection from B to {1,2,..m} for some m in N
Hence B is finite and countable
Case 2) A is inifnite
Let $\displaystyle B\subseteq A$
Since A is infinite , $\displaystyle A \thicksim N$ so there exists a bijection from A to N. Hence there exists a bijection from N to A.
$\displaystyle f:N\rightarrow A$
Since $\displaystyle B\subseteq A$ ,
$\displaystyle \forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon$
$\displaystyle f(n_1)=b$
Now we define a function
$\displaystyle g:N\rightarrow B$
from above arguments, its clear that g is onto. I have to prove that B is also countable, so it could mean that B is either finite or infinite or empty. So how
do I proceed now ? I have checked some proofs of this theorem online and I had
trouble understanding it , so I decided to post the question.
thanks
Define the following function:
f:B-->N where to every x in B, the set of elements from B that less than x is finite.
So, for every x in B, f(x) be the set of elements from B that less than x.
Example:
If B={1,4,9,16,25,...}
f(25)=4
f(16)=3
f(9)=2
.
.
.
Now, prove that f is 1-1 and onto.(Not an easy task...)
Re: Need some guidance for a proof of countable sets
Quote:
Originally Posted by
Also sprach Zarathustra
f:B-->N where to every x in B, the set of elements from B that less than x is finite.
Why is that true, the highlighted part. Is there any other proof of that ?
Re: Need some guidance for a proof of countable sets
Let $\displaystyle A$ be countable and $\displaystyle B\subset A$. If B is empty or finite the result is trivial, so the only interesting case is where A is countably infinite and B is infinite. Put A in bijection with N, this yields a bijection between B and an infinite subset (call it M) of N. So it's enough to show that an infinite subset of N is countable. By well-ordering, M has a least element m, so pair m with 1. Then M\{m} has a least element; pair that one with 2, and so on. Clearly we will exhaust every natural number in this way, and almost as clearly we will use up every element of M (this is where the thing AsZ said comes in), so we have the bijection.
(You can see that every element of M has only finitely many elements less than it, since elements of M are natural numbers and are finite.)
Re: Need some guidance for a proof of countable sets
Hi Tinyboss, so is my proof to case 1 right ? and within case 2, am I right when I say that we can use the same arguments for
the finite subset of infinite A ?
You said " Put A in bijection with N, this yields a bijection between B and an infinite subset (call it M) of N"
I did prove in my post that the function g : B --> N is onto. How do I prove your claim in the above statement ?
Re: Need some guidance for a proof of countable sets
Quote:
Originally Posted by
issacnewton
I am proving that any subset of a countable set is also countable.
There is no need for cases. Because $\displaystyle A\text{ is countable }$ by definition there is a injection $\displaystyle \mathif{f}:A\to \mathbb{N}$.
Define $\displaystyle \mathif{g}:B\to \mathbb{N}$ as $\displaystyle \mathif{g} (b)= \mathif{f}(b). $
Now show that $\displaystyle \mathif{g}$ is an injection.
Re: Need some guidance for a proof of countable sets
intuitively (and somewhat naively, or informally), we can list the elements of A.
since B is a subset of A, we just "cross off the elements in the list not in B" and "fill in the gaps" by "moving things up".
Re: Need some guidance for a proof of countable sets
Thanks everybody ......... I will try to put my proof together and show it here. Its late here , have to sleep now.
Re: Need some guidance for a proof of countable sets
Hi
Sorry for the late reply. I was out of town. So here's my proof. I have decided to use Plato's arguments.
Since A is countable $\displaystyle \exists$ an injection $\displaystyle f:A\to \mathbb{N}$
Now let $\displaystyle B\subseteq A$ , lets define a function
$\displaystyle g:B\to \mathbb{N}$
Consider arbitrary $\displaystyle b_1,b_2 \in B$ ,
since $\displaystyle B\subseteq A \;\;\Rightarrow b_1,b_2 \in A $
Since A is an injection, if $\displaystyle b_1\neq b_2 \Rightarrow f(b_1)\neq f(b_2)$
But since $\displaystyle B\subseteq A$,
$\displaystyle g(b)=f(b)$ (how do we justify this ?)
so, $\displaystyle \Rightarrow g(b_1)\neq g(b_2)$
which proves that g is an injection and so B is countable.
Like I said withing the proof, how do we justify that g(b)=f(b) for all b in B?
Second thing is when A itself is empty set. Is it still possible to say that there is
an injection from A to N, since its still countable ?
thanks
Re: Need some guidance for a proof of countable sets
can anybody confirm my proof in the last post ?
thanks
Re: Need some guidance for a proof of countable sets
Quote:
Originally Posted by
issacnewton
Now let $\displaystyle B\subseteq A$ , lets define a function
$\displaystyle g:B\to \mathbb{N}$...
$\displaystyle g(b)=f(b)$ (how do we justify this ?)
You never said how you defined g. Plato's suggestion is that
$\displaystyle g(b) = f(b)$ for every $\displaystyle b\in B$
holds by definition. In other words, g is the restriction of f to B.
Quote:
Second thing is when A itself is empty set. Is it still possible to say that there is
an injection from A to N, since its still countable ?
The situation when A is empty does not require a special case; it is covered by the proof above. The injection from $\displaystyle \emptyset$ to $\displaystyle \mathbb{N}$ is the empty function.
Re: Need some guidance for a proof of countable sets
Hi makarov
Thanks for the reply. Makes sense now.