Results 1 to 6 of 6

Math Help - countably infinite / uncountable sets

  1. #1
    Junior Member
    Joined
    Dec 2007
    Posts
    25

    countably infinite / uncountable sets

    Is it true if the set X is countably infinite then there are bijective maps f: X-->N and f:N-->X ?

    Separately, could someone start me off on this proof:

    Prove that if A in uncountable, then A - {x} is uncountable.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Chizum View Post
    Is it true if the set X is countably infinite then there are bijective maps f: X-->N and f:N-->X ?
    Just what is your understanding of the term countably infinite?
    What is a bijection?

    Quote Originally Posted by Chizum View Post
    Prove that if A in uncountable, then A - {x} is uncountable.
    In light of the first question, what would it imply if A\setminus \{x\} were not uncountable?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2007
    Posts
    25
    Quote Originally Posted by Plato View Post
    Just what is your understanding of the term countably infinite?
    a set with the same cardinality as N

    What is a bijection?
    a map that is 1-1/onto

    A\setminus \{x\}
    restate that please
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Chizum View Post
    Is it true if the set X is countably infinite then there are bijective maps f: X-->N and f:N-->X ?
    Why would you think otherwise?

    Quote Originally Posted by Chizum View Post
    Prove that if A in uncountable, then A - {x} is uncountable.
    Suppose A - {x} were countable. What you have to do now is show how to put A one-to-one with N, which would contradict the assumption that A is uncountable.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Chizum View Post
    restate that please
    A\{x} is just another notation of A - {x}. What you're being asked to do is to show a contradiction that would follow if we had A uncountable but A\{x} countable.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Chizum View Post
    Is it true if the set X is countably infinite then there are bijective maps f: X-->N and f:N-->X ?

    Separately, could someone start me off on this proof:

    Prove that if A in uncountable, then A - {x} is uncountable.

    Thanks
    Suppose that A was uncountable but A-\{x\} was countable. Then, there exists a bijection f:A-\{x\}\mapsto\mathbb{N} and so g:A\mapsto \mathbb{N}\cup \{0\} given by g(z)=\begin{cases} f(z) & \mbox{if} \quad z\ne x \\ 0 & \mbox{if}\quad z=x\end{cases}. This is clearly a bijeciton and thus a contradiction.

    In fact, there is a much stronger statement that can be made.

    Let E be uncountable and F\subseteq E be countable. Then E-F is uncountable.

    Proof: Since E-F is countable there exists some f:E-F\mapsto \mathbb{N} which is bijective. Also, since F is countable there is some g:F\mapsto \mathbb{Z}-\mathbb{N} which is also bijective. Clearly then, \eta:E\mapsto\mathbb{Z} given by \eta(x)=\begin{cases} f(x) & \mbox{if} \quad x\in E-F \\ g(x)  &\mbox{if} \quad x\in F\end{cases} is a bijection, this of course contradicts that E is uncountable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Indexed Union of Countably Infinite Sets
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: April 4th 2011, 09:55 AM
  2. Finite, countably infinite, or uncountable
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 25th 2011, 08:40 AM
  3. Intersection of two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2011, 06:30 PM
  4. Union of Two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 22nd 2011, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum