ΘρϵηΠατπ

Set Difference

Set Difference
Suppose that A,B are sets, then A∖B:={a∈A:a∉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=∅, if and only if A⊆B
TODO
Difference of a Superset is Empty
Suppose that A,B⊆X are sets such that A⊆B, then (X∖B)∩A=∅
Let p∈(X∖B)∩A, therefore p∈X, p∉B and p∈A, this is impossible since if p∈A then p∈B as A⊆B, therefore no such p is an element of this set, so that (X∖B)∩A=∅
Empty Intersection implies Superset Difference
Suppose that A,B⊆X are sets, assuming A∩B=∅ , then X∖A⊇B
Taking an element p∈B we'd like to show that p∈X∖A, we can see p∈X because B⊆X, it's also clear that p∉A since if it were then A∩B≠∅ which would be a contradiction. Combining this, we have that p∈X∖A as needed.
Set Difference with Itself is Empty
X\X=∅
X\X={x∈X:x∉X}=∅
Set Difference with the Empty set is Itself
X\∅=X
TODO
Redundant Intersection in Difference
Suppose that A,B,X are sets then (A∩X)\B=(A∩X)\(B∩X)

Suppose that p∈(A∩X)\B therefore p∈A, p∈X but p∉B, we can see that p∈(A∩X) and since p∉B, then p∉(B∩X), therefore p∈(A∩X)\(B∩X)

Now suppose that p∈(A∩X)\(B∩X), so that p∈A∩X and p∉B∩X, from this we deduct that p∈X, so to avoid contradiction, we must have p∉B, since we also know p∈A, we can say that p∈(A∩X)∖B

Intersection Distributes through Set Difference
Suppose that A,B,X are sets then (A\B)∩X=(A∩X)\B

Suppose that p∈(A\B)∩X so p∈A, p∉B and p∈X, this means that p∈A∩X and p∉B, this shows that p∈(A∩X)\B as needed

Now suppose that p∈(A∩X)\B so p∈A, p∈X but p∉B, recombining this information we can see that p∈(A\B)∩X, as needed.

Set Difference Decomposition
Suppose that A and B are sets. Then A∖B and A∩B are disjoint, and A=(A∖B)∪(A∩B).
First, suppose that x∈(A∖B)∩(A∩B). Then x∈A∖B, so x∉B, and x∈A∩B, so x∈B. This is impossible, so A∖B and A∩B are disjoint.

To prove the equality, use set equality by subsets. If x∈A, then either x∈B or x∉B. If x∈B, then x∈A∩B. If x∉B, then x∈A∖B. In either case, x∈(A∖B)∪(A∩B).

Conversely, if x∈(A∖B)∪(A∩B), then x∈A∖B or x∈A∩B. Either condition implies x∈A, so (A∖B)∪(A∩B)⊆A. Therefore A=(A∖B)∪(A∩B).

Intersection with an Ambient Difference
Suppose that A,B⊆X. Then (X∖A)∩B=B∖A
We have x∈(X∖A)∩B if and only if x∈X, x∉A, and x∈B. Since B⊆X, this is equivalent to x∈B and x∉A, which is equivalent to x∈B∖A.
Intersection of Ambient Differences
Suppose that A,B⊆X. Then (X∖A)∩(X∖B)=(X∖A)∖B.
We have x∈(X∖A)∩(X∖B) if and only if x∈X, x∉A, and x∉B. This is equivalent to x∈X∖A and x∉B, which is equivalent to x∈(X∖A)∖B.
Union Intersection Inversion through set Difference
Suppose that A,B,C are sets then A\(B∩C)=A\B∪A\C

We know that x∈A\(B∩C) is true iff x∈A and x∉(B∩C), equivalent to x∉B or x∉C, since x∈A, we can biconditionally re-write this as x∈A\B or x∈A\C iff x∈(A\B)∪(A\C)

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

Double Difference creates Intersection
Suppose that A,B,C are sets such that A⊆B, then A\(B\C)=(A\B)∩C

Suppose that x∈A\(B\C) which is true iff x∈A and x∉(B\C) which means that it's not true that (x∈Bandx∉C) so that x∉B or x∈C, since x∈A and we know that A⊆B then x∈B, which forcs x∈C to avoid a contradiction, therefore

Suppose that x∈A\B∩C, therefore x∈A, x∉B and x∈C, thus we can see that x∉B\C thus x∈A\(B\C)

Triple Difference Equality
Suppose that A,B,C are sets such that A⊆B, then A\(B\C)=(A∩C)∪(A∖B)

x∈A\(B\C) iff x∈A and x∉(B\C) equivalent to the following statement not being true: (x∈B∧x∉C) which is x∉B or x∈C, therefore x∈A∩C or x∈A∖B so that x∈(A∩C)∪(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∩B

Suppose that x∈A\(A\B) which is true iff x∈A and x∉(A\B) which means that it's not true that x∈A∧x∉B we already know that x∈A holds, so we must have that x∉B to be false, which means that x∈B so that x∈A∩B

Suppose that x∈A∩B, since x∈B, then it's not true that x∉B, therefore x∉(A\B) since x∈A, this shows that x∈A\(A\B)

Double Set Difference Cancels for Subsets
Suppose that B⊆A then A∖(A∖B)=B
Recall that A∖(A∖B)=A∩B. Since B⊆A, intersection with a superset is itself, so A∩B=B.
TODO
Suppose that Y⊆X and Y\A=Y∩U, then A=Y∩(X\U) solves the given equation
Suppose that A=Y∩(X\U), then Y\A=Y\(Y∩(X\U))=(Y\Y)∪(Y\(X\U))=∅∪
DeMorgan's Laws
Suppose that M is a family of sets, then X\(⋃A∈MA)=⋂A∈M(X\A) and X\(⋂A∈MA)=⋃A∈M(X\A)

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