2
$\begingroup$

I am having trouble proving the theorem below:

$A \cup (B - C) = (A \cup B) - (C - A)$

Using the direct method I am to assume that the hypothesis is true. So that is where I start:

$\begin{array}{ccl} A \cup (B-C) & = & \{x \;|\; x\in A \vee x \in (B-C) \} \\ & = & \{x \;|\; x \in A \vee (x \in B \wedge x \not\in C)\} \\ & = & \{x \;|\; (x \in A \vee x \in B) \wedge (x \in A \vee x \not\in C)\} \end{array}$

But I don't know where to go from here. I have $(A \cup B)$ on the right side but how do I derive "$- (C - A)$"?

1 Answers 1

1

Use De Morgan's laws to rewrite $x\in A \lor x\not\in C$ to $\neg(x\not\in A\land x\in C)$, and then commutativity of $\land$ for $\neg(x\in C \land x\not\in A)$.

By the way, it is also useful to be able to do these manipulation at the set level, without explicitly unfolding to a comprehension formula: $A\cup(B\setminus C)=A\cup(B\cap \overline C)=(A\cup B)\cap(A\cup\overline C)=\ldots$