Thursday 19 November 2020

Gödel’s First Incompleteness Theorem in Simple Symbols and Simple Terms


 


The following piece explains a particular symbolic expression (or version) of Kurt Gödel’s first incompleteness theorem. It also includes a particular expression (or example) of a Gödel sentence (i.e., “This statement is false” — this link takes you to a humorous entry!). In terms of the actual symbols used, this representation of the theorem expresses a (slight) philosophical and logical bias. So it’s worth noting that almost every symbolisation of the theorem is unique — if sometimes only in tiny detail. (In logic and mathematical logic there’s the common phenomenon of various symbolic “dialects” competing with — or simply complementing — each other.) And this representation and explanation exclude all the other details which surround the bare theorem itself. Indeed this symbolic representation alone doesn’t prove or demonstrate anything. And even when the symbols are defined or interpreted, that’s still the case. In addition, it’s worth distinguishing the truth (and lack of proof ) of a Gödel sentence from any proof of the first incompleteness theorem itself — even if the two can’t be entirely disentangled!

Thus the following words don’t attempt to tackle the arguments and extra details which are required to establish the theorem. And neither do they extrapolate anything from it. However, even this basic approach is bound to leave out much detail. And that’s simply because this is a short introduction to a particular symbolisation of Gödel’s first incompleteness theorem.


Three things need to be noted to begin with:

  1. The first incompleteness theorem is essentially about systems and the truth-values of certain statements within those systems. (Alternatively, the first incompleteness theorem is about a particular system and a Gödel sentence within that particular system.)
  2. Those systems and statements are arithmetical and therefore use natural numbers. (In other words, the first incompleteness theorem is not applied across the board — as it often is.)
  3. Within those systems there are some true statements about natural numbers which cannot be proved within those systems. (Alternatively, within a given system there will be a true statement about natural numbers that cannot be proved within that system.)

To get to the core of Kurt Gödel’s first incompleteness theorem, let’s sum it up in its bare logical (or symbolic) form. This particular symbolism (just one among many) will hopefully capture what’s at the heart of the theorem.

Take the following symbolic representation from the logician and philosopher Professor Alasdair Urquhart (as found in his paper ‘Metatheory’):

G ↔ ¬Prov(G⌝)

The following is a list of definitions of the symbols in the biconditional theorem above:

G = a Gödel sentence
= if and only if (i.e., the biconditional symbol)
¬ = negation (or “not”)
Prov = provable
¬Prov = not provable
G = The “code number” of the Gödel sentence G. (The superscripted Quine corners are — basically — quotation marks.)

Thus G ¬Prov (⌜G⌝ ) means:

The sentence “This sentence is false” is true if and only if it is not provable in system T (i.e., the system to which it belongs).

Or:

Gödel sentence G is true if and only if there is no proof of G in system T (i.e., the system to which it belongs).

So why is the symbol G put in brackets after the if and only if (i.e., ↔) sign and the sign (i.e., ¬) for negation? Why do we have the symbol ⌜ G rather than plain G? This is because the brackets (i.e., ⌜ and ⌝) symbolise self-reference or “quotation”. That is, firstly we have the symbol G, and then when we refer to G we get ⌜G ⌝.

Thus ⌜ G⌝ is a “code number”.

A code number is a number which is used to identify something. This means that ⌜ G⌝ is the code number of the Gödel sentence G (i.e., the symbol G without brackets). Furthermore, a Gödel number is a specific kind of code number. In mathematical logic, Gödel numbers are natural numbers which are assigned to statements (as well as to the individual symbols within those statements ) within a given system or formal language.

In terms of the biconditional symbol (i.e., ↔).

This symbolises that both sides of the equality sign (i.e., =) are logically equivalent in that both are either jointly true or jointly false. Note: this doesn’t also mean that they have the same meaning.

This is one expression of the aforesaid biconditional:

i) G 
is true
if and only if 
ii) ¬Prov(⌜
G⌝) 
is true.

Alternatively, the inversion (i.e., since the theorem includes a biconditional):

i) ¬Prov(⌜ G⌝)
is true
if and only if
ii)
G
is true.

The Gödel sentence G (in this instance, “This statement is false”) is self-referential. That is, it refers to itself (or G refers to G). The archetype of this Gödel sentence is the Liar paradox; which is also self-referential. Indeed self-reference is at the heart of the whole show! Without self-reference we wouldn’t have a Gödel sentence or the problems and insights which arise from it. (See my ‘Why Empty Logic Leads to the Liar Paradox’.)

In addition, Gödel sentence G is true if and only if there is no proof of G. Ordinarily it’s taken that a mathematical statement P is taken to be true if and only if there is a proof of P. Gödel’s first incompleteness theorem is saying the literal opposite of that.

What’s also important here is to note the Gödel sentence’s position in a system (or theory). None of this makes any sense outside the context of the system (or theory) to which Gödel sentence G belongs. In other words, taking G entirely on its own makes no sense at all.

No comments:

Post a Comment