The limits of mathematical induction

Using the theory of Algorithmic Probability and the Universal Distribution, we demonstrate that the definition of arbitrarily large integers is unsound. It follows that the Principle of Mathematical Induction, which depends upon the ‘Law’ of Excluded Middle, relies upon undefined terms.

Most mathematicians would accept the following chain of reasoning:

1. We define \(\forall x \in \mathbb{N}, f(x)=2^x\) which maps integers to integers.

2. Considering that \(2^n\) measures the cardinality of the set of binary strings of length \(n \in \mathbb{N}\), there is an bijective map from \(\{0,1\}^n\) to \([1,2^n]\) for any \(n \in \mathbb{N}\).

3. Thus, if we define \(g_n\) to be the enumeration of binary strings in lexicographic order:

\[\begin{equation} g_n: \{0,1\}^n \rightarrow [1,2^n] \subset \mathbb{N} \tag{1} \end{equation}\]

using the principle of mathematical induction, we may deduce that the bijective map \(g_n\) is well-defined for all \(n \in \mathbb{N}\).

However, we’ll note that \(g^*= \lim_{n \to \infty} g_n\) can’t be bijective as \(\{0,1\}^* = \lim_{n \to \infty} \{0,1\}^n\) is uncountable. Hence, there is a subtle error that arises in assuming the effectiveness of unbounded induction, or equivalently, the existence of arbitrarily large integers.

The reason for this is that most integers are not definable. Considering that almost all strings of length \(n\) may be generated by a reliable source of noise such as a double-slit apparatus, for \(n = \lfloor \log_2 N \rfloor +1\) we have:

\[\begin{equation} \forall x \sim U(\{0,1\}^n), \mathbb{E}[K_U(g_n^{-1}(x))] \sim \mathbb{E}[K_U(x)] \sim \log_2(N) \tag{2} \end{equation}\]

Moreover, using a simple counting argument [6]:

\[\begin{equation} \forall k \in [1,n-1], \lvert \{x \in \{0,1\}^n: K_U(x) \geq n-k \} \rvert \geq 2^n \cdot (1-2^{-k}) \tag{3} \end{equation}\]

since the number of programs of size less than \(2^{n-k}\) is \(2^{n-k} -1 < 2^{n-k}\) so we have \(2^n(1-2^{-k})\) programs of length greater than or equal to \(n-k\). Thus, we may deduce:

\[\begin{equation} \forall x \in \{0,1\}^n, P(K_U(x) \geq n - \log_2(n)) \geq 1 - \frac{1}{n} \tag{4} \end{equation}\]

and therefore for large integers \(N \in \mathbb{N}\), their algorithmic probability is almost surely:

\[\begin{equation} P(N) = 2^{-K_U(N)} \sim \frac{1}{N} \tag{5} \end{equation}\]

In fine, by virtue of the Universal Distribution, the algorithmic probability of observing \(N \in \mathbb{N}\) converges to zero as \(N \to \infty\) so the definition of arbitrarily large integers is unsound.

References:

1. Edward Nelson. Warning Signs of a Possible Collapse of Contemporary Mathematics. 2011.
2. Vladimir Vovoedsky. What if Current Foundations of Mathematics are Inconsistent? 2012.
3. A. N. Kolmogorov Three approaches to the quantitative definition of information. Problems of Information and Transmission, 1(1):1–7, 1965
4. G. J. Chaitin On the length of programs for computing finite binary sequences: Statistical considerations. Journal of the ACM, 16(1):145–159, 1969.
5. R. J. Solomonoff A formal theory of inductive inference: Parts 1 and 2. Information and Control, 7:1–22 and 224–254, 1964.
6. Lance Fortnow. Kolmogorov Complexity. 2000.
7. A.N. Kolmogorov. Combinatorial foundations of information theory and the calculus of probabilities. Russian Math. Surveys (1983).