4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry to be naive, but what exactly is this map? Given $B-C$ and $D-E$, we map to... what exactly? $\endgroup$
    – Zach Teitler
    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$
    – Zach Teitler
    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$
    – Joel David Hamkins
    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$
    – Joel David Hamkins
    Commented Sep 5, 2017 at 0:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .