- #1

hetaeros

- 6

- 0

## Homework Statement

Let [tex]A[/tex] be an infinite set which is not countable and let [tex]B \subset A[/tex] be a countably infinite set.

(1) Show that [tex]A - B[/tex] is also infinite and not countable

(2) Show that [tex]A[/tex] and [tex]A - B[/tex] have the same cardinality

## Homework Equations

Hints written directly:

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

## 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 [tex]C[/tex] is a finite subset, which is why I believe the professor gave us that hint about constructing a map from [tex]C \cup B[/tex] to make sure it is infinite.

Here, then is where I show that [tex]C \cup B[/tex] is infinitely countable.

Define [tex]C \subset (A - B)[/tex] as a countable subset of [tex]A - B[/tex]

Construct [tex]f : C \cup B \rightarrow B[/tex]

Since [tex]C[/tex] and [tex]B[/tex] are disjoint countable sets, their union is also countable.

[tex]B[/tex] is a countably infinite set

[tex]\Rightarrow C \cup B[/tex] is countably infinite

[tex]\Rightarrow #B = #(C \cup B) = \aleph_{0}[/tex]

[tex]\exists bijection f : C \cup B \rightarrow B[/tex]

Construct [tex]f : C \cup B \rightarrow B[/tex]

Since [tex]C[/tex] and [tex]B[/tex] are disjoint countable sets, their union is also countable.

[tex]B[/tex] is a countably infinite set

[tex]\Rightarrow C \cup B[/tex] is countably infinite

[tex]\Rightarrow #B = #(C \cup B) = \aleph_{0}[/tex]

[tex]\exists bijection f : C \cup B \rightarrow B[/tex]

However, this is where I get stuck. I can easily conclude that since [tex]A[/tex] is not countable, there is no bijection between and [tex]C \cup B[/tex], 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 [tex]C \cup B[/tex] could possibly be a strict subset of [tex]A - B[/tex], since [tex] B \notin (A - B)[/tex]. I will probably need to use this fact that [tex]A - B[/tex] is infinite, but I am completely lost as to how to go about this.

To prove that [tex]A - B[/tex] is also uncountable: will I need to show that there cannot exist a bijection between it and [tex]C \cup B[/tex] ? The funny thing about this is that if [tex]A - B[/tex] is infinite, it must have a bijection between it and [tex]C[/tex], which is where the whole issue with [tex]C \cup B[/tex] 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 [tex]A - B[/tex] and [tex]A[/tex]. Would the results of the previous part be required to solve this?

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