Principia Mathematica and Kurt Gödel

Is reality mathematical? The ancient Pythagoreans thought so.

In the last blog, we saw how George Boole in the mid-1800s combined logic and set theory in a new algebraic formulation, which prefigured subsequent advances in statistics and digital computing. Boole was not alone, however, in moving the field of mathematical logic rapidly forward. The German philosopher and mathematician Gottlob Frege at the University of Jena founded a system of symbolic logic that covered some of the same topics as Boole, but served as a more rigorous basis for the merging of mathematics and philosophy. Frege explained, for example, what constitutes a “definition” and what constitutes a “proof,” and he provided a more concise notational system for logical analysis. Guiseppe Peano at the University of Turin contributed axioms supporting the operations of addition and subtraction on natural numbers (positive or non-negative integers).

The most ambitious achievement combining formal logic with mathematics was the 3-volume book, Principia Mathematica, published between 1910 and 1913 by the English mathematicians-cum-philosophers Alfred North Whitehead and Bertrand Russell. Beginning with simple axioms, which they termed primitive premises, the authors carefully worked out theories of hierarchical types, classes, relations, logical products and sums, cardinal arithmetic, mathematical series, and quantity and measurement. Their mathematical derivations, seemingly endless rows of equations, comprise the bulk of Principia Mathematica. They intended to produce a logical treatment of geometry as well, but could not continue as their intellectual energy and partnership were depleted after 10 years of work together. Principia Mathematica was hailed in any case as a monumental achievement, deserving in some subsequent publications the shorthand notation, PM.

If mathematics does not occupy a separate arena of thought, but grows out of basic logic…what might the next discovery be? The subtext of PM was that the world seemed several steps closer to being logically understandable. At the same time, physics, chemistry, and even biology were coming to be viewed as mathematically based. The work of Whitehead and Russell thus appeared to provide a framework, or the beginning of a framework, for the understanding of everything.

Symbols on the pages of PM revealed, line by line, truth-statements beginning with utterly simple axioms and aiming toward ever more complex consequences. Moreover, the operations that unfolded before the eye were driven by simple and automatic rules. A machine might produce such line-by-line derivations as valid as the derivations scribbled by a human hand. Therein was the allure of PM. All nature might be just such a machine, producing quite logically all the sights and sounds of the world before our eyes. PM re-ignited the flame tended so reverently more than 2 millenia earlier by the ancient Pythagoreans – the flaring intuition that reality itself is mathematical.

Enter a 25 year old Austrian, Kurt Gödel, who received his Ph.D. from the University of Vienna in 1930, just a year before publishing the most important research paper in mathematics of the 20th century.

Gödel used the methods of mathematical logic to prove that any system such as PM proceeding from logical axioms cannot be both complete and consistent. “Complete” means that every statement known to be true and expressible within the symbolic language of the system must be provable from the given axioms. “Consistent” means that one cannot derive from the axioms results that are contradictory.

The conclusion provided by Gödel thus undercut any pretension that the methods of PM can ever lead to a final mathematically and logically based theory of knowledge.

How did he do it? Gödel knew that theorems in PM could be self-referencing. Statements of the kind “This theorem is proven from the axioms and steps shown in the sequence above” were common. Importantly PM could also answer questions about the provability of certain theorems. (This is somewhat akin to showing the impossibility of trisecting an angle using only a compass and ruler.) These capabilities of mathematical logic allowed Gödel to use a variation of the Liar’s Paradox from Epimenides of Crete (who said, “Cretans, always liars…”). Gödel found that he could express within the symbolic language of PM the statement “This theorem is not provable” as a theorem.

Let’s consider the statement “This theorem is not provable.” If by some sequence of steps a proof of this statement were claimed, then the statement itself would not be true. If not true, then certainly it is not proven. The same logic applies to any sequence of steps claiming to be a proof. Hence the statement cannot be proven. The impossibility of proving the theorem is a solid result from the logic. Yet this is exactly what the theorem asserts. Thus it is true, but not provable.

As written above, Gödel’s Incompleteness Theorem looks like nothing more than a play on words. “Clever” or “cute,” one might remark, before turning to some more substantial topic.

