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 xAx\in A if xx is a member of a set AA and xAx\notin A if not.

Example 20.1.1

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

Definition 20.1.2

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

x(xAxB)\forall x\left(x\in A\implies x\in B\right) (20.1)
Definition 20.1.3

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

We can write this in logic symbols as

A=Bx(xAxB)A=B\iff\forall x\left(x\in A\iff x\in B\right) (20.2)
Theorem 20.1.1

Two sets AA and BB are equal if and only if ABA\subseteq B and BAB\subseteq A.

Example 20.1.2

Prove that

AC=BC and AC=BCA=B\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=BA=B. We can do this by showing that ABA\subseteq B and BAB\subseteq A.

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

xA\displaystyle x\in A xAxC\displaystyle\implies x\in A\lor x\in C (20.4)
xAC\displaystyle\implies x\in A\cup C (20.5)
xBCAs AC=BC (by assumption)\displaystyle\implies\underbrace{x\in B\cup C}_{\text{As $A\cup C=B\cup C$ (by% assumption)}} (20.6)
xBxC\displaystyle\implies x\in B\lor x\in C (20.7)
xB(xCxA)This follows as xA is true.\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)
xB(xCA)\displaystyle\implies x\in B\lor(x\in C\cap A) (20.9)
xB(xBC)\displaystyle\implies x\in B\lor(x\in B\cap C) (20.10)
xB(xBxC)\displaystyle\implies x\in B\lor(x\in B\lor x\in C) (20.11)
xB\displaystyle\implies x\in B (20.12)

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

20.1.1 Some example set theory proofs

Example 20.1.3

Prove that A(BC)=(AB)(AC)A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C).

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

xA(BC)\displaystyle x\in A\setminus(B\cap C) xA and x(BC)\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 ¬(xBC)\lnot(x\in B\cap C) (read: \sayx is not in BB and CC) is equivalent to xBx\notin B or xCx\notin C11 1 Don’t forget that \notin is the negation of \in. Therefore, our statement is true if and only if

xA and (xB or xC).\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

(xA and xB) or (xA and C).\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)

(xAB) or (xAC).\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

x(AB)(AC)\displaystyle x\in\left(A\setminus B\right)\cup\left(A\setminus C\right) (20.17)

which is what we wanted to prove.