View source for Godel numbering

You do not have permission to edit this page, for the following reason:

This IP address range has been globally blocked.
This does not affect your ability to read Wikipedia pages.

Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

This block affects editing on all Wikimedia wikis.

The IP address or range 2A01:4F8:0:0:0:0:0:0/29 has been globally blocked by XXBlackburnXx for the following reason(s):

Open proxy/Webhost: See the help page if you are affected:

This block will expire on 13:19, 27 May 2030. Your current IP address is 2a01:4ff:1f0:6c9::1.

Even while globally blocked, you will usually still be able to edit pages on Meta-Wiki.

If you believe you were blocked by mistake, you can find additional information and instructions in the Stewards Block Wizard.

Other useful links: Global blocks * Help:I have been blocked

You can view and copy the source of this page:

{{Short description|Function in mathematical logic}}
{{For|numberings of the set of computable functions|Numbering (computability theory)}}
{{inline|date=April 2021}}{{moreref|date= May 2025}}

In [[mathematical logic]], a '''Godel numbering''' is a [[function (mathematics)|function]] that assigns to each symbol and [[well-formed formula]] of some [[formal language]] a unique [[natural number]], called its '''Godel number'''. [[Kurt Godel]] developed the concept for the proof of his [[Godel's incompleteness theorems|incompleteness theorems]].<ref name= formal>{{cite journal |last=Godel|first=Kurt|title=Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I |journal=[[Monatshefte fur Mathematik und Physik]]|volume=38|year=1931|pages=173-198 | language= de |doi= 10.1007/BF01700692|s2cid=197663120|url=http://www.w-k-essler .de/pdfs/goedel.pdf|access-date=2013-12-07|archive-url= https://web.archive.org/web/20180411113347/http://www.w-k-es sler.de/pdfs/goedel.pdf|archive-date=2018-04-11|url-status= dead}}</ref>{{rp|pages= 173-198}}

A Godel numbering can be interpreted as an [[Semantics encoding|encoding]] in which a number is assigned to each [[symbol]] of a [[mathematical notation]], after which a sequence of [[natural number]]s can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.

Since the publishing of Godel's paper in 1931, the term "Godel numbering" or "Godel code" has been used to refer to more general assignments of natural numbers to mathematical objects.

== Simplified overview ==
Godel noted that each statement within a system can be represented by a natural number (its ''Godel number''). The significance of this was that properties of a statement--such as its truth or falsehood--would be equivalent to determining whether its Godel number had certain properties. The numbers involved might be very large indeed, but this is not a barrier; all that matters is that such numbers can be constructed.

In simple terms, Godel devised a method by which every formula or statement that can be formulated in the system gets a unique number, in such a way that formulas and Godel numbers can be mechanically converted back and forth. There are many ways to do this. A simple example is the way in which English is stored as a sequence of numbers in computers using [[ASCII]]. Since ASCII codes are in the range 0 to 127, it is sufficient to pad them to 3 decimal digits and then to concatenate them:
* The word '''{{mono|1=foxy}}''' is represented by {{value|102111120121}}.
* The logical formula '''{{code|1=x=y => y=x}}''' is represented by {{value|120061121032061062032121061120}}.

== Godel's encoding ==
{| class=wikitable
|-
| COLSPAN=8 |
! COLSPAN=4 | number variables
! COLSPAN=3 | property variables
| ...
|-
! Symbol
| 0
| ''s''
| !
| 
| 
| (
| )
| ''x''<sub>1</sub>
| ''x''<sub>2</sub>
| ''x''<sub>3</sub>
| ...
| ''P''<sub>1</sub>
| ''P''<sub>2</sub>
| ''P''<sub>3</sub>
| ...
|-
! Number
| 1
| 3
| 5
| 7
| 9
| 11
| 13
| 17
| 19
| 23
| ...
| 289
| 361
| 529
| ...
|+Godel's original encoding<ref name= formal />{{rp|pages= 179}}{{efn-lr|Godel's notation<ref name= formal />{{rp|pages= 176}} has been adapted to modern notation.}}
|}
Godel used a system based on [[prime factorization]]. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.

To encode an entire formula, which is a sequence of symbols, Godel used the following system. Given a sequence <math>(x_1,x_2,x_3,...,x_n)</math> of positive integers, the Godel encoding of the sequence is the product of the first ''n'' primes raised to their corresponding values in the sequence:

:<math>\mathrm{enc}(x_1,x_2,x_3,\dots,x_n) = 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots p_n^{x_n}.</math>

According to the [[fundamental theorem of arithmetic]], any number (and, in particular, a number obtained in this way) can be uniquely factored into [[prime factor]]s, so it is possible to recover the original sequence from its Godel number (for any given number n of symbols to be encoded).

Godel specifically used this scheme at two levels: first, to encode sequences of symbols representing formulas, and second, to encode sequences of formulas representing proofs. This allowed him to show a correspondence between statements about natural numbers and statements about the provability of theorems about natural numbers, the proof's key observation ({{harvnb|Godel|1931}}).

There are more sophisticated (and more concise) ways to construct a [[Godel numbering for sequences]].

=== Example ===
In the specific Godel numbering used by Nagel and Newman, the Godel number for the symbol "0" is 6 and the Godel number for the symbol "=" is 5. Thus, in their system, the Godel number of the formula "0 = 0" is 2<sup>6</sup> x 3<sup>5</sup> x 5<sup>6</sup> = 243,000,000.

== Lack of uniqueness ==

Infinitely many different Godel numberings are possible. For example, supposing there are ''K'' basic symbols, an alternative Godel numbering could be constructed by invertibly mapping this set of symbols (through, say, an [[invertible function]] ''h'') to the set of digits of a [[Bijective numeration|bijective base-''K'' numeral system]]. A formula consisting of a string of ''n'' symbols <math> s_1 s_2 s_3 \dots s_n</math> would then be mapped to the number

:<math> h(s_1) \times K^{n-1} + h(s_2) \times K^{n-2} + \cdots + h(s_{n-1}) \times K^1 + h(s_n) \times K^0 .</math>

If K is chosen to be a power of 10, this scheme makes it fairly easy for a human to convert between a string of symbols and its Godel number, since the Godel number represented in base 10 is just the concatenation of the <math>n</math> decimal numbers <math>h(s_i)</math>.

