Set Difference

Suppose that

A, B

are sets, then

A ∖ 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 \ 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

(X ∖ B) \cap A = \emptyset

Let

p \in (X ∖ B) \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

A \subseteq B

, therefore no such

p

is an element of this set, so that

(X ∖ B) \cap A = \emptyset

Empty Intersection implies Superset Difference

Suppose that

A, B \subseteq X

are sets, assuming

A \cap B = \emptyset

, then

X ∖ A \supseteq B

Taking an element

p \in B

we'd like to show that

p \in X ∖ 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 ∖ A

as needed.

Set Difference with Itself is Empty

X \ X = \emptyset

X \ X = {x \in X : x \notin X} = \emptyset

Set Difference with the Empty set is Itself

X \ \emptyset = X

TODO

Redundant Intersection in Difference

Suppose that

A, B, X

are sets then

(A \cap X) \ B = (A \cap X) \ (B \cap X)

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

Now suppose that $p \in (A \cap X) \ (B \cap X)$ , 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 (A \cap X) ∖ B$

Intersection Distributes through Set Difference

Suppose that

A, B, X

are sets then

(A \ B) \cap X = (A \cap X) \ B

Suppose that $p \in (A \ B) \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 (A \cap X) \ B$ as needed

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

Union Intersection Inversion through set Difference

Suppose that

A, B, C

are sets then

A \ (B \cap C) = A \ B \cup A \ C

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

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

Double Difference creates Intersection

Suppose that

A, B, C

are sets such that

A \subseteq B

, then

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

Suppose that $x \in A \ (B \ C)$ which is true iff $x \in A$ and $x \notin (B \ C)$ which means that it's not true that $(x \in B and x \notin C)$ 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 \ B \cap C$ , therefore $x \in A$ , $x \notin B$ and $x \in C$ , thus we can see that $x \notin B \ C$ thus $x \in A \ (B \ C)$

Triple Difference Equality

Suppose that

A, B, C

are sets such that

A \subseteq B

, then

A \ (B \ C) = (A \cap C) \cup (A ∖ B)

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

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

Double Set Difference Yields Intersection

Suppose that

A, B

are sets, then

A \ (A \ B) = A \cap B

Suppose that $x \in A \ (A \ B)$ which is true iff $x \in A$ and $x \notin (A \ B)$ which means that it's not true that $x \in A \land x \notin B$ 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 (A \ B)$ since $x \in A$ , this shows that $x \in A \ (A \ B)$

Double Set Difference Cancels for Subsets

Suppose that

B \subseteq A

then

A ∖ (A ∖ B) = B

Recall that

A ∖ (A ∖ B) = A \cap B

and since

B \subseteq A

we know it's equal to

B

TODO

Suppose that

Y \subseteq X

and

Y \ A = Y \cap U

, then

A = Y \cap (X \ U)

solves the given equation

Suppose that

A = Y \cap (X \ U)

, then

Y \ A = Y \ (Y \cap (X \ U)) = (Y \ Y) \cup (Y \ (X \ U)) = \emptyset \cup

DeMorgan's Laws

Suppose that

M

is a family of sets, then

X \ (⋃_{A \in M} A) = ⋂_{A \in M} (X \ A)

and

X \ (⋂_{A \in M} A) = ⋃_{A \in M} (X \ A)

Note that, $p \in X \ (⋃_{A \in M} A)$ , if and only if $p \in X$ and $x \notin ⋃_{A \in M} A$ , which is equivalent to: for all $A \in M$ $p \notin A$ , which is the same as $p \in (X \ A)$ for each $A \in M$ , so by definition $p \in ⋂_{A \in M} (X \ A)$ . 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 \ (⋂_{A \in M} A)$ , if and only if $p \in X$ and $x \notin ⋂_{A \in M} A$ , which is equivalent to: there is some $A \in M$ $p \notin A$ , which is the same as $p \in (X \ A)$ for some $A \in M$ , so by definition $p \in ⋃_{A \in M} (X \ A)$ . Since each connective in the previous paragraph was an iff, then this implies the two sets are equal