A Fibonacci-Based Gödel Numbering: $Δ_0$ Semantics Without Exponentiation

Abstract

We introduce a more efficient G\"odel encoding scheme based on Zeckendorf representations of natural numbers, avoiding the use of unbounded exponentiation and without appealing to the fundamental theorem of arithmetic. The resulting encoding is injective, primitive recursive, and $\Delta_0$-definable in weak arithmetical theories such as $I\Delta_0 + \Omega_1$. This allows for the construction of fixed points and the formalization of incompleteness theorems entirely within bounded arithmetic. Compared to traditional prime-exponent $\Pi$ codings, the Zeckendorf approach yields longer codes but supports simpler substitution mechanisms and more transparent definability properties.

Categories