文档介绍：A Problem Course
in
Mathematical Logic
Volume II
Computability and pleteness
Stefan Bilaniuk
Author address:
Department of Mathematics
Trent University
Peterborough, Ontario
Canada K9J 7B8
E-mail address: ******@
1991 Mathematics Subject Classification. 03.
A Problem Course in Mathematical Logic
Volume II: Computability and pleteness
Version
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
putability, using Turing machines and recursive functions,
and G¨odel’s pleteness Theorem, and could be used for a one-
semester course on these topics. Volume I, Propositional and First-
Order Logic, covers the basics of these topics through the Sound-
ness, Completeness, pactness 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 LATEX, using the AMS-LATEXand
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 putable Functions 25
Chapter 14. Primitive Recursive Functions 29
Chapter 15. Recursive Functions 35
pleteness 41
Chapter 16. Preliminaries 43
Chapter 17. Coding First-Order Logic 45
Chapter 18. Defining Recursive Functions In Arithmetic 49
Chapter 19. The pleteness 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 fo