# Thread: Countable and Uncountable sets

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

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

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

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

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

6. Any subset of a countable set is countable.
Therefore, any superset of an uncountable set must be uncountable.

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