Terms and Conditions:

Stefan Bilaniuk wrote:See the GNU Free Documentation License in Appendix D for what you can do with this text. The gist is that you are free to copy, distribute, and use it unchanged, but there are some restrictions on what you can do if you wish to make changes. If you wish to use this text in a manner not covered by the GNU Free Documentation License, please contact the author.

Book Excerpts:

This book is a free text intended to be the basis for a problem-oriented course(s) in mathematical logic and computability for students with some degree of mathematical sophistication. Parts I and II cover the basics of propositional and first-order logic respectively, Part III covers the basics of computability using Turing machines and recursive functions, and Part IV covers Godel's Incompleteness Theorems. They can be used in various ways for courses of various lengths and mixes of material. The author typically uses Parts I and II for a one-term course on mathematical logic, Part III for a one-term course on computability, and/or much of Part III together with Part IV for a one-term course on computability and incompleteness.

In keeping with the modified Moore-method, this book supplies definitions, problems, and statements of results, along with some explanations, examples, and hints. The intent is for the students, individually 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 text is somewhat stripped-down. Various concepts and topics that are often covered in introductory mathematical logic and computability courses are given very short shrift or omitted entirely. Instructors might consider having students do projects on additional material if they wish to to cover it.

Prerequisites:

The material in this text is largely self-contained, though some knowledge of (very basic) set theory and elementary number theory is assumed at several points. A few 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 definitions. What is really needed to get anywhere with all of the material developed here is competence in handling abstraction and proofs, including proofs by induction. The experience provided by a rigorous introductory course in abstract algebra, analysis, or discrete mathematics ought to be sufficient.

More Resources:

• The book's webpage at the Department of Mathematics at Trent University