Elsamuko, infinity mirror, licensed under Creative Commons Attribution 2.0 Generic, via Wikimedia Commons

Part I: Principia Mathematica

Russell’s paradox, in the language of naïve set theory, is the set S whose elements are all sets that don’t contain themselves as elements. One simply asks the question, is S an element of itself? If it is, by definition it isn’t, and vice versa. We’re faced with the standard liar’s paradox.

There are plenty of other Russellian paradoxes. For example, what is the smallest number requiring at least twelve words to define it? This number is not 52, as “fifty-two” is a two-word definition. It is also not 999,999,999,997, as this number has the four-word definition “one trillion minus three.”

Suppose the number were N. Then, we could take as the definition of N “the smallest number requiring at least twelve words to define it,” which in particular is an eleven-word definition. But this contradicts how we chose N in the first place. Hence there is no smallest number requiring at least twelve words to define it; i.e., all numbers can be defined in eleven words or less. This is clearly impossible in a language such as English because there are only finitely many words, hence only finitely many such definitions.

Is the English language a failure for these paradoxes? Certainly not. As Bertrand Russell and Alfred North Whitehead explain early in Principia Mathematica (henceforth PM),

…the very abstract simplicity of the ideas of this work defeats language. Language can represent complex ideas more easily. The proposition ‘a whale is big’ represents language at its best, giving terse expression to a complicated fact; while the true analysis of ‘one is a number’ leads, in language, to an intolerable prolixity.

Russell-like paradoxes are not well-formed mathematical sentences. In Volume I of PM, Russell & Whitehead lay the groundwork for a completely rigorous logic. It is a tricky, tedious, and difficult pursuit. Russell accurately recognizes that all paradoxes result from “The Vicious-Circle Principle,” i.e. self-reference, and connects it to illegitimate totalities:

The vicious circles in question arise from supposing that a collection of objects may contain members which can only be defined by means of the collection as a whole. Thus, for example, the collection of propositions will be supposed to contain a proposition stating that ‘all propositions are either true or false.’ It would seem, however, that such a statement could not be legitimate unless ‘all propositions’ referred to some already definite collection, which it cannot do if new propositions are created by statements about ‘all propositions.’ We shall, therefore, have to say that statements about ‘all propositions’ are meaningless.

The illegitimate totality at issue in the first of the above paradoxes is clear—there can be no set defined with reference to “all sets.” The second is more subtle—there can be no number defined with reference to “definable.” Russell & Whitehead avoid illegitimate totalities and self-reference by introducing the (now infamous) theory of types.

Suppose we have a universe of objects; we could take our own universe, or the universe of coffee mugs, or any other collection. The objects themselves will be called zeroth-order functions. Any proposition which only discusses zeroth-order functions will be called a first-order function. For example in the universe of men, “All men are mortal” is a first-order function. Similarly, a function which discusses only first-order functions is called a second-order function. For example, in the universe of generals, “Napoleon had all the qualities that make a great general” is second order. We could notate this sentence as follows:

For all P such that P(X) implies Q(X) for all X, we have P(Y).

Where P is a first-order function, Q is greatness, and Y is Napoleon. The variable X ranges over the universe of generals. The above statement is second-order because it discusses first-order functions. Every proposition or function is required to have a well-defined type or order. Thus, the standard Epimenides paradox “I am false” along with Russellian paradoxes are prevented. If these statements had a well-defined type, say N, then the fact that they referred to themselves would imply that they in fact had type N+1, a contradiction. Ideally, there is no way to formulate self-reference in a theory of types…

Part II: Psychohistory

Psychohistory is the ultimate social science: a science which predicts the evolution of societies. In Isaac Asimov’s Foundation, Hari Seldon, the creator of psychohistory, has predicted that the cumbersome, heavily centralized Galactic Empire verges on collapse! In but 60 years, one quintillion people (about 100 million current Earth populations) will descend into barbarism and petty squabbling for 30,000 years, until the Second Galactic Empire restores order to our spiraling spiral.

But! Psychohistory is not a fatalistic science. Knowing perfectly the position of 15 billiard balls is (theoretically) enough information to send the cue ball at just the right angle, sinking them all in a single shot. And unlike billiards, psychohistory gets more accurate with larger populations. Here’s the catch…a pool ball doesn’t choose its motion. It acts without knowledge of its future. Otherwise, when physics told it to go right, it might dodge left. So what must be the basic tenet (BT) of psychohistory? That humans do not know psychohistory. An infinite recursion would be introduced—knowledge of the motion of their own society would lead to their alteration of that motion, ad infinitum.

In his wisdom, Hari Seldon formulates the Plan. Prior to the collapse Seldon forms a small society called the Foundation, living on Terminus, a resource-poor planet on the outskirts of the galaxy. The purported goal: to create an encyclopedia that records all human knowledge. Of course this is simply a charade. The true motive is to create a society perfectly positioned to restore the Galactic Empire to its former glory, not in thirty thousand years, but in a mere one thousand!

The material deficiencies of Terminus lead to its formation of essential trade alliances early after the collapse. Terminus’s scientific development is a resource with which it yields unconventional control: the technicians of its extra-planetary power plants are treated not as scientists but as priests. Like Hari Seldon, the members of the Foundation recognize that certain types of knowledge are dangerous to publicize.

The path of the Foundation lies on a ridge with deep valleys to either side. When faced with a crisis, it is essential that they have one and only one solution. These moments that come to define the history of the Foundation are called “Seldon Crises.” Their singular nature further exhibits the need for the BT: As only one solution exists, knowledge of that solution would be completely corrosive to its implementation.

