# countably infinite / uncountable sets

• February 9th 2010, 11:54 AM
Chizum
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
• February 9th 2010, 12:08 PM
Plato
Quote:

Originally Posted by Chizum
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
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?
• February 9th 2010, 12:15 PM
Chizum
Quote:

Originally Posted by Plato
Just what is your understanding of the term countably infinite?

a set with the same cardinality as N

Quote:

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

Quote:

$A\setminus \{x\}$
• February 9th 2010, 12:37 PM
MoeBlee
Quote:

Originally Posted by Chizum
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
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.
• February 9th 2010, 12:39 PM
MoeBlee
Quote:

Originally Posted by Chizum

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.
• February 9th 2010, 01:18 PM
Drexel28
Quote:

Originally Posted by Chizum
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.