Results 1 to 5 of 5

Math Help - Bijection - Countability

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    Bijection - Countability

    I want to establish the following:
    "There exists a bijection from N to any 'infinite subset of N'."

    Definitions -
    1. If there exists a bijection from J_n -> S. Then S is finite AND countable. Else S is infinite (and maybe countable)
    2. If there exists a bijection from N -> S. Then S is infinite AND countable.

    J_n = {1,2,3,....,n}
    N = {1,2,3,....,n,....}

    (I need this to prove subset of any countable set is countable. And I want to work out a rigorous proof for the same.)

    Any pointers plz?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by aman_cc View Post
    I want to establish the following:
    "There exists a bijection from N to any 'infinite subset of N'."

    Definitions -
    1. If there exists a bijection from J_n -> S. Then S is finite AND countable. Else S is infinite (and maybe countable)
    2. If there exists a bijection from N -> S. Then S is infinite AND countable.

    J_n = {1,2,3,....,n}
    N = {1,2,3,....,n,....}

    (I need this to prove subset of any countable set is countable. And I want to work out a rigorous proof for the same.)

    Any pointers plz?
    If we're working in the context of proving that the subset of any countable set is countable itself, would it not suffice to prove that there is an injection from any infinite subset of \mathbb{N} to \mathbb{N} itself?

    This would give us the result that the subset itself is countable, however not that it's cardinality is the same as that of \mathbb{N}. A proper injection from A \subset N to \mathbb{N} would be: f:A \to \mathbb{N} : f(n) = n therefore |A| \leq |\mathbb{N} |...

    Are you allowed to make the assumption that \aleph_0 = |\mathbb{N}| is the smallest infinite cardinal number? If so, this would also give us the result that |A| = |\mathbb{N}|, otherwise, I would need to think of another way to prove equivalence.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Defunkt View Post
    If we're working in the context of proving that the subset of any countable set is countable itself, would it not suffice to prove that there is an injection from any infinite subset of \mathbb{N} to \mathbb{N} itself?

    This would give us the result that the subset itself is countable, however not that it's cardinality is the same as that of \mathbb{N}. A proper injection from A \subset N to \mathbb{N} would be: f:A \to \mathbb{N} : f(n) = n therefore |A| \leq |\mathbb{N} |...

    Are you allowed to make the assumption that \aleph_0 = |\mathbb{N}| is the smallest infinite cardinal number? If so, this would also give us the result that |A| = |\mathbb{N}|, otherwise, I would need to think of another way to prove equivalence.
    Thanks yes I would agree to you.

    You seem to use that if there is an injection from S into N, S is countable,

    I want to prove this.

    I am referring Rudin. Definitions he has given is that S is countable IFF there is a bi-jection between S and N.

    About assuming cardinality of N - I guess these are much stronger statements which are not needed in this context. We should be able to do whatever definitions we have at our disposal.

    Please excuse me if I am off the track. I am reading all this on my own - so might not really know the established methods.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,912
    Thanks
    1760
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    I want to establish the following:
    "There exists a bijection from N to any 'infinite subset of N '."
    Quote Originally Posted by aman_cc View Post
    I am referring Rudin. Definitions he has given is that S is countable IFF there is a bi-jection between S and N.
    You say that you are reading Rudin. Well notice the statement posted in the first quote is found as theorem 2.10 in Rudin. His proof depends upon \mathbb{J}, the symbol he uses for \mathbb{Z}^+, being well ordered (every non-empty subset having a first term).

    Although Rudin does not use this, many other authors do.
    Is S = \bigcup\limits_n {E_n } is the countable union of countable sets then S = \bigcup\limits_n {F_n } where n \ne m\, \Rightarrow \,F_n  \cap F_m  = \emptyset .
    In other words, S is the countable union of pairwise disjoint sets, each of which is at most countable.
    So x\in S\, \Rightarrow \, x=f_{n,j}\in F_n define  \phi :S \mapsto J as  \phi(x)=2^n\cdot 3^j.
    It is easy to show that  \phi(x) is an injection. So use 2.10 to conclude that S is at most countable.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Plato View Post
    You say that you are reading Rudin. Well notice the statement posted in the first quote is found as theorem 2.10 in Rudin. His proof depends upon \mathbb{J}, the symbol he uses for \mathbb{Z}^+, being well ordered (every non-empty subset having a first term).

    Although Rudin does not use this, many other authors do.
    Is S = \bigcup\limits_n {E_n } is the countable union of countable sets then S = \bigcup\limits_n {F_n } where n \ne m\, \Rightarrow \,F_n  \cap F_m  = \emptyset .
    In other words, S is the countable union of pairwise disjoint sets, each of which is at most countable.
    So x\in S\, \Rightarrow \, x=f_{n,j}\in F_n define  \phi :S \mapsto J as  \phi(x)=2^n\cdot 3^j.
    It is easy to show that  \phi(x) is an injection. So use 2.10 to conclude that S is at most countable.

    Thanks Defunkt and Plato. It's beginning to make sense. Let me please read your arguments more carefully. Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. countability of a set
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 6th 2011, 04:18 AM
  2. Countability
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: February 15th 2010, 09:36 PM
  3. Countability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 23rd 2009, 01:09 AM
  4. Countability
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 28th 2008, 11:49 AM
  5. Countability
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2008, 07:26 AM

Search Tags


/mathhelpforum @mathhelpforum