2
$\begingroup$

I have a few questions about Tarski's theorem on the field of real numbers.

The theorem states that $$\{\mathbb{R}:0, 1, +, ·, <\}$$ with the ordered field axioms augmented with the axioms: "every positive element is a square" and "every odd degree polynomial has a zero" is complete and decidable.

What does the proof of this theorem look like? And, if possible, could someone refer me to a proof of this theorem? I have been unable to find one. I am also wondering, how does this theorem relate to Gödel's incompleteness theorem of $\mathbb{N}$ in PA. More particularly, how is the logic used in Gödel's incompleteness theorem not applicable to the reals with the aforementioned axioms?

Thanks.

$\endgroup$
8
  • 3
    $\begingroup$ dear Zachary, depending on how much background you have, Dave Marker has a very nice exposition of these results; see for example here. the reason that Gödel's incompleteness theorem does not apply here is that this first-order theory is "too weak" to interpret Robinson arithmetic; this latter fact may be viewed as a corollary of Tarski's theorem $\endgroup$
    – Atticus Stonestrom
    Jul 29, 2021 at 3:35
  • 2
    $\begingroup$ For commentary on how PA can be so much more complicated than the theory of the real field (RCF), see my answer here: math.stackexchange.com/a/151010/7062 $\endgroup$
    – Alex Kruckman
    Jul 29, 2021 at 13:47
  • 2
    $\begingroup$ (1/3) dear Zachary, when I say "too weak", I mean in the way indicated by @AlexKruckman's answer linked above. precisely, the theory of $\mathbb{R}$ – also known as RCF – does not admit an interpretation of PA. I know of at least two ways of showing this; the first is to appeal directly to Gödel's theorem, exactly in the way that you do in your question! indeed, if RCF interpreted PA, this would contradict Gödel's theorem, since RCF is complete and decidable by Tarski's theorem $\endgroup$
    – Atticus Stonestrom
    Jul 29, 2021 at 20:43
  • 2
    $\begingroup$ (2/3) there is a more direct way to prove that RCF does not interpret PA, relying on more modern model-theoretic tools. the crux of the argument is that PA has something called the "independence property", which is a kind of combinatorial condition that gives a measure of the expressiveness of a theory. RCF can be shown to not have this property, and hence cannot interpret PA, since a theory with the independence property cannot be interpreted in a theory without it. $\endgroup$
    – Atticus Stonestrom
    Jul 29, 2021 at 20:43
  • 3
    $\begingroup$ (3/3) these facts require a fair amount of machinery to prove, but they do give a direct model-theoretic proof that RCF cannot interpret PA. I personally do not know whether there is a simpler proof of this fact; maybe some of the model theorists on the site might have some insight. as a final point, I'll just point out that QE alone is in general not enough to guarantee that a theory is tame; indeed, every theory admits an expansion that has QE. (this process is sometimes called "Morleyization".) in particular, there are theories with QE that can interpret PA $\endgroup$
    – Atticus Stonestrom
    Jul 29, 2021 at 20:49

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .