Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.
View the Project on GitHub neugierde/cantors-attic
Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar
Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine
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.
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.
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$.
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\}$.
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$.
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$.
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}$.
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.
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$.
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).
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\].\)
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.
To be expanded.
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.
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 and Mostowski collapsing lemma 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}$.
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}$.
Its height is smaller then the least stable ordinal although the existence of stable ordinals is provable in ZFC and the existence of transitive models is not. (Madore, 2017)
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.
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.
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.
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 $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}$.
Recall that Löwenheim-Skolem theorem and Mostowski collapsing lemma show that if there is a transitive model of ZFC (or other set theory), then there is a countable such model. That means that $L$ of each uncountable transitive model is a model of ZFC+$V=L$+«there is a countable transitive model of ZFC+$V=L$» and there are countable transitive models of this theory that must have greater height that the minimal model. Similarly, there are transitive models of theories asserting any number of countable transitive models of different heights up to $\omega_1$ (meaning of which depends on the model: in general $\omega_1^{M_1} \neq \omega_1^{M_2}$). Further, there are transitive models of theories asserting «There are $\alpha$ countable transitive models of ZFC+«There are $\omega_1$ countable transitive models of ZFC of different heights» of different heights» etc. Therefore, if there is an uncountable transitive model, then there are “really very many” (in the informal meaning that was suggested by ‘etc.’) countable transitive models and they are unbounded in $\omega_1$ (for otherwise they could not have $\omega_1$ different heights).
Assume that in $V$ we have a transitive model of height of cardinality $\kappa$. We can turn each uncountable successor cardinal $\lambda^+ \leq \kappa$ into $\omega_1$ by forcing (in $V[G]$). In $V[G]$, transitive models are unbounded in $\omega_1^{V[G]}$ ($= (\lambda^+)^V \leq \kappa$). The constructible universe of a transitive model ($L_{\mathrm{ht}(M)}$) is a model of ZFC+$V=L$ and it is an element of $L$ which is common for $V$ and $V[G]$. So models of ZFC+$V=L$ are unbounded in $(\lambda^+)^V$ in $V$. Some of them have height of cardinality $\lambda$ and there are “very many” of them. Therefore, if there is a transitive model of height of cardinality $\kappa$, then there are “very many” transitive models of heights of all cardinalities $\lambda<\kappa$.
In particular, models of ZFC (and of ZFC+«models of ZFC are unbounded» etc.) are unbounded in $V_\kappa$ for worldly $\kappa$, just like in $V_\kappa$ for inaccessible $\kappa$ there are worldly, 1-worldly, hyper-worldly etc. cardinals.
This article is a stub. Please help us to improve Cantor's Attic by adding information.