Hari Seldon knows best the dangers of self-reference. The knowledge of the psychohistorians is undoubtedly of a higher type than the uninformed masses. But need their knowledge be supreme? Perhaps there could be sciences of psychopsychohistory, psychopsychopsychohistory, etc., each one predicting all those multi-psychohistorians of lower order than them, but always unable to predict their own futures.

Part III: Interpreting Gödel-Type Statements

Kurt Gödel’s Incompleteness Theorem was a major blow to the philosophy behind Russell's theory of types. The idea behind Gödel incompleteness is that it is possible to construct a strictly numerical statement G, which when properly interpreted states “I am not provable in this mathematical system.” If G is true, then it is a true but unprovable statement, hence the term incompleteness. If G is false, then it is a false, provable statement, which is called inconsistency. Of course, inconsistency must be avoided at all costs; otherwise, a rigorous notion of “proof” is pointless.

Gödel found a way to encode self-reference without ill-definedness. The idea is to use a “Gödel numbering” to encode the logical structure of a mathematical system numerically. One constructs a correspondence between the formal symbols used in the mathematical language and actual numerical values.

Symbol	Value	Explanation
0	0	the number 0
S	1	the successor function; thus 2 is written SS0
+	2	the addition operation
*	3	the multiplication operation
x	4	the letter used for a variable
'	5	to create more variables, such as x’, x’’, x’’’, etc.
NOT	6	negation
AND	7	and
→	8	implies
=	9	equality

Now, let’s convert a mathematical statement into a number. The law of commutativity of addition may be written x+x' = x'+x. This statement would become the number 424594524 via the above correspondence. Using a Gödel numbering, we can convert all statements of our mathematical language into numbers. Let num(A) denote the numerical conversion of a mathematical statement A. Some numbers will not correspond to sensible mathematical sentences. To say that statement A is implied by statement B, we can find an equivalent numerical statement relating num(A) to num(B).

Think of our theorems in a theorem piggy bank T. At first, T has only the axioms of our mathematical system. Each time we use methods of deduction to prove a statement, that statement is added to T. Define num(T) to be the set of num(A) for all A in T. It starts with the Gödel numbers corresponding to our axioms. Each time we apply specific numerical operations to these numbers, we get a new number, which we throw into num(T).

Consider modus ponens, which states that if we have Q and Q→P, then we have P. Equivalently, say I have two numbers in num(T):

424594524	= num(x+x' = x'+x)	= num(Q)
4245945248421091024	= num(x+x' = x'+x → x+S0 = S0+x)	= num(Q→P)

Then, I am allowed to include

421091024 = num(x+S0 = S0+x) = num(P)
in the bank. Rephrasing modus ponens numerically:

If N and M are in the bank, and there exists a k such that M - N*(10^k) has first digit 8 and k digits, then we can add to the bank the number M – N*10^k – 8*10^(k-1).

Since being a number in the bank can be converted into a strictly numerical problem, there exists some mathematical function THM(x) whose value is 1 whenever x is in the bank and 0 whenever it isn’t. In other words, the statement corresponding to x by reversing the Gödel correspondence is a theorem if and only if THM(x) = 1. But now we do the sickest thing in the book. It’s a trick that Douglas Hofstadter calls arithmoquining in his book Gödel, Escher, Bach. The idea is to construct a sentence analogous to this one:

“, when preceded by itself in quotes, is unprovable.”, when preceded by itself in quotes, is unprovable.

Let P be a statement with one variable x, such as

x+S0 = SS0.

Then, the arithmoquine of num(P), denoted AQ(num(P)), is the Gödel number of the statement gotten by replacing the variable x with num(P). Note that num(P) is a huge number, 42109110, and must be written as follows

SSS…SSS0

Where the number of S’s is 42109110. Thus, AQ(num(P)) is given by the Gödel number of

SSS…SSS0+S0 = SS0.

Of course, this statement is false, because 42109110 + 1 ≠ 2. Now, we are ready to write down G. Consider the statement A with the variable x

THM(AQ(x)) = 0.

When x = num(P), for example, this statement is true, as AQ(num(P)) represents the false statement

SSS…SSS0+S0 = SS0.

Note that A has one variable and so can itself be arithmoquined. Thus, we define G to be

THM(AQ(A))=0.

This G is the holy grail. It is a statement which is true but unprovable. Let’s unravel the complications and see why. G states the following:

The arithmoquine of “The arithmoquine of x is not a theorem” is not a theorem.

While this doesn’t explicitly contain self-reference, it implicitly does, as the arithmoquine of “The arithmoquine of x is not a theorem” is itself G. Hence, G in fact states that G is not a theorem, as desired.

Now, you may feel as though I’ve played a dirty trick on you, and you’d be right. After all, how could a numerical statement, such as 3+7=2, be self-referential? The key is in the fact that we interpret the statement in the first place. We have to notice (and accept) that the numerical statements concerning Gödel numbers in fact have something to say about the propositions to which they correspond. G does not gain its self-referential qualities until someone has read it off the page and understood its meaning.

Theory of types or no, self-reference is an essential component of mathematics, because Gödel numbering is possible in any sufficiently powerful mathematical system. As we saw above, a mathematical system that can describe the arithmetic of the integers must necessarily have unprovable statements. Russell’s dream of a complete, consistent mathematics is impossible. Alas and alack.

---