Mathematical Logic

Version 1.5

Volume I

Propositional and

First-Order Logic

Stefan Bilaniuk

Author address:

Department of Mathematics

Trent University

Peterborough, Ontario

Canada K9J 7B8

E-mail address: sbilaniuk@trentu.ca

1991 Mathematics Subject Classi¬cation. 03.

A Problem Course In Mathematical Logic

Volume I: Propositional and First-Order Logic

Version 1.5

Copyright c 1994“1999 by Stefan Bilaniuk.

Abstract. This is a text for a problem-oriented undergraduate

course in mathematical logic. It covers the basics of propositional

and ¬rst-order logic through the Soundness, Completeness, and

Compactness Theorems. Volume II, Computation, covers the ba-

sics of computability using Turing machines and recursive func-

tions, the Incompleteness Theorems, and complexity theory through

the P and NP.

Information on availabality and the conditions under which

this book may be used and reproduced are given in the preface.

This book was typeset using L TEX, using the AMS-L TEX and

A A

AMSFonts packages of the American Mathematical Society.

Contents

Preface v

Introduction 1

Propositional Logic 5

Chapter 1. Language 7

Chapter 2. Truth Assignments 11

Chapter 3. Deductions 15

Chapter 4. Soundness and Completeness 19

First-Order Logic 21

Chapter 5. Languages 23

Chapter 6. Structures and Models 33

Chapter 7. Deductions 41

Chapter 8. Soundness and Completeness 47

Chapter 9. Applications of Compactness 51

Hints 57

Chapter 1. Hints 59

Chapter 2. Hints 61

Chapter 3. Hints 63

Chapter 4. Hints 65

Chapter 5. Hints 67

Chapter 6. Hints 69

Chapter 7. Hints 71

iii

iv CONTENTS

Chapter 8. Hints 73

Chapter 9. Hints 75

Appendices 77

Appendix A. A Little Set Theory 79

Appendix B. The Greek Alphabet 81

Appendix C. Logic Limericks 83

Bibliography 85

Index 87

Preface

This book is intended to be the basis for a problem-oriented full-year

course in mathematical logic for students with a modicum of mathe-

matical sophistication. Volume I covers the basics of propositional and

¬rst-order logic through the Soundness, Completeness, and Compact-

ness Theorems, plus some material on applications of the Compactness

Theorem. It could easily be used for a one-semester course on these

topics. Volume II covers the basics of computability using Turing ma-

chines and recursive functions, the Incompleteness Theorem, and basic

complexity theory; it could also be used as for a one-semester course

on these topics.

In keeping with the modi¬ed Moore-method, this book supplies

de¬nitions, problems, and statements of results, along with some ex-

planations, examples, and hints. The intent is for the students, indi-

vidually or in groups, to learn the material by solving the problems

and proving the results for themselves. Besides constructive criticism,

it will probably be necessary for the instructor to supply further hints

or direct the students to other sources from time to time. Just how

this text is used will, of course, depend on the instructor and students

in question. However, it is probably not appropriate for a conventional

lecture-based course nor for a really large class.

The material presented in this volume is somewhat stripped-down.

Various concepts and topics that are often covered in introductory

mathematical logic courses are given very short shrift or omitted en-

tirely, among them normal forms, de¬nability, and model theory.1 In-

structors might consider having students do projects on additional ma-

terial if they wish to to cover it. A diagram giving the dependence of

the chapters in this volume can be found in the Introduction.

Acknowledgements. Various people and institutions deserve the

credit for this text: All the people who developed the subject. My

1

Future versions of both volumes may include more “ or less! “ material. Feel

free to send suggestions, corrections, criticisms, and the like ” I™ll feel free to ignore

them or use them.

v

vi PREFACE

teachers and colleagues, especially Gregory H. Moore, whose math-

ematical logic course convinced me that I wanted to do the stu¬.

The students at Trent University who su¬ered, su¬er, and will suf-

fer through assorted versions of this text. Trent University and the

taxpayers of Ontario, who paid my salary. Ohio University, where I

spent my sabbatical in 1995“96. All the people and organizations who

developed the software and hardware with which this book was pre-

pared. Anyone else I™ve missed.

Any blame properly accrues to the author.

Conditions. This book may be freely transmitted, stored, copied,

and used until 31 December, 2000, subject to the following restrictions:2

1. It may not be modi¬ed in any way without the express written

permission of the author.

2. It may not be sold at a pro¬t, but only to recover the cost of

reproduction.

3. After 31 December, 2000, it may no longer be reproduced, stored,

or transmitted in any form without the express written permis-

sion of the author, except that printed copies existing as of 31

December, 2000, may be retained and used after this date.

The reason for the time-limit is that I hope to improve this book

and make a new version available.3

Availability. The URL of the home page for A Problem Course

A

In Mathematical Logic, with links to L TEX, PostScript, and Portable

Document Format (pdf) ¬les of the latest available releases of both

volumes, is:

• http://www.trentu.ca/mathematics/sb/misc/pcml.html

A text-only information ¬le and LTEX, PostScript, and Portable Doc-

A

ument Format (pdf) ¬les of the latest release of both volumes can be

accessed by anonymous ftp in the directory:

• ftp://ftp.trentu.ca/pub/sbilaniuk/pcml/

