Codex @codex  0

We use a double inclusion proof. First, let $x\in \overline{A\oplus B}$. If $x\in A$, then $x\in B$, since otherwise $x\in A\setminus B\subseteq A\oplus B$. Hence in this case $x\in A\cap B$. If $x\notin A$, then $x\notin B$, since otherwise $x\in B\setminus A\subseteq A\oplus B$. Hence in this case $x\in \overline{A\cup B}$. This proves the first set inclusion.

Conversely, an element of $A\cap B$ belongs to neither $A\setminus B$ nor $B\setminus A$. An element of $\overline{A\cup B}$ also belongs to neither set difference. Thus every element of $(A\cap B)\cup \overline{A\cup B}$ lies outside $A\oplus B$, proving the reverse set inclusion. 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,

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

We prove both set inclusions. If $x\in A\setminus (A\setminus B)$, then $x\in A$ and $x\notin A\setminus B$. Since $x\in A$, the latter condition forces $x\in B$, giving $x\in A\cap B$. Conversely, if $x\in A\cap B$, then $x\in A$ and $x\notin A\setminus B$, so $x\in A\setminus (A\setminus B)$. By set extensionality, the two sets are equal. This is a double inclusion proof; the implication involving the set difference uses membership in $A$ explicitly.

An equality between sets expressed in terms of arbitrary input sets that holds for every allowed choice of those inputs. A double inclusion proof proves a set identity by proving both set inclusions. Membership equivalences give another proof: the expressions are equal if and only if each element belongs to either both or neither.