xu-2024-proof-by-cantor-diagonalization

IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-s2-training-and-validation-iteration.md

Created 2026-08-24T17:11:29+00:00

Xu et al. (2024) prove hallucination inevitability via Cantor's diagonalization argument—constructing a ground-truth function f by flipping diagonal entries of the LLM output table (f(s_k) = Δ(ĥ_k(s_k)))—rather than via probabilistic or complexity lower-bound methods.

Summary

Xu et al. (2024) show that LLM hallucination is mathematically unavoidable, not just a training or data problem. They prove this constructively: for any table of model answers across all possible prompts, you can always build a correct-answer function that forces the model to be wrong on at least one prompt, meaning no amount of further training can eliminate hallucination in principle.