# Set Difference

Set Difference
Suppose that $$A , B$$ are sets, then $$A \setminus B := \{a \in A: a \notin B \}$$ and call it the set difference of $$A$$ and $$B$$
set difference is empty iff one is a superset of the other
Suppose that $$A , B$$ are sets, then $$A \backslash B = \emptyset$$, if and only if $$A \subseteq B$$
TODO
Difference of a Superset is Empty
Suppose that $$A, B \subseteq X$$ are sets such that $$A \subseteq B$$, then $$\left( X \setminus B \right) \cap A = \emptyset$$
Let $$p \in \left( X \setminus B \right) \cap A$$, therefore $$p \in X$$, $$p \notin B$$ and $$p \in A$$, this is impossible since if $$p \in A$$ then $$p \in B$$ as $$A \subseteq B$$, therefore no such $$p$$ is an element of this set, so that $$\left( X \setminus B \right) \cap A = \emptyset$$
Empty Intersection implies Superset Difference
Suppose that $$A, B \subseteq X$$ are sets, assuming $$A \cap B = \emptyset$$ , then $$X \setminus A \supseteq B$$
Taking an element $$p \in B$$ we'd like to show that $$p \in X \setminus A$$, we can see $$p \in X$$ because $$B \subseteq X$$, it's also clear that $$p \notin A$$ since if it were then $$A \cap B \neq \emptyset$$ which would be a contradiction. Combining this, we have that $$p \in X \setminus A$$ as needed.
Set Difference with Itself is Empty
$$X \backslash X = \emptyset$$
TODO
Set Difference with the Empty set is Itself
$$X \backslash \emptyset = X$$
TODO
Redundant Intersection in Difference
Suppose that $$A , B , X$$ are sets then $$\left ( A \cap X \right ) \backslash B = \left ( A \cap X \right ) \backslash \left ( B \cap X \right )$$

Suppose that $$p \in \left ( A \cap X \right ) \backslash B$$ therefore $$p \in A$$, $$p \in X$$ but $$p \notin B$$, we can see that $$p \in \left ( A \cap X \right )$$ and since $$p \notin B$$, then $$p \notin \left (B \cap X \right )$$, therefore $$p \in \left ( A \cap X \right ) \backslash \left ( B \cap X \right )$$

Now suppose that $$p \in \left ( A \cap X \right ) \backslash \left ( B \cap X \right )$$, so that $$p \in A \cap X$$ and $$p \notin B \cap X$$, from this we deduct that $$p \in X$$, so to avoid contradiction, we must have $$p \notin B$$, since we also know $$p \in A$$, we can say that $$p \in \left ( A \cap X \right ) \setminus B$$

Intersection Distributes through Set Difference
Suppose that $$A , B , X$$ are sets then $$\left ( A \backslash B \right ) \cap X = \left ( A \cap X \right ) \backslash B$$

Suppose that $$p \in \left ( A \backslash B \right ) \cap X$$ so $$p \in A$$, $$p \notin B$$ and $$p \in X$$, this means that $$p \in A \cap X$$ and $$p \notin B$$, this shows that $$p \in \left ( A \cap X \right ) \backslash B$$ as needed

Now suppose that $$p \in \left ( A \cap X \right ) \backslash B$$ so $$p \in A$$, $$p \in X$$ but $$p \notin B$$, recombining this information we can see that $$p \in \left ( A \backslash B \right ) \cap X$$, as needed.

Union Intersection Inversion through set Difference
Suppose that $$A , B , C$$ are sets then $$A \backslash \left ( B \cap C \right ) = A \backslash B \cup A \backslash C$$

We know that $$x \in A \backslash \left ( B \cap C \right )$$ is true iff $$x \in A$$ and $$x \notin \left ( B \cap C \right )$$, equivalent to $$x \notin B$$ or $$x \notin C$$, since $$x \in A$$, we can biconditionally re-write this as $$x \in A \backslash B$$ or $$x \in A \backslash C$$ iff $$x \in \left ( A \backslash B \right ) \cup \left ( A \backslash C \right )$$

Since all connectives in the above proof are bi-conditionals, then we know that $$A \backslash \left ( B \cap C \right ) = \left ( A \backslash B \right ) \cup \left ( A \backslash C \right )$$

Double Difference creates Intersection
Suppose that $$A , B , C$$ are sets such that $$A \subseteq B$$, then $$A \backslash \left ( B \backslash C \right ) = \left ( A \backslash B \right ) \cap C$$

