# 20.1 Basic set theory notions

###### Definition 20.1.1

The core definition in set theory is as to whether or not something is a member of a set or not. We write $x\in A$ if $x$ is a member of a set $A$ and $x\notin A$ if not.

###### Example 20.1.1

If we consider $S=\{0,1,2,3\}$ then $0\in S$ but $4\notin S$.

###### Definition 20.1.2

We say that $A$ is a subset of $B$ (written $A\subseteq B$) if and only if every member of $A$ is also a member of $B$. In logic-y notation, this is

###### Definition 20.1.3

We say that two sets $A$ and $B$ are equal (written $A=B$) if and only they contain the same elements.

We can write this in logic symbols as

###### Theorem 20.1.1

Two sets $A$ and $B$ are equal if and only if $A\subseteq B$ and $B\subseteq A$.

###### Example 20.1.2

Prove that

$\displaystyle A\cup C=B\cup C\text{ and }A\cap C=B\cap C\implies A=B$ | (20.3) |

Note: this requires a bit of knowledge of some of the basics of logic.

We start by applying a standard technique; to prove an implication we assume that the antecedent (aka \sayleft-hand side) is true, and prove that therefore the right-hand side must also be true.

Therefore, we assume that the left-hand side is true, and will try to show that therefore $A=B$. We can do this by showing that $A\subseteq B$ and $B\subseteq A$.

To show that $A\subseteq B$, let $x\in A$ be arbitrary. In this case we can show this

$\displaystyle x\in A$ | $\displaystyle\implies x\in A\lor x\in C$ | (20.4) | ||

$\displaystyle\implies x\in A\cup C$ | (20.5) | |||

$\displaystyle\implies\underbrace{x\in B\cup C}_{\text{As $A\cup C=B\cup C$ (by% assumption)}}$ | (20.6) | |||

$\displaystyle\implies x\in B\lor x\in C$ | (20.7) | |||

$\displaystyle\implies x\in B\lor\underbrace{(x\in C\land x\in A)}_{\text{This % follows as $x\in A$ is true.}}$ | (20.8) | |||

$\displaystyle\implies x\in B\lor(x\in C\cap A)$ | (20.9) | |||

$\displaystyle\implies x\in B\lor(x\in B\cap C)$ | (20.10) | |||

$\displaystyle\implies x\in B\lor(x\in B\lor x\in C)$ | (20.11) | |||

$\displaystyle\implies x\in B$ | (20.12) |

Note that the other direction follows by symmetry; if we swap $A$ and $B$ in the above proof, then the statement is still true and thus $A=B$ (under the assumptions set out).

## 20.1.1 Some example set theory proofs

###### Example 20.1.3

Prove that $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$.

To prove this statement we must show that $x\in LHS\leftrightarrow x\in RHS$, that is, for every value of $x$, this value of $x$ is in the left-hand side set if and only if (read: exactly when) it is in the right-hand side set.

$\displaystyle x\in A\setminus(B\cap C)$ | $\displaystyle\iff x\in A\text{ and }x\notin(B\cap C)$ | (20.13) |

We can then apply De Morgan’s laws here, which tell us that
$\lnot(x\in B\cap C)$ (read: \sayx is not in $B$ and $C$) is equivalent to
$x\notin B$ or $x\notin C$^{1}^{1}
1
Don’t forget that $\notin$ is the
negation of $\in$. Therefore, our statement is true if and only if

$\displaystyle x\in A\text{ and }\left(x\notin B\text{ or }x\notin C\right).$ | (20.14) |

Now, it is important not to forget that logical and distributes over logical or, i.e. this is equivalent to

$\displaystyle\left(x\in A\text{ and }x\notin B\right)\text{ or }\left(x\in A% \text{ and }\notin C\right).$ | (20.15) |

Then we know that this is equivalent to (by applying the definitions)

$\displaystyle\left(x\in A\setminus B\right)\text{ or }\left(x\in A\setminus C% \right).$ | (20.16) |

Then, after applying the definition of set union, we know that the previous is true if and only if

$\displaystyle x\in\left(A\setminus B\right)\cup\left(A\setminus C\right)$ | (20.17) |

which is what we wanted to prove.