[FOM] Recursive invariance

Michael Carroll mcarroll at pobox.com
Mon Jul 12 01:41:13 EDT 2010

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).

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 

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.

Michael Carroll

More information about the FOM mailing list