# Proof-theoretic ordinals and the Axioms of Replacement

According to this Wiki article, ZFC-R (ZFC without the Axioms of Replacement) cannot construct $\omega \cdot 2$. It also claims that $V_{\omega\cdot 2}$ is a model of ZFC-R and is sufficient to do basically all of second-order arithmetic.

(It also seems to refer to ZFC-R as Z, which isn't clear to me that they're equivalent.)

However, in this article it says that the proof-theoretic ordinal of a theory is the smallest recursive ordinal that the theory can't prove to be well-founded. It then further claims that the proof-theoretical ordinal of second-order arithmetic is (currently) undescribably large--far larger than $\omega \cdot 2$. Since ZFC-R can do second-order arithmetic, its proof-theoretical ordinal must be at least as large.

So how is it that ZFC-R can prove that $\omega\cdot 2$ is well-founded, but apparently cannot prove it exists?

You need to distinguish between well ordered sets and von Neumann ordinals. While $\sf ZFC-R$ cannot prove the existence of von Neumann ordinals $\geq\omega+\omega$, it can prove the existence of many well ordered sets. In fact, in $V_{\omega+\omega}$ any order type below $\beth_\omega$.
(To wit, if $M$ is any countable transitive model of $\sf ZFC-R$, then it contains only countably many ordinals, and countably many sets. So only countably many order types exist there. And we could ask what is the least order type of a set that provably exists in a transitive model of $\sf ZFC-R$. This has to be a countable ordinal.)
• @NoahSchweber So, if I understand you correctly, ZFC-R can prove that sets with the order type $\omega\cdot 2$ exist, but not that the specific set $\{\omega + n: n\in N\}$ exists? – eyeballfrog Jan 11 '17 at 20:50
• @eyeballfrog Exactly. For instance, the set $$\{(m, n): \mbox{m is even and n is odd, or m and n have the same parity and m<n}\}$$ is a linear order with ordertype $\omega+\omega$, and ZFC-R proves that it exists. – Noah Schweber Jan 11 '17 at 21:06