# 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

$$\forall x \left (x \in A \implies x \in B\right )$$

• 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

$$A = B \iff \forall x \left (x \in A \iff x \in B \right )$$

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