Introduction To Mathematical Logic (Extended Edition)

by Michal Walicki

Overview

This is a systematic and well-paced introduction to mathematical logic. Excellent as a course text, the book presupposes only elementary background and can be used also for self-study by more ambitious students.Starting with the basics of set theory, induction and computability, it covers propositional and first order logic — their syntax, reasoning systems and semantics. Soundness and completeness results for Hilbert's and Gentzen's systems are presented, along with simple decidability arguments. The general applicability of various concepts and techniques is demonstrated by highlighting their consistent reuse in different contexts.Unlike in most comparable texts, presentation of syntactic reasoning systems precedes the semantic explanations. The simplicity of syntactic constructions and rules — of a high, though often neglected, pedagogical value — aids students in approaching more complex semantic issues. This order of presentation also brings forth the relative independence of syntax from the semantics, helping to appreciate the importance of the purely symbolic systems, like those underlying computers.An overview of the history of logic precedes the main text, while informal analogies precede introduction of most central concepts. These informal aspects are kept clearly apart from the technical ones. Together, they form a unique text which may be appreciated equally by lecturers and students occupied with mathematical precision, as well as those interested in the relations of logical formalisms to the problems of computability and the philosophy of logic.This revised edition contains also, besides many new exercises, a new chapter on semantic paradoxes. An equivalence of logical and graphical representations allows us to see vicious circularity as the odd cycles in the graphical representation and can be used as a simple tool for diagnosing paradoxes in natural discourse.

Product Details

ISBN-13:	9789814719964
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	10/03/2016
Pages:	304
Product dimensions:	5.90(w) x 8.90(h) x 0.70(d)

Table of Contents

Acknowledgments vii

A History of Logic 1

A Patterns of Reasoning 2

A.1 Reductio Ad Absurdum 2

A.2 Aristotle 3

A.3 Other Patterns and Later Developments 8

B A Language and its Meaning 9

B.1 Early Semantic Observations and Problems 10

B.2 The Scholastic Theory Of Supposition 11

B.3 Intension vs. Extension 11

B.4 Modalities 12

C A Symbolic Language 14

C.1 The "Universally Characteristic Language" 15

C.2 Calculus of Reason 15

D 1850-1950 - Mathematical Logic 17

D.1 George Boole 18

D.2 Gottlob Frege 22

D.3 Set Theory 25

D.4 20th Century Logic 27

E Modern Symbolic Logic 30

E.1 Formal Logical Systems: Syntax 30

E.2 Formal Semantics 34

E.3 Computability and Decidability 37

F Summary 41

Part I Elements of Set Theory 43

1 Sets, Functions, Relations 45

1.1 Sets and Functions 45

1.2 Relations 52

1.3 Ordering Relations 54

1.4 Infinities 56

Exercises 1 63

2 Induction 65

2.1 Well-Founded Relations 65

2.1.1 Inductive Proofs 68

2.2 Inductive Definitions 73

2.2.1 "1-1" Definitions 77

2.2.2 Recursive Programming [Optional] 79

2.2.3 Proofs by Structural Induction 82

2.3 Transfinite Induction [Optional] 87

Exercises 2 89

Part II Turing Machines 95

3 Computability and Decidability 97

3.1 Alphabets and Languages 97

3.2 Turing Machines 99

3.2.1 Composing Turing Machines [Optional] 105

3.3 Universal Turing Machine 107

3.4 Undecidability 110

Exercises 3 114

Part III Prepositional Logic 117

4 Syntax and Proof Systems 119

4.1 Axiomatic Systems 119

4.2 Propositional Syntax 125

4.3 Hilbert's Axiomatic System H 126

4.4 The Axiomatic System N 129

4.5 Provable Equivalence 131

4.6 Consistency 133

4.7 H Versus N 135

4.8 Gentzen's Axiomatic System G 136

4.8.1 Decidability of PL 136

4.8.2 Rules for Abbreviated Connectives 138

4.9 Some Proof Techniques 139

Exercises 4 140

5 Semantics of PL 143

5.1 The Boolean Semantics 143

5.1.1 Syntactic Abbreviations 150

5.2 Semantic Properties 151

5.2.1 Some Propositional Laws 152

5.3 Set-Based Semantics 153

5.3.1 Sets and Propositions 154

5.3.2 Boolean Algebras [Optional] 157

Exercises 5 159

6 Soundness and Completeness 163

6.1 Expressive Completeness 163

6.2 Disjunctive and Conjunctive Normal Forms 166

6.2.1 CNF, Clauses and Sat [Optional] 167

6.3 Soundness 170

6.4 Completeness 174

6.5 Some Applications 178

Exercises 6 179

7 Diagnosing Paradoxes 185

7.1 Semantic Paradoxes 186

7.2 Finitary Paradoxes are Circular 187

7.3 Acyclic Paradoxes and Infinttary Logic 191

7.4 GNF and Sat 193

Exercises 7 194

Part IV First Order Logic 197

8 Syntax and Proof Systems of FOL 199

8.1 Syntax of FOL 201

8.2 Scope of Quantifiers 204

8.2.1 Some Examples 206

8.2.2 Substitution 209

8.3 The Axiomatic System N 211

8.3.1 Deduction Theorem in FOL 213

8.4 Gentzen's System for FOL 215

Exercises 8 217

9 Semantics of FOL 221

9.1 The Basic Definitions 221

9.2 Semantic Properties 227

9.3 Open vs. Closed Formulae 229

9.3.1 Deduction Theorem in Q and N 232

Exercises 9 234

10 More Semantics 237

10.1 Prenex Normal Form 237

10.1.1 PNF Hierarchy 241

10.2 Substructures: An Example from Model Theory 242

10.3 "Syntactic" Semantics 245

10.3.1 Reachable and Term Structures 246

10.3.2 Herbrand's Theorem 251

10.3.3 Horn Clauses 252

10.3.4 Herbrand Models of Horn Theories 253

10.3.5 Computing With Horn Clauses 255

10.3.6 Computational Completeness 257

Exercises 10 259

11 Soundness and Completeness 261

11.1 Soundness of AF 261

11.2 Completeness of N 262

11.2.1 Completeness of Gentzen's System [Optional] 268

11.3 Some Applications 270

Exercises 11 274

Why Is First Order Logic "First Order"? 277

Index 281

Index of Symbols 285

The Greek Alphabet 287