The Self-Reference Trap: What AI cannot say about itself

A note before we begin

This is a series about mathematical limits. It is not a critique of AI, and not a defensive piece by a research team that feels threatened by it, God forbid! Quite the opposite. As a Cyber Researcher and Head of Research at Pentera, I can say that embracing AI has been a major boon for the pace of our research and development. We use it every working day: to traverse vulnerability corpora, draft exploit candidates, accelerate reverse engineering, summarise vendor advisories and open-source noise, surface weak signals across graphs, and reason over attack chains at machine speed. The systems we build at Pentera lean on AI in ways that would have been science fiction in 2023.

So this is not an anti-AI series. It is an attempt to answer a different question: where, exactly, does the tool stop being a tool?

The answer turns out to be unusually clean. There are nine well-established mathematical theorems – some of them nearly a century old, some published in the last eighteen months – that together describe the ceiling. Above that ceiling lives the fantasy of an all-knowing machine mind. Below it lives the powerful, indispensable, but mathematically non-final tool that AI actually is. Each theorem closes one specific door in the fantasy.

This first chapter covers the four theorems about self-reference. Chapters 2-4 will cover, in order, behavioural undecidability, the limits of learning, and the impossibility of universal value aggregation. None of them argues that AI is weak. All of them clarify what AI can and cannot be.

Why self-reference is the first wall

Many of the deepest results in modern logic turn on one trick: a formal system constructing, inside itself, a sentence that talks about its own provability or its own truth. The same trick – the diagonal – appears in Cantor’s proof that the reals are uncountable, in Russell’s paradox, in the halting problem, and in the four theorems we walk through below.

Self-reference matters because a lot of what we hope AI will do for us one day quietly requires it. We want a model that can audit itself, score its own confidence, prove its own consistency, and tell us when it is wrong. We want, in short, a system that contains its own truth predicate. The math of the next four sections says that this aspiration is structurally out of reach – mathematically impossible in the strong sense, not merely difficult.

Gödel’s first incompleteness theorem (1931)

What the theorem says.

Any consistent, recursively axiomatizable formal system strong enough to express elementary arithmetic contains true statements that cannot be proved within that system.

Three qualifications, each load-bearing:

• Consistent means the system doesn’t prove a contradiction. An inconsistent system proves everything, so the result would be trivial for it.
• Recursively axiomatizable means there is an algorithm that can list the axioms. This is what makes the system effective – the kind of formal system a computer could implement.
• Strong enough to express elementary arithmetic means the system can talk about natural numbers, addition, and multiplication. The bar is low: Robinson arithmetic Q, which is much weaker than Peano arithmetic, already crosses it.

Why it is true.

Gödel’s proof is one of the most famous diagonal arguments in mathematics. He showed how to construct, inside the system, a sentence that is provably equivalent to “I am not provable in this system.” Call it G_T. Then:

• If the system proves G_T, the system proves its own assertion that G_T is not provable. So the system contradicts itself.
• If the system is consistent, it cannot prove G_T. So G_T is unprovable.
• But G_T says “I am not provable.” Since G_T is in fact not provable, G_T is true.

Conclusion: G_T is true and unprovable in the system. The natural reply is: fine, let’s extend the system. Add G_T as a new axiom and now we can prove it. But the extended system is itself a new formal system – call it T’. By the same construction, T’ has its own unprovable sentence G_T‘. And so on, forever. There is no countable ordinal at which the ladder closes. Solomon Feferman proved in 1962 that even iterating the construction along all recursive ordinals does not capture all arithmetic truth.

What it rules out for AI.

The dream of a single, fixed AI system that constitutes a complete theory of any domain rich enough to encode arithmetic. There will always be true claims, expressible in the model’s own representation, that the model cannot derive. Climbing the ladder of stronger and stronger models is not the same as reaching the top.

What it does not rule out: anything we actually do with AI today. AI systems are not, and do not pretend to be, complete formal theories of their domains. They are heuristic engines that work astonishingly well on the part of the domain where they have evidence. The point is not that we are doing anything wrong. The point is that we should not expect a future model to be different in kind on this dimension.

Gödel’s second incompleteness theorem (1931)

What the theorem says.

The statement that the system is consistent can itself be encoded as an arithmetic sentence – call it Con(T). Gödel showed that in the same kind of system, Con(T) is unprovable. Spelled out: no consistent formal system strong enough to express arithmetic can prove its own consistency from within itself.

Why it is true.

The proof reuses the first theorem. Working inside T, one can derive the conditional Con(T) → G_T. If T proved Con(T), then T would prove G_T as well. But Gödel 1 says T cannot prove G_T. Therefore T cannot prove Con(T). The argument depends on three formalised facts about the system’s own provability predicate – the Hilbert-Bernays-Löb derivability conditions – but the punch line survives every reasonable choice of system.

