# Thread: countably infinite / uncountable sets

1. ## 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

2. 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?

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?

3. Originally Posted by Plato
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\}$

4. 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?

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.

5. 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.

6. 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.