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

In summary, Gödel numbering is a process that assigns a unique number to any statement or collection of statements. It is often used to translate formulas into numbers, but its domain is actually a superset of all formulas. This has led to some debate about whether it can be considered a first-order function or if it requires a second-order structure. However, in model theory, the notion of a definable function allows for the possibility of a Gödel-numbering to be definable in a first-order structure.
  • #1
nomadreid
Gold Member
1,665
203
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.
 
Physics news on Phys.org
  • #2
Gödel-numbering does NOT just "translate a formula into numbers". It translate any statement of collection of statements into a unique number.
 
  • Like
Likes 1 person
  • #3
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 ns such that if s is not identical to t, then ns≠nt". Now that we have corrected my English, perhaps someone could answer the meat of the question?
 
  • #4
By "first order function", do mean "function definable in a first-order structure"?
 
  • Like
Likes 1 person
  • #5
gopher_p, thanks.
gopher_p said:
By "first order function", do mean "function definable in a first-order structure"?
Yes.
 
  • #6
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.
 
  • Like
Likes 1 person
  • #7
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, [itex]\in[/itex]>

It's late in my part of the world, so I hope I am making sense. :zzz: To be continued?
 
  • #8
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}##.
 
  • Like
Likes 1 person
  • #9
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.
 

1. What is Gödel numbering?

Gödel numbering is a method developed by mathematician Kurt Gödel to assign unique numerical values to symbols, formulas, and expressions in formal systems. This allows for the manipulation and analysis of formal systems using mathematical operations.

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

Gödel numbering is a second order function, as it operates on the symbols and expressions of a formal system rather than the elements of the system itself.

3. How does Gödel numbering work?

Gödel numbering assigns a unique prime number to each symbol, variable, and function in a formal system. These prime numbers are then multiplied together to create a unique numerical value for each expression in the system.

4. What is the significance of Gödel numbering?

Gödel numbering is significant because it provided a way to mathematically represent and analyze formal systems, such as mathematical logic and computer programs. It also played a crucial role in Gödel's incompleteness theorems, which proved the limitations of formal systems.

5. Are there any limitations to Gödel numbering?

While Gödel numbering is a powerful tool in formal systems, it does have its limitations. For example, it cannot be used in systems that contain infinitely many symbols or expressions, as there is no way to assign unique prime numbers to an infinite set.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
28
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top