文档介绍：A Problem Course
in
Mathematical Logic
Volume II
Computability and pleteness
Stefan Bilaniuk
Department of Mathematics
Trent University
Peterborough, Ontario
Canada K9J 7B8
E-mail address: ******@
1991 Mathematics Subject Classification. 03
Key words and phrases. computability, Turing machines, recursive
functions, pleteness
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’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-LATEX and
AMSFonts packages of the American Mathematical Society.
Contents
iii
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 putability,
using Turing machines and recursive functions, and pleteness.
It could be used for a one-semester course on these topics. Volume
I covers the basics of propositional and first-order logic through the
Soundness, Completeness, pactness Theorems, plus some ma-
terial on applications of pactness Theorem; it could also be
used as for a one-semester course on these topics. However, part of
Volume II, particularly the chapters on pleteness, assume some
familiarity with the basics of first-order logic.
In keeping with the modified Moore-method, this book supplies
definitions, probl