Logic: Courses

Course Descriptions | Books in Mathematical Logic

Studying Mathematical Logic at UIUC

Mathematical logic became, mostly within the 20th century, the mathematical study of logical reasoning. This study clarified the nature and limitations of the axiomatic method and yielded new concepts and techniques for use within mathematics.

The starting point, and a distinctive feature of mathematical logic, is the introduction of suitable formal languages. For assertions (sentences) in such a language, key notions are "provability" and "truth". To formulate a formal system for proving sentences requires the introduction of axioms and rules of inference. Truth of sentences depends on fixing a universe of discourse and appropriate meanings for the special symbols in the language.

In our introductory courses (Math 414 at the undergraduate level and Math 570 at the graduate level) we set up this basic framework for first-order logic, and study the fundamental and sometimes surprising connections between provability and truth. Mathematical logic is traditionally seen as being roughly composed of four main areas: model theory, set theory, computability theory, and proof theory. The first two of these areas are well represented in our group and are covered extensively in the graduate courses that we offer above Math 570.

Discussion of Courses

Two introductory courses (Math 414 and Math 570) are offered in logic. Math 414 is primarily for undergraduates. Math 570 is a prerequisite for all other graduate courses in logic and is also the best course for a graduate student who wants to take a single semester of logic. Math 570 is one of the basic courses in the Comprehensive Exams system of the PhD program in the UIUC Department of Mathematics. Students who have had a course similar to Math 570 elsewhere and wish to go directly into other graduate logic courses should consult a faculty member in logic to be sure that they have the necessary prerequisites.

Normally Math 414 is offered every spring and Math 570 is offered every fall; courses at the next level are Math 571,  Math 573, and Math 574 and they are offered regularly. Math 595 is a topics course usually offered every semester. Its content varies widely from one offering to the next. It may be either an advanced continuation of a regular course or a course in a different area from the regular courses. Math 597 is a reading course which may be arranged with a faculty member on any advanced topic of interest to the student. There is no limit to the number of times a student may register for Math 595 or Math 597.

Students majoring in logic should give serious consideration to taking some courses in computer science and gaining practical experience with computers. There are a number of important links between computer science and logic and, as a practical matter, a strong background in computer science (combined with logic) can be of benefit in job hunting.

Course Descriptions

Math 414. Introduction to Mathematical Logic

This is usually taken by junior or senior mathematics majors. Math 414 is concerned with the logical framework for mathematical reasoning. To begin, emphasis is placed on formalizing mathematical and other statements and on gaining familiarity with the formal languages studied. Next a concept of formal provability is introduced, motivated by the goal of understanding deductive reasoning in a precise way. It is clear that any sentence which is provable from a set of axioms should be true in any interpretation of the language under which all the axioms are true. This is the minimum requirement on a formal concept of proof, that only true formulas can be proved. The main technical result discussed in this course is the Completeness Theorem, proved in 1930 by Kurt Gödel, which states that the converse holds: the sentences which are formally provable from a particular set of axioms are exactly the sentences which are true in all models of the axioms. This shows that the specific concept of provable sentence which is studied gives a complete and correct analysis of the informal concept of "provable statement" in much the same way that integration theory gives a correct interpretation of the intuitive idea of "area." This course also discusses the fact that there cannot be an effective algorithm for determining which sentences are formally provable.

Math 570. Logical Foundations of Mathematics

This is the beginning graduate level course in logic, and it is a prerequisite for all later courses. It covers the subject matter treated in Math 314, including the important Completeness Theorem, at a more rapid pace and a deeper level, together with a careful study of formalized elementary number theory. Number Theory is a typical and simple example of a mathematical theory to which the ideas developed earlier can be applied. Moreover, the consequences of doing so are fundamental for all mathematical theories. The main result about formal number theory is the Incompleteness Theorem, also due to Gödel. Consider an axiom system for number theory which consists of sentences which are true in the usual model of the natural numbers and which contains a few specified axioms. Suppose further that there is an algorithm which is capable of deciding which number-theoretic sentences are axioms and which are not. This is a minimum requirement that a reasonable formal axiomatization of number theory should satisfy. Then Gödel's Incompleteness Theorem gives a procedure for constructing a specific sentence of number theory which is true but not provable. That is, no such axiomatization can capture all the true sentences of number theory among its theorems. Moreover, this result is not limited to number theory, but applies to any mathematical theory which is at least as strong as number theory. In particular, it applies to set theory or any other theory which is used to provide a foundation for mathematics as a whole. Thus, mathematics is prevented from ever having a reasonable axiomatic foundation whose theorems include all true mathematical statements.

Math 571. Model Theory

The general goal of model theory is to come to as complete an understanding as possible of the class of all models of a given set of axioms and of the relations between models and the sentences which they satisfy. An important aspect of this course is to show how model theory can be applied to various familiar mathematical theories such as linear orderings, algebraically closed fields, real closed fields, etc. For example, Tarski's Theorem which gives an algorithm for deciding whether a given sentence is true in the field of real numbers is often proved.

Another important part of this course is the development of various methods for constructing models of particular sets of sentences. One basic method is based on the Goedel Compactness Theorem which is closely related to the Completeness Theorem discussed above. This Compactness Theorem states that if S is a set of formal sentences and if every finite subset of S has a model, then there is a model for S itself. For example, if S is countable and if S has a model whose universe is an infinite set, then the Compactness Theorem can be used to obtain models of S whose universes have arbitrarily large cardinality. This immediately yields the existence of non-standard models for a wide variety of theories such as elementary number theory or real analysis. Many other methods of constructing models are developed and used in this course.

Also studied here are properties of axiom systems which can be expressed as algebraic properties of the class of models but which also turn out to be expressible purely in terms of the syntax of sentences. For example, if the class of models of S is closed under formation of substructures, then there is a system of axioms which is equivalent to S and which consists entirely of axioms containing no quantifiers.

Math 573. Computability Theory

The intuitive notion of computability is introduced and various formal notions of computability are given. These notions include computability by abstract digital computers (such as Turing machines or register machines), and generation from certain basic functions by operations such as composition and recursion. Proof of equivalence of the formal notions is sketched and evidence is given for the Church-Turing Thesis, which asserts the equivalence of the intuitive and the formal notions. The existence of a universal Turing machine, which can simulate the action of any other Turing machine, is established and used to show the algorithmic unsolvability of the halting problem for Turing machines. This leads to many other unsolvability results.

A set A of objects (for example, a set of natural numbers) is called computable if there is an algorithm for testing membership in A. The set A is called computably enumerable if there is an effective procedure which, when given an element of the set as input, halts in finitely many steps, but otherwise runs forever. The halting problem for a universal Turing machine is an example of a computably enumerable set which is not computable. Other examples are the set of sentences provable from the usual axioms of set theory or of number theory and the set of Diophantine equations (with integer coefficients) which have integer solutions.

Let A and B be sets of natural numbers. One says that A is Turing reducible to B if there is an algorithm for determining whether a given natural number is in A given a black box or "oracle" which can answer individual membership questions about B. It is shown that there exist computably enumerable sets A and B such that neither is Turing reducible to the other. More generally, Turing reducibility is studied both on computably enumerable sets and on arbitrary subsets of the natural numbers as a means toward understanding the relative complexity of sets of natural numbers.

Math 574. Set Theory

This is an introductory graduate course in set theory. The first one third of the course is devoted to a systematic development of basic notions and results of set theory such as, for example, ordinal numbers, cardinal numbers, transfinite recursion, and elements of cardinal arithmetic. The remaining two thirds of the course is devoted to one of the following topics (chosen by the instructor and varying from one offering the the course to another):
I. An introduction to the constructible universe L including a proof of the Continuum Hypothesis in L followed by an introduction to forcing with a proof of the consistency of the negation of the Continuum Hypothesis.
II. Elements of descriptive set theory, that is, the theory of Borel, analytic, and co-analytic subsets of complete, separable metric spaces up to the uniformization theorems and the determinacy of certain infinite games.

New courses:

Four other graduate courses are offered (on an irregular basis) as topics courses. Descriptions follow.

Descriptive Set Theory

This is a second course in set theory. Material to be covered will be chosen from the following topics: classical theory of Borel, analytic and coanalytic sets; infinite games with perfect information; effective methods with their applications to Borel equivalence relations.

Prerequisite. Math 574 or consent of the instructor.

Details: Descriptive set theory studies the structure of definable subsets of complete separable metric spaces and quotients of such spaces by definable equivalence relations. It is one of the central areas of set theory with many applications to other areas of mathematics. Recently, its notions and methods have been used in areas as diverse as topological dynamics, classification problems in algebra, and general topology. Descriptive set theory is part of the standard education of the set theorist and is relevant to students working in other areas of logic and outside of it.

