An infinite chain of theories

Question

Let $\sf X$ be some theory stronger in some form than $\sf ZFC$.

In the theory $\sf X$, you might be able to prove $con(\sf ZFC)$

Now, let $\sf Y$ be some theory stronger in some way or form than theory $X$.

In theory $\sf Y$, you might be able to prove $con(\sf X)$

Now, let theory $\sf N$ be some theory that is somehow "infinitely more strong" than all other theories.

My question is that:

• In this case, it is possible to prove $con(\sf N)$?

• Is there a more formal way to describe this chain of theories? And if so, would the theory $\sf N$ be able to prove $con(\sf N-1)$, where $\sf N-1$ is a theory that is $1 \space unit$ less than $\sf N$, assuming we have formally defined what a "unit" is in the case?

Answer 1

Well, where do you wish to "prove $\operatorname{Con}(\mathsf N)$"?

If you $\sf N$ satisfies the conditions of Godel's incompleteness theorem, then $\sf N$ cannot prove its own consistency. Period. End of story. On the other hand, we can show that from the assumption "There exists a transitive model of $\sf ZFC$" we can prove the consistency of $\sf ZFC+\operatorname{Con}^n(ZFC)$ for all $n$, and more. So you can find such $\sf N$ and prove its consistency all the same.

On the other hand, working in $\sf PA$, we can still talk about $\sf ZFC$ and an infinite chain of stronger theories (simply take $T_0=\sf ZFC$ and $T_{n+1}=T+\operatorname{Con}(T_n)$, then $T=\bigcup_n T_n$ is a perfectly recursive theory). But nonetheless, $\sf PA$ cannot even prove that $\sf ZFC$ is consistent, let alone any stronger theory.

So again, the issue is that proofs don't live in vacuo. Proofs are born from theories. And unless you tell us what is the theory in which you're working, we cannot tell you if you can prove the consistency of $\sf N$.

Finally, you could---and should---describe these theories as stronger in the sense that each theory proves the consistency of the previous one. But that's more or less all we can say here. Do note that it is possible to prove the consistency of $T$ in a theory $T'$ which is not stronger than $T$, in the sense that while $T'$ proves the consistency of $T$, it does not prove all the statements of $T$. For example, the consistency of $\sf ZFC$ can be proved from $\sf PA+\operatorname{Con}(ZFC)$. Or $\sf PA$ can be proved consistent from $\sf PRA+\operatorname{Con}(PA)$. So again, this becomes a delicate issue to consider.

Answer 2

A slightly more formal way of describing it would be to say that $T_0=\textrm {ZFC}$, $T_{n+1}=T_n\cup \{\operatorname{Con}(T_n)\}$, while $T_\omega=\bigcup_{n\in \omega} T_n$ (which you called ${\sf N}$).

Naively you could think that since $T_\omega$ contains $\operatorname{Con}(T_n)$ for every $n$, it would imply that no finitely many statements in any $T_n$ are contradictory, and hence that $T_\omega$ itself is not contradictory, by compactness, which by incompleteness theorem would imply that $T_\omega$ is contradictory, and hence (by compactness) some $T_n$ is already contradictory.

The same reasoning can be performed if you take $T_0=\textrm{PA}$, and (if you believe in ${\bf N}$), the conclusion is absurd, since each $T_n$ is clearly a part of TA (and so consistent).

I am not a proof theorist, so I do not feel exactly certain, but I think the issue with the reasoning in the second paragraph is the subtlety of the statement of $\operatorname{Con}(T_n)$. You need to understand what it really says: it means that if you interpret it as a statement about the true universe of sets, then it says that $T_n$ has a set model.

But what we really get is that $T_{n+1}$ says about a model $M$ if $M\models T_{n+1}$ is that "$M$ satisfies $T_n$ and in addition, it thinks it has a model of $T_n$ inside". Similarly, when we have some $M\models T_\omega$, it just means that $M$ satisfies $\textrm{ZFC}$, and in addition, it thinks it has models of each $T_n$ inside.

The issue here is with the "thinks". It may very well be that $M$ is wrong about containing the model of some $T_n$ (for example, its membership relation might not at all be the true membership relation), in which case the dominoes fall. Again, one might argue that since $M$ thinks it has a model of each $T_n$, we can apply compactness (in $M$, since it satisfies ZFC!) to find a model of $T_\omega$ inside $M$ (or at least to make $M$ think it has one). But that will not work because to apply compactness, $M$ would need to be aware not only of a model of each of $T_n$ separately, but also of models for all simultaneously.

More precisely, even if we have $m_n\in M$ such that $M\models "m_n\models T_n"$, we cannot say that it implies that $M\models "(\forall n)\, m_n\models T_n"$; indeed, $M$ may not even know the true natural numbers, so it doesn't make much sense to quantify over them! And even if $M$ does know all the natural numbers, it may know more of them than just $\omega$, so even if for all $n$ we have $M\models "m_n\models T_n"$, it may have some nonstandard $n^*$ such that $M\models "m_{n^*}\not\models T_{n^*}"$, in which case actually $M\models \exists n\in {\omega} "m_n\not\models T_n"$ (as witnessed by $n^*$, which $M$ considers to be in $\omega$).

Answer 3

This phenomenon has been well-studied, at least for arithmetic, but the results should extend to ZFC and similar theories.

You can iterate into the transfinite the process of passing from a theory $T$ to the theory $T + \operatorname{Con}(T),$ using notations for recursive ordinals (and taking unions at the limit stages).

The construction has levels going up to (but not including) $\omega_1^{CK},$ the least non-recursive ordinal (the Church-Kleene $\omega_1).$

The whole situation is quite tricky, because the theory that corresponds to a particular notation for a recursive ordinal generally depends on the notation chosen, not just on the ordinal. (The specific issue is that at a limit stage $\lambda,$ the theory you get will depend on the particular cofinal $\omega$-sequence through $\lambda$ that you use, and on the notations chosen for the members of that $\omega$-sequence.)

Somewhat surprisingly, you can find a recursive progression of theories through Kleene's $\mathscr{O}$ (the set of all notations for recursive ordinals), together with a path through $\mathscr{O}$ that is itself recursive in $\mathscr{O},$ such that the union of the theories along this path is true first-order arithmetic.

On the other hand, there is also a wide collection of paths through $\mathscr{O}$ such that the union of theories along the path is incomplete with respect to even $\Pi^0_1$ sentences of arithmetic.

The above is all for theories of arithmetic, but I think everything should work for ZFC and similar theories as well, in terms of asking which sentences of true arithmetic the theories are able to prove. (Recall that the sentence $\operatorname{Con}(T),$ where T is a recursively presented theory, is itself a sentence of arithmetic.)

References:

Alan Turing, Systems of Logic Based on Ordinals, Ph.D. thesis (Princeton Univ.), 1938, which I believe can be found in: Andrew W. Appel, ed., Alan Turing's Systems of Logic: The Princeton Thesis, Princeton University Press, 2012.

S. Feferman, Transfinite Recursive Progressions of Axiomatic Theories, Journal of Symbolic Logic, Vol. 27, No. 3 (Sept. 1962), pp. 259-316, URL: http://www.jstor.org/stable/2964649 in JSTOR.

S. Feferman and C. Spector, Incompleteness Along Paths in Progressions of Theories, Journal of Symbolic Logic, Vol. 27, No. 4 (Dec., 1962), pp. 383-390, URL: http://www.jstor.org/stable/2964544 in JSTOR.