What, when, where?

Course ID: | Math 571 |

Time: | MWF 8:50—9:40AM |

Place: | Van Vleck Hall B123 |

Instructor

Mariya Soskova | |

Office: | 523 Van Vleck |

Email: | msoskova@math.wisc.edu |

Office hours: | MW 9:45AM—10:45AM |

Course description and textbook

A summary of the course information can be downloaded here.
This course provides an introduction into mathematical logic, including the syntax and semantics of first-order languages, a formal calculus for proofs, Gödel's completeness theorem and the compactness theorem, nonstandard models of arithmetic, decidability and undecidability, and Gödel's incompleteness theorem. We will mainly be following A Mathematical Introduction to Logic, Second Edition by Herbert B. Enderton, ISBN 978-0122384523. Homework will include problems form this book. |

Exams and evaluation

There will be two midterms and one final exam. Your final grade will be determined using the formula:
Midterm 1: | October 12th (5:30PM to 7:00PM Room 5231 Social Science Building) |

Midterm 2: | November 16th (5:30PM to 7:00PM Room 5231 Social Science Building) |

Final: | December 19th (2:45PM—4:45PM) |

Homework

Every Friday you will receive a new homework assignment. Homework will be due the following Friday at the beginning of class. Late homework will not be accepted.
Homework will be graded for completeness and one problem (selected at random) will be graded for correctness.

Recall that this is a proof-based course, and thus a strict level of rigor is necessary in your solutions. Pictures are never proofs, but are always encouraged along with proofs. Your solution should not be just a sequence of equations and formulas, write in complete sentences.

It is okay, even encouraged, if you work on the homeworks in groups. If you do, please acknowledge that in your homework. The solutions you submit, have to be written by each student individually. Copying is not allowed and will be acted against.

HW 1(due Sept 15) | Section 1.1: Ex 3, Ex 5; Section 1.2: Ex 2, Ex 5, Ex 8, Ex 9. |

HW 2(due Sept 22) | Section 1.2: Ex 10 a and b, Ex 11, Ex 13; Section 1.3: Ex 3, Ex 4(read the parsing algorithm in Section 1.3 and design a similar algorithm to parse formulas with no right parentheses.) |

HW 3(due Sept 29) | Section 1.4: Ex 1(Omit the question about C4), 3; Section 1.5 Ex 1, Ex 3(since we did not have time to cover this material Ex 3 will be moved to HW4), as well as the exercise you can find here. |

HW 4(due Oct 6) | Section 1.5: Ex 3 (Hint: Show that all Boolean functions realized with the given connectives give opposite values to arguments (T,T,..., T) and (F,F,..F)), Ex 4, Ex 9, Ex 10; Section 1.7: Ex 4. |

HW 5(due Oct 13) | Section 1.7: Ex 10, Ex 12, as well as the exercises you can find here. |

HW 6(due Oct 20) | Section 2.1: Ex 3, Ex 4, Ex 5; Section 2.2: Ex 1, Ex 2. Note that the last two exercises are on notions that we will discuss next Monday and Wednesday. |

Honors Assignement

To complete this class with honors, you must turn in several Honors Assignements that will be posted in the course of the semester. Each assignement is worth 10 points and is counted towards the homeowrk grade. HA 1(due Oct 23) | You can find the first assignemen here . For Problem 1 you can use the fact that the sum of the entries in the nth row of Pascal's triangle is the nth power of 2. (See here) Deadline extended to Monday Oct 23! |