FOM: Re: Inventional and Verificational Complexity

[Charles Silver]

Joe Shipman wrote:

>Detlefsen's distinction between "inventional" and "verificational"
>complexity is very reminiscent of the P-NP distinction.

       It's also reminiscent of Popper's well-known distinction between the
logic of discovery and the logic of verification.


>Godel's first incompleteness theorem required two
>brilliant new ideas (arithmetization of syntax plus diagonalization).


    I wouldn't have thought these two ideas were the central ones.
Besides, Godel wasn't the person who discovered diagonalization, and I think
arithmetization (in some general sense) had also been done earlier, though
not in his way for the purpose of getting a theory to express something
about itself.   In assessing the brilliance and novelty involved in  the
discovery of the first theorem, I think the semantic insights need to be
separated off from the syntactic proof.  There seem to be lots of insights
in both camps.  In the semantic camp, the insight that Truth ourtruns
Provability, and the use of the Liar Paradox (or at least, *some* paradox)
deserve mention.   When you get to the syntactic part, there seem to be lots
of things to say.  For one, it seems to me the fancy (and complicated) way
to transform a formula with one free variable, say P(x),  into a sentence,
say P(_n_), where n is the Godel number for that sentence itself should be
mentioned.  Then, there's the representability of recursive functions in N.
I think there are several other insights....

    I tend to think Godel Numbering is not in itself such a big deal, though
it's kind of fun.   Diagonalization seems more central.  But, a problem I
have is that I don't know exactly what the necessary ingredients are for a
diagonalization argument to be present.  I seem to recall (though I can't
think of examples at the moment) of proofs where one person could claim
diagonalization was used while someone else could argue that it wasn't.  I
guess all I'm saying is that there seem to be fuzzy cases.   Has anyone ever
given something like a definition of a diagonalization argument, so that a
decision could be arrived at in each case whether an argument used
diagonalization or not?

Charlie Silver