Is Gödel numbering a first or second order function?

[nomadreid]

Gödel-numbering (in its broadest meaning, not necessarily the one Gödel used): On one side, it would seem that an assignment of a symbol to a number is just a first order function, and the recursion set up to translate a formula into numbers would be first-order, but on the other hand the process is a function whose domain is the collection of all strings of symbols from the alphabet , which is a superset of the set of all formulas, and so that sounds second-order to me.

 

[HallsofIvy]

Gödel-numbering does NOT just "translate a formula into numbers". It translate any statement of collection of statements into a unique number.

 

[nomadreid]

HallsofIvy, thanks, but this is what I meant: this was a colloquial usage of the plural, mixing "gives a bijection from the set of allowed strings onto a subset of the set of natural numbers" and "maps a given string s to a natural number n_s such that if s is not identical to t, then n_s≠n_t". Now that we have corrected my English, perhaps someone could answer the meat of the question?

 

[gopher_p]

By "first order function", do mean "function definable in a first-order structure"?

 

[nomadreid]

gopher_p, thanks.

By "first order function", do mean "function definable in a first-order structure"?

Yes.

 

[gopher_p]

OK. Well the domain of a definable function has to be a definable set in some Cartesian power of the universe of the structure. So it's not technically proper to say that a function which accepts strings of symbols as input can be definable in the first-order structure of the natural numbers.

I don't have much experience with second-order logic, but I don't believe it would make any sense to talk about definability of such a function in a second-order structure or the natural numbers either.

You have to be really careful as a beginner studying model theory (especially if it's a self-guided tour) that you pay attention not only to what the author says but what they mean. For instance, if they say that a function whose domain is something other than a subset of ordered tuples of natural numbers is somehow definable in a first-order structure of the natural numbers, you know that's not what they really mean. They mean something else, and it's (unfortunately) your job to figure out what they do mean. It is virtually impossible to be 100% precise with some of this stuff without being over-verbose to the point of unreadability. So it's possible that the Gödel function(s) in the structure and in the "real world" are actually different things with different domains and such, but the author(s) treat them as being the same because there is a reasonable way to consider them as doing the same thing.

 

[nomadreid]

Thanks, gopher_p.

Well the domain of a definable function has to be a definable set in some Cartesian power of the universe of the structure. So it's not technically proper to say that a function which accepts strings of symbols as input can be definable in the first-order structure of the natural numbers.

I am not sure I follow that: Since Gödel numbering is a function with input of strings from the theory (not from the universe of the model of that theory containing the strings), then the resulting Gödel-numbering function could conceivably have a structure of the natural numbers for its model. For example, since (if the strings are finite) a collection of ordered pairs, with one member the string, and the other member a symbol corresponding to a natural number, would still end up countable, one tends to look to the natural numbers for a universe. (Even if the number of formulas appeared uncountably infinite, you could still usually invoke the Löwenheim-Skolem downward theorem.) However, Gödel numbering, when viewed as a function, could not itself be a string of that theory, and would have to be part of another theory (and its corresponding sentence or sentence schema satisfied by another model) and so I am still inclined to think that this construction would require (and would be able to be defined via) a second-order structure. But I am open to suggestions.

By the way, it was never said that the universe of the structure of a first-order structure had to be that of the natural numbers. You can have your universe of one model be an infinite number of elements which, in another context, might be the symbols of an alphabet for a theory of another model. (Perhaps indexed by a subset of the ordinals to fit a convenient Cartesian product form.)

if they say that a function whose domain is something other than a subset of ordered tuples of natural numbers is somehow definable in a first-order structure of the natural numbers, you know that's not what they really mean.

Yes, a good warning to distinguish between model and theory is Skolem's paradox. By the "real world" I presume you mean <V, \in>

It's late in my part of the world, so I hope I am making sense. :zzz: To be continued?

 

[gopher_p]

As with definable sets in the other thread, the notion of a definable function is given a fairly precise meaning in model theory. Basically a function $f$ is definable in a structure $\mathcal{M}$ iff the graph of $f$ is definable (as a set) in $\mathcal{M}$. By definition, the domain (and codomain, for that matter) of a definable function has to be a (definable) subset of some Cartesian power of the universe of our structure.

It seems that maybe your question is whether a Gödel-numbering of $\mathcal{L}$-formulas can be definable in some first-order structure (not necessarily that of the natural numbers), where $\mathcal{L}$ is some "standard" language in which the theory of the natural numbers might be expressed. If that's the case, then I'm pretty sure (though not 100%) that could be accomplished trivially. I don't know if it would be at all interesting or if it would lead to any additional understanding (if any is to be had) of the given Gödel-numbering.

Sorry if I was confused by your original question. I interpreted it as indicating that you had seen a presentation of a proof of the Incompleteness Theorem and were maybe a bit dubious with regards to the use of a Gödel-numbering in a structure on $\mathbb{N}$.

 

[nomadreid]

Many thanks for the reply, gopher_p

It seems that maybe your question is whether a Gödel-numbering of L-formulas can be definable in some first-order structure (not necessarily that of the natural numbers), where L is some "standard" language in which the theory of the natural numbers might be expressed.

Correct.

If that's the case, then I'm pretty sure (though not 100%) that could be accomplished trivially.

Indeed, on the face of it, it would seem that this is just reducible to a function on sequences of natural numbers, and hence easily expressible in a first-order language. What I am worried about is whether another way of looking at it cannot come up with the same conclusion; if not, what is wrong with that other point of view (or maybe the "simply" in "simply reducible" is hand-waving a step that would wreak havoc). That is: if we consider the Gödel-numbering F is a function with the domain being all well-formed strings expressible in L, the string expressing this Gödel-numbering could not be expressed only in L. Hence we would need to extend L to another language L' to express F. I am wondering whether the extension would not require symbols which would be interpreted as second-order (or higher) quantifiers.
Put another way: to express F, we would need to quantify over all admissible strings in L; this would include the necessity to quantify over all formulas and sentences. This is the hallmark of a second order theory.

I don't know if it would be at all interesting...

If both of these approaches are correct, then this would just be an example of a second-order theory that is reducible to a first-order one. In that case, it would be (for me) of interest to figure out what this reduction procedure consists of.