Propositional calculus and first-order logic. Theorem proving, Model theory, soundness, completeness, and compactness, Herbrand’s theorem, Skolem-Lowenheim theorems, Craig interpolation. Theory of computation and recursive function theory, Church’s thesis, computability and undecidability. Feasible computability and complexity. Peano arithmetic and the incompleteness theorems, nonstandard models.
page