Let $\mathscr{A} $ be a set of sets. Let's denote $\{A \setminus B : A,B \in \mathscr{A}\}$ by $\mathscr{A} \setminus \mathscr{A} $.

The Marica-Schönheim theorem says that $|\mathscr{A} \setminus \mathscr{A}| \geq |\mathscr{A}|$ for every finite $\mathscr{A}$.

This immediately implies the result for countably-infinite $\mathscr{A}$, since if we had $|\mathscr{A} \setminus \mathscr{A}|=n $ is finite, then taking a subset of size $n+1$ out of $\mathscr{A}$ gives a contradiction.

There seems to be no natural one-to-one mapping $\mathscr{A} \to \mathscr{A} \setminus \mathscr{A} $, so this raises the question:

Do we have $|\mathscr{A} \setminus \mathscr{A}| \geq |\mathscr{A}|$ for families $\mathscr{A}$ of arbitrary cardinality?

I asked it on math.SE a while ago.


1 Answer 1


The answer is yes, because from $A$ and $A-B$ and $B-A$, you can reconstruct $B$ via $$B=(B-A)\cup(A-(A-B)).$$ So if we fix $A$, we get a map from $(\mathscr{A}\setminus\mathscr{A})^2$ onto $\mathscr{A}$. So $\mathscr{A}\setminus\mathscr{A}$ must be at least as large as $\mathscr{A}$.

(Note that this argument used $\kappa^2=\kappa$ for infinite cardinals, which requires AC.)

  • $\begingroup$ Sorry to be naive, but what exactly is this map? Given $B-C$ and $D-E$, we map to... what exactly? $\endgroup$ Commented Sep 4, 2017 at 19:14
  • 2
    $\begingroup$ I think you want to fix $A \in \mathcal{A}$ and map your pair to $(B-C) \cup (A - (D-E))$. Note that the restriction of this map to pairs of the form $(B-A, A-B)$ (this is the same $A$ that we fix) gives a surjection onto $\mathcal{A}$. $\endgroup$
    – Tony Huynh
    Commented Sep 4, 2017 at 19:33
  • $\begingroup$ Okay, thanks. For some reason I was thinking the goal was to recover $\mathcal{A}$ from $\mathcal{A}\setminus\mathcal{A}$ rather than just, knowing $\mathcal{A}$, to make a surjection. $\endgroup$ Commented Sep 4, 2017 at 19:38
  • $\begingroup$ @TonyHuynh Yes, that is exactly what I meant. I suppose the next task is to try to construct a counterexample from an amorphous set or an infinite Dedekind-finite set in order to show that the axiom of choice is required. $\endgroup$ Commented Sep 4, 2017 at 19:49
  • $\begingroup$ If $\mathscr{A}$ is infinite, then the argument shows in ZFC that $\mathscr{A}\setminus\mathscr{A}$ has the same size as $\mathscr{A}$. Meanwhile, this conclusion requires the axiom of choice, since if $X$ is an amorphous set and $\mathscr{A}$ consists of the cofinite subsets of $X$, except for $X$ itself, then $\mathscr{A}\setminus\mathscr{A}$ consists precisely of the finite subsets of $X$, which is strictly larger (by one) than $\mathscr{A}$. So the claim that they have the same size is independent of ZF. $\endgroup$ Commented Sep 5, 2017 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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