MATH 6810: Mathematical Logic Spring 2013

Instructor: Richard Shore

Texts:Mathematical Logic by Ebbinghaus, Flum, and Thomas plus supplementary material

This course will be a basic introduction to mathematical logic. The content will, to some extent, depend on the background and interests of the students.

As a common starting point, we will describe and develop a formal syntax for mathematical discourse along with precise semantics by defining both the notions of a formula in a given language and a structure for the language. The next step in our analysis is to give precise definitions of proofs and provability and to establish Gödel’s Completeness Theorem: A sentence is provable (from given axioms) iff it is true in every structure (which satisfies the axioms).

We will next develop some of the basic results of model theory such as the Compactness Theorem: A set S of sentences is consistent (i.e. does not prove a contradiction) iff it has a model (a structure in which every one of the sentences is true) iff every finite subset of S has a model. (Corollary: If a sentence of the appropriate language is true in all fields of characteristic 0, it is true in all fields of sufficiently large characteristic.) The Skolem-Löwenheim Theorem: If a countable set of sentences S has an infinite model then it has a countable one.

We will also develop other connections between the forms of axioms and properties of models. Sample: If a sentence is true in one algebraically closed field of characteristic 0, e.g. in the complexes, then it is true in every algebraically closed field of characteristic 0.

The time devoted to these basic topics will depend on the background of the students. Other topics as time permits and student interest dictates will include some of the following:

  • A brief development of the basic facts of recursion theory (computability theory) to the point that we can prove the undecidability of the halting problem as well as various mathematical theories especially by interpreting one theory in another. Tarksi’s result on the undefinability of truth. Church’s result on the undecidability of first order logic (validity).
  • Decidability or undecidability of some mathematical theories, i.e. algorithms for determining of every sentence if it is a theorem or not.
  • Gödel’s Incompleteness Theorem: Given any reasonable, consistent theory T containing arithmetic, there is a true sentence of arithmetic which is not provable in T (nor, of course, is its negation).
  • The basics of axiomatic set theory to ordinals and cardinals and their arithmetic.