MA201: Mathematical Logic and Theory of Computation

Course Syllabus for "MA201: Mathematical Logic and Theory of Computation"

Please note: this legacy course does not offer a certificate and may contain broken links and outdated information. Although archived, it is open for learning without registration or enrollment. Please consider contributing updates to this course on GitHub (you can also adopt, adapt, and distribute this course under the terms of the Creative Commons Attribution 3.0 license). To find fully-supported, current courses, visit our Learn site.

Mathematics is about structure, about reasoning, and about modeling.  This course braids these three threads together.  Mathematical logic began as the study of the reasoning used in mathematics, but it turns out to be useful in describing the mathematical concept of structure and in modeling automated reasoning—that is, modeling computation. 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.

Learning Outcomes

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.

Course Requirements

In order to take this course you must:

√    Have access to a computer.

√    Have continuous broadband Internet access.

√    Have the ability/permission to install plug-ins or software (e.g., Adobe Reader or Flash).

√    Have the ability to download and save files and documents to a computer.

√    Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).

√    Be competent in the English language.

√    Have read the Saylor Student Handbook.

√    Be comfortable with mathematical proofs like those you might see in MA231: Abstract Algebra I or MA241: Real Analysis I.

Note: Familiarity with the key examples of MA231, while not strictly necessary, will be helpful in Unit 1.

Course Information

Welcome to MA201. Below, please find general information on this course and its requirements.

Course Designer: Prof. Wesley Calvert

Primary Resources: This course is composed of a range of different free, online materials. However, the course makes primary use of the following materials:

Requirements for Completion: In order to complete this course, you will need to work through each unit and all of its assigned materials.

In order to pass this course, you will need to earn a 70% or higher on the Final Exam. Your score on the exam will be tabulated as soon as you complete it. If you do not pass the exam, you may take it again.

Table of Contents: You can find the course's units at the links below.