Results 1 to 12 of 12

Math Help - Need some guidance for a proof of countable sets

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    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 A=\{a_1,a_2,\cdots,a_n\} and let

    B\subseteq A

    then B=\{b_1,b_2,\cdots, b_m\}

    where m\leqslant n and

    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 B\subseteq A

    Since A is infinite , A \thicksim N so there exists a bijection from A to N. Hence there exists a bijection from N to A.

    f:N\rightarrow A

    Since B\subseteq A ,

    \forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon

    f(n_1)=b

    Now we define a function

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Need some guidance for a proof of countable sets

    Quote Originally Posted by issacnewton View Post
    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 A=\{a_1,a_2,\cdots,a_n\} and let

    B\subseteq A

    then B=\{b_1,b_2,\cdots, b_m\}

    where m\leqslant n and

    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 B\subseteq A

    Since A is infinite , A \thicksim N so there exists a bijection from A to N. Hence there exists a bijection from N to A.

    f:N\rightarrow A

    Since B\subseteq A ,

    \forall \;\;b\in B \;\;\exists \; n_1 \in N \backepsilon

    f(n_1)=b

    Now we define a function

    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...)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    Re: Need some guidance for a proof of countable sets

    Quote Originally Posted by Also sprach Zarathustra View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433

    Re: Need some guidance for a proof of countable sets

    Let A be countable and 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.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    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 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,406
    Thanks
    1488
    Awards
    1

    Re: Need some guidance for a proof of countable sets

    Quote Originally Posted by issacnewton View Post
    I am proving that any subset of a countable set is also countable.
    There is no need for cases. Because A\text{ is countable } by definition there is a injection  \mathif{f}:A\to \mathbb{N}.
    Define \mathif{g}:B\to \mathbb{N} as  \mathif{g} (b)= \mathif{f}(b).
    Now show that  \mathif{g} is an injection.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,158
    Thanks
    597

    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".
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    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 \exists an injection f:A\to \mathbb{N}

    Now let B\subseteq A , lets define a function

    g:B\to \mathbb{N}

    Consider arbitrary b_1,b_2 \in B ,

    since B\subseteq A \;\;\Rightarrow b_1,b_2 \in A

    Since A is an injection, if b_1\neq b_2 \Rightarrow f(b_1)\neq f(b_2)

    But since B\subseteq A,

    g(b)=f(b) (how do we justify this ?)

    so,  \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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    Re: Need some guidance for a proof of countable sets

    can anybody confirm my proof in the last post ?

    thanks
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Need some guidance for a proof of countable sets

    Quote Originally Posted by issacnewton View Post
    Now let B\subseteq A , lets define a function

    g:B\to \mathbb{N}...

    g(b)=f(b) (how do we justify this ?)
    You never said how you defined g. Plato's suggestion is that

    g(b) = f(b) for every b\in B

    holds by definition. In other words, g is the restriction of f to 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 ?
    The situation when A is empty does not require a special case; it is covered by the proof above. The injection from \emptyset to \mathbb{N} is the empty function.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    Re: Need some guidance for a proof of countable sets

    Hi makarov

    Thanks for the reply. Makes sense now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  2. Replies: 3
    Last Post: March 7th 2010, 02:41 PM
  3. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  4. Proof about countable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 3rd 2010, 06:42 PM
  5. Proof of countable sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 16th 2009, 08:34 PM

/mathhelpforum @mathhelpforum