MENTAL
 Main Menu
 Applications
 Mathematics
 The True Meaning of Gödel-s Theorem

The True Meaning of Gödel's Theorem
 THE TRUE MEANING
OF GÖDEL'S THEOREM

"The Ego Cogito of the 20th century" (Manuel Garrido).

"The leitmotiv of the 20th century" (Palle Yourgrau).

"A milestone in the history of logic and mathematics" (Ernest Nagel & James R. Newman).

"The most important mathematical article of the 20th century" (Toby Ord).


Gödel's Theorem

Kurt Gödel's paper "On formally undecidable propositions of the Principia Mathematica and related systems" (from 1931) is considered the most famous ever published paper on mathematical logic. Gödel's paper proves the incompleteness (or undecidability) theorem, which states the following: From this theorem derives another, called the "second incompleteness theorem": Paradoxically, Gödel proved this metamathematical theorem (which reveals the limitations of mathematics) by means of mathematics itself, namely by means of arithmetic. And this theorem also expresses something paradoxical: it proves something that can never be proved.


A simple example illustrating Gödel's incompleteness theorem

To get an idea of the nature of Gödel's theorem, let us illustrate it with a simple example. Suppose our PBS consists of: The derivation process is as follows: Therefore, the undecidable (inaccessible) numbers are: 1, 2, 4, 6, 6, 7, 9, 10, 12, 15, 17, 20, etc.

This example is intended to illustrate only that with axioms and rules of inference one can create "gaps" that correspond to inaccessible expressions.


General lines of the proof of Gödel's theorem

The proof of Gödel's theorem is very long and quite complex. The complete and detailed proof can be found in the book by Nagel & Newman [1994]. It is based primarily on arithmetic, as in the previous example. The key ideas of the proof are the following: A simple way to prove Gódel's theorem is the following [Guzmán, 1995]: The second incompleteness theorem is proved analogously to the first one, using in this case the sentence "I am not consistent".


The paradoxical sentence G

From the logical point of view, the sentence G is paradoxical, that is, it is both true and false, provided that truth and demonstrability are equivalent concepts. Indeed: From the conceptual-intuitive point of view, we know (without recourse to logic) that G is true. And yet, from the point of view of a PAS it is undecidable.

Gödel showed that arithmetic is essentially incomplete, for even if new axioms (such as G) were admitted, another true and formally undecidable sentence could be constructed. In fact, there are infinitely many true sentences that are undecidable. Since arithmetic is incomplete, every FAS based on it is also incomplete.

This theorem does not exclude, as Gödel already indicated in his article, the possibility of proving the consistency of a PBS (including the arithmetic of natural numbers) by means of a higher order system. This is precisely what Gerhard Gentzen did a few years later, in 1936.


Gödel and Platonism

Gödel reflected deeply on the philosophical consequences of his incompleteness theorems. He concluded that his theorems proved that mathematical Platonism was the correct position in the philosophy of mathematics.

This Platonic philosophy of Gódel was made known in a Gibbs Lecture given on December 26, 1951, at the annual meeting of the AMS (American Mathematical Society). He corrected the text of this lecture with the intention of having it published, but did not succeed in giving it a form satisfactory to him. It was finally published in 1994, as part of a volume entitled "Kurt Gödel: Unpublished Essays" [1994].


Other Undecidable Subjects

The fifth postulate of Euclid's geometry

This postulate, which can be expressed as "Through a point exterior to a straight line passes only one line parallel to it", is undecidable from the other four axioms. Whether we add the fifth postulate or its negation, we obtain a consistent system. With its negation we obtain the non-Euclidean geometries. If we establish that there are no parallel lines, we have elliptic geometry (whose simplest model is spherical geometry). And if we admit several parallel lines, we have hyperbolic geometry.


The axiom of choice of set theory

This axiom states that "in any collection of disjoint sets, another set can be constructed consisting of a single element from each of the sets in the collection. "This axiom is obvious for finite sets, but is intended for infinite sets. In 1940, Gentzen and Gödel proved that the axiomatic set theory ZF (Zermelo-Fraenkel) is consistent, with or without the axiom of choice. Therefore, the axiom of choice is undecidable. The ZF axiomatic with the axiom of choice is called ZFC (the "C" is for "Choice").


The continuum hypothesis

The continuum has a close relationship with infinity. For example, on every segment of the real line there are at least as many points as Cantor's transfinite ℵ1, which is 2^ℵ0, a cardinal greater than the cardinality of the natural numbers (ℵ0). The continuum hypothesis states that the cardinality c of the continuum is ℵ1. Well, Gödel proved in 1940 that the continuum hypothesis was independent of the ZF axioms of set theory, Therefore, it is undecidable.


The equivalence of expressions in the lambda calculus