Please note that in addition to LTEX you will need the AMS-L TEX

A A

and AMSFonts packages to typeset and print either volume.

If you have any problems, feel free to contact the author at the

addresses given on the title page, preferably by e-mail, for assistance

or even to ask for a paper copy.

Author™s Opinion. It™s not great, but the price is right!

2

If you violate these restrictions, I will be ¬‚attered, but you will still be in the

wrong.

3

Who knows, maybe even ¬nd a publisher . . .

Introduction

Mathematical Logic. What sets mathematics aside from other

disciplines is its reliance on proof as the principal technique for de-

termining truth, where science, for example, relies on (carefully ana-

lyzed) experience. So what is a proof? Practically speaking, it is any

reasoned argument accepted as a proof by other mathematicians.4 A

more precise de¬nition is needed, however, if one wishes to discover

what mathematical reasoning can accomplish in principle. This is one

of the reasons for studying mathematical logic, which is also pursued

for its own sake and ¬nding new tools to use in the rest of mathematics

and in related ¬elds.

In any case, mathematical logic is concerned with formalizing and

analyzing the kinds of reasoning used in the rest of mathematics. The

point of mathematical logic is not to try to do mathematics per se

completely formally ” the practical problems involved in doing so are

usually such as to make this an exercise in frustration ” but to study

formal logical systems as mathematical objects in their own right in

order to (informally!) prove things about them. For this reason, the

formal systems developed in this book are optimized to be easy to prove

things about, rather than to be easy to use. Natural deductive systems

such as those developed by philosophers to formalize logical reasoning

are equally capable in principle and much easier to actually use, but

harder to prove things about.

Part of the problem with formalizing mathematical reasoning is the

necessity of precisely specifying the language(s) in which it is to be

done. The natural languages spoken by humans won™t do: they are

so complex and continually changing as to be impossible to pin down

completely. By contrast, the languages which underly formal logical

systems are, like programming languages, much simpler and less ¬‚exible

than natural languages but rigidly de¬ned. A formal logical system also

requires the careful speci¬cation of the allowable rules of reasoning, plus

some notion of how to interpret statements in the underlying language

4

If you are not a mathematician, gentle reader, you are hereby temporarily

promoted.

1

2 INTRODUCTION

and determine their truth. The real fun lies in the relationship between

interpretation of statements, truth, and reasoning.

This volume develops the basics of two kinds of formal logical sys-

tems, propositional logic and ¬rst-order logic. Propositional logic at-

tempts to make precise the relationships that certain connectives like

not, and , or , and if . . . then are used to express in English. While it

has uses, propositional logic is not powerful enough to formalize most

mathematical discourse. For one thing, it cannot handle the concepts

expressed by all and there is. First-order logic adds all and there is to

those which propositional logic could handle, and su¬ces, in principle,

to formalize most mathematical reasoning. To be sure, it will not han-

dle concepts which arise outside of mathematics, such as possible and

relevant, among many others. (Trying to incorporate such concepts

into systems extending ¬rst-order logic is a substantial industry in phi-

losophy, but of marginal interest in mathematics.) Propositional logic,

which is much simpler, will be dealt with ¬rst in order to gain some

experience in dealing with formal systems before tackling ¬rst-order

logic. Besides, some of the results about propositional logic carry over

to ¬rst-order logic with little change.

Approach. This book supplies de¬nitions and statements of re-

sults, plus some explanations and a number of problems and examples,

but no proofs of the results. The hope is that you, gentle reader, will

learn the material presented here by solving the problems and proving

the results for yourself. Brief hints are supplied for almost all of the

problems and results, but if these do not su¬ce, you should consult

your peers, your instructor, or other texts.

Prerequisites. In principle, not much is needed by way of prior

mathematical knowledge to de¬ne and prove the basic facts about

propositional and ¬rst-order logic. Some knowledge of the natural

numbers and a little set theory su¬ces; the former will be assumed

and the latter is very brie¬‚y summarized in Appendix A. What re-

ally is needed to get anywhere with the material developed here is

competence in handling abstraction and proofs, especially proofs by

induction. The experience provided by a rigorous introductory course

in algebra, analysis, or discrete mathematics ought to be su¬cient.

Some problems and examples draw on concepts from other parts of

mathematics; students who are not already familiar with these should

consult texts in the appropriate subjects for the necessary de¬nitions.

Other Sources and Further Reading. [4], [8], and [9] are texts

which go over similar ground (and much more), while [1] and [3] are

INTRODUCTION 3

good references for more advanced material. Entertaining accounts of

some related topics may be found in [7] and [10]. Those interested

in natural deductive systems might try [2], which has a very clean

presentation.

Credit. Almost no attempt has been made to give due credit to

those who developed and re¬ned the ideas, results, and proofs men-

tioned in this work. In mitigation, it would often be di¬cult to assign

credit fairly because many people were involved, frequently having in-

teracted in complicated ways. (Which really means that I™m too lazy

to do it. I apologize to those who have been hurt by this.) Those

interested in who did what should start by consulting other texts or

reference works covering similar material.

Chapter Dependencies. The following diagram indicates how

the chapters in this volume depend on one another, with the excep-

tion of a few isolated problems or results.

1

¨r

¨¨ rr