Sets
In mathematics, everything is a set. This page serves as an introduction to sets.
Definition 1. A set is a collection of elements, subject to the axioms that follow. Every element of a set is a set. We denote that a set \(x\) is an element of a set \(A\) by writing \(x\in A\). If a set \(x\) is not an element of a set \(A\), we write \(x\notin A\). If all elements of a set are known, it may be denoted as its elements separated by commas and surrounded by curly braces.
Axiom 1 (Extensionality). Sets \(A\) and \(B\) are equal, denoted \(A=B\), if they have the same elements. \[\forall A \ \forall B \quad (\forall x \ (x \in A \iff x \in B)) \implies A = B\]
Definition 2. Sets \(A\) and \(B\) are unequal if they are not equal, denoted \(A\neq B\). \[A\neq B \iff \lnot (A=B)\]
Example 1. If a set \(A\) satisfies \(x\in A\), \(y\in A\), and for all sets \(z\) one has \(z=x\) or \(z=y\) or \(z\notin A\), then \(A\) may be denoted as \(\{x,y\}\). Moreover, the axiom of extensionality yields \[A = \{x,y\}\]
Definition 3. A set \(B\) is a subset of a set \(A\) if every element of \(B\) is an element of \(A\). This is denoted as \(B \subseteq A\). \[B \subseteq A \iff \forall x \ (x \in B \implies x \in A)\] If \(B \subseteq A\), then \(A\) contains \(B\). This is denoted as \(A \supseteq B\). \[A \supseteq B \iff B \subseteq A\] A set \(B\) is a proper subset of a set \(A\) if \(A\subseteq B\) and \(B\neq A\). This is denoted as \(B \subset A\). \[B \subset A \iff (B\subseteq A) \land (B\neq A)\] If \(B \subset A\), then \(A\) properly contains \(B\). This is denoted as \(A \supset B\). \[A \supset B \iff B \subset A\]
Theorem 1. If \(A\) and \(B\) are sets, then \(A\subseteq B\) and \(B\subseteq A\) if and only if \(A=B\). \[(A\subseteq B) \land (B\subseteq A) \iff A=B\]
Proof. Let \(A\) and \(B\) be sets.
One has \(A\subseteq B\) if and only if \[\forall x \ (x \in A \implies x \in B).\] One has \(B\subseteq A\) if and only if \[\forall x \ (x \in B \implies x \in A).\] Then \(A\subseteq B\) and \(B\subseteq A\) if and only if \[\forall x \ (x \in A \iff x \in B).\] By the axiom of extensionality, one has \(A=B\) if and only if \[\forall x \ (x \in A \iff x \in B).\] Therefore \[(A\subseteq B) \land (B\subseteq A) \iff A=B.\] ◻
Definition 4. A set \(A\) is empty if there are no elements in \(A\), denoted \(A=\emptyset\). \[A=\emptyset \iff \lnot \exists x \ (x\in A)\] A set \(A\) is nonempty if it is not empty, denoted \(A\neq\emptyset\). \[A\neq\emptyset \iff \exists x \ (x\in A)\]
Axiom 2 (Regularity). Every nonempty set \(A\) contains an element \(x\) such that \(A\) and \(x\) are disjoint sets. \[\forall A \ ((\exists a \ (a \in A)) \implies \exists x \ (x \in A \land \lnot \exists z \ (z \in A \land z \in x)))\] Equivalently, \[\forall A \ (A \neq \emptyset \implies \exists x \ ((x \in A) \land (A \cap x = \emptyset)))\]
Axiom 3 (Specification). Given a set \(A\) and a statement \(P\), there is a set \(B\) containing elements of \(A\) satisfying \(P\). That is \[\forall A \ \exists B \ \forall x \quad x \in B \iff ((x \in A) \land P)\]
Definition 5. Set builder notation is a way of writing the set \(B\) in the axiom of specification, namely \[B = \{ x\in A : P\}\]
Definition 6. If \(A\) and \(B\) are sets, the set \(A\) whithout \(B\) is the set existing by the axiom of specification \[A\setminus B = \{x\in A : x\notin B\}\]
Example 2. If \(\{x,y\}\) and \(\{x\}\) are sets, then the set \(\{x,y\}\setminus\{x\}=\{y\}\) exists.
Axiom 4 (Pairing). If \(x\) and \(y\) are sets, there exists a set containing \(x\) and \(y\) as elements. \[\forall x \ \forall y \ \exists A \quad (x \in A) \land (y \in A)\]
Example 3. If \(x\) and \(y\) are sets, then the set \(\{x,y\}\) exists.
Proof. Let \(x\) and \(y\) be sets. By the axiom of pairing, there is a set \(A\) with \(x\in A\) and \(y\in A\). By the axiom of specification, the set \[B = \{ a\in A : (a = x) \lor (a = y) \}\] exists. If \(b\in B\), then \(b=x\) or \(b=y\) so that \(b\in\{x,y\}\) and \(B\subseteq\{x,y\}\). Since \(x\in A\) and \(x=x\), we have \(x\in B\). Since \(y\in A\) and \(y=y\), we have \(y\in B\). Then \(\{x,y\}\subseteq B\). It follows that \(B = \{x,y\}\). Since \(B\) exists, so does \(\{x,y\}\). ◻
Example 4. If \(x\) is a set, then the set \(\{x\}\) exists.
Proof. Let \(x\) be a set. Let \(y=x\). Then the set \(\{x,y\}\) exists. One can check that \(\{x,y\}=\{x\}\). ◻
Axiom 5 (Union). For any set \(\mathcal{A}\), there is a set containing every element that is an element of some element of \(\mathcal{A}\). \[\forall \mathcal{A} \ \exists B \ \forall A \ \forall x \ (((A \in \mathcal{A}) \land (x \in A)) \implies x \in B)\]
Definition 7. For any set \(\mathcal{A}\), the union of the elements in \(\mathcal{A}\) is the set existing by the axiom of specification \[\cup \mathcal{A} = \{x \in B : \exists A \ ((A \in \mathcal{A}) \land (x \in A))\}\] where \(B\) is a set existing by the axiom of union. We often denote \(\cup\mathcal{A}\) by \[\bigcup_{A\in\mathcal{A}} A\] If all elements of \(\mathcal{A}\) are known, we may denote \(\cup\mathcal{A}\) as the elements of \(\mathcal{A}\) separated by the symbol \(\cup\).
Example 5. If \(\{x\}\) and \(\{y\}\) are sets, then \(\{x\}\cup \{y\} = \{x,y\}\).
Proof. Let \(\{x\}\) and \(\{y\}\) be sets. Let \(\mathcal{A} = \{\{x\},\{y\}\}\). One can check that \(\cup\mathcal{A} = \{x,y\}\). ◻
Definition 8. For any set \(\mathcal{A}\), the intersection of the element in \(\mathcal{A}\) is the set existing by the axiom of specification \[\cap\mathcal{A} = \{ x\in\cup\mathcal{A} : \forall A \ (A\in\mathcal{A} \implies x\in A)\}\] We often denote \(\cap\mathcal{A}\) by \[\bigcap_{A\in\mathcal{A}} A\] If all elements of \(\mathcal{A}\) are known, we may denote \(\cap\mathcal{A}\) as the elements of \(\mathcal{A}\) separated by the symbol \(\cap\).
Example 6. If \(\{x,y\}\) and \(\{x\}\) are sets, then \(\{x,y\}\cap\{x\} = \{x\}\).
Theorem 2 (Laws of De Morgan). Let \(X\) and \(\mathcal{A}\) be sets such that \(\cup\mathcal{A}\subseteq X\). Then \[X \setminus \cup \mathcal{A} = \bigcap_{A\in\mathcal{A}} (X\setminus A)\] and \[X \setminus \cap \mathcal{A} = \bigcup_{A\in\mathcal{A}} (X\setminus A)\]
Proof. Let \(x\in X\setminus\cup\mathcal{A}\). Then \(x\in X\) and \(x\notin\cup\mathcal{A}\). Then for each \(A\in\mathcal{A}\), one has \(x\notin A\) and so \(x\in X\setminus A\). Then \(x\in \bigcap_{A\in\mathcal{A}} (X\setminus A)\). Hence \[X \setminus \cup \mathcal{A} \subseteq \bigcap_{A\in\mathcal{A}} (X\setminus A).\] Let \(x\in\bigcap_{A\in\mathcal{A}} (X\setminus A)\). Then for each \(A\in\mathcal{A}\), one has \(x\in X\setminus A\) and so \(x\in X\) and \(x\notin A\). Then \(x\notin\cup\mathcal{A}\) and \(x\in X\setminus\mathcal{A}\). Hence \[\bigcap_{A\in\mathcal{A}} (X\setminus A) \subseteq X\setminus\cup\mathcal{A}.\] It follows that \[X \setminus \cup \mathcal{A} = \bigcap_{A\in\mathcal{A}} (X\setminus A).\] Let \(x\in X\setminus\cap\mathcal{A}\). Then \(x\in X\) and \(x\notin\cap\mathcal{A}\). Then there is \(A\in\mathcal{A}\) such that \(x\notin A\). Then \(x\in X\setminus A\) and so \(x\in\bigcup_{A\in\mathcal{A}} (X\setminus A)\). Hence \[X \setminus \cap \mathcal{A} \subseteq \bigcup_{A\in\mathcal{A}} (X\setminus A).\] Let \(x\in \bigcup_{A\in\mathcal{A}} (X\setminus A)\). Then there is \(A\in\mathcal{A}\) such that \(x\in X\setminus A\). Then \(x\in X\) and \(x\notin A\). Then \(x\notin\cap\mathcal{A}\) and so \(x\in X\setminus\cap\mathcal{A}\). Hence \[\bigcup_{A\in\mathcal{A}} (X\setminus A) \subseteq X \setminus \cap \mathcal{A}.\] It follows that \[X \setminus \cap \mathcal{A} = \bigcup_{A\in\mathcal{A}} (X\setminus A).\] ◻
Axiom 6 (Replacement). Given a set \(A\) and a statement \(P\), if for each \(x\in A\) there is a unique set \(y\) satisfying \(P\), then there is a set containing all of the \(y\)s associated with all of the \(x\)s in \(A\). \[\forall A \ ((\forall x \ (x \in A \implies \exists!y \ P)) \implies \exists B \ \forall x \ (x \in A \implies \exists y \ ((y \in B) \land P)))\]
Definition 9. If \(x\) is a set, the successor of \(x\) is the set \(x \cup \{x\}\). We denote this set as \(s(x)\).
Axiom 7 (Infinity). There exists a set \(X\) containing an empty set such that if \(x\in X\), then \(s(x)\in X\). \[\exists X \ (\exists e \ (\forall z \ \lnot (z \in e) \land e \in X) \land \forall y \ (y \in X \implies s(y) \in X))\] Equivalently, \[\exists X \ ((\exists e \ (e\in X \land e=\emptyset)) \land \forall y \ (y \in X \implies s(y) \in X))\]
Theorem 3. There exists an empty set and it is unique. It is denoted by \(\emptyset\).
Proof. (Existence) By the axiom of infinity, there exists a set \(X\). By the axiom of specification, the set \[Z = \{x\in X : x\notin X\}\] exists. Since for any set \(x\), either \(x\in X\) or \(x\notin X\), it follows that \(Z\) is empty. Hence an empty set exists.
(Uniqueness) Suppose \(A\) and \(B\) are empty sets. Then for any set \(x\), one has \(x\notin A\) and \(x\notin B\). Then \[\forall x \quad x\in A \iff x\in B.\] It follows that \(A=B\). ◻
Axiom 8 (Power set). For any set \(A\), there is a set \(S\) that contains every subset of \(A\). \[\forall A \ \exists S \ \forall B \ (B \subseteq A \implies B \in S)\]
Definition 10. For any set \(A\), the power set of \(A\) is the set existing by the axiom of specification \[\mathcal{P}(A) = \{B \in S : B \subseteq A \}\] where \(S\) is a set existing by the axiom of power set.
Definition 11. If \(x\) and \(y\) are sets, the ordered pair of \(x\) and \(y\) is the set \(\{x,\{y\}\}\). We denote this set as \((x,y)\).
Definition 12. For any sets \(A\) and \(B\), the cartesian product of \(A\) and \(B\) is the set of ordered pairs \[A\times B = \{x\in \mathcal{P}(A\cup\mathcal{P}(B)) : \exists a \ \exists b \ (a\in A \land b\in B \land x=(a,b))\}\] existing by the axioms of specification, union, and power set.
Source File: jakemath.com/latex/sets/sets.tex