Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.7: Gödel Numbering

( \newcommand{\kernel}{\mathrm{null}\,}\)

We now change our focus from looking at functions and relations on the natural numbers, where it makes sense to talk about representable sets, to functions mapping strings of LNT-symbols to N. We will establish our coding system for formulas, associating to each LNT formula ϕ its Gödel number, ϕ. We will make great use of the coding function that we defined in Definition 4.5.3.

Definition 5.7.1.

The function , with domain the collection of finite strings of LNT-symbols and codomain N, is defined as follows:

s={1,αifsis(¬α),whereαis anLNT-formula3,α,βifsis(αβ),whereαandβareLNT-formulas5,vi,αifsis(vi)(α),whereαis anLNT-formula7,t1,t2ifsis=t1t2,wheret1andt2are terms9ifsis011,tifsisSt,withta term13,t1,t2ifsis+t1t2,wheret1andt2are terms15,t1,t2ifsist1t2,wheret1andt2are terms17,t1,t2ifsisEt1t2,wheret1andt2are terms19,t1,t2ifsis<t1t2,wheret1andt2are terms2iifsis the variablevi3otherwise.

Notice that each symbol is associated with its symbol number, as set out in Table 5.1.

Example 5.7.2:

Just for practice, let's find 0. Just from the chart above, 0=9=210=1024. To look at another example, look at 0=0. Working recursively,

=00=7,0,0=7,1024,1024=283102551025

Exercise 3 asks you to investigate some of the subtleties of coding as it relates to this last example.

Example 5.7.3:

This is a neat function, but the numbers involved get really big, really fast. Suppose that we work out the Gödel number for the formula ϕ, where ϕ is (¬=0S0).

Since ϕ is a denial, the definition tells us that

ϕis1,=0S0=223=0S0+1.

So we need to find =0S0, and by the "equals" clause in the definition,

=0S0is7,0,S0=2830+15S0+1.

But 0=210=1024, and S0=21230+1=21231025. Now we're getting somewhere. Plugging things back in, we get

=0S0is28310255[21231025+1]

so the Gödel number for (¬=0S0) is

ϕis223(28310255[21231025+1]+1).

Chaff: To get an idea about how large this number is, consider the fact that the exponent on the 5 is S0=21231025+1, which is

4588239037329654294933009459423640636113835 33711852348723982661700090725110495540711416 24496800232720851201851240219667428400380468 28472630247645228844759293716788206726298594 57606066116964029586110650008838161967674248 714876110453564150536269711030213614452805279 213722748800276796114884183810302573694405480 301945785627339339194850085383681785222504546 327111992210992776215014423059901287305704225 3643605726211189929819826835540873386794064170 563975508362231081323849454313910276632860438529,

approximately 10490.

Now, let us play a bit with the Gödel number of ϕ:

ϕ=223(28310255[21231025+1]+1)>35[10490],

so if we take common logarithms, we see that

log(ϕ)>5[10490]log3

and taking logarithms again,

log(log(ϕ))>10490log5+log(log3)>10489.

Hmm... So this means that log(ϕ) is bigger than 10[10489]. But the common logarithm of a number is (approximately) the number of digits that it takes to express the number in base 10 notation, so we have shown that it takes more than 10[10489] digits to write out the Gödel number of ϕ. If you remember that a googol is 10100 and a googolplex is 1010100, ϕ is starting to look like a pretty big number, but it gets better!

To write out a string of 10[10489] characters (assuming a million characters per mile, or about 16 characters per inch) would require far more than 10[10488] miles, which is far more than 10[10487] light years.

Or, to look at it another way, if we assume that we can put about 132 lines of type of an 8.5- by 11-inch piece of paper, and since a ream of paper (500 sheets) is about 2 inches thick, that gives a tack of paper more than 10[10488] light years high. Since the age of the universe is currently estimated to be in the tens of billions of years (on the order of 1010 years), if we assume that the universe is both Euclidean and spherical, the volume of the universe is less than 1040 cubic light years, rather less than the 10[10488] cubic light years we would need to store our stack of paper. In short, we don't win any prizes for being incredibly efficient with the coding that we have chosen. What we do win is ease of analysis. The fact that we have chosen to code using a representable function will make our proofs to come much easier to comprehend.

Exercises

  1. Evaluate the Gödel number for each of the following:
    (a) (v3)(v3+0=v4)
    (b) SSSS0
  2. Find the formula or term that is coded by each of the following:
    (a) 283(2143(2183951025+1)5(21833351025+1)+1]5[218312951025+1]
    (b) 223(220310255(21231025+1)+1)
    (c) 26395(283959+1)
  3. Look at the number c=283102551025=7,0,0. Find the number e such that IthElement(e,2,c) is true. Suppose that d=3,1,4,5=24325576. Why is IthElement(4,1,d) false?

This page titled 5.7: Gödel Numbering is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Christopher Leary and Lars Kristiansen (OpenSUNY) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?