The lambda calculus is a formal system aimed at unifying the world of functions, in its definition and application aspects. Church [1936] proved that there is no computable function that can decide whether two expressions of the lambda calculus are equivalent or not. The equivalence of lambda expressions is not decidable. Historically, it was the first undecidability problem that could be proved.


The problem of stopping a Turing machine

Alan Turing, in his famous 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem", proved that the halting problem of a Turing machine is undecidable, in the sense that there is no general algorithm (or Turing machine) −or meta-algorithm− that determines whether another algorithm (or Turing machine) will come to a halt, after a finite number of steps, with the obtaining of a result, or will continue indefinitely. This is equivalent to saying that it is not possible to know what is computable and what is not.


The problem of algorithmic compression

According to Gregory Chaitin, given an algorithm that produces a certain output or result, there is undecidability with respect to the possible existence of another, more compressed (i.e., shorter length) algorithm that produces the same output.

In his work "The Unknowable", Chaitin [1999] calls the shortest program that produces a given output "elegant". I show that it is impossible to prove that a program is elegant. This is Chaitin's theorem, which is proved by reductio ad absurdum: Other versions of Chaitin's theorem are:
  1. It is impossible to know whether a program is the shortest possible program to perform a given task.

  2. It is impossible to prove that a sufficiently long sequence is random. [A random sequence is one that does not have a compact representation and it is necessary to specify it extensively, i.e., by specifying all its elements].
The following table reflects the analogies between the views of Gödel, Church, Turing and Chaitin:

ElementDecidibility
GödelSentenceT o F
ChurchLambda expressionEquivalence
TuringProgramHalting
ChaitinExpressionMaximum compression


The decision problem (Entscheidungsproblem)

