These are the course descriptions submitted so far for the Fall 2008 Pure and Applied Logic listings. 80-521 Seminar on Methodology Fall: The Theory and Philosophy of Ockham's Razor Instructor: Kevin T. Kelly T 3:30PM-5:50PM BH 150 9-12 units Description: Ockham's razor is the vague but crucial principle of scientific method, named after the 14th century logician and theologion William of Ockham, that one should prefer simpler theories. This raises two obvious questions: what simplicity is and why one should expect the simpler theory to be true. The questions were already raised by Leibniz and Kant and have been discussed by Goodman, Quine, Lewis, Rosenkrantz, Glymour, Kitcher, Friedman and other philosophers. But the significance of the question extends far beyond philosophy, for statistics and machine learning have their own sophisticated accounts of Ockham's razor, including simplicity-biased prior probabilities, sample coverage, structural risk minimization, and Kolmogorov complexity. Each of these approaches will be examined critically and will be found either to evade or to dismiss the central question of how Ockham's razor helps one find the true theory. Then I will introduce a new foundational account of the nature and scientific role of simplicity, according to which Ockham's razor cannot point straight at the true theory but nonetheless keeps science on the uniquely straightest path thereto. The theory, which is based loosely upon H. Putnam's computational concept of "trial and error predicates" and upon the related, learning theoretic literature on "mind-changes", will be applied to causal discovery, conservation laws, curve fitting and the inference of regular sets. The course will interest anyone who cares about the foundations of scientific method and learning, including students in philosophy, psychology, statistics, machine learning, social and decision sciences, physics, biology or any area in which questions of modeling, causation, or theory choice arise. Students should have some comfort level with basic mathematical logic, probability theory, computability theory, and analysis, all of which are crucial to the topic. 21-600 Mathematical Logic I Instructor: Peter Andrews MWF 11:30am-12:20pm BH A53 12 Units Description: The study of formal logical systems which model the reasoning of mathematics, scientific disciplines, and everyday discourse. Propositional calculus and first-order logic. Syntax, axiomatic treatment, derived rules of inference, proof techniques, computer-assisted formal proofs, normal forms, consistency, independence, semantics, soundness, completeness, the Lowenheim-Skolem and Downward Lowenheim-Skolem Theorems, compactness. 21-602 Set Theory I Instructor: Ernest Schimmerling MW 3:30 - 4:50 Wean Hall 5312 12 Units Description: First semester graduate level set theory. Godel proved that if ZF is consistent, then so is ZFC + GCH; this is the most important theorem that will be covered in the course. The main topics are ZFC, cardinal arithmetic, the rank hierarchy, the H(\kappa) hierarchy, absoluteness, relative consistency, infinitary combinatorics, constructibility and descriptive set theory. TEXTBOOK OR REFERENCES: Kenneth Kunen, "Set theory : An introduction to independence proofs" 21-603 Model Theory I Instructor: Rami Grossberg (rami@cmu.edu) MWF 1:30-2:20 Baker Hall 255A 12 Units DESCRIPTION: Model theory is one of the four 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. Topics will include: compactness theorem, model completeness, elementary decideability results, Henkin's omitting types theorem, prime models. Elementary chains of models, some basic two-cardinal theorems, saturated models (characterization and existence), 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 where undergraduates, so the prerequisites are kept to the minimum of "an undergraduate-level" course in logic. Motivated undergraduate students are encouraged to contact the instructor. 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. I will not use a text, but will provide access to my notes on a weekly basis. 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.08.desc.html 80-612 Philosophy of Mathematics INSTRUCTOR: Wilfried Sieg Wed 2:00-4:20 CFA 102 12 units DESCRIPTION: The 20th century witnessed remarkable developments in mathematics - rooted in the radical transformation of the subject during the 19th century. An analysis of this transformation is at the center of the course, as it led to significant foundational problems and provoked a variety of programmatic responses: logicism, intuitionism, and finitism. The resulting "disputes" from the 1920s are taken as a starting-point in the first part of the course. They are complemented by an analysis of meta-mathematical studies initiated by Hilbert and pursued by Gödel, Church, Turing and many others. In order to gain a deeper understanding of the fundamental issues, the second part discusses the 19th century arithmetization of analysis; the problematic reaches back to Greek mathematics, in particular,to Eudoxos' theory of proportion. The third part surveys systematic foundational work that has been pursued throughout the 20th century. We will discuss in detail set-theoretic and constructive approaches. Against this background, the final part makes explicit important aspects of mathematical experience; they find their articulation in the framework of "reductive structuralism". In addition to the regular class meeting, there will be a special weekly discussion meeting (only for graduate students) in which an important new book is going to be read, namely, Charles Parsons, Mathematical thought and its objects; Cambridge University Press, 2008. 21-804 Math Logic Seminar Coordinator: James Cummings Tuesday 12:00-1:20 Porter Hall A19A