Outer Limits of Reason (60 page)

These different actions bring the mattress back to its normal position and express a symmetry of the mattress. There are still more reorientations that one can do with the mattress. If S denotes flipping the mattress clockwise on the short edge, let S′ denote flipping it counterclockwise on the short edge. There will similarly be reorientations L′ and R′. Given these different reorientations, we can combine them by first performing one action and then another. For example, first flip the mattress along the long edge (L) and then perform a rotation (R′). We denote this combined action as LR′.

Consider some reorientations. It is obvious that LL means just flipping it twice along the long edge. This will return the mattress to its original orientation. Similarly, R′R will rotate the mattress counterclockwise and clockwise to bring it back to its original orientation. Slightly less obvious is that LRS will also bring the mattress back to its original orientation. (Do not strain yourself with a heavy mattress just to discover mathematical truths. The facts can easily be proved using a light book.) LRL will not bring the mattress back to its original position. After a few minutes, you can see that

SR´R´RRRLLL´SRLLL

also brings you back to the original position. What about

R´SLR´R´L´SL´RLS´S´L´S´L´SRLS´L′R´LSR?

Given enough time and patience, you can actually sit down and determine if the mattress will go back to its original position. Such a problem, where you are given a sequence of operations or a word in the group and asked whether doing these operations will return you to the original position, is called a
Word Problem
for the group. It turns out that the word problem for this trouble-free group of mattress orientations is decidable. That is, one can sit down and write an algorithm that indicates if the given word gets back to the original orientation. Is this true for other groups?

In the mid-1950s, Russian mathematician Pyotr Novikov (1901–1975) and American mathematician William W. Boone (1920–1983) proved that there are certain groups for which there are no algorithms or computers that can solve their Word Problems. For these groups the Word Problem is undecidable.

 

Once a few problems have been shown to be undecidable, many others can also be shown to be undecidable. To show that a new problem is undecidable, one has to show that an undecidable problem can be transformed into it. One might say that a problem that is harder than a problem that is already known to be harder than the Halting problem is harder than the Halting Problem. In particular, since group theory is at the core of large chunks of modern mathematics and physics, there are a lot of problems within those areas that are undecidable.

Since there are many aspects of modern physics that use group theory in a fundamental way and there are many problems in group theory that are undecidable, there will be many aspects of modern physics that are undecidable. There are decision problems regarding the physical world that no computer could ever answer. One aspect of science is the ability to predict or reveal certain facts about the physical universe. This undecidability makes predictability impossible. However, we must be cautious here. While it is true that many physical theories can be expressed in the language of group theory (and other mathematical structures that have undecidable problems associated with them), if these mathematical structures were the only way of expressing these theories, then we would be right in saying that these physical theories are undecidable. However, there might be other ways of expressing certain physical theories that are not plagued with such undecidable problems.

A case in point is geometry. An elementary school child knows that one needs to do a lot of basic arithmetic to get results in geometry. As we will see in the next section, basic arithmetic has certain limitations. One might conjecture that since there are limitations in basic arithmetic and geometry is expressed using basic arithmetic, there are certain limitations on geometry. However, this is not true! There are ways of expressing basic facts of geometry without using arithmetic and hence geometry does not have these limitations.
¹⁴

Of course, one might object and say that just because a problem is undecidable does not mean that it is beyond human capabilities or beyond reason. Even if a computer cannot solve the problem, there may be other ways of solving it. Perhaps human beings can solve certain problems that a computer cannot. That brings us back to the question of the nature of the human mind. Is it more powerful than a computer or not? Can a human being perform actions that a computer cannot? We have already discussed this question in 
section 6.5
while pondering the Halting Problem. Although we did not come to any firm conclusions in that section, whichever answers one arrives at for the Halting Problem will be the same for the undecidable problems discussed in this section.

9.4  Logic

Logic is the language of reason. Its roots reach back to ancient Greece, where philosophers realized that certain forms of reasoning used common constructions. To understand the structure of reason, they studied these recurring patterns. In the nineteenth century, mathematicians and logicians turned to the structure of proofs in mathematics and studied their patterns. They set up axiom systems to put mathematics on a firm foundation.

An Italian logician named Giuseppe Peano (1858–1932) created a simple axiom system to describe the basic arithmetic of natural numbers. This system came to be known as
Peano Arithmetic
. The axioms of this system are as follows:

1. There is a natural number 0.

2. Every natural number,
a
, has a successor denoted
a
+ 1.

3. There is no natural number whose successor is 0.

4. Distinct natural numbers have distinct successors: if
a
≠
b
, then
a
+ 1 ≠
b
+ 1.

5. If the number 0 has a certain property, and any natural number
a
has the property implies that
a
+
1 also has the property, then every natural number has the property.
¹⁵

Hilbert and others showed that these few axioms describe most of the properties of the natural numbers.

Logicians then went further by using symbols to characterize these logical systems. Axiom 2, for example, can be written as

∀
a
∃
b b
=
a
+ 1

and axiom 4 can be written in symbols as

∀
a
∀
b
(
a
≠
b
) → (
a
+ 1 ≠
b
+ 1).

Using such symbols, every statement and proof in basic arithmetic can then be turned into sequences of symbols. We refer to this conversion of mathematics into symbolic statements as
symbolization
.

Kurt Gödel, impressed by the power of self-reference, showed that mathematics can also have self-reference. By converting the symbolic language into mathematical language, he was able to complete the loop and have mathematical statements talk about themselves (see
figure 9.19
). Gödel's method gives a number to every logical symbol, statement, and proof. Since the logical statements that were about numbers also have numbers, we have mathematics dealing with mathematics, or numbers talking about numbers. The logician Emil Post (1897–1954) summed it up nicely with the statement that “Symbolic Logic may be said to be Mathematics become self-conscious.”
¹⁶

This process of converting logical symbols, statements, and proofs into numbers is called
arithmetization
. While it is not important for us to know exactly how Gödel assigned numbers to logical structures, we can sketch some of his ideas. Since there are a finite number of symbols, we can assign each symbol a number: to every symbol
x
, we can assign a number “
x.
” So for example “→” = 1, “∃” = 2, “V” = 3, etc. Once every symbol is given a number, then a statement, which is a sequence of symbols, can be assigned a unique number by making each symbol an exponent of a prime number and multiplying them. For example,

∀
a
∃
b b
=
a
+ 1

will be assigned the number

2
^“∀”
3
^“
a
”
5
^“∃”
7
^“
b
”
11
^“
b
”
13
^“=”
17
^“
a
”
19
^“+”
21
^“1”

where the base numbers are the prime numbers in order. This number is unique in the sense that distinct formulas will be given distinct numbers. We can take this arithmetization or encoding of symbols to the level of proof. Since a logical proof consists of a sequence of statements, we can assign a unique number to every proof. Moreover, these encodings are “mechanical” in the sense that given a symbol, statement, or proof, we can easily find the number that corresponds to it. Similarly, given a number, we can mechanically find the logical symbol, statement, or proof that corresponds to it.
¹⁷

The number generated for even the smallest proof will be humongous. For larger statements or proofs, these numbers will quickly become greater than the number of particles in the universe. This need not concern us, for we are never going to run out of natural numbers. Besides, our goal is not really to calculate these numbers. The simple idea is that every proof can be given a number and that makes self-reference possible. Exactly which number is generated is uninteresting.

We are dealing with basic arithmetic and we would like to describe certain sets of numbers in a symbolic way. Predicates are like functions that accept numbers as input and then output true or false depending on whether the numbers satisfy that property. For example, the property that determines if a number is even or not can be written as

Even(x) ≡ (∃y)(2y=x).

This predicate is true for
x
if there is a natural number
y
such that 2 times
y
is
x
. There are predicates with two variables. The predicate that determines if
x
divides
y
evenly is given as

Divide(x,y) ≡ (∃z)(xz=y).

That is,
x
divides
y
evenly if a
z
exists such that
x
times
z
equals
y.
One can use predicates to formulate other predicates. For example, the predicate that determines if a number is prime or not is

Prime(x) ≡ x>1 ∧(∀y)(Divide(y,x) → (y=1 ∨ y=x)).

In English, this says that
x
is a prime number if
x
is greater than 1, and if any number divides
x
then that number is either 1 or
x
itself.

The final ingredient that we will need in order to have self-reference is something called a
fixed-point machine
. This is a way of turning any predicate into a self-referential statement. For any predicate
F
(
x
) that depends on one number, there is a logical statement
C
such that
C
is going to be equivalent to
F
(
“C”
). In symbols this is

C ≡ F(“C”).

In words,
C
is a statement that says

“This logical sentence has property
F
(
x
).”

or

“I have property
F
(
x
).”

C
is called a “fixed point” because
F
(
x
) is thought of as a function and generally the output of a function is different from the input. Here the input is
“C”
and the output is equivalent to the input. It is “fixed.” This means that the sentence is going to talk about itself. It would take us too far afield to show exactly how this fixed-point machine works and how
C
is actually constructed. Suffice it to say that the fixed-point machine works very similarly to the diagonalization proofs done in chapters
4
and
6
. All of these are ways of describing self-reference.