3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.