Suppose that $$x \in A \backslash \left ( B \backslash C \right )$$ which is true iff $$x \in A$$ and $$x \notin \left ( B \backslash C \right )$$ which means that it's not true that $$\left ( x \in B \quad\text{and}\quad x \notin C \right )$$ so that $$x \notin B$$ or $$x \in C$$, since $$x \in A$$ and we know that $$A \subseteq B$$ then $$x \in B$$, which forcs $$x \in C$$ to avoid a contradiction, therefore 

Suppose that $$x \in A \backslash B \cap C$$, therefore $$x \in A$$, $$x \notin B$$ and $$x \in C$$, thus we can see that $$x \notin B \backslash C$$ thus $$x \in A \backslash \left ( B \backslash C \right )$$

Triple Difference Equality
Suppose that $$A , B , C$$ are sets such that $$A \subseteq B$$, then $$A \backslash \left ( B \backslash C \right ) = \left ( A \cap C \right ) \cup \left ( A \setminus B \right)$$

$$x \in A \backslash \left ( B \backslash C \right )$$ iff $$x \in A$$ and $$x \notin \left ( B \backslash C \right )$$ equivalent to the following statement not being true: $$\left ( x \in B \land x \notin C \right )$$ which is $$x \notin B$$ or $$x \in C$$, therefore $$x \in A \cap C$$ or $$x \in A \setminus B$$ so that $$x \in \left ( A \cap C \right ) \cup \left ( A \setminus B \right)$$

The above chain of steps can be traversed forwards or backwards since each connective is an iff, therefore the proof is complete

TODO
Suppose that $$A , B$$ are sets, then $$A \backslash \left ( A \backslash B \right ) = A \cap B$$

Suppose that $$x \in A \backslash \left ( A \backslash B \right )$$ which is true iff $$x \in A$$ and $$x \notin \left ( A \backslash B \right )$$ which means that it's not true that $$\left ( x \in A l \quad\text{and}\quad x \notin B \right )$$ we already know that $$x \in A$$ holds, so we must have that $$x \notin B$$ to be false, which means that $$x \in B$$ so that $$x \in A \cap B$$

Suppose that $$x \in A \cap B$$, since $$x \in B$$, then it's not true that $$x \notin B$$, therefore $$x \notin \left ( A \backslash B \right )$$ since $$x \in A$$, this shows that $$x \in A \backslash \left ( A \backslash B \right )$$

TODO
Suppose that B sube A, then A \\ (A \\ B) = B
A \\ (A \\ B) = A nn B since A nn B = B, we are done
TODO
Suppose that $$Y \subseteq X$$ and $$Y \backslash A = Y \cap U$$, then $$A = Y \cap \left ( X \backslash U \right )$$ solves the given equation
Suppose that $$A = Y \cap \left ( X \backslash U \right )$$, then $$Y \backslash A = Y \backslash \left ( Y \cap \left ( X \backslash U \right ) \right ) = \left ( Y \backslash Y \right ) \cup \left ( Y \backslash \left ( X \backslash U \right ) \right ) = \emptyset \cup$$
DeMorgan's Laws
Suppose that $$M$$ is a family of sets, then $$X \backslash \left ( \bigcup_{A \in M} A \right ) = \bigcap_{A \in M} \left ( X \backslash A \right )$$ and $$X \backslash \left ( \bigcap_{A \in M} A \right ) = \bigcup_{A \in M} \left ( X \backslash A \right )$$

Note that, $$p \in X \backslash \left ( \bigcup_{A \in M} A \right )$$, if and only if $$p \in X$$ and $$x \notin \bigcup_{A \in M} A$$, which is equivalent to: for all $$A \in M$$ $$p \notin A$$, which is the same as $$p \in \left ( X \backslash A \right )$$ for each $$A \in M$$, so by definition $$p \in \bigcap_{A \in M} \left ( X \backslash A \right )$$. Since each connective in the previous paragraph was an iff, then this implies the two sets are equal

For the second proof, we'll follow a similar structure to the first. Note that, $$p \in X \backslash \left ( \bigcap_{A \in M} A \right )$$, if and only if $$p \in X$$ and $$x \notin \bigcap_{A \in M} A$$, which is equivalent to: there is some $$A \in M$$ $$p \notin A$$, which is the same as $$p \in \left ( X \backslash A \right )$$ for some $$A \in M$$, so by definition $$p \in \bigcup_{A \in M} \left ( X \backslash A \right )$$. Since each connective in the previous paragraph was an iff, then this implies the two sets are equal