Mathematical Logic

Joseph R. Shoenfield

• Publisher: A K Peters/CRC Press
• Year: 2018
• ISBN:
  9781351433303
• Edition: 1
• Topic: Mathematik
• Subtopic: Mathematik Allgemein

This classic introduction to the main areas of mathematical logic provides the basis for a first graduate course in the subject. It embodies the viewpoint that mathematical logic is not a collection of vaguely related results, but a coherent method of attacking some of the most interesting problems, which face the mathematician. The author presents the basic concepts in an unusually clear and accessible fashion, concentrating on what he views as the central topics of mathematical logic: proof theory, model theory, recursion theory, axiomatic number theory, and set theory. There are many exercises, and they provide the outline of what amounts to a second book that goes into all topics in more depth. This book has played a role in the education of many mature and accomplished researchers.

CHAPTER 1

THE NATURE OF MATHEMATICAL LOGIC

1.1 AXIOM SYSTEMS

Logic is the study of reasoning; and mathematical logic is the study of the type of reasoning done by mathematicians. To discover the proper approach to mathematical logic, we must therefore examine the methods of the mathematician.

The conspicuous feature of mathematics, as opposed to other sciences, is the use of proofs instead of observations. A physicist may prove physical laws from other physical laws; but he usually regards agreement with observation as the ultimate test of a physical law. A mathematician may, on occasions, use observation; for example, he may measure the angles of many triangles and conclude that the sum of the angles is always 180°. However, he will accept this as a law of mathematics only when it has been proved.

Nevertheless, it is clearly impossible to prove all mathematical laws. The first laws which one accepts cannot be proved, since there are no earlier laws from which they can be proved. Hence we have certain first laws, called axioms, which we accept without proof; the remaining laws, called theorems, are proved from the axioms.

For what reason do we accept the axioms? We might try to use observation here; but this is not very practical and is hardly in the spirit of mathematics. We therefore attempt to select as axioms certain laws which we feel are evident from the nature of the concepts involved.

We thus have a reduction of a large number of laws to a small number of axioms. A rather similar reduction takes place with mathematical concepts. We find that we can define certain concepts in terms of other concepts. But again, the first concepts which we use cannot be defined, since there are no earlier concepts in terms of which they can be defined. We therefore have certain concepts, called basic concepts, which are left undefined; the remaining concepts, called derived concepts, are defined in terms of these. We have a criterion for basic concepts similar to that for axioms: they should be so simple and clear that we can understand them without a precise definition.

In any statement, we can replace the derived concepts by the basic concepts in terms of which they are defined. In particular, we may do this for axioms. Hence we may suppose that all the concepts which appear in the axioms are basic concepts.

We may now describe what a mathematician does as follows. He presents us with certain basic concepts and certain axioms about these concepts. He then explains these concepts to us until we understand them sufficiently well to see that the axioms are true. He then proceeds to define derived concepts and to prove theorems about both basic and derived concepts. The entire edifice which he constructs, consisting of basic concepts, derived concepts, axioms, and theorems, is called an axiom system. It may be an axiom system for all of mathematics, or for a part of mathematics, such as plane geometry or the theory of real numbers.

We have so far supposed that we have definite concepts in mind. Even so, it may be possible to discover other concepts which make the axioms true. In this case, all the theorems proved will also be true for these new concepts. This has led mathematicians to frame axiom systems in which the axioms are true for a large number of concepts. A typical example is the set of axioms for a group. We call such axiom systems modern axiom systems, as opposed to the classical axiom systems discussed above. Of course, the difference is not really in the axiom system, but in the intentions of the framer of the system.

Guided by this discussion, we shall begin the study of mathematical logic by studying axiom systems. This will eventually lead us to a variety of problems, some of them only faintly related to axiom systems.

1.2 FORMAL SYSTEMS

An axiom (or theorem) may be viewed in two ways. It may be viewed as a sentence, i.e., as the object which appears on paper when we write down the axiom, or as the meaning of a sentence, i.e., the fact which is expressed by the axiom. At first sight, the latter appears much more important. The obvious purpose of the sentence is to convey the meaning of the sentence in a clear and precise manner. This is a useful purpose, but it does not seem to have much to do with the foundations of mathematics.

Nevertheless, there are two good reasons for studying axioms and theorems as sentences. The first is that if we choose the language for expressing the axioms suitably, then the structure of the sentence will reflect to some extent the meaning of the axiom. Thus we can study the concepts of the axiom system by studying the structure of the sentences expressing the axioms. This is particularly valuable for modem axiom systems, since for them our initial understanding of the basic concepts may be very weak.

The second reason is that the concepts of mathematics are usually very abstract and therefore difficult to understand. A sentence, on the other hand, is a concrete object; so by studying axioms as sentences, we approach the abstract through the concrete.

One point is apparent: there is no value in studying concrete (rather than abstract) objects unless we approach them in a concrete or constructive manner. For example, when we wish to prove that a concrete object with a certain property exists, we should actually construct such an object, not merely show that the nonexistence of such an object would lead to a contradiction.

Proofs which deal with concrete objects in a constructive manner are said to be finitary. Another description, suggested by Kreisel, is this: a proof is finitary if we can visualize the proof. Of course, neither description is very precise; but we can apply them in many cases to decide whether or not a particular proof is finitary.