The decision problem is the tenth problem posed by Hilbert, among the 23 he posed at the International Congress of Mathematicians in 1900, in Paris. Its statement is as follows: That is, Hilbert posed the possible existence of an algorithm with input a diophantine equation and which would return "Yes" if the equation had a solution or "No" if it did not. The problem was not solved until 70 years later, and in the negative sense: in 1970 Yuri Matiyasevich proved that such an algorithm does not exist. In 1928, at the International Congress of Mathematicians in Bologna, Hilbert posed another similar decision problem. It consisted in trying to discover a general method for determining whether or not an expression of Boolean formal logic is universally true (a tautology). This problem was later generalized as: Is there a general algorithm capable of answering, in a finite number of steps, whether a proposition of first-order predicate logic is true or false? Before this question was answered, no formal definition of algorithm existed at the time it was posed. This was done by: Subsequently, Turing himself showed that both models of computation were equivalent: the concepts of lambda-definable function and algorithm computable by means of a Turing machine coincide. The Church-Turing thesis states that the only thing that is computable is that which is realized by means of lambda functions or by means of Turing machines. The decision problem was generalized to the very roots of mathematics by Hilbert himself, also in 1928 at the same International Congress of Mathematicians in Bologna, when he posed three key questions:
  1. Is mathematics complete? That is, can every mathematical statement be proved?

  2. Is mathematics consistent?. That is, is it impossible to prove for every mathematical proposition its truth and falsity?

  3. Is mathematics decidable?. That is, is there an algorithm to determine whether a mathematical `proposition is true or false.
Hilbert's aim was to create a universal, complete and consistent formal axiomatic system from which all mathematical truths could be derived. And also to make it decidable, that is, to find an algorithm that would determine the truth or falsity of any proposition in such a formal system.

With Gödel's theorem, the first two questions posed by Hilbert were answered in the negative. It is impossible to construct such a universal system: any consistent first order system containing the arithmetic of the natural numbers is not complete because there are undecidable propositions. Nor can the system prove its own consistency.

The answer to the third question came in the mid-1930s, when Alonzo Church and Alan Turing both published papers, independently, showing that problems similar to Gödel's existed in the area of computation: the problem of equivalence of lambda expressions and the halting problem, respectively. Since the Turing and Church systems are equivalent, this result is known as the "Church-Turing theorem" (not to be confused with the Church-Turing thesis).


MENTAL vs. Gödel's Theorem

Gödel, with his famous incompleteness theorem, brought two issues to light:
  1. The limitations of formal axiomatic systems.
  2. The existence of a deep abyss between truth and demonstrability, since there are many true propositions that are indemonstrable.
These conclusions shook the foundations of mathematics, just as Heisenberg's indeterminacy (or uncertainty) principle did a few years earlier (in 1927) in quantum physics. The arithmetic of the natural numbers, the rock on which the edifice of mathematics rests, is axiomatically incomplete.

The impact of Gödel's theorem transcends the mere mathematical field to affect other fields such as computer science, artificial intelligence, linguistics, psychology, physics and even philosophy. There is still discussion today about Gödel's results in the sense of what it may mean about the limitations of the human mind to know or discern, as well as the limitations of languages.

The problem posed by Gödel's theorem is clarified in the light of the principle of downward causality. Actually, the leitmotiv of Gödel's theorem is the dialectic between two ways of contemplating reality: between the rational, the formal and the superficial, versus the semantic, the intuitive and the profound. There are mathematicians who admit that they have not fully understood the argument of the theorem. And it has not been understood because this dialectic between these two modes of consciousness has not been considered.
The irrational numbers and Gödel's theorem

Gödel's theorem is associated with the limits of the deducible and also, with the limits of the computable, the operative, in short with the expressible. In this sense, we can establish an analogy with the real numbers. The axioms in this case are the digits 0 to 9, the rules of inference are the arithmetic operations, and the theorems are the rational numbers.

The real numbers are divided into two groups:
  1. The rational ones, which are those expressible by means of the arithmetic of the natural numbers. They belong to the conscious, superficial and expressible world.

  2. The irrationals, which are neither expressible nor computable by means of arithmetic in a finite number of steps. They belong to the unconscious, deep and inexpressible world. We can consider them as "imaginary numbers", because we can only imagine them.
However, some irrationals are expressible at the descriptive level by a finite expression, although they represent infinite computational steps. Among these are transcendental numbers such as π, e, Φ, √2, etc. These transcendent numbers act as mathematical archetypes, as bridges between the conscious (expressible) world and the unconscious (inexpressible) world. For example, the square root of 2 can be expressed as √2 = 1 + 1/(1 + √2), which is a recursive expression and gives rise to the continued fraction


If we consider as axioms (operative) addition and division, we need infinite steps to compute it, then it is inaccessible in a finite number of steps. However, it is accessible at the descriptive level. In MENTAL, the expression is:

( r2 =: (1 + 1.÷(1+r2)) )


The self-referential statement G as a fractal expression

The Gödel Incompleteness (or Undecidability) Theorem is based on the use of the self-referential sentence G "I am not provable" (or "I am undemonstrable") as the key piece of its proof. It is an archetypal sentence, for it unites opposites: the linguistic and the metalinguistic or the mathematical and the metamathematical. It is a sentence that symbolizes consciousness. The theorem proves that it is not possible to prove either the truth or the falsity of G (it is undecidable) by means of the axioms and the rules of inference of a formal axiomatic system that includes the natural numbers, such as that of Principia Mathematica by Russell and Whithead. In other words, that G is not accessible by means of the axioms and rules of inference of such a formal axiomatic system.

The essence of the problem is the separation between the superficial and the deep, between form and substance. For G is a profound sentence, because it is self-referential (it refers to itself) and, it is evoking consciousness through the union of opposites.

But this problem is solved by using the archetypes of MENTAL. Indeed, the sentence G is accessible through the semantic primitives and is describing a fractal expression:

(S =: S/I) represents the fractal expression ((((S/I)/I)I)...

where I is the predicate "I am undemonstrable".


Conclusions In short, Gödel's theorem is not applicable in MENTAL because there are no undecidable expressions. There are only (operational and descriptive) expressions constructible with the primitives. This eliminates an enormous conceptual stumbling block, since Gödel proved that the formal alone is insufficient. That semantics is also necessary.


Addenda

Gödel's theorem and Heisenberg's indeterminacy principle

In 1927, Heisenberg discovered that the more precisely the position of a quantum particle is determined, the less precisely its momentum (or velocity) is known at that instant, and vice versa. Four years later, in 1931, Gödel proved that a formal axiomatic system that includes arithmetic is incomplete. Both results express a kind of impossibility or the inherent limitations on what is possible for us to know. Therefore, it is natural to ask whether there is a relationship between them. This question has been repeatedly addressed over time. The main interest lies in the possible incompleteness of physics. The question can be posed as follows: does quantum uncertainty imply incompleteness? This topic is covered extensively in Douglas Hofstadter's book "Gödel, Escher, Bach" and has been discussed in hundreds of articles since the 1930s.

Today we can answer this question in generic terms, i.e. they do have a connection: from the superficial we have limitations to access the deep. Moreover, the deep is inherently diffuse, inaccessible and imprecise.

On this subject there is a curious episode. John Wheeler, the Princeton physicist, also wondered whether the uncertainty principle might have some deep connection with Gödel's incompleteness theorem. Wheeler recounts: "One day, I was at the Institute for Advanced Study, and I went to Gödel's office, and there he was. It was winter, and Gödel had an electric heater and his legs wrapped in a blanket. I said, 'Professor Gödel, what connection do you see between your incompleteness theorem and Heisenberg's uncertainty principle?' And Gödel got angry and threw me out of the office."


Bibliography