1
$\begingroup$

I am just learning set theory proofs and I am struggling with the following:

Prove that $(S_1 \setminus S_2) \cup (S_2 \setminus S_3) \subseteq (S_1 \cup S_2) \setminus(S_1 \cap S_2 \cap S_3)$

Here is my attempt so far:

  1. Let $x \in (S_1 \setminus S_2) \cup (S_2 \setminus S_3)$ so we know by definition that $x\in S_1 $and $ x \notin S_2$ or $x\in S_2 $and $ x \notin S_3$.
  2. So $x \in S_1$ or $x\in S_2$ and $x \notin S_2$ and $x \notin S_3$.
  3. $(S_1 \cup S_2) \setminus(S_2\cap S_3)$

I am unsure on how to continue this proof or if my steps above are even correct. Any help or insights are greatly appreciated. Thank you!

$\endgroup$
0
1
$\begingroup$

Fix $x\in (S_1\setminus S_2)\cup (S_2\setminus S_3)$.

Suppose first that $x\in S_1\setminus S_2$. Then $x\in S_1$, and so $x\in S_1\cup S_2$. Also, $x\not\in S_2$, so $x\not \in S_1\cap S_2\cap S_3$. Therefore, $x\in (S_1\cup S_2)\setminus (S_1\cap S_2 \cap S_3)$.

The case $x\in S_2\setminus S_3$ is analogous.

$\endgroup$
1
  • $\begingroup$ Thank you for this insight! $\endgroup$ Oct 12 '20 at 1:20
0
$\begingroup$

You can also use set algebra to simplify the inclusion you have to prove. Recall that by definition $A\backslash B=A\cap B^c$.

So we have \begin{equation} \begin{split} (S_1\cup S_2)\backslash(S_1\cap S_2\cap S_3)&=(S_1\cup S_2)\cap(S_1\cap S_2\cap S_3)^c\\&=(S_1\cup S_2)\cap({S_1}^c\cup {S_2}^c\cup {S_3}^c) \end{split}\tag{1} \end{equation}

And for the other set, \begin{equation} \begin{split} (S_1\backslash S_2)\cup(S_2\backslash S_3)&=(S_1\cap {S_2}^c)\cup(S_2\cap {S_3}^c)\\ &=(S_1\cup S_2)\cap(S_1\cup {S_3}^c)\cap({S_2}^c\cup S_2)\cap ({S_2}^c\cup {S_3}^c)\\ &=(S_1\cup S_2)\cap\big((S_1\cap {S_2}^c)\cup{S_3}^c\big) \end{split}\tag{2} \end{equation}

So from (1) and (2), it suffices to prove that $$\big((S_1\cap {S_2}^c)\cup{S_3}^c\big)\subseteq({S_1}^c\cup {S_2}^c\cup {S_3}^c)$$ hint: $(S_1\cap {S_2}^c)\subseteq S_2^c$

$\endgroup$

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.