# countably infinite / uncountable sets

• Feb 9th 2010, 10: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
• Feb 9th 2010, 11:08 AM
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 $\displaystyle A\setminus \{x\}$ were not uncountable?
• Feb 9th 2010, 11:15 AM
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:

$\displaystyle A\setminus \{x\}$
• Feb 9th 2010, 11:37 AM
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.
• Feb 9th 2010, 11:39 AM
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.
• Feb 9th 2010, 12: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 $\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.