True, But Unprovable

1. The Smug Defense of the Working Mathematician

Ask an educated non-mathematician about Kurt Gödel’s 1931 Incompleteness Theorems, and you will almost certainly hear a version of the liar paradox dressed up in formal evening wear.

They will explain that Gödel assigned a unique integer to every formal symbol and formula—Gödel numbering—and then used Georg Cantor’s diagonal method to construct an ingenious sentence $G$ that asserts its own unprovability:

If the formal system $\mathcal{F}$ (say, Peano Arithmetic or Zermelo-Fraenkel set theory with Choice, ZFC) is consistent, it cannot prove $G$; for if it did, $G$ would be false, making $\mathcal{F}$ prove a falsehood. But because $G$ asserts that it cannot be proved, and it indeed cannot be proved, $G$ is true. The system is incomplete: there exist truths it cannot reach.

It is an undeniably brilliant piece of 20th-century intellectual judo. But notice what popular culture did with it: it converted Gödel into a philosophical parlor trick. In popular accounts, incompleteness is treated as a linguistic singularity—a snake eating its own tail, an ouroboros manufactured by self-referential trickery.

And that framing gave working mathematicians permission to do something very dangerous: they completely ignored it.

André Weil famously quipped that "God exists since mathematics is consistent, and the Devil exists since we cannot prove it." The Nicolas Bourbaki collective relegated Gödel to a minor historical footnote, preferring to treat axiomatic foundations as an unshakeable bedrock upon which the cathedral of modern geometry and analysis could be constructed without fear.

This defense was comforting. It was convenient. And it was dead wrong.

Incompleteness is not a clever glitch of self-referential grammar. It is a fundamental conservation law of computation. And once you leave the artificial confines of self-referential sentences and look at actual, down-to-earth mathematical objects—polynomial equations with integer coefficients, short computer programs, finite graphs, quantum crystal lattices, and the distribution of prime numbers—you discover something deeply unsettling:

The boundary between what is provable and what is merely true runs straight through the middle of ordinary mathematics. And for a massive class of our most cherished unsolved problems, if they are unprovable, they are guaranteed to be true.

2. The $\Pi^0_1$ Asymmetry: Why Unprovable Means True

To understand what real mathematics loses to Gödel, we must first confront the single most profound structural property in all of mathematical logic: the arithmetical hierarchy asymmetry.

Logicians classify mathematical assertions about natural numbers by the structure of their quantifiers over decidable (primitive recursive) relations:

Here, $P(n)$ is a finite, mechanical, computational check. If you hand a computer an integer $n$, it can execute a deterministic program and answer TRUE or FALSE in a finite number of steps without needing any infinite quantifiers.

Now consider what happens when a $\Pi^0_1$ sentence encounters our axiomatic foundations (ZFC).

The proof of this theorem is stunningly simple—so simple that it fits in four sentences, yet its philosophical consequences are staggering:

1. Suppose $\phi$ were false in the standard integers $\mathbb{N}$.
2. Then there must exist a concrete counterexample: a specific integer $n^* \in \{0, 1, 2, \dots\}$ such that $P(n^*)$ evaluates to FALSE.
3. Because $P$ is a decidable, mechanical computation, evaluating $P(n^*)$ requires only a finite sequence of elementary additions and multiplications. Any formal system capable of basic arithmetic (even weak Robinson arithmetic $\mathcal{Q}$, let alone ZFC) can execute this calculation and formally prove that $\neg P(n^*)$ holds.
4. From $\neg P(n^*)$, the system immediately deduces $\exists n \, \neg P(n)$, which is the formal negation $\neg \phi$. Therefore, ZFC would prove $\neg \phi$ (it would disprove $\phi$).

Run the contrapositive: If ZFC cannot disprove $\phi$, then no counterexample $n^*$ can possibly exist anywhere in the infinite expanse of natural numbers. And if no counterexample exists, the statement $\forall n \, P(n)$ holds universally. It is true.

Pause and absorb what this means.

In standard mathematical pedagogy, we are taught that "unprovable" means an open question floating in limbo—like the Continuum Hypothesis, which can be made true or false depending on which universe of sets you choose to live in.

For $\Pi^0_1$ statements, there is no such relativism. The natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$ are a concrete, rigid structure. For a $\Pi^0_1$ statement, unprovability does not mean undetermined; unprovability implies absolute, objective truth.

If you ever succeed in proving that a $\Pi^0_1$ conjecture cannot be resolved in ZFC, you have not left the problem unsolved. You have just proved that it is true!

3. Hilbert's Tenth Problem & Matiyasevich's Trap

At this point, a skeptic might interject: "Fine, but what actual mathematical problems are $\Pi^0_1$? Isn't this just another backdoor for logicians to smuggle Turing machines into math?"

To see how ordinary, classical mathematics gets swallowed whole by incompleteness, we have to look at Hilbert’s Tenth Problem.

In 1900, at the Paris International Congress of Mathematicians, David Hilbert laid out 23 grand challenges for the coming century. Number 10 was disarmingly concrete:

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

Hilbert wasn't asking about meta-mathematics or proof theory. He was asking the ultimate high-school algebra question: If someone hands you a polynomial equation with whole numbers—like $x^3 + y^3 = z^3$ or $17x^2 y - 4z^5 + 2 = 0$—can you build a computer algorithm that looks at it and tells you whether it has whole-number solutions?

In 1970, after decades of pioneering work by Martin Davis, Hilary Putnam, and Julia Robinson, a 22-year-old Soviet mathematician named Yuri Matiyasevich delivered the fatal blow (the MRDP Theorem):

The implications of MRDP are staggering. A "recursively enumerable set" is anything that can be output by an arbitrary computer program. What Matiyasevich proved is that the execution of any Turing machine—no matter how complex, recursive, or bizarre—can be compressed into a single, static multivariable polynomial equation:

The polynomial has an integer solution $(x_1, \dots, x_m)$ if and only if the computer program halts on input $k$.

Because Alan Turing proved in 1936 that the Halting Problem is undecidable, Hilbert's dream was annihilated: there can never exist a general algorithm to decide whether Diophantine equations have solutions.

Now connect this to Gödel. Consider a Turing machine $M_{\text{ZFC}}$ that systematically searches through all possible proofs in ZFC, looking for a proof that $0 = 1$ (i.e., looking for an inconsistency in our foundations).

By Matiyasevich’s theorem, we can mechanically write down an explicit polynomial:

This is an ordinary polynomial with integer coefficients in a few dozen variables. Now ask the innocent question: Does this equation have any integer solutions?

Notice: There is no self-reference here. There is no snake eating its tail. There is no meta-linguistic quote mark. There is only a fixed polynomial with whole-number coefficients. The claim "This polynomial has no integer roots" is an ordinary $\Pi^0_1$ mathematical statement. It is 100% true. And human mathematics will never be able to prove it from its foundational axioms.

4. The Busy Beaver Wall: 748 States Defeat ZFC

A mathematician clinging to the smug defense might try one last retreat: "Fine, but Matiyasevich's polynomial must be monstrous! It probably has thousands of variables and degrees in the billions. It's a synthetic construct, not something that would ever arise naturally."

How small does a mathematical system have to be before it slips past the event horizon of ZFC?

Enter the Busy Beaver problem, introduced by Tibor Radó in 1962. Consider a deterministic Turing machine with $n$ states and a 2-symbol alphabet $\{0, 1\}$, starting on an all-zero tape. The Busy Beaver function $\text{BB}(n)$ is the maximum number of steps that any such machine can execute before eventually halting.

Look at the bottom row of that table.

In 2016, Adam Yedidia and Scott Aaronson made headlines by constructing an explicit 7,910-state Turing machine whose halting was formally independent of ZFC. Soon after, Stefan O'Rear collapsed that number to 1,919 states.

Then, in 2023, David Riebel and collaborators pushed the frontier to an astonishing extreme: an explicit 748-state Turing machine that halts if and only if ZFC is inconsistent.

The boundary of human deductive certainty is not located at the end of the universe or at infinite cardinals. In computation, it is located at 748 lines of state logic. Beyond that tiny threshold, mathematical truth drifts forever beyond the reach of our axioms.

5. The Arithmetic Giants: Riemann, Goldbach, and Collatz

Now we arrive at the crown jewels of pure mathematics: the great unsolved conjectures of number theory.

Could the Riemann Hypothesis, Goldbach's Conjecture, or the Collatz Conjecture actually be unprovable? And if they are, does Gödel tell us they are true?

Goldbach’s Conjecture: A Pure $\Pi^0_1$ Target

In 1742, Christian Goldbach wrote to Leonhard Euler conjecturing that every even integer greater than 2 can be written as the sum of two primes:

Is this statement $\Pi^0_1$? Yes. For any given even number $2k$, there are only finitely many candidate primes to check (all primes less than $2k$). A computer can exhaustively check them in milliseconds.

Therefore, Goldbach's conjecture is of the form $\forall n \, P(n)$ where $P$ is a finite check.

By the arithmetic asymmetry theorem: If Goldbach's conjecture is unprovable in ZFC, then Goldbach's conjecture is TRUE.

Why might Goldbach be unprovable? Consider the probabilistic heuristic of the primes. By the Prime Number Theorem, the "probability" that a randomly chosen integer $x$ is prime is roughly $1 / \ln x$. For an even integer $N$, the expected number of prime pairs summing to $N$ is approximately:

As $N \to \infty$, this number explodes. For $N = 10^{18}$, there are literally billions of different prime pairs that satisfy the equation. Goldbach's conjecture has been checked numerically up to $4 \times 10^{18}$ without a single exception.

It is entirely conceivable that Goldbach is true simply as an emergent, statistical consequence of the density of primes—a fact of nature without any deeper, compressible algebraic proof. If no counterexample exists simply because the representation count is always positive, but no formal proof can guarantee this for all infinity from the axioms, Goldbach is an unprovable truth.

The Riemann Hypothesis: An Analytic Colossus Made Arithmetic

The Riemann Hypothesis (RH)—that all non-trivial zeros of the Riemann zeta function $\zeta(s)$ lie on the critical line $\text{Re}(s) = 1/2$—is widely regarded as the most important open problem in mathematics. It commands the distribution of primes, the error bounds in arithmetic progressions, and the spectra of quantum chaotic systems.

Because RH is formulated over the continuous complex plane $\mathbb{C}$, mathematicians long assumed it belonged to high-level analysis ($\Pi^0_2$ or higher in the analytical hierarchy).

Then, in 2002, Jeffrey Lagarias proved a breathtaking equivalence that shocked the number theory community:

Here, $\sigma(n) = \sum_{d \mid n} d$ is the sum of divisors of $n$, and $H_n = \sum_{j=1}^n \frac{1}{j}$ is the $n$-th harmonic number.

Notice what Lagarias did: he stripped away complex analysis, analytic continuation, and contour integrals. Equation 7 is a pure, finitary inequality about whole numbers! For any specific $n$, calculating $\sigma(n)$ and $H_n$ is a finite computation.

Let the existential weight of that settle in.

If a mathematician in the 22nd century proves that RH cannot be derived from ZFC, they will not have left the distribution of primes in doubt. They will have proven the Riemann Hypothesis! The non-trivial zeros really do sit on the critical line, all infinity of them—and the reason they do will remain permanently uncapturable by formal deductive proof.

The Collatz Conjecture ($3x + 1$)

Take any positive integer $n$. If it’s even, divide by 2; if it’s odd, multiply by 3 and add 1. Repeat. Does every trajectory eventually crash into the cycle $4 \to 2 \to 1$?

Paul Erdős famously warned: "Mathematics is not yet ready for such problems."

Collatz is harder to classify because it contains an alternation of quantifiers ($\Pi^0_2$): "For every integer $n$, there exists some finite number of steps $k$ such that $T^k(n) = 1$."

However, in 1972, John Conway proved that a natural generalization of the Collatz algorithm (where the multiplier and divisor depend on $n \pmod m$) is computationally universal—it can simulate any Turing machine! Conway proved that determining whether a generalized Collatz sequence ever reaches 1 is undecidable.

While the specific $3x+1$ sequence has not been proven undecidable, Conway's theorem established that Collatz-type dynamical systems live right on the edge of the computational abyss. It is entirely possible that the standard Collatz conjecture has no counterexample (no number escapes to infinity and no other cycle exists), but that proving this fact requires unbounded computational verification that cannot be compressed into a ZFC proof.

6. Natural Combinatorics: Goodstein, Paris-Harrington, & TREE(3)

So far, we have looked at statements whose unprovability is linked to Turing machines or Diophantine equations. But what about purely combinatorial problems—the kind you could explain to a clever high school student?

In the late 1970s and 1980s, mathematical logic experienced an earthquake: the discovery of natural unprovable theorems that make no mention of logic, code, or computation, yet are strictly unprovable within Peano Arithmetic (PA).

Goodstein’s Theorem: The Explosion That Collapses

In 1944, Reuben Goodstein defined a simple arithmetic game. Take a number, say 4, and write it in hereditary base 2 notation (where both bases and exponents are written in base 2):

Now apply two rules:

1. Bump the base: Replace every 2 with 3: $3^{3^1} = 27$.
2. Subtract 1: $27 - 1 = 26$. In hereditary base 3, this is $2 \cdot 3^2 + 2 \cdot 3^1 + 2$.

Now repeat. Bump base 3 to base 4:

Subtract 1: $41$.

As the base bumps from 4 to 5 to 6, the numbers do not just grow—they violently detonate. By base 4, starting from just 4, the number reaches $3 \cdot 2^{402653211}$. By base 100, the number of digits exceeds the number of fundamental particles in the observable universe raised to the power of the universe.

Goodstein’s Theorem asserts: Every Goodstein sequence, no matter what number you start with, eventually terminates at exactly zero.

In 1982, Laurie Kirby and Jeff Paris proved:

Why? Because the proof that the sequence hits zero requires assigning an infinite transfinite ordinal $\epsilon_0$ (Cantor's ordinal) to each term. Because ordinal numbers are well-ordered, every strictly decreasing sequence of ordinals must terminate.

The sequence really does reach zero. It is an undeniable fact of arithmetic. But standard Peano Arithmetic—the foundation of ordinary integer arithmetic—is fundamentally incapable of seeing this truth because the proof requires an inductive strength that exceeds PA's proof-theoretic ceiling.

The Paris-Harrington Theorem & TREE(3)

In 1977, Jeff Paris and Leo Harrington took a foundational result from finite combinatorics—Ramsey's Theorem (which guarantees that within any sufficiently large graph, you can find a clique of monochromatic edges)—and added a trivial-sounding finiteness condition: the size of the subset must be at least as large as its smallest element.

This "strengthened finite Ramsey theorem" is:

• A completely elementary statement about finite sets and colorings.
• 100% mathematically true.
• Strictly unprovable in Peano Arithmetic.

And if you push this into graph theory with Harvey Friedman's work on Kruskal’s Tree Theorem, you get monsters like $\text{TREE}(3)$.

$\text{TREE}(3)$ is defined by a simple game of drawing colored trees. Friedman proved that the game must terminate—a finitary, verifiable truth. But the number of steps before it terminates grows so fast that it cannot even be expressed using Ackermann functions or Conway chained arrows. To prove that the game terminates, you must employ axioms of second-order arithmetic ($\Pi^1_1$-comprehension) that far outstrip the foundations of ordinary arithmetic.

7. Macroscopic Physics: The Spectral Gap Problem

If you think unprovability is confined to discrete integers and trees, modern theoretical physics has an unpleasant surprise for you.

In 2015, Toby Cubitt, David Perez-Garcia, and Michael Wolf published a landmark paper in Nature titled "Undecidability of the Spectral Gap".

The spectral gap determines the core macroscopic properties of matter:

• Gapped: The material is an electrical insulator, has exponentially decaying correlations, and can exhibit topological phases (like fractional quantum Hall states).
• Gapless: The material is a conductor, exhibits power-law correlations, and supports continuous excitations (like photons or phonons).

Cubitt, Perez-Garcia, and Wolf proved that this question is formally undecidable in ZFC:

Given the microscopic local Hamiltonian $h_{ij}$ of a 2D quantum lattice, there is no algorithm that can determine whether the system is gapped or gapless in the thermodynamic limit. Furthermore, for specific, concrete quantum materials, whether they are insulators or conductors is independent of the axioms of ZFC!

Let that sink in. You can write down the exact Schrödinger equation for a crystal lattice. The physics is completely deterministic and continuous. The material sitting in the cryostat either conducts electricity at zero Kelvin or it does not.

The physical reality is definite: it is either gapped or gapless. It is an objective truth of the physical universe.

Yet, starting from the standard axiomatic foundations of mathematics, it is provably impossible to prove which one it is. Gödel's incompleteness is not just haunting prime numbers; it is embedded in the physical phases of matter.

8. Living with the Quasi-Empirical Future

Where does this leave us?

For over two millennia, from Euclid to Hilbert, mathematicians operated under a profound metaphysical assumption: Truth and Proof are co-extensive. What is true in mathematics is precisely that which can be proven from first principles.

Gödel shattered that equation forever. But the full scope of that fracture is only now becoming clear:

As the late Gregory Chaitin observed through the lens of Algorithmic Information Theory, mathematical truth is not a neat, fully compressible crystalline web. It is riddled with incompressible complexity.

A formal axiomatic system like ZFC has a finite information content—its axioms and inference rules can be encoded in a few thousand bits of software. A statement like the Riemann Hypothesis or Goldbach’s Conjecture makes an assertion about an infinite sequence of integers.

Why should every infinite truth be compressibly derivable from a few thousand bits of foundational axioms?

The answer is: there is no reason at all. The assumption that every true arithmetic fact must have a finite deductive trail leading back to Zermelo and Fraenkel is sheer aesthetic hubris.

And this forces a profound reassessment of how mathematics is actually practiced.

When number theorists test the Riemann Hypothesis to the first 10 trillion non-trivial zeros, or when they verify Goldbach’s conjecture to $4 \times 10^{18}$, they are not merely "killing time while waiting for a proof."

They are acting as quasi-empirical scientists.

Just as a physicist measures the fine-structure constant $\alpha \approx 1/137.036$ without knowing the grand unified theory that generates it, the modern mathematician must confront the real possibility that some of our greatest conjectures are arithmetic facts of nature: true propositions that hold across all infinity, but whose truth is an irreducible brute fact that no formal proof will ever capture.

The snake is not eating its tail. The snake has escaped the terrarium. And mathematics is vastly larger than proof will ever be.