# Cardnality of Infinite Sets (2)

1. Apr 29, 2008

### kingwinner

1) Let A be an infinite set and B is countably infinite set, prove that |A U B| = |A|.

(Incomplete) solution:
Let B={b_1,b_2,b_3,...} since B is countably infinite.
Take A1 in A such that A1={a_1,a_2,a_3,...}. A1 is countably infinite.
Take A2=A \ A1
So A=A1 U A2

Construct map f: A U B->A such that
f(a_i)=a_(2i), if a_i E A1
f(b_i)=a_(2i-1), if b_i E B
f(x)=x, if x E A2

I think this map is at least onto, but it may not be a one-to-one function. The trouble that I can see is that A1 and B may not be disjoint and A2 and B may not be disjoint. If they overlap, then the map f is not a bijection. How can we fix this problem?

Any help is appreciated!

2. Apr 30, 2008

### mutton

To account for the overlap, maybe you can push that overlap into A1 (not A2 due to its possible uncountability). For example, let A1 = {a_1,a_2,a_3,...} U B and A2 be as you have it. Then it seems A U B = A1 U A2 and you're left with two cases for f: one over a countable set and another over a possibly uncountable set.

Furthermore, it seems that {a_1,a_2,a_3,...} isn't necessary under this view because you can consider A1 = B and A2 as above. Then the map would be
A \ B on A \ B
and
B on A $$\cap$$ B, both countable

3. Apr 30, 2008

### kingwinner

So which of the following should I change?
f(a_i)=a_(2i), if a_i E A1
f(b_i)=a_(2i-1), if b_i E B
f(x)=x, if x E A2

Thanks!

4. May 1, 2008

### kingwinner

I have an idea! If I write AUB as "disjoint" union AUB = A1 U (A\A1) U (B\A), would it help?

But how can I define the f: A U B->A as a bijection now?

5. May 1, 2008

### mutton

The disjoint union should exclude A $$\cap$$ B. Your A1 U (A\A1) U (B\A) doesn't do this.

Here is what I was thinking of. Please check that this is actually a bijection.

Let B \ A = {b_1, b_2, ...}
Let A $$\cap$$ B = {c_1, c_2, ...}
Both of these sets are countable because B is countable.

f(b_i) = c_(2i), if b_i E B \ A
f(c_i) = c_(2i - 1), if c_i E A $$\cap$$ B
f(x) = x, if x E A \ B

6. May 1, 2008

### kingwinner

But AUB = A1 U (A\A1) U (B\A) is a disjoint union, right?
B\A means B take away A, so we can't have A$$\cap$$B, right?

7. May 1, 2008

### kingwinner

If I define
f: A U B->A such that
f(a_i)=a_(2i), if a_i E A1
f(b_i)=a_(2i-1), if b_i E B\A
f(x)=x, if x E A2

Would this be one-to-one and onto? I think the sets are disjoint and can't have any overlap now, so I think it's one-to-one, but I am not totally sure. Can someone please confirm this?

8. May 1, 2008

### jambaugh

There is an issue here. The statement is not necessarily true if you do not assume the continuum hypothesis or equivalently the axiom of choice.

If A is an infinite set then $$|A| \ge |\mathbf{N}|=\aleph_0$$

Thus $$|A| \ge |B|$$

Then consider that $$|A\cup B| = |A|$$ is equivalent to $$|A \cup B| \le |A| \text{ and }|A \cup B| \ge |A|$$
(This is the Cantor–Bernstein–Schroeder theorem)

It is much easier to construct injections rather than bijections so using the obvious subset injection to show $$|A| \le |A\cup B|$$ you only need to find an injection showing that $$|A\cup B| \le |A|$$. You can use the one you get from the continuum hypothesis: $$|B| \le |A|$$ directly or you can worry it out from the axiom of choice.

Recall that cardinal lax inequality is defined as the existance of an injective mapping:
$$|A|\le|C| \quad \equiv \quad \exists \phi:A \stackrel{inj}{\rightarrow}C$$

9. May 1, 2008

### mutton

But A $$\subseteq$$ A1 U (A\A1) whatever A1 you pick inside the regular union A U B. So A $$\cap$$ B $$\subseteq$$ A1 U (A\A1) U (B\A). Draw some Venn diagrams.

10. May 1, 2008

### mutton

Check these as usual. For one-to-one, let x, y in A U B be such that f(x) = f(y). Then x, y must both be in A1, B \ A, or A2 because otherwise, f(x) $$\neq$$ f(y) because . . .

11. May 1, 2008

### kingwinner

Hold on...I don't understand what's wrong with my claim that AUB = A1 U (A\A1) U (B\A) is a disjoint union

note: B\A={xEB|x is not in A}

A1 and (A\A1) can never intersect
A1 and (B\A) can never intersect
(A\A1) and (B\A) can never intersect

=> AUB = A1 U (A\A1) U (B\A) is a disjoint union, right?

Define f: A U B->A
f(a_i)=a_(2i), if a_i E A1
f(b_i)=a_(2i-1), if b_i E (B\A)
f(x)=x, if x E (A\A1)

f is clearly onto.

The key question is : is f a one-to-one function?
Since AUB = A1 U (A\A1) U (B\A) is a disjoint union, the a_i, b_i, x are taking elements from disjoint sets, and so must be one-to-one function, and this is all I need to prove.

The trouble that may arise if the sets are not disjoint is e.g. f(a1)=a2, f(b1)=a1, but actually a1=b1, so the same element is mapped to 2 different elements, which means that f is not a "function", and hence is not one-to-one, it's one-to-many. But if A1 U (A\A1) U (B\A) is a disjoint union, then this trouble cannot occur and f has to be a one-to-one function.

Please correct me if anywhere is wrong.

P.S. I understand that A $$\cap$$ B $$\subseteq$$ A1 U (A\A1) U (B\A), but why does this matter? AUB of course contains all elements in the intersection of A and B. Again, please correct me if I am wrong, I may be totally missing something.

Last edited: May 1, 2008
12. May 2, 2008

### jambaugh

Forget what I said about continuum hypothesis. It was late, I was confused. Still I think that you're going to run into difficulties if you don't invoke CBS.

Here is my proof:
$$|A| \le |A\cup B|$$ since $$A\subseteq A\cup B$$

Let $$C = (A\cup B)/A$$ and observe $$C\subseteq B$$ and $$C\cap A =\emptyset$$

$$|A| \le |B| \le |C|$$ since A is infinite.
thus $$\exists \varphi:C\to A$$ where $$\varphi$$ is injective (into).

If $$|A / \varphi(C) | \le |B|$$ then A is countable and the result is trivial, the union of two countable sets is countable.

Otherwise if $$|B| < |A / \varphi(C) | <|A|$$ then by disjoint unions of sets of equal cardinality:
$$|B\cup C| < |A/\varphi(C)\cup \varphi(C)| < |A\cup C|$$
or
$$|A\cup B| < |A| < |A\cup B|$$ which is impossible.

Thus otherwise $$|A|\le |A/ \varphi(C)|$$ then of course $$|A| = |A/\varphi(C)|$$
and $$\exists \psi:A\to (A/\varphi(C)$$
where $$\psi$$ is bijective and thus injective.

You can then take the union of disjoint mappings
$$\eta= \psi \cup \varphi$$ which is an injective map $$\eta:A\cup C\to A$$
Since $$A\cup C = A \cup B$$ we have that: $$|A\cup B| \le |A|$$.

Thus by CBS whe have $$A\cup B| = |A|$$.