Gödel numbers and arithmetic functions

Gödel numbers may be used to define a programming language, where sets of propositions may be studied using arithmetic functions.

Aidan Rocke https://github.com/AidanRocke
03-10-2022

Everything is a number.-Pythagoras

Let’s suppose we design a formal language, Gödel, using a finite set of symbols $$S \subset \mathbb{N}^*$$.

Using the Unique Factorisation Theorem, any logical proposition $$\{\alpha_i\}_{i=1}^n \in S^n$$ may be uniquely defined as follows:

$$$\mathcal{A} = \prod_{k=1}^n p_k^{\alpha_k} \tag{1}$$$

where $$p_k$$ is the kth prime.

To define a sequence of propositions, such as a proof or program, we may use the Unique Factorisation Theorem a second time:

$$$\zeta = \prod_{j=1}^n p_j^{\mathcal{A}_j} \tag{2}$$$

and to encode a sequence of programs, we may use the Unique Factorisation Theorem yet again:

$$$\mathcal{T} = \prod_{i=1}^n p_i^{\zeta_i} \tag{3}$$$

where $$\mathcal{T}$$ denotes a theory.

One issue we have not yet carefully addressed is how we may distinguish integers of type $$\mathcal{A}, \zeta, \mathcal{T}$$. In order to address this problem, it is necessary and sufficient to define a type hierarchy: $$\mathcal{A} \subset \zeta \subset \mathcal{T}$$.

Thus, we have a formal system which allows us to encode programs, libraries of programs, and mathematical theorems in a uniquely-decodable manner via the Unique Factorisation Theorem. For an explicit decoder, it is sufficient to use an algorithm for integer factorisation.

As a natural consequence, sets of logical propositions may be studied using arithmetic functions.

References:

1. Gödel, K. “Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I.” Monatshefte für Math. u. Physik 38, 173-198, 1931.
2. Gödel, K. On Formally Undecidable Propositions of Principia Mathematica and Related Systems. New York: Dover, 1992.
3. Hardy, G. H.; Wright, E. M. (1979) [1938]. An Introduction to the Theory of Numbers (5th ed.). Oxford: Clarendon Press.

Citation

Rocke (2022, March 10). Kepler Lounge: Gödel numbers and arithmetic functions. Retrieved from keplerlounge.com
@misc{rocke2022gödel,
}