a set A is enumerable iff there is a total or partial function from the
positive integers to A that is one-to-one and onto.
two sets A and B are equinumerous iff there is a function from A to B that
is total, one-to-one, and onto. (We can also express this by saying there is a
correspondence between A and B.)
you should be able to give intuitive proofs that the following sets are
enumerable: the positive integers; all the integers; the positive rational
numbers; the set of all the ordered pairs of positive integers
Suppose A and B are enumerable sets. Show that their union is enumerable.
(An informal argument in terms of constructing lists is OK.)
Diagonalization (Nonenumerability)
be able to show that the real numbers between 0 and 1 are not enumerable
(by means of a diagonalization argument)
be able to show that the set of all sets of positive integers is not
enumerable (again, by using a diagonalization argument; the easiest way is
to make use of the idea of the characteristic function of a set)
Recursive Functions
know the basic functions: the zero function z, the successor function s,
and the identity (projection) functions id.
how many projection functions are there for an n-place function?
know the basic techniques for building other primitive recursive functions
out of the basic functions: composition and primitive recursion (If I give
you two functions, you should be able to say what the result of composing
them in a given order is. If I give you a primitive recursive definition of
a function, you should be able to say what the function does. for example,
consider this definition of a function h: h(x,0) = id(x) and h(x, y') =
s(h(x,y)). What function is h?)
know the difference between recursive and primitive recursive functions.
be able to explain the relation between primitive recursive functions and
BlooP
. . . and between recursive functions and FlooP
are there any primitive recursive functions that aren't total? why?
understand the function-building technique that allows us to get recursive
functions that aren't primitive recursive, namely minimization.
are all recursive functions total? if so, why? if not, give an example of
one that isn't.
if I give you a function, you should be able to tell me what the
minimization of that function is for a given set of arguments. (Example: let
f(x,y) be the addition function, i.e. f(x,y) = x + y. What is the value of
Mn[f](0)? What about Mn[f](5)?)
Church's Thesis: all computable functions are recursive.
Recursive Sets and Relations
a set is recursive iff its characteristic function is recursive.
relations also have characteristic functions. (The characteristic function
of a k-place relation is a function of k arguments.)
a relation is recursive iff its characteristic function is recursive.
Arithmetization
Gödel numbers
be able to say (roughly) why, given an appropriate Goedel numbering, there
are recursive functions on the natural numbers that correspond to things
like: the set of formulas of a language; the set of sentences; the
concatenation operation; the function that takes a sentence and produces its
negation; the function that takes two sentences and produces their
conjunction; etc.
recall that, given an appropriate Goedel numbering, the set of deductions
is a recursive set; the property of being a deduction of a sentence S from a
set of sentences Gamma is recursive; and so on.
Representability
any recursive function is definable in the language of arithmetic (perhaps
supplemented by a function symbol for exponentiation)
know what definability in L* means
know what minimal arithmetic is
you don't need to memorize all the Q axioms, but should know a few and
have a feel for what they're for
know what is meant by a theory
know what the theory Q is (namely a set of sentences that is closed
under logical implication, that is, a set of sentences such that every FO
consequence of elements of the set is also an element of the set)
be able to explain why it is important (for Goedel's purposes) that Q
is a weak theory
not only is every recursive function (as well as recursive sets and
relations) definable in L*, every recursive function is also representable
in Q. You should know what this means. (Very roughly, it means that
not only can you "translate" the recursive function into L*, but
you can also do so in such a way that whenever, for specific natural numbers
a and b, f(a) = b,
the "translation" into L* is provable from the axioms of minimal
arithmetic, and therefore is in the set Q.
Gödel's First Incompleteness Theorem
you should have a good informal understanding of what the theorem says
(namely, that for any set of axioms stronger than minimal arithmetic, there
is a sentence in the language of arithmetic that is true in the standard
interpretation but is not provable from the axioms)
you should be able to give a very informal description of the reasoning
that leads to the theorem (starting from the point that the Gödel sentence
G can be understood roughly as saying "The sentence with Gödel number
g is not provable," where it turns out that g is the GN of that very
sentence).