First Incompleteness Theorem: Does the limit of $\mathsf{T}_n\cup\{\rho_{\mathsf{T}_n}\}$ exist?

168 Views Asked by At

Suppose $\mathsf{T}$ is a consistent, computably axiomatizable theory extending $\mathsf{Q}$, Robinson arithmetic. Then by the First Incompleteness theorem there is a sentence $\rho_\mathsf{T}$ such that $\mathsf{T}\nvdash\rho_\mathsf{T}$ and $\mathsf{T}\nvdash\neg\rho_\mathsf{T}$. Then $\mathsf{T}\cup\{\rho_\mathsf{T}\}$ is consistent and computably axiomatizable, and extends $\mathsf{Q}$.

Writing $\mathsf{T}_0:=\mathsf{T}$, and $\mathsf{T}_{n+1}:=\mathsf{T}_{n}\cup\{\rho_{\mathsf{T}_n}\}$, does the limit exist, i.e. a theory $\mathsf{T}^\prime$ such that $\mathsf{T}_n\subseteq\mathsf{T}^\prime$ for all $n$? If it does, is it consistent and computably axiomatizable? I realize it won't be complete.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, assuming that you construct all $\rho$s in a systematic way such as that described by Gödel's proof, your "limit" $$ T_\omega = T\cup\{\rho_{T_n}\mid n\in \mathbb N\}$$ will be consistent (because every finite subset of it is) and recursively axiomatized. You can then continue the process transfinitely: $$ T_{\omega+1} = T_\omega \cup \{\rho_{T_\omega}\} \\ T_{\omega+2} = T_{\omega+1} \cup \{\rho_{T_{\omega+1}}\} \\ \vdots$$ up to any recursive ordinal you can describe.

By the time you reach the Church-Kleene ordinal, you get $T_{\omega^{\rm CK}_1}$ which (if it exists in a well-defined way, which I think it does, though the details are slightly fuzzy) is still a consistent theory, but this is where the buck stops -- $T_{\omega^{\rm CK}_1}$ won't be recursively axiomatized, so there is no $\rho_{\omega^{\rm CK}_1}$ and no $T_{\omega^{\rm CK}_1+1}$.

If your original $T$ was true (that is, the standard integers form a model for it), then all of the new axioms you add along the way will also be true.