The genius of Gödel, however, was to express the logic of his self-referencing liar’s theorem in the rigorous symbolic language of the theory of natural numbers described in PM. To appreciate his work, let’s take a very brief look at that language and the brilliant numerical transformation that exposed it to its own severe logic. I am guided here by the clear explanation of Gödel’s theorem given by Ernest Nagel and James Newman.[1]

Here is a formula of elementary logic:

(1)                                      (→ r ) → (( q     (( p V q )   ))

The logical symbol    signifies “if … then,” and the symbol V means “either … or.” The formula therefore can be expanded to read

(2)                                     If (if p then r ), then if [if (if q then )
.                                         then (if (either 
p or q ) then )]

and this can be re-stated

(3)                                       If p implies r, and if q also implies r, then
 .                                         if either p or q is true, then r is true

Of course the formula is valid according to usual assumptions (axioms).

Note that formula (1) is a more succinct statement than either (2) or (3). Logical statements written with symbols as in (1) can be developed and transformed (by substitution rules, symmetry rules, etc.) much more readily than word statements such as (2) or (3).

Gödel took the schematizaton and brevity to a new level in order to prove his Incompleteness Theorem. He showed how any formula such as (1) can be reduced to a single positive integer, its Gödel number, as long as the axioms and variables of the mathematical system are pre-specified.

To understand how the Gödel number is derived for a given formula, the reader is best referred to the wonderful short book by Nagel and Newman. Here is a key paragraph:

Gödel described a formalized calculus, which we shall call “PM,” within which all the customary arithmetical notations can be expressed and familiar arithmetical relations established. The formulas of the calculus are constructed out of a class of elementary signs, which constitute the fundamental vocabulary. A set of primitive formulas (or axioms) are the underpinning, and the theorems of the calculus are formulas derivable from the axioms with the help of a carefully enumerated set of Transformation Rules (or rules of inference).[2]

Nagel and Newman describe the derivation of Gödel numbers by postulating just 12 elementary constant signs (there are more in PM itself), including for our purposes the left parenthesis “(“, the right parenthesis “)”, the sign for “if … then” that we show as “  ”, and the sign for “either … or” that we show as “V”. The Gödel numbers 1 to 12 are assigned in a fixed manner to the constant signs. For the setential or “sentence” variables – p, q, and r – Gödel assigned the square of successive prime numbers greater than 12. Thus p could be signified by 132 = 169, q by 172 = 289, r by 192 = 361, and so on for as many such variables as are needed by the calculus. (Nagel and Newman provide a clear description of the difference between numerical variables, usually designated by x, y, and z, and setential variables p, q, and r. George Boole had noted the necessity of such a distinction. A setential variable can represent a formula or a logical premise; a numerical variable, commonly encountered in ordinary algebra, stands for a number.)

Now we are ready to assign a Gödel number to the formula (1) shown above. Each position in the formula is represented by a prime number beginning with 2. The Gödel number of the corresponding sign at that position is placed in the exponent. Thus the Gödel number for the formula (1) could be

(1)                                      (→ r ) → (( q     (( p V q )   ))

(4)                                     m = 21 × 3169 × 53 × 7369 × 112 × 133 × 171 ×
.                                          19
× 23289 × 293 × 31369 × 372 × 413 × 431
.                                          × 471 × 53169 × 574 × 59289 × 612 × 673 ×
.                                          71369 × 732 × 772

Galaxy_Hubble M100 spiral 2
M100 spiral galaxy as seen by the Hubble Space Telescope

We won’t try to calculate the product of the enormously large number shown above. It is far larger than the number of elementary particles in the universe. Gödel himself wasn’t interested in doing any such calculations. Yet he was careful to demonstrate that it is a distinct number which completely describes the logical formula (1). He further demonstrated that in theory any such number can be reduced to a product of prime numbers raised by discoverable exponents by exploiting the rules according to which Gödel numbers are derived. Thus in our example the number displayed in (4), even as a single gargantuan number, can be translated by factoring back to the formula (1), in theory at least, and that was all the mattered for the purposes of proving the Incompleteness Theorem.

Gödel did not stop with formulas, but went on to describe how his numbering system similarly can be applied to sequences of formulas beginning with primitive formulas (axioms) and leading via transformation rules to a concluding formula. These sequences, of course, are called theorems. Certain theorems, called demonstrations, state whether a particular formula under consideration is provable or not. A Gödel number can also be assigned to such a demonstration.

In the blog titled Emergence of Mathematics, I showed how the set of all rational numbers can be “mapped” onto the set of natural numbers – that is, zero and all the positive integers. This was done to understand the concept of orders of infinity, but it was also an example of mapping one set of mathematical entities onto another, in order to understand the first set of entities better. It should be clear that Gödel’s process was one of mapping the logic that produces mathematics onto natural numbers. Yet the natural numbers are the subject matter of mathematics. Therefore, Gödel’s method was well suited to the task of discerning whether mathematics could describe itself – that is, whether mathematics is complete, consistent, and “self-contained” as a logical system of thought.

One might wonder why completeness and consistency in mathematics ever drew such interest, or came to be regarded as critical in science and philosophy. Remember that mathematics, already the underpinning of physics at the beginning of the 20th century, was being attached at a rapid pace to every other field of science from chemistry to sociology. Much of the success was due to the advances in the field of statistics, owing much to pioneers like George Boole. Decisions about data henceforth would be determined mathematically.

Therefore questions about the completeness and consistency of mathematics, as the language of science, were considered crucial. The German mathematician George Hilbert defined the criteria for proving completeness and consistency. Within certain small, well circumscribed axiomatic systems such as logical tautologies, Hilbert’s criteria were achieved (see Nagel and Newman for an explanation). The monumental effort of Russell and Whitehead’s PM aimed at a complete, consistent description of quantitative mathematics.

Against this background, the outcome of Kurt Gödel’s 1931 research paper was that any axiomatic logical system – mathematics being the prime example – of more than minor complexity must be incomplete (that is, capable of formulating true statements not provable within the system), inconsistent (that is, flawed in the sense of leading logically to two or more contradictory results), or both.

Let’s look once more at the Gödel statement, “This theorem is not provable.” Although the statement is recognizably true, its truth is not shown through the axiomatized system of logic itself. Recognizing that axiomatized system of logic as mathematics, the truth of the Gödel statement can be described as metamathematical. It moves beyond mathematics (beyond that which can be summarized in a Gödel number) and applies to mathematics a criterion from outside.

In physics the concept of Elegance applies to the mathematical description of observed phenomena, when that description can be summarized simply, sometimes within a few key equations relating physical quantities, and yet can be applied to describe a vast array of real events in the physical world. I think of Maxwell’s equations, 4 in number, which can be used to predict the behavior of electromagnetic waves ranging up the frequency scale from infrared heat to radio waves to light to x-rays. Think about how many engineers’ calculations have brought how much benefit from those equations!

I wish there were a word like Elegance to describe what Kurt Gödel’s discovery could eventually mean to science and philosophy. It should be a word that suggests Openness or Going Beyond. There are truths not provable within the parameters of any closed, consistent logical system. Even if the system is addended to encompass a new truth, Gödel’s Incompleteness Theorem can be applied again. One cannot, therefore, construct a closed (complete), consistent system. Our minds are free to roam outside the walls. Gödel has stamped our passport for the journey. It may be a journey to a realm beyond, or a journey to self, or both. We’ll look at one destination next week.

One of the authors of Principia Mathematica, Bertrand Russell, subscribed to the philosophy of positivism, which held that notions of truth and reality should be limited to that which can demonstrated scientifically – that is, demonstrated reproducibly in space-time and among observers.

Because mathematics is the language of science, positivism in some ways revives the ancient Pythagorean creed that reality is mathematical.

Gödel tells us no.

How can reality be mathematical?

Not even math is consistently and completely mathematical.

 

Next post:  The Most Beautiful Word in Any Language

Previous post:  Boolean Thinking

Searching for GSOT outline:  Home


Header image: Left, medieval illuminated manuscript, Graduel d’Aliénor – Entrée dans Jérusalem, Wikimedia Commons Public Domain. Right, Principia Mathematica, by Alfred North Whitehead and Bertrand Russell, University of Michigan Historical Math Collection. M100 spiral galaxy from Hubble Legacy Archive, NASA, ESA, Wikimedia Commons Public Domain.

[1] Nagel E and Newman JR. Gödel’s Proof. New York University Press, New York, revised edition, 2001, Kindle edition.

[2] Ibid., Kindle location 862.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s