# How to prove every partition of same cardinality sets has same cardinality?

Assume $A$ is a set, and $A$ is partitioned into two ways, $\{A_i\}$ and $\{B_i$} where any $A_1,A_2 \in \{A_i\}$ and $B_1,B_2 \in \{B_i\}$ we have $|A_1|=|A_2|=|B_1|=|B_2|$. Then is that true $|\{A_i\}|=|\{B_i\}|$?

Intuitively, $|\{A_i\}|=|\{B_i\}|=|A|/|A_1|$ where $A_1 \in \{A_i\}$. However it makes sense when it's only in finite case. I can't construct bijection between those two partitions. Help me.

• Do you assume the axiom of choice? – Asaf Karagila Apr 7 '15 at 7:51
• Sure, I think it needs something like transfinite induction. Otherwise, it will be super-hard. – Maddy Apr 7 '15 at 7:52

## 2 Answers

We can find a counterexample even assuming $\{A_i\}$ is infinite.

Let $\omega_1$ be the first uncountable ordinal. Consider the 1-1 correspondence $f:\omega_1\times\omega_1 \to \omega_1$. Then $$\{f[\omega_1\times\{\alpha\}]: \alpha <\omega_1\}$$ is a partition of $\omega_1$ with cardinality $\aleph_1$ and all of its elements also have cardinality $\aleph_1$. On the other hand, the collection of sets of the form $$A_n = \{\omega\cdot\alpha + n : \alpha<\omega_1\}$$ is countable. You can easily check that $|A_n|=\aleph_1$ holds.

• Why ordinal in $\omega_1$ can be decomposed into $\omega \alpha+n$? – Maddy Apr 7 '15 at 8:19
• @Maddy Since every ordinal has its unique Cantor normal form. – Hanul Jeon Apr 7 '15 at 8:24

The statement is not generally true if $A$ is allowed to be infinite; for instance take $A=\Bbb Z$ and (severely abusing notation) $A_{0,1}=\{0,1\}+2\Bbb Z$ and $B_{0,1,2}=\{0,1,2\}+3\Bbb Z$.

As the comment chain suggests, forcing one of the partitions to have infinitely many parts would probably help, at least with AoC. Unfortunately, I can't see how to do the proof.

• I think you read the question wrong? – Asaf Karagila Apr 7 '15 at 7:56
• @Asaf: That's likely, but I don't see how. I always manage to misread set theory questions even after re-reading them six times. – Eric Stucky Apr 7 '15 at 7:58
• Ohh, right, I'm reading the answer wrong! Sorry. :-) – Asaf Karagila Apr 7 '15 at 8:03
• npnp. Feels nice to get it right for once :P – Eric Stucky Apr 7 '15 at 8:03
• Even simpler: just let $B_0=\{\mathbb Z\}$, so $|\{A_i\}| = 2$ and $|\{B_i\}| = 1$. – TonyK Apr 7 '15 at 11:14