Math 430: Formal Logic

# General Information

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

Instructor: Matthias Aschenbrenner
Homepage: http://www.math.uic.edu/~maschenb
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.

# Description

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.

# Homeworks

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:

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.

# Exams

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.

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.

Course grades are roughly computed as follows:

90-100 A
80-89 B
70-79 C
60-69 D
below 60 E

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)