Preliminary Material
Preliminary logic primer, P. Madhusudan (for CS173)
Notes on induction on natural numbers, P. Madhusudan (for CS173)
More notes on induction, Chandra Chekuri (for CS173)
Motivation, Introduction and Administrivia
First Order Logic: Over a single structure, over a class of structures, and over all structures
Logic in CS; Chapter 1Background: Theory of computation, Induction
Countable and uncountable sets; Turing machines; decidability; undecidability of the halting problem (and proof); Rice's theorem; Induction; "strong" and "weak" induction; induction over expressions generated by a grammar. Lecture notes by Sariel and Madhu: Turing machines, Undecidability, halting, and diagonalization