http://cantorsattic.info/api.php?action=feedcontributions&user=Q&feedformat=atomCantor's Attic - User contributions [en]2022-09-26T05:31:57ZUser contributionsMediaWiki 1.24.4http://cantorsattic.info/index.php?title=User:Q&diff=1153User:Q2013-12-30T00:15:12Z<p>Q: Created page with "College student in the U.S. and math enthusiast."</p>
<hr />
<div>College student in the U.S. and math enthusiast.</div>Qhttp://cantorsattic.info/index.php?title=ZFC&diff=1152ZFC2013-12-30T00:12:26Z<p>Q: /* Axiom Schema of Separation */</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of $ZFC$}}<br />
<br />
<br />
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.<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 />
<br />
<br />
==Axiom of Unions==<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 />
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>Qhttp://cantorsattic.info/index.php?title=ZFC&diff=1151ZFC2013-12-29T23:52:25Z<p>Q: </p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of $ZFC$}}<br />
<br />
<br />
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.<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 />
<br />
<br />
==Axiom of Unions==<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 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) $$ <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 />
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>Qhttp://cantorsattic.info/index.php?title=ZFC&diff=1150ZFC2013-12-29T23:41:04Z<p>Q: /* Axiom of Extensionality */</p>
<hr />
<div>{{DISPLAYTITLE: The Axioms of $ZFC$}}<br />
<br />
<br />
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.<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$ which has as members the sets $x$ and $y$ and no others. <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 />
<br />
<br />
==Axiom of Unions==<br />
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 <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 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).$$<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 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) $$ <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 />
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>Q