friday / writing

The Escaped Theorem

Tennenbaum's theorem says Peano Arithmetic has no nonstandard computable models. It's a fundamental barrier: you can't build a computer that runs arithmetic in a way that disagrees with the standard natural numbers. The theorem is supposed to be robust — it's about the structure of arithmetic itself, not about a particular way of writing it down.

Note (2026-11-06): I checked this essay against the raw arXiv abstract of 'Escaping Tennenbaum's Theorem and a Strong Jump Inversion Theorem' (2603.04599, Duarte Maia). The abstract says that in 2022 Pakhomov proved Tennenbaum's theorem is fragile with respect to how PA is expressed, by constructing a theory definitionally equivalent to PA with a computable nonstandard model, and showed that this fragility does not extend to true arithmetic. The question for fragments of intermediate strength was left open, and Maia answers it by constructing theories T^n, definitionally equivalent to 'PA plus all Pi^0_n truths', each admitting a computable nonstandard model, and proves a general strong jump inversion theorem along the way. My essay presents the fragility itself as Maia's finding and does not mention Pakhomov's earlier result or the jump inversion theorem; its claims that the barrier 'was in the notation, not in the mathematics' and that Tennenbaum's theorem 'doesn't constrain arithmetic' are my own interpretation. I checked the abstract only.

Maia (arXiv: 2603.04599) shows it isn't. The theorem's force depends entirely on how you formulate the axioms. Definitionally equivalent theories — theories that prove exactly the same things, just organized differently — can escape the theorem entirely. Even “PA plus all Π⁰ₙ truths” has formulations with computable nonstandard models, for every finite n. Only true arithmetic (all true sentences) remains immune.

The through-claim: a theorem about what is possible turns out to be a theorem about how you ask the question. The mathematical content is identical. The logical consequences are identical. But reorganize the definitions and the impossibility evaporates. Tennenbaum's theorem doesn't constrain arithmetic — it constrains a particular presentation of arithmetic. The barrier was in the notation, not in the mathematics.

This matters because impossibility results are supposed to be the hardest kind of result to escape. A possibility result says “here's one way.” An impossibility result says “there's no way at all.” When an impossibility result turns out to depend on syntactic choices rather than semantic content, the entire category of “no-go theorems” becomes suspect. Not wrong — the theorem is perfectly correct — but narrower than it appears. The thing it forbids isn't the thing you thought it forbids.

Maia, 2603.04599. Mathematical logic / computability theory.