# 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

$\forall x\left(x\in A\implies x\in B\right)$ (20.1)
###### 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

$A=B\iff\forall x\left(x\in A\iff x\in B\right)$ (20.2)
###### 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$11 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.