[FOM] Axiomatic Syntax

Richard Heck heck at fas.harvard.edu
Mon Sep 1 16:08:00 EDT 2003

Thanks, Harvey, for this post, which clarified several matters a good 
deal for me.

A couple remarks on this exchange.

>There is a form of the self reference lemma that makes the self referential
>nature of this business as clear as I have ever seen it made in print. I saw
>this first in Jerosolow.
>SELF REFERENCE LEMMA. Let phi(x) be a formula of PA with only the free
>variable x. There exists a closed term t such that the godel number of the
>sentence phi(t) IS the correct value of t.
Meaning, of course, that the following is provable in PA: t = *phi(t)*, 
where the latter is the numeral for the goedel number of phi(t).

>It is compelling to say that: The sentence phi(t) asserts that the property phi holds of the sentence itself.
How compelling it is to say this will depend a little bit upon one's 
purposes. I'll say a further word about this matter shortly.

>This Lemma works for PA formulated with primitive recursive function symbols. 
It is worth emphasizing this point: The lemma mentioned works /only/ for 
a version of PA that has some additional function symbols for primitive 
recursive functions. You certainly don't need to have function symbols 
for all primitive recursive functions (all infinitely many of them), but 
only as much as is required for the relevant facts about diagonalization 
to be meaningful and provable. The discussion in Boolos's /The Logic of 
Provability/, which works with what he calls 'pseudo-terms', can be 
adapted to this end, by exchanging the pseudo-terms for real ones. (The 
treatment there is extremely clear and extremely careful, and is highly 
recommended. It's great for a "second look" at diagonalization.)

For present purposes, assume (what I think is true) that the term t in 
the lemma mentioned is "diag(phi(x))",where "diag(x)" is a function 
symbol for the primitive recursive function that numeralwise represents 
diagonalization (with respect to the coding in question, of course). So 
we will have:
    PA |- diag(*phi(x)*) = *phi(diag(*phi(x)*))*,
where again the *...* means: the numeral for the goedel number of ....

That said, the term in question /describes/ the sentence in question 
rather than actually /naming/ it: The contrast, to borrow an example 
from Russell, is that between "the author of /Waverly/" and "Sir Walter 
Scott". According to Russell, "the author of /Waverly/ is Scottish" does 
not really refer to Sir Walter Scott. Rather, it says that there is 
someone, namely, the one and only one person who wrote /Waverly/, who is 
Scottish. That person happens to be Sir Walter Scott, but that fact is 
no part of what the sentence /says/. One wonder whether the author of 
/Waverly/ was Scottish even if one knew that Sir Walter Scott was.

So similarly, one might well want also to say that phi(diag(*phi(x)*)) 
does not /refer/ to itself at all. It does not really say of itself that 
it has phi. Rather, it says that there is an object, namely, the one and 
only one sentence that diagonalizes phi(x), that has phi. That object 
happens to be the very sentence phi(diag(*phi(x)*)), but that fact is no 
part of what that sentence /says/. Formally, we may think of the numeral 
for its goedel number as a sentence's /name/. So, from this point of 
view, only a sentence of the form phi(n), for n a numeral, could really 
say of itself that it had phi.

There is a disanalogy between the two cases. Since diag is primitive 
recursive, one can effectively determine both what the value of the 
function is and whether a given numeral (sentence) is its value. How 
much one might make of that disanalogy is another question.

One might think this sort of contrast is of interest only to 
philosophers, but there is reason to suppose that it runs rather deeper 
than that. I once heard Kripke suggest, rightly, as it seems to me, that 
it lies at the foundations of recursion theory. To illustrate, the 
contrast at which Russell was gesturing comes out a little bit when one 
asks such questions as "Do you know who the author of /Waverly/ is?" 
It's obvious that it's not sufficient to answer, "Why yes, the author of 
/Waverly/" or even (in most cases) "Why yes, the author of /Ivanhoe/". 
For one could still ask, "And who is the author of /Ivanhoe/?" The 
answer "Sir Walter Scott" is, in most cases, a "buckstopper", in a way 
"the author of...." is not. Similarly, recursion theory operates with a 
very particular conception of what counts as /the answer/ to a 
computational question. If we ask "What is 234x567?" it is obviously 
insufficient to answer "Why, 567x234". The "buckstopper" in such a case 
is "132,678".

Exactly what this contrast comes to is another matter, one investigated 
in epistemic logic under the title "The Exportation Problem".

By the way, for those who do not know the history behind Russell's 
famous example (as I did not until recently), /Waverly/ was originally 
published anonymously, in 1814, when Scott was 41 and by which time he 
was already an establihed poet. (Scott was offered but declined the Poet 
Laureateship in 1813.) Scott's later novels, such as /Ivanhoe/ (1819), 
were typically attributed to "the Author of /Waverly/" or "the Author of 
/Waverly/ and /Guy Mannering/" or what have you. He sometimes used 
playful pennames, as well. The reasons Scott preferred anonymity 
apparently remain a matter of speculation. He only admitted authorship 
in 1827, the year after he had become insolvent and forced into a form 
of bankruptcy. (In part to repay his debts, Scott was then about to 
arrange for the publication of his so-called "Magnum Opus", a collection 
of his works.) But he was by then widely suspected to have authored 

For more on Scott, see http://www.walterscott.lib.ed.ac.uk/.

Richard Heck

More information about the FOM mailing list