2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ $C\Delta D \Delta C = \{x_1\} \Delta C$ (the symmetric difference is a commutative and associative operation and $A\Delta A = \varnothing$ for all $A$ ). You can think of the symmetric difference as an abelian group in which every element has order $2$ and that speeds up computations. $\endgroup$
    – Asinomás
    Apr 6, 2021 at 3:41
  • 1
    $\begingroup$ Well, the most important part is that you understand why $A,B,C$ and $D$ all contain $X$ and are contained in $X\cup\{x_1,x_2\}$. Is that part clear? $\endgroup$
    – Asinomás
    Apr 6, 2021 at 3:46
  • 1
    $\begingroup$ The main idea is that $A,B,C$ and $D$ are all pretty much the same set, except for the elements $\{x_1\}$ and $\{x_2\}$. $\endgroup$
    – Asinomás
    Apr 6, 2021 at 3:53
  • 1
    $\begingroup$ @GraphMathTutor It's a lot easier to understand $A\Delta B$ as the elements that differentiate $A$ and $B$, and in this case we get that for all combinations $A\Delta B$, $A\Delta C$, $A\Delta D$ etcetera, the only elements that differentiate the sets are among $x_1$ and $x_2$. $\endgroup$
    – Asinomás
    Apr 6, 2021 at 3:55
  • 1
    $\begingroup$ No, we don't know that $A$ is the parent set. When I write $A\setminus \{x_1,x_2\}$ I don't mean to say that $A$ necessarily contains $x_1$ and $x_2$, you can define set substractions even when you don't know the elements are in there. $\endgroup$
    – Asinomás
    Apr 6, 2021 at 3:57

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.