Math 430: Formal Logic

General Information

Time and Place: MWF 9-9:50am, 219 Taft Hall
Control Number: 20084/20442

Instructor: Matthias Aschenbrenner
E-mail address: 
Office:  417 SEO (notice change of office!)
Office Phone: (312) 413-2149
Office Hours: MWF 10-11am, or by appointment.

Prerequisites: Grade of C or better in CS 202 or grade of C or better in MCS 261 or grade of C or better in MATH 320.

Downloading files from this website requires software to display PDF files, such as Acrobat Reader or Ghostview.

Click here to download the class information handout.


The main objective of this course is to introduce you to first-order logic and study various aspects of it:

1. Pure logic: Syntax and semantics of first-order languages. The Completeness Theorem.

2. Basic model theory: Löwenheim-Skolem Theorems. Compactness Theorem. Elementary equivalence.

3. Fundamentals of the theory of computability: Enumerability and decidability. Register machines. The halting problem. Undecidability of first-order logic. Gödel's Incompleteness Theorems.

Course Text

Recommended text: Mathematical Logic, Second edition, by  H.-D. EbbinghausJ. Flum, and  W. Thomas.


There will be a problem set due every two weeks or so, to be handed in at the beginning of class. Up to 3 individuals may work together on homework problems (and I encourage you to do so), but when you turn in the problem set you should acknowledge that you have collaborated. No late homework will be accepted.

Put the following information in the upper right hand corner of the first page:

   Your Name(s)
    Math 430, Homework # number.

On each additional page, put your name(s) in the upper right-hand corner. Work single-sided, that is, write on only one side of each sheet of paper. STAPLE any homework that is more than one page long. Remove all perforation before submitting. Write legibly. Homework that fails to meet the above requirements will be marked ``Unacceptable'' and returned unread.

 Problem Set 1, due September 17.  Solutions
 Problem Set 2, due September 24.  Solutions.
 Problem Set 3, due October 11.  Solutions.
 Problem Set 4, due November 1.  Solutions.
 Problem Set 5, due November 29.  Solutions.
 Problem Set 6, due December 3.

For a summary of the rules of the sequent calculus click here.


There were two midterm examinations, in class, on Monday, September 27, and on Friday, November 5.No makeup exams will be given.

The final exam will take place on Tuesday, December 7, 8:00-10:00am, in 219 Taft Hall

A review session for the final will be held on Monday, December 6, 4:00-6:00pm, in  636 SEO.

Click here  for a study guide for the final exam.

Students with final examinations which conflict with the Math 430 final examation are responsible for discussing a makeup examination with me no later than 12/03.

No books, calculators, scratch paper or notes will be allowed during exams. Students are expected to be thoroughly familiar with the University's policy on academic integrity. The University has instituted serious penalties for academic dishonesty. We have encouraged you to work with your classmates on homework. Regarding homework, midterm exams, and the final examination:

Copying work to be submitted for grade, or allowing your work to be submitted for grade to be copied, is considered academic dishonesty.

It is University policy that students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services.


Your course grade is based on your homework scores (20%), your midterm exam scores (each 20%), and your final exam score (40%).

Course grades are roughly computed as follows:

% of points Grade
90-100 A
80-89 B
70-79 C
60-69 D
below 60 E

Comments and Questions

Use an anonymous remailer to send comments on the class (including suggestions, complaints, and compliments) and questions about the course material to the instructor (e-mail address see above).

Do not use this form to address personal concerns. All other matters specific to your situation (for example, your performance in class) should be sent by usual e-mail.

Your submission may remain anonymous, but please provide your name and e-mail address if you would like a personal response. Please indicate whether I may publish your question and my response to it on this webpage.

Historical Information

``Contrariwise,'' continued Tweedledee, ``if it was so, it might be; and if
it were so, it would be; but as it isn't, it ain't. That's logic.''
 Lewis Carroll  (1832-1898)

Click below to learn more about some of our logic heroes:

 Wilhelm Ackermann
 Paul Bernays
 George Boole
Georg Cantor
 Alonzo Church
 Paul Cohen
 René Descartes
 Richard Dedekind
 Adolf Fraenkel
 Gottlob Frege
 Gerhard Gentzen
 Kurt Gödel
 Jacques Herbrand
 David Hilbert
 Stephen Kleene
 Gottfried Wilhelm Leibniz
 Ramon Llull
 Leopold Löwenheim
 Augustus de Morgan
 John von Neumann
 Guiseppe Peano
 Emil Post
 Abraham Robinson
 Bertrand Russell
 Thoralf Skolem
 Alfred Tarski
 Alan Turing
 Alfred North Whitehead
 Ernst Zermelo

Back to my homepage

Last modified 12/01/04.