# Homework Help: Subsets of Uncountable Infinite Sets

1. Feb 1, 2009

### hetaeros

1. The problem statement, all variables and given/known data

Let $$A$$ be an infinite set which is not countable and let $$B \subset A$$ be a countably infinite set.

(1) Show that $$A - B$$ is also infinite and not countable

(2) Show that $$A$$ and $$A - B$$ have the same cardinality

2. Relevant equations

Hints written directly:

"Show that there is a countable subset $$C \subset (A - B)$$ and that there is a bijection $$g : C \cup B \rightarrow B$$, and try to make it into a bijection of $$A$$ with $$A - B$$."

3. The attempt at a solution

Here is what I have so far:

Given the hint, I am thinking that I want to use the fact that a set is infinite if there is a bijection between it and a strict subset of it. However, there's a possibility that the set $$C$$ is a finite subset, which is why I believe the professor gave us that hint about constructing a map from $$C \cup B$$ to make sure it is infinite.

Here, then is where I show that $$C \cup B$$ is infinitely countable.

Define $$C \subset (A - B)$$ as a countable subset of $$A - B$$
Construct $$f : C \cup B \rightarrow B$$
Since $$C$$ and $$B$$ are disjoint countable sets, their union is also countable.

$$B$$ is a countably infinite set
$$\Rightarrow C \cup B$$ is countably infinite
$$\Rightarrow #B = #(C \cup B) = \aleph_{0}$$
$$\exists bijection f : C \cup B \rightarrow B$$

However, this is where I get stuck. I can easily conclude that since $$A$$ is not countable, there is no bijection between and $$C \cup B$$, but that seems quite trivial at the moment, especially if I'm going to be using the theorem from above.

The part that gets me the most is how $$C \cup B$$ could possibly be a strict subset of $$A - B$$, since $$B \notin (A - B)$$. I will probably need to use this fact that $$A - B$$ is infinite, but I am completely lost as to how to go about this.

To prove that $$A - B$$ is also uncountable: will I need to show that there cannot exist a bijection between it and $$C \cup B$$ ? The funny thing about this is that if $$A - B$$ is infinite, it must have a bijection between it and $$C$$, which is where the whole issue with $$C \cup B$$ turns almost circular.

Can someone please help me clear things up and perhaps find a better strategy for a proof?

As per part (2), I would assume that the easiest way to do this is to show that there exists a bijection between $$A - B$$ and $$A$$. Would the results of the previous part be required to solve this?

Thank you for your time--any help would be greatly appreciated!

2. Feb 1, 2009

### Office_Shredder

Staff Emeritus
For part (1), just notice $$(A-B) \cup B$$ = A, and the union of two countable sets is countable.

For part (2), you (should) know there is a countable subset C of A-B. This is useful to know. When making your bijection from A to A-B, try separating it into the case of whether an element of A is in (A-B)-C or not.

3. Feb 1, 2009

### hetaeros

Ah, but we're trying to prove that $$(A - B)$$ is uncountable.

4. Feb 1, 2009

### Dick

Office_Shredder is gently suggesting a proof by contradiction. If (A-B) were countable then so would (A-B) union B. But that's A. And it's not countable. Hence A-B is uncountable.

5. Feb 2, 2009

### hetaeros

Ah, I see. The contradiction comes from the fact that the given A is uncountable.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook