Godel's Proof

by Ernest Nagel

Gödel’s great stroke of genius—as readers of Nagel and Newman will see—was to realize that numbers are a universal medium for the embedding of patterns of any sort, and that for that reason, statements seemingly about numbers alone can in fact encode statements about other universes of discourse. In other words, Gödel saw beyond the surface level of number theory, realizing that numbers could represent any kind of structure.

come to think of it, that does make sense

because numbers are a universal medium for the embedding of patterns of any sort, computers can deal with arbitrary patterns, whether they are logical or illogical, consistent or inconsistent.

In short, when one steps back far enough from myriads of interrelated number patterns, one can make out patterns from other domains, just as the eye looking at a screen of pixels sees a familiar face and nary a 1 or 0.

Still, it is ironic that in a book devoted to celebrating Gödel’s insight that numbers engulf the world of patterns at large, the primary philosophical conclusion would be based on not heeding that insight, and would thereby fail to see that calculating machines can replicate patterns of any imaginable sort—even those of the creative human mind.

The axiomatic method consists in accepting without proof certain propositions as axioms or postulates (e.g., the axiom that through two points just one straight line can be drawn), and then deriving from the axioms all other propositions of the system as theorems. The axioms constitute the “foundations” of the system; the theorems are the “superstructure,” and are obtained from the axioms with the exclusive help of principles of logic.

He presented mathematicians with the astounding and melancholy conclusion that the axiomatic method has certain inherent limitations, which rule out the possibility that even the properties of the nonnegative integers can ever be fully axiomatized.

the Greeks had proposed three problems in elementary geometry: with compass and straight-edge to trisect any angle, to construct a cube with a volume twice the volume of a given cube, and to construct a square equal in area to that of a given circle. For more than 2,000 years unsuccessful attempts were made to solve these problems; at last, in the nineteenth century it was proved that the desired constructions are logically impossible.

Ancient Greek mathematicians were amazing. Imagine the kind of stuff they spoke when they got together without realizing they are at cusp of revolutionary advances.

another problem that the Greeks raised without answering. One of the axioms Euclid used in systematizing geometry has to do with parallels. The axiom he adopted is logically equivalent to (though not identical with) the assumption that through a point outside a given line only one parallel to the line can be drawn. For various reasons, this axiom did not appear “self-evident” to the ancients. They sought, therefore, to deduce it from the other Euclidean axioms, which they regarded as clearly self evident.1 Can such a proof of the parallel axiom be given? Generations of mathematicians struggled with this question, without avail.

I wish I could go back in time and listen to them discuss and argue over logic and proof.

It was not until the nineteenth century, chiefly through the work of Gauss, Bolyai, Lobachevsky, and Riemann, that the impossibility of deducing the parallel axiom from the others was demonstrated. This outcome was of the greatest intellectual importance. In the first place, it called attention in a most impressive way to the fact that a proof can be given of the impossibility of proving certain propositions within a given system.

Need to check out these proofs, hopefully there are beginner level resources to get a taste of it.

Gödel’s paper is a proof of the impossibility of formally demonstrating certain important propositions in number theory.

This is too meta for my taste

The traditional belief that the axioms of geometry (or, for that matter, the axioms of any discipline) can be established by their apparent self-evidence was thus radically undermined. Moreover, it gradually became clear that the proper business of pure mathematicians is to derive theorems from postulated assumptions, and that it is not their concern whether the axioms assumed are actually true.

Mathematics was thus recognized to be much more abstract and formal than had been traditionally supposed: more abstract, because mathematical statements can be construed in principle to be about anything whatsoever rather than about some inherently circumscribed set of objects or traits of objects; and more formal, because the validity of mathematical demonstrations is grounded in the structure of statements, rather than in the nature of a particular subject matter.

This may sound banal today but back then it wasn't so.

We repeat that the sole question confronting the pure mathematician (as distinct from the scientist who employs mathematics in investigating a special subject matter) is not whether the postulates assumed or the conclusions deduced from them are true, but whether the alleged conclusions are in fact the necessary logical consequences of the initial assumptions.

This is the point of Russell’s famous epigram: pure mathematics is the subject in which we do not know what we are talking about, or whether what we are saying is true.

However, the increased abstractness of mathematics raised a more serious problem. It turned on the question whether a given set of postulates serving as foundation of a system is internally consistent, so that no mutually contradictory theorems can be deduced from the postulates.

Since the Euclidean axioms were generally supposed to be true statements about space (or objects in space), no mathematician prior to the nineteenth century ever considered the question whether a pair of contradictory theorems might some day be deduced from the axioms.

