Subsets of Uncountable Infinite Sets

[hetaeros]

Homework Statement

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

Homework 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."

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!

 

[Office_Shredder]

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.

 

[hetaeros]

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.

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

 

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

 

[hetaeros]

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