Math 4010/5010 Fall 2016

(back to home)

Course Information: Syllabus

This will be a one semester course in logic and set theory. Of primary importance will be the completeness and incompleteness theorems of first-order logic and their mathematical amd metamathematical consequences. We will cover basic model theory, recursion theory, and set theory as time permits. Possible extra topics include undecidability/incompleteness results in number theory (Hilbert's 10th problem) and algebra.
We will not use a single book as a text for the class. There will be class notes on the web site. However there are a couple of texts which will make good references. They are:

1.) A Mathematical Introduction to Logic, by H. Enderton.
2.) Model Theory: an Introduction, by D. Marker.
3.) The Foundations of Mathematics, by K. Kunen.

Probably Enderton's book would be a good one to start with for the material we will be covering first. I will give additional references as we go through the course.


Notes on propositional logic: propositional logic.

Notes on first-order logic: first-order logic.

Notes on the incompleteness theorem: incompleteness theorem.



Homework 1:
The first four exercises in the notes on propositional logic. Here they are again.

1.) Give the details of the inductive proof of part (2) of Lemma 3 in the case \( \varphi=(\alpha \to \beta)\). That is, show that if \( \varphi' \) is a proper initial segment of \(\varphi\), then \( \ell(\varphi') > r(\varphi')\).

2.) Show that if \( \nu_1\) and \( \nu_2\) are truth value assignments, \( \varphi \in \text{WFF}\), and \( \nu_1\), \( \nu_2\) agree on the variables in \(\varphi\), then \(\nu_1(\varphi)=\nu_2(\varphi)\).

3.) Show that \( \Gamma \models A\) where \(\Gamma \) is the following set of formulas:

1.) \( (A \vee B) \to (C \vee \neg(A \to D))\)
2.) \( (\neg A \wedge (C \vee D)) \to (\neg C \wedge B)\)
3.) \( (B \vee C) \to (D \vee \neg A)\)
4.) \( ((\neg A \wedge \neg B ) \vee (C \wedge D)) \to ((\neg B \to C) \wedge (D \to \neg A))\)
You can either show this using the definition of \( \models\), or you can give a ``proof'' that from \( \Gamma\) you can deduce \( A\).

4.) Show that all the logical axioms are tautologies.




Homework 2 (due Monday, September 26):
Undergraduates: Exercises 5,6,7,8 of the notes (dated 9/21/2016).
Graduates: Exercises 5,6,8,9 of the notes (dated 9/21/2016).

Homework 3 (due Friday, October 28):
Exercises 3,4,5,6 of the notes on first-order logic (dated 10/19/2016).



Homework 4 (due Monday, 11/14):
Exercises 7, 8, 10, 11 of the notes on first-order logic (dated 11/7/2016).



Second test on Monday, 11/14/2016.


Homework 5 (due Friday, 12/02):
Note on incompleteness theorem dated 11/23/2016, exercises 1, 2, 6, 7.