## 116c: Mathematical Logic (Set Theory) – Syllabus

March 31, 2008

Math 116c. Tuesday, Thursday 2:30-4:00 pm. 151 Sloan.

Instructor: Andres Caicedo, caicedo at caltech dot edu, 384 Sloan
Office Hours: By appointment

Grader: Todor Tsankov, todor at caltech dot edu, 260 Sloan
Office Hours: Monday 3-4pm

Math 116 provides an introduction to the basic concepts and results of mathematical logic and set theory. Math 116C will be devoted to set theory. This is formalized following Cantor’s approach of considering ordinals and cardinals; we will present the Zermelo-Fraenkel axioms, explain how different mathematical theories can be modelled inside the set theoretic universe, and discuss the role of the axiom of choice. Once these basic settings have been studied, we will present different combinatorial results and describe Gödel’s constructible universe.

Grading Policy: The grade for this course will be based on homework assignments. There will be no exams.
Solutions to homework problems should be written individually, although collaboration is allowed unless otherwise stated. All references used to solve a problem should be explicitly mentioned, including those students you collaborated with. You cannot look up solutions from any source.
No late submissions of solutions are allowed, except for medical problems (note needed from the health center) or serious personal difficulties (note needed from the Deans office).

Please try to solve as many problems as it seems reasonable from each set.
Let me know if you find some problems to be too hard or too easy or to contain mistakes. Feedback is greatly appreciated.

Textbook: There is no required textbook. The following suggested references may be useful:

• Set theory for the working mathematician. By K. Ciesielski. Cambridge U. Press (1997), ISBN-10: 0521594650  ISBN-13: 978-0521594653
• Set theory. By A. Hajnal and P. Hamburger. Cambridge U. Press (1999), ISBN-10: 052159667X  ISBN-13: 978-0521596671
• Set theory. By T. Jech. Springer (2006), ISBN-10: 3540440852  ISBN-13: 978-3540440857
• Discovering modern set theory. By W. Just and M. Weese. Vol I. AMS (1995), ISBN-10: 0821802666 ISBN-13: 978-0821802663
Vol II. AMS (1997), ISBN-10: 0821805282 ISBN-13: 978-0821805282
• Problems and theorems in classical set theory. By P. Komjath and V. Totik. Springer (2006), ISBN-10: 038730293X  ISBN-13: 978-0387302935
• Set theory. An introduction to independence proofs. By K. Kunen. North Holland (1983), ISBN-10: 0444868399  ISBN-13: 978-0444868398
• Notes on set theory. By Y. Moschovakis. Springer (2005), ISBN-10: 038728723X  ISBN-13: 978-0387287232

Additional references will be provided throughout the course.

## Boise

March 17, 2008

I accepted today BSU’s offer.

## 116b- Lecture 20

March 13, 2008

Given any complete, consistent extension $T$ of $\mathsf{PA}$, we showed that there is a minimal model $K_T$ of $T$. This model is unique up to (unique) isomorphism, it is rigid (i.e., it has no automorphisms other than the identity), and has no proper elementary substructures.

Given a model $M\models\mathsf{PA}$, let $SSy(M)$, the standard system of $M$, be the set of those $A\subseteq\mathbb{N}$ coded by elements of $M$, where $a\in M$ codes $A$ iff $A=\{i\in\mathbb{N} : (a)_i\ne0\}.$ Thus $SSy(\mathbb{N})$ is the class of finite sets. We showed that if $M\models\mathsf{PA}$ is nonstandard, $SSy(M)$ contains all recursive sets, and that for any non-recursive $S$ there is a nonstandard $M\models \mathsf{PA}$ such that $S\notin SSy(M)$.

## 116b- Homework 9

March 11, 2008

Homework 9

Due Tuesday March 18 at 1pm.

## 116b- Lecture 19

March 11, 2008

We showed that Exponentiation is Diophantine, completing the proof of the Davis-Matiyasevich-Putnam-Robinson theorem. The result follows from a careful examination of certain second order linear recurrence relations.

## 116b- Lecture 18

March 10, 2008

Hilbert’s tenth problem asks whether there is an algorithm that given a polynomial with integer coefficients (in an arbitrary number of variables) determines whether it has integer roots. A celebrated theorem of Davis, Matiyasevich, Putnam and Robinson shows that this is not the case. Their result shows that the class of Diophantine sets coincides with the a priori larger class of r.e. (or $\Sigma_1$)  sets.

We proved this result under the assumption that exponentiation is Diophantine. This is the key result, and will be dealt with in the following lecture.

## 116b- Homework 8

March 5, 2008

Homework 8

Due Tuesday March 11 at the beginning of lecture.

Important update: In problem 4.(a), recall that $U^1$ is a universal $\Sigma_1$ predicate for unary formulas, so if $x$ is the Gödel number of a $\Sigma_1$ formula $\psi(v)$ in one free variable $v$, then $U^1_x(y)$ holds iff $\psi(y)$ holds. Hence, asking that $U^1_x$ is finite is the same as asking that $\{n:\mathbb{N}\models \psi(n)\}$ is finite.  Actually, this is a serious typo: $\{x:U^1_x \mbox{\ is finite}\}$ is $\Sigma_{\bf 2}$-complete. The set $\{x \colon U^1_x \mbox{\ is cofinite}\}$ is $\Sigma_3$-complete.

Sorry about this. Either ignore 4.(a), or try to show (for extra credit) that the set is $\Sigma_2$-complete, or (for a much more challenging problem) that the corresponding set with “cofinite” is $\Sigma_3$-complete.

## 116b- Lecture 17

March 4, 2008

We proved the Rice, Shapiro, McNaughton theorem characterizing $\Sigma_1$ index sets.

We also showed that there incomparable Turing degrees below ${\bf 0}'$.

## 116b- Lecture 16

March 4, 2008

(Covered by Todor Tsankov)

We defined the analog $K_X$ of the halting problem for any oracle $X$ and showed that any set r.e. in $X$ is many-to-one reducible to $K_X$ (in particular, it is recursive in $K_X$). Hence, $K_X$ is a complete $\Sigma_1(X)$ set and no such set is recursive in $X$.

We proved the $S$ $m$ $n$ (or index function) theorem and Kleene’s recursion (or fixed point) theorem. Finally, we introduced the notion of an index set and proved Rice’s theorem that the only recursive index sets are ${\mathbb N}$ and $\emptyset$.

## 116b- Lecture 15

March 4, 2008

We proved that the class of functions computable by means of Turing machines coincides with the class of recursive functions. Together with the characterization of the recursive functions as those admitting $\Sigma_1$ graphs, one can see this result as empirical evidence for Church’s thesis, the claim that the intuitive notion of “algorithmically computable” is correctly formalized in the notion of recursive. An immediate consequence of this result is the existence of universal Turing machines.

We defined machines with oracles and stated the corresponding result: Given an oracle $X\subseteq\mathbb{N}$, a function $f: \mathrm{dom}(f) \subseteq \mathbb{N}^k\to\mathbb{N}$ is computable by a Turing machine with oracle $X$ iff $f$ is recursive in $X$ (meaning that it is built up from $\chi_X$ and the basic functions by composition, recursion and minimalization) iff $f$ has a graph $\Sigma_1$ definable in the structure $(\mathbb{N},+,\times,0,1,<,X)$. We then defined the partial order $A\le_T B$ among subsets of $\mathbb{N}$ which holds iff $\chi_A$ is recursive in $B$.