Outer Limits of Reason (67 page)

20
. Rohit Parikh also wrote a very interesting paper on this topic: Parikh 1994.

Chapter 4

1
. From Pascal,
Pensées
(267):
La dernière démarche de la raison est de reconnaître qu'il y a une infinité de choses qui la surpassent, Elle n'est que faible si elle ne va jusqu'à connaître cela.

2
. We will see more of this in 
section 9.1
.

3
. The set (0,1) should not be thought of as the ordered pair of numbers 0 and 1. Rather it denotes the interval of all real numbers between the number 0 and the number 1.

4
. Cantor announced this earth-shattering result in a letter to his friend Richard Dedekind (1831–1916). The letter was dated December 7, 1873, and that date can be taken as the beginning of modern set theory.

5
. In 
section 2.3
, I presented Richard's paradox about English phrases that describe real numbers. It should now be clear that this diagonalization proof was in mind when Richard's paradox was conjured up.

6
. There are many other axiom systems besides Zermelo-Fraenkel set theory, but most of them are known to be just as powerful as Zermelo-Fraenkel set theory. That means that whatever can be proved using Zermelo-Fraenkel set theory can be proved using the other systems and vice versa. Thus, I will only discuss Zermelo-Fraenkel set theory.

7
. Nicholas Bourbaki, “Aujord'hui qu'il est possible, logiquement parlant, de faire deriver toute la mathématique actuelle d'une source unique, la Théorie des Ensembles” (
Théorie des ensembles
(Paris, 1954), 4).

8
. One of the leading number theorists of the last century, André Weil, summed it up nicely: “God exists since mathematics is consistent, and the Devil exists since we cannot prove it.”

9
. I am going to ignore Washington, D.C., and all the anomalies that make that place so detrimental to rational thought.

10
. Note that the infinitesimal mathematical points of one ball can easily be put into correspondence with the infinitesimal mathematical points of the two balls, just as the natural numbers can be put into correspondence with the positive and negative integers. However, if the ball were made out of atoms, such a correspondence would not be possible. There are only a finite number of atoms in any ball and a finite number cannot be put into correspondence with twice that size. Once again, as we did with Zeno's paradox, we must ask whether we are justified in using (infinite) mathematics as a model for the real physical world.

11
. There are many different schools of thought, and I am doing an injustice by lumping them all into one group. Large tomes are written defending nominalism of type
x
against nominalism of type
y
, and so on. However all of these different schools of thought share a dislike for abstract entities.

12
. In fact, this is done in geometry. We will see in 
section 8.2
that Euclid's fifth axiom is independent of the other nine axioms. Rather than restricting themselves to one axiom system, mathematicians study both. They look at the nine axioms with the truth of the fifth axiom and get Euclidean geometry; at the same time, they also study the nine axioms with the falsehood of the fifth axiom and get non-Euclidean geometry. This still leaves us with some open questions. In geometry, the two systems correspond to different backgrounds. Euclidean geometry is the geometry of the flat surface. Non-Euclidean geometry describes curved and twisted surfaces. What is the analogy in set theory? What does the system with choice correspond to? What does the system without choice correspond to? After all, this is set theory where we are talking about collections of objects. How could there be variability about collections of objects? Another possible solution to all our questions is to regress and abandon all axiomatic systems. After all, Cantor did his magnificent work without the benefit of axioms. However, without axioms, we might return to having paradoxes and contradictions. More about this at the end of 
section 9.5
.

13
. We will discuss these questions in more depth in
chapter 8
.

14
. I found this quote from Paul Cohen on the Internet (but could not find a source for it): “The notion of a set is too vague for the continuum hypothesis to have a positive or negative answer.” That means that we cannot come to an answer about the continuum hypothesis because the notion of a set is not well defined. This leads to the following question: What could possibly be vague about the obvious concept of a collection of objects?

Chapter 5

1
. From Al-Daif 2000, 4.

2
. There are 2.5 million people in Brooklyn. Due to the speed and efficiency of the web, phone books have really fallen out of use.

3
. On the island is the tomb of Königsberg's most famous resident, Immanuel Kant.

4
. In fact, only 120 routes have to be checked since it does not matter which city we designate as the first. In other words, for
n
cities, there are only (
n
- 1)! possible routes.

5
. A certain Internet company wanted to use the vastness of this number as their name. Legend has it that they misspelled the word. It's a shame they did not have Google to check their spelling.

6
. We are being a bit wishy-washy about the exact definition of
NP
. To give the real definition would take us a little too far afield. However, most examples of NP problems are, in fact, either 2
ⁿ
or
n
!. It is important to know that NP does not stand for “
N
on
P
olynomial.” Rather, it stands for “
N
ondeterministic
P
olynomial.” This means that the problems can be solved in polynomial time, if a nondeterministic machine performs the task. A nondeterministic machine is essentially a machine that makes a lot of guesses at the same time. Alas, nondeterministic machines do not exist and we cannot use nonexistent machines to solve our problems . . .

7
. We will meet these ideas in depth in 
section 7.2
.

8
. In essence, what Cook and Levin did was to show that for every NP problem and for every input to that problem, one can write down a (very long) logical expression that mimics the actions of the computer finding a solution. If such a solution can be found by the computer, the logical expression will be satisfiable. If no such solution can be found, the logical expression will not be satisfiable.

9
. There are those who believe that neither of these statements can be proved with the axioms of modern mathematics. They believe that the
P
=?
NP
question is “independent” of the axioms of mathematics. I discussed such independent statements in 
section 4.4
and will discuss them again in 
section 9.5
.

10
. I feel obligated to warn you that one of the seven Millennium Problems proposed, the Poincaré conjecture, has already been solved by Grigori Perelman. So there is now more pressure to solve one of the remaining problems. Do it fast!

11
. Since the traveler is not permitted to visit any city twice, we must assume that in her trip from vertex c to e she is flying over vertex a.

12
. I have never seen this approximation algorithm in the literature. This could be because, in general, it is not very good at getting to the solution.

Chapter 6

1
. Mac or Linux users might find these concepts hopelessly abstract. Good for them.

2
. Interestingly enough, Microsoft uses this proposed solution to the Halting Problem. When a program runs for a longish period of time, a “Not Responding” message is put on the top bar of the open window. One is then supposed to “break out” of the alleged infinite loop. Unfortunately, it is not clear that the program is really in an infinite loop. It might simply be going on longer than the Windows operating system expects.

3
. It is easy to see this correspondence between programs and numbers: every program is stored in a computer as a unique series of zeros and ones. This sequence is simply a very large binary number. A typical program might be stored as millions of zeros and ones. The associated number will be astronomically large, but that need not bother us.

4
. Other than 42 being the answer to the ultimate questions of life, the universe, and everything, there is really no reason why this number is special.

5
. A very similar concept was presented in the last chapter. However, since I do not assume knowledge of that chapter, I undertake it again.

6
. Currently, the hardest problem in mathematics is called the
Riemann hypothesis
. It is one of the seven Millennium Problems that the Clay Institute set up in 2000. If you solve this problem, you will get $1,000,000. The problem is somewhat harder to state than the Goldbach conjecture, so I will not delve into it. However, for the cognoscenti, just as there exists a program to look for a counterexample to the Goldbach conjecture, so too can a program exists to systematically search for zeros of the zeta function whose real part is not 1/2.

7
. Formally, they showed that this question is independent of Zermelo-Fraenkel set theory. There is more discussion of such independence in sections 
4.4
and 
9.5
.

8
. Bierce, 1906/2010, 21.

9
. Can human beings determine many facts about their own mind? What about our subconscious? Psychology is the study by human minds about human minds and especially their subconscious. Do psychologists have a deeper insight into themselves than others? One must give a resounding No! to this question.

Chapter 7

1
. Poincaré 2010, 75.

2
. From Alanis Morissette's song
Ironic.

3
. Pierre-Simon Laplace, introduction to
A Philosophical Essay on Probabilities
. The original passage is as follows: “Nous devons donc envisager l'état présent de Fin il vers, comme l'effet de son état antérieur, et comme la cause de celui qui va suivre. Une intelligence qui, pour un instant donné, connaîtrait toutes les forces dont la nature est animée, et la situation respective des êtres qui la composent, si d'ailleurs elle était assez vaste pour soumettre ces données à l'analyze, embrasserait dans la même formule les mouvemens des plus grands corps de l'imivers et ceux du plus léger atome: rien ne serait incertain pour elle, et l'avenir comme le passé, serait présent à ses yeux.”

4
. In fact, there has been some fascinating work done on laboratory coin tossing. See Diaconis, Holmes, and Montgomery 2011.

5
. If complex numbers are unfamiliar, simply consider
c
to be a pair of real numbers <
c
₁
, c
₂
> and
z
to be a pair of real numbers <
z
₁
, z
₂
>. Then iterate by simply taking <
z
₁
, z
₂
> to <
z
₁
²
–
z
₂
²
+
c
₁
, 2
z
₁
z
₂
+
c
₂
>.

6
. Some subtlety is involved when dealing with the exact time and simultaneity.

7
. One of the earliest sources seems to be Lucian of Samosata (125–180 AD) in his
The Sale of Lives.
The
Oxford English Dictionary
under the word crocodilite says it is from ancient Egypt. For more sources, see Von Prantl 1855, 493.

8
. It should be noted that precisely because quantum mechanics is the
only
known system that seems random, there are physicists who believe that even this system must also be deterministic. As we will see, such researchers believe that although it seems random, there are hidden variables that determine the behavior of the system. Some actually provide (not simple) formulas that make predictions about quantum mechanics. Although such researchers include the likes of David Bohm and Albert Einstein, they are not considered part of the orthodoxy of modern physicists who believe that quantum mechanics is, in fact, random. If hidden variables for quantum mechanics do exist, then all known physical systems are deterministic.

There is, however, another side of the story. While I am taking the usual approach in presenting other physical systems besides quantum mechanics as deterministic, that is slightly disingenuous.
All
the laws of physics are—to the extent that they are complete—nondeterministic. The laws of electricity are based on quantum electromagnetism, which is a quantum system and hence nondeterministic. The laws of fluid dynamics are based on quantum mechanics and statistical mechanics. Hence, they too are nondeterministic. Gravity, classical mechanics, and general relativity might seem deterministic, but in fact, they are not real laws because they do not take quantum mechanics into account. Such laws are incomplete. When scientists finally do formulate quantum gravity, it will take quantum mechanics into account and be nondeterministic.

The two paragraphs mean that there are two options: (a) If there are hidden variables for quantum mechanics then all the laws of physics are deterministic. (b) If there are no hidden variables for quantum mechanics, then all the laws of physics are nondeterministic. Is our universe random or not?

9
. This is similar to the discussion about solvable computer problems at the end of 
section 6.3
. We will meet similar arguments about mathematics in sections 
9.1
and 
9.4
.

10
. Chapter 5 of Rescher 2009 actually has several proofs that there are “More Facts Than Truths.” Rescher also says this disparity between what can be expressed and what actually exists shows that nominalism is false. We don't go there.