> [!NOTE] Definition (ZFC in $L_{2}$) > ZFC is an axiom system for [[Sets|sets]] formulated in [[L2 (FOL)|L2]] with equality and with only one binary relation symbol $\in$ for membership (we write $a\in b$ to express that $a$ is a member of the set $b$). > > Below are the axioms of ZFC: > 1. [[Zermelo Frankel set theory (ZFC)|Extension]]: Two sets are equal iff they have the same elements. > 2. [[Zermelo Frankel set theory (ZFC)|Specification (or Separation or Restricted comprehension)]]: For every set $A$ and every given property, there is a set containing exactly the elements of $A$ that have that property. A *property* is given by a predicate $\varphi$ of the first-order language of set theory. Thus, Separation is not a single axiom but an axiom schema, that is, an infinite list of axioms, one for each predicate $\varphi.$ > 3. [[Zermelo Frankel set theory (ZFC)|Pair]]: For any two objects there is a set that has both as elements (and no others). *NB*: It is a requirement of $L_{2}$ that the domain of discourse is non-empty, and so the Unordered Pair Axiom implies the existence of a set that contains this object, whatever it is. From this set, we can use the Axiom of Specification to derive the existence of the empty set as the subset of this set whose elements satisfy $x \neq x$ which may replace the [[Zermelo Frankel set theory (ZFC)]]. > 4. union: Given any a set of sets, the union of all the members is also a set > 5. [[Zermelo Frankel set theory (ZFC)]]: For every set $A$ there exists a set, denoted by $\mathcal{P}(A)$ and called the _power set_ of $A$, whose elements are all the [[Subsets|subsets]] of $A.$ > 6. [[Zermelo Frankel set theory (ZFC)|Infinity]]: The set $\mathbb{N}$ exists. > 7. [[Zermelo Frankel set theory (ZFC)|Replacement]]: This axiom tells us that if we have a set and a formula which relates each element of the set to a unique object, then the collection of those objects is also a set. Again this axiom is actually a schema since it holds for any formula with the required uniqueness property. > 8. [[Zermelo Frankel set theory (ZFC)|Choice]]: For every set $A$ of pairwise-disjoint non-empty sets, there exists a set that contains exactly one element from each set in $A.$ > 9. [[Zermelo Frankel set theory (ZFC)|Regularity (or Foundation)]]: No nonempty set has a nonempty intersection with each of its own elements. Specifically, this axiom rules out the possibility of “irregular” sets, such as a set which contains itself as its only member. > > [!NOTE] Axiom (Power Set) > Every [[Zermelo Frankel set theory (ZFC)|set]] has a powerset. $\forall a \exists b \forall x (x\in b \leftrightarrow x\subseteq a)$ # Properties Note that [[Cantor's Theorem|Cantor's theorem]] guarantees that the cardinality of the power set is strictly greater than the set. > [!NOTE] Axiom (Extension) > $\forall a \forall b (\forall x (x\in a \leftrightarrow x\in b ) \rightarrow a=b)$ > Hence two [[Zermelo Frankel set theory (ZFC)|sets]] are equal iff they have the same elements. > [!NOTE] **Axiom (Specification or Separation or Restricted Comprehension)** > $\forall z_1\ldots\forall z_n\forall a\exists b\forall x[x\in b\leftrightarrow(x\in a\land P(x))]$ > For every [[Zermelo Frankel set theory (ZFC)|set]] $A$ and every given property, there is a set containing exactly the elements of $A$ that have that property. > >Note that the Axiom of Separation is a weakened version of the [[Axiom of Unrestricted Comprehension]] that led to contradiction ([[Russell's Paradox]]) in naive set theory. # Applications The [[Union of sets|difference]] of $X$ and $Y$ denoted $X-Y,$ is the defined as the subset of $X$ defined by $\{ x\in X \mid x \not \in Y \}.$ > [!NOTE] Axiom (Unordered Pair) > For any two objects there is a [[Zermelo Frankel set theory (ZFC)|set]] that has both as elements (and no others). $\forall x \forall y \exists a \forall z (z\in a \leftrightarrow (z=x \lor z = y) )$ > It is a requirement of [[L2 (FOL)|L2]] that the domain of discourse is non-empty, and so the Unordered Pair Axiom implies the existence of a set that contains this object, whatever it is. From this set, we can use the Axiom of Separation to derive the existence of the empty set as the subset of this set whose elements satisfy $x \neq x.$ # Application The [[Ordered pair|ordered pair]] $(x,y)$ is defined as the set $\{ \{ x \}, \{ x,y \} \}.$ > [!NOTE] Definition (Axiom of Infinity) > There is a [[Sets|set]] containing the empty set and which contains $\{ a \}$ for every $a$ that it contains. $\exists a (\emptyset \in a \land x (x\in a \rightarrow \{ x \} \in a))$ > This axiom asserts the existence of a set containing all the [[Natural Numbers|natural numbers]]. We can think of the set $\emptyset$ as representing the number $0,$ and $\{ \emptyset \}$ as representing $1,$ $\{ \{ \emptyset \} \}$ as $2$ and so on. > [!NOTE] Axiom (Replacement) > Suppose $P(x,y)$ is a formula which holds of exactly one $y$ for each $x\in a$: $\forall x (x\in a \rightarrow \exists! P(x,y))$Then, there is a set $\{ y | \exists x (x \in a\land P(x,y)) \}$ >Equivalently, if we have a decidable [[Function|function]] whose domain is $A$ then there is a set whose elements are all the values of the function. > [!NOTE] Definition (Axiom of Choice) > Suppose $a$ is a [[Zermelo Frankel set theory (ZFC)|set]] whose whose members are all non-empty sets. Then there is a [[Function|function]] $f:a\to \cup_{e\in a} e$ that satisfies the following $\forall x (x\in a \to f(x) \in x)$ # Properties The idea here is that the function $f$ looks at each set in $a$ and chooses exactly one member of that set. Each choice function on a collection _X_ of nonempty sets is an element of the [[Cartesian Product|Cartesian product]] of the sets in $a.$ This axiom is therefore equivalent to: Given any family of nonempty sets, their Cartesian product is a nonempty set. This axiom is more controversial than the others. It gives no new results when applied to finite sets, but for infinite sets, it results in certain surprising results such as the [[Banach-Tarski Paradox]]. As a result, many mathematicians investigate what parts of mathematics can be obtained without the axiom of choice, which results of mathematics require the axiom of choices, and plausible negations of the axiom of choice \[[1](https://artofproblemsolving.com/wiki/index.php/Zermelo-Fraenkel_Axioms)]. # Applications Consequences: [[Surjection|Surjective iff right-invertible]]; [[Cartesian Product]]; [[Zorn's Lemma]]. > [!NOTE] Axiom (Regularity or Foundation) > No nonempty set has a nonempty intersection with each of its own its elements. That is $\forall b [b \neq \emptyset \rightarrow \exists y(y\in b \land y \cap b = \emptyset)]$ >Specifically, this axiom rules out the possibility of “irregular” sets, such as a set which contains itself as its only member. We might write this set as $S = \{ S \}$, or as $\{ \{ \{ \dots \} \} \}.$ **Axiom** There is an *empty [[Sets|set]]* denoted $\emptyset$.