Logic

In broad strokes, we might profitably identify the following areas. The first four are often known as the “four pillars” of foundational mathematics or mathematical logic, while the fifth, while not considered to be a branch of logic, relies heavily on formal axiomatic methods and is also relevant to the foundations of mathematics. There is substantial overlap between each subject; for example, Gödel’s completeness theorem is a fundamental result in both proof theory and model theory.

1) Proof theory: The area of mathematical logic closest to philosophical logic, proof theory is the study of proofs as mathematical objects in their own right. Modern proof theory began with Hilbert’s program to reduce all of mathematics to a finitist formal system, a task famously proved to be impossible by Gödel with his incompleteness theorems (in a nutshell, the first incompleteness theorem, as strengthened by Rosser, proves that any consistent theory that is strong enough to express basic arithmetic contains a true sentence that is not provable within the theory). Questions that arise in proof theory are syntactic in nature, rather than semantic as in model theory: that is, they refer to formal languages in and of themselves without necessarily making claims about their interpretations.

2) Model theory: The study of universal algebra using the language and tools of logic. The basic objects of study are structures, which give an interpretation for constant symbols, function symbols, and relation symbols in a formal language. Equipped with Tarski’s definition of truth and basic logical definitions, we can then interpret the meaning and truth value of sentences in this formal language. A model of a sentence or set of sentences is a structure in which that sentence or set of sentences is interpreted as true. For example, in the language (e,*) consisting of a constant symbol and a binary function symbol, we can formalize the group axioms in a set of sentences; a group is then merely a model of this particular set of sentences. Questions in model theory relate to the interplay of properties of theories and models or particular classes of models, most notably properties that control the cardinality (size) of models.
In addition to being a field of study in and of itself, there are model-theoretic proofs and constructions in mainstream mathematics. Examples include the Ax-Grothendieck theorem that any injective polynomial function from C^n to C^n is also surjective and the ultraproduct construction of Robinson’s nonstandard analysis.

3) (Axiomatic) set theory: The study of sets and the axiomatization of their properties. Perhaps the first modern proof in set theory was Cantor’s diagonalization argument, which showed that a set cannot be put in a bijection with the set of its subsets (and has the immediate consequence that the real numbers cannot be put in a bijection with the natural numbers). Set theory is often taken to be “the” foundation of mathematics; indeed, naïve set theory is nearly ubiquitous. Consider the universality of “set builder” notation, e.g., the use of the symbol {x|x>2} to represent the set of elements greater than two (in some presupposed larger set, such as the real numbers).
Many questions in set theory relate to the choice of set theory axioms and their relations to each other, such as the Zermelo-Frankel axioms and various “large cardinal” axioms asserting the existence of certain special infinite cardinals. Descriptive set theory deals with set-theoretic questions about the real line, or Polish spaces more generally.

4) Recursion theory: Also called computability theory. Following Turing’s proposed definition of a computable function in terms of his Turing machine, recursion theory studies questions of decidability by algorithm and the hierarchies of noncomputable functions. There is a considerable overlap between “mathematical” recursion theory and theoretical computer science, which, unsurprisingly, focuses more on classes of functions that are computable, such as P (functions computable in polynomial time) and NP (functions whose outputs are verifiable in polynomial time).

5) Category theory: A category is an algebraic object consisting of a class of objects and a class of morphisms (“arrows”) between them, such that we are allowed to compose morphisms associatively and there exists an identity arrow from each object to itself. For example, Set is a category where the objects are sets and the morphisms are set functions, and any monoid can be made into a category with one object x, with morphisms x -> x corresponding to each element of the monoid. Category theory takes categories to be the basic objects of study. By abstracting many common mathematical structures, the language of category theory has proven useful in a variety of fields, most notably algebraic geometry and algebraic topology. In fact, certain categories called topoi provide an alternative foundation to mathematics; that is, just like an axiomatic set theory, all of mathematics could be performed inside such an object.

Classes in logic and foundational mathematics are generally based in the philosophy department, with some crosslisted with mathematics. There is also at least one course of interest taught in the computer science department. Relevant professors include Edward Nelson in the mathematics department, John Burgess and Hans Halvorson in the philosophy department, and several professors in the computer science department’s theory group. In addition to the classes listed below and in the Undergraduate Announcement, there are often graduate courses; for example PHI 520: Logic, PHI 536: Philosophy of Mathematics, and Professor Nelson’s classes in the mathematics department.

