Ytukyg

I was reading these notes and found the definition of computable set of L-sentences (page 101 paper pdf):

$$ ulcorner Sigma urcorner = { ulcorner sigmaurcorner : sigma in Sigma }$$

where $ulcorner varphiurcorner$ is the Godel number of $varphi$. The notes say:

call $Sigma$ computable if $ulcorner Sigma urcorner$ is computable.

However, they have only defined what computable means for the Godel numbers of symbols (and not for sets) so I don't know what this means. We can take the definition of computable that given an input the output is a returned in finite time. Note that at this point we have NOT defined recursively enumerable in the notes (nor computably generated which are synonyms), so I am not confusing them (yet) since I'm not suppose to know about them at this point in the text.

What confuses me is that I know how to compute the Godel number of symbols, L-terms, L-formulas but not of a set. So what exactly is the Godel number of a set of L-sentences?

I recently asked a very related question and noticed I had no chance in understanding it without this clarification:

What is the difference between computably generated and computable?

An important convention that, unfortunately, often goes un-stated is that when an operation that ordinarily only applies to objects of a certain sort is applied to a set of objects of that sort, the result is the set obtained by applying that operation to the elements of that set. For example, multiplication by $2$ is an operation usually applied only to numbers. $mathbb{Z}$ is the set of all integers, so in particular is not a number but a set of numbers. The expression $2mathbb{Z}$, therefore, doesn't really make sense - we don't know what it means to multiply a set by a number. Instead, what we mean by "$2mathbb{Z}$" is ${2x mid x in mathbb{Z}}$ - in this case, the set of all even integers.

Likewise, you're right that the Godel-numbering operation typically applies only to sentences. $Sigma$ is a set of sentences; therefore, $ulcornerSigmaurcorner$ refers to the set ${ulcornervarphiurcornermidvarphiinSigma}$. In other words, $ulcornerSigmaurcorner$ is the set of Godel numbers of sentences in $Sigma$.

Now, you say you know what it means for a Godel number to be computable. If that's the case, either you're misunderstanding something or you're mis-stating something - a single Godel number is always computable, because it's just an integer. Any integer can be computed (by a program which just outputs that number). What you almost certainly mean is that you know what it means for a set of Godel numbers to be computable - that is, there is an algorithm which, given a Godel number, will determine whether or not that number is in the set. If I'm correct in thinking that, then this notion of "computable" is specifically for things like $ulcornerSigmaurcorner$ (sets of Godel numbers).

If we have a set of Godel numbers for their L-sentences then we have:

$$ ulcorner Sigma urcorner = { ulcorner sigma urcorner : sigma in Sigma }$$

what the notes define is that $Sigma $ is computable (i.e. we can determine if a specific L-sentence is a member of that set in finite time) if its corresponding "Godel number set" $ulcorner Sigma urcorner$ is computable (i.e. can we determine if a specific natural number corresponds to Godel number that corresponds to a sentence). Thats the meaning.

Basically to check membership for $Sigma$ for a specific L-sentence $sigma$ we compute its Godel number $a = ulcorner sigma urcorner $. Then if we assume $ulcorner Sigma urcorner$ is computable (i.e. membership can be queried in finite time) then we just do:

$$ a in ulcorner Sigma urcorner $$

which will return a boolean True or False value in finite time if $ulcorner Sigma urcorner$ is computable. The key here being that the characteristic function is computable.

To emphasize, computable means that the characteristic function is computable so in finite time we can know if $a in R$ or $a not in R$. So we can get both positive and negative information about the membership of $a$ wrt to $R$.

This important detail is important because of computably enumerable/generable sets. Those are the sets that ONLY positive information can be extracted.

Thanks to the comments in the question!