Computability and Logic

Undergraduate catalogue

Proofs of some of the principal results regarding first-order languages (and the theories expressed in them): Church's undecidability theorem, the Lowenheim-Skolem Theorem, Gödel's theorems on the completeness of first-order logic and the incompleteness of arithmetic; because several of these concern the possibility of devising computational tests for semantic properties (logical validity, truth), an introduction to the theory of computability (Turing Machines/recursive functions); if time permits, some properties of second-order logic. Two 90-minute classes.