Due Tuesday February 5 at the beginning of lecture.
116b- Homework 3January 29, 2008
116- Lecture 7January 29, 2008
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.
116b- Lecture 6January 24, 2008
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.
116b- Homework 2January 22, 2008
Due Tuesday January 29 at the beginning of lecture.
Update: There is a typo in problem 2, it must be .
116b- Lecture 5January 22, 2008
We showed that a function is in iff it has a -graph. It follows that a set is r.e. iff it is -definable.
116b- Lecture 4January 18, 2008
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.
116b- Homework 1January 15, 2008
Due Tuesday January 22 at the beginning of lecture.
116b- Lecture 3January 15, 2008
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.
116b- Lecture 2January 15, 2008
We defined the class of Primitive Recursive functions and showed several examples of functions that belong to this class.
116b- Lecture 1January 15, 2008
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).