. 1
( 10 .)



>>

A Problem Course
in
Mathematical Logic

Volume II
Computability and Incompleteness

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 II: Computability and Incompleteness
Version 1.3
Copyright c 1994-1997 by Stefan Bilaniuk.

Abstract. This is the Volume II of a text for a problem-oriented
undergraduate course in mathematical logic. It covers the basics
of computability, using Turing machines and recursive functions,
and G¨del™s Incompleteness Theorem, and could be used for a one-
o
semester course on these topics. Volume I, Propositional and First-
Order Logic, covers the basics of these topics through the Sound-
ness, Completeness, and Compactness Theorems.
Information on availability 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

Computability 5
Chapter 10. Turing Machines 7
Chapter 11. Variations and Simulations 13
Chapter 12. Universal Turing Machines and the Halting Problem 17
Chapter 13. Computable and Non-Computable Functions 25
Chapter 14. Primitive Recursive Functions 29
Chapter 15. Recursive Functions 35

Incompleteness 41
Chapter 16. Preliminaries 43
Chapter 17. Coding First-Order Logic 45
Chapter 18. De¬ning Recursive Functions In Arithmetic 49
Chapter 19. The Incompleteness Theorem 53

Hints 57
Chapter 10. Hints 59
Chapter 11. Hints 61
Chapter 12. Hints 63
Chapter 13. Hints 65
Chapter 14. Hints 67
Chapter 15. Hints 69
iii
iv CONTENTS

Chapter 16. Hints 71
Chapter 17. Hints 73
Chapter 18. Hints 75
Chapter 19. Hints 77
Bibliography 79
Index 81
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 II covers the basics of computability,
using Turing machines and recursive functions, and incompleteness.
It could be used for a one-semester course on these topics. Volume
I covers the basics of propositional and ¬rst-order logic through the
Soundness, Completeness, and Compactness Theorems, plus some ma-
terial on applications of the Compactness Theorem; it could also be
used as for a one-semester course on these topics. However, part of
Volume II, particularly the chapters on incompleteness, assume some
familiarity with the basics of ¬rst-order logic.
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 here is somewhat stripped-down. Various
concepts and topics that are often covered in introductory courses on
computability are given very short shrift or omitted entirely, among
them models of computation other than Turing machines and recursive
functions, formal languages, and computational complexity.1 Instruc-
tors might consider having students do projects on additional material
if they wish to cover it. It might also be expedient, in view of the
somewhat repetitive nature of devising Turing machines and recursive
functions for various purposes, to be selective about the problems the
students are required to do or to divide them up among the students.
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

Acknowledgements. Various people and institutions deserve the
credit for this text: All the people who developed the subject. My
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, 1998, 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, 1998, 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, 1998, 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
In Mathematical Logic, with links to L TEX and PostScript source ¬les
A

of the latest release of both volumes, is:
• http://www.trentu.ca/academic/math/sb/misc/pcml.html
A text-only information ¬le and LTEX and PostScript source ¬les of
A

the latest release of both volumes can be accessed by anonymous ftp
at:
• 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.
2
If you violate these restrictions, I will be ¬‚attered, but you will still be in the
wrong.
3
Who knows, it might even ¬nd a publisher . . .
PREFACE vii

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

The Entscheidungsproblem. Recall that a logic satis¬es the
Completeness Theorem if, whenever the truth of a set of sentences
Σ implies the truth of a sentence •, there is a deduction of • from
Σ. Propositional and ¬rst-order logics both satisfy the Completeness
Theorem, though second- and higher-order logics do not. In the case
of propositional logic, the Completeness Theorem leads to a rote pro-
cedure for determining whether Σ • or not, so long as Σ is ¬nite:
write out a complete truth table for all of Σ together with • and check
whether every assignment that makes every sentence of Σ true also
makes • true. It is natural to ask whether something of the sort can
be done for ¬rst-order logic. If so, it might be very useful: since most
of mathematics can be formalized in ¬rst-order logic, such a method
would have the obvious use of putting mathematicians out of business
. . . This question is the general Entscheidungsproblem 4 for ¬rst-order
logic:
Entscheidungsproblem. Given a set Σ of formulas of a ¬rst-
order language L and a formula • of L, is there an e¬ective method
for determining whether or not Σ •?
Of course, the statement of the problem begs the question of what
“e¬ective” is supposed to mean here. In this volume we™ll explore
two formalizations of the notion of “e¬ective method”, namely Tur-
ing machines and recursive functions, and then use these to answer
the Entscheidungsproblem for ¬rst-order logic. The answer to the gen-
eral problem is negative, though decision procedures do exist for some
particular ¬rst-order languages and sets Σ.
Historically, the Entscheidungsproblem arose out of David Hilbert™s
scheme to secure the foundations of mathematics by axiomatizing math-
ematics in ¬rst-order logic and showing that the axioms do not give rise
to any contradictions. It did so in two related ways. First, given some
plausible set of axioms, it is necessary to show that they do not lead
to a contradiction, such as ± § (¬±). Second, it is desirable to know

Entscheidungsproblem ≡ decision problem.
4


1
2 INTRODUCTION

whether such a set of axioms is complete; i.e. given any sentence • of
the language, that the axioms either prove or disprove •.
In the course of trying to ¬nd a suitable formalization of the no-
tion of “e¬ective method”, mathematicians developed several di¬erent
abstract models of computation in the 1930™s, including recursive func-
tions, »-calculus, Turing machines, and grammars. Although these
models are very di¬erent from each other in spirit and formal de¬ni-
tion, it turned out that they were all essentially equivalent in what they
could do. This suggested the (empirical!) principle:
Church™s Thesis. A function is e¬ectively computable in princi-
ple in the real world if and only if it is computable by (any) one of the
abstract models mentioned above.
Of course, this is not a mathematical statement . . . We will study
Turing machines and recursive functions, and then use this knowledge
to formulate and answer a more precise version of the general Entschei-
dungsproblem for ¬rst-order logic.
The development of the theory of computation actually began be-
fore the development of electronic digital computers. In fact, the com-
puters and programming languages we use today owe much to the ab-
stract models of computation which preceded them. For two, the stan-
dard von Neumann architecture for digital computers was inspired by
Turing machines and the programming language LISP borrows much
of its structure from »-calculus.
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, little is needed by way of prior math-
ematical knowledge to de¬ne and prove the basic facts about com-
putability. Some knowledge of the natural numbers and a little set the-
ory su¬ces. The material leading up to the Incompleteness Theorem
” the resolution of the general Entscheidungsproblem for ¬rst-order
logic ” does require grounding in ¬rst-logic, such as that provided in
Volume I, as well as in computability.
What really is needed to get anywhere with all of the material
developed here is competence in handling abstraction and proofs, in-
cluding proofs by induction. The experience provided by a rigorous
INTRODUCTION 3

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. [3], [5], [7], and [8] are
texts which go over at least some of the material, while [1] is a good
if terse reference for more advanced material. Entertaining accounts of
much of the material may be found in [6] and [9]; the latter discusses
the possibility that Church™s Thesis may not be true. Many of the
original sources for the material in this volume can be found in the
anthology [4].
4 INTRODUCTION
Computability
CHAPTER 10


Turing Machines

Of the various ways to formalize the notion an “e¬ective method”,
the most commonly used are the simple abstract computers called Tur-

. 1
( 10 .)



>>