A calculus of the absurd

Part II Undergraduate mathematics

Chapter 17 Set theory

Sometimes it is helpful to talk about collections of things. Some things have common attributes, which means that any reasoning we apply to one object with this attribute can be applied to any other object with these attributes. Sets are about abstraction - we can focus less on the individual particularities of different objects, and instead focus more on their commonalities.

17.1 Basic set theory notions

Definition 17.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 17.1.1 If we consider $S = \{0, 1, 2, 3\}$ then $0 \in S$ but $4 \notin S$.

Definition 17.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
$\seteqnumber{0}{17.}{0}$
\begin{equation} \forall x \left (x \in A \implies x \in B\right ) \end{equation}

Definition 17.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

\begin{equation} A = B \iff \forall x \left (x \in A \iff x \in B \right ) \end{equation}

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

Example 17.1.2 Prove that
$\seteqnumber{0}{17.}{2}$
\begin{align} A \cup C = B \cup C \text { and } A \cap C = B \cap C \implies A = B \end{align}

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 “left-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

\begin{align} x \in A & \implies x \in A \lor x \in C \\ & \implies x \in A \cup C \\ & \implies \underbrace {x \in B \cup C} _{\text {As $A \cup C = B \cup C$ (by assumption)}} \\ & \implies x \in B \lor x \in C \\ & \implies x \in B \lor \underbrace {(x \in C \land x \in A)} _{\text {This follows as $x \in A$ is true.}} \\ & \implies x \in B \lor (x \in C \cap A) \\ & \implies x \in B \lor (x \in B \cap C) \\ & \implies x \in B \lor (x \in B \lor x \in C) \\ & \implies x \in B \end{align}

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).

17.1.1 Some example set theory proofs

Example 17.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.

\begin{align} x \in A \setminus (B \cap C) &\iff x \in A \text { and } x \notin (B \cap C) \end{align}

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

\begin{align} x \in A \text { and } \left ( x \notin B \text { or } x \notin C \right ). \end{align}

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

\begin{align} \left ( x \in A \text { and } x \notin B \right ) \text { or } \left ( x\in A \text { and } \notin C \right ). \end{align}

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

\begin{align} \left ( x \in A \setminus B \right ) \text { or } \left ( x\in A \setminus C \right ). \end{align}

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

\begin{align} x \in \left ( A \setminus B \right ) \cup \left ( A \setminus C \right ) \end{align}

which is what we wanted to prove.