Raymond M. Smullyan - A Beginners Guide to Mathematical Logic

Raymond M. Smullyan

Dover Publications, Inc.
Mineola, New York

Copyright

Copyright 2014 by Raymond M. Smullyan
All rights reserved.

Bibliographical Note

A Beginners Guide to Mathematical Logic is a new work,
first published by Dover Publications, Inc., in 2014.

International Standard Book Number
eISBN-13: 978-0-486-78297-3

Manufactured in the United States by Courier Corporation
49237001 2014
www.doverpublications.com

Just what is Mathematical Logic? More generally, what is Logic, whether mathematical or not? According to Tweedledee in Lewis Carrolls Through the Looking Glass, If it was so, it might be, and if it were so, it would be, but since it isnt, it aint. Thats logic.

In The 13 Clocks by James Thurber, the author says, Since it is possible to touch a clock without stopping it, it follows that one can start a clock without touching it. That is logic, as I understand it.

A particularly delightful characterization of logic was given by Ambrose Bierce, in his book The Devils Dictionary. This is really a wonderful book that I highly recommend, which contains such delightful definitions as that of an egotist: An egotist is one who thinks more of himself than he does of me. His definition of logic is Logic; n. The art of thinking and reasoning in strict accordance with the limitations and incapacities of the human misunderstanding. The basis of logic is the syllogism, consisting of a major and a minor premise and a conclusion thus:

The philosopher and logician Bertrand Russell defines mathematical logic as The subject in which nobody knows what one is talking about, nor whether what one is saying is true.

Many people have asked me what mathematical logic is, and what its purpose is. Unfortunately, no simple definition can give one the remotest idea of what the subject is all about. Only after going into the subject will its nature become apparent. As to purpose, there are many purposes, but again, one can understand them only after some study of the subject. However, there is one purpose that I can tell you right now, and that is to make precise the notion of a proof.

I like to illustrate the need for this as follows: Suppose a geometry student has handed in to his teacher a paper in which he was asked to give a proof of, say, the Pythagorean Theorem. The teachers hands back the paper with the comment, This is no proof ! If the student is sophisticated, he could well say to the teacher, How do you know that this is not a proof? You have never defined just what is meant by a proof! Yes, with admirable precision, you have defined geometrical notions such as triangles, congruence, perpendicularity, but never in the course did you define just what is meant by a proof. How would you prove that what I have handed you is not a proof?

The students point is well-taken! Just what is meant by the word proof? As I understand it, on the one hand it has a popular meaning, but on the other hand, it has a very precise meaning, but only relative to a so-called formal mathematical system, and thus the meaning of proof varies from one formal system to another. It seems to me that in the everyday popular sense, a proof is simply an argument that carries conviction. However, this notion is rather subjective, since different people are convinced by different arguments. I recall that someone once said to me, I can prove that liberalism is an incorrect political philosophy! I replied, Im sure you can prove this to your satisfaction, and to the satisfaction of those who share your values, but without even hearing your proof, I can assure you that your so-called proof would carry not the slightest conviction to those with a liberal philosophy! He then gave me his proof, and indeed it seemed perfectly valid to him, but obviously would not make the slightest dent on a liberal.

Speaking of logic, here is a little something for you to think about: I once saw a sign in a restaurant which read, Good food is not cheap. Cheap food is not good.

Do those two statements say different things, or the same thing?

Note that solutions to problems are given at the end of the chapters.

Mathematical Logic is sometimes also referred to as Symbolic Logic. Indeed, one of the most prominent journals on the subject is entitled The Journal of Symbolic Logic. How did the subject even start? Well, it was preceded by logic of a non-symbolic nature. The name Aristotle obviously comes to mind, for that famous ancient Greek philosopher was the person who introduced the notion of the syllogism. It is important to understand the difference between a syllogism being valid and a syllogism being sound. A valid syllogism is one in which the conclusion is a logical consequence of the premises, regardless of whether the premises are true or not. A sound syllogism is a syllogism which is not only valid, but in which, in addition, the premises are true. An example of a sound syllogism is the well-known:

All men are mortal.

Socrates was a man.

Therefore, Socrates was mortal.

The following is an example of a syllogism which, though obviously unsound, is nevertheless valid:

All bats can fly.

Socrates is a bat.

Therefore, Socrates can fly.

Clearly, the minor premise (the second one) is false, and also, of course, so is the conclusion. Nevertheless, the syllogism is valid the conclusion really is a logical consequence of the two premises. If Socrates were a bat, then he really could fly.

I am amused by syllogisms that appear to be obviously invalid, but are actually valid! Here are two examples:

Everyone loves my baby.

My baby loves only me.

Therefore, I am my own baby.

Doesnt that sound ridiculous? But it really is valid! Here is why:

Since everyone loves my baby, then my baby, being also a person, loves my baby. Thus my baby loves my baby. But also, my baby loves only me (minor premise). Since my baby loves only me, then there is only one person my baby loves (namely me), but since my baby loves my baby, that one person must be me. Thus I must be my own baby.

Here is another example of a valid syllogism which seems invalid. We define a lover as one who loves at least one person.

Everyone loves a lover.

Romeo loves Juliet.

Therefore: Iago loves Othello.

Here is why the syllogism is valid. Since Romeo loves Juliet (second premise), then Romeo is a lover. Since Romeo is a lover, then everyone loves Romeo (by the first premise). Since everyone loves Romeo, then everyone is a lover. Since each person is a lover, then everyone loves that person (by the first premise). Thus it follows that everyone loves everyone! In particular, Iago loves Othello.

Once, the eminent logician and philosopher Bertrand Russell was asked, What is really new in the conclusion of a syllogism? Russell replied that logically, the conclusion may contain nothing new, but the conclusion can nevertheless have psychological novelty, and he then told the following story to illustrate his point.