(2019-01-12) Shalizi Godels Theorem

Cosma Shalizi on Godel's Theorem. A much-abused result in mathematical logic, supposed by many authors who don't understand it to support their own favored brand of rubbish, and even subjected to surprisingly rough handling by some who really should know better. (Kurt Godel)

Gödel's theorem is a result about axiomatic systems, which is already a source of some confusion. In ordinary educated speech, axioms are undubitable truths; for mathematicians, they are propositions it is convenient or amusing to start from. (nature of truth)

There are really two points to setting up an axiomatic system. First, it's a very compact description of the whole field of propositions derivable from the axioms, so large bodies of math can be compressed down into a very small compass. Second, because it's so abstract, the system lets us derive all and only the results which follow from things having the formal properties specified by the axioms

An axiomatic system is said to be consistent if, given the axioms and the derivation rules, we can never derive two contradictory propositions; obviously, we want our axiomatic systems to be consistent.

Gödel showed that, either the system is inconsistent (horrors!), or there are true propositions which can't be reached from the axioms by applying the derivation rules. The system is thus incomplete, and the truth of those propositions is undecidable (within that system).

So far we've just been talking about Peano arithemtic, but now comes the kicker. Results about an axiomatic system apply to any bunch of things which satisfy the axioms.

It follows that these systems, too, contain undecidable propositions, and are incomplete.

There are two very common but fallacious conclusions people make from this, and an immense number of uncommon but equally fallacious errors I shan't bother with.

The first is that Gödel's theorem imposes some some of profound limitation on knowledge, science, mathematics. Now, as to science, this ignores in the first place that Gödel's theorem applies to deduction from axioms

This brings us to the other, and possibly even more common fallacy, that Gödel's theorem says artificial intelligence is impossible, or that machines cannot think.

Since there are true propositions which cannot be deduced by interesting axiomatic systems, there are results which cannot be obtained by computers, either. (True.) But we can obtain those results, so our thinking cannot be adequately represented by a computer, or an axiomatic system.

This would actually be a valid demonstration, were only the pentultimate sentence true; but no one has ever presented any evidence that it is true, only vigorous hand-waving and the occasional heartfelt assertion

Readings... Roger Penrose, The Emperor's New Mind (Does a marvelous job of explaining what goes into the proof — his presentation could be understood by a bright high school student, or even an MBA — but then degenerates into an unusually awful specimen of the standard argument against artificial intelligence)