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

    \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

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