Prove that if $x \in A$ and $x \not\in (B \cap C^c)$, then $(x \in A$ and $x \not\in B)$ or $(x \in A$ and $x \not\in C^c)$

Question

This is part of a larger proof where I am attempting to show that $$A \setminus (B \setminus C) = (A \setminus B) \cup (A \setminus C^c).$$

I have already shown that $(A \setminus B) \cup (A \setminus C^c) \subseteq A \setminus (B \setminus C)$.

I also know that $A \setminus (B \setminus C) = A \setminus (B \cap C^c)$. My proof so far only consists of

"If $x \in A \setminus (B \cap C^c)$, then $x \in A$ and $x \not\in B \cap C^c$. If $x \not\in B \cap C^c$ then $x \in B$ and $x \in C^c$. Thus if $x \in A \setminus (B \cap C^c)$, then $(x \in A$ and $x \not\in B)$ or $(x \in A$ and $x \not\in B).$"

The problem I am having is that I can't use the distributive properties of conjunctions and disjunctions to prove this (as we have not done them so far). I'm not quite sure how to go about showing the above without using propositional logic. Any help would be appreciated.

Answer 1

From De Morgan's laws (you can also prove them yourselves), you have that $B \cap C^C = (B^c \cup C)^C$.

Then $A \setminus (B^c \cup C)^C = A \cap (B^C \cup C)$ by definition of set difference.

For the Distributive property in set algebra, you get that $A \cap (B^C \cup C) = (A \cap B^C) \cup (A \cap C)$.

Now observe that $A \cap B^C = A \setminus B$ and $A \cap C = A \setminus C^c$ by definition of set difference.

Thus $ (A \cap B^C) \cup (A \cap C) = (A \setminus B) \cup (A \setminus C^c)$ and you have your thesis.

Indeed, if $x \in (A \setminus B) \cup (A \setminus C^C)$, then $x \in A \setminus B$ or $x \in A \setminus C^C$, which means that $$(x \in A \ \ \text{and} \ \ x \notin B) \ \ \text{or} \ \ (x \in A \ \ \text{and} \ \ x \notin C^C).$$

Answer 2

Let DeMorgan's rules and distributivity do the logic for you. Here is a direct, one liner, (set) algebra proof.

A - (B - C) = A - (B $\cap$ C$^c$)
= A $\cap (B^c \cup C) = (A - B) \cup (A \cap C)$
= (A - B) $\cup$ (A - C$^c$)