Set Theory
Chapter 2 Getting Started
2.1 Extensionality
\(Set\), \(elements\) or \(members\), \(empty\) set or “\(\emptyset\)”
Extensionality \[(A = B) \Leftrightarrow (\forall x \mid x \in A \leftrightarrow x \in B)\] Objects \[a_1, a_2, \dots , a_n\]
Set \[\{a_1, a_2, \ldots , a_n\}\]
Members or elements \[a_1, a_2, \dots, a_n\]
The order of members does not matter. \[\{a, b\} = \{a, a, b\} = \{a, b, b\}\]
The set of positive integers less than 4 is \(\{1,2,3\}\), but it can also be written as \(\{3,2,1\}\) or even as \(\{1,2,1,2,3\}\). These are all the same set, by extensionality.
2.2 Subsets and Power Sets
Approach: Everything in one set is in the other too.
Definition 2.5 (Subset). If every member of a set \(A\) is also a member of B, then we say that \(A\) is a subset of B, and write \(A \subseteq B\). If \(A\) is not a subset of B we write \(A \subsetneq B\). If \(A \subseteq B\) but \(A \neq B\), we write \(A \subsetneq B\) and say that \(A\) is a proper subset of \(B\).
Every set is a subset itself and \(\emptyset\) is a subset of every set. \[\forall A \quad A\subseteq A \ \text{and} \ \emptyset\subseteq A\] A set may happen to both be a member or a subset of some other set. \[\{0\} \in \{0, \{0\}\} \ \text{and} \ \{0\} \subseteq \{0, \{0\}\}\] Proposition 2.8. \((A = B) \iff (A \subseteq B) \ \cap (B\subseteq A)\)
Definition 2.9 \((\forall x \in A)\varphi\) abbreviates \(\forall x (x \in A \to 𝜑)\). Similarly, \((\exists x \in A)\varphi\) abbreviates \(\exists x(x \in A \wedge \varphi)\).
\(\Large \forall\)
\((\forall x \in A)\varphi\) means that “For every element \(x\) in the set \(A\), the property \(\varphi\) holds.
\(\forall x(x \in A \to \varphi)\) means that “For every \(x\) (in the entire universe of discourse), if \(x\) is an element of \(A\), then \(\varphi\) holds for \(x\).” If an element \(x\) is not in \(A\), the condition \(x \in A \to \varphi\) is automatically true (since the premise \(x \in A\) is false). That’s why ‘happen’ is born.
Example for \(\forall\)
Let \(A = \mathbb{N}\) (the set of natural numbers, \(\{1, 2, 3, \ldots\}\)). Let \(\varphi\) be the statement: \(x > 0\).
Restricted form: \((\forall x \in \mathbb{N})(x > 0)\)
In words: “Every natural number \(x\) is greater than 0.” (This is true.)
Abbreviated form: \(\forall x(x \in \mathbb{N} \to x > 0)\)
In words: “For every \(x\), if \(x\) is a natural number, then \(x\) is greater than 0.” (This is the logical equivalent, and it is also true.)
\(\Large \exists\)
\((\exists x \in A)\varphi\) meas that “There exists at least one element \(x\) in the set \(A\) for which the property \(\varphi\) holds.
\(\exists x(x \in A \wedge \varphi)\) means that “There exists at least one \(x\) (in the entire universe of discourse) such that \(x\) is an element of \(A\) and \(\varphi\) holds for \(x\).
“The use of the conjunction (\(\wedge\), meaning”and”) is crucial here. To assert the existence of an element in \(A\) with property \(\varphi\), you must state two things: that the element exists, AND that it satisfies both conditions: being in \(A\) and satisfying \(\varphi\).
Example for \(\exists\)
Let \(A = \{1, 3, 5, 7, 9\}\) (a set of odd numbers).Let \(\varphi\) be the statement: \(x < 4\).
Restricted form: \((\exists x \in A)(x < 4)\)
In words: “There exists an element \(x\) in \(A\) such that \(x\) is less than 4.” (This is true, as \(x=1\) or \(x=3\) satisfy it.)
Abbreviated form: \(\exists x(x \in A \wedge x < 4)\)
In words: “There exists an \(x\) such that \(x\) is in \(A\) AND \(x\) is less than 4.” (This is the logical equivalent, and it is also true.)
\(A \subseteq B \iff (\forall x \in A)x \in B.\)
The negation of \((\forall x \in A)\varphi\) is \((\exists x \in A)\neg\varphi\).
\((\forall x \in A)\varphi\) Every element in \(A\) has \(\varphi\).
\((\exists x \in A)\neg\varphi\) There exists at least one element in \(A\) that does not have \(\varphi\).
The equivalence \[(\forall x \in A)\varphi \quad \equiv \quad \neg (\exists x \in A)\neg\varphi\]
Definition 2.10 (Power Set). The set consisting of all subsets of a set \(A\) is called the power set of \(A\), written \(\mathcal{P}(A)\).
\[\mathcal{P}(A) = \{B \mid B\subseteq A\}\] Example 2.11 What are all possible subsets of \(\{a, b, c\}\)?
\(\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\)
How many? Combination \(\dfrac{3!}{1!(3-1)!}=3; \dfrac{3!}{2!(3-2)!}=3; \dfrac{3!}{3!(3-3)!}=1; \emptyset=1\). Total = \(8\)
\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\] \(\mathcal{P}(\{a, b, c\})=\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}\)