Stability Theory.

Forking in stable theories, stable group theory, and elements of geometric stability theory such as the geometry of strongly minimal sets and 1-based groups.

Prerequisite: Math 571 or consent of the instructor.

Details: Stability theory was originally developed by Shelah, following earlier work by Morley, as part of Shelah's program of classifying first order theories according to whether their class of models can be classified by "nice" invariants. This body of work and machinery is the topic of several books, and has become rather central to contemporary model theory. The ideas are being extended within model theory beyond the rather restricted class of stable theories. Moreover, the theory has applications in algebra, geometry, and number theory.

O-Minimal Structures

The theory of o-minimal structures is on the one hand a far reaching generalization of topics like the geometry and topology of semialgebraic and subanalytic sets, and on the other hand a lively subject in model theory. The course will reflect these two aspects.

Prerequisites: Math 570 or consent of instructor

Details: O-minimality is an active area in model theory, and has also captured the interest of real analytic geometers, because it gives a general framework for understanding finiteness and tameness phenomena in real analytic situations. (A big open question of this type is the second part of Hilbert's 16th problem that concerns limit cycles of polynomial vector fields in the plane.) UIUC is one of the main centers for the subject.

Nonstandard Analysis

Prerequisite: Math 570 or consent of the instructor. (Some familiarity with predicate logic is assumed; more than enough is covered in the first half of Math 570 or in a good undergraduate course in logic.)

Details: This branch of applied model theory originated in about 1960 in work of the logician Abraham Robinson. In the 40+ years since then it has developed into a substantial and clearly identified research area, representing one of the ways in which model theory gets applied to the geometry/analysis side of mathematics. Many applications, especially those in stochastic analysis and functional analysis, are recognized as valuable by specialists from the applications area. This particular course has a minimal logic prerequisite. Assuming prior exposure to basic logic allows one to cover a larger number of applications and thereby to offer a mathematically more substantial set of applications.

Math 595. Advanced Topics in Mathematics

This is a lecture course on a topic of current interest, with the topic varying from semester to semester. Usually one section of Math 595 offered each semester is in advanced topics in logic. There is no limit on the number of times a student may register for Math 595. Advanced graduate students in the logic program are encouraged to register for Math 595 in logic whenever it is offered, in order to increase the breadth of their exposure to current research topics in all parts of the field.

Math 597. Reading Course

This is primarily a way for graduate students to receive credit for individual study of a subject not covered in course offerings. To arrange such a course, the student should ask a suitable faculty member to act as supervisor of the work. Normally Math 597 involves much more self-study than would be the case in a standard course with regular class meetings. Content of the course is completely up to the student and faculty member. There is no limit on the number of times a student may register for Math 597.

• Lou van den Dries (call # for 597/599: 24352 / 25603; section LV)
• o-minimal structures
  
• C. Ward Henson (call # for 597/599: 24345 / 25586; section CWH )
• model theory in functional analysis and metric geometry
  
• Carl G. Jockusch (call # for 597/599: 24318 / 25803; section CGJ)
• Slawomir Solecki (call # for 597/599: 24337 / 25845; section SS)

1. H. B. Enderton, A Mathematical Introduction to Logic.
2. J. R. Shoenfield, Mathematical Logic.
3. J. Barwise, ed., Handbook of Mathematical Logic.
4. C. Smorynski, Logical Number Theory, I.
   

1. C. C. Chang and H. J. Keisler, Model Theory.
2. D. Marker, Model Theory, An Introduction.
3. B. Poizat, A Course in Model Theory.
   

1. H. Rogers, Jr., Theory of Recursive Functions and Effective Computability.
2. R. Soare, Recursively Enumerable Sets and Degrees.
3. P. Odifreddi, Classical Recursion Theory (2 vols)
4. E. Griffor (ed.), Handbook of Computability Theory.
   

1. T. Jech, Set Theory.
2. K.Kunen, Set Theory.
3. A. Kanamori, The Higher Infinite.
4. A. Kechris, Classical Descriptive Set Theory.
5. W. Just and M. Weese, Discovering Modern Set Theory (2 vols).

Comments: (1) and (2) are standard graduate monographs; (3) gives considerable information about large cardinal axioms and other extensions of the basic axioms; (4) is a comprehensive introduction to one of the more important areas for applications in the rest of mathematics; (5) is an introduction that is suitable for self-study.