Due Tuesday February 5 at the beginning of lecture.
We showed that recursive functions and recursive sets are -representable in . We also defined Gödel numberings and exhibited an example of one. This allowed us to define when a theory is recursive. Finally, we proved Gödel’s diagonal lemma.
We proved that a set is recursive iff it is -definable.
We showed some elementary properties of the theory , defined end-extensions, and verified that is -complete.
We also defined what it means for a function, or a set, to be represented in a theory.
Due Tuesday January 29 at the beginning of lecture.
Update: There is a typo in problem 2, it must be .
We showed that a function is in iff it has a -graph. It follows that a set is r.e. iff it is -definable.
We defined the notion of r.e. sets and proved Gödel’s lemma stating that there is a coding of finite sequences by numbers.
We defined Ackermann’s function and showed it is not primitive recursive. We showed that -formulas have a primitive recursive characteristic function, and defined the class of recursive functions.
We defined the class of Primitive Recursive functions and showed several examples of functions that belong to this class.
We introduced the course, stated the incompleteness theorems, defined (Robinson Arithmetic), (Peano or first-order Arithmetic), and (the subsystem of second-order Arithmetic given by the arithmetic comprehension axiom).