A Beginner's Guide to Mathematical Logic

Raymond M. Smullyan

• Publisher: Dover Publications
• Year: 2014
• ISBN:
  9780486782973
• Topic: Mathematics
• Subtopic: Logic in Mathematics

Combining stories of great writers and philosophers with quotations and riddles, this completely original text for first courses in mathematical logic examines problems related to proofs, propositional logic and first-order logic, undecidability, and other topics. 2013 edition.

Part I

General Background

1

Genesis

Just what is Mathematical Logic? More generally, what is Logic, whether mathematical or not? According to Tweedledee in Lewis Carroll’s Through the Looking Glass, “If it was so, it might be, and if it were so, it would be, but since it isn’t, it ain’t. That’s 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 Devil’s 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:

Major Premise:	Sixty men can do a piece of work sixty times as quickly as one man.
Minor Premise:	One man can dig a post-hole in sixty seconds. Therefore,
Conclusion:	Sixty men can dig a post hole in one second.”

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 student’s 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, “I’m 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.”

Problem 1. 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...