Difference between revisions of "ZFC"

From Cantor's Attic
Jump to: navigation, search
(fixed quotation marks)
Line 1: Line 1:
{{DISPLAYTITLE: The Axioms of ZFC}}
+
{{DISPLAYTITLE: The axioms of Zermelo-Fraenkel set theory}}
Zermelo-Frankel Set Theory with Axiom of Choice 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.
+
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.
  
 
==Axiom of Extensionality==  
 
==Axiom of Extensionality==  
Line 76: Line 76:
  
 
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.
 
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.
 +
 +
== See also ==
 +
 +
* [[Con ZFC|Consistency of ZFC]]
 +
* [[Transitive ZFC model|Transitive model of ZFC]]
  
 
{{References}}
 
{{References}}
  
 
{{stub}}
 
{{stub}}

Revision as of 13:36, 14 November 2017

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.

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

Axiom of 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$.

Axiom of Foundation (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$.

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

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

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

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

See also

References

    Main library


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