# For every family $\mathscr A$ of sets, there are at least $|\mathscr{A}|$ sets of the form $A_1 \setminus A_2$

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.

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.)
• Sorry to be naive, but what exactly is this map? Given $B-C$ and $D-E$, we map to... what exactly? Sep 4, 2017 at 19:14
• 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}$. Sep 4, 2017 at 19:33
• 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. Sep 4, 2017 at 19:38
• 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. Sep 5, 2017 at 0:16