Results 1 to 6 of 6

Thread: 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
    21,782
    Thanks
    2824
    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 $\displaystyle 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

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

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    470
    Thanks
    6
    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
    470
    Thanks
    6
    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
    22
    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 $\displaystyle A$ was uncountable but $\displaystyle A-\{x\}$ was countable. Then, there exists a bijection $\displaystyle f:A-\{x\}\mapsto\mathbb{N}$ and so $\displaystyle g:A\mapsto \mathbb{N}\cup \{0\}$ given by $\displaystyle 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 $\displaystyle E$ be uncountable and $\displaystyle F\subseteq E$ be countable. Then $\displaystyle E-F$ is uncountable.

    Proof: Since $\displaystyle E-F$ is countable there exists some $\displaystyle f:E-F\mapsto \mathbb{N}$ which is bijective. Also, since $\displaystyle F$ is countable there is some $\displaystyle g:F\mapsto \mathbb{Z}-\mathbb{N}$ which is also bijective. Clearly then, $\displaystyle \eta:E\mapsto\mathbb{Z}$ given by $\displaystyle \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 $\displaystyle 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: Apr 4th 2011, 09:55 AM
  2. Finite, countably infinite, or uncountable
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 25th 2011, 08:40 AM
  3. Intersection of two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 22nd 2011, 06:30 PM
  4. Union of Two countably infinite sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 22nd 2011, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum