# Logic, Rationality and Common Sense (1)

**Logic**

How can we know things for sure? How can we talk about things in a precise way? What are the properties of the language that we use to talk about simple things, say? Simple things like the numbers that we use to count with. It turns out that we can view the numbers that we count with – mathematicians say: the natural numbers – as things that have some kind of reality, as objects with properties like being odd or even. We can use mathematics to find out deep truths about these things.

Logic is an attempt to understand this process. Logic looks at the properties of the language that we use to talk about mathematical objects. Logic studies the nature of the smallest steps that give strength and structure to mathematical proofs. Logic, surprisingly, finds limits to what we can *say* if we use a given language, or limits to what we can *prove* using that language.

The original scope of logic was common sense reasoning. When logic developed, it was connected to rhetoric and philosophy, and hardly at all to mathematics and science. Later on, logicians got interested in what makes mathematical reasoning so exceptionally solid. What is the nature of the process of finding and checking proofs? What is a proof, really? What are the properties of the language in which we state proofs? Why is checking proofs so much easier than finding proofs? Is there method to the art of finding proofs, is there maybe some as yet undiscovered master key to mathematical truth? Well, this master key has not shown up. Almost nobody believes that it exists, although we do not have a proof that it cannot exist; this relates to the famous unsolved P versus NP problem.

To see what logic is about, let’s consider a mathematical problem, the problem of finding the length *x* of the diagonal of a square with sides of length 1.

To find out something about *x* we can put four of those squares together.

If the length of the side of a single square is 1, then the surface area of four of these squares put together must be *4*. And the surface of the shaded area is precisely half of this, so it has to be *2*:

So we know something about *x*. The product of *x* with itself, or the *square* of *x*, has to be *2*. Now what is *x*? How do we find *x*?

Imagine you are a *very* clever guy or lass, and project yourself back in time. You are in ancient Babylonia, and you consider this question. We know that someone like you found the answer. This clay tablet is the proof of that:

This tablet has a number at one of the sides of the square, and a number on the diagonal of the square. It turns out that the number on the diagonal is remarkably close to the square root of 2 times the number on the side. So the Babylonians must have found a way to compute, roughly, the square root of 2. How did they do it? In order to see the magnitude of the achievement, ask yourself: how would I do it? Mathematics as taught in schools is often perceived as a dry subject. One way of bringing it to life is by taking a *first person* perspective. How would I tackle this question, assuming that I know what the Babylonians knew?

So you know what you are after: you want to find an *x* that, if you multiply *x* with itself, you get 2. Certainly, *x* is larger than 1, you get that from the picture. How about starting with two *unequal* sides that give 2 when multiplied? We could start with 1 and 2. Then we can view 1 as an under-approximation of *x*, and 2 as an over-approximation. Their product is 2, as required.

Here is an insight that this clever boy or girl in Babylon must have had. If we have an under-approximation and an over-approximation of *x*, then we can always improve our guess by taking the average. If we start out with 1 and 2 the average is 3/2. Take this as our new approximation. Next, see that there is no reason to stop here.

Since the square of 3/2 is 9/4, the value 3/2 that we found is an over-approximation. But if we divide 2 by this over-approximation, we get an under-approximation. This gives 2 divided by 3/2, which equals 2 times 2/3, which is 4/3. OK, we have found a new under-approximation 4/3 and over-approximation 3/2.

We want to get closer. How do we do this? By taking the average again. So we take the average of 4/3 and 3/2, which is (8/6 + 9/6)/2, that is 17/12. This is still a slight over-approximation, for the square of 17/12 is 289/144 which is 2 + 1/144. But then 2/(12/17) = 24/17 is an under-approximation. We want to get still closer. So again we can take the average. This gives 577/408. Now the Babylonians are in trouble, for it takes a lot of scratch clay tablet to go on. But we are *very* close now, for the square of 577/408 is 332929/166464 which equals 2 + 1/166464.

This procedure, invented by the Babylonians, is a very early and very clever example of what we now call an algorithm. A pocket calculator that gives us the square root of 2 executes a tiny program that goes through the steps above, and then prints out an approximate result in decimal notation.

For all practical purposes, our problem is solved. But we can now ask a fundamental question, a question of the kind that people involved with the design and analysis of algorithms, such as the researchers at CWI, that I have spent most of my working life with, ask themselves every day. The question is this: suppose we have enough time, and enough scratch clay tablet, or enough scratch paper, or enough computing power, will the Babylonian algorithm for computing the square root of 2 (or any other algorithm that attempts to express the square root of 2 as a fraction) ever find a *precise* answer?

How would one go about answering such a question? As far as we know, the Babylonians never found out. But the Greeks, inventors of the method of proof in mathematics, did find out. More precisely, some member of the mystery school led by Pythagoras found out. And the answer was such a shock to them that they decided to keep it secret. In any case, that is the legend. There is also a legend that there was a guy, Hippasus of Metapontum, who spilled the beans (divulged the secret), and was murdered for his betrayal.

The proof that the square root of two cannot be expressed as a ratio between two numbers *m* and *n* goes as follows.

Assume, for a contradiction, that there are positive whole numbers *m* and *n* with the property that the square of *m* divided by the square of *n* equals 2. That is, we *assume* that the Babylonian method, or some other method, has given us a precise fraction *m/n* for which *mm/nn = 2*, and then we explain how that assumption gets us into logical trouble. And we conclude from this that the assumption must have been wrong.

Here goes. We may assume that *m/n* is canceled down to its lowest form, i.e., there are no whole numbers *k,p,q* with *k* larger than 1, and such that *m = kp* and *n = kq*. In particular, we can assume that *m* and *n* are not both even, for if they were, we could simplify the fraction by divide both numerator *m* and denominator *n* by *2*.

We have: *mm/nn = 2*, and therefore *mm = 2nn*, that is to say, *mm* is even. But if the product of a number with itself (the square of a number) is even, then the number itself has to be even. For suppose *m* is odd, that is, *m = 2p + 1* for some *p*. Then *mm = (2p + 1)(2p + 1) = 4pp + 4p + 1 = 4(pp + p) + 1*, that is to say, *mm* is also odd. So odd numbers always have odd squares. Since the square of *m* is even, *m* has to be even.

So there is a whole number *q* such that *m = 2q*. Using this, we can rewrite *mm = 2nn*, and get *4qq = 2nn*, and therefore *nn = 2qq*. But this means, horror of horrors, that the square of *n* is also even. But that means that *n* is even, and we have a contradiction with the assumption that *m* and *n* are not both even.

It follows that there are no whole numbers *m* and *n* such that *mm/nn = 2*. And that means that the Babylonian method, that finds closer and closer approximations *m/n* to the square root of 2, can never halt with a precise answer.

If this example intrigues you then I encourage you to pursue the story of the square root of 2 on Wikipedia. It is also possible to play with the Babylonian method on a computer. Here is a Haskell program that computes fractions that get closer and closer to the square root of 2:

```
bab :: (Integer,Integer) -> (Integer,Integer)
bab (m,n) = (m^2 + 2*(n^2), 2*m*n)
gen :: (a -> a) -> a -> [a]
gen f x = x : gen f (f x)
babseq :: [(Integer,Integer)]
babseq = gen bab (1,1)
```

If you play with this, you will see that `babseq`

generates an endless list of pairs (m,n) of whole numbers such that the fraction m/n gets closer and closer to the square root of 2. And if you understand the above proof, you will *know* why this process of getting closer and closer has to go on forever.

How does logic come in? Logic studies the process by which mathematical proof gives us certainty. What is the language of proofs? What is the nature of proofs? What are the smallest reasoning steps that are used in a proof, and how can we be sure that they are correct? What is the nature of the world of mathematics that mathematical proofs talk about?

The great Greek philosophers marvelled at the magical power of the method of proof, the method that has the power to give us certainty when talking about shape and proportion in a precise manner. Aristotle made the observation that there seems to be a great difference between two mental activities:

understanding a given proof

finding our own proof.

He observed that if someone gave him a proof of some mathematical statement, then he could, by tracing the steps of the proof, quite easily convince himself that the statement was true. But if someone would give him the same statement without its proof, he would usually have great difficulty in finding out whether the statement was true, and in many cases he would not succeed, even with great effort. Finding proofs is difficult, checking well-written proofs is much easier.

To understand this better, the following analogy is helpful. Here is a do-it-yourself instruction to create a set of Tangram pieces. Take a square sheet of paper, and cut according to the following lines. This will give you two big triangles, one medium triangle, two small triangles, a square, and a lozenge.

A Tangram puzzle is a figure of a particular shape. The puzzle is: find out how to construct this shape by combining the seven Tangram shapes. Here is an example:

And here is its solution:

It is easy to check that this uses precisely the seven Tangram shapes, so it *is* indeed a solution to the problem.

In the same way, we can have the experience of suddenly seeing an explanation of something puzzling that we observe. Here is a photograph of the Amolf building at Science Park, nextdoor to CWI. The building has a parking lot next to it. Only a small part of that is visible on the picture.

In passing this building in the evening, around 7 pm, one can observe something peculiar about the cars parked next to the building. There will be one or two cars immediately next to the building, and quite a few cars at the parking spots that are furthest removed from the building. This is a regularity: I see it every time I pass by the building on my bicycle ride towards home from work. What is the explanation?

This is the kind of thing where it is funny to observe your own mind. First you cycle by and you do not observe anything. At some point you notice a regularity, and you think nothing of it. Then, suddenly, it dawns on you that there is a reason for this pattern. The researchers at Amolf have flexible working hours. The people that show up at 7 am leave their car close to the building. The people that show up only at 12 can only find a parking spot further away from the building. Those are the people that leave late; they are still around at 7 pm, and this is why I can see their cars at the far side of the parking lot, while the parking space next to the building is nearly empty. The nice thing of this type of insight is that, once you hit at it, you can be almust sure that you have it right.

Here is another example, taken from a (very much recommended) book on Buddhism.

Some people can immediately recognize what this is a picture of, but most people cannot. If you cannot, the following is interesting. Keep looking at the picture. At some point, if you are lucky, you suddenly see it. Now observe what happens in your mind at this moment, and, in particular, note the feeling of absolute certainty *that* you got it. And note that you cannot *not* see is once it has dawned on you. The picture is taken from the book Buddhism plain and simple by Steve Hagen. The author compares the experience of seeing what the picture is about with the sudden illumination on seeing what your life is about.

In the last thirty years, the scope of logic has shifted considerably, from investigation of the foundations of mathematics to investigation of the nature of computation (logic in computer science), the nature of communication (the logic of interaction), and the nature of rational behaviour (logic in connection to game theory and decision theory).

So our next topic is the use of logic in getting a grip on the nature of *rationality*, on what it means to behave as a rational person in some given social situation. Logic has something important to say about this. But it is also important to see that logic cannot give us the *full* story.