MATH 681 — Spring 2000
Logic

 

Instructor:	Anil Nerode
Time:	MWF 11:15-12:05
Room:	MT 206

A first graduate course in logic at a rapid pace.

Topics Outline:

1. Informal elements of Zermelo-Fraenkel Set Theory Cardinals, Ordinals, Definitions by Transfinite Induction, forms of the axiom of choice
2. Propositional logic, compactness and completeness,
3. Boolean Algebras and Boolean Spaces and Stone Duality
4. Quantifiers as lattice operations in the Boolean algebra of formulas, algebraic and topological proofs of compactness and completeness
5. Definitions of recursively enumerable sets by Post canonical systems, Horn clause logic, primitive recursion and the least number operator, lambda calculus
6. Godel's incompleteness of formal arithmetic, Tarski's proof of the indefinability of truth
7. Constructible sets and a sketch of consistency and independence in formal set theory
8. Elements of model theory, types, saturation, etc.

No required text: References will be on reserve

• Nerode-Shore, Logic for Applications
• Hartley Rogers, Theory of Effective Computability
• Joe Shoenfield, Mathematical logic
• Chang-Keisler, Model Theory
• Jech, Set Theory

There will be eight homework assignments and no examinations.

Last modified: April 7, 2003