**Section:**001

**Term:**WN 2018

**Subject:**Mathematics (MATH)

**Department:**LSA Mathematics

This course is about two fundamental concepts of mathematics: computability and provability. The first topic to be covered is a precise definition of computability in principle, where "in principle" means that a computation must give a result after finitely many steps but we place no specific bounds on the number of steps or the amount of memory used. In fact, several precise definitions of computability have been proposed, but they all turn out to be equivalent. We shall discuss a few of them and develop the tools needed to prove their equivalence. We shall also discuss the connection between computability and definability, giving specific examples of definable but uncomputable functions.

The second part of the course, building on the concepts and techniques of the first part, explores the limits of provability in axiomatic systems. It includes the proof of Goedel's incompleteness theorems --- that reasonable axiomatic systems cannot exactly capture truth, even in the limited domain of the arithmetic of natural numbers, and that they cannot prove their own consistency.

The final part of the course is a deeper study of computability, and in particular a classification of uncomputable functions according to a criterion of the form "if we had access to values of f then we could compute values of g." The analysis of this relation has led to some deep andelegant arguments, the simplest of which will be covered in this course.

**
Text:** Fundamentals of Mathematical Logic , Peter G. Hinman Optional

**Course Requirements:**

No data submitted

**Intended Audience:**

Prerequisites: It is useful to have had a first course in mathematical logic, but it is not strictly necessary if you are willing to take some basic facts on faith.

**Class Format:**

No data submitted

*NOTE: Data maintained by department in Wolverine Access. If no textbooks are listed below, check with the department.*

**ISBN: 9781568812625**

**Optional**

**IMPORTANT:**These syllabi are provided to give students a general idea about the courses, as offered by LSA departments and programs in

**prior academic terms**. The syllabi

**do not**necessarily reflect the assignments, sequence of course materials, and/or course expectations that the faculty and departments/programs have for these same courses in the current and/or future terms.

*Click the button below to view historical syllabi for MATH 684 (UM login required)*

View Historical Syllabi

CourseProfile (ART)