3
$\begingroup$

Set theory in the usual first order axiomatization, as far as I understand, is powerful enough to construct structures that satisfy the axioms of the second order axiomatization for naturals, integers, rationals and reals...

It has been proven that the second order axiomatizations presented above, are all categorical. Thus, for any formula $\phi$: $\Phi_2\models\phi$ or $\Phi_2\models\neg\phi$, where $\Phi_2$ is the set of second order axioms.

Gödel showed that first order logic is semantically complete, that is: $\Phi_1\models \phi$ implies $\Phi_1\vdash\phi$.

Gödel also proved the incompleteness result for first order logic. That is, if the set of axioms is strong enough to prove certain results about natural numbers, then there exists a formula such that: $\Phi_1\nvdash\phi$, $\Phi_1\nvdash\neg\phi$. From the result it's also possible to prove that in second order logic with sufficient axioms, using any proof system, there exists a formula such that if $\Phi_2\models\phi$, then $\Phi_2\nvdash\phi$ (ie. second order logic is never semantically complete). So no matter what, there is a formula that can't be proven. But as far as I understand this all only applies to theories about numbers, not sets.

However, I believe it's common knowledge that the incompleteness result applies to numbers constructed in set theory as well. But as discussed above, set theory has first order axiomatization, that is able to construct structures equivalent to the second order structures... so where/how exactly does it break down, where is the unprovable formula?

$\endgroup$
2
$\begingroup$

The second-order is interpreted within set theory, as a first-order statement.

In the context of $\sf ZFC$, when you say that "the real numbers are the only Dedekind-complete field", which is a second-order statement about the real numbers, you are just saying something very complicated about sets. In the language of set theory, this is now a first-order statement.

More specifically, $\sf ZFC$ itself is a first-order theory. The incompleteness is about $\sf ZFC$, meaning that this incompleteness takes place in the meta-theory of $\sf ZFC$, which can be $\sf ZFC$ itself, or just some arithmetic theory which can internalize logic (e.g. $\sf PA$ or even $\sf PRA$).

For example, $\sf ZFC$ cannot prove its own consistency. You can phrase this in the language of arithmetic, since $\sf ZFC$ satisfies all the hypothesis needed for this (it is countable and recursively enumerable). So $\operatorname{Con}\sf (ZFC)$ is in fact a statement about the natural numbers. And because of the incompleteness theorem holds, $\sf ZFC$ cannot decide on its own whether or not this statement is true or false in the natural numbers.

The crux of the whole thing is that $\sf ZFC$ is a mathematical theory. Even if we often like to think about a fixed universe of $\sf ZFC$, where things are settled (the Riemann Hypothesis is either true or false; the Continuum Hypothesis is either true or false), it does not mean that $\sf ZFC$ can prove all these statements. Our proofs are not inside the mathematical universe, they are outside of that universe, in the meta-universe, which is governed by the meta-theory (which can be again $\sf ZFC$, or it can be an arithmetic theory like $\sf PA$ or even $\sf PRA$). The incompleteness theorem works its spells in the meta-universe, and there, where we do our proofs, we can show that $\sf ZFC$ is incomplete. Even if after this we go back into our universe, and continue to argue as if nothing else exist outside of it.

$\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.