Set Theory Problem (with Symmetric Differences)

Question

I'm reading "Shattering-extremal set systems of VC dimension at most 2" by Tamás Mészáros and Lajos Rónyai, which is not about set theory, but uses a lot of set theory and shows none of its steps. I've been left to fill in the blanks, which I'm really struggling with! I'm trying to draw lots of Venn diagrams but I can't seem to get anywhere.

Here is the information: $A\bigtriangleup B=\{x_1\},B\bigtriangleup C =\{x_2\}, D=B\bigtriangleup \{x_1,x_2\}, C\bigtriangleup D=\{x_1\},A\bigtriangleup D=\{x_2\}.$

They claim that the following sets will each be one of $\{A,B,C,D\}$: $$B\cap D, (B\cap D)\cup \{x_1\},(B\cap D)\cup \{x_2\}, (B\cap D)\cup \{x_1,x_2\}.$$

I'm trying to use the definition of the symmetric difference, but my expressions get very messy very fast.

---

Mészáros, Tamás; Rónyai, Lajos, Shattering-extremal set systems of VC dimension at most 2, Electron. J. Comb. 21, No. 4, Research Paper P4.30, 17 p. (2014). ZBL1302.05201.

Answer 1

Let $X= A\setminus\{x_1,x_2\}$

A first good step is to show $A,B,C$ and $D$ all contain $X$ and are all contained in $X\cup \{x_1,x_2\}$

Notice that we have $X = B\cap D$ because neither $x_1$ nor $x_2$ can be in both sets.

There are only $4$ sets that contain $X$ and are contained in $X\cup\{x_1,x_2\}$ (they are $X,X\cup\{x_1\},X\cup\{x_2\}$ and $X\cup\{x_1,x_2\}$ ).

So all we have to show is that none of $A,B,C,D$ are equal.

To do this notice:

$B\Delta A = \{x_1\}$

$B\Delta C = \{x_1,x_2\}$

To calculate $B\Delta D$ we are going to take a couple of steps. First notice since $C\Delta D = \{x_1\}$ we have $D= C\Delta\{x_1\}$

Now we have: $B\Delta D = B\Delta(C\Delta \{x_1\}) = (B\Delta C) \Delta \{x_1\} = \{x_1,x_2\} \Delta \{x_1\} = \{x_2\}$.

Since $B\Delta A$ and $B\Delta C$ and $B\Delta D$ are all different and non-empty it follows $A,B,C$ and $D$ are $X,X\cup\{x_1\},X\cup\{x_2\}$ and $X\cup\{x_1,x_2\}$ in some order, as desired.

---

Alternative solution:

$B= A\Delta(A\Delta B) = A \Delta \{x_1\}$

$C= B\Delta(B\Delta C) = (A\Delta\{x_1\}) \Delta \{x_2\} = A \Delta \{x_1,x_2\}$

$D= A\Delta(A\Delta D) = A \Delta \{x_2\}$.

It follows that $A,B,C,D$ are all distinct subsets that contain $A\setminus \{x_1,x_2\}$ and that are all contained in $A\cup \{x_1,x_2\}$. We can also see that $B\cap D = A\setminus \{x_1,x_2\}$, to see this notice $B\cap D = (A\Delta \{x_1\} ) \cap(A\Delta\{x_2\})$, so it is impossible for both intersecands to contain $x_1$ and it is impossible for both intersecands to contain $x_2$.

We conclude $B\cap D = A\setminus \{x_1,x_2\}$. So the sets $A,B,C,D$ must be the four sets that contain $B\cap D$ but are contained in $B\cap D \cup \{x_1,x_2\}$ in some order as desired.