116b- Homework 6

Homework 6

Due Tuesday February 26 at the beginning of lecture.

116b- Lecture 13

We proved the Kanamori-McAloon result on regressive functions as a corollary of Ramsey’s theorem, and proved, using the method of indicators, that it cannot be proven in .

116b- Lecture 12

We sketched the method of indicators and the hierarchy of fast-growing functions as techniques to prove independence in . Then we proved Ramsey’s theorem. We will use the method of indicators to show the Kanamori-McAloon theorem that the version of Ramsey’s theorem for regressive functions is not provable in .

116b- Lecture 11

We presented the provability conditions and showed how a theory with a provability predicate satisfies the second incompleteness theorem. We showed several remarks about the incompleteness results, including Rosser’s proof of the first incompleteness theorem, and Löb’s  theorem on sentences asserting their own provability.

We closed with some examples of “mathematically meaningful” sentences independent of .

116b- Homework 5

Homework 5

Due Tuesday February 19 at the beginning of lecture.

116b- Lecture 10

We showed that proves the completeness theorem. We then proved the second incompleteness theorem using the result on completeness, the fact that if a model of thinks that it contains a model of then we can really see this latter model, and the diagonal lemma.

116b- Lecture 9

(Covered by Todor Tsankov)

We proved the -uniformization theorem. This allowed us to introduce the standard notation for the -th partial recursive function in variables (with respect to an enumeration induced by a -uniformization of a universal -ary relation), and proved that the halting problem is unsolvable and that there are partial recursive functions without (total) recursive extensions. A corollary of this (that separation of r.e. sets by recursive sets fails) is part of this week’s homework.

We then reviewed the axioms of and began to work towards proving that this theory is powerful enough to prove the basic theorems of logic.  Specifically, we showed that given a set coding a countable language, in one can prove that the set of formulas of the language exists, and the same holds for the sets of sentences or logical axioms. Using this, one can define a provability predicate that states of a set and a number that is a (not necessarily r.e.) set of sentences in the given language, and codes the Gödel number of a sentence provable from . Hence, in one can define the classes of consistent, closed under deduction, and complete theories.

116b- Lecture 8

(Covered by Clinton Conley.)

We proved the Gödel-Rosser incompleteness theorem, as a consequence of the diagonal lemma. This is a stronger version of the first incompleteness theorem than originally proved by Gödel, who needed to assume more than just consistency of the underlying theory . Several corollaries follow: is essentially undecidable, there are r.e. sets that are not recursive, and truth is undefinable, a result due to Tarski.

We closed with some observations about r.e. sets, to which we will return at some later point. Namely, there are universal -relations, which provides us with a new proof that there are r.e. sets that are not recursive. Then, we proved the enumeration theorem of Kleene.

116b- Homework 4

Homework 4

Due Tuesday February 12 at the beginning of lecture.

116b- Homework 3

Homework 3

Due Tuesday February 5 at the beginning of lecture.