[FOM] Recursive invariance

[Vaughan Pratt]

On 7/11/2010 10:41 PM, Michael Carroll wrote:
> Hartley Rogers gives a key role to recursive invariance in his 1967 text
> "Theory of Recursive Functions and Effective Computability." He devotes
> Chapter 4 to it, after his introductory chapters and before plunging into
> details. He also remarks intriguingly that "Our fixed choice of Gödel
> numbering ... appears to be a rather noninvariant feature of our theory" (p.
> 22 in my copy).

You're getting the chronology out of order.  The word "appears" is 
crucial here.  The immediately following sentence on p. 22 promises "We 
shall see however (Chapter 4 and Exercise 2-10), that our results 
possess an invariant significance independent of this choice."  The word 
"however" is crucial here: you need to pattern match on 
"appears...however".  But you probably intuited that anyway.

> Some later texts such as Soare's 1987 "Recursively Enumerable Sets and
> Degrees" follow Rogers in his definition of recursive invariance. But it
> does not seem to be mentioned in either of Smullyan's books, neither his
> 1992 "Gödel's Incompleteness Theorems" nor his 1993 "Recursion Theory for
> Metamathematics."
>
> I'm having trouble fixing whether Rogers' recursive invariance is generally
> regarded as an important and well-accepted concept in recursive function
> theory, and was hoping FOM subscribers might enlighten me.

I took two courses in recursion theory from Manuel Blum in 1969/70 when 
I was a Ph.D. student at Berkeley.  The very first thing he talked about 
in his first course was acceptable Goedel numberings, which is at the 
heart of recursive invariance.  (But then you'll notice Manuel's name in 
connection with Corollary III(b) of Chapter 4 of Rogers.)

I have no idea why Smullyan did not draw attention to it.  I will admit 
however that when I taught recursion theory at Stanford I never paid 
attention to recursive invariance.  It's a valid concern, but I have to 
say that I was relieved when Manuel moved on from acceptable Goedel 
numberings to what seemed to me at the time more important matters.  I 
was quite willing back then to forgive every unacceptable Goedel 
numbering, being very open-minded in my naivete about every kind of 
mathematical object.  I later saw the wisdom of keeping the unacceptable 
ones on a shorter leash, but I'm not sure I would want to trouble my 
students with that distinction early on.

So I think my answer to your question about the importance of recursive 
invariance is about the same as for that of vector spaces.  Linear 
algebra is all about the category of vector spaces over an arbitrary 
field and their linear transformations, one of the world's most 
important families of categories, but I'd prefer to start the students 
off with matrices over the reals.

Vaughan