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$ ¹¹ 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.