Logic at Harvard

Structure

The courses in logic at Harvard cover all of the major areas of mathematical logic—proof theory, recursion theory, model theory, and set theory—and, in addition, there are courses in closely related areas, such as the philosophy and foundations of mathematics, and theoretical issues in the theory of computation.

Here is a brief guide for the beginning student: The most introductory course in logic is EMR 17. The first tier of introductory courses consists of Phil 143Y, Phil 144, Math 141, CS 121. These courses provide a comprehensive introduction to the main areas of mathematical logic. In particular, Phil 144 provides an introduction to proof theory and recursion theory, while Phil 143Y provides an introduction to model theory and set theory. The next tier consists of courses devoted to each of the main areas of mathematical logic. These courses are offered on a rotating basis. For example, this year there are courses in model theory (Math 141) and forcing and independence in set theory (Math 143).

In addition there are many logic courses offered at neighbouring universities (see below).

Current Courses

Harvard

Fall 2011

Philosophy 143r: Topics in Logic: Proseminar (Koellner)
Investigation of the philosophical and mathematical aspects of the independence results in mathematics. We shall concentrate on the work of the major experts in the field, who will be visiting us. Boylston Hall 110, W 4-7.
Mathematics 141: Introduction to Mathematical Logic (Sacks)
An introduction to mathematical logic with applications to computer science and algebra. Formal languages. Completeness and compactness of first order logic. Definability and interpolation. Decidability. Unsolvable problems. Computable functions and Turing machines. Recursively enumerable sets. Transfinite induction. Science Center 310, MWF 11-12.
Computer Science 121. Introduction to Formal Systems and Computation (Lewis)
General introduction to formal systems and the theory of computation, teaching how to reason precisely about computation and prove mathematical theorems about its capabilities and limitations. Finite automata, Turing machines, formal languages, computability, uncomputability, computational complexity, and the P vs. NP question. Maxwell Dworkin G-115, TR 10-11.30.

Spring 2012

Philosophy 143r: Topics in Logic: Proseminar (Koellner)
Investigation of the philosophical and mathematical aspects of the independence results in mathematics. We shall concentrate on the work of the major experts in the field, who will be visiting us. Boylston Hall 110, W 4-7.
Philosophy 144: Logic and Philosophy (Goldfarb)
Three philosophically important results of modern logic: Gödel’s incompleteness theorems; Turing’s definition of mechanical computability; Tarski’s theory of truth for formalized languages. Discusses both mathematical content and philosophical significance of these results. Location TBD, MWF 10-11.
Mathematics 143: Set Theory (Sacks)
Axioms of set theory. Godel's constructible universe. Consistency of the axiom of choice and of the generalized continuum hypothesis. Cohen's forcing method. Independence of the AC and GCH. Location TBD, MWF 12-1.

MIT

Fall 2011

24.241 Logic I (McGee)
Introduction to the aims and techniques of formal logic. The logic of truth functions and quantifiers. The concepts of validity and truth and their relation to formal deduction. Applications of logic and the place of logic in philosophy. 26-314, TR 9:30-11.
24.244 Modal Logic (Stalnaker)
Sentential and quantified modal logic, with emphasis on the model theory ("possible worlds semantics"). Soundness, completeness, and characterization results for alternative systems. Tense and dynamic logics, epistemic logics, as well as logics of necessity and possibility. Applications in philosophy, theoretical computer science, and linguistics. 56-180, R 2-5
18.404 Theory of Computation (Sipser)
A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. 2-190, TR 11-12.30.
18.510 Introduction to Mathematical Logic and Set Theory (Cohn)
Propositional and predicate logic. Zermelo-Frenkel set theory. Ordinals and cardinals. Axiom of choice and transfinite induction. Elementary model theory: completeness, compactness, and Löwenheim-Skolem theorems. Gödel's incompleteness theorem. 2-142, MWF 2.
6.893 Philosophy and Theoretical Computer Science (Aaronson)
This new offering will examine the relevance of modern theoretical computer science to traditional questions in philosophy, and conversely, what philosophy can contribute to theoretical computer science. Topics include: the status of the Church-Turing Thesis and its modern polynomial-time variants; quantum computing and the interpretation of quantum mechanics; complexity aspects of the strong-AI and free-will debates; complexity aspects of Darwinian evolution; the claim that "computation is physical"; the analog/digital distinction in computer science and physics; Kolmogorov complexity and the foundations of probability; computational learning theory and the problem of induction; bounded rationality and common knowledge; new notions of proof (probabilistic, interactive, zero-knowledge, quantum) and the nature of mathematical knowledge. Intended for graduate students and advanced undergraduates in computer science, philosophy, mathematics, and physics. Participation and discussion are an essential part of the course. 36-112, W 2-5.

