In the previous lecture, we discussed the opposition between two philosophies of mathematical existence: the formalist and the constructivist (or intuitionist).

Today, most mathematicians subscribe without hesitation to the formalist point of view. Interestingly, while the word "constructivist" means exactly what it purports, the word "intuitionist" can be very misleading. The word essentially meant that a mathematical object exists if its existence can be intuited by human mental faculties. But intuition is not only innate. One's intuition can be formed by training, and modern mathematical training has given mathematicians a strong intuitive sense that the objects they are studying, no matter how abstract, possess an objective existence.

Thus, today it may appear difficult to really comprehend and justify the constructivist/intuitionist point of view. However, there is one excellent example of the opposition between the two views which reveals the truth and the value behind the constructivist way of thinking.

This example concerns what is called the law of excluded middle. Formalist mathematicians (and most people) choose to accept this law, which simply states that if A is some mathematical statement, then either A is true, or A is not true.

Formalists accept this law, even when they are incapable of actually proving either A or not A. Constructivists claim a third possibility (the middle), namely that A is undecidable.

This conflict came to a head with the work of Kurt Gödel, who in 1931 proved one of the major results of the 20th century, known as Gödel's Incompleteness Theorem. This theorem states that within any fixed "mathematical universe" of objects, operations and axioms, there will be statements which can be made within the universe, but which are undecidable within the universe, i.e. they may be true in some larger universe, but they cannot be deduced from the axioms of the universe using the objects and operations of the given universe. We will give a more precise explanation of this incredible theorem below.

But first, let us address the question of why formalist mathematicians continue to accept the law of excluded middle on a daily basis, in spite of Gödel's Incompleteness Theorem? Basically, formalists always make the assumption, based on a combination of faith, experience and philosophy, that there exists some bigger, more general universe in which the statement A can be proved either true or false, even if it cannot be proved within the universe where it was first stated. Constructivists object that first of all, we do not know that such a larger universe exists -- and secondly, even if it did, it would then contain its own undecidable statements! Seen from this point of view, the advantage appears to be with the constructivists. Some kind of educated feeling convinces most mathematicians (and most people) to accept the law of excluded middle, but logic indicates that this law may not really hold.

An example of an undecidable statement:  One of the most famous examples of an undecidable statement turns out to be Cantor's cherished continuum hypothesis, stating that there is no set of numbers with cardinal between ℵ₀ and ℵ₁, the cardinality of the reals (in other words, should the notation ℵ₁ refer to the cardinal of some set smaller than the real numbers?). In the 1960's, Paul Cohen proved that the continuum hypothesis is undecidable within the standard axioms of modern set theory, a piece of work which won him the Fields Medal in 1966.

Now we explain the statement of Gödel's Incompleteness theorem. It's proof is based on an argument similar to Cantor's diagonal argument for the uncountability of the reals!

First of all, one must set up the universe of objects to study and the axioms one accepts as a starting point concerning these objects. One could for instance start with the whole numbers as objects, and add symbols with meanings such as "for every", "there exists", "unique", "implies", "equals", and so forth. One then accepts initial axioms such as "if a=b and c=b then a=c". In such a language, one can construct zero by taking as an axiom the statement "there exists a unique number x such that n+x=n for every whole number n". Then we can construct integers by a statement such as "for every whole number n, there exists a unique number x such that x+n=0", so that x=-n, and and the fractions by saying "for every pair of whole numbers p and q, there exists a unique number x such that qx=p", so x=p/q. In this way we set up an axiomatic universe.

Now Gödel argues that we can make a list of all statements that exist in this universe, simply by taking all finite strings of symbols, whether those symbols be objects of the universe (we started with whole numbers here) or quantifiers or operations. Most of these finite strings of symbols will be nonsense, but some of them will be coherent statements, and more importantly, any coherent statement can be written as such a finite string of symbols. By choosing some arbitrary ordering on the list of strings of symbols, we assign a "code number" (positive whole number) to every single string in the list. We write F(S) for the code number of the string S.

Now, in the list of finite strings of symbols that we have just established, there are strings of two types: meaningless strings containing garbled nonsense (by far the most common), and coherent statements that actually make sense. The set of coherent statements can be further split into three types: statements whose truth can be proved from the axioms, statements whose falsehood can be proved from the axioms, and statements which cannot be proved either true or false from the axioms.

What Gödel's theorem asserts is that the last class of statements is never empty in any universe.

To prove this theorem, Gödel proceeds to construct a statement which is not only unprovable either true or false from the axiom, but is actually true in the larger context, seen outside the universe.

Let us explain Gödel's construction. The first thing to do is to pick out from the list of strings above all strings which correspond to coherent statements which are provable true from the axioms. Since each of these statements is just a string of symbols S, it possesses some code number F(S). We make a master list L of the code numbers of all the statements which are "provable true".

Now we go through our complete list of statements and pick out a new, shorter list, taking only those strings of symbols which are actual statements about a variable x. For example, we could take the statement "x=x+0", which is provable true, and the statement "x=x+2", which is provable false.

Write out a list of these statements about x; all possible statements, as long as they are simply coherent in the language. Call the elements of this list A₁(x), A₂(x), A₃(x), etc., and place them vertically in an infinite column. Now, for each of these statements, we make a whole row of new statements by substituting in 1 for x, then 2 for x, then 3 for x, then 4 for x and so on. (So for example, the statement "x=x+0" will generate the row of statements "1=1+0", "2=2+0", "3=3+0", etc., all of which can be proven false.)

A₁(x)      A₁(1)  A₁(2)  A₁(3)  A₁(4)...

A₂(x)      A₂(1)  A₂(2)  A₂(3)  A₂(4)...

A₃(x)      A₃(1)  A₃(2)  A₃(3)  A₃(4)...

A₄(x)      A₄(1)  A₄(2)  A₄(3)  A₄(4)...

Each of the statements in the rows can be written A_i(j) where the number j is substituted for x into the i-th statement A_i(x) about x. Recall that again, since each of the A_i(j) is just a finite string of symbols, it possesses some code number F(A_i(j)). If the statement A_i(j) is provable true, the code number F(A_i(j)) will be on the master list L.

Now we create a new list of statements corresponding to the statements on the diagonal of the table above:

   The code number F(A₁(1)) is not on the master list L
   The code number F(A₂(2)) is not on the master list L
   The code number F(A₃(3)) is not on the master list L
etc.

We can write a single statement about x encapsulating all of the statements on this list, as follows:

"The code number F(A_x(x)) of the statement A_x(x) is not on the master list L."

This is a statement about the variable x, and as such, it lies in the complete list of statements about x which we made above and labeled as A₁(x), A₂(x), A₃(x), A₄(x),...

Therefore, there exists some whole number n such that the statement A_n(x) is exactly this one: "The code number of the statement A_x(x) is not on the master list L." By substituting n for x in this statement, we find ourselves looking at the statement A_n(n) along the diagonal of the table above, and this statement says: "The code number of A_n(n) is not in L", in other words it says "My own code number is not in L", in other words "I am not provable true."

We have to show that this statement is not provable either true or false from the axioms of the universe. If it is provable true, then it is true that it is not provable true, which is clearly a contradiction. But if it is provable to be false, then we have shown it is false that the statement is not provable true, so it must be provable true, contradicting the fact that we have just proved it false. Therefore, neither the truth nor the falsity of this statement can be deduced from the axioms of the system we started with. So the statement is undecidable within the axiom system: it cannot be proved either true or false, thus proving that undecidable statements can be constructed within any system.

Yet note as a final remark that seen from outside the system, there is no difficulty accepting the statement as simply true. It says that it is not provable true within the system, and we know that that is correct: it really is not provable true within the system, therefore we fully agree with the statement. This remark is the basis on which formalists build their conviction that just because statements can be undecidable within a given system, they must all be decidable somewhere, in some bigger system. Even though one has no proof of this, 21st century mathematicians (although not necessarily logicians) mostly work with a consensus agreement to make this assumption once and for all.

Remark. Note that there is a difference with Cantor's diagonal argument here. Cantor made the assumption that he could list all the reals in a countable way, and then found a real number not on the list by using the diagonal. Gödel makes a list of all statements about x, right or wrong, and his list is complete. It is not a question of proving that his list is incomplete. Thus the new statement that he generates about x must be on the list.

Lecture 29: April 2, 2008

After completing the proof of Gödel's Undecidability Theorem, we will talk about logic paradoxes in general, and the historical effects of Russell's paradox in particular.

The first step is to discuss what is actually meant by the word paradox. A paradox is a seeming contradiction, but one can "solve" a paradox by understanding that some of its elements do not behave according to one's intuition, or according to the way one thought they would following their definition, which might have been erroneous. Thus, a paradox can be "solved" when the misapprehension is brought to light, or the definition rectified.

Before turning to Russell's paradox, we consider a simpler paradox, closely related to the notion of countability that we have been studying. This is

The paradox here is the seemingly contradictory assertions that the hotel is full (which it is, to start with) and that there are apparently as many free rooms as one wishes. Mathematically, what this paradox is expressing is that many countable sets which appear to be strictly contained inside each other actually all have the same size. For instance, the set of whole numbers 1,2,3,4,... (the set of full rooms of the hotel at the start) has the same cardinality as the set of numbers 2,3,4,5,... (the full rooms when everyone has moved over one), by the one-to-one matching of n with n+1. Also, the set of whole numbers 1,2,3,4,... (full rooms at the start) has the same cardinality as the set of even numbers 2,4,6,8,... by the one-to-one matching of n with 2n. The final part of the paradox, with the buses, shows that if we take as many separate collections of the whole numbers as there are whole numbers (first collection of the whole numbers, second collection of the whole numbers, third collection of the whole numbers, on to infinity...) then this whole collection of collections has the same cardinality as the set of whole numbers. These assertions appear counterintuitive to us because we are used to visualizing finite sets, and the "paradox" comes from this mistaken intuition. In fact, the mathematical assertions above about countability are all correct.

Lecture 30: April 4, 2008

Let us now introduce

Russell's paradox is extremely simple to state. Some sets, such as the set of all teacups, are not members of themselves. Other sets, such as the set of all non-teacups, are members of themselves. Call the set of all sets that are not members of themselves "R". If R is a member of itself, then by definition, it must not be a member of itself. Similarly, if R is not a member of itself, then by definition it must be one. This contradiction stems from exactly the same principle of self-reference that Gödel used to prove his theorem. Russell solved it by realizing that it is a mistake to use the word "set" for any collection of objects defined by some condition. Clearly, it is all right to define the set of objects described by the condition "is a teacup", whereas the paradox shows that it is not all right to define the set of objects described by the condition "is not a teacup". Yet this second condition certainly defines some kind of "collection", or "class" of objects. If one does not make this distinction, but applies basic set theory indiscriminately to all "collections defined by a condition", one will run into a contradiction.

Russell's solution to the paradox consisted in taking all the statements that set theorists and logicians had hitherto been making lightheartedly about sets -- simple statements such as "this set lies inside that one" or "this element lies inside that set" or "each of these two sets lies inside the union of the two" or "every element in the intersection of these two sets lies inside each of the sets" -- and restricting the manner in which these statements can be made.

He first defined the type of a set as follows: a set is of type 1 if it is a collection of individuals, of type 2 if it is a set of sets, of type 3 if it is a set of sets of sets, etc. Then Russell said that all the above statements will be valid and non-contradictory if each occurrence of the word every "set" in the statement is replaced by "set of type n", where n must be a fixed number throughout the statement. In this way, the statement "The set R is a member of the set R" would be forbidden because the elements of a set always have one type less than the set itself, so no relationship between "The set R" and "a member of the set R" can be made. In this way, Russell founded a set of definitions and axioms for set theory which contains no contradictions.

Note that the constructivist theory of mathematics is another response to Russell's paradox. If only explicitly constructible sets are allowed, then the paradox can never arise because "the set of all non-teacups" is certainly not constructible, even though one may imagine that "the set of all teacups" is.

Now that we have a clear idea of what a paradox is and what it means to "solve" a paradox, we can use this to spot paradoxes in real life. Contrarily to what one might think, this is an extremely important ability leading one to a greatly improved sense of judgment about what one reads, for example, in the newspaper. Newspaper writing can be misleading and manipulatory in so many ways. For instance, we are expected to rejoice upon reading the proud headline "New Arrival Enterprises moves from 50 to 60 percent of market share!", while shaking our heads sadly over the second headline, often on the same page, "Ye Olde Style Mom-and-Pop Store Chain loses 10 percent of the market," as if these two statements were unrelated.

Similarly, have you noticed how often trivial statements are lent weight by prestigious citation:

"It's a worrisome situation -- it could go either way," says Professor Sam Wise, 32, Chisholm Chair of Statistical Analysis at Brill University.

"There are many indications. The temperature could rise or fall in coming days," explains Dr. James Fisher of the Federal Bureau of Meteorology in Melbourne, Australia.

And of course, newspapers have constant recourse to the much-abused "experts say"... (look 7-9 paragraphs from end)

Example 1. Fatalities soar after helmet law lifted.

Paradox: The motorcycle death rate actually decreased after repeal of the helmet law.

Solution: Yes, it's true. If there were X motorcycle riders in Florida in the year 2000 for 259 deaths, the death rate for 2000 was 259/X. In 2004 (the year providing the most recent data), motorcycle registrations have increased by 87 percent, so there are X+(.87)X = (1.87)X motorcycle riders in Florida for 432 deaths. The death rate is 432/(1.87X) = 231/X. The death rate has decreased.

Example 2. The price of melons is a dollar per pound, so a load of melons weighing 1000 pounds is worth 1000 dollars. Freshly harvested melons contain 99 percent water. A farmer packs 1000 pounds of melons for transport to market. During the trip, the melons become somewhat dehydrated, so that they contain only 98 percent water.

Paradox: The retailer tells the farmer that his melons are now worth only half as much.

Solution: It's unexpected, but true. The solid content of a melon is 1 percent, so the solid content of 1000 pounds of melons is 10 pounds. If after transport, this 10 pounds represents not 1 percent of the melons weight, but 2 percent (with 98 percent of the weight being water), we can easily compute the total weight W of the melons after transport: 10 = (.02)W, so W = 10/.02 = 1000/2 = 500.

Example 3. Being a student turns out to be the most dangerous profession. Indeed, recent studies have shown that that students tend to decease at a far younger age than members of any other profession.

Example 4. Aristotle's Wheel Paradox: All circumferences of circles have the same length regardless of diameter!

Example 5. Tie a string tightly around the diameter of the earth (40,000 kilometers, or 40 million meters). Now cut the string and add in a single meter, loosening it slightly. How many razor blades can one slide under the string? How about rabbits?

Lecture 31: April 7, 2008

Gödel's work led to further development of the study of which logical deductions can be made from given axioms in a given formal language. We will start by giving a more detailed explanation of the notion of a formal language in logic, as the universe in which Gödel's Theorem takes place. The importance of the notion of formal language is that computer science is based on it. Gödel's theorem can be summarized as showing that there are undecidable statements within any formal language.

Alan Turing, known as the founder of computer science, was the next to make a fundamental contribution to this theory with incredible, ground-breaking work. His life was dense and exciting, from his seminal discoveries published at the age of 24, his instrumental contributions to cracking the German Enigma code during World War II, his excellence as a runner (he nearly participated in the 1948 Olympics) and his homosexual orientation, which led him to a catastrophic trial (during which instead of admitting guilt he declared that he saw no wrong in his actions). He was sentenced to receive estrogen injections (!) and lost the security clearance which had allowed him to work at code-breaking. These events precipitated a mental crisis, and he committed suicide in 1954 at the age of 41.

Turing's first major contribution to the theory of logic was to define computable quantities in a formal language. In the language of arithmetic, for instance, he defines "computable" numbers as any number whose decimal expansion can be determined by a procedure, or algorithm. As we saw, if a decimal number can be determined in a finite number of steps, then it is simply a rational number. But we saw other numbers which are computable by a finite set of rules, so that one can compute them out as far as one wishes in a finite time, although of course never "out to infinity". One example of this that we saw was the number π, the successive terms of whose decimal expansion can be computed by patiently adding up the terms of the single defining rule

One might think that if one can define a number, then one can set up an algorithm to compute it. Certainly, constructivist thinkers would not accept a definition which did not have this property. But Turing's first major results on this subject were:

* that the class of computable numbers is countable (so, as we saw, very small compared to the whole set of real numbers),

* that one can give a precise definition of a real number which is not computable,

* as a kind of analog of Gödel's theorem, Turing proved that there is no fixed algorithm which will decide, within a given formal language, whether a given proposition is provable or not. So, not only does Gödel's theorem tell us that there will always be undecidable propositions, but Turing's theorem tells us that given a proposition, we may never be able to know whether it is in fact provable (either way) or undecidable.

Yet most mathematicians remain firmly convinced that the problems they are trying to solve are not undecidable.

It is as if Gödel's and Turing's results have not penetrated the psyche of mathematicians, or else (more likely) as if their intuition as to what is or is not actually decidable is stronger than the knowledge provided by formal logic.

What Turing invented to define the notion of "computability" is known as the Turing Machine. It is a computer that he designed completely in his head (real computers were only built some years later). The main properties of the Turing machine are these:

(1) It is extremely simple, consisting only of a "head" which can scan a symbol and print a symbol, that can read symbols (containing the input and the instructions) written on a long tape passing throught the head.

(2) It can read and execute the instructions to perform any (finite) calculation whatsoever. Thus, it was called "universal". Any number which can be computed, can be computed by the UTM.

Before Turing, various "calculation machines" had been invented to perform specific kinds of computations, such as addition or computation of logarithms. These machines were powered by various methods, such as a human being turning a crank, or by a steam engine. To invent such a machine, one has to decide what form the input will take, what form the instructions will take, how the machine can "read" this information, and what the energy source will be to get the machine moving.

A simple example: an addition machine.
Input: 2 sets of marbles weighing 1 gram each
Instructions: no instructions are needed as this machine performs only one type of calculation.
Mechanism: the marbles all fall into a scale which is attached to a needle which points at the total weight.

Turing's contribution was the "universality" of his machine which could carry out any set of computing instructions, and was in fact tantamount to a definition of what it means for a number to be computable.

Experiment with the Virtual Turing Machine.

Lectures 32-33: April 9-11, 2008

The film Breaking the Code about Alan Turing will be shown during these lectures.