MAT 312: Mathematical Logic
This class assumes no prior knowledge and begins with first order theories. Early topics include the Tautology Theorem and Gödel Completeness/Incompleteness. It could be considered a survey of mathematical logic and foundations, since it briefly covers theorems and topics in proof theory, model theory, and set theory. For the past two years, the course has covered chapters one through four of Shoenfield’s Mathematical Logic for the first half of the semester. The second half of the semester usually covers set theory, with more advanced material at the end. For example, in spring 2011, Internal Set Theory was the last topic covered. The workload and pace tend to be reasonable, although Shoenfield can be dense and lacks examples.

PHI 323/MAT313: Advanced Logic
This course has recently been used as a topics course by Professor Halvorson, who has taught classes in category theory and model theory recently under this number. Going forward, Professor Burgess reports that it will be a course in set theory getting at least through a proof of the consistency of the axiom of choice. The following is a description of the course when it focused on model theory.
This course served as an introduction to model theory: a branch of logic concerned with the various ways that internally consistent sets of axioms may be implemented in concrete mathematical structures (e.g. rings, fields, groups, etc.). Such a structure is called a “model” of the axioms. As an example, consider the Peano axioms for arithmetic. The integers are then a model of these axioms, and one may inquire as to whether other such models exist. Using basic tools of model theory, it is not too hard to show that the answer is “yes.” Even more surprisingly, it is possible to find models of the Peano axioms having arbitrarily large cardinalities. This turns out to be a very general phenomenon.
Despite a bevy of other curious results in this vein, model theory, like most of mathematical logic, is considered somewhat peripheral to mainstream mathematics. As a result, the course tended to focus on applications to “real” math and to present the material in a style amenable to this end. This proved to be an interesting approach, as model theory is rife with unexpected connections to algebraic geometry and commutative algebra, often providing fresh albeit non-intuitive insights and deceptively short proofs of difficult theorems. However, the non-model-theoretic problems which have been solved with model theory are few and far between. Thus, the material in this course is probably non-essential for the student without a strong interest in mathematical logic. Conversely, for anyone with such an interest, the material in this course should provide a solid foundation for future research in the subject.

COS 487: Theory of Computation
Basic computability theory, computational complexity classes, topics relevant to theoretical computer science. The first part is a substantial overlap with PHI 312. Although the class formally lists COS 340 as a prerequisite, in reality all that is needed is a familiarity with mathematical arguments, and there have been no issues with getting permission to take this class with no computer science background.

PHI 312: Intermediate Logic.
This course is taught by Professor Burgess; it covers topics in logic and computability theory such as Turing machines and Gödel’s Incompleteness Theorem. The course starts slowly from the mathematics point of view in order to bring the philosophy majors up to speed, but it gets more interesting quickly.

PHI 324: Category Theory
This course is taught by Hans Halvorson, and it used to be under the listing PHI 323: Advanced Logic. It is an introduction to category theory using the standard text in the field, Mac Lane’s Categories for the Working Mathematician.

PHI 340: Philosophical Logic
Philosophical Logic (PHI340) is a course that is usually offered every other year and only assumes basic previous knowledge of logic (mostly in the form of boolean variable manipulation and knowing how to produce rigorous proofs, which math majors should be familiar with). It is considered a philosophy course because it discusses extensions/alternatives to classical logic that can be used to model things like time, necessity and possibility. In Burgess’s words, “Philosophical logic […] is the part of logic dealing with what classical leaves out, or allegedly gets wrong.” The topics that are covered each year may vary, but the are usually included in professor Burgess’s book Philosophical Logic.
Initially, temporal logic is introduced. Temporal logic attempts to allow logical statements to take time into account. As such, axioms for describing time as we consider it in everyday life (continuous) or as is used in computer science (discrete) are presented, and the philosophical debates surrounding them are also discussed. Afterwords, modal logic, which attempts to introduce the concept of necessity and possibility, is presented. Again, an axiomatic approach for proving theorems is given, and soundness and completeness proofs are also discussed. Both temporal and modal logic can be considered as extensions of some form to classical logic, and are thus also called “extra-classical” logics.
The second half of the semester deals with “anti-classical” logics, which not only try to add parts of logic that are missing, but fix parts of logic that are “wrong”. As such, the various types of logics presented discuss the possibilities of multiple truth values, as well as other controversial statements regarding the notions of truth and the validity of tautologies and deductions.
Because of professor Burgess’s mathematical background as well as the mixture of the class (which usually consists of approximately equal philosophy and math majors), the lectures/discussions are very interesting and intellectually simulating. And because the course is problem set based (which require rigor!), math majors will find this class to be a great fit.

Evan Warner ’12 (ebwarner[at]stanford[dot]edu) for general questions
Mark Pullins ’13 (mpullins) for questions on MAT 312
Simon Segert ’14 (ssegert) for questions on PHI 323
Ilias Giechaskiel ’13 (igiechas) for questions on PHI 340