InCognito

If I had a bitcoin for every time that I have heard somebody use Gödel's proof of undecidability to justify some ideologically attractive statement, I would be hodling. Maybe these claims are right, but it always seems like there is magic involved. I have attempted to brush up on his proof several times before, however, at the moment I have the benefit of purpose as the Undecidability Proof is at the center of controversies of interest to me. Maybe, with effort, we can treat Gödel's proof on its own terms, at least, before treating it as a magic wand.

My intention here is to show nothing new. Rather, it is to clarify the structure of Gödel's argument for mortals like myself. I anticipate that my presentation will be incomplete.

What is Undecidability?

Gödel proved that even relatively simple systems of logic contain at least one undecidable statement. An undecidable statement is a statement that is part of the system that cannot be proven or disproven. Gödel presented his proof by assigning a numeric value to each symbol. Any string, a collection of characters, can then be encoded as a Gödel number. For example, consider the statement:

$$(x)$$

Most likely, you want to read this statement as just $x$. However, suppose that symbols are encoded such that:

$$( \rightarrow 3$$

$$x \rightarrow 1$$

$$) \rightarrow 5$$

Applied in a manner developed by Gödel to present his proposal "On Formally Undecidable Propositions", this ordering would be encoded as:

$$2^3 * 3^1 * 5^5$$

Gödel leverages the Fundamental Theorem of Arithmetic, which ensures that there is a one-to-one correspondence between each integer and the product of a unique combination of prime number values. We call this product a Gödel number, $G$. For example, consider the following Gödel numbers and their unique prime products:

$$4: 2^2$$

$$8: 2^3$$

$$12: 2^23^1$$

$$24: 2^33^1$$

You probably remember doing prime factorizations at some point during your primary or secondary education. That is good news because that means that Gödel's proof is at least slightly less complicated than you first imagined.

Gödel selected this system of logic in light of its simplicity. Such statements are realizable in the system but themselves cannot be proven by the axioms that together serve as foundation of a system of logic. Because of Gödel's encoding, every statement in the system can be assigned a Gödel number that is unique to that statement. Entire systems of logic could now be encoded and investigated using the same tools that mathematicians had usd to investigate sets.

Diagonalization

Gödel proves that some statements are undecidable - they can neither be proven true nor proven false using axiomatic reasoning - by diagonalization. Before understanding how Gödel proved this argument, we will want to prove a simpler claim.

Suppose that we wanted to prove that there is not a one-to-one correspondence between real numbers between 0 and 1 and countable integers. We could assert that there is such a correspondence and then find a case that contradicts the assertion. We could count from one to infinity with the hope that every possible combination of decimals between 0 and 1 are captured by these integers. But we would be wrong. Diagonalization shows us why we would be wrong.

The diagonalization argument shows us that if we are to attempt to create a one-to-one correspondence between countable integers and real numbers, such a description is impossible. The way we show this is to construct a table whose size increases by one unit in each direction for every integer we count. For simplicity, we will place the integer counted all the way to the right, thus indicating a relatively small decimal number.

So the first three tables generated counting in binary from a length of 2 would be:

Counting to 2

	1	2
1	0	1
2	1	0

Counting to 3

	1	2	3
1	0	0	1
2	0	1	0
3	0	1	1

Counting to 4

	1	2	3	4
1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0

The problem emerges that, even using a binary counting system, the full set of integers cannot be fit in the space being described where each real number between 0 and 1 is linked to an integer. We are guaranteed to generate a number not in the table if we do the following:

Traveling along the diagonal, we switch every value from a $0$ to a $1$ and from a $1$ to a $0$.

This is going to be true no matter how many integers we count. The reason for this is that the new number fails to match every single other number on at least one digit. The list is not exhaustive.

For each table, indicated by table length, this would result in the following rows that are not in each table:

2. $11$

3. $100$

4. $1101$

This may be easier to envision using lists.

2. $[1,1]$

3. $[1,0,0]$

4. $[1,1,0,1]$

We can see each number simply does not exist in the corresponding table.

Let's use python to show that no matter how big the table (really... especially as the table grows), this manipulation of the diagonal will generate a value that is not in the table. Even if we could conceive of the table's length and width being $\infty$, this must be true. Let's build a few tables in python to get the idea. We will start by counting using the standard counting system with $10$ unique numbers from $0$ to $9$. We will make a table where numbers reading from left to right are 30 digits long. Each number, aligned to the right, will simply count up 1 for every row.

