[FOM] Axiomatic Syntax
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
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/.
More information about the FOM