In elliptic geometry, for example, Euclid’s parallel postulate is replaced by the assumption that through a given point outside a line no parallel to it can be drawn. Now consider the question: Is the elliptic set of postulates consistent? The postulates are apparently not true of the space of ordinary experience. How, then, is their consistency to be shown? How can one prove they will not lead to contradictory theorems? Obviously the question is not settled by the fact that the theorems already deduced do not contradict each other—for the possibility remains that the very next theorem to be deduced may upset the apple cart. But, until the question is settled, one cannot be certain that elliptic geometry is a true alternative to the Euclidean system, i.e., equally valid mathematically. The very possibility of non-Euclidean geometries was thus contingent on the resolution of this problem.

Well said.

The proof attempts to settle the consistency of elliptic geometry by appealing to the consistency of Euclidean geometry. What emerges, then, is only this: elliptic geometry is consistent if Euclidean geometry is consistent. The authority of Euclid is thus invoked to demonstrate the consistency of a system which challenges the exclusive validity of Euclid. The inescapable question is: Are the axioms of the Euclidean system itself consistent?

Lol so true. Consistency of elliptic geometry is proved by taking help of Euclid geometry. But then we had rejected the idea that Euclidian axioms are true hence consistent. We are back to square one.

Another answer is that the axioms jibe with our actual, though limited, experience of space and that we are justified in extrapolating from the small to the universal. But, although much inductive evidence can be adduced to support this claim, our best proof would be logically incomplete. For even if all the observed facts are in agreement with the axioms, the possibility is open that a hitherto unobserved fact may contradict them and so destroy their title to universality. Inductive considerations can show no more than that the axioms are plausible or probably true.

Imagine what would happen if we built a whole universe based on certain axioms which are taken at face value as true, and centuries later derive two contradicting theorems.

Russell’s antinomy can be stated as follows. Classes seem to be of two kinds: those which do not contain themselves as members, and those which do. A class will be called “normal” if, and only if, it does not contain itself as a member; otherwise it will be called “non-normal.”

Let ‘N’ by definition stand for the class of all normal classes. We ask whether N itself is a normal class. If N is normal, it is a member of itself (for by definition N contains all normal classes); but, in that case, N is non-normal, because by definition a class that contains itself as a member is non-normal. On the other hand, if N is non-normal, it is a member of itself (by definition of “non-normal”); but, in that case, N is normal, because by definition the members of N are normal classes. In short, N is normal if, and only if, N is non-normal. It follows that the statement ‘N is normal’ is both true and false. This fatal contradiction results from an uncritical use of the apparently pellucid notion of “class.”

Russell's Paradox. It blew my mind when I first heard about the barber story back in college days.

The limitations inherent in the use of models for establishing consistency, and the growing apprehension that the standard formulations of many mathematical systems might all harbor internal contradictions, led to new attacks upon the problem. An alternative to relative proofs of consistency was proposed by Hilbert. He sought to construct “absolute” proofs, by which the consistency of systems could be established without assuming the consistency of some other system.

Gilbert is determined, Gilbert does not budge, Gilbert falls and learns Gilbert does not give up Gilbert puts consistent efforts, In establishing absolute proof of You guessd it right, "Consistency"

The first step in the construction of an absolute proof, as Hilbert conceived the matter, is the complete formalization of a deductive system. This involves draining the expressions occurring within the system of all meaning: they are to be regarded simply as empty signs. How these signs are to be combined and manipulated is to be set forth in a set of precisely stated rules. The purpose of this procedure is to construct a system of signs (called a “calculus”) which conceals nothing and which has in it only that which we explicitly put into it. The postulates and theorems of a completely formalized system are “strings” (or finitely long sequences) of meaningless marks, constructed according to rules for combining the elementary signs of the system into larger wholes.

Moreover, when a system has been completely formalized, the derivation of theorems from postulates is nothing more than the transformation (pursuant to rule) of one set of such “strings” into another set of “strings.”

Peano’s axioms can be stated as follows: 1. Zero is a number. 2. The immediate successor of a number is a number. 3. Zero is not the immediate successor of a number. 4. No two numbers have the same immediate successor. 5. Any property belonging to zero, and also to the immediate successor of every number that has the property, belongs to all numbers. The last axiom formulates what is often called the “principle of mathematical induction.”

Interesting, I have come across similar axioms in the "Principia Mathematics" by Whitehead & Russell. Of course, I haven't read the original text (apparently Godel has read it cover-to-cover, no wonder he was able to tatter it into pieces)