The axioms of Zermelo-Fraenkel set theory

From Cantor's Attic
Jump to: navigation, search

Zermelo-Frankel set theory with axiom of choice ($\text{ZFC}$) is 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.

Axioms

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.

Empty 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$.

Pairing

For any two sets $x$ and $y$ (not necessarily distinct) there is a further set $z$ whose members are exactly the sets $x$ and $y$.

$$ \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\}$.

Union

For any set $x$ there is a further set $y$ whose members are exactly all the members of the members of $x$. That is, the union of all the members of a set exists. 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$.

Foundation (or Regularity)

Every nonempty set $x$ has a member disjoint from $x$, ensuring that no set can contain itself directly or indirectly. 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$.

Schema of separation

For any set $a$ and any predicate $P(x)$ written in the language of ZFC, the set $\{x\in a: P(x)\}$ 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}$.

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.

Powerset

For any set $x$ there is a further set $y$ that has as members all subsets of $x$ and no other elements. $y$ is the powerset of $x$. 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$.

Choice

Main article: 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).

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 \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.

History

To be expanded.

Consistency of ZFC

The assertion $\text{Con(ZFC)}$ is the assertion that the theory $\text{ZFC}$ is consistent. This is an assertion with complexity $\Pi^0_1$ in arithmetic, since it is the assertion that every natural number is not the Gödel code of the proof of a contradiction from $\text{ZFC}$. Because of the Gödel completeness theorem, the assertion is equivalent to the assertion that the theory $\text{ZFC}$ has a model $\langle M,\hat\in\rangle$. One such model is the Henkin model, built in the syntactic procedure from any complete consistent Henkin theory extending $\text{ZFC}$. In general, one may not assume that $\hat\in$ is the actual set membership relation, since this would make the model a transitive model of $\text{ZFC}$, whose existence is a strictly stronger assertion than $\text{Con(ZFC)}$.

The Gödel incompleteness theorem implies that if $\text{ZFC}$ is consistent, then it does not prove $\text{Con(ZFC)}$, and so the addition of this axiom is strictly stronger than $\text{ZFC}$ alone.

The expression $\text{Con}^2(\text{ZFC})$ denotes the assertion $\text{Con}(\text{ZFC}+\text{Con}(\text{ZFC}))$, and iterating this more generally, one may consider the assertion $\text{Con}^\alpha(\text{ZFC})$ whenever $\alpha$ itself is expressible.

Transitive models

A transitive model of $\text{ZFC}$ is a transitive set $M$ such that the structure $\langle M,\in\rangle$ satisfies all of the $\text{ZFC}$ axioms of set theory. The existence of such a model is strictly stronger than $\text{Con(ZFC)}$ and stronger than an iterated consistency hierarchy, but weaker than the existence of an worldly cardinal, a cardinal $\kappa$ for which $V_\kappa$ is a model of $\text{ZFC}$, and consequently also weaker than the existence of an inaccessible cardinal. Not all transitive models of $\text{ZFC}$ have the $V_\kappa$ form, for if there is any transitive model of $\text{ZFC}$, then by the Löwenheim-Skolem theorem there is a countable such model, and these never have the form $V_\kappa$.

Nevertheless, every transitive model $M$ of $\text{ZFC}$ provides a set-theoretic forum inside of which one can view nearly all classical mathematics taking place. In this sense, such models are inaccessible to or out of reach of ordinary set-theoretic constructions. As a result, the existence of a transitive model of $\text{ZFC}$ can be viewed as a large cardinal axiom: it expresses a notion of largeness, and the existence of such a model is not provable in $\text{ZFC}$ and has consistency strength strictly exceeding $\text{ZFC}$.

Minimal transitive model of $\text{ZFC}$

If there is any transitive model $M$ of $\text{ZFC}$, then $L^M$, the constructible universe as computed in $M$, is also a transitive model of $\text{ZFC}$ and indeed, has the form $L_\eta$, where $\eta=\text{ht}(M)$ is the height of $M$. The minimal transitive model of $\text{ZFC}$ is the model $L_\eta$, where $\eta$ is smallest such that this is a model of $\text{ZFC}$. The argument just given shows that the minimal transitive model is a subset of all other transitive models of $\text{ZFC}$.

$\omega$-models of $\text{ZFC}$

An $\omega$-model of $\text{ZFC}$ is a model of $\text{ZFC}$ whose collection of natural numbers is isomorphic to the actual natural numbers. In other words, an $\omega$-model is a model having no nonstandard natural numbers, although it may have nonstandard ordinals. (More generally, for any ordinal $\alpha$, an $\alpha$-model has well-founded part at least $\alpha$.) Every transitive model of $\text{ZFC}$ is an $\omega$-model, but the latter concept is strictly weaker.

