9
$\begingroup$

I have wondered for a while what gave rise to the notation $0^\sharp$. According to wikipedia this is due to Solovay in 1967, but (perhaps unsurprisingly) there's no discussion of why that notation was chosen. In contrast, Silver mentions in a paper that he chose the symbol $\Sigma$ to represent the same thing. Nonetheless, I couldn't turn anything up with a bit of searching.

So, why did Solovay choose zero-sharp as the name for this object? (The zero part at least makes sense in the general sense of $a^\sharp$ where we consider $L[a]$ instead of $L$) Especially given that there are plenty of ways of indicating something "a little bit more/different" that are quite normal in mathematical notation.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

I've heard that the symbol was originally $O^\#$, with a capital letter O, not zero. This set was viewed as a higher-level analog of Kleene's O (a universal $\Pi^1_1$ set).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Yes, that's what I've always heard. Of course, you were probably the one to tell me this, Andreas. ;) $\endgroup$
    – Todd Eisworth
    Commented Oct 19, 2011 at 14:48
  • 2
    $\begingroup$ I've also heard that it was in analogy to 0' from recursion theory. $\endgroup$
    – Todd Eisworth
    Commented Oct 19, 2011 at 14:57
  • $\begingroup$ My only concrete guess was a relation to zero-jump. Interestingly the jump operator seems to be in part due to Kleene as well. In any case, Solovay's paper does seem to say $O^\#$ (with a hash/pound, rather than a musical sharp, but that could be a limitation of the typesetting...) so that seems the most plausible answer. $\endgroup$
    – Chris Le Sueur
    Commented Oct 19, 2011 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .