Mathematical Logic and Theory of Computation (saylor.org)

The logical approach to structure gives an alternate perspective on such other mathematical subjects as combinatorics and abstract algebra. This, for the most part, is described by the area of model theory, which is the focus of Unit 1.

In Unit 2, we will look at modeling computation. The central fact of these models, from a logical standpoint, is that once we can handle a computation as a definable mathematical object, we can prove that certain computations are impossible. The most famous such proof is Gödel’s Incompleteness Theorem, showing that it is impossible to compute truth in a system sufficiently strong to describe natural number arithmetic.

Finally, in Unit 3, we turn to proof theory. Just as modeling computations results in new insights, modeling the process of mathematical proof results in a surprising connection: a proof is analogous to a computation.

These three often interact. Proofs and computations have natural parallels with the language we use to describe structures. Structures from model theory give natural settings for computation, as in Gödel’s Incompleteness Theorem. After completing this course, you will understand all three.

Upon successful completion of this course, the student will be able to:

- Prove categoricity of a first-order theory in simple examples.

- Distinguish elementary and non-elementary properties.

- Describe mathematical models of computation and their respective limitations.

- Use the coding of computations by natural numbers to construct examples and proofs of impossibility.

- Explain the Curry-Howard analogy between proofs and computations.