Below is an attempt to describe a model $\mathcal{M}''$ of ZFC wherein a chain of sets $c_0 \ni c_1 \dots \ni c_p \ni \dots$ seemingly exists, even as a $\omega$-sequence $(c_0, c_1, \dots) \in \mathcal{M}''$ which if true would violate the axiom of regularity. More precisely, the construction is claimed (surely falsely) to yield sets $c_0 = \{c_1\}, c_1 = \{c_2\}, c_2 = \{c_3\}$, and so forth, and their sequence $(c_0, c_1, \dots)$ inside the model.
-
Begin with ZFC and its classical signature $\langle \varnothing, \varnothing, \{\in, =\}\rangle$. Assume ZFC is consistent. Then it has some model $\mathcal{M}$ via Henkin-Lindebaum arguments. We may fix the model $\mathcal{M}$ to be transitive, for if ZFC is consistent then also ZFC + “ZFC has transitive model” is consistent via a version of the reflection principle.
-
Add a countable infinity of constant symbols $c_0, c_1, c_2, \dots$ for a signature $\langle \{c_0, c_1, c_2, \dots\}, \varnothing, \{\in, =\}\rangle$. These constants will play the role of the infinite chain later on, cf. points 3 and 4. Note that the metainteger subindices are essentially placeholders and could be replaced by bars, i.e. $c, c_|, c_{||}$, et cetera.
-
Add a countable infinity of axioms $c_0 = \{c_1\}, c_1 = \{c_2\}, c_2 = \{c_3\}, \dots$. This can be accomplished via the axiom schema $\forall x (x \in c_i \Leftrightarrow x = c_{i+1})$ with $i = 0, 1, 2, \dots$. The bar interpretation has for $+1$ the appending of one additional bar. But perhaps the sets $c_p$ will start to repeat somewhere: for some $i \neq k$, it holds that $c_i = c_k$? We will avoid this with point 4.
-
Add a countable infinity of axioms $c_0 \neq c_1, c_0 \neq c_2, \dots, c_1 \neq c_2, c_1 \neq c_3, \dots$. The axioms claim that all sets $c_p$ are distinct, and this may be achieved via the axiom schema $c_i \neq c_j$ for $i\not\overset{\cdot}{=} j = 0, 1, 2, \dots$. (Equality with dot $\overset{\cdot}{=}$ means syntactic equality).
We will refer to the theory of ZFC plus points 2 to 4 by ZFC + C below.
Is this countably infinite addition of constants from 2, plus the axioms in 3 and 4 “fair game”? Meaning, that it will not lead to contradictions if ZFC is consistent? I claim the answer is yes; that no “additional” contradictions are possible in ZFC + C. This is the essence of points 5 to 9. The proof is by assumption to the contrary.
-
Assume to the contrary that ZFC + C is contradictory. In other words, that ZFC + C $\Vdash \mathcal{F} \wedge \neg\mathcal{F}$ for some (any) formula $\mathcal{F}$. Any proof of a contradiction $\mathcal{F} \wedge \neg\mathcal{F}$ will be finite, so too it must contain a finite number of new constants $c_{i_1}, c_{i_2}, \dots, c_{i_k}$ and a finite number of new axioms $\mathcal{A}_{j_1}, \mathcal{A}_{j_2}, \dots, \mathcal{A}_{j_m}$.
-
WLOG, since we may add new redundant branches and axioms to any proof, our proof of $\mathcal{F} \wedge \neg\mathcal{F}$ may be assumed to contain precisely new constants $c_0, c_1, \dots, c_k$ and new axioms $\mathcal{A}_{1}, \mathcal{A}_{2}, \dots, \mathcal{A}_{m}$ (after, possibly, a suitable renaming of $k$ and $m$). It will not matter much for our purposes how exactly the axioms are enumerated, so far as it is remembered that if an axiom $\mathcal{A}_j$ contains a constant symbol $c_i$, that $c_i$ will have been included amongst listed constants $c_0, c_1, \dots, c_k$.
Call the theory ZFC + $\{c_0, c_1, \dots, c_k\}$ + $\{\mathcal{A}_{1}, \mathcal{A}_{2}, \dots, \mathcal{A}_{m}\}$ by the name ZFC + D.
-
By definition of ZFC + D, it must also be the case that ZFC + D $\Vdash \mathcal{F} \wedge \neg\mathcal{F}$. In other words, ZFC + D must also be contradictory, should ZFC + C be contradictory. This will be in contradiction with point 8 where a model of ZFC + D is built. (In 9, we therefore conclude that our assumption in 5, of ZFC + C being contradictory, must be false).
-
ZFC + D cannot be contradictory because it has a model (if ZFC is not contradictory). Let us construct the model, which we will denote by $\mathcal{M}'$. We will turn the model $\mathcal{M}$ of ZFC into a model of ZFC + D. All to be done is to add an interpretation for constant symbols $c_0, c_1, \dots, c_k$. This may be done as follows:
\begin{align*}
c_k &:= \varnothing\\
c_{k-1} &:= \{\varnothing\}\\
c_{k-2} &:= \{\{\varnothing\}\}\\
\vdots\\
c_{1} &:= \underbrace{\{\dots\{}_{k-1 \text{ braces}} \hspace{-0.5em} \varnothing \hspace{-1.2em} \underbrace{\}\dots\}}_{\hspace{1.3em}k-1 \text{ braces}}\\
c_{0} &:= \underbrace{\{\dots\{}_{k \text{ braces}} \hspace{-0.1em} \varnothing \hspace{-0.4em} \underbrace{\}\dots\}}_{\hspace{0.5em}k \text{ braces}}
\end{align*}
These sets are all pairwise different, thus satisfying any axioms of type 3 among $\mathcal{A}_{1}, \mathcal{A}_{2}, \dots, \mathcal{A}_{m}$. And $x \in c_i$ iff $x \in c_{i+1}$, meeting all axioms of type 2 among $\mathcal{A}_{1}, \mathcal{A}_{2}, \dots, \mathcal{A}_{m}$. Note that $\varnothing = \varnothing^\mathcal{M}$ because $\mathcal{M}$ is transitive. -
On the one hand, we assumed that ZFC + C is contradictory which yielded a contradiction in ZFC + D. On the other hand, ZFC + D must be contradiction-free as it possesses a model, namely $\mathcal{M}'$. We conclude that ZFC + C must, in fact, be consistent provided ZFC is consistent. So additions in points 2 to 4 were “fair game”.
-
If ZFC + C is consistent, as it must be if ZFC is, then ZFC + C also has a model. Fix one such model $\mathcal{M}''$ which we may again assume to be transitive.
Finally, we attempt to argue that $\mathcal{M}''$ has contradictions.
- It is derivable in ZF − Regularity that if regularity holds, then there is no $\omega$-sequence $f: \omega \to X$ of sets, $f := (X_0, X_1, \dots)$, such that $\forall i \in \omega\, (X_i \ni X_{i+1})$. Now $\mathcal{M}''$ is a model of ZFC + C, thus it has $c_0 \ni c_1 \dots \ni c_p \ni \dots$ (again, the indices of $c$'s are bars $|$). We conclude, again because $\mathcal{M}''$ is a model of ZFC + C, the sequence $(c_0, c_1, \dots, c_p, \dots) = (c_0, c_1, \dots, c_p, \dots)^{\mathcal{M}''}$ cannot exist inside $\mathcal{M}''$ to avoid contradictions. (The sequences are “the same” because $\mathcal{M}''$ is transitive, and being a function, $\omega$, $\mathrm{ran}$, $\mathrm{dom}$ are absolute wrt transitive models. As for the $c_p$'s, what will be most important about them in $\mathcal{M}''$ is captured by them satisfying axioms of type 2 and type 3).
In points 12 through 14 we will use transitive closure and recursion to show that $(c_0, c_1, \dots, c_p, \dots) \in \mathcal{M}''$ which is the crux of the issue.
-
Now, in ZF − Regularity one may prove, for any set $Y$, the existence of the transitive closure of $Y$, namely $\operatorname{TC}(Y)$. Here $\operatorname{TC}(Y)$ is the unique $\subseteq$-smallest transitive set such that $Y \in \operatorname{TC}(Y)$. One may prove that $\operatorname{TC}(Y) = \bigcup\{Y, \cup Y, \cup\cup Y, \dots\}$.
-
The transitive closure must thus also exist inside $\mathcal{M}''$ for any $Y \in \mathcal{M}''$. The transitive closure of a set is also absolute wrt transitive models, so, for $Y \in \mathcal{M}''$, $\operatorname{TC}(Y) = \operatorname{TC}(Y)^{\mathcal{M}''}$. Most notably, $\operatorname{TC}(c_0) \in \mathcal{M}''$, and since $\operatorname{TC}(c_0) = \{c_0, c_1, \dots, c_p, \dots\} =: \zeta$, then $\{c_0, c_1, \dots, c_p, \dots\} \in \mathcal{M}''$. (Taking a union is also absolute wrt transitive models).
-
Let us use recursion (provable in at least ZF) to construct the trouble-maker $(c_0, c_1, \dots, c_p, \dots)$ inside $\mathcal{M}''$. We proceed thusly.
\begin{cases}
u({0}_\omega) &= c_0,\\
u({n^+}_\omega) &= F(u(n_\omega))
\end{cases}
where $F$ “picks the only element” inside of its argument set. More precisely, let $F = F(x, y)$ be the formula
\begin{align*}F(x, y) \overset{\cdot}{=}&\ x \neq \varnothing \wedge \forall a \in x\, \forall b \in x\,(a = b) \wedge y \in x \vee\phantom{x}\\
&\vee y = \varnothing.
\end{align*}
Therefore the recursion is justified. Furthermore, $u(n_\omega) = c_n$. Here $F(x, y)$ is (equivalent to) a $\Delta_0$-formula and ergo absolute wrt transitive models. -
In conclusion, $u = (c_0, c_1, \dots, c_p, \dots)$ will exist inside $\mathcal{M}''$. This is in contradiction with the axiom of regularity which must also hold inside $M''$ as it is a model for ZFC (take $f := u$ for point 11).
- Q: What is a/the source of the problem here?
It is probably most comfortable to say, “Hey, the mistakes are in points numbered x, y, z”. This is part of the reason for introducing the numbering 1 to 15.
Best Answer
The compactness argument that there is a model of what you're calling $\sf ZFC +C$ (assuming there is a model of $\sf ZFC$) is fine, but the issue is when you extrapolate that to saying $\sf ZFC + C$ has a transitive model. Everything after that is moot because it plainly doesn't, at least provided we're assuming foundation in the metatheory. A model of $\sf ZFC + C$ is necessarily not-well-founded and thus not transitive... that's sort of the point of the construction. It's as if you've shown the existence of a nonstandard model of arithmetic with compactness, and then you turn around and say "we can assume the model is $\mathbb N$".
The existence of a model of some theory doesn't usually imply the existence of a well-founded/transitive model of that theory, even in the case where there are no obvious problems. For instance, if there were a transitive model of $\sf ZFC$, then the minimal tranistive model (i.e. $L_\alpha$ for the minimal $\alpha$ such that $L_\alpha \models \sf ZFC$) thinks there are no transitive models, but it is arithmetically sound so it knows that $\sf ZFC$ is consistent. Thus it is consistent that there are no transitive models of $\sf ZFC,$ even in the case that there are models of $\sf ZFC.$
You attempt to rebut this in the comments by giving an argument that $\sf Con(ZFC)\to Con(ZFC^+)$ where $\sf ZFC^+$ is a theory in an expanded language with a constant symbol $t$ whose axioms are $\sf ZFC$ $\cup$ {"$t$ is transitive"} $\cup$ $\{\varphi^t: t\in \sf ZFC\}.$ This proof is correct, but the consistency of $\sf ZFC^+$ doesn't imply the consistency of $\sf ZFC$ + "there is a transitive model of $\sf ZFC$." Sure, you get a model of $\sf ZFC^+$, but this model may have nonstandard integers, and hence nonstandard axioms in its internal version of $\sf ZFC$. The $t$-relativized axioms (and the theorem schema $\varphi^t\leftrightarrow t\models \ulcorner \varphi \urcorner$) only allow you to conclude that $M\models (t\models \ulcorner \varphi \urcorner)$ for the standard (i.e. actual) axioms $\varphi$ of $\sf ZFC$ and it may be that $M$ thinks that $t$ fails to satisfy some (nonstandard) axioms. So you aren't guaranteed that $M\models (t\models \ulcorner \sf ZFC\urcorner)$ any more than you would be guaranteed that some model $M$ of $\sf PA$ has $M\models \forall x\varphi(x)$ just on the basis that for all $n\in\mathbb N,$ $M\models\varphi(S^n0).$
Now, if you were guaranteed a transitive model of $\sf ZFC^+,$ or even just a model with standard integers, things would be different, but the whole point of this discussion is that you aren't.