0
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ A subset of $\mathbb N$ is computable if its characteristic function is recursive. (i.e. there is an effective procedure for deciding if a number is an element or not). This is a special case of a computable relation (arity 1). $\endgroup$ – spaceisdarkgreen Dec 1 '18 at 3:16
  • 1
    $\begingroup$ Also, I'm not sure what you mean by 'computable symbols'... that doesn't make sense as far as I know. They've presumably defined computable functions and computable relations. They've defined the Godel number of a sentence / formula (probably based on a notion of a Godel number for a symbol), and $\ulcorner \Sigma \urcorner$ is the set of Godel numbers of the sentences in $\Sigma$, so a subset of $\mathbb N,$ and thus it makes sense to ask if it's computable in the above sense. $\endgroup$ – spaceisdarkgreen Dec 1 '18 at 3:33
  • $\begingroup$ Do you understand what a computable set of natural numbers is? (Note that $\ulcorner \Sigma\urcorner$ is just a set of natural numbers - namely, the set of Godel numbers of things in $\Sigma$ - so that's all that's going on here.) $\endgroup$ – Noah Schweber Dec 1 '18 at 4:53
  • $\begingroup$ @spaceisdarkgreen so are you saying to treat $\ulcorner \Sigma \urcorner $ as a characteristic function? I think I do understand what the characteristic function being computable is (just that in finite time we know if an element if part of the relation set or not). So what he means is that $\chi_{\ulcorner \Sigma \urcorner }(\sigma)$ is computable? i.e. given an L-sentence we can decide in finite time if its Godel number is in the set or not? $\endgroup$ – Charlie Parker Dec 1 '18 at 16:10
  • $\begingroup$ @spaceisdarkgreen sorry I was a bit informal with the "computable symbols", for computable symbols I meant that their Godel numbers are computable. $\endgroup$ – Charlie Parker Dec 1 '18 at 16:11
4
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Note that the OP's text does state explicitly that $\ulcorner\Sigma\urcorner=\{\ulcorner\varphi\urcorner:\varphi\in\Sigma\}$. $\endgroup$ – Noah Schweber Dec 1 '18 at 17:11
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.