View
223
Download
7
Category
Preview:
Citation preview
Hans Hermes
Introduction to Mathematical Logic
Translated from German by Diana Schmidt
Springer-Verlag Berlin· Heidelberg· New York 1973
Dr. HANS HERMES o. Professor an der Albert-Ludwigs-Universitat Mathematisches Institut Abteilung fur mathematische Logik und Grundlagen der Mathematik 78 Freiburg i. Br. Hermann-Herder-StraBe 10
Dr. DIANA SCHMIDT 6368 Bad Vilbel-Heilsberg Schlesienring 4
By permission of the publishers B. G. Teubner, Stuttgart, only authorized English translation of the German original edition "Einfiihrung in die mathematische Logik, 2. Auf!.", which appeared in the series "Mathematische Leitfaden", edited by Professor G. Kothe.
AMS Subject Classifications (1970): 02-01, 02B05, 02B10
ISBN-13: 978-3-540-05819-9
001: 10.1007/978-3-642-87132-0
e-ISBN-13: 978-3-642-87132-0
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproductions by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher, © by Springer-Verlag, BerlinlHeidelberg t 973. Printed in Germany Library of Congress Catalog Card Number 72-76760
Preface
This book grew out of lectures. It is intended as an introduction to classical two-valued
predicate logic. The restriction to classical logic is not meant to imply that this logic
is intrinsically better than other, non-classical logics; however, classical logic is a
good introduction to logic because of its simplicity, and a good basis for applications
because it is the foundation of classical mathematics, and thus of the exact sciences
which are based on it.
The book is meant primarily for mathematics students who are already acquainted with
some of the fundamental concepts of mathematics, such as that of a group. It should
help the reader to see for himself the advantages of a formalisation. The step from the
everyday language to a formalised language, which usually creates difficulties, is dis
cussed and practised thoroughly. The analysis of the way in which basic mathematical
structures are approached in mathematics leads in a natural way to the semantic notion
of consequence.
One of the substantial achievements of modern logic has been to show that the notion of
consequence can be replaced by a provably equivalent notion of derivability which is
defined by means of a calculus. Today we know of many calculi which have this property.
Some of these calculi are characterised by particular elegance and symmetry, which,
however, is bought at a price: The process of operating with them bears little relation
to the practices which mathematicians have adopted through years of experience in
proving. In order that the mathematician I s experience should not be useless when it
comes to deriving by means of a calculus, calculi have been developed which, to vary
ing degrees, mirror the traditional mathematical methods. The calculus which is treat
ed here, a form of sequent calculus, is of this sort. For technical reasons, we initially
consider only negation, conjunction and generalisation, in order to keep the theoretical
treatment as short as possible. However, the other logical connectives are treated
later on.
In order to make the significance of the completeness theorem clear, second-order logic
is also discussed briefly, using Peano I s axiom system as a starting-point.
Using model-theoretic methods, we prove a satisfiability theorem of A. Robinson; and,
with the aid of this, Beth I s definability theorem and Craig I s interpolation lemma'.
IV Preface
I am greatly indebted to Heinz-Dieter Ebbinghaus, Walter Oberschelp, Dieter Rodding,
Dieter Titgemeyer and Rainer Titgemeyer for their valuable help.
Finally, my thanks are due to Diana Schmidt for a most careful translation of this book,
which was first published in 1963 in German.
Freiburg i. Br., Summer 1972 Hans Hermes
Table of Contents
I. Introduction • • • • . • • • • . • • • • • • • • • • • • • • • • • • • • • • • . . • • • • • • • • • • 1
§ 1. The task of logic . • • • • . . • • . . • • • • • • • • • • • • . • . • • . . • • • • • • • • • 1
§ 2. EXamples of mathematical proofs •••••••••••.•••.•••.••••..• 4
2.1 Example from geometry. • • • • . • • • . • • • • . • . • • • • . • • • • . • • • • 4
2.2 Example from arithmetic • . • . • • . • • . • • • . . • • . • . • • • • . • • • . • 5
2.3 Example from group theory. • • • • • . • . • • . . • • . • • • • . • • • • • • • • 6
§ 3. The notion of consequence. • • . • • • . . • . • • • • • • . . • • • . • • • • . • • • . . 7
3.1 Statement of the problem ••••••• • • • • • • • • • • • • • • • • • . . • • • • 7
3 • 2 Groups •.••••••.•.••••••.••...•••.•••••.••.•.•••. 7
3.3 Group-theoretic statements •.••••••••••..••••••.•.•.••. 8
3.4 Consequences of the axioms for groups. . • • • . . • . • • • • • • • • • • .. 10
3.5 Another axiom system for group theory ••••••.••.••.••••••. 11
3.6 Consequences of the axioms for ring, field and lattice theory . . . • •. 12
3.7 Consequences of the axioms of Peano • • • • • • • • • . • • • • . • . • . . .• 12
3.8 Consequences of the axiom system for geometry •.••••••.•••.• 13
3.9 General definition of the notion of consequence. . • • • • • • . • . • • • .• 14
§ 4. Remarks on the notion of consequence •.•••••.••••••....•.•..• 15
4. 1 Independence proofs .••••.••••.••.•••..•..••••••••.•• 15
4.2 Mathematical statements as statement forms. . . • • • • • . • • • • . • .. 17
4.3 Categoricity. • • • • • • • • . • • • • • • • • • • • • • • • • . • • • • • • • • • • •• 19
4.4 The applicability of mathematics ••.•• • • • • • • • • • • • • • • . • • . •• 20
4.5 Semantics ••••••••••..•••. . • • • • • . • . • • • • . . . • • • • • • •• 20
§ 5. Logic calculi •.••.••.••.••••.••..••.•••••••••••••••••. 21
5.1 Mathematical proofs ••••.•.•.•••..••••••••••••••••• •• 21
5.2 Indefiniteness of the concept of immediate consequence • • • • . • . . .• 22
5 • 3 Rules of inference. . • • • • . • • • • . • • • • • • . • • • • • • • • • • • • • • •• 23
5.4 Complete sets of rules. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 25
5.5 Assumption calculi ••.•••.•••••••••••••.•• • • • • • • • . • •• 27
5.6 Mechanical proof ••••••••••••••••••.•••••••••••••••• 29
VI Table of Contents
§ 6. The symbolisation of mathematical statements: Junctors and quantifiers 30
6.1 Statement of the problem 30
6.2 Junctors 30
6.3 Symbols, rules for dispensing with brackets 33
6.4 Example of a non-extensional junctor 34
6.5 The quantifiers in predicate logic. • • 35
§ 7. The symbolisation of mathematical statements: Individuals, predicates and functions • • • • • • 39
7. 1 Survey •••••••••••••••••••••••••••••
7.2 Names for individuals, predicates and functions.
7.3 Examples of aristotelian statements ••••
7.4 Examples of mathematical statements
7.5 Definability of the existential quantifier by means of the universal quantifier •••••••••••••••.••••••••••••••••••••••
39
39
40
42
42
II. The Language of Predicate Logic
§ 1. Terms and expressions ••
45
45
45
46
48
49
49
51
1.1 Survey ••••••••••
1.2 Primitive symbols and rows of symbols
1.3 Terms ••••••••••
1.4 Atomic expressions.
1.5 Expressions •••
1.6 Finite alphabet
§ 2. Elementary questions of decidability
2. 1 Statement of the problem
2.2 Inversion principle •••••
2.3 Classification of terms and expressions
2.4 Decidability of the property of being a term.
2.5 Decidability of the property of being an expression.
52
52
52
52
53
53
2.6 Unique decomposition of sequences of terms ••• • 54
2.7 Unique decomposition of sequences of expressions 55
2.8 Decomposition of terms and expressions. • • • • • • • 56
§ 3. Proofs and definitions by induction on the structure of the expressions. 57
3.1 Analogy to arithmetic • • • • • • 57
3.2 Inductive definitions 59
§ 4. Free and bound variables
4. 1 Introduction •••••••
4.2 The rules of the calculi
4 • 3 D ecidabili ty • • • • • • • • •
4.4 Free occurrence of function and predicate variables
60
60
61
61
62
Table of Contents VII
§ 5. Substitution • • • • • • • • • • . • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 62
5. 1 Introduction. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 62 t 5.2 The operator Ax • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •. 63
5.3 Substitution calculus • • • • • •.• • • • • • • • • • • • • • • • • • • • • • • • • •• 64
5.4 Theorems about substitution. • • • • • • • • • • • • • • • • • • • • • • • • • •. 66
5.5 Proof of the above theorems. • • • • • • • • • • • • • • • • • • • • • • • • • •• 67
5.6 Further theorems about substitution •••••••••••••••••••••• 70
III. The Semantics of Predicate Logic. • • • • • • • • • • . • • • • • • • • • • • . • • • • •• 72
§ 1. Introduction to the semantics of the language of predicate logic. • • • • • •• 72
1.1 Expressions as statement forms • • • • . • • • • • • • • • • . • • • • • • • •• 72
1.2 Interpretations. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •. 73
1 • 3 Models • • • • • • • • • • • • • • • • • • • • • • . • • • • • • • • • • • • . • 75
1.4 Models of generalisations. • • • • • • • • • . • • • • • • • • • • • • • • 75
§ 2. Definition of the most important semantic concepts. • • • • • • • • • • • • • •• 76
2.1 The foundations of semantics •••••••••••••••••••.••• -. . • •• 76
2.2 Definition of the concept of an interpretation. • • • • • • • • • • • • • • •• 78
2.3 Definition of a model. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 79
2.4 Definition of consequence and of universal validity • • • • • • • • • • • •• 79
2.5 Definition of satisfiability. • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 80
§ 3. Theorems about models • • • • • • • • • • . • • • • . • • • • • • • • • • • • • • • • •• 82
3.1 The coincidence theorem
3.2 The substitution theorem
IV. A Predicate Calculus ••••••••••••••••••••••••••••••••••••••
§ 1. Preliminary remarks about the rules of the predicate calculus. The concept of derivability •••••••••••••••••.•••••••••••••••••••.••
1. 1 The relation Q'1"" ,Q'n I- Q', or I- Q'1 ••• an Q' •••••••••••••••••
1.2 The relation ~ I- Q' • • • • • • • • • • • • • • • • • • • • • • • • • •••••••••
83
84
86
86
86
87
§ 2. The rules of the predicate calculus •••••.•••••••.••••.••••••• 89
2.1 Introduction. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 89
2.2 Formulation of the rules ••••••••••••••••••• • • • • • • • . • •• 89
2.3 Schematic representation of the rules. • • • • • • • • •• •••••••••• 92
2.4 Derivations • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •. 92
2.5 Examples of derivations. • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 93
2.6 Three general remarks •••••••••••. • • • • • • • • • • • • • • • • • •• 94
2.7 Decidability of the property of being a derivation • • • • • • • • • • • • •• 95
§ 3. The soundness of the predicate calculus ••••••••••••••••••••• •. 97
3.1 Theorem of the soundness of the predicate calculus. • • • • • • • 97
3.2 The soundness of the rules of predicate logic. • • • • • • • • • • • 97
VIII Table of Contents
§ 4. Derivable rules 100
4. 1 Introduction • 100
4.2 Derived rules which can be justified by means of the rules (A), (R), (X) alone ...................•.................... 101
4.3 Derived rules for whose justification the rules (C), (C'), (C") are needed • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 103
4.4 Derived rules for whose justification the rules (A), (R), (X), (G), (Gx )' (Si) are needed. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 105
4.5 Derived rules for whose justification the rules (A), (R), (X), (st), (E) and (Ei) are used. • • • • • • • • • • • • • • • • • • • • • • • • • •• x 107
§ 5. Some properties of the concept of derivability. Consistency • 109
5.1 Survey •••••••••••••••••••••••••••
5.2 Some properties of the concept of derivability
5.3 Consistent and inconsistent sets of expressions
§ 6. The decidability of propositional derivability
6.1 Propositional derivability ••
6.2 Tautologies
6. 3 Assignments. • •••••
6.4 Decidability of the property of being a tautology.
6.5 Proof of Lemma 1, first part
6.6 Proof of Lemma 1, second part
6.7 Proof of Lemma 3 ••••••••••
V. Godel' s Completeness Theorem •••
§ 1. Isomorphisms of expressions
1. 1 Definition of isomorphisms ••
1.2 Local invertibility ••••••••
1.3 Theorems about isomorphisms ••
1.4 Proof of the theorems stated ••
§ 2. Sketch of the proof of the completeness theorem.
2 • 1 Sketch of the proof. • • • • • • • • • • • • • • • • •
2.2 Definition of the isomorphism q, 0 of expressions
§ 3. The process of maximalisation
3.1 Survey ••••••••••
3.2 Definition of the sets !Dlj and !Dl* of expressions.
3.3 The maximal consistency of !Dl* •••••••••
3.4 Consequences of the maximal consistency of !Dl*.
§ 4. Completion of the proof of the completeness theorem
4.1 Survey •••••••••••••
4.2 The domain of individuals w
4.3 The interpretation 3 over w
4.4 Satisfiability of !Dl* •••••••
109
109
112
114
114
115
116
117
118
119
120
122
122
122
123
124
124
129
129
130
130
130
131
132
133
134
134
135
135
136
Table of Contents IX
§ 5. Consequences of the completeness theorem • • • • • • • • • • • • • • • • • • • •• 138
5.1 The compactness theorems • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 138
5.2 Example. Non-archimedean ordered fields • • • • • • • • • • • • • • • • •• 139
5.3 The Lowenheim-Skolem theorem •••••••••••••.•.••••..••• 141
VI. Peano I s Axiom System. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 144
§ 1. The language and semantics of second-order logic. • • • • • • • • • • • • • • •• 145
1.1 The expressions of ~2 •••••••••••••••••••••••••••••••• 146
1.2 Models and the relation of consequence. • • • • • • • • • • • • • • • • • • •• 146
1.3 Equality ••••••••••••••••••••••..•••••••••••••••••• 147
1.4 Rules of inference. • • • • • • • • • • • • • . • • • • • • • • • • • • • • • • • • •• 147
§ 2. Isomorphic interpretations. Categoricity of axiom systems • • • • • • • • •• 148
2.1 Algebras • • • • • • • • • • • • • • • • • • • • • • • • • . • • • • • • • • • • • • • •• 148
2.2 Isomorphisms of algebras. • • • • • • • • • • • • • • • . • • • • • • • • • • • •• 149
2.3 The model relationship in the case of isomorphic algebras a~( 3) , ~ (3 I ). • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 150
2.4 Categorical axiom systems. • . • • • • • • • • • • • • • • • • • • • • • • • • •• 152
§ 3. The characterisability of the natural numbers in the language of second-order predicate logic. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 153
3.1 Survey •••••••••••••••••••••••.••••••••••••••••••• 153
3.2 Induction over the natural numbers. • • • • • • • • • • • • • • • • • • • • • •• 155
3.3 Proof of (***) ••••••••••••••••••••••••••••••••••••• 155
3.4 Peano relations. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 156
3.5 Proof of the Lemma in 3.1 ••••••••••••••••••••••••••••• 158
§ 4. The non-characterisability of the natural numbers in the language of predicate logic • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 159
4.1 Arithmetic within second-order logic • • . • • . • • . • . • • • • • • • • • •• 159
4.2 Arithmetic within predicate logic. • • • . • • • • • • • • • . • • • • • • • • •• 159
4.3 The main result. • • • • • . • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 161
4.4 Proof of Skolem I s theorem. • • • • • • • • • • • • • • • • • • • • • • • • • • •• 161
4.5 The incompleteness of second-order logic ••••••• ~ • • • • • • • • • •• 163
4.6 Increasing the number of arithmetical primitive notions. • • • • • • • •• 164
VII. Extensions of the Language, Normal Forms •••••••••••••••••••••• 166
§ 1. Extensions of the language of predicate logic • • • • • • • • • • • • • • • • • • •• 166
1.1 Statement of the problem • • • • • • • • • • • • • • • • • • • • • • • • • • • • •. 166
1.2 The language of the extended predicate logic. • • • • • • • • • • • • • • • •• 166
1.3 The semantics of the extended predicate logic. • • • • • • • • • • • • • • •• 168
1.4 An extended predicate calculus ••••••••• • • • • • • • • • • • • • • • •• 169
1.5 The completeness of the extended predicate calculus • • • • • • • • • • •• 171
x Table of Contents
§ 2. "Derived rules and derivability relations with the connectives v, -+, V . .. 172
2.1 Derived rules for V, -+ ••••••••••••••••••••••••••••••• 172
2.2 Derivability relations. • • • • • • • • • • • • • • • • • . • • • • • • • • • • • • •• 173
2.3 Derived rules for V ................................. 175
§ 3. Further derivability relations connected with quantification • • • • • • • • •• 176
3.1 Summary ••••••••••••••••••••••••••••••••••••••••• 176
3.2 Proof of the derivability relations (1) to (13) •••••••••••••••• 177
§ 4. Conjunctive and disjunctive normal forms • • • • • • • • • • • • • • • • • • • • •• 181
4.1 Statement of the problem ••••••••••••• • • • • • • • • • • • • • • • •• 181
4.2 Iterated conjunctions and disjunctions •••••
4.3 Producing conjunctive normal forms ••••••
181
182
§ 5. Prenex normal forms ••••••••••••••••••••••••••••••••••• 183
5.1 Prefixes •••••••• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 183
5.2 Prenex normal forms. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 184
5.3 Proof ••••••••••••••••••••••••••••••••••••••••••• 184
5.4 Proof of Lemma 1 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 186
5.5 Proof of Lemma 2 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 187
VIII. The Theorems of A. Robinson, Craig and Beth •••••••••••••• 189
§ 1. Embeddings of algebras, subalgebras, chains of algebras ••••• • • • • •• 189
1.1 Notation. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 189
1.2 Embeddings ••••••••••••••••••••••••••••••••••••••• 190
1.3 Subalgebras • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 190
1. 4 The union of a chain of algebras. • • • • • • • • • • • • • • • • • • • • • • • •• 191
§ 2. Theories •••••••••••••••••••••••••••••••••••••••••••• 192
2.1 Theories. The theory of an algebra. • • • • • • • • • • • • • • • • • • • • • •• 192
2.2 Different algebras with the same theory • • • • • • • • • • • • • • • • • • •• 192
2.3 Some lemmas. • • • • • • • • • • • • • • • • • • • • • • • . • • • • • • • • • • • •• 193
§ 3. Elementary embeddings of algebras. Elementary subalgebras. Elementary chains of algebras. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 194
3.1 Elementary embeddings • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 194
3.2 Elementary subalgebras • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 195
3.3 The union of an elementary chain of algebras • • • • • • • • • • • • • • • •• 195
§ 4. Three lemmas about elementary embeddings •••••••••••••••••••• 197
4.1 Lemma 1
4.2 Lemma 2
4.3 Lemma 3
§ 5. The theorems of A. Robinson and Craig •••••••••••••
197
199
200
201
5.1 A. Robinson r s satisfiability theorem. • • • • • • • • • • • • • • • • • • • • •• 201
5.2 Craig r s interpolation lemma. • • • • • • • • • • • • • • • • • • • • • • • • • •• 203
Table of Contents XI
§ 6. Beth I s definability theorem. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 204
6.1 The notion of definability. • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 204
6.2 Beth I s definability theorem for a predicate variable • • • • • • • • • • •• 204
6.3 Beth I s definability theorem for a function variable • • • • • • • • • • • •• 206
IX. Miscellaneous. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 209
§ 1. Extended substitution. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 209
1. 1 Introduction • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 209
1. 2 The operations c:Y ~ and c:Y ~ ••••••••••••••••••••••••••••• 211
1.3 Applications. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 214
§ 2. The admissability of definitions • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 216
2.1 Statement of the problem •••••••••••••••••••••••••••••• 216
2.2 Simultaneous extended sustitution. • • • • • • • • • • • • • • • • • • • • • • •• 217
2.3 Substitution for a predicate variable. • • • • • • • • • • • • • • • • • • • • •• 222
§ 3. The process of relati visation • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 225
3. 1 Introduction • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 225
3.2 Theorems about relativisation • • • • • • • • • • • • • • • • • • • • • • • • • •• 225
Further Reading • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 229
Index of Abbreviations for Defining' and Derived Rules • • • • • • • • • • • • • • • • • •• 232
Notation. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 233
Name and Subject Index ••••••••••••••••••••••••••••••••••••••• 235
Recommended