It seems very confusing that real closed field (which also can be used as the theory of real number) is decidable, while Peano arithmetic, which seems to be a subset of real closed field is undecidable.
What am I getting wrong?
Logic – Tarski’s Decidability Proof on Real Closed Field and Peano Arithmetic
logicmodel-theory
Related Solutions
Essentially, yes, but I believe the undecidability of Peano arithmetic (henceforth, PA) follows from the way the proof of Gödel's incompleteness theorem goes, rather than being a consequence of the fact that PA is incomplete. The proof (outlined below) starts by showing that PA can talk about computable relations, and goes on to show from this how you can construct an unprovable sentence. However, we can take a different approach to show that PA is undecidable: if PA can talk about computable relations, then you can formulate a sentence in the language of PA that is true if and only if a given algorithm halts / does not halt. (Briefly: An algorithm is the same thing as a computable partial function, and an algorithm halts on some input if and only if the corresponding partial function is defined on that input.) So if an algorithm can decide whether arbitrary sentences in PA are provable or not, we have an algorithm which solves the halting problem... but there are nonesuch. So the key point is that PA is rich enough to talk about computation. An essential ingredient for talking about computation is the ability to encode a pair of numbers as a number and the ability to recover the original pair from the encoding. It's not immediately clear to me that $+$ is insufficient to do this, but it's certainly plausible that you need at least two binary operations.
Here is a sketch of the proof of Gödel's first incompleteness theorem: First let's select a sufficiently powerful theory $T$, e.g. PA, and assume that it is a consistent theory, i.e. does not prove a contradiction.
- We show that we can encode formulae and proofs in the models of $T$.
- We show that $T$ is powerful enough to talk about computable relations.
- We show that there is a computable relation $\mathrm{Prf}(m, n)$ which holds if and only if $m$ encodes a valid proof of the sentence encoded by $n$.
- The above shows that there is a computable relation $Q(m, n)$ which holds if and only if $n$ encodes a formula $F(-)$ with one free variable and $m$ does not encode a valid proof of $F(n)$.
- So we can define a formula $P(x)$ by $\forall m. Q(m, x)$. This means $P(x)$ holds if and only if there is no valid proof of $F(x)$, assuming $x$ encodes a formula $F(-)$ with one free variable.
- But $P(-)$ is a formula with one free variable, and it can be encoded by some number $n$. So is the sentence $P(n)$ provable or not? Suppose it were. Then, that means $P(n)$ is true, so the theory asserts that there is no valid proof of $P(n)$ — a contradiction.
- So we are forced to conclude that the sentence $P(n)$ is not provable. This is the Gödel sentence which we wished to prove the existence of, so we are done.
Note I haven't said anything about whether $P(n)$ is actually true. It turns out there is some subtlety here. Gödel's completeness theorem tells us that everything that can be proven in a first-order theory is true in every model of that theory and that every sentence which is true in every model of a first-order theory can be proven from the axioms of that theory. With some stronger consistency assumptions, we can also show that $\lnot P(n)$ is also not provable in PA, and this means that there are models of PA where $P(n)$ is true and models where it is false.
The key point is that the phrases "$n$ encodes a formula ..." and "$m$ encodes a valid proof of ..." are strictly outside the theory. The interpretation of a particular number as a formula or proof is defined externally, and we only define it for "standard" numbers. The upshot of this is that in a model $\mathcal{M}$ of PA where $P(n)$ is false, there is some non-standard number $m \in \mathcal{M}$ which $\mathcal{M}$ "believes" is a valid proof of $P(n)$, but because it's non-standard, we cannot translate it into a real proof.
Your summary seems accurate, with one exception: The theory of algebraically closed fields of characteristic 0 is complete. Perhaps you meant the theory of algebraically closed fields, without specifying the characteristic?
Best Answer
As William pointed out in his answer, Peano Arithmetic is a certain first-order theory which describes properties of $\mathbb{N}$, the natural numbers (that is, $\mathbb{N}\models\text{PA}$). However, it is incomplete (as shown by Gödel), and hence it is not equal to the complete theory of the natural numbers, denoted $\text{Th}(\mathbb{N})$, which consists of all first-order statements true of $\mathbb{N}$. The situation is different with the theory of real closed fields - this is a complete theory, and $\mathbb{R}\models \text{RCF}$, so $\text{RCF} = \text{Th}(\mathbb{R})$.
Your main confusion, however, seems to be about how $\text{Th}(\mathbb{N})$ can be so much more complicated than $\text{Th}(\mathbb{R})$, despite the fact that $\mathbb{N}\subset \mathbb{R}$. If $\text{Th}(\mathbb{R})$ is decidable, why can't we use the decision procedure to decide all questions about $\mathbb{N}$?
This phenomenon is possible because there is no single first-order formula (in our language $\{0,1,+,\cdot\}$) which picks out the natural numbers as a subset of the reals. To decide whether a sentence is true about $\mathbb{N}$ by asking a question about $\mathbb{R}$, we would have to somehow ensure that all quantifiers talk only about the integers.
To illustrate the difficulty, consider the sentence $\phi:\forall x\,\exists y\, (y+y = x)$. $\phi$ is certainly false in $\mathbb{N}$. But to use the decidability of $\text{Th}(\mathbb{R})$ to see this, we would need to be able to express that for all natural numbers $x$ there is a natural number $y$ such that $y+y = x$, which we cannot do. Allowing the variables to range over $\mathbb{R}$, $\phi$ is true.
Intuitively, it is questions about divisibility like this one which make $\text{Th}(\mathbb{N})$ so much more complicated than $\text{Th}(\mathbb{R})$. The formula $\psi(x,y):\exists z (x = y\cdot z)$, expressing that $y|x$, gives access to all the complexity of the prime numbers. By contrast, the reals are extremely homogeneous: $\psi(x,y)$ is true of a pair of reals $(a,b)$ whenever $b\neq 0$.