What it rules out for AI.

Self-validation. An AI can run internal checks, score its own outputs, generate explanations, audit its own reasoning, and produce confidence intervals. None of those activities constitutes a proof of correctness from inside the same formal system. They are heuristic activities relative to a metalanguage that lives outside the system.

To validate T you need a stronger metasystem M. But then the consistency of M becomes the next question. The regress is infinite from the inside. The standard AI-safety cliché that a system saying it is safe is not thereby safe is folk-mathematics for Gödel’s second theorem.

“Self-attestation is not validation. It never was.”

Löb’s theorem (1955)

What the theorem says.

Martin Hugo Löb sharpened the picture even further. Writing □_T φ for “φ is provable in T,” Löb’s theorem says:

In words: the only sentences for which the system can prove the reflection principle “if I prove this, it is true” are the sentences it already proves. There is no non-trivial formal self-trust.

Why it is true.

The proof uses a Gödel-style fixed point. Construct, inside T, a sentence ψ that is provably equivalent to (◻ψ → φ). Manipulating the derivability conditions, one shows that T must prove ψ, hence T must prove ◻ψ, hence T must prove φ. The whole argument is one of the cleanest in provability logic; it is the foundation of the modal logic GL, in which Gödel-Löb-style reasoning is its own algebra.

What it rules out for AI.

Reflective self-improvement on a formal basis. An AI agent that wants to reason about whether its own future computations should be trusted faces what the alignment-theory community has dubbed the Löbian obstacle (Yudkowsky and Herreshoff, 2013). The system cannot consistently endorse “if my future self proves it, it is true” without already proving it. This is one of the main reasons that self-modifying AI architectures are mathematically delicate, and is an active area of research that has produced things like logical induction (Garrabrant et al., 2018) and Löb-safe modal logics (Seth Ahrenbach, arXiv:2408.09590v2 [cs.LO] 21 Aug 2024).

The fact that Löb’s theorem is so deep and so old is one of the more sobering features of AI safety. We are not stumbling on a new mathematical surprise. We are walking into a wall that was charted in 1955.

Tarski’s undefinability theorem (1936)

What the theorem says.

The previous three theorems are about provability. Tarski’s is about truth. The statement: in a sufficiently expressive formal language, the predicate “is true” cannot itself be defined within that language.

Why it is true.

The proof is again diagonal. If a formula True(x) existed in the system such that True(⌜φ⌝) were equivalent to φ for every sentence φ, then the diagonal lemma would produce a Liar sentence λ such that the system proves λ ↔ ¬True(⌜λ⌝). Substituting, we get λ ↔ ¬λ – a contradiction. So no such formula exists. The corollary: truth for a language must live in a strictly stronger metalanguage. The hierarchy is unavoidable. Saul Kripke’s theory of truth (1975) and various paraconsistent and partial-fixed-point responses give partial workarounds, but they all amount to relaxing one of the conditions Tarski’s theorem assumes. The basic inseparability of object-language and truth-language remains.

What it rules out for AI.

Internal truth. For a large language model, the object language is the training corpus. The probabilities the model assigns to strings are statistics about that corpus. They are not truths about the world. A fluent sentence can be false. A high-probability sentence can be wrong. A well-structured explanation can be confidently misleading. The model has no internal mechanism for separating “true” from “likely” – and the structural reason, the one Tarski’s theorem makes precise for formal languages, is that no sufficiently expressive system can carry its own truth predicate. The metalanguage of truth has to be supplied from outside, by humans, by tests, by reality.

Hallucination is the operational consequence. No purely internal mechanism in the model can separate “true” from “likely” – which is why every real reduction in hallucination, from RAG to tool use to external evaluators, has to come from outside the model. Scale alone, on the inside, runs into a wall that Tarski charted ninety years ago.

The thread

Across these four theorems the same structural fact appears: a formal system that tries to be its own ultimate judge runs into one of the diagonal walls. Gödel 1 says: it cannot be its own complete theory. Gödel 2 says: it cannot be its own consistency proof. Löb says: it cannot non-trivially trust itself. Tarski says: it cannot be its own truth predicate.

The combined message is not that AI is weak. The combined message is that AI is non-final on the dimension of self-reference. We will not build a model that is the final theory, the final auditor, the final reflector, or the final truth predicate. We can build, and we do build, extraordinarily powerful tools that operate inside frames whose adequacy is judged from outside.

What’s next

Next time I want to look at a different wall – the one Turing and Rice built around the question of what a program does, and what the alignment community has been doing with it in the last three years.