When speak­ing in a math­e­mat­i­cal con­text of “logic” — a field with a long his­tory in phi­los­o­phy — we are really talk­ing about math­e­mat­i­cal logic, which takes as its sub­strate the inter­sec­tion of logic and math­e­mat­i­cal rea­son­ing. This works in two direc­tions — the appli­ca­tion of math­e­mat­i­cal rea­son­ing to for­mal log­i­cal sys­tems, and the appli­ca­tion of these sys­tems back to math­e­mat­ics. This inter­play has been espe­cially impor­tant and influ­en­tial as applied to foun­da­tional math­e­mat­ics — that is, sys­tems in which large parts of math­e­mat­ics can be for­mal­ized. There­fore one often hears “foun­da­tional math­e­mat­ics” and “math­e­mat­i­cal logic” as approx­i­mate synonyms.

Areas [Show]Areas [Hide]
In broad strokes, we might prof­itably iden­tify the fol­low­ing areas. The first four are often known as the “four pil­lars” of foun­da­tional math­e­mat­ics or math­e­mat­i­cal logic, while the fifth, while not con­sid­ered to be a branch of logic, relies heav­ily on for­mal axiomatic meth­ods and is also rel­e­vant to the foun­da­tions of math­e­mat­ics. There is sub­stan­tial over­lap between each sub­ject; for exam­ple, Gödel’s com­plete­ness the­o­rem is a fun­da­men­tal result in both proof the­ory and model the­ory.
1) Proof the­ory: The area of math­e­mat­i­cal logic clos­est to philo­soph­i­cal logic, proof the­ory is the study of proofs as math­e­mat­i­cal objects in their own right. Mod­ern proof the­ory began with Hilbert’s pro­gram to reduce all of math­e­mat­ics to a fini­tist for­mal sys­tem, a task famously proved to be impos­si­ble by Gödel with his incom­plete­ness the­o­rems (in a nut­shell, the first incom­plete­ness the­o­rem, as strength­ened by Rosser, proves that any con­sis­tent the­ory that is strong enough to express basic arith­metic con­tains a true sen­tence that is not prov­able within the the­ory). Ques­tions that arise in proof the­ory are syn­tac­tic in nature, rather than seman­tic as in model the­ory: that is, they refer to for­mal lan­guages in and of them­selves with­out nec­es­sar­ily mak­ing claims about their inter­pre­ta­tions.
2) Model the­ory: The study of uni­ver­sal alge­bra using the lan­guage and tools of logic. The basic objects of study are struc­tures, which give an inter­pre­ta­tion for con­stant sym­bols, func­tion sym­bols, and rela­tion sym­bols in a for­mal lan­guage. Equipped with Tarski’s def­i­n­i­tion of truth and basic log­i­cal def­i­n­i­tions, we can then inter­pret the mean­ing and truth value of sen­tences in this for­mal lan­guage. A model of a sen­tence or set of sen­tences is a struc­ture in which that sen­tence or set of sen­tences is inter­preted as true. For exam­ple, in the lan­guage (e,*) con­sist­ing of a con­stant sym­bol and a binary func­tion sym­bol, we can for­mal­ize the group axioms in a set of sen­tences; a group is then merely a model of this par­tic­u­lar set of sen­tences. Ques­tions in model the­ory relate to the inter­play of prop­er­ties of the­o­ries and mod­els or par­tic­u­lar classes of mod­els, most notably prop­er­ties that con­trol the car­di­nal­ity (size) of mod­els.
In addi­tion to being a field of study in and of itself, there are model-theoretic proofs and con­struc­tions in main­stream math­e­mat­ics. Exam­ples include the Ax-Grothendieck the­o­rem that any injec­tive poly­no­mial func­tion from C^n to C^n is also sur­jec­tive and the ultra­prod­uct con­struc­tion of Robinson’s non­stan­dard analy­sis.
3) (Axiomatic) set the­ory: The study of sets and the axiom­a­ti­za­tion of their prop­er­ties. Per­haps the first mod­ern proof in set the­ory was Cantor’s diag­o­nal­iza­tion argu­ment, which showed that a set can­not be put in a bijec­tion with the set of its sub­sets (and has the imme­di­ate con­se­quence that the real num­bers can­not be put in a bijec­tion with the nat­ural num­bers). Set the­ory is often taken to be “the” foun­da­tion of math­e­mat­ics; indeed, naïve set the­ory is nearly ubiq­ui­tous. Con­sider the uni­ver­sal­ity of “set builder” nota­tion, e.g., the use of the sym­bol {x|x>2} to rep­re­sent the set of ele­ments greater than two (in some pre­sup­posed larger set, such as the real num­bers).
Many ques­tions in set the­ory relate to the choice of set the­ory axioms and their rela­tions to each other, such as the Zermelo-Frankel axioms and var­i­ous “large car­di­nal” axioms assert­ing the exis­tence of cer­tain spe­cial infi­nite car­di­nals. Descrip­tive set the­ory deals with set-theoretic ques­tions about the real line, or Pol­ish spaces more gen­er­ally.
4) Recur­sion the­ory: Also called com­putabil­ity the­ory. Fol­low­ing Turing’s pro­posed def­i­n­i­tion of a com­putable func­tion in terms of his Tur­ing machine, recur­sion the­ory stud­ies ques­tions of decid­abil­ity by algo­rithm and the hier­ar­chies of non­com­putable func­tions. There is a con­sid­er­able over­lap between “math­e­mat­i­cal” recur­sion the­ory and the­o­ret­i­cal com­puter sci­ence, which, unsur­pris­ingly, focuses more on classes of func­tions that are com­putable, such as P (func­tions com­putable in poly­no­mial time) and NP (func­tions whose out­puts are ver­i­fi­able in poly­no­mial time).
5) Cat­e­gory the­ory: A cat­e­gory is an alge­braic object con­sist­ing of a class of objects and a class of mor­phisms (“arrows”) between them, such that we are allowed to com­pose mor­phisms asso­cia­tively and there exists an iden­tity arrow from each object to itself. For exam­ple, Set is a cat­e­gory where the objects are sets and the mor­phisms are set func­tions, and any monoid can be made into a cat­e­gory with one object x, with mor­phisms x -> x cor­re­spond­ing to each ele­ment of the monoid. Cat­e­gory the­ory takes cat­e­gories to be the basic objects of study. By abstract­ing many com­mon math­e­mat­i­cal struc­tures, the lan­guage of cat­e­gory the­ory has proven use­ful in a vari­ety of fields, most notably alge­braic geom­e­try and alge­braic topol­ogy. In fact, cer­tain cat­e­gories called topoi pro­vide an alter­na­tive foun­da­tion to math­e­mat­ics; that is, just like an axiomatic set the­ory, all of math­e­mat­ics could be per­formed inside such an object.

