Absolutely undecidable statements in Peano arithmetic

Question

Let "Undec(x)" be a predicate in Peano Arithmetic that says "x is the Gödel number of a sentence that is neither provable nor refutable" It is easy to see that this predicate is in fact expressible in Peano arithmetic. We can keep iterating this "Undec" operator. My question is, can anyone exhibit a specific formula F such that F is true, Undec(F) is true, Undec(Undec(F)) is true, Undec(Undec(Undec(F))) is true, and so on.

Answer 1

You can let your $F$ be any PA-undecidable sentence that happens to be true. This is because PA, if it is consistent, can never prove any statement of the form $\mathsf{Undec}(\cdots)$, because that would imply proving the consistency of PA, which the second incompleteness theorem forbids. Therefor each of your $\mathsf{Undec}(\cdots)$ being true implies the truth of the next one.

---

If you don't want to appeal to the second incompleteness theorem, here is a more pedestrian argument which just assumes that some undecidable (and sufficiently simple) sentence exists:

It will be slightly less confusing to speak in terms of decidable rather than "undecidable", so let $\newcommand{\D}{\mathop{\sf D}\nolimits} \D\phi$ mean the arithmetical sentence that asserts that PA either proves or refutes $\phi$. You're then looking for a $\psi$ such that $\psi$, $\D\psi$, $\D\D\psi$ and so forth are all false. (Here, "false" and "true" always mean false and true in the standard integers).

I claim that we can take $\psi$ to be any undecidable $\Sigma^0_1$ sentence -- and the negation of the usual Gödel sentence for PA is exactly such a sentence.

To prove that $\D^n\psi$ is false for all $n\ge 0$, proceed by induction.

$\D^0\psi\equiv\psi$ is false because every true $\Sigma^0_1$ is provable, and we chose $\psi$ to be undecidable.

$\D^1\psi\equiv \D\psi$ is false because we're assuming that $\psi$ is undecidable.

For the induction step, assume for $n\ge 2$ that $\D^{n-1}\psi$ is false, and suppose for a contradiction that $\D^n\psi$ is true. Then, since $\D^{n-1}\psi$ is false but decidable we must have $$ \tag1 PA\vdash \neg\D^{n-1}\psi$$

Now, however, $\D^{n-2}\psi$ is a $\Sigma^0_1$ sentence -- this is by construction for $n=2$, and otherwise because $\D\phi$ is always $\Sigma^0_1$ for every $\phi$. It is well known that for every $\Sigma^0_1$ sentence $\varphi$ we have $PA\vdash \varphi\to[PA\vdash \varphi]$, so in particular $$\tag 2 PA \vdash \D^{n-2} \psi \to \D^{n-1} \psi $$ and by propositional reasoning (1) and (2) combine to $$ PA \vdash \neg\D^{n-2} \psi $$ But this implies that $\D^{n-1}\psi$ is true, which contradicts the induction hypothesis. So $\D^n\psi$ is false, as required.

---

(The idea behind the above proof is pilfered from this answer by Timothy, which took me a long time to grasp due to being in prose. Hopefully the symbolism here makes it easier to keep the metalevels straight.)