You can see the table is quite boring since the number of digits included simply cannot keep pace with the growing table. It is not difficult to see that if we create a diagonal with marginal changes in values (say add or subtract $1$ to every value in the diagonal, counting from $0$ to $9$ when we subtract $1$ from $0$ and from $9$ to $0$ when we add $1$ to $0$) that the asserted value simply does not exist in the table. The number of real numbers potentiated by this one-to-one correspondence is quite vast compared to the values included.

Now, we could just choose random numbers from $0$ to $10^l$ where $l$ is the value of the tables length and its width. While it is possible that a number is repeated, it is highly unlikely that this occurs. The probability that the same number is chosen twice on this table is $\frac{1}{10^{30}}$ since there are $10$ different numbers for each digit and there are $30$ digits in total.

First, let's check that no number appears twice by using the .duplicated() method from the pandas DataFrame class. Then, we will check that the altered diagonal does not contain a single value from the diagonal in this table.

To be clear, I have not provided Gödel's proof here. Rather, it is the logic that the new value is different from every other value on the diagonal by at least one digit that guarantees that the modified diagonal is a unique value not contained in any row of the table. A similar meaning is intended when Gödel used diagonalization to prove the existence of undecidable statements in axiomatic systems.

The exercise that we have just completed refers to Cantor's proof that real numbers are uncountable. This corresponds with the idea that some infinite sets are larger than other infinite sets. Here we refer to the infinite set of natural numbers. Supposing that this is an infinite set, we find that the potential set of real number generated by the table is far greater than the set of natural numbers that counts upward as the table descends. Diagonalization is used to guarantee that we find at east one value not included in the table.

We can formulate diagonalization argument using a binary counting system. The result still holds. We repeat the exercise below counting in binary:

Gödel's Undecidability Proof

Suppose that instead of using binary values, this represented an exhaustive list of all statements possible in Gödel's system where the number referenced at each pair of row and column would be a Gödel number. That Gödel number encodes the statement at that coordinate in the table. Each Gödel number can be broken down into a product of prime numbers. When like prime numbers are multiplied together, we represent the number of occurrences by the exponent of the base, as described earlier.

Each row is filled with Gödel numbers that themselves can be encoded using prime factorization to create a Gödel number representing a proof. Thus, each row is an encoding of a proof, with each column being a sentence in that proof.

With this, we can now understand the meaning of each row, column, and the values that comprise each row and column pair. Each row is a proof. For a given row, a statement of the proof is encoded as a Gödel number. If a proof does not extend to the end of the table, the Gödel number $\omega$ values are used to indicate that the proof is completed in a prior column. Each statement is again encoded using the fundamental theorem of arithmetic to form a final Gödel number that encodes the entire proof. Moving across the columns from left to right, the base of each subsequent column is raised to the power of the Gödel number of each column moving from $2$ to $3$ to $5$ and a so on for all subsequent prime numbers.

Gödel is able to encode these statements because there is a one-to-one correspondence between each symbol and its value. Since the value of each symbol is encoded as the exponent of a prime number drawn from an ordered list that correlates with the order of the symbols, there is a one-to-one correspondence between each statement and the Gödel number representing that statement. And since there is a one-to-one correspondence between each statement and each Godel number, the statements across the row can again be encoded using each Gödel number as occurred for the encoding of each statement encoding individual symbols. Thus, a single column of Gödel numbers can represent the entire table.

In sum, each column of the table employed by Gödel contains a Gödel number that refers to a statement from a proof. The following table of statements corresponds to the following table of Gödel numbers.

	$S_1$	$S_2$	. . .	$S_{n-1}$	$S_{n}$
$P_1$	$s_{1,1}$	$s_{1,2}$	. . .	$s_{1,n-1}$	$s_{1,n}$
$P_2$	$s_{2,1}$	$s_{2,2}$	. . .	$s_{2,n-1}$	$s_{2,n}$
. . .	. . .	. . .	. . .	. . .	. . .
$P_{n-1}$	$s_{n-1,1}$	$s_{n-1,2}$	. . .	$s_{n-1,n-1}$	$s_{n-1,n}$
$$P_{n}$$	$$s_{n,1}$$	$$s_{n,2}$$	. . .	$$s_{n,n-1}$$	$$s_{n,n}$$

Since each statement corresponds to a Gödel number, we rewrite:

	$S_1$	$S_2$	. . .	$S_{n-1}$	$S_{n}$
