CP8201: Recommended reading
This page lists material that student might wish to read
in addition to the lecture notes. The following
abbreviations are used below:
[BBJ] Boolos, Burgess, Jeffrey "Computability and Logic", 5th edition,
Cambridge University Press, 2007.
[EM] Elliot Mendelson "Introduction to Mathematical Logic", 4th edition,
published by Chapman & Hall, 1997.
[HE] Herbert Enderton "Computability Theory", 1st edition,
published by Elsevier, 2011.
Electronic version.
[MBA] Mordechai BenAri
"Mathematical Logic For Computer Science", corrected 2nd edition,
Springer 2008.
[MD] Martin Davis "Computability and Unsolvability", Dover Publications, 1982.
[PS] Peter Smith "An Introduction to Godel's Theorems",
Cambridge University Press, 2007.
[SC] Stephen Cook
``
CSC 438F/2404F: Computability and Logic'', Lecture Notes, Fall
2008.
[SS] Stephen Simpson
Lecture Notes on Mathematical Logic for MATH557.
MATH 557 is an introductory graduatelevel course on mathematical logic
at Penn State University.
[US] Uwe Schonning "Logic for computer scientists".
Publisher Boston : Birkhauser, 1999.
Electronic
version.

September 4: Introduction. Brief review of functions, relations,
cartesian products of sets. The primitive recursive (p.r.) functions:
basic functions (zero, successor, identity) closed under operations of
composition and primitive recursion. Examples: constant functions,
addition, multiplication, factorial, signum, truncated subtraction,
and so on. The p.r. functions
are effectively computable using a sequence of possibly nested
"for"loops. Not all effectively computable functions are p.r.:
Cantor's diagonal argument. Introduction to murecursive functions.
Regular functions. Unbounded "whiledo"loops computing the value of
h(x) as the minimal value when a regular function becomes 0 for
the first time. Read the handout. Also, read [HE]: Section 1.2.2 (pages
1822) and Chapter 2, Items 111 (pages 2935).
[BBJ]: Chapter 6 [PS]: Chapter 11.

September 11:
(\mu)Recursive Functions. a finite sum and product of (primitive)
recursive functions are (primitive) recursive. Recursive Sets and
Relations: characterisic function. Function defined by cases,
substitution of (primitive) recursive functions into a (primitive)
recursive relation. Negation, disjunction, conjunction,
bounded existential and universal quantification of
(primitive) recursive relation(s) is a (primitive) recursive relation.
Bounded minimization (maximization) and bounded search. Examples:
lessthan relation, equality, max(x,y) and min(x,y) function, "m divides n"
relation, remainder and quotient, number of divisors relation,
prime numbers. Read: [BBJ] Chapter 6 and Section 7.1.
[PS]: Chapters 11, 29. [HE]: Sections 2.1, items 915, and Section 2.2
(pages 4749). Examples of Recursive Functions. [EM]: Section 3.3.

September 18:
Recursively Enumerable Sets. Enumerability using lists and using (general)
recursive functions. The methods to prove enumerability: examples.
Cantor's zigzag method for enumerating pairs of positive integers.
Baseb encoding. Shuffling of enumerable sets. Prime decomposition. The set
of all sets is not enumerable. Diagonalization. [BBJ] Chapters 1 and 2.
Encoding string of numbers by a single number using a p.r. encoding function.
Decoding function (returns ith element of the string) is also p.r.
Sequence numbers. A p.r. function lh(x) computing the number of the initial
nonzero prime factors. Concatenation of strings of natural numbers.
Read [HE]: Chapter 2, Section 2.1.1, items 1624. [BBJ]: Example 7.11.
Kleene Normal Form for recursive functions: \muminimization is needed
only once.

September 25: Turing Computability.
[EM]: Section 5.1 and [MD]: Sections 1.1 and 1.2. You can read
also [BBJ]: Chapter 3.
2009 editition of this course
[SK] Stephen Kleene ``An Introduction to Metamathematics" (any edition).
[RS] Raymond M. Smullyan ``FirstOrder Logic", Dover, 1995.

September 15:
Introduction. Review of background [read handout].
PrimitiveRecursive Functions.
[BBJ]: Chapter 6
[PS]: Chapter 11.
[SK]: Section 43.

September 22:
PrimitiveRecursive Functions.
Recursive Functions.
Recursive Sets and Relations.
[BBJ]: Chapter 6 and Section 7.1.
[PS]: Chapters 11, 29.
Examples of Recursive Functions.
[EM]: Section 3.3.
[SK]: Sections 44, 45.
Dr. Gianluigi Bellin's handout on primitive recursive functions.

September 29:
Recursive Functions and Relations, examples: [SK] Section 45.
The AckermannPeter function: [SK] Section 55, [PS] Section 29.3.
Kleene Normal Form: [SK] Section 58.
Recursively Enumerable Sets.
Enumerability. Diagonalization. [BBJ] Chapters 1 and 2.
 October 6: Turing Computability.
