What does it mean for a set of L-sentences $\Sigma$ to be computable?

Question

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

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

where $\ulcorner \varphi\urcorner$ 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?

Answer 1

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 $2\mathbb{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 "$2\mathbb{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, $\ulcorner\Sigma\urcorner$ refers to the set $\{\ulcorner\varphi\urcorner\mid\varphi\in\Sigma\}$. In other words, $\ulcorner\Sigma\urcorner$ 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 $\ulcorner\Sigma\urcorner$ (sets of Godel numbers).

Answer 2

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!