__Sets Proofs__
===============

By _Joram Stith_ and _Noah Soto_

## Proofs Involving the Empty Set

For sets $A$, $B$, and $C$ suppose

$$(A \cap B) \subseteq C$$

then prove:

$$(B-C) \cap(A-C)=Ø $$

### Proof by Contradiction

Suppose not:

$$(A \cap B) \subseteq C$$

and

$$(B-C) \cap(A-C)≠Ø $$

Because this statment is not equal to the zero set, this means that there exists some $x$, such that:

$$x \in (B-C)$$ and

$$x \in (A-C)$$

But if $(A \cap B) \subseteq C$ then this means that:

$$x \in (A-C)=Ø$$

$$x \in (B-C)=Ø$$

This is because, by the definition of a subset, whatever is in $A$, must also be in $C$. By the same logic, what is in $B$ must also be in $C$. But, by the definition of set difference, $(A-C)$ and $(B-C)$ will yield the elements of $A$ and $B$ that are not also a part of set $C$. Thus:
$$(B-C) \cap(A-C)=(Ø)\cap(Ø)=Ø $$

__This is a contradiction__

Therefore:

$$(B-C) \cap(A-C)=Ø $$

## Other Proofs About Sets

For all sets $A$ and $B$, prove that:

$$ A-(A-B) = A \cap B $$

By the *Set Difference* law:

$$A-(A-B) = A-(A \cap B^c)$$

By the *Set Difference* law:

$$ A-(A \cap B^c)=A \cap (A \cap B^c)^c $$

By *DeMorgan's Law*:

$$A \cap (A \cap B^c)^c = A \cap (A^c \cup B)$$

By *The Distributive* Law:

$$A \cap (A^c \cup B) = (A \cap A^c) \cup (A \cap B)$$

By the *Compliment Law*

$$(Ø) \cup (A \cap B) = (A \cap B)$$

## Disprove

For all sets $A$, $B$, and $C$:

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

### Counter example:

Let:
$$A = \{1, 2, 3, 4, 6, 7\}$$
$$B = \{1, 2, 4\}$$
$$C = \{1, 3, 5\}$$

Thus,

$$ A-(B \cap C) = \{2, 3, 4, 6, 7\} $$

by definition of intersection and difference.

And,

$$ (A-B) \cap (A-C) = \{6, 7\} $$

by definition of intersection and difference.

However,

$$ \{2, 3, 4, 6, 7\} ≠ \{6, 7\} $$

Therefore, the statement is __false__.