Use boolean algebra to proof $(A\cap B)\Delta (C\cap D)\subseteq (A\Delta C)\cup (B\Delta D)$

Question

I'm trying to prove that $(A\cap B)\Delta (C\cap D)\subseteq (A\Delta C)\cup (B\Delta D)$ and using the laws in set theory might be complicated. I think this can be somehow simplified by the boolean algebra like $1_A\oplus 1_B\leq 1_A \cdot 1_B$ and $1_{A\bigtriangleup B}=1_A\oplus 1_B$ but I'm stuck here.

Similarly, can $(A\cup B)\Delta (C\cup D)\subseteq (A\Delta C)\cup (B\Delta D)$ reduced by boolean algebra, too? I can reduce them to $(1_A\cdot 1_B)\oplus (1_C\cdot 1_D)\leq (1_A\cdot 1_B)\cdot (1_C\cdot 1_D)$ and $(1_A\oplus 1_C)\cdot (1_B\oplus 1_D)\leq (1_A\cdot 1_C)\cdot (1_B \cdot 1_D)$, but that doesn't help.

Answer 1

The "direct" way of using Boolean variables that comes to mind doesn't look simple to me.

For Boolean variables $p,q\in\{0,1\}$, we have

• $\neg p=1-p$,
• $p\wedge q=pq$.

Thus, we also have

• $p\vee q=\neg(\neg p\wedge \neg q)=1-(1-p)(1-q)$,
• $(p\Rightarrow q)=\neg(p\wedge \neg q)=1-p(1-q)$.

For any set $P$, we can think of $x\in P$ as a Boolean-valued function of $x$ which we'll simply call $p$ for short, and do the same for other letters. Then $P\cap Q$ corresponds to $p\wedge q$, and $P\cup Q$ corresponds to $p\vee q$, and $P\bigtriangleup Q$ corresponds to $p+q$ if we interpret addition mod $2$. Plus, $P\subseteq Q$ is equivalent to $p\Rightarrow q$.

Therefore, the subset relation $(A\cap B)\bigtriangleup(C\cap D)\subseteq(A\bigtriangleup C)\cup(B\bigtriangleup D)$ is equivalent to

$$ (ab+cd)\Rightarrow\big[(a+c)\vee(b+d)\big] $$

which becomes $(ab+cd)\Rightarrow\big[1-(1-a-c)(1-b-d)\big]$ which becomes

$$ 1-(ab+cd)(1-a-c)(1-b-d). $$

If you expand this out, and use the fact that for all $x$ mod $2$,

• $x=-x$,
• $x^2=x$,
• $x+x=0$,

then simplification and cancellation results in plain old $1$.

Answer 2

I'll use just $+, \cdot$ as the Boolean ring operations. Note that union $A\cup B$ corresponds to the Boolean operation $1_A+1_B-1_A1_B=1_A+1_B+1_A1_B$. Hence the RHS is $$(1_A+1_C)+(1_B+1_D)+(1_A+1_C)(1_B+1_D)$$ $$=(1_A+1_D+1_A1_D)+(1_B+1_C+1_B1_C)+\text{LHS}$$

To show $X+Y\ge Y$, it suffices to show $XY=0$ (actually, they are equivalent). That is, $A\Delta B$ contains $B$ iff $A\cap B=\emptyset$.

And $$(1_A+1_D+1_A1_D)(1_A1_B+1_C1_D)$$ $$=(1_A1_B+1_A1_C1_D)+(1_A1_B1_D+1_C1_D)+(1_A1_B1_D+1_A1_C1_D)=1_A1_B+1_C1_D$$

which is expected, as $1_A+1_D+1_A1_D=1_{A\cup D}$ and $A\cup D$ clearly covers $(A\cap B)\Delta(C\cap D)$.

similarly, $$(1_B+1_C+1_B1_C)(1_A1_B+1_C1_D)=1_A1_B+1_C1_D$$

hence $$[(1_A+1_D+1_A1_D)+(1_B+1_C+1_B1_C)+\text{LHS}]\cdot(\text{LHS})=0$$