http://cantorsattic.info/api.php?action=feedcontributions&user=Stefan+Mesken&feedformat=atomCantor's Attic - User contributions [en]2022-09-26T12:13:47ZUser contributionsMediaWiki 1.24.4http://cantorsattic.info/index.php?title=Talk:Kripke-Platek&diff=2131Talk:Kripke-Platek2017-11-14T21:34:24Z<p>Stefan Mesken: </p>
<hr />
<div>The proof theoretic ordinal for KP is the Bachmann-Howard ordinal. I think this &ldquo;large countable&rdquo; ordinal deserves its own article in Cantor's Attic. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:15, 14 November 2017 (PST)<br />
<br />
The article is missing references and I'm not sure where to point at. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:25, 14 November 2017 (PST)<br />
<br />
Welcome to the wiki Stefan. The article on ZFC doesn't have any reference either. We can let it like this for now, but if we add results like its proof theoretic ordinal we'll add references for those results. [[User:Julian Barathieu|Julian Barathieu]] ([[User talk:Julian Barathieu|talk]]) 13:32, 14 November 2017 (PST)</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=Talk:Kripke-Platek&diff=2129Talk:Kripke-Platek2017-11-14T21:25:29Z<p>Stefan Mesken: </p>
<hr />
<div>The proof theoretic ordinal for KP is the Bachmann-Howard ordinal. I think this countable ordinal deserves its own article in Cantor's Attic. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:15, 14 November 2017 (PST)<br />
<br />
The article is missing references and I'm not sure where to point at. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:25, 14 November 2017 (PST)</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=User_talk:Stefan_Mesken&diff=2128User talk:Stefan Mesken2017-11-14T21:21:16Z<p>Stefan Mesken: Created page with "Edit this page if you wish to contact me. --~~~~"</p>
<hr />
<div>Edit this page if you wish to contact me. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:21, 14 November 2017 (PST)</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=ZFC&diff=2127ZFC2017-11-14T21:20:02Z<p>Stefan Mesken: fixed quotation marks</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of ZFC}}<br />
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.<br />
<br />
==Axiom of Extensionality== <br />
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).$$ <br />
<br />
The &ldquo;$\rightarrow$&rdquo; can be replaced by &ldquo;$\leftrightarrow$&rdquo;, 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)$$<br />
<br />
meaning that sets with the same elements belong to the same sets.<br />
<br />
==Axiom of Null Set==<br />
There exists some set. In fact, there is a set which contains no members. <br />
This is expressed formally $$ \exists x \forall y (y\not\in x).$$ <br />
<br />
Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.<br />
<br />
==Axiom of Pairing== <br />
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$.<br />
<br />
$$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$ <br />
<br />
Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.<br />
<br />
==Axiom of Union==<br />
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 <br />
<br />
$$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$ <br />
<br />
Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.<br />
<br />
==Axiom of Foundation (Regularity)==<br />
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).$$<br />
<br />
Equivalently, by the [[Axiom of Choice]] there's no infinite descending sequence $\dots \in x_2\in x_1\in x_0$.<br />
<br />
==Axiom Schema of Separation== <br />
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) $$ <br />
<br />
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)\}$.<br />
<br />
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}$.<br />
<br />
==Axiom of Infinity==<br />
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).$$<br />
<br />
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.<br />
<br />
==Axiom of Power Set== <br />
For any set $x$ there is a further set $y$ that has as members all subsets of $x$ and no other elements. <br />
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)$.]<br />
<br />
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$.<br />
<br />
==Axiom of Choice==<br />
''Main article: [[Axiom of Choice]].''<br />
<br />
There are many formulations of this axiom. It is historically the most controversial of the axioms of $ZFC$. <br />
<br />
$$\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] $$<br />
<br />
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).<br />
<br />
==Axiom Schema of Replacement==<br />
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:<br />
$$ \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].$$<br />
<br />
===Applications of Replacement===<br />
<br />
The axiom of replacement proves that every well-ordered set is isomorphic to a (unique) ordinal.<br />
<br />
''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$<br />
<br />
$\forall x\exists \alpha (x\in V_\alpha)$.<br />
<br />
For all ordinals $\alpha$, $\aleph_\alpha$ exists (i.e. for every $\alpha$ there are at least $\alpha + 1$-many infinite cardinals).<br />
<br />
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.<br />
<br />
{{References}}<br />
<br />
{{stub}}</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=Kripke-Platek&diff=2126Kripke-Platek2017-11-14T21:19:16Z<p>Stefan Mesken: fixed quotation marks</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of Kripke-Platek}}<br />
Kripke-Platek set theory is a collection of axioms that is considerably weaker than [[ZFC]]. 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.<br />
<br />
==Axiom of Extensionality== <br />
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).$$ <br />
<br />
The &ldquo;$\rightarrow$&rdquo; can be replaced by &ldquo;$\leftrightarrow$&rdquo;, but the $\leftarrow$ direction is a theorem of logic.<br />
<br />
==Axiom of Null Set==<br />
There exists some set. In fact, there is a set which contains no members. <br />
This is expressed formally $$ \exists x \forall y (y\not\in x).$$ <br />
<br />
Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.<br />
<br />
==Axiom of Pairing== <br />
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$.<br />
<br />
$$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$ <br />
<br />
Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.<br />
<br />
==Axiom of Union==<br />
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 <br />
<br />
$$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$ <br />
<br />
Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.<br />
<br />
==Axiom Schema of Foundation==<br />
Suppose that a given property $P$ is true for some set $x$. Then there is a $\in$-minimal set for which $P$ is true.<br />
In more detail, given a formula $\varphi(x_1,\dots,x_n,x)$ the following is an instance of the induction schema:<br />
$$\forall x_1, \ldots, x_n \big[ \exists x \varphi(x_1, \ldots, x_n, x) \rightarrow \exists y \big( \varphi(x_1, \ldots, x_n, y) \wedge \forall z \in y \neg \varphi(x_1, \ldots, x_n, z) \big) \big]$$<br />
<br />
==Axiom Schema of $\Sigma_0$-Separation== <br />
For any set $a$ and any $\Sigma_0$-predicate $P(x)$ written in the language of ZFC, the set $\{x\in a: P(x)\}$ exists. In more detail, given any $\Sigma_0$-formula $\varphi$ with free variables $x_1,x_2,\dots,x_n$ the following is an instance of the $\Sigma_0$-seperation schema: <br />
$$ \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) $$ <br />
<br />
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)\}$.<br />
<br />
==Axiom Schema of $\Sigma_0$-Collection==<br />
If $a$ is a set and for all $x\in a$ there's a some $y$ such that $(x,y)$ satisfies a given $\Sigma_0$-property, then there is some set $b$ such that for all $x \in a$ there is some $y \in b$ such that $(x,y)$ satisfies that property. In more detail, given a $\Sigma_0$-formula $\varphi(x_1,\dots,x_n,x,y)$ the following is an instance of the $\Sigma_0$-collection schema:<br />
$$ \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 \big(\exists b \forall x \in a \exists y \in b \varphi(x_1, \ldots, x_n, x,y) \big) \big].$$<br />
<br />
==Axiom of Infinity==<br />
Some authors include the axiom of infinity in Kripke-Platek set theory which states that there is an [[inductive set]] – a canonical example of an infinite set. More precisely:<br />
$$ \exists x \big( \emptyset \in x \wedge \forall y \in x (y \cup \{y \} \in x) \big).$$<br />
The axiom of infinity combined with an instance of $\Sigma_0$-separation imply the axiom of null set so that it be dropped if one assumes the axiom of infinity.</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=Talk:Kripke-Platek&diff=2125Talk:Kripke-Platek2017-11-14T21:15:06Z<p>Stefan Mesken: Created page with "The proof theoretic ordinal for KP is the Bachmann-Howard ordinal. I think this countable ordinal deserves its own article in Cantor's Attic. --~~~~"</p>
<hr />
<div>The proof theoretic ordinal for KP is the Bachmann-Howard ordinal. I think this countable ordinal deserves its own article in Cantor's Attic. --[[User:Stefan Mesken|Stefan Mesken]] ([[User talk:Stefan Mesken|talk]]) 13:15, 14 November 2017 (PST)</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=Kripke-Platek&diff=2124Kripke-Platek2017-11-14T21:12:50Z<p>Stefan Mesken: Axioms of Kripke-Platek set theory</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of Kripke-Platek}}<br />
Kripke-Platek set theory is a collection of axioms that is considerably weaker than [[ZFC]]. 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.<br />
<br />
==Axiom of Extensionality== <br />
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).$$ <br />
<br />
The ``$\rightarrow$" can be replaced by $``\leftrightarrow"$, but the $\leftarrow$ direction is a theorem of logic.<br />
<br />
==Axiom of Null Set==<br />
There exists some set. In fact, there is a set which contains no members. <br />
This is expressed formally $$ \exists x \forall y (y\not\in x).$$ <br />
<br />
Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.<br />
<br />
==Axiom of Pairing== <br />
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$.<br />
<br />
$$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$ <br />
<br />
Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.<br />
<br />
==Axiom of Union==<br />
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 <br />
<br />
$$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$ <br />
<br />
Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.<br />
<br />
==Axiom Schema of Foundation==<br />
Suppose that a given property $P$ is true for some set $x$. Then there is a $\in$-minimal set for which $P$ is true.<br />
In more detail, given a formula $\varphi(x_1,\dots,x_n,x)$ the following is an instance of the induction schema:<br />
$$\forall x_1, \ldots, x_n \big[ \exists x \varphi(x_1, \ldots, x_n, x) \rightarrow \exists y \big( \varphi(x_1, \ldots, x_n, y) \wedge \forall z \in y \neg \varphi(x_1, \ldots, x_n, z) \big) \big]$$<br />
<br />
==Axiom Schema of $\Sigma_0$-Separation== <br />
For any set $a$ and any $\Sigma_0$-predicate $P(x)$ written in the language of ZFC, the set $\{x\in a: P(x)\}$ exists. In more detail, given any $\Sigma_0$-formula $\varphi$ with free variables $x_1,x_2,\dots,x_n$ the following is an instance of the $\Sigma_0$-seperation schema: <br />
$$ \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) $$ <br />
<br />
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)\}$.<br />
<br />
==Axiom Schema of $\Sigma_0$-Collection==<br />
If $a$ is a set and for all $x\in a$ there's a some $y$ such that $(x,y)$ satisfies a given $\Sigma_0$-property, then there is some set $b$ such that for all $x \in a$ there is some $y \in b$ such that $(x,y)$ satisfies that property. In more detail, given a $\Sigma_0$-formula $\varphi(x_1,\dots,x_n,x,y)$ the following is an instance of the $\Sigma_0$-collection schema:<br />
$$ \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 \big(\exists b \forall x \in a \exists y \in b \varphi(x_1, \ldots, x_n, x,y) \big) \big].$$<br />
<br />
==Axiom of Infinity==<br />
Some authors include the axiom of infinity in Kripke-Platek set theory which states that there is an [[inductive set]] – a canonical example of an infinite set. More precisely:<br />
$$ \exists x \big( \emptyset \in x \wedge \forall y \in x (y \cup \{y \} \in x) \big).$$<br />
The axiom of infinity combined with an instance of $\Sigma_0$-separation imply the axiom of null set so that it be dropped if one assumes the axiom of infinity.</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=ZFC&diff=2123ZFC2017-11-14T20:55:03Z<p>Stefan Mesken: /* Axiom Schema of Replacement */</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of ZFC}}<br />
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.<br />
<br />
==Axiom of Extensionality== <br />
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).$$ <br />
<br />
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)$$<br />
<br />
meaning that sets with the same elements belong to the same sets.<br />
<br />
==Axiom of Null Set==<br />
There exists some set. In fact, there is a set which contains no members. <br />
This is expressed formally $$ \exists x \forall y (y\not\in x).$$ <br />
<br />
Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.<br />
<br />
==Axiom of Pairing== <br />
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$.<br />
<br />
$$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$ <br />
<br />
Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.<br />
<br />
==Axiom of Union==<br />
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 <br />
<br />
$$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$ <br />
<br />
Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.<br />
<br />
==Axiom of Foundation (Regularity)==<br />
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).$$<br />
<br />
Equivalently, by the [[Axiom of Choice]] there's no infinite descending sequence $\dots \in x_2\in x_1\in x_0$.<br />
<br />
==Axiom Schema of Separation== <br />
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) $$ <br />
<br />
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)\}$.<br />
<br />
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}$.<br />
<br />
==Axiom of Infinity==<br />
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).$$<br />
<br />
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.<br />
<br />
==Axiom of Power Set== <br />
For any set $x$ there is a further set $y$ that has as members all subsets of $x$ and no other elements. <br />
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)$.]<br />
<br />
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$.<br />
<br />
==Axiom of Choice==<br />
''Main article: [[Axiom of Choice]].''<br />
<br />
There are many formulations of this axiom. It is historically the most controversial of the axioms of $ZFC$. <br />
<br />
$$\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] $$<br />
<br />
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).<br />
<br />
==Axiom Schema of Replacement==<br />
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:<br />
$$ \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].$$<br />
<br />
===Applications of Replacement===<br />
<br />
The axiom of replacement proves that every well-ordered set is isomorphic to a (unique) ordinal.<br />
<br />
''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$<br />
<br />
$\forall x\exists \alpha (x\in V_\alpha)$.<br />
<br />
For all ordinals $\alpha$, $\aleph_\alpha$ exists (i.e. for every $\alpha$ there are at least $\alpha + 1$-many infinite cardinals).<br />
<br />
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.<br />
<br />
{{References}}<br />
<br />
{{stub}}</div>Stefan Meskenhttp://cantorsattic.info/index.php?title=ZFC&diff=2122ZFC2017-11-14T20:26:04Z<p>Stefan Mesken: changed "Axiom of Unions" to "Axiom of Union" because I view the plural as a break in style, considering for example the "Axiom of Pairing"</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of ZFC}}<br />
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.<br />
<br />
==Axiom of Extensionality== <br />
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).$$ <br />
<br />
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)$$<br />
<br />
meaning that sets with the same elements belong to the same sets.<br />
<br />
==Axiom of Null Set==<br />
There exists some set. In fact, there is a set which contains no members. <br />
This is expressed formally $$ \exists x \forall y (y\not\in x).$$ <br />
<br />
Such an $x$ is unique by extensionality and this set is denoted by $\emptyset$.<br />
<br />
==Axiom of Pairing== <br />
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$.<br />
<br />
$$ \forall x \forall y \exists z \forall w \big(w\in z\leftrightarrow (w=x\vee w=y)\big).$$ <br />
<br />
Such a $z$ is unique by extensionality and is denoted as $\{x,y\}$.<br />
<br />
==Axiom of Union==<br />
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 <br />
<br />
$$\forall x \exists y \forall z \big(z\in y \leftrightarrow \exists w (w\in x \wedge z\in w)\big).$$ <br />
<br />
Such a $y$ is unique by extensionality and is written as $y = \bigcup x$.<br />
<br />
==Axiom of Foundation (Regularity)==<br />
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).$$<br />
<br />
Equivalently, by the [[Axiom of Choice]] there's no infinite descending sequence $\dots \in x_2\in x_1\in x_0$.<br />
<br />
==Axiom Schema of Separation== <br />
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) $$ <br />
<br />
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)\}$.<br />
<br />
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}$.<br />
<br />
==Axiom of Infinity==<br />
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).$$<br />
<br />
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.<br />
<br />
==Axiom of Power Set== <br />
For any set $x$ there is a further set $y$ that has as members all subsets of $x$ and no other elements. <br />
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)$.]<br />
<br />
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$.<br />
<br />
==Axiom of Choice==<br />
''Main article: [[Axiom of Choice]].''<br />
<br />
There are many formulations of this axiom. It is historically the most controversial of the axioms of $ZFC$. <br />
<br />
$$\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] $$<br />
<br />
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).<br />
<br />
==Axiom Schema of Replacement==<br />
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:<br />
$$ \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].$$<br />
<br />
===Applications of Replacement===<br />
<br />
The axiom of replacement proves that every well-ordered set is isomorphic to a (unique) ordinal.<br />
<br />
''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$<br />
<br />
$\forall x\exists \alpha (x\in V_\alpha)$.<br />
<br />
For all ordinals $\alpha$, $\aleph_\alpha$ exists (i.e. for every $\alpha$ there are at least $\alpha + 1$-many infinite cardinals).<br />
<br />
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.<br />
<br />
{{References}}<br />
<br />
{{stub}}</div>Stefan Mesken