Consistency hierarchy

The existence of an $\omega$-model of $\text{ZFC}$ and implies $\text{Con(ZFC)}$, of course, and also $\text{Con(ZFC+Con(ZFC))}$ and a large part of the iterated consistency hierarchy. This is simply because if $M\models\text{ZFC}$ and has the standard natural numbers, then $M$ agrees that $\text{Con(ZFC)}$ holds, since it has the same proofs as we do in the ambient background. Thus, we believe that $M$ satisfies $\text{ZFC+Con(ZFC)}$ and consequently we believe $\text{Con(ZFC+Con(ZFC))}$. It follows again that $M$ agrees with this consistency assertion, and so we now believe $\text{Con}^3(\text{ZFC})$. The model $M$ therefore agrees and so we believe $\text{Con}^4(\text{ZFC})$ and so on transfinitely, as long as we are able to describe the ordinal iterates in a way that $M$ interprets them correctly.

Every finite fragment of $\text{ZFC}$ admits numerous transitive models, as a consequence of the reflection theorem.

Transitive models and forcing

Countable transitive models of set theory were used historically as a convenient way to formalize forcing. Such models $M$ make the theory of forcing convenient, since one can easily prove that for every partial order $\mathbb{P}$ in $M$, there is an $M$-generic filter $G\subset\mathbb{P}$, simply by enumerating the dense subsets of $\mathbb{P}$ in $M$ in a countable sequence $\langle D_n\mid n\lt\omega\rangle$, and building a descending sequence $p_0\geq p_1\geq p_2\geq\cdots$, with $p_n\in D_n$. The filter $G$ generated by the sequence is $M$-generic.

For the purposes of consistency proofs, this manner of formalization worked quite well. To show $\text{Con}(\text{ZFC})\to \text{Con}(\text{ZFC}+\varphi)$, one fixes a finite fragment of $\text{ZFC}$ and works with a countable transitive model of a suitably large fragment, producing $\varphi$ with the desired fragment in a forcing extension of it.

Transitive model universe axiom

The transitive model universe axiom is the assertion that every set is an element of a transitive model of $\text{ZFC}$. This axiom makes a stronger claim than the Feferman theory, since it is asserted as a single first-order claim, but weaker than the universe axiom, which asserts that the universes have the form $V_\kappa$ for inaccessible cardinals $\kappa$.

The transitive model universe axiom is sometimes studied in the background theory not of $\text{ZFC}$, but of ZFC-P, omitting the power set axiom, together with the axiom asserting that every set is countable. Such an enterprise amounts to adopting the latter theory, not as the fundamental axioms of mathematics, but rather as a background meta-theory for studying the multiverse perspective, investigating how the various actual set-theoretic universe, transitive models of full $\text{ZFC}$, relate to one another.

Every model of $\text{ZFC}$ contains a model of $\text{ZFC}$ as an element

Every model $M$ of $\text{ZFC}$ has an element $N$, which it believes to be a first-order structure in the language of set theory, which is a model of $\text{ZFC}$, as viewed externally from $M$. This is clear in the case where $M$ is an $\omega$-model of $\text{ZFC}$, since in this case $M$ agrees that $\text{ZFC}$ is consistent and can therefore build a Henkin model of $\text{ZFC}$. In the remaining case, $M$ has nonstandard natural numbers. By the reflection theorem applied in $M$, we know that the $\Sigma_n$ fragment of $\text{ZFC}$ is true in models of the form $V_\beta^M$, for every standard natural number $n$. Since $M$ cannot identify its standard cut, it follows that there must be some nonstandard $n$ for which $M$ thinks some $V_\beta^M$ satisfies the (nonstandard) $\Sigma_n$ fragment of $\text{ZFC}$. Since $n$ is nonstandard, this includes the full standard theory of $\text{ZFC}$, as desired.

The fact mentioned in the previous paragraph is occasionally found to be surprising by some beginning set-theorists, perhaps because naively the conclusion seems to contradict the fact that there can be models of $\text{ZFC}+\neg\text{Con}(\text{ZFC})$. The paradox is resolved, however, by realizing that although the model $N$ inside $M$ is actually a model of full $\text{ZFC}$, the model $M$ need not agree that it is a model of $\text{ZFC}$, in the case that $M$ has nonstandard natural numbers and hence nonstandard length axioms of $\text{ZFC}$.

References

    Main library


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