[EM]: Section 5.1 and [MD]: Sections 1.1 and 1.2. You can read
also [BBJ]: Chapter 3.
Side reading (not required): Patrick Hayes and Kenneth Ford
Turing Test Considered Harmful, in the proceedings of the
International Joint Conference on AI (IJCAI1995), Montreal Canada,
August 2025, 1995.

October 13:
Examples of Turing Computable Functions. Basic p.r. functions are
Turing computable (successor, zero, identity).
[EM]: Section 5.1 and [MD]: Sections 1.2 and 1.3. Read also examples in
[BBJ]: Chapter 3.
Enumeration of Turing Machines. Diagonal function is not Turing
computable. [BBJ], Chapter 4. [PS]: Sections 33.1 and 33.2

October 20:
Uncomputability (The Halting Problem). [BBJ], Chapter 4.
Theorem: "Every recursive function is Turing
computable" (using dextral Turing machines).
[PS]: Chapter 32.
Theorem: "Every unary Turing computable function is recursive".
[BBJ]: Section 8.1. For arbitrary nplace functions see [MD]:Section
4.1 (not required).
(Extra class on Friday October 23rd)
Finish the proof that every unary Turing computable function
is recursive. Universal Turing machines.
Kleene normal form theorem
[BBJ]: Section 8.2. [PS]: Section 33.6.

October 27:
Semirecursive relations [BBJ] Section 7.2
Recursively enumerable sets [BBJ] Section 8.3
Propositional logic: [RS] Chapter 1 and [MBA] Chapter 2.
You can also find all definitions, theorems and many examples in
Stephen Simpson's lecture notes on mathematical logic:
Read Chapter 1, pages 322.

November 3 Midterm test (in class).
Semantic Tableau: construction. Soundness theorem.
[MBA]: Chapter 2. You can also read [RS]: Chapters 2 and 3.

November 10.
Completeness theorem for semantic tableau. [MBA]: Chapter 2.
A brief summary is provided in S.Simpson's lecture notes
pages 1822.
Introduction to first order logic. Basic Semantic Definition.
[SC]
Predicate Calculus, pages 1822. You can find an excellent
introduction to FOL in [EM]: Sections 2.1 and 2.2.
You can also read S.Simpson's lecture notes
pages 2530.

November 17.
Semantics of FOL: satisfiability, logical consequence, validity.
Logical equivalence: examples. Note that we used in class the symbol <=>
from metalanguage to say that sentences A and B are logically equivalent:
A <=> B (i.e., A and B have same models). Please use the symbol <> as the
equivalence connective when you
write formulas, e.g. (A <> B), in the FOL "object language".
Substitution in terms and in formulas, a term freely
substitutable for a variable in a formula, substitution theorem.
[SC]
Predicate Calculus, pages 23  27. Read also
Chapter 6 (pages 3339) from Stefan Bilaniuk's
A Problem Course in
Mathematical Logic (LaTeX source is available too).
There are several related articles in Stanford Encyclopedia
of Philosophy, e.g., read
Semantics in the entry on classical logic (by Stewart Shapiro) and
Firstorder languages and structures in the entry
Firstorder Model Theory (by Wilfrid Hodges).
Proofs in FOL. Semantic tableau: examples, Gammarules, Deltarules,
systematic construction of semantic tableau, soundness and completeness.
Godel completeness theorem for FOL. Read [MBA], Section 5.5.
Also, consult Dr. D.Delic's handouts about semantic tableau that
he prepared for his undegraduate course
MTH714 (Logic and Computability):
read Section 2.6 (tableau in propositional logic) and
read Section 5.5 (tableau in FOL); you may skip other sections.
Konig Lemma, Compactness theorem (countable case only).
Read [SS], Sections 1.6 & 1.7 (pages 2021: propositional logic)
and Section 2.6 (page 46: FOL).
Theorem: if a language L is finite, then
the set of valid Lsentences is r.e. (i.e., semidecidable or
semirecursive). Recall a definition of a recursive
set and the complementation principle from your lecture notes
(see also [BBJ] Section 7.2): a set X is recursive iff both X and
the complement of X are r.e.

November 24. Read S. Cook's 2006 Notes:
Herbrand theorem (pages 5152, Nonstandard Models). In addition,
you might wish to read (not required) H.Enderton's book "A mathematical
introduction to logic", Section 3.1 (theory of successor) and Section 3.2
(Presburger arithmetics).
Also, read
Incompleteness and Undecidability: Representing relations by
formulas (pages 8195, but we skipped in class the proof of Exists Delta
Theorem because of lack of time) and
The Peano Arithmetic theory (PA) (pages 9699).

December 1.
Robinson Arithmetics: RA Representation Theorem: pages 99102.
Main Lemma and its Corollaries. Results for Consistent (possibly
unsound theories): pages 105108. Godel's Incompleteness Theorems.
Read S. Cook's 2008 Lecture Notes, pp109112.
You can read also S.Simpson's paper
Partial Realizations of Hilbert's Program.
It was published in 1988 in the Journal of Symbolic Logic, volume 53,
pages 349363 and it is available from S.Simpson's Web page in a various
formats. Extra reading: [BBJ], Chapter 18 (not required).
CP8201: Algorithms and Computability.