### Math 430: Formal Logic.

Instructor: Sherwood Hachtman

e-mail: hachtma1 at uic dot edu

Lectures: 9am-9:50am in Addams Hall 306.

Office hours: Monday and Tuesday 11am-12pm in SEO 616, or by appointment.

**Textbook:** Herbert Enderton, *An Introduction to Mathematical Logic*, Second Edition.

**Course description:**
Mathematical logic is the study of mathematics via the representation of mathematical *discourse* as a mathematical *object*. We will rigorously define the notion of proof

, see how to represent axioms, theorems, and proofs in a formal language, investigate the power and limitations of this language, and apply these results to prove theorems in ordinary mathematics, such as algebra and combinatorics. The course has three main components:
- Propositional logic: An introduction to formal languages.
- First-order logic: Formalizing the language of mathematics. Semantics and syntax. The deductive calculus. Gödel's completeness theorem. The compactness theorem and applications.
- Number theory: Codifying proof systems in the language of natural number arithmetic. Gödel's incompleteness theorem.

Experience writing and reading proofs is an essential prerequisite for the course. Some acquaintance with mathematical structures, e.g. in algebra (groups and rings) or combinatorics (graphs and trees) will be helpful, thought not essential.

**Materials:**

Notes for Week 1: Basic set theory

Homework 1. Due Wednesday, January 20.

Homework 2. Due Friday, January 29.

Homework 3. Due Wednesday, February 3.

Homework 4. Due Friday, February 12.

Review problems for the first midterm.

Homework 5. Due Friday, February 26.

Homework 6. Extended to Friday, March 11.

Homework 7. Due Wednesday, March 16.

Homework 8. Due Wednesday, March 30.

Homework 9. Due Wednesday, April 6.

Solutions to midterm 2.

Homework 10. Due Wednesday, April 20.

Homework 11. Due Friday, April 29.

Review problems for the final exam.

**Course policies:**

Grading:

Homework will be assigned once a week. There will be two midterm exams, given in class, and a final exam. Final grades will be determined according to the following breakdown:
- 25% Homework
- 20% Midterm 1: on Friday, February 19
- 20% Midterm 2: on Friday, April 8
- 35% Final exam

Homework is a major component of the course. Collaboration on the homework is encouraged, but any assignment you hand in must be your own work. A good way to ensure this is the case is to write your final write-up in isolation (without peers or the internet). You should acknowledge any sources for the ideas used in your write-up.