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.

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

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.

  • $\begingroup$ Why ordinal in $\omega_1$ can be decomposed into $\omega \alpha+n$? $\endgroup$ – Maddy Apr 7 '15 at 8:19
  • $\begingroup$ @Maddy Since every ordinal has its unique Cantor normal form. $\endgroup$ – 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.

  • $\begingroup$ I think you read the question wrong? $\endgroup$ – Asaf Karagila Apr 7 '15 at 7:56
  • $\begingroup$ @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. $\endgroup$ – Eric Stucky Apr 7 '15 at 7:58
  • 1
    $\begingroup$ Ohh, right, I'm reading the answer wrong! Sorry. :-) $\endgroup$ – Asaf Karagila Apr 7 '15 at 8:03
  • 1
    $\begingroup$ npnp. Feels nice to get it right for once :P $\endgroup$ – Eric Stucky Apr 7 '15 at 8:03
  • 1
    $\begingroup$ Even simpler: just let $B_0=\{\mathbb Z\}$, so $|\{A_i\}| = 2$ and $|\{B_i\}| = 1$. $\endgroup$ – TonyK Apr 7 '15 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.