21-600 Math Logic Instructor: Jose Iovino MWF 11:30 HH B131 12 units Description: The course is an introduction to first-order logic. Topics to be covered include: syntax and semantics of first-order logic, formal deductive systems, the completeness theorem of first-order logic, the compactness theorem, applications of compactness, ultraproducts of structures, nonstandard models of arithmetic, and beginnings of model theory. http://math.cmu.edu/~iovino/ http://math.cmu.edu/~iovino/logic-description.html 21-602 Introduction to Set Theory Instructor: Ernest Schimmerling MWF 3:30 Wean 7201 12 units Description: The axioms of ZFC, ordinal arithmetic, cardinal arithmetic including Kőnig's lemma, class length induction and recursion, the rank hierarchy, the Mostowski collapse theorem, the H(λ) hierarchy, the Δ1 absoluteness theorem, the absoluteness of wellfoundedness, the reflection theorem for hierarchies of sets, ordinal definability, the model HOD, relative consistency, Gödel's theorem that HOD is a model of ZFC, constructibility, Gödel's theorem that L is a model of ZFC + GCH, the Borel and Projective hierarchies and their effective versions, Suslin representations for Σ11, Π11 and Σ12, sets of reals, Shoenfield's absoluteness theorem, the complexity of the set of constructible reals, the combinatorics of club and stationary sets (including the diagonal intersection, the normality of the club filter and Fodor's lemma), Solovay's splitting theorem, model theoretic techniques commonly applied in set theory (e.g., elementary substructures, chains of models and ultrapowers), club and stationary subsets of [X]ω (including a generalization of Fodor's lemma and and connections with elementary substructures), Jensen's diamond principles and his proofs that they hold in L, Gregory's theorem, constructions of various kinds of uncountable trees (including Aronszajn, special, Suslin, Kurepa), Jensen's square principles and elementary applications, the basic theory of large cardinals (including inaccesssible, Mahlo, weakly compact and measurable cardinals), Scott's theorem that there are no measurable cardinals in L, Kunen's theorem that the only elementary embedding from V to V is the identity. Prerequisites for 21-602 The minimum background for 21-602 is the equivalent of undergraduate set theory (e.g., 21-329) and the fundamentals of logic (e.g., 21-600). Students should arrive with a working knowledge of basic ordinal and cardinal arithmetic, Gödel's completeness theorem and the downward Loewenheim-Skolem theorem. An understanding of the statement of Gödel's incompleteness theorem is also assumed. (This theorem is mentioned in 21-600 but proved in 21-700.) 21-603 Model Theory I Instructor: Rami Grossberg (rami@cmu.edu) MWF 1:30 Wean 7201 12 Units DESCRIPTION: Model theory is one of the major branches of mathematical logic. There are many applications of model theory to algebra (e.g. field theory, algebraic geometry, number theory, and group theory), analysis (non-standard analysis, complex manifolds and the geometry of Banach spaces) and theoretical computer science (via finite model theory) as well as set theoretic topology and set theory. This course is the first in a sequence. The purpose of this course to introduce the student to some of the most important ideas of the field with a special attention to "classification theory" which is the most important subfield of modern model theory. The main focus of the course is Morely's categoricity theorem, the related conceptual infrastructure and extensions. Topics will include: compactness theorem, model completeness, elementary decideability results, cardinal transfer theorems, Henkin's omitting types theorem, prime models. Elementary chains of models, some basic two-cardinal theorems, saturated models (characterization and existence), special models, the monster model, basic results on countable models including Ryll-Nardzewski's theorem. Indiscernible sequences, and connections with Ramsey theory, Ehrenfeucht-Mostowski models. Introduction to stability (including the equivalence of the order-property to instability), chain conditions in group theory corresponding to stability/superstablity/omega-stability, strongly minimal sets, various rank functions, primary models, and a proof of Morley's categoricity theorem. Basic facts about infinitary languages and abstract elementary classes, computation of Hanf-Morley numbers. PREREQUISITE: This is a graduate level course, while at the beginning the pace will be slow, the pace will speed up in the second half. In the past many students were undergraduates, so the prerequisites are kept to the minimum of "an undergraduate-level" course in logic. Motivated undergraduate students are encouraged to take this course. TEXT: Rami Grossberg, A course in model theory, a book in preparation. Most of the material (and more) appears in the following books: 1. C. C. Chang and H. J. Keisler, Model Theory, North-Holland 1990. 2. Bruno Poizat, A course in Model Theory, Springer-Verlag 2000. 3. S. Shelah, Classification Theory, North-Holland 1991. EVALUATION: Will be based on weekly homework assignments (20%), a 50 minutes midterm (20%) and a 3 hours in-class comprehensive final written examination (60%). COURSE WEBPAGE: www.math.cmu.edu/~rami/mt1.12.desc.html 80-610 Formal Logic Instructor: Jeremy Avigad TR 1:30pm-2:50pm PH A18A 12 Units Description: Among the most significant developments in modern logic is the formal analysis of the notions of provability and logical consequence for the logic of relations and quantification, known as first-order logic. These notions are related by the soundness and completeness theorems: a logical formula is provable if and only if it is true under every interpretation. This course provides a formal specification of the syntax and semantics of first-order logic and then proves the soundness and completeness theorems. Other topics may include: basic model theory, intuitionistic, modal, and higher-order logics. 80-713 Category Theory Instructor: Spencer Breiner MW 10:30-11:50 Wean Hall 5403 12 Units Description: Category theory, a branch of abstract algebra, has found many applications in mathematics, logic, and computer science. Like such fields as elementary logic and set theory, category theory provides a basic conceptual apparatus and a collection of formal methods useful for addressing certain kinds of commonly occurring formal and informal problems, particularly those involving structural and functional considerations. This course is intended to acquaint students with these methods, and also to encourage them to reflect on the interrelations between category theory and the other basic formal disciplines. Textbook: "Category Theory" 2nd Edition, by Steve Awodey Prerequisites: One course in logic or algebra. 80-714 Seminar on Logic: Constructive type theory Instructor: Cody Roux Wednesdays, 10-12:20 Doherty 4303 Description: This course covers various topics in constructive type theory. Prerequisites: introductory knowledge of first-order logic, mathematical sophistication, knowledge of some programming language helpful but not required. Topics covered include: Simply typed lambda calculus: syntax, basic metatheory, set-theoretic model, strong normalization, Curry-Howard correspondence with propositional logic. Martin-Lof type theory with a single universe: syntax, set-theoretic model, strong normalization, C-H correspondence; natural numbers and recursion, strong elimination and equality, inductive families. Universes, logical expressivity. Impredicativity, system F, Type:Type and paradoxes. The K axiom, the groupoid model of type theory. 80-813 Seminar on Mathematical Understanding and Cognition Instructor: Jeremy Avigad Fridays, 10:00am-12:20pm BH 150 12 Units This course will consider mathematical understanding and cognition from multiple perspectives, including mathematical logic, philosophy, cognitive science, and automated reasoning. A description of the seminar, preliminary syllabus, and bibliography can be found on line: http://www.andrew.cmu.edu/user/avigad/Teaching/understanding_seminar/ Auditors and casual participants are welcome.