6
$\begingroup$

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.

  • 1
    "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.2012-09-19

1 Answers 1

1

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

  • 1
    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.2012-09-19