Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 1 / a

We prove both set inclusions, as required by a double inclusion proof. If $x\in A\setminus (B\cup C)$, then $x\in A$ and $x\notin B\cup C$. Thus $x\notin B$ and $x\notin C$, so $x\in A\setminus B$ and $x\in A\setminus C$. This proves the forward set inclusion.

Conversely, if $x\in (A\setminus B)\cap (A\setminus C)$, then $x\in A$, $x\notin B$, and $x\notin C$. Hence $x\notin B\cup C$, giving $x\in A\setminus (B\cup C)$. Therefore

For the first set inclusion, take $x\in (A\cap B)\setminus C$. Membership in the intersection gives $x\in A$ and $x\in B$, while the set difference gives $x\notin C$. Consequently $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, an element of $(A\setminus C)\cap (B\setminus C)$ belongs to both $A$ and $B$ and does not belong to $C$. It therefore belongs to $(A\cap B)\setminus C$. By double inclusion proof,

Complements are relative to the same universal set $\mathcal{U}$. Suppose $A\subseteq B$ and $x\in \overline{B}$. Then $x\in \mathcal{U}$ and $x\notin B$. If $x$ belonged to $A$, the assumed set inclusion would imply $x\in B$, a contradiction. Thus $x\notin A$ and $x\in \overline{A}$, provingThere is only one set inclusion in this conclusion; a reverse inclusion is neither needed nor generally true. The request for double inclusion applies to the equalities in (i) and (ii).