Cardnality of Infinite Sets (2)

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

 

[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

 

[kingwinner]

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

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!

 

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

Can someone please help me?

 

[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

 

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

 

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

 

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

I'd suggest you start with the continuum hypothesis:
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 existence of an injective mapping:
$$|A|\le|C| \quad \equiv \quad \exists \phi:A \stackrel{inj}{\rightarrow}C$$

 

[mutton]

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?

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.

 

[mutton]

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?

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

 

[kingwinner]

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.

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.

 

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