But one might also wish to study the Gödel phenomenon, itself, in the newly erected, general framework. The "Gödel phenomenon" may be expressed by saying that every attempt to effectively enumerate the truths of arithmetic is bound to fail. Fix a Godel numbering of formulas in the language of arithmetic. Let A denote the set of all Gödel numbers of truths of arithmetic. Then:
"n, A ¹ W[n].So for each proposed recursive enumeration W[n] of A, either some falsehood is included (unsoundness) or some truth is missed (incompleteness). Equivalently, for each enumeration W[n], if W[n] doesn't include a falsehood, then W[n] misses a truth.
"n, W[n] Í A Þ $x. A(x) Ù ØW[n](x).But the situation is more interesting than that. Gödel's construction allows one to effectively produce the missing truth from a sound enumeration. In other words, the existence claim is uniform:
$total recursive f. "n, W[n] ÍA Þ A(f(x)) Ù ØW[n](f(x)).This situation is computationally stronger than the non-uniform version, which states only that A is not recursively enumerable. What more, beyond non r.e.-ness does it imply? This encourages us to formulate the Gödel phenomenon as a general, recursion theoretic property of sets:
S is productiveÛ$total recursive f. "n, W[n] ÍS Þ S(f(x)) Ù ØW[n](f(x)).Then f is called the productive function for S.
Everybody who hears about Gödel has thought of the following idea. Each r.e.approximation to a productive set misses something. What if we keep adding the new things to what we started with?
Proposition 1: Each productive set has an infinite r.e. subset.
Proof: There is a total recursive f such that for each x, y,
W[f(x, y)] = W[x] È {y}.Exercise 1: Prove it.
Let g be the productive function of S.
Let W[a] = Æ.
Now do what everybody wants to:
h(0) = a;We know that rng(d) is infinite because W[h(n)] Í S (by induction on n), so ØW[h(n)](g(n)).
h(n + 1) = f(h(n), g(h(n))
d(n) = g(s(n)).
Now we may ask: is productivity (a.k.a. the Gödel phenomenon) just the same as non-r.e.-ness or is it something more? Our first clue is that ØK, our favorite example of a non-r.e. set, is productive.
Proposition 2: ØK is productive.
Proof: The identity function p1,1 serves
as a productive function.
For suppose that W[n] Í ØK.
We need to show that ØK(n)
Ù
ØW[n](n).
Suppose, for reductio, that W[n](n).
Then K(n), by the definition of K.
But this contradicts W[n] Í
ØK.
So ØW[n](n).
Now suppose, for reducto, that K(n).
Then W[n](n),
by the definition of K.
But this again contradicts W[n] Í
ØK.
So ØK(n).
-|
Roger Penrose turned this argument into a second career by claiming it proves that humans are not machines. It can't be producing the missing elements of ØK that makes us superior, since that is a matter of computing the identity function! It can't be that we see that the the produced object belongs to ØK, for arbitrary n, since that depends on seeing first that W[n] Í ØK, and it isn't likely we can "see" that. If we could, then cracking the Pentagon's web pages would be a cake walk in comparison. I think the linchpin of the argument is his cryptic discussion that complex systems n for which we couldn't "see" W[n] Í ØK wouldn't count as systems of mathematics (which must be simple and intersubjective), so the range of n for which we must decide the question is radically restricted.
The next result is that productivity is closed upward in the many-one reducibility ordering
Proposition 3: S is productive Ù S £mQ Þ Q is productive.
Proof: Let g be the productive function and let
f
witness the reduction relation.
We need to construct from these a total recursive productive function
h
for Q.
This function must have the property:
"n, W[n] Í Q Þ Q(h(x)) Ù ØW[n](h(x)).Here's an idea for how to proceed. First we construct a total recursive d that computes the index of the inverse image of an r.e. set under the reduction function f:
"n, W[d(n)] = f -1(W[n]).This can be done as follows. Define partial recursive
y(x, y) »mz U(x, d(z, 0), d(z, 1), <f(y)>).Applying s-m-n, we obtain total recursive d such that
f[d(x)](y) »y(x, y).Thus:
W[d(x)](y) Û y(x, y)¯Û mz U(x, d(z, 0), d(z, 1), <f(y)>)¯ Û (f -1(W[n]))(y).We now propose that h(x) = f(g(d(x)) is a productive function for Q.
Corollary 4:
All co-r.e.-hard problems are productive.
All index sets that are not experimentally verifiable are productive.
Proof: The first follows from the fact that is co-.r.e.
complete. The second follows from the Rice-Shapiro theorem.
-|
So we know that everything from ØK upward is productive. What about sets below ØK? Clearly, the recursive ones cannot be productive because productivity implies non-r.e. But even if there were non-recursive co-r.e. sets below ØK, they couldn't be productive.
Before we can show this, we require a strenghened version of the recursion theorem.
Proposition 5 (The strenghened recursion thoerem):
"total recursive f $total
recursive g. f[f(g(x),
x)]
= f[g(x)].
Proof: Let total recursive f be given. Using the universal and s-m-n theorems, construct total recursive s such that
f[s(x, y)](z) » f[f(f[x](x), y)](z).By s-m-n again we obtain total recursive m such that:
f[m(y)](x) » s(x, y).So
f[f[m(y)](x)](z) » f[f(f[x](x), y)](z)Now substitute m(y) for x.
f[f[m(y)](m(y))](z) » f[f(f[m(y)](m(y)), y)](z).Now define g(y) = f[m(y)](m(y)) = s(m(y), m(y)). This is total recursive since s, m are.
f[g(y)](z) » f[f(g(y), y)](z).-|
Now we may show the following characterization of productivity. According to this result, productivity is equivalent to non-r.e.-ness just in case there are no incomplete r.e. degrees. The proof get the Deviousness Award for the day.
Proposition 6 (Myhill's theorem): A is producive Û ØAis r.e.-hard.
Proof: By corollary 4, co-r.e. hardness implies productivity. But by proposition 9.1, ØAis r.e.-hard just in case A is co-r.e. hard.
Conversely, suppose A is productive
with producive function g.
Let arbitrary r.e. set W[n]
be given.
Using the universal construction
and s-m-n, obtain total recursive s such that:
f[s(x, y)](z) » o(mw g(x) = z Ù U(n, d(z, 0), d(z, 1), <y>)).Thus
W[s(x, y)] = {g(x)} if W[n](y) andApplying the strengthened recursion theorem we obtain a total recursive h such that
W[s(x, y)] = Æ otherwise.
W[h(y)] = W[s(h(y), y)].Now I claim that the composition C(g, h)(x) = g(h(x)) witnesses W[n] £m ØA.
Now suppose that ØW[n](y).
Then W[h(y)]
= W[s(h(y),
y)]
=
Æ
Í ØA.
So since g is the productive
function of ØA,
A(g(h(y))).
-|
But maybe we can turn the issue around. Maybe we can use what we have learned to find out whether there are incomplete co-r.e. (and hence incomplete r.e.) degrees. Since such degrees would not reduce ØK, that would be something new! Turning matters around, we now know that every complete r.e. set has a productive complement. Productive complements all contain infinite r.e. sets. So how about trying to construct an r.e. S set whose complement ØS contains no infinite r.e. set? That's not quite enough, because the complement ØS might be finite, and all co-finite sets are recursive (use a finite lookup table for the complement). But it is enough if we also require that the complement ØS is infinite.
S is simple Û
Proposition 7:
So if they exist, simple sets witness the difference between the Gödel phenomenon and mere non-r.e.-ness. More fundamentally, they represent a new way to prove non-verifiability, since they can't reduce ØK. This idea is due to Emil Post.
Proposition (Post's Theorem): There exists a simple set.
Proof: Using the universal construction, define
f[a](x) »f[x](mz (f[x](z) > 2x)).We know that ranges of partial recursie functions are r.e., so
1. E[a] is r.e.Next, let S be an infinite r.e. set.
2. ØE[a] contains no infinite r.e. set.Finally, for each such x, f[a](x) > 2x.
3. ØE[a] is infinite.-|
Now we know that every complete r.e. set has a productive complement,
which implies that the complement is is infinite.
Exercise 3: Which of the examples prior to proposition 8.3 are productive? Prove your answer, including positive and negative claims.
Exercise 4: (Rogers exercise 7-25) Show that
A productive Ù B r.e. ÙBÍ AÞ A - B productive.