A calculus of the absurd

6.2 Basic set theory notions

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

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

Definition 6.2.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 6.2.1 Two sets $A$ and $B$ are equal if and only if $A \subseteq B$ and $B \subseteq A$.

Example 6.2.2 Prove that
$\seteqnumber{0}{6.}{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).