MATH 713 -- MATHEMATICAL LOGIC II:
	   INCOMPLETENESS, UNDECIDABILITY, COMPUTABILITY	


TIME & ROOM: MWF at 1:00 in MTH 1313

INSTRUCTOR:  David W. Kueker
	     Office:  MATH 1102
	     Phone:   405-5052
	     e-mail:  dwk@math.umd.edu
	     Office hours: by appointment

DESCRIPTION: Following an introduction to computable (recursive) functions,
	MATH 713 presents the classic incompleteness and undecidability
	results of K. Godel, A. Church, A. Tarski and others.  These include
	the incompleteness of elementary arithmetic, the undecidability of
	first-order logic, the undecidability of the theories of various
	types of mathematical structures, and the unsolvability of Hilbert's
	10th Problem.  The remainder of the course will cover some topics
	in recursion theory, including partial recursive functions, Turing
	degrees, and the arithmetic hierarchy. Familiarity with first-order
	logic through the completeness theorem is assumed.

OUTLINE:			MATH 713

	C.  Incompleteness and Undecidability

	    Chapter 7.  Informal Introduction to Decidability Problems
	    Chapter 8.  Recursive Functions, Representability, Incompleteness
	    Chapter 9.  Undecidablility

	D.  Recursion Theory

	    Chapter 10. Partial Recursive Functions
	    Chapter 11. Relative Recursion, Turing Reducibility & Degrees
	    Chapter 12. Arithmetic Hierarchy

EXAM SCHEDULE:			Spring 2007

	Midterm: Monday 2 April 
	Final: Monday 14 May 1:30-3:30