# cardinality of infinite sets

prove or disprove:

If two infinite sets $A$,$B$ have the same cardinality, then $A\cup B$ and $A$ have the same cardinality.

I even cannot make a judgement.

P.S: Can this be done without using cardinals? This concept has not been introduced in class yet.

-
For infinite cardinals $\kappa, \lambda,$ $\kappa + \lambda = \max\{\kappa + \lambda\}$. –  tomcuchta Sep 19 '12 at 3:08
@tomcuchta Do you mean $\max\{\kappa,\lambda\}$? –  yunone Sep 19 '12 at 3:13
I believe this requires the Axiom of Choice (or some fragment thereof.) –  Trevor Wilson Sep 19 '12 at 3:21
Recall that one definition of an infinite set $S$ is that there exists a set $S'\subset S$ for which a bijection exists between $S'$ and $S$. That should help. –  crf Sep 19 '12 at 3:22
"If the axiom of choice is also true, infinite sets are precisely the Dedekind-infinite sets [which are sets which can be put into bijection with some of their proper subsets]." Huh, learn something new every day. That axiom of choice sure does pop up a lot. –  crf Sep 19 '12 at 3:43
show 7 more comments

Since $A\cup B$ contains $A$, and we have an injection $A\cup B= A\sqcup(B\setminus A)\to A\sqcup A$, by the Cantor-Schroeder-Bernstein theorem it is enough to show $A\sqcup A$ has the same cardinality as $A$ whenever $A$ is infinite.

The idea behind the proof is that we know how to interleave two copies of $\mathbb{N}$, so write $A$ as a disjoint union of copies of $\mathbb{N}$ and interleaf each corresponding pair separately.

In particular, form a bijection $\mathbb{N}\sqcup\mathbb{N}\to\mathbb{N}$ by surjecting each copy of $\mathbb{N}$ onto the sets of even and odd natural numbers. For general $A$, consider all the ways of partitioning a subset of $A$ into countable subsets. These are partially ordered by containment, i.e. partition $P$ is contained in partition $Q$ if, for any countable subset $S\subset A$ included in $P$, it is also included in $Q$. Furthermore, if $\{P_\alpha\}$ is any ascending chain of such partitions, then $\bigcup_\alpha P_\alpha$ is also a partition of a subset of $A$ into countable subsets. So by Zorn's lemma, there is a maximal such partition $P$.

If $P$ is maximal, then $A\setminus\bigcup P$ must be finite, or else we could pull out another countable subset from $A$ and add it to $P$. Then pick any element $S$ of $P$ and replace it with the countable set $S\cup (A\setminus\bigcup P)$; the modified partition $P'$ is therefore a partition of $A$ into disjoint countable subsets.

We can therefore write $A\cong \bigsqcup_{S\in P'}\mathbb{N}$.

Then $A\sqcup A\cong(\bigsqcup_{S\in P'}\mathbb{N})\sqcup(\bigsqcup_{S\in P'}\mathbb{N})\cong \bigsqcup_{S\in P'}(\mathbb{N}\sqcup\mathbb{N})\cong\bigsqcup_{S\in P'}\mathbb{N}\cong A$.

-
This seems excessively complicated to me. If you're going to invoke ZL/AC (which I think you do have to do), wouldn't it be simpler to start by well-ordering $A$ and $B$? –  MJD Sep 19 '12 at 4:04
@MJD: It is the same thing: If you well order $A$ you can assume it is in limit order type, and then check that both the set of odd ordinals and the set of even ordinals have the same order type as $A$, so $A\sim A\sqcup A$. This is exactly what is being done here, as the bijection is carried out by blocks of type $\omega$. –  Andres Caicedo Sep 19 '12 at 4:33
And yes, some amount of choice is needed. –  Andres Caicedo Sep 19 '12 at 4:34
@AndresCaicedo Any idea how much? I understand that the equivalence between $A$ and $A\times A$ is fully equivalent to AC, and I would suspect this is the same but I've never seen this form... –  Steven Stadnicki Sep 19 '12 at 8:16
That $A$ and $A\sqcup A$ are equipotent for all infinite $A$ (the idemmultiple hypothesis) is strictly weaker than choice. I learned this recently, via Asaf Karagila. The reference is Gershon Sageev, "An independence result concerning the axiom of choice", Ann. Math. Logic 8, (1975), 1–184. MR0366668 (51 #2915). The question of whether the idemmultiple hypothesis implies choice was asked by Tarski in 1924, it is a difficult problem, Sageev's paper is rather intricate. –  Andres Caicedo Sep 19 '12 at 16:30