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