$P_1$	$G_{1,1}$	$G_{1,2}$	. . .	$G_{1,n-1}$	$G_{1,n}$
$P_2$	$G_{2,1}$	$G_{2,2}$	. . .	$G_{2,n-1}$	$G_{2,n}$
. . .	. . .	. . .	. . .	. . .	. . .
$P_{n-1}$	$G_{n-1,1}$	$G_{n-1,2}$	. . .	$G_{n-1,n-1}$	$G_{n-1,n}$
$$P_{n}$$	$$G_{n,1}$$	$$G_{n,2}$$	. . .	$$G_{n,n-1}$$	$$G_{n,n}$$

We could, likewise, rewrite the columns as a list of Gödel numbers that corresponds to each proof.

$$G = [G_{P_1},G_{P_2}, . . ., G_{P_{n-1}}, G_{P_{n}}]$$

Now that we understand how the table of encoded proofs is constructed, it is much easier to approach the Gödel's Undecidability Proof. We can now create a new proof through diagonalization. We construct a $G_{P_d}$ by reference to statements in the list $G$. So we add a proof to the list of proofs. To do this, let's start constructing the statement as follows:

$$G_{P_d} \equiv \forall n \vdash(n, G_{P_n})$$

This says that for each n, $G_{P_d}$ asserts that the encoded proof, $G_{P_n}$, is provable for each $n$. But when it reaches the end of the list we are left with the following statement that $G_{P_n}$ asserts that it itself is provable. We can imagine $G_{P_n}$ being a computer program that passes itself as an argument. This results in a recursive problem that has a corollary in the halting problem published in 1936 by Alan Turing.

More devastating, though is the possibility that a complete description of the system would generate an internal contradiction. Drawing on the Diagonalization Lemma, we modify the statement to include the symbol for negation, $\neg$, so that the function now attempts to show that the proof is not provable. To avoid confusion, I have changed the $n$ to $i$ as $i$ will count from an index of 1 to n.

$$G_{P_n} \equiv \forall i \neg \vdash(i, G_{P_i})$$

When applied to $G_{P_n}$ this implies that $G_{P_n}$ proves its own inprovability.

$$G_{P_n} \leftrightarrow \neg \vdash(n, \ulcorner G_{P_n} \urcorner)$$

But if $G_{P_n}$ proves that it is not provable, we would face a contradiction. Instead, we say the statement is undecidable. The system is consistent, but it is incomplete as not all statements in it can be proven.

The Inheritance of Undecidability

This result both limited and structured developments in computer science. To shine a light on how undecidability impacted these developments, I leave you with a passage from Marvin Minsky reflecting on this problem in his book, Computation: Finite and Infinite Machines.

What happens when a machine is confronted with its own description? If this is done to the universal machine, then, as one might expect, the machine must become parallyzed by an infinite regression of interprations cycles -- it can never actually get to compute anything. At first, such phenomena seem entertaining, then annoying, and finally we are forced to conclude that they signal a portentous obstacle to our exploration. We find that certain of the questions we naturally ask about machines cannot be answered, at least by any effective procedure for answering questions. . . .

Which machine computations eventually terminate with a definite result, and which go on forever without any definite conclusion? We show, by some simple technical tricks, that assuming the existence of a machine that can answer this question leads to a contradiction; hence, no such machine can exist. . . .

But so far as our goals here are concerned, this result is indeed very serious; no Turing machine can answer this question. But then, if we accept Turing's thesis, there can be no effective way at all to answer it. That is, we can never aspire to a complete, systematic theory of the conditions under which a computation is sure to terminate. We may be able to decide, for one reason or another, that certain machines will work, and that certain others will not, but we will never be able to put this art on a systematic basis which will work for all machines! I regard this, and similar other 'undecidability' results, to be among the most significant intellectual discoveries of modern times. One can reject its implications only by rejecting Turing's thesis, but there is no apparent prospect of any satisfactory replacement.

With the demonstration of these elementary undecidability results, several new lines of exploration are opened (even if the most desirable line is thus irrevocably closed). We could try to restrict our machines so that their behavior is not quite so complicated; . . . Another line (that we do not follow) is to study, as if by default, the interrelations between various kinds of unsolvability results; this forms much of the subject matter of the modern mathematical 'theory of recursive functions.' Our main activity will be to examine a variety of alternative formulations of effectiveness and through this to try to understand something of the sources of what we know is a hopelessly complex range of behavior. In the course of this we will come to understand better the relation between the modern comptuer (and its programs) on the one hand and these abstract machines (and their descriptions) on the other. (Minsky 1967, 112,113)