This page contains keywords and key-phrases characterizing
individual lectures so that it is easier to find relevant places
in the literature suggested on
the main course page.
In particular, material from
Lectures 1-6 can be found in van den Dries's
lecture notes (Chpt. 2 and Secs.3.1-2 and 4.1),
Lectures 7 and 8 in
Chpts.3 and 4 in Sipser's book,
Lectures 8 (part about PA and Q),
9 and 10: almost all suggested books contain
relevant material but in none of them it is presented and
organized (and used for the proof) as we are
doing it. So I wrote several short notes
on the key points:
- PA and Q,
-
Sigma_1-completeness of Q,
-
Delta_0-definable functions,
- coding sequences,
- Sigma_1-definability of RE sets,
- Godel's First Incompleteness
Theorem,
-
unsolvability of Hilbert's Entscheidungsproblem.
[Possible corrections will be marked in yellow directly in the
pdf files.]
Lecture 11: Smorynski's paper
(first 8 pages only) for Godel's original proof and his Second theorem
and Chaitin's paper for another proof
of the First theorem using the notion of Kolmogorov complexity.
Further texts are at the
Spring 2011 Babylogic page.
For links between Hilbert's problems and computational complexity
see the page of the Logic and Complexity course
and, in particular, Godel's 1956 letter to
von Neumann.
Lecture 1 (29.IX.2021)
A review of propositional logic:
atoms, propositional connectives, formulas, DeMorgan language.
The unique readability lemma, prefix notation.
Boolean functions and their representability by formulas,
DNF and CNF formulas. Size of formulas.
Boolean functions and properties of finite strings. Strings
represent finite "mathematical objects" (finite graphs,
integers, equations, formulas, ...).
Lecture 2 (6.X.2021)
(Prop.logic cont'd.)
HW: CNFs.
Logical consequences,
satisfiable and logically valid formulas (tautologies), sets
SAT and TAUT.
Logically equivalent formulas, DeMorgan rules, implication and equivalence
connectives, the deduction lemma.
Deciding the satisfiability, the P vs. NP problem.
Ex. of a p-reduction to SAT: 3-colorability of finite graphs.
Propositional theories and their logical consequences. Compactness
theorem for propositional logic. Ex.: 3-colorability of infinite graphs.
Lecture 3 (13.X.2021)
A review of first-order logic.
Syntax: languages, terms, formulas,
free and bound occurrences of var's,
sentences, theories. Ex.: RCF (real closed fields).
Semantics: FO-structures, Tarski's satisfiability relation,
ex.: the real closed field.
Models of theories, logical consequences of a theory.
Lecture 4 (20.X.2021)
Logically valid formulas and
the Entscheidungsproblem.
Predicate calculus: axioms and inference rules. Deduction lemma,
consistent theories.
The completeness theorem, its alternative formulation, the soundness
direction.
Lecture 5 (3.XI.2021)
Proof of the Completeness theorem via Henkin's construction
and Lindenbaum's lemma.
Lecture 6 (10.XI.2021)
Consequences of the Completeness theorem and its proof:
the Compactness theorem and the Lowenheim-Skolem theorem.
Some applications: Vaught's test, non-standard models of
the ring of integers and of the ordered field of reals.
HW: explain Skolem paradox.
Lecture 7 (24.XI.2021)
Hilbert's program and the Entscheidungsproblem. Church-Turing thesis.
Turing machines, recursive (= computable) sets (R) and functions (RF),
partial recursive functions (PRF), r.e. sets (RE).
Decision problems and their decidability.
Hilbert's 10th problem (DIOF) and
the Halting problem (HALT). DIOF \in RE.
HW: Non-empty RE sets are exactly ranges of RF.
Lecture 8 (1.XII.2021)
Universal Turing machine and HALT \in RE. Undecidability of HALT.
Many-one reducibility.
Recursive theories,
from completeness to decidability.
Peano arithmetic PA and
Robinson arithmetic Q. PA and finite set theory (ZF_{fin}).
Lecture 9 (8.XII.2021)
Bounded quantifiers and bounded (= Delta_0-) and Sigma_1-formulas.
Sigma_1-completeness of Q.
Delta_0-definable functions, coding of k-tuples.
Computable (many-one) reducibilities, undecidability
of sets to which HALT reduces.
Chinese remainder theorem.
Lecture 10 (15.XII.2021)
Godel's beta function, coding of finite sequences.
Sigma_1-definability of all RE sets.
Godel's First Incompleteness Theorem and its proof.
Unsolvability of the Entscheidungsproblem.
Lecture 11 (5.I.2022)
Ideas in Godel's original proof (including his diagonal lemma)
and his Second Incompleteness Theorem.
An alternative argument via Kolmogorov's complexity.
Undefinability of truth (Tarski).
Variants of Hilbert's foundational problems (of the
Entscheidungsproblem, in particular)
and computational complexity, and Godel's 1956 letter to
von Neumann
(more in Logic and Complexity course).