Once the fundamental difference between concrete and abstract objects is appreciated, a variety of questions are suggested which can only be answered by a study of finitary proofs. For example Hilbert, who first instituted this study, felt that only finitary mathematics was immediately justified by our intuition. Abstract mathematics is introduced in order to obtain finitary results in an easier or more elegant manner. He therefore suggested as a program to show that all (or a considerable part) of the abstract mathematics commonly accepted can be viewed in this way. The question of how far such a program can be carried out is of obvious interest, even to those who do not find Hilbert’s view of abstract mathematics congenial.

The study of axioms and theorems as sentences is called the syntactical study of axiom systems; the study of the meaning of these sentences is called the semantical study of axiom systems. For the above reasons, we shall often keep the syntactical and the semantical parts of our investigations separate. When it is possible and reasonably convenient, we shall carry out our syntactical investigations in a finitary manner. We shall always consider axioms and theorems to be sentences, and hence syntactical objects; when we wish to study them semantically, we speak of the meaning of the axiom or theorem.

To guide us in our syntactical study, we introduce the notion of a formal system. Roughly, a formal system is the syntactical part of an axiom system. We shall give a precise definition.

The first part of a formal system is its language. As previously stated, this should be chosen so that, as far as possible, the structure of the sentences reflects their meaning. For this reason among others, we generally use artificial languages for our formal systems.

To specify a language, we must first of all specify its symbols. In the case of English, the symbols would be the letters, the digits, and the punctuation marks. Most of our artificial languages will have infinitely many symbols.

Any finite sequence of symbols of a language is called an expression of that language. It is understood that a symbol may appear several times in an expression; each such, appearance is called an occurrence of that symbol in the expression. The number of occurrences of symbols in an expression is called the length of that expression. (Thus the English expression boot has length 4.) We allow the empty sequence of symbols as an expression; it is the only expression of length 0.

It is possible for one expression to appear within another expression. Each such appearance is called an occurrence of the first expression in the second expression. Thus the English expression on has two occurrences in the English expression confront. However, we do not count it as an occurrence when the symbols of the first expression appear in the second expression in a different order or separated by other symbols. Thus on has no occurrences in not or in corn.

Most expressions in English are meaningless. Among the meaningful ones are the (declarative) sentences, which may be roughly described as those expressions which state some fact. We shall require that in each language, certain expressions of the language are designated as the formulas of the language; it is intended that these be the expressions which assert some fact.

We consider a language to be completely specified when its symbols and formulas are specified. This makes a language a purely syntactical object. Of course, most of our languages will have a meaning (or several meanings); but the meaning is not considered to be a part of the language. We shall designate the language of a formal system F by L(F).

The next part of a formal system consists of its axioms. Our only requirement on these is that each axiom shall be a formula of the language of the formal system.

We need a third part of a formal system which will enable us to conclude theorems from the axioms. This is provided by the rules of inference, which we often call simply rules. Each rule of inference states that under certain conditions, one formula, called the conclusion of the rule, can be inferred from certain other formulas, called the hypotheses of the rule.

How should we define the theorems of a formal system F? Obviously they should satisfy the two laws:

i) the axioms of F are theorems of F;

ii) if all of the hypotheses of a rule of F are theorems of F, then the conclusion of the rule is a theorem of F.

Moreover, we want a formula to be a theorem of F only if it follows from these laws that it is a theorem. We can therefore define a theorem of F to be a formula of F which can be seen to be a theorem on the basis of laws (i) and (ii).

We can give a somewhat more explicit description of the theorems of F. Let S₀ be the set of axioms; these are the formulas which can be seen to be theorems on the basis of (i). Let S₁ be the set of formulas which are conclusions of rules whose hypotheses are all in S₀; these are some of the formulas which can be seen to be theorems on the basis of (ii). Let S₂ be the set of formulas which are conclusions of rules whose hypotheses are all in S₀ and S₁; these are also theorems on the basis of (ii). In this way, we can construct sets S₃, S₄,…. Let S_ω be the set of formulas which are conclusions of rules whose hypotheses are all in at least one of S₀, S₁,…; these are again theorems by (ii). We continue in this way until no new theorems can be obtained by (ii); and we then have all of the theorems.

A definition of the type just given is called a generalized inductive definition. A generalized inductive definition of a collection C of objects consists of a set of laws, each of which says that, under suitable hypotheses, an object x is in C. Some of the hypotheses may say that certain objects (related to x in a certain way) are in C. When we give such a definition, we always understand that an object shall be in C only if it follows from the laws that it is in C. We can then give a more explicit description of C along the above lines.

As another example, suppose that we have defined 0 and successor, and wish to define natural number. (The natural numbers ...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Table of Contents
• Chapter 1 The Nature of Mathematical Logic
• Chapter 2 First-Order Theories
• Chapter 3 Theorems in First-Order Theories
• Chapter 4 The Characterization Problem
• Chapter 5 The Theory of Models
• Chapter 6 Incompleteness and Undecidability
• Chapter 7 Recursion Theory
• Chapter 8 The Natural Numbers
• Chapter 9 Set Theory
• Appendix The Word Problem
• Index