Logic and foun­da­tions courses at Prince­ton [Show]Logic and foun­da­tions courses at Prince­ton [Hide]
Classes in logic and foun­da­tional math­e­mat­ics are gen­er­ally based in the phi­los­o­phy depart­ment, with some crosslisted with math­e­mat­ics. There is also at least one course of inter­est taught in the com­puter sci­ence depart­ment. Rel­e­vant pro­fes­sors include Edward Nel­son in the math­e­mat­ics depart­ment, John Burgess and Hans Halvor­son in the phi­los­o­phy depart­ment, and sev­eral pro­fes­sors in the com­puter sci­ence department’s the­ory group. In addi­tion to the classes listed below and in the Under­grad­u­ate Announce­ment, there are often grad­u­ate courses; for exam­ple PHI 520: Logic, PHI 536: Phi­los­o­phy of Math­e­mat­ics, and Pro­fes­sor Nelson’s classes in the math­e­mat­ics depart­ment.
MAT 312: Math­e­mat­i­cal Logic
This class assumes no prior knowl­edge and begins with first order the­o­ries. Early top­ics include the Tau­tol­ogy The­o­rem and Gödel Completeness/Incompleteness. It could be con­sid­ered a sur­vey of math­e­mat­i­cal logic and foun­da­tions, since it briefly cov­ers the­o­rems and top­ics in proof the­ory, model the­ory, and set the­ory. For the past two years, the course has cov­ered chap­ters one through four of Shoenfield’s Math­e­mat­i­cal Logic for the first half of the semes­ter. The sec­ond half of the semes­ter usu­ally cov­ers set the­ory, with more advanced mate­r­ial at the end. For exam­ple, in spring 2011, Inter­nal Set The­ory was the last topic cov­ered. The work­load and pace tend to be rea­son­able, although Shoen­field can be dense and lacks exam­ples.
PHI 323/MAT313: Advanced Logic
This course has recently been used as a top­ics course by Pro­fes­sor Halvor­son, who has taught classes in cat­e­gory the­ory and model the­ory recently under this num­ber. Going for­ward, Pro­fes­sor Burgess reports that it will be a course in set the­ory get­ting at least through a proof of the con­sis­tency of the axiom of choice. The fol­low­ing is a descrip­tion of the course when it focused on model the­ory.
This course served as an intro­duc­tion to model the­ory: a branch of logic con­cerned with the var­i­ous ways that inter­nally con­sis­tent sets of axioms may be imple­mented in con­crete math­e­mat­i­cal struc­tures (e.g. rings, fields, groups, etc.). Such a struc­ture is called a “model” of the axioms. As an exam­ple, con­sider the Peano axioms for arith­metic. The inte­gers are then a model of these axioms, and one may inquire as to whether other such mod­els exist. Using basic tools of model the­ory, it is not too hard to show that the answer is “yes.” Even more sur­pris­ingly, it is pos­si­ble to find mod­els of the Peano axioms hav­ing arbi­trar­ily large car­di­nal­i­ties. This turns out to be a very gen­eral phe­nom­e­non.
Despite a bevy of other curi­ous results in this vein, model the­ory, like most of math­e­mat­i­cal logic, is con­sid­ered some­what periph­eral to main­stream math­e­mat­ics. As a result, the course tended to focus on appli­ca­tions to “real” math and to present the mate­r­ial in a style amenable to this end. This proved to be an inter­est­ing approach, as model the­ory is rife with unex­pected con­nec­tions to alge­braic geom­e­try and com­mu­ta­tive alge­bra, often pro­vid­ing fresh albeit non-intuitive insights and decep­tively short proofs of dif­fi­cult the­o­rems. How­ever, the non-model-theoretic prob­lems which have been solved with model the­ory are few and far between. Thus, the mate­r­ial in this course is prob­a­bly non-essential for the stu­dent with­out a strong inter­est in math­e­mat­i­cal logic. Con­versely, for any­one with such an inter­est, the mate­r­ial in this course should pro­vide a solid foun­da­tion for future research in the sub­ject.
COS 487: The­ory of Com­pu­ta­tion
Basic com­putabil­ity the­ory, com­pu­ta­tional com­plex­ity classes, top­ics rel­e­vant to the­o­ret­i­cal com­puter sci­ence. The first part is a sub­stan­tial over­lap with PHI 312. Although the class for­mally lists COS 340 as a pre­req­ui­site, in real­ity all that is needed is a famil­iar­ity with math­e­mat­i­cal argu­ments, and there have been no issues with get­ting per­mis­sion to take this class with no com­puter sci­ence back­ground.
PHI 312: Inter­me­di­ate Logic.
This course is taught by Pro­fes­sor Burgess; it cov­ers top­ics in logic and com­putabil­ity the­ory such as Tur­ing machines and Gödel’s Incom­plete­ness The­o­rem. The course starts slowly from the math­e­mat­ics point of view in order to bring the phi­los­o­phy majors up to speed, but it gets more inter­est­ing quickly.
PHI 324: Cat­e­gory The­ory
This course is taught by Hans Halvor­son, and it used to be under the list­ing PHI 323: Advanced Logic. It is an intro­duc­tion to cat­e­gory the­ory using the stan­dard text in the field, Mac Lane’s Cat­e­gories for the Work­ing Math­e­mati­cian.
PHI 340: Philo­soph­i­cal Logic
Philo­soph­i­cal Logic (PHI340) is a course that is usu­ally offered every other year and only assumes basic pre­vi­ous knowl­edge of logic (mostly in the form of boolean vari­able manip­u­la­tion and know­ing how to pro­duce rig­or­ous proofs, which math majors should be famil­iar with). It is con­sid­ered a phi­los­o­phy course because it dis­cusses extensions/alternatives to clas­si­cal logic that can be used to model things like time, neces­sity and pos­si­bil­ity. In Burgess’s words, “Philo­soph­i­cal logic […] is the part of logic deal­ing with what clas­si­cal leaves out, or allegedly gets wrong.” The top­ics that are cov­ered each year may vary, but the are usu­ally included in pro­fes­sor Burgess’s book Philo­soph­i­cal Logic.
Ini­tially, tem­po­ral logic is intro­duced. Tem­po­ral logic attempts to allow log­i­cal state­ments to take time into account. As such, axioms for describ­ing time as we con­sider it in every­day life (con­tin­u­ous) or as is used in com­puter sci­ence (dis­crete) are pre­sented, and the philo­soph­i­cal debates sur­round­ing them are also dis­cussed. After­words, modal logic, which attempts to intro­duce the con­cept of neces­sity and pos­si­bil­ity, is pre­sented. Again, an axiomatic approach for prov­ing the­o­rems is given, and sound­ness and com­plete­ness proofs are also dis­cussed. Both tem­po­ral and modal logic can be con­sid­ered as exten­sions of some form to clas­si­cal logic, and are thus also called “extra-classical” log­ics.
The sec­ond half of the semes­ter deals with “anti-classical” log­ics, which not only try to add parts of logic that are miss­ing, but fix parts of logic that are “wrong”. As such, the var­i­ous types of log­ics pre­sented dis­cuss the pos­si­bil­i­ties of mul­ti­ple truth val­ues, as well as other con­tro­ver­sial state­ments regard­ing the notions of truth and the valid­ity of tau­tolo­gies and deduc­tions.
Because of pro­fes­sor Burgess’s math­e­mat­i­cal back­ground as well as the mix­ture of the class (which usu­ally con­sists of approx­i­mately equal phi­los­o­phy and math majors), the lectures/discussions are very inter­est­ing and intel­lec­tu­ally sim­u­lat­ing. And because the course is prob­lem set based (which require rigor!), math majors will find this class to be a great fit.

Con­tacts [Show]Con­tacts [Hide]
Evan Warner ’12 (ebwarner[at]stanford[dot]edu) for gen­eral ques­tions
Mark Pullins ’13 (mpullins[at]princeton[dot]edu) for ques­tions on MAT 312
Simon Segert ’14 (ssegert[at]princeton[dot]edu) for ques­tions on PHI 323
Ilias Giechask­iel ’13 (igiechas[at]princeton[dot]edu) for ques­tions on PHI 340