# Countable and Uncountable sets

• Oct 21st 2010, 11:18 AM
zebra2147
Countable and Uncountable sets
Here is a proof that was in my notes. My professor did not do a great job of explaining how to prove a set is countable or uncountable so any explanation would be appreciated.

Prove that if A is uncountable and B is any set, then $\displaystyle A\bigcup B$ is uncountable.

I'm thinking I start by saying that A is some set $\displaystyle A={a_{1},a_{2},a_{3}...}$.
Then, I'm thinking maybe you do a proof by cases? Let B be a set defined by $\displaystyle B={b_{1},b_{2},b_{3}...}$. Then assume B is countable. Then, somehow show $\displaystyle A\bigcup B$ is uncountable.
Then assume B is uncountable. Then, somehow show $\displaystyle A\bigcup B$ is uncountable???
• Oct 21st 2010, 11:21 AM
Ackbeet
I would probably do a cardinality argument. You know that $\displaystyle \text{card}(A\cup B)\ge\text{card}(A).$

Since $\displaystyle A$ cannot be put into a one-to-one correspondence with the integers, surely $\displaystyle A\cup B$ can't as well.

I wouldn't index elements of the set, because that's assuming that there IS a correspondence with the integers, contrary to the uncountable assumption.
• Oct 21st 2010, 11:24 AM
zebra2147
That is a very good suggestion. However, I'm not sure that I'm allowed to use the cardinality arguement since he has not yet discussed it in his class. Is there any other way that you could think of?
• Oct 21st 2010, 11:30 AM
Ackbeet
Hmm. Well, I think this sort of argument is basically what you have to do, since "uncountable" is defined in terms of one-to-one correspondences (or lack thereof) with the integers. Maybe Plato or Opalg could contribute a more direct argument that doesn't use cardinality.
• Oct 21st 2010, 11:37 AM
zebra2147
Alright. Thank you very much for your time and your good explanation.
There is another proof that states... Prove that if A is uncountable and B is countable then A\B is uncountable. I realize this is similar but since card(A\B)<card(A) how would you show this?
• Oct 21st 2010, 11:58 AM
Plato
Any subset of a countable set is countable.
Therefore, any superset of an uncountable set must be uncountable.

$\displaystyle A\subseteq (A\cup B)$.