Editing Gödel's incompleteness theorems (section)

=== Arithmetization of syntax ===

The main problem in fleshing out the proof described above is that it seems at first that to construct a statement {{mvar|p}} that is equivalent to "{{mvar|p}} cannot be proved", {{mvar|p}} would somehow have to contain a reference to {{mvar|p}}, which could easily give rise to an infinite regress. Gödel's technique is to show that statements can be matched with numbers (often called the arithmetization of [[syntax]]) in such a way that ''"proving a statement"'' can be replaced with ''"testing whether a number has a given property"''. This allows a self-referential formula to be constructed in a way that avoids any infinite regress of definitions. The same technique was later used by [[Alan Turing]] in his work on the ''[[Entscheidungsproblem]]''.

In simple terms, a method can be devised so that every formula or statement that can be formulated in the system gets a unique number, called its [[Gödel number]], in such a way that it is possible to mechanically convert back and forth between formulas and Gödel numbers.  The numbers involved might be very long indeed (in terms of number of digits), but this is not a barrier; all that matters is that such numbers can be constructed. A simple example is how English can be stored as a [[Character encoding|sequence of numbers for each letter]] and then combined into a single larger number:
:* The word '''<code>hello</code>''' is encoded as 104-101-108-108-111 in [[ASCII]], which can be converted into the number 104101108108111.
:* The logical statement '''<code>x=y => y=x</code>''' is encoded as 120-061-121-032-061-062-032-121-061-120 in [[ASCII]], which can be converted into the number 120061121032061062032121061120.

In principle, proving a statement true or false can be shown to be equivalent to proving that the number matching the statement does or does not have a given property. Because the formal system is strong enough to support reasoning about ''numbers in general'', it can support reasoning about ''numbers that represent formulae and statements'' as well. Crucially, because the system can support reasoning about ''properties of numbers'', the results are equivalent to reasoning about ''provability of their equivalent statements''.