Motivation:

Let’s suppose we would like to evaluate the hypothesis, advanced by Bertrand Russell and Alfred North Whitehead in the Principia Mathematica(1910), that mathematics is reducible to logic. How might we evaluate this hypothesis without toiling away(as Russell did) for more than a decade?

By assigning a Gödel number to each logical proposition formulated with respect to a formal system \(F\), a variation of Chaitin’s incompressibility argument leads us to a complexity-bound on the largest Gödel number whose truth-value is decidable. In other words, if a sufficiently complex mathematical proposition is true then it is not provable.

Assigning Gödel numbers to logical propositions:

Given a formal system \(F\) with \(N\) symbols, each symbol may be assigned a unique integer from \(A \subset \mathbb{N}\) where \(|A|=N\). In particular, to encode any logical proposition such as:

\begin{equation} a = (a_1,a_2,…,a_n) \in A^n \end{equation}

we may use the prime factorisation:

\begin{equation} G(a) = \prod_{i=1}^n p_i^{a_i} = 2^{a_1} \cdot 3^{a_2} … \cdot p_n^{a_n} \end{equation}

and by the fundamental theorem of arithmetic, i.e. unique prime factorisation, it is possible to recover the original logical proposition from its Gödel number.

Chaitin’s incompressibility argument:

For concreteness, let’s suppose \(F\) corresponds to Peano Arithmetic(PA). Given that a universal theory of computation may be modelled with \(PA\) and any formal system necessarily has a finite description, \(F\) may be described in a finite number of bits:

\begin{equation} \exists f \in \mathbb{N}, K(F) = f \end{equation}

with respect to prefix-free Kolmogorov Complexity.

Moreover, for any Gödel number \(x \in \mathbb{N}^*\) decidable in \(F\) we may express:

\begin{equation} K(x) \geq \log_2(x) \end{equation}

where \(\log_2(x)\) is the length of the binary encoding of \(x\).

Now, let’s define a large Gödel number \(N >> f\) and perform a stochastic search until we find a Gödel number \(x \in \mathbb{N}\) such that:

\begin{equation} K(x) \geq \log_2(x) \geq N + \text{Cst} \end{equation}

Given that almost all integers are incompressible the search algorithm has converged to (3) almost surely. However, given that the search algorithm \(\mathcal{A}\) is assumed to be consistent with \(F\) it can’t contain more independent axioms than \(F\) so we have:

\begin{equation} K(\mathcal{A}) \leq f \end{equation}

and since \(x\) is defined in terms of \(N\) with respect to \(\mathcal{A}\) it may be encoded using at most \(\log_2(N)\) bits so we have:

\begin{equation} K(x) \leq \log_2(N) + f \end{equation}

which leads us to a contradiction almost surely.

Conclusions:

  1. We can’t have mathematical systems that are both consistent and arbitrarily complex.

  2. If a sufficiently complex proposition emerges from \(F\) then it is not decidable with respect to \(F\).

  3. Formal systems are living systems that must continue to grow organically if they are to remain useful and relevant to the applications of modern physics.

References:

  1. Whitehead, Alfred North and Bertrand Russell (1963). Principia Mathematica. Cambridge: Cambridge University Press
  2. Smoryński, C., 1977, “The incompleteness theorems,” in Handbook of Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland
  3. G. J. Chaitin, Information-theoretic limitations of formal systems, J. Assoc. Comput. Mach. 21 (1974); 403–424 (Reprinted in: [19], 113–128).