The Axioms of $ZFC$

From Cantor's Attic
Revision as of 16:41, 29 December 2013 by Q (Talk | contribs) (Axiom of Extensionality)

Jump to: navigation, search

Zermelo-Frankel Set Theory with Axiom of Choice is a (the?) standard collection of axioms used by set theorists. The formal language used to express each axiom is first-order with equality ($=$) together with one binary relation symbol, $\in$, intended to denote set membership. The axiom of the null set and the schema of separation are superseded by later, more inclusive axioms.

Axiom of Extensionality

Sets are determined uniquely by their elements. This is expressed formally as $$ \forall x \forall y \big(\forall z (z\in x\leftrightarrow z\in y)\rightarrow x=y\big).$$

The ``$\rightarrow$" can be replaced by $``\leftrightarrow"$, but the $\leftarrow$ direction is a theorem of logic. Optionally, the axiom of extensionality can serve as a definition of equality, and a different axiom can be used in its place: $$\forall x \forall y \big(\forall a (a \in x \leftrightarrow a \in y) \rightarrow \forall b (x \in b \leftrightarrow y \in b)\big)$$

meaning that sets with the same elements belong to the same sets.

Axiom of Null Set

There exists some set. In fact, there is a set which contains no members. This is expressed formally $$ \exists x \forall y (y\not\in x).$$

Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.

Axiom of Pairing

For any two sets $x$ and $y$ (not necessarily distinct) there is a further set $z$ which has as members the sets $x$ and $y$ and no others. $$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$

Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.

Axiom of Unions

For any set $x$ there is a further set $y$ which has a members all the members of members of $x$ and no others. This is expressed formally as $$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$

Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.

Axiom of Foundation (Regularity)

Every nonempty set has an $\in$-minimal element. This is expressed formally as $$\forall x\neq\emptyset \exists y\in x\neg\exists z (z\in x\wedge z\in y).$$

Equivalently, by the Axiom of Choice there's no infinite descending sequence $\dots \in x_2\in x_1\in x_0$.

Axiom Schema of Separation

For any set $a$ and any property $\dots x\dots$, the set $\{x\in a: \dots x\dots \}$ exists. In more detail, given any formula $\varphi$ with free variables $x_1,x_2,\dots,x_n$ the following is an axiom: $$ \forall a \forall x_1 \forall x_2\dots \forall x_n \exists y \forall z \big(z\in y \leftrightarrow (z\in a \wedge \varphi(x_1,x_2,\dots,x_n,z)\big) $$

Such a $y$, unique by extensionality and is written (for fixed sets $a, x_1\dots, x_n$) $y=\{z\in a: \varphi(x_1,x_2,\dots,x_n,z)\}$.

So far we cannot prove that infinite sets exists. Namely $\langle V_\omega, \in\rangle$ is a model of the first five axioms and the infinitely many instances of separation. Each member of $V_\omega$ is finite, in fact $V_\omega$ is the collection of hereditarily finite sets. This is essentially the standard model of $\mathbb{N}$.

Axiom of Infinity

There is an infinite set. This is expressed formally as $$ \exists x \big(\emptyset\in x\wedge \forall z (z\in x \rightarrow z\cup\{z\}\in x\big).$$

At this point we can define $\omega, +,$ and $\cdot$ on $\omega$, derive the basic facts for $\omega$ and the principle of mathematical induction on $\omega$ (i.e., we can prove that the Peano Axioms are true in $\langle \omega, +, \cdot\rangle$). But we can't yet prove the existence of an uncountable set.

Axiom of Power Set

For any set $x$ there is a further set $y$ that has as members all subsets of $x$ and no other elements. This is expressed formally as $$ \forall x \exists y \forall z \big(z\in y \leftrightarrow \forall w(w\in z \rightarrow w\in x)\big)$$ [The unique such $y$ is written as $y = \mathcal{P}(x)$.]

Define the ordered pair $(a,b)$ to be $\{\{a\},\{a,b\}\}$. A relation as a collection of ordered pairs, and a function as a relation $f$ such that $(a,b)\in f$ and $(a,c)\in f$ implies $b=c$.

Axiom of Choice

There are many formulations of this axiom. It is historically the most controversial of the axioms of $ZFC$.

$$\forall x \big[\forall y (y\in x \rightarrow y\neq\emptyset)\rightarrow \exists f \big(\operatorname{dom} f = x\wedge \forall a\in x (f(a) \in a )\big)\big] $$

The theory generated by the axioms above was explicitly spelled out by Zermelo (1908). Most of classical math can be carried out in this theory, but, surprisingly, no ordinals greater than $( \omega \cdot 2 )$ can be proven to exist within this theory (at least to Zermelo, who simply overlooked the next axiom discovered by Fraenkel and others).

Axiom Schema of Replacement

If $a$ is a set and for all $x\in a$ there's a unique $y$ such that $(x,y)$ satisfies a given property, then the collection of such $y$s is a set. In more detail, given a formula $\varphi(x_1,\dots,x_n,x,y)$ the following is an instance of the replacement schema: $$ \forall a \forall x_1 \dots \forall x_n \big[\big( \forall x\in a \exists ! y\in a \varphi(x_1,\dots,x_n,x,y)\big)\rightarrow \exists z \forall w (w\in z \leftrightarrow \exists u\in a \varphi(x_1,\dots,x_n,u,w))\big].$$

Applications of Replacement

The axiom of replacement proves that every well-ordered set is isomorphic to a (unique) ordinal.

proof. It suffices to show that for every w.o. $\langle L, <_L\rangle$ and every $l\in L$, $L_{< l} =\{m\in L: m <_L l\} \cong $ to a (unique) ordinal $f(l)$. Fix $l\in L$, $l$ the least counterexample. Then $f$ is defined on $L_{<l}$ and by replacement, $ran(f\restriction L_{<l})$ is a set of ordinals $A$. By basic facts about ordinals and order, it's easy to see that $A$ is an ordinal $\alpha$. If $l$ is a successor in $L$ then $L_{<l}\cong \alpha + 1$. If $l$ is a limit in $L$, then $L_{<l}\cong \alpha$. $\Box$

$\forall x\exists \alpha (x\in V_\alpha)$.

For all ordinals $\alpha$, $\aleph_\alpha$ exists (i.e. for every $\alpha$ there are at least $\alpha + 1$-many infinite cardinals).

Furthermore, the axiom of replacement also proves the axiom of separation, and in turn, the axiom of the null set. Furthermore, along with the power set axiom, it proves the axiom of pairing.


    Main library

        This article is a stub. Please help us to improve Cantor's Attic by adding information.