ELEMENTARY RECURSION THEORY AND ITS APPLICATIONS
TO FORMAL SYSTEMS
By Professor Saul Kripke
Department of Philosophy, Princeton University
Notes by Mario Gómez-Torrente,
revising and expanding notes by John Barker
Copyright © 1996 by Saul Kripke. Not for reproduction or quotation without express
permission of the author.
Elementary Recursion Theory. Preliminary Version
Copyright © 1995 by Saul Kripke
i
CONTENTS
Lecture I
1
First Order Languages / Eliminating Function Letters / Interpretations / The
Language of Arithmetic
Lecture II
8
The Language RE / The Intuitive Concept of Computability and its Formal
Counterparts / The Status of Church's Thesis
Lecture III
18
The Language Lim / Pairing Functions / Coding Finite Sequences
Lecture IV
27
Gödel Numbering / Identification / The Generated Sets Theorem / Exercises
Lecture V
36
Truth and Satisfaction in RE
Lecture VI
40
Truth and Satisfaction in RE (Continued) / Exercises
Lecture VII
49
The Enumeration Theorem. A Recursively Enumerable Set which is Not Recursive /
The Road from the Inconsistency of the Unrestricted Comprehension Principle to
the Gödel-Tarski Theorems
Lecture VIII
57
Many-one and One-one Reducibility / The Relation of Substitution / Deductive
Systems / The Narrow and Broad Languages of Arithmetic / The Theories Q and
PA / Exercises
Lecture IX
66
Cantor's Diagonal Principle / A First Version of Gödel's Theorem / More Versions
of Gödel's Theorem / Q is RE-Complete
Lecture X
73
True Theories are 1-1 Complete / Church's Theorem / Complete Theories are
Decidable / Replacing Truth by ω-Consistency / The Normal Form Theorem for RE
Elementary Recursion Theory. Preliminary Version
Copyright © 1995 by Saul Kripke
ii
/ Exercises
Lecture XI
81
An Effective Form of Gödel's Theorem / Gödel's Original Proof / The
Uniformization Theorem for r.e. Relations / The Normal Form Theorem for Partial
Recursive Functions
Lecture XII
87
An Enumeration Theorem for Partial Recursive Functions / Reduction and
Separation / Functional Representability / E