[FOM] Lucas, Penrose, and the Church-Kleene ordinal

[Timothy Y. Chow]

Lucas, Penrose, and others have argued that there is something inherently 
non-recursive about human thought.  For some reactions to Penrose's 
arguments as put forward in his book "Shadows of the Mind," see

  http://psyche.csse.monash.edu.au/psyche-index-v2.html

Here I want to propose the thesis that the key concept underlying the
arguments of Penrose (and others; I use Penrose's name synecdochically)
is the Church-Kleene ordinal w_1^CK.  I make this claim even though I
do not recall seeing w_1^CK mentioned explicitly by Penrose.

Before explaining my thesis, I want to clarify that it is not my intention
to defend Penrose's claim that human thought is non-recursive.  In fact,
I side with the majority in regarding Goedel's theorem per se as providing 
no decisive evidence one way or the other on that question (although I 
will not try to argue that here).  What I hope to do is to shed some light
on what Penrose's argument *is*, since I personally have found it to be
quite hard to grasp what he is trying to say.  My approach is not to do a
close reading of Penrose's writings, but to present a version of the 
argument that I think captures its essence.

Now let me present my reading of the argument.  Let Q denote Robinson's 
arithmetic (or any other suitable weak fragment of arithmetic).  We wish
to analyze the "set of first-order arithmetic truths that are unassailably
known by human mathematicians"; call this set S.  This description of S
is vague, so let us try to introduce precision by stating some precise
properties of S, motivated by the informal concept.  For example:

- S is a set of first-order sentences in the language of arithmetic.
- S contains Q.
- S is consistent.

Call any set having these three properties a CFA (for "consistent fragment
of arithmetic").  Now, Goedel tells us that if T is any *recursive* CFA,
then there is a first-order sentence Con(T) of arithmetic that is not
provable from T.  (It's not critical here that we specifically use Con(T),
i.e., "T is consistent," but it's convenient.)  We now introduce a
critical assumption about S, which I will label "RP" (for "Roger Penrose,"
but I note with some amusement that R and P are also the initial letters 
of "Reflection Principle").

- RP: If T is a subset of S and T is a recursive CFA, then Con(T) is in S.

RP seems to me to be what Penrose is driving at with his terminology of
"knowably sound" and "unassailably true" and so forth.  Indeed, I am sure
that many working mathematicians share the underlying intuition: If I 
write down explicitly a list of statements of arithmetic and you know
for certain that they are true, then surely you also know for certain
that the list of statements is consistent.  Similarly, once people come
to accept ZFC, they almost imperceptibly come to accept Con(ZFC) as well.

But now we're almost done, because we immediately deduce:

- S is not recursively axiomatizable, i.e., there is no recursive CFA
  T contained in S such that every element of S is provable from T.

We could, and many do, stop here, since this is the conclusion that
Penrose is after.  However, I think that it is helpful to take one small
step further, and to ask for an example of S.  Otherwise, it's not quite
clear whether Penrose's argument is a pure argument from contradiction,
or whether it actually yields candidates for "the set of unassailably
known truths."

Here's where w_1^CK comes in.  Unless I'm confused (and if I am, please
enlighten me), we get "minimal" examples of S by starting with Q and
iteratively adjoining stronger and stronger consistency statements,
until we're forced to stop when we finally get a *non-recursive* CFA
and therefore can't apply Goedel's theorem any more.  Let me call an S
that is obtained in such a way a "CK set" (is there a standard term?).

In other words, I would say that Penrose's argument is best described
not as trying to use Goedel's theorem to show that human thought is 
non-recursive, but as a philosophical argument that RP is true and
hence that "humanly known mathematical truths" are best modeled as
CK sets.

This concludes my main point, but let me add a footnote that I think
that what I have said sheds light on the anti-Lucas argument that
Douglas Hofstadter gives in "Goedel, Escher, Bach: An Eternal Golden
Braid."  Hofstadter argues that as we ascend the "Goedelization chain"
of stronger and stronger theories, we will eventually reach a point
where the system is so complicated that we can't figure out how to
"Goedelize" it any more, and then we'll stall.  But this seems to be
a wrong-headed move to me; what Hofstadter *should* say is that we'll
eventually reach a point where Goedel's theorem *can't* be applied
because the recursivity condition is violated, not that we'll reach
a point where "Goedelization" is still possible but we can't figure
out how to do it.

Tim