Math 461 - Mathematical Logic
Description
Math 461 is an introduction to mathematical logic, which, roughly speaking, is the study of formal reasoning and language within mathematics. Beyond the proof techniques and set theory seen in, for example, Math 411, mathematical logic considers questions concerning:
- what structures and subsets of structures are definable by formal language;
- what problems are algorithmically solvable; and
- what statements are provable in a given formal system.
In particular, Math 461 gives an introduction to concepts like provability in first-order logic and definability in structures like graphs and fields. Much of the interesting material of 461 is concerned with definability in these structures as well as strange models of sets of axioms like Peano arithmetic.
Math 461 is usually taken as an additional math elective as it does not satisfy algebra or analysis requirements. Its material is somewhat unique while being highly motivated by and connected to other subjects in the undergraduate curriculum. As such, it is recommended for students curious about foundations and metamathematics.
Topics covered
Topics covered in Math 461 usually include:
- Elementary set theory
- Countable and uncountable sets
- The Schröder-Bernstein theorem
- Relations, orders, and order isomorphisms
- Propositional logic
- Truth and satisfaction
- The compactness theorem, applications, and equivalence to Kőnig’s lemma
- First-order logic
- Structures and Tarski’s definition of truth
- Axiomatizability and definability
- Deductions and the soundness theorem
- Gödel’s completeness theorem and applications
Sometimes more emphasis is put on applications versus further topics like incompleteness. Time allowing, more model-theoretic material may be covered, including:
- Elementary equivalence and elementary embeddings
- Completeness, model completeness, and the Łos-Vaught theorem
- Quantifier elimination
Comments on prerequisites
While the course has only basic prerequisites, logic is said in general to demand “mathematical maturity” out of students. In particular, it is useful to have familiarity with structures in math, i.e. sets equipped with operations and relations obeying formal axioms. A close familiarity with proof techniques taught in 300 and 311 are also highly recommended, as well as set-theoretic reasoning.
Resources
Textbook
The usual textbook for the class is A Mathematical Introduction to Logic by Herbert Enderton. This textbook is standard and aligns with many iterations of 461. While it is often optional, it can be used for further reading.
Additional resources
Some past course webpages are available online.
- Spring 2024, taught by Tom Benhamou: https://sites.math.rutgers.edu/~tb822/Math461.html.
- Spring 2017, taught by Simon Thomas: https://sites.math.rutgers.edu/~sthomas/461.html. Includes lecture notes which may be useful.
For the extra curious, the Open Logic Project is a free compendium for mathematical logic aiming to serve as an introduction to the field with no prerequisite knowledge necessary.