For example, the numbering described [[Proof sketch for Godel's first incompleteness theorem#G.C3.B6del numbering|here]] has K=1000.{{efn-lr|name=fn1}}

== Application to formal arithmetic ==

===Recursion===
{{Main|Course-of-values recursion}}
One may use Godel numbering to show how functions defined by [[course-of-values recursion]] are in fact [[primitive recursive function]]s.

===Expressing statements and proofs by numbers===
{{Main|Proof sketch for Godel's first incompleteness theorem}}
Once a Godel numbering for a formal theory is established, each [[rule of inference|inference rule]] of the theory can be expressed as a function on the natural numbers. If ''f'' is the Godel mapping and ''r'' is an inference rule, then there should be some [[arithmetical function]] ''g<sub>r</sub>'' of natural numbers such that if formula ''C'' is derived from formulas ''A'' and ''B'' through an inference rule ''r'', i.e.
:<math> A, B \vdash_r C, </math>
then
:<math> g_r(f(A),f(B)) = f(C). </math>
This is true for the numbering Godel used, and for any other numbering where the encoded formula can be arithmetically recovered from its Godel number.

Thus, in a formal theory such as [[Peano arithmetic]] in which one can make statements about numbers and their arithmetical relationships to each other, one can use a Godel numbering to indirectly make statements about the theory itself. This technique allowed Godel to prove results about the consistency and completeness properties of [[formal system]]s.

== Generalizations ==

In [[computability theory]], the term "Godel numbering" is used in settings more general than the one described above. It can refer to:
#Any assignment of the elements of a [[formal language]] to natural numbers in such a way that the numbers can be manipulated by an [[algorithm]] to simulate manipulation of elements of the formal language.{{Citation needed|date=February 2020}}
#More generally, an assignment of elements from a countable mathematical object, such as a countable [[group (mathematics)|group]], to natural numbers to allow algorithmic manipulation of the mathematical object.{{Citation needed|date=February 2020}}

Also, the term Godel numbering is sometimes used when the assigned "numbers" are actually strings, which is necessary when considering models of computation such as [[Turing machine]]s that manipulate strings rather than numbers.{{Citation needed|date=February 2020}} 
<!--
There is a very different meaning of the term Godel numbering relating to 
[[numbering (computability theory)|numberings]] of the class of [[computable function]]s. COMMENTED OUT PER TALK -->

==Godel sets==
Godel sets are sometimes used in set theory to encode formulas, and are similar to Godel numbers, except that one uses sets rather than numbers to do the encoding. In simple cases when one uses a [[hereditarily finite set]] to encode formulas this is essentially equivalent to the use of Godel numbers, but somewhat easier to define because the tree structure of formulas can be modeled by the tree structure of sets. Godel sets can also be used to encode formulas in [[infinitary logic|infinitary languages]].

== See also ==
* [[Church encoding]]
* [[Description number]]
* [[Godel numbering for sequences]]
* [[Godel's incompleteness theorems]]
* [[Kolmogorov complexity#Chaitin.27s incompleteness theorem|Chaitin's incompleteness theorem]]

== Notes ==
{{notelist-lr|refs=
{{efn-lr|name=fn1|For another, perhaps-more-intuitive example, suppose you have three symbols to encode, and choose bijective base-10 for familiarity (so enumeration starts at 1, 10 is represented by a symbol e.g. ''A,'' and place-value carries at 11 rather than 10: decimal ''19'' will still be ''19,'' and so with ''21;'' but decimal ''20'' will be ''1A''). Using <math> h(s_n) = n</math> and the formula above:
{{pb}}
<math>(1 \times 10^{(3-1)} + 2 \times 10^{(3-2)} + 3 \times 10^{(3-3)}) = (1 \times 10^{2} + 2 \times 10^{1} + 3 \times 10^{0}) = (100 + 20 + 3)</math>{{efn-lr|name=fn2}}
{{pb}}
...we arrive at '''<math>123</math>''' as our numbering--a neat feature.}}
{{efn-lr|name=fn2|(or, in bijective base-10 form: <math>9A + 1A + 3</math>)}}}}

== References ==
{{Reflist}}

* {{cite book| title= Godel's Proof| first1=Ernest | last1= Nagel|authorlink1= Ernest Nagel | first2= James R. | last2= Newman|authorlink2= James R. Newman| year= 1959| publisher= }}

== Further reading ==
* {{cite book| title= [[Godel, Escher, Bach|Godel, Escher, Bach: an Eternal Golden Braid]]| first= Douglas | last= Hofstadter| authorlink= Douglas Hofstadter | publisher= Basic Books| year= 1979 | isbn= 978-0-465-02656-2}} Defines and uses an alternative Godel numbering.
*{{cite book| title= [[I Am a Strange Loop]]| first= Douglas | last= Hofstadter| year= 2007 | publisher= Basic Books |isbn= 978-0-465-03078-1}} Includes the history of Godel's numbering.
* {{cite journal| url= https://blog.theincredibleholk.org/TarpitGazer/jot-visualiza tion.pdf |title= Visualizing the Turing Tarpit| first1= Jason | last1= Hemann | first2= Eric |last2= Holk| date= June 15, 2013| journal= FARM '13: Proceedings of the First ACM SIGPLAN Workshop on Functional Art, Music, Modeling & Design| pages= 71-76| archiveurl= https://web.archive.org/web/20160927114325/https://blog.thei ncredibleholk.org/TarpitGazer/jot-visualization.pdf |archivedate= September 27, 2016| doi= 10.1145/2505341.2505348 |isbn= 978-1-4503-2386-4|access-date= }} Uses Godel numbering to encode programs.

{{Mathematical logic}}
{{Authority control}}

{{DEFAULTSORT:Godel numbering}}
[[Category:Mathematical logic]]
[[Category:Theory of computation]]
[[Category:Works by Kurt Godel|Numbering]]

Pages transcluded onto the current version of this page (help):

Template:Ambox (view source) (template editor protected)
Template:Authority control (view source) (template editor protected)
Template:Citation needed (view source) (fully protected)
Template:Cite book (view source) (fully protected)
Template:Cite journal (view source) (fully protected)
Template:Code (view source) (template editor protected)
Template:Delink (view source) (fully protected)
Template:Efn (view source) (template editor protected)
Template:Efn-lr (view source) (extended confirmed protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Fix (view source) (fully protected)
Template:Fix/category (view source) (fully protected)
Template:For (view source) (template editor protected)
Template:Harvard citation no brackets (view source) (template editor protected)
Template:Harvnb (view source) (template editor protected)
Template:Hlist/styles.css (view source) (fully protected)
Template:Ifsubst (view source) (template editor protected)
Template:Inline (view source) (template editor protected)
Template:Main (view source) (template editor protected)
Template:Main other (view source) (fully protected)
Template:Mathematical logic (view source) (semi protected)
Template:Mono (view source) (template editor protected)
Template:Mono/styles.css (view source) (template editor protected)
Template:More citations needed (view source) (template editor protected)
Template:Moreref (edit)
Template:Navbox (view source) (template editor protected)
Template:No footnotes (view source) (template editor protected)
Template:Notelist (view source) (template editor protected)
Template:Notelist-lr (view source) (extended confirmed protected)
Template:Pagetype (view source) (fully protected)
Template:Paragraph break (view source) (fully protected)
Template:Pb (view source) (fully protected)
Template:Portal-inline (view source) (template editor protected)
Template:R/superscript (view source) (template editor protected)
Template:R/where (view source) (template editor protected)
Template:Reference page (view source) (template editor protected)
Template:Reflist (view source) (fully protected)
Template:Reflist/styles.css (view source) (fully protected)
Template:Rp (view source) (template editor protected)
Template:SDcat (view source) (fully protected)
Template:Short description (view source) (fully protected)
Template:Short description/lowercasecheck (view source) (fully protected)
Template:Val (view source) (template editor protected)
Template:Value (view source) (semi protected)
Template:Yesno (view source) (fully protected)
Template:Yesno-no (view source) (template editor protected)
Module:Arguments (view source) (fully protected)
Module:Authority control (view source) (template editor protected)
Module:Authority control/config (view source) (template editor protected)
Module:Category handler (view source) (fully protected)
Module:Category handler/blacklist (view source) (fully protected)
Module:Category handler/config (view source) (fully protected)
Module:Category handler/data (view source) (fully protected)
Module:Category handler/shared (view source) (fully protected)
Module:Check for unknown parameters (view source) (fully protected)
Module:Citation/CS1 (view source) (fully protected)
Module:Citation/CS1/COinS (view source) (fully protected)
Module:Citation/CS1/Configuration (view source) (fully protected)
Module:Citation/CS1/Date validation (view source) (fully protected)
Module:Citation/CS1/Identifiers (view source) (fully protected)
Module:Citation/CS1/Utilities (view source) (fully protected)
Module:Citation/CS1/Whitelist (view source) (fully protected)
Module:Citation/CS1/styles.css (view source) (fully protected)
Module:Convert (view source) (template editor protected)
Module:Convert/data (view source) (template editor protected)
Module:Convert/text (view source) (template editor protected)
Module:DecodeEncode (view source) (template editor protected)
Module:Delink (view source) (fully protected)
Module:Disambiguation/templates (view source) (fully protected)
Module:EditAtWikidata (view source) (fully protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Footnotes (view source) (template editor protected)
Module:Footnotes/anchor id list (view source) (template editor protected)
Module:Footnotes/anchor id list/data (view source) (template editor protected)
Module:Footnotes/whitelist (view source) (template editor protected)
Module:For (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:Gapnum (view source) (template editor protected)
Module:GetParameters (view source) (fully protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (fully protected)
Module:Message box/ambox.css (view source) (fully protected)
Module:Message box/configuration (view source) (fully protected)
Module:Namespace detect/config (view source) (fully protected)
Module:Namespace detect/data (view source) (fully protected)
Module:Navbar (view source) (fully protected)
Module:Navbar/configuration (view source) (fully protected)
Module:Navbar/styles.css (view source) (fully protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Pagetype (view source) (fully protected)
Module:Pagetype/config (view source) (fully protected)
Module:Pagetype/disambiguation (view source) (fully protected)
Module:Pagetype/rfd (view source) (fully protected)
Module:Pagetype/setindex (view source) (fully protected)
Module:Pagetype/softredirect (view source) (fully protected)
Module:Plain text (view source) (template editor protected)
Module:Portal (view source) (fully protected)
Module:Portal-inline (view source) (template editor protected)
Module:Portal/images/m (view source) (template editor protected)
Module:SDcat (view source) (fully protected)
Module:String (view source) (fully protected)
Module:String2 (view source) (template editor protected)
Module:TableTools (view source) (fully protected)
Module:Unsubst (view source) (fully protected)
Module:Val (view source) (template editor protected)
Module:Wikitext Parsing (view source) (fully protected)
Module:Yesno (view source) (fully protected)

Return to Godel numbering.

Retrieved from "https://en.wikipedia.org/wiki/Godel_numbering"