(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.