Spring 2012

24.118 Paradox and Infinity (Rayo)
Different kinds of infinity; the paradoxes of set theory; the reduction of arithmetic to logic; formal systems; paradoxes involving the concept of truth; Godel's incompleteness theorems; the nonformalizable nature of mathematical truth; and Turing machines. Location TBD.
24.242 Logic II (McGee)
The central results of modern logic: the completeness of predicate logic, recursive functions, the incompleteness of arithmetic, the unprovability of consistency, the indefinability of truth, Skolem-Löwenheim theorems, and nonstandard models. Location TBD

Brown

Spring 2012

PHIL1880: Advanced Deductive Logic (Heck)
An introduction to the 'limitative' theorems of deductive logic, including the undecidability of first-order logic, the Gödel incompleteness theorems, and the arithmetical undefinability of arithmetical truth. Intended as a sequel to PHIL 1630; previous participation in either that course or one of similar content is strongly recommended. Students who have completed PHIL 0540 with a grade of "A" may enroll with instructor permission. C Hour (M.,W.,F. 10:00-10:50 AM) at 54 College St-Gerard House 119.

BU

Fall 2011

CAS MA531 A1 Math Logic (Kanamori)
The syntax and semantics of sentential and quantificational logic, culminating in the Gödel Completeness Theorem. The Gödel Incompleteness Theorem and its ramifications for computability and philosophy. Location TBD, TR 11-12:30.

Past & Recurring Courses

Harvard

