Math 681 — Spring 1999
Mathematical Logic

Instructor: Richard Shore

Time:  TR 1:25-2:40

Room: WE B29

This course will be a basic introduction to mathematical logic. We will describe 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 Goedel's Completeness Theorem: A sentence is provable iff it is true in every structure.

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. Sample 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-Loewenheim Theorem: If a countable set S of sentences 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 complex numbers, then it is true in every algebraically closed field of characteristic 0.

We will also quickly develop the basic facts of recursion theory (computability theory) to the point that we can prove the decidability of various mathematical theories and undecidability of others as well as of the halting problem. We will also prove Goedel's Incompleteness Theorem: Given any reasonable consistent theory of arithmetic T, there is a true sentence of arithmetic which is not provable in T.

Last modified: April 7, 2003