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