Empirical and Mathematical Reasoning 17. Deductive Logic (Taught: Fall 2010)
The concepts and principles of symbolic logic: valid and invalid arguments, logical relations of statements and their basis in structural features of those statements, the analysis of complex statements of ordinary discourse to uncover their structure, the use of a symbolic language to display logical structure and to facilitate methods for assessing arguments. Analysis of reasoning with truth-functions ("and", "or", "not", "if...then") and with quantifiers ("all", "some"). Attention to formal languages and axiomatics, and systems for logical deduction. Throughout, both the theory underlying the norms of valid reasoning and applications to particular problems will be investigated.
Philosophy 142. Set Theory: The Higher Infinite (Last Taught: Fall 2010)
An introduction to the hierarchy of axioms of infinity in set theory.
Philosophy 142q. Topics in Set Theory (Last Taught: Spring 2011)
This is a proseminar on advanced topics in set theory. The topics will depend on the interests of the participants. Possible topics include: large cardinal axioms, forcing and large cardinals, singular cardinal combinatorics, determinacy, inner model theory.
Philosophy 142z. Intermediate Logic: Introduction to Model Theory (Last Taught: Spring 2008)
Peter Koellner
Review of first-order logic; basic elements of model theory, including completeness, compactness, Loewenheim-Skolem theorem, Craig's interpolation lemma, Robinson's theorem, Beth's definability theorem, a unified perspective. The approach is based on a series of entertaining puzzles.
Philosophy 143. Set Theory (Last Taught: Fall 2003)
An introduction to set theory, covering fundamental notions and results of the standard system of set theory (ZFC), Gödel's constructible universe, Cohen's method of forcing, and extensions of ZFC that settle some problems not decidable within it. The course is suitable for both graduate students and undergraduate students with background in logic or mathematics.
Philosophy 143y. Logic and the Foundations of Mathematics (Last Taught: 2005)
An introduction to foundational aspects of set theory and model theory. Topics include: formalization of mathematics in set theory, theory of infinities, axiom of choice, completeness theorem, existence of non-standard models, and mathematical instances of incompleteness. Attention will be paid to how these developments affect views of the nature of mathematics.
Philosophy 144. Logic and Philosophy (Last Taught: Spring 2010)
Three philosophically important results of modern logic: Gödel's incompleteness theorems; Turing's definition of mechanical computability; Tarski's theory of truth for formalized languages. Discusses both mathematical content and philosophical significance of these results.
Philosophy 148. Philosophy of Mathematics (Last Taught: Spring 2011)
Philosophical issues concerning mathematics, such as: its degree of certainty and necessity, its being apparently a priori, what reference to objects such as numbers and sets amounts to, the relation of mathematics and logic, whether classical logic can be called into question. Reading of such writers as Frege, Brouwer, Hilbert, Carnap, Quine, and contemporaries.
Philosophy 242. From Frege to Gödel
Warren Goldfarb
The rise of modern logic in its formative period. Both technical and philosophical issues will be considered. Primary authors will be Cantor, Dedekind, Peano, Zermelo, Hilbert and his school, Brouwer, Weyl, Skolem, and Herbrand
Philosophy 243w. Foundational Aspects of Set Theory (Last Taught: Spring 2007)
Peter Koellner
Philosophical and mathematical aspects of the program to find axioms that settle statements undecided by the standard axioms. Discusses strong axioms of infinity, definable determinacy, the continuum hypothesis, recent advances in inner model theory.
Philosophy 248. Topics in the Philosophy of Mathematics (Last Taught: Fall 2009)
Peter Koellner
Mathematical objects and knowledge of mathematical truths. We will start with weak systems of arithmetic and work through more complex systems, to systems involving the infinite in a substantive way. Focus on contemporary authors.
Mathematics 141. Introduction to Mathematical Logic (Last Taught: Spring 2011)
An introduction to mathematical logic with applications to computer science and algebra. Formal languages. Completeness and compactness of first order logic. Definability and interpolation. Decidability. Unsolvable problems. Computable functions and Turing machines. Recursively enumerable sets. Transfinite induction.
Mathematics 143. Set Theory
Warren Goldfarb
Axioms of set theory. Ordinal and cardinal numbers. Gödel's constructible universe. Consistency of the axiom of choice and the generalized continuum hypothesis. Cohen's forcing method. Independence of the axiom of choice and the generalized continuum hypothesis.
Mathematics 162. Introduction to Quantum Computing (Last Taught: Spring 2011)
This course is meant to give an introduction to the fundamental mathematics of quantum computing. Notions from linear algebra, elementary number theory and probability theory are introduced along the way as needed.
Mathematics 242. Set Theory: Large Cardinals from Determinacy (Last Taught: Fall 2004)
A course on the strength of the axiom of determinacy. First we prove a classic result of Woodin: 'ZF + AD' is consistent, then 'ZFC + there are ?-many Woodin cardinals' is consistent. Second goal: to discuss recent work of Woodin in this area, in particular, the HOD-analysis, a key ingredient in his results on CH.
Mathematics 244. Advanced Set Theory (Last Taught: Spring 2008)
Peter Koellner
Inner models of large cardinal axioms, focusing on recent work on inner models for large cardinals at the level of supercompact and beyond. Topics include: Continuum Hypothesis and Omega Conjecture.
Mathematics 245. Proof Theory
Warren Goldfarb
Herbrand's and Gentzen's analyses of logical inference; Hilbert's program for consistency proofs by metamathematical treatment of proof structures; consistency of number theory and subsystems of analysis; ordinal-theoretic measures of the strength of axiomatic theories; the logic of provability.
Mathematics 248. Decidability
Warren Goldfarb
Recursively decidable and undecidable problems from different areas: word problems, combinatorial systems, tiling problems, arithmetic, diophantine equations, second-order theory of trees; investigation in depth of decision problems for first-order logic.
Mathematics 253. Introduction to Computability and Randomness (Last Taught: Spring 2011)
An introduction to computability theory and algorithmic randomness. Topics: Turing reducibility, computably enumerable sets, complexity, notions of randomness, and martingales, as well as interactions between computability and randomness.