What Is Mathematical Logic?
96
What Is Mathematical Logic?
96eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
Although mathematical logic can be a formidably abstruse topic, even for mathematicians, this concise book presents the subject in a lively and approachable fashion. It deals with the very important ideas in modern mathematical logic without the detailed mathematical work required of those with a professional interest in logic.
The book begins with a historical survey of the development of mathematical logic from two parallel streams: formal deduction, which originated with Aristotle, Euclid, and others; and mathematical analysis, which dates back to Archimedes in the same era. The streams began to converge in the seventeenth century with the invention of the calculus, which ultimately brought mathematics and logic together. The authors then briefly indicate how such relatively modern concepts as set theory, Gödel's incompleteness theorems, the continuum hypothesis, the Löwenheim-Skolem theorem, and other ideas influenced mathematical logic.
The ideas are set forth simply and clearly in a pleasant style, and despite the book's relative brevity, there is much covered on these pages. Nonmathematicians can read the book as a general survey; students of the subject will find it a stimulating introduction. Readers will also find suggestions for further reading in this lively and exciting area of modern mathematics.
Product Details
| ISBN-13: | 9780486151526 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 08/01/2012 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 96 |
| File size: | 19 MB |
| Note: | This product may take a few minutes to download. |
About the Author
Read an Excerpt
What Is Mathematical Logic?
By J.N. Crossley, C.J. Ash, C.J. Brickhill, J.C. Stillwell, N.H. Williams
Dover Publications, Inc.
Copyright © 1972 Oxford University PressAll rights reserved.
ISBN: 978-0-486-15152-6
CHAPTER 1
Historical Survey
The different areas in logic emerged as a result of difficulties and new discoveries in a complicated history, so this first chapter is going to describe a flow chart (see p. 2). I shall skip rather briefly over the different areas, so do not be worried if you find a lot of strange terminology—it will be explained later on in the book. I am going to view the history as two different streams, both of which are very long: one is the history of formal deduction which goes back, of course, to Aristotle and Euclid and others of that era, and the other is the history of mathematical analysis which can be dated back to Archimedes in the same era. These two streams developed separately for a long time—until around 1600–1700, when we have Newton and Leibnitz and their invention of the calculus, which was ultimately to bring mathematics and logic together.
The two streams start to converge in the 19th century, let us say arbitrarily about 1850, when we have logicians such as Boole and Frege attempting to give a final and definitive form to what formal deduction actually was. Now Aristotle had made rather explicit rules of deduction, but he had stated them in natural language. Boole wanted to go further than this and he developed a purely symbolic system. This was extended by Frege, who arrived at the predicate calculus which turned out to be an adequate logical basis for all of today's mathematics. Perhaps I can dwell a little on this, since symbolism became so important from this point onwards. A little description of what symbolism can look like will help.
Purely logical connectives, such as and, or, not are given symbols such as &, V, [??]; need symbols (x, y, z and so on) for variables and also symbols P, Q, R for predicates (or properties or relations). Out of these we make formulae such as this: P (x) VQ (x), which is read as saying that x has property P or x has property Q, and this can be quantified by expressing 'for all x' by [for all]x and 'there exists an x' by [there exist]x. Thus [for all]xP (x) says every x has property P.
Now any mathematical domain can be translated into this language with a suitable choice of predicate letters: arithmetic, for instance. We have numbers as the objects that the variables will denote, and we have various properties of numbers that we wish to express, such as being equal or the relationship between two numbers and a third one which is the sum of the other two; another one could be the product relationship. You can quickly convince yourself that all statements that we are accustomed to make in number theory about divisibility, prime numbers, and whether one number is the sum of another two can be made using these predicates. Frege gave rules for making deductions in this language and the whole conglomeration is called predicate calculus.
Now meanwhile in analysis there was a long period, a couple of centuries, of controversy over the meaning of concepts that Newton introduced—the derivative and the integral—because he talked about infinitesimals. A lot of people did not believe in these and thought they were contradictory, which they were. But nevertheless he got the right results and, to find out why he got the right results, clarification of the notions was made. Some of the people responsible for this were Bolzano, Dedekind, and Cantor. (This brings us down to about 1880.) These people realized that, to deal adequately with derivatives and integrals, infinite sets had to be considered, and considered very precisely. There was no way of avoiding infinite sets. This was the origin of set theory.
I think it is worth pointing out that Cantor had got into set theory from a problem in analysis. He was not trying to define natural numbers or any of the other things that people have used set theory for since. His original motivation was analysis of infinite sets of real numbers. And I think this is really the proper domain of set theory: to solve problems like that rather than problems of definition of primitive concepts. This can be done and it was done by Frege (actually in an inconsistent way, but this was put right by Russell). Russell was dedicated to the proposition that mathematics was just logic. Logic to Russell was a lot more than we would consider logic today. We would say that really he showed that mathematics was logic and set theory. With sufficient patience and sufficient lengths of definitions any mathematical field can be defined in terms of logic and set theory and all the proofs carried out within the predicate calculus.
But of course Cantor was jumping ahead at this stage. He went way beyond trying to solve problems in analysis; he was interested in sets themselves and he really discovered how fascinating they were. (His results in set theory did feed back into analysis, as we shall see in a moment.) I think it is important to give you at least two proofs here of Cantor's results because the arguments he used were totally revolutionary and they have permeated the whole of logic ever since then. In fact most of the theorems, I feel, can be traced back to one or other of these arguments that I am about to describe. Cantor, in considering infinite sets, quickly came to the realization that a lot of infinite sets were similar to the set of natural (whole) numbers in the sense that they could be put in one-to-one correspondence with them. This was already known to Galileo in the simple case of even numbers. Galileo realized this correspondence existed and he was rather distraught about it, because he thought this ruined all hope of describing different sizes of infinite sets; he thought the concept must be meaningless. But Cantor was not bothered about this; he said we shall nevertheless say that these two sets are of the same infinite size, and then see how many other sets we can match with the set of natural numbers. And his first major discovery was that the rational numbers can be put in one-to-one correspondence with the natural numbers. (The rational numbers are the fractions p/q, where p and q are natural numbers, q ≠ 0.)
This comes as a great surprise to people, because as you know the rational numbers lie densely on the line, that is to say, between any two points there is a rational number. So if you try and start counting from the left you run out of numbers before you get anywhere at all. Cantor's method was this: he said that the rational numbers can be arranged as in the table on page 4. In the first row we put all the ones with denominator one, in the second one all the ones with denominator two, and then those with denominator three, and so on. And this table will include all the rational numbers. Now we count them like this: we start at the top left and then zig-zag, following the arrows. So the list goes 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2,.... We are not going to miss any out by this method, and every rational number will get assigned to a natural number (the number denoting its place in our list). That was his first discovery. In view of this extraordinary fact that a dense set on a line can nevertheless be counted, you might begin to expect that any infinite set can be counted. Of course, as you may well know, this is not the case and this was his second argument.
Now the real numbers, which correspond to the points on the line (all points on the line, forming a continuum) can be expressed by infinite decimal expansions and in general the decimal expansion has to be infinite ([square root of 2] for instance is an infinite decimal; there is no finite representation for it). So if we are going to make a correspondence between the real numbers and the natural numbers it will look something like this: we start by matching zero with some infinite decimal. (I just consider real numbers between zero and one, so there is nothing in front of the decimal point.) Next one is matched with some infinite decimal, then two is matched with some infinite decimal, and so on. Our ambition is somehow to get a list with all the real numbers in. Cantor said that no matter how you try to do this you fail, for the following reason: for any list that is given we can construct a number that is different from the first number by writing down a different digit in the first decimal place. We can make the number different from the second number by making it different in the second decimal place and we can make it different from the third number by making it different in the third decimal place, and by continuing in this way we get a real number that is an infinite decimal that is different from any number of the list. And it does not matter what the list is, this method will always work. So there cannot be any correspondence between the real numbers and the natural numbers, and so we have discovered a larger infinite set.
Cantor gave an elaboration of this argument too, which I shall briefly describe. Take any set, S: you cannot put S in one-to-one correspondence with the set of all its subsets, that is, the set {T:T [subset or equal to] S}. And the argument is really the same as the previous one, though it looks a bit different. This time we shall make what we would loosely call a list of the members of S. They might not be a listable set, but just imagine that somehow we are trying to match the members of S with the subsets of S. And let Ts be the subset that we match with the member s. Cantor immediately constructs a subset which is not on this list. He constructs a subset U consisting of the members s which are matched with a subset to which they do not belong. Now if you think about it we are making U different from every subset T because Ts either has s as an element or it does not. Either way we make U different from Ts with respect to this element s. If s is in Ts, we leave s out of U. If s is not in Ts we put s in U. Thus there are more subsets of S than can ever be matched one-to-one with the members of S —any such matching omits a set U such as we have described.
Now there is one further step you can take in this argument: suppose S is the set of all sets in the universe. Take the subsets of S—that is, another set, or it ought to be. This argument seems to be saying that if you start with all of the sets in the universe and take all the subsets, you get more. But you cannot get more than there is in the universe. Cantor was aware of this problem but took it in his stride, which I think was very perceptive of him. Russell also found out about it, and he worried about it. This was the notorious Russell paradox, or something very similar to it anyway.
So this whole program of reducing mathematics to logic and set theory was endangered by the fact that set theory looked very dodgy at this point. Immediately the first concern of mathematicians was to clean up the basis of set theory so that paradoxes could not arise. Somehow we have to prevent the collection of all sets in the universe being considered as a set itself. And that is actually very easy to do, if you insist that sets are always built up from things that you know about to begin with—that is, the natural numbers and the real numbers—and you do not stop; you always consider it possible to go one level higher, so that you never complete the whole universe and only things which are completed are regarded as sets. Now this idea was suggested about 1908, by Zermelo. And Russell did a similar thing, though his method is technically more clumsy and is scarcely used today. The idea was finally polished up with the help of Fraenkel and Skolem in 1922. This was then an axiomatic set theory which seemed to avoid the problems.
Around the same time another problem had developed with this conception of reducing mathematics to a symbolic language, and this was the following. So far, we had a certain domain of study in mind; it might have been the natural numbers or it might have been analysis and we have gone to a formal theory, just using symbols. And so formal that everything is just mechanical. Every statement about this domain is a series of symbols. We make the deductions by mechanical operations on the symbols. We get things out which we call theorems, and these are true statements about the domain. So that seems fine. But when we just have a collection of symbols, they are susceptible to many different interpretations (or models as they are called) and it is possible that interpretations exist that are entirely different from the domain we thought of in the first place. So to be careful we should consider other models, if there are any, of the theory. The decisive result which shows that there are definitely unintended interpretations was proved in 1915 by Löwenheim, and this was sharpened by Skolem. Naturally enough it is called the Löwenheim–Skolem Theorem.
We shall talk a little about this interesting result. This deserves a box of its own in our chart. The Löwenheim–Skolem Theorem simply says that every theory has countable models. This was a tremendous shock because we already have uncountable sets and theories about these things, such as the theory of real numbers, that are supposed to be about uncountable domains. So we have models for axioms that are definitely not what we intended. I can briefly describe how this result comes about. First we observe that languages after all are only countable—they are just finite strings of symbols and by elaborating the technique of enumerating the rational numbers given above, you can enumerate all the statements in a theory. Now consider the intended domain and what the axioms really determine about it. Axioms can say that certain objects exist initially; for example, they can say that zero exists, if you talk about the natural numbers. If you analyze the other things they can say, roughly speaking they are things like: if such and such exists, then something else must exist. So not too many things are actually necessary in order to satisfy the axioms. We have to start with the initial objects and then what is needed because of them, and what is needed because of that, and so a skeleton can be built up which contains only countably many points. This is possible because, if you can only say countably many things about a certain domain, then only countably many objects are needed to satisfy those statements.
Obvious as this may be, it escaped people's attention for a long time and then it bothered them, of course, that such things can hold about set theory where there are supposed to be uncountably many objects existing. Since the axioms of set theory yield a proof that uncountable sets exist, how can they be satisfied in a countable domain? This state of affairs is called the Skolem paradox. It is not a real paradox and it gets resolved later, but there seems to be a paradox if theories can have countable models and yet there is a theory about uncountable things. We have to say: what does 'countable' mean in relation to a model? And this will be treated in Chapter 3. But this was very thought-provoking and it led to exceptionally good theorems later on.
All the time up until this (1920), and up to 1930 in fact, people had used predicate calculus for making logical deductions without finding out for sure whether they obtained all of the valid statements this way. The argument that was developed for the Löwenheim-Skolem theorem is similar, in some presentations at least, to a proof of the completeness of the predicate calculus. This is another milestone. This was the first major result that Gödel proved, and not the last. What exactly does 'completeness' mean? If we have a language with predicate symbols, variables, and quantifiers, certain things are valid no matter how we interpret the symbols. No matter what property P may denote and no matter what domain the variables are ranging over, [for all]xP (x) [right arrow] [there exist]xP (x ) is definitely true (where ? means implies). The object of the predicate calculus was to produce in a mechanical fashion all logically valid formulae. Gödel succeeded in proving that it was complete, that it did achieve this object.
Just a little while later he proved a really shattering result, in 1931, about incompleteness: incompleteness was present even in arithmetic. By arithmetic I mean the theory I sketched before, in which you can prove things about the natural numbers and the properties that are definable in terms of addition and multiplication. Now, our object with the formal system for arithmetic naturally would be to prove everything that is true about the natural numbers. But Gödel showed that, no matter what formal system you start with, this cannot be accomplished; there are always sentences of arithmetic which cannot be proved or disproved relative to the original system. In establishing this result he used a welter of arguments: some of them dated back to Cantor's diagonal argument; another technique was to express properties of the symbols of the formal system in terms of numbers and hence in terms of statements in the system itself. The system could therefore talk about itself in some sense. And this coding of formulae and symbols was accomplished by rather elaborate machinery: he defined functions from very simple functions like addition and multiplication and from these he built up to more and more complicated functions, but all of these functions could be defined in arithmetic. After he had done this, people began to be interested in the functions themselves. They are called recursive functions and reached their definitive form around 1936. I shall try and briefly explain what a recursive function is. In fact in one word it is a computable function. The functions Gödel used were ones which anybody could compute given simple instructions. Anybody could compute the product of two numbers and the sum of two numbers; anybody can compute the nth prime number. (It is a bit complicated, but you can do it.) Mathematicians began to wonder if Gödel's functions did indeed include every computable function. They were not convinced of this for quite some time, and a lot of experimentation was done with other methods of defining computable.
(Continues...)
Excerpted from What Is Mathematical Logic? by J.N. Crossley, C.J. Ash, C.J. Brickhill, J.C. Stillwell, N.H. Williams. Copyright © 1972 Oxford University Press. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
Introduction1. Historical Survey
2. The Completeness of Predicate Calculus
3. Model Theory
4. Turing Machines and Recursive Functions
5. Gödel's Incompleteness Theorems
6. Set Theory
Some Suggestions for Further Reading
Index