*Slate* runs a good debunking of romantic popular misinterpetations of Godel’s theorem. Key quote

The precise mathematical formulation that is Gödel’s theorem doesn’t really say “there are true things which cannot be proved” any more than Einstein’s theory means “everything is relative, dude, it just depends on your point of view.”

I’ve lost count of the number of times I’ve seen dubious appeals to intuition or claims about chaos theory and the like supported with reference to Godel’s theorem, but I have derived the following proposition:

Quiggin’s metatheorem: Any interesting conclusion derived with reference to Godel’s theorem is unfounded.

Feel free to evaluate with reference to the post title, and your level of interest in the formalist program.

{ 1 trackback }

{ 82 comments }

Jonathan 03.10.05 at 9:45 pm

But what should we think about his ontological proof? Or umlauts?

Brian Weatherson 03.10.05 at 9:56 pm

I thought the best bit of Jordan’s article was the story about his fourth-grade class on peanut butter sandwiches. Either his teacher had read Quine as a student, or they had some real philosophical talent.

bob mcmanus 03.10.05 at 9:59 pm

Before I click the link I test my own popular misconception:Any descriptive system or language can be complete or internally consistent, but not both. Looking at this, I thought “taxonomy?” and decided Godel may be technically limited to mathematical or logical languages, but that would be no fun, especially for those of us who connect him with fugues and staircases.

Matt Weiner 03.10.05 at 10:05 pm

I hope the Slaters let Jordan give a good talking to Tim Noah, who said (of David Brock), “‘Everything I say is a lie’ is a standby of late-night bull sessions in college dormitories, sometimes attributed to Episode 41 of Star Trek, titled ‘I, Mudd.’ In fact, the true provenance of such riddles is Kurt GÃ¶del’s Incompleteness Theorem.”

“Everything I say is a lie” is just a version of the Epimenedes paradox, which is of ancient origin.

Matt Weiner 03.10.05 at 10:06 pm

Whaddaya know, WordPress doesn’t help morons who neither close tags nor use preview. The link actually still works.

bob mcmanus 03.10.05 at 10:15 pm

Well, read the article. I don’t know where I got my formulation above, maybe 20 years ago in Hofstadter. I will admit that I look at theoretical physics(string theory) and cosmology thru my lay psuedo-Godel sunglasses and shake my head in sadness.

“Unified Theorey of Everything? Someday Godel will break their hearts.”

I find a kind of comfort there.

Keith M Ellis 03.10.05 at 10:23 pm

Add to this list the vulgar mechanistic interpretation of Heisenberg Uncertainty. These are, in my opinion, the Big Three.

Pop relativity is so ubiquitoius, so endemic to contemporary culture, that I don’t think you can point to any single writer or personality as being responsible. In the case of HU and related QM vulgar misrepresentations, chief blame lies at the feet of the 70s and 80s popularizers that linked QM with Eastern mysticism, particularly Gary Zukav.

It’s not quite fair to Douglas Hoftadter to blame him for vulgar GÃ¶delian philosophy as he does an admirable job of treating the subject rigorously though in a popularizing context in GEB. Even so, most people who read GEB skip the actual work involved (and which Hofstadter almost begs the reader to perform) in GEB and come away from the book with a sloppy gloss on GÃ¶del’s Incompleteness.

The common thread in these ideas and the key to understanding why they are so important to and representative of pop philosophy is that they are implicitly epistemological and implicitly or explicitly, at least superficially, concerned with the limits of knowledge. The transition in both science in general and in western culture away from the hubris of nineteenth century absolutist determinism is important and legitimate; but in the vulgar consciousness these ideas are totemified and serve rhetorical, not intellectually rigorous, purposes. Not that most practitioners are aware of this.

It’s hard for me to imagine any subject, even in the vulgar context, that

requiresmore rigour than epistemology. Without rigour, the subject lacks utility at best and is pathological at worst.Geoff Robinson 03.10.05 at 10:26 pm

Peter Novick’s That Noble Dream is good on how some early 20th century historians rushed to embrace the uncertainty principle but sadly had no idea what they were talking about.

edhall 03.10.05 at 7:00 pm

None of this tops “quantum jump” in terms of popular mis-understanding. How else could the smallest possible change be interpreted to mean a paradigm-smashing event? (And speaking of “paradigms” …)

dsquared 03.10.05 at 7:10 pm

OK, count me among the heretics on this one. I believe that Searle, Lucas and Roger Penrose are fundamentally correct when they argue (make arguments which imply) that one implication of Goedel’s Theorem is that no Turing machine is a syntatic system.

I also think that the Axiom of Choice is transparently wrong, but that’s for another time. Come to think of it, I do think that there are particular ethical conclusions that can be drawn from Special Relativity, but those are also for another post.

Dan Simon 03.10.05 at 8:51 pm

I’m with Ed Hall on this one.

“You have nothing to do but mention the quantum theory, and people will take your voice for the voice of science, and believe anything.”

— G.B. Shaw,

Geneva(1938)edhall 03.10.05 at 8:59 pm

My “7:00pm” post was made

afterGeoff Robinson’s “10:26pm” post. Seems that WordPress and/or some sysadmin has reordered the timeline. (My comment makes a bit more sense after the thread drift of the then-preceding eight.) I’d make a physics analogy, butthatwould just be silly…Walt Pohl 03.10.05 at 9:02 pm

Last time I looked, the Wikipedia page was

pierre 03.10.05 at 9:05 pm

How else could the smallest possible change be interpreted to mean a paradigm-smashing event?The transition from one quantum state to another has no intermediate states. Hence.

Walt Pohl 03.10.05 at 9:06 pm

That’s bizarre. Somehow, I accidently posted my reply half-written, and the software placed as the 5th reply, when it should have been the 13th.

Joe 03.10.05 at 9:07 pm

Jordan Ellenberg is right about two things: most mathematicians can get along just fine without ever thinking about GÃ¶del, and most people who cite GÃ¶del’s theorem outside of mathematics are cranks. It seems that he is not entirely immune to the second point.

The reductionist (or do I mean formalist?) program was not killed by GÃ¶del. Far from it. Whether they know it of not, whether they’re are trying to or not, (almost) all mathematicians are doing work that can easily be formalized within set theory and all of their theorems can be proved in ZFC. So they are “limited” by GÃ¶del’s theorem, even if (as Jordan points out) they are not likely to ask provably undecidable questions in their everyday work. But it’s not as if Jordan Ellenberg has insight into the natural numbers — however much they may exist despite our inability to axiomatize them — which would allow him to prove something which is not provable in ZFC. His colleagues would not accept such a proof as valid without some sort of philosophical upheaval. Not because they think about of care about ZFC, but because the formalist (or do I mean reductionist?) program was so successful.

What I’m saying is: the axiomatic fondations of mathematics are strong, GÃ¶del didn’t weaken those foundations (he only illuminated their nature) and the conclusion of Jordan’s article is complete bunk.

(But he’s allowed his opinion. It’s not like I can prove any of what I just stated.)

pierre 03.10.05 at 9:09 pm

BTW I think the new software is confused by commenters in different time zones. I read comment #14 before my comment #6 was composed!

Will this be #7?

Randolph Fritz 03.10.05 at 9:24 pm

I think Ellenberg overstates his case by a good bit. It’s true, I suppose, that Goedel’s incompleteness theorem is more of a confirmation of something that seemed likely from mathematical experience than a world-shattering, revolutionary surprise. The formalist claim of completeness was made partly to astonish, and while ultimately it turned out to be false, the trip it took mathematics on was worth making. But Ellenberg’s “at least so far” rings very hollow in a field where we still rely, day-to-day, on ideas thousands of years old; if incompleteness still makes no difference to number theory in a few thousand years, then we can let that go by.

And, by the way, Ted Chiang covered all this ground to enormous effect in his story “Division by Zero”. It’s collected in *Stories of Your Life and Others”, which I think would be of interest to all the *Crooked Timber* authors.

Brian Weatherson 03.10.05 at 9:33 pm

I’m not sure where in the comments order this will turn up, but I only just noticed one clear counterexample to Quiggin’s conjecture formerly known as a metatheorem(at least on its most natural reading), namely the proof of the unprovability of the consistency of arithmetic.

If we take Godel’s theorem to be the incompleteness proof, then the unprovability of consistency is a separate result, one which Godel published six months later and which was independently derived (as a consequence of the incompleteness result) by von Neumann.

The unprovability of consistency is actually a bit of an embarrassment for Jordan’s claim that Godel’s theorem is primarily about relatively abstract claims like P that are of little interest to the practicing mathematician. That we can’t prove 2+2=5 is a pretty important fact – if indeed it is a fact! For that matter the continuum hypothesis seems pretty important from where I stand, but that could be because philosophers these days care more about set theory than about any other branch of mathematics.

Two other random thoughts.

The argument that the Godel sentence P is true in Jordan’s article goes by much too quickly. All that informal argument shows is that no natural number is the code of a proof of P. It’s still consistent to say that P is false. Remember P doesn’t strictly say that it has no proof, it just says that no number satisfies a certain equation, and that equation has the property that if a natural number satisfies the equation that would correspond to a proof that P. Now we could boldly conjecture that arithmetic is inconsistent and some natural number does satisfy the equation. More interestingly, we could conjecture that some unnatural number satisfies the equation in a way that does not correspond to P actually having a proof. (That is, we could conjecture that the translation between numbers and proofs breaks down.) Doing so is consistent (if arithmetic is consistent) and gives us a new class of numbers to play with – transfinite numbers. I haven’t looked at this stuff for years, but from memory it was a move like this that let Conway build some of his fancy realms of unnatural numbers. All fun stuff, and potentially of relevance to a number theorist!

(This sort of suggests that one consequence of Godel’s argument, the undefinability of ‘finite’, should be of interest to number theorists. Maybe not.)

I wasn’t quite sure what Daniel meant in his post. I thought Searle always argued that Turing machines were nothing but syntactic systems – the problem is that they aren’t semantic. And the simple answer to Searle is that Turing machines don’t have intrinsic semantic properties, but that’s only because intrinsic semanticness is not to be had. You get to represent things by being related to them in the right way, and there’s no reason why a Turing machine that’s suitably hooked up to its environment couldn’t have semantic properties.

Danny Yee 03.10.05 at 9:51 pm

Historian K.N. Chaudhuri wrote an excellent work

Trade and Civilisation in the Indian Ocean: An Economic History from the Rise of Islam to 1750. Enough for me to hunt down his later bookAsia Before Europefrom the library…What do I find? He’s been to a conference full of lunatic French philosophers, and is now using everything from Gödel’s Theorem to the Axiom of Choice as arguments for his historical theses. Aaaarrgggh!

Anyway, I’d add the Axiom of Choice to the metatheorem: it has no (direct) application outside mathematics (how many uncountable collections are there in the real world?)

John Emerson 03.10.05 at 10:01 pm

Goedelians should think twice before accusing people of being lunatics. That’s all I have to say.

Christopher Ball 03.10.05 at 10:27 pm

Ellenberg’s argument would be more compelling if he avoided a compositional fallacy:

But most pure mathematicians can easily go through life with only a vague acquaintance with GÃ¶del’s work. So far, I’ve done it myself.Joe 03.10.05 at 10:52 pm

But most pure mathematicians can easily go through life with only a vague acquaintance with GÃ¶delâ€™s work. So far, Iâ€™ve done it myself.This is funny. I don’t know about it being a compositional fallacy, but it does sound like he’s admitting that he doesn’t know much about the subject of his column. I most humbly agree.

pedro 03.10.05 at 11:23 pm

I humbly agree with Jordan Ellenberg, though I may be accused of not being the sort of person who cares too much for Godel’s incompleteness theorem. On the other hand, Godel’s completeness theorem (equivalent to the compactness theorem of first order logic) has very important applications in mathematics, via model theory. I also rely very heavily on the Axiom of Choice. So I’m looking forward anxiously to dsquared’s critique. I’m sure it will be enjoyable to read, as is the case with everything he writes.

Luc 03.10.05 at 11:57 pm

Is this reordering of arguments part of some Goedelian experiment?

As for the AI stuff, I have never understood how philosophers can get away with refusing to define consciousness in mathematical terms and then thinking that referring to mathematical results makes their argument that there is no strong AI.

There’s little point in discussing Turing machines, Goedel, or Chinese rooms for that matter, if the result is predestined by what, in my limited view, is some ad hoc description of consciousness or intelligence.

John Quiggin 03.11.05 at 2:48 am

“That we canâ€™t prove 2+2=5 is a pretty important fact – if indeed it is a fact! ”

Actually, I’m pretty sure that we can prove both 2+2=4 and 45.

For the first step, take the proof by Russell and Whitehead ( p 362) that 1+1=2 and make the obvious adaptations. The second step is right by whatever axiom is needed to ensure N is an infinite set. Taken together we have

2+25.

Let no-one say you don’t learn useful stuff here on CT. Next up, evidence that water is wet.

John Quiggin 03.11.05 at 2:49 am

Sorry should be 4â‰ 5 and 2+2â‰ 5 in comment above

Kieran Healy 03.11.05 at 3:03 am

> Next up, evidence that water is wet.

If you ask Kent Bach, he’ll tell you that water isn’t wet. It makes things wet.

Matt Freestone 03.11.05 at 3:41 am

One way of looking at Godels first theorem is that it tells you that first order logic isn’t up to the job of characterising what we mean by arithmetic systems. Of course, it has the nice property of being provably complete + consistent, which a lot of mathematicians were worried about at the time.

If you go to a higher order logic, you can characterize what you mean by arithmetic more precisely and the problem goes away. Or rather, it goes into the logical system itself, which becomes more descriptive at the price of being incomplete.

btw – I’d also be really interested to hear Dsquared expand on his post.

bad Jim 03.11.05 at 3:43 am

Grrr. As anyone who has dealt with sensors with limited resolution can attest, it is in fact the case that 2+2=5, for sufficiently large values of 2.

Henry 03.11.05 at 3:44 am

Randolph – we had a brief “discussion”:https://crookedtimber.org/2003/08/01/philosophical-romances/ of _Division by Zero_ and Godel last year

Darren 03.11.05 at 4:09 am

So what is the opinion of John R Boyd around here?

g 03.11.05 at 4:17 am

A simpler refutation of “Quiggin’s metatheorem”: Goedel’s incompleteness theorem is *itself* an interesting conclusion.

dsquared: you surely don’t mean what you say, which is provably false and isn’t what Lucas, Searle and Penrose have been arguing for. I think Lucas’s argument had been refuted by Putnam before Lucas even published it; I don’t recall Searle talking about Goedel, but his “Chinese room” argument is utterly demolished by what he calls the “systems reply” and derives its power-to-convince not from logic but from a compelling mental image which happens to be many, many orders of magnitude away from being possible and therefore takes the intuition into realms where we shouldn’t trust it; and Penrose seems to me to be doing much the same as Lucas but surrounding what he does with clouds of erudite obfuscation to make outright refutation harder without changing the fallacious core of the argument.

I thought Ellenberg’s article was pretty good, though anyone who can write “dizzy-making” where “dizzying” would have done and call GEB an “exposition” needs to tighten up his thinking and writing a wee bit. And yes, his last paragraph is pretty silly.

(Note for anyone wanting to read comments in actual chronological order: I’m in the GMT timezone.)

abb1 03.11.05 at 6:21 am

Actually, Iâ€™m pretty sure that we can prove both 2+2=4 and 4â‰ 5.Clearly you’re an Ivory Tower Liberal Elitist who’s never dealt with real-life finance, media or politics.

Michael Mouse 03.11.05 at 7:03 am

Quigginâ€™s metatheorem: Any interesting conclusion derived with reference to Godelâ€™s theorem is unfounded.I think this metatheorem contains the seeds of its own destruction, in true Hegelian stylee. It’s either unfounded, uninteresting, or both.

If it’s both well-founded and interesting, then the meta-theorem itself represents an interesting conclusion derived with reference to Goedel’s theorem. By its own lights it must, therefore, be unfounded.

Nodding to Occam, I think we multiply very few entities if we take the line that it is, in truth, not a very interesting metatheorem.

Matt 03.11.05 at 8:30 am

The axiom of choice isn’t so bad. It’s unavoidable in the countable case– Russell’s example (constructing a set of ‘right’ socks from an infinite set of pairs of socks requires an axiom of choice) persuades me.

And it’s not so bad in the in the uncountable case either. Descriptions of the various notorious examples (Banach-Tarski, et. al.) tend to leave out the basic point that unmeasurable sets are not physically realizable. At least in the negative form (there are uncountable sets on which one cannot consistently define a measure) AC seems OK to me.

Brock Sides 03.11.05 at 8:58 am

John Quiggin wrote, replying to Brian Weatherson:

“That we canâ€™t prove 2+2=5 is a pretty important fact – if indeed it is a fact!”Actually, Iâ€™m pretty sure that we can prove both 2+2=4 and 4≠5.Of course we can prove 2+2≠5 from the usual arithmetic axioms. It’s a trivial proof.

But can we also prove 2+2=5? If the axioms are inconsistent, i.e. if arithmetic is a load of bunk (as Boolos put it), then we can.

Now I don’t believe the usual axioms of arithmentic are inconsistent. No one does. After all, I can specify a model in which they are all true. But we can’t prove it. Or, more to the point: if we can prove that the axioms are consistent, then they aren’t.

Mark Kalderon 03.11.05 at 9:01 am

Quigginâ€™s metatheorem: Any interesting conclusion derived with reference to Godelâ€™s theorem is unfounded.

If that is understood as “derived with reference to Godel’s theorem alone” then I agree. Indeed it would be merely an application of Benacerraf’s dictum “No philosophy in, no philosophy out” or you can’t derive a philosophical conclusion for a mathematical result without supplementary philosophical assumptions.

Brock Sides 03.11.05 at 9:12 am

I wrote:

Now I donâ€™t believe the usual axioms of arithmentic are inconsistent. No one does. After all, I can specify a model in which they are all true. But we canâ€™t prove it. Or, more to the point: if we can prove that the axioms are consistent, then they arenâ€™t.I guess I should be a little more specific here: If we can prove that the usual axioms of arithmetic are consistent, using just the usual axioms of arithmetic, then they aren’t consistent. Of course I can prove they’re consistent if I add another axiom, viz. “the usual axioms of arithmetic are consistent.” But then I can’t prove that that new system is consistent, without adding further axioms. (Unless of course it’s inconsistent, in which case I can prove anything.)

peter ramus 03.11.05 at 10:26 am

I love this kind of talk.

(Recently at Pharyngula P.Z. Meyers set his comments to run from newest comment to oldest. Reading down, it was startling to run across the contradiction of a point that hadn’t been made yet. But this G&oum;del mash-up is way better)

A question to brock sides. You say,

Does this mean the same thing as saying they aren’t all “axioms,” that some irreducible number of them can always be provably swapped out for another likely formulation, as with the non-Euclidean geometries?

I look forward to seeing you answer my question before I post it.

peter ramus 03.11.05 at 10:27 am

On reflection, Gödel, eh?

Dave MB 03.11.05 at 10:30 am

Penrose’s first book struck me as amazingly badly

reasoned for a man with so many genuine accomplishments.

A friend of mine who does work on quantum cryptography

said he had asked Penrose at a lecture:

“You say that consciousness is impossible for a machine

because it exploits certain quantum effects. I have built

machines that exploit quantum effects in interesting ways,

such as to send bits across a channel that cannot be intercepted.

Why couldn’t a machine be built to exploit the quantum

effects you speak of, and thus create consciousness?”

Penrose, he says, essentially didn’t answer…

Cosma 03.11.05 at 10:49 am

dsquared:

> no Turing machine is a syntatic system

The mind boggles.

Alan Bostick 03.11.05 at 11:03 am

I think I’ve nailed what I don’t like about Jordan Ellenberg’s dismissal of GÃ¶del’s incompleteness theorem. Ellenberg writes:

The parable of the peanut-butter sandwiches seems to be referring to (or, at least, it reminds me of) Abraham Robinson’s nonstandard analysis. A mathematician can step out of strict number theory into a realm where P is provable and where P does not encode “P cannot be proven”, so the proof of P does not result in contradiction. That’s all well and good for the number theory we started with; but in the new nonstandard realm there exists a statement P’ which

doesencode “P’ cannot be proven”. You can continue this recursively, but at every stage there will always be a statement that cannot be proven without contradiction until the next iteration.(I’m not actually a mathematician; I just know a few bits and pieces of mathematics.)

In the end, Ellenburg trivializes GÃ¶del’s theorem by saying that statement P might not be provable, but it’s not an interesting statement in the first place. (Those grapes were sour anyway.) This reminds me of the proof that there are no uninteresting integers.

Andrew Boucher 03.11.05 at 12:10 pm

“This reminds me of the proof that there are no uninteresting integers.”

I can’t imagine how the proof goes, because it’s clear the easy proof is that all integers are interesting.

Pf:

0 is obviously interesting. If x is interesting, then (x+1) is interesting (since subtracting 1 produces an interesting number).

But then all natural numbers are interesting.

If x

digamma 03.11.05 at 12:10 pm

Does anyone agree with me that the question of whether God knows the future can be reduced to the halting problem, and thus answered “no”?

Sebastian Holsclaw 03.11.05 at 12:26 pm

The basic problem I have with the article is found in this portion:

The problem with popularizations of the incompleteness therom is not that “there are true things which cannot be proved” is a bad aphorism, it is that the aphorism is misused by antirationalists. The fact that there are true things which cannot be proved is not an indictment of those true things which can be proved, nor is it an indictment for systems which prove the true things that can be proved.

Clayton 03.11.05 at 12:34 pm

I thought that something significant could be derived from the observation that it is not apriori that it was Godel who was responsible for the discovery of Godel’s theorem. Is this the undoing of Quiggin’s metatheorem?

Brian Weatherson 03.11.05 at 12:34 pm

Andrew,

The proof isn’t quite like that. I learned it as a the following.

# If not all numbers are interesting, then by an application of the least number theorem, there is a least number that is not interesting.

# Being the least number that is not interesting is interesting.

# So there is no least number that is not interesting.

# So, by our application of the least number theorem, all numbers are interesting.

I remember reading a book on interesting numbers where they dodged this problem by having the first number about which they had nothing (else) to say be interesting for that reason, and not letting numbers be interesting for higher-order reasons.

Brian Weatherson 03.11.05 at 12:37 pm

Oh, and what Brock said above about Quiggin’s conjecture!

That we can prove 2 and 2 isn’t 5 doesn’t show we can’t prove that it is. Which is interesting!

Walt Pohl 03.11.05 at 12:50 pm

I thought I’d try posting to this thread again, in the hopes my response won’t end up in the middle where no one will read it.

Bob: It’s not true that systems are either complete or consistent, but not both. Complete and consistent axiom systems are not particularly rare (though not particularly common either). For example, Euclidean geometry is complete and consistent. It’s only when your system allows you to make statements about the integers that you are in trouble.

Brian: I’m pretty sure there’s no direct connection between assuming Goedel’s P to be false and Conway’s work. They both have in common that they imply the existence of infinitely large numbers, but systems with infinitely large numbers are pretty thick on the ground: ordinals, cardinals, etc.

Peter: I’m not sure I understand what you’re saying, but here goes. Goedel’s second incompleteness theorem states that no consistent axiom system can prove its own consistency. (Inconsistent axiom systems can be used to prove anything.) In some systems, you can’t even state consistency (within Euclidean geometry there is no way to encode “Euclidean geometry is consistent”), but systems where you can (such as number theory) are necessarily incomplete.

Alan: Goedel’s P probably is uninteresting, but since it’s just an algorithm for generating unprovable statements, it’s probably too much to ask for it to only generate interesting ones as well. Where Ellenburg (probably) goes wrong is assuming that any interesting question in number will turn out to be decidable using current axioms. This has certainly failed to be the case in set theory. The large number of open problems in number theory is certainly suggestive in that regard.

Luc 03.11.05 at 1:35 pm

As for 2 + 2 = 4 and 4 not equal 5, I remember vaguely peano aritmetic. It wouldn’t matter at all that 2 + 2 = 4 and 4 = 5 if you simply defined S(3) = 4, 4 = 5, and S(5) = 6.

Not that it would be useful in any way, but it would introduce no (new) inconsistencies in simple arithmetic.

And these abstractions aren’t entirely useless because irl you have to be able to understand that 12 can be equal to 10 and equal to A depending on the context.

Matt 03.11.05 at 1:49 pm

Goodstein’s Theorem (which I won’t try to explain, but you can look it up) is an example of a non-trivial, non-self-referential theorem that can’t be proved in Peano arithmetic.

pedro 03.11.05 at 2:14 pm

Something as simple as the principle of well-ordering for the natural numbers is not expressible in first order logic. How can one say that every subset of the natural numbers has a least element in a finite-length first order sentence? The reason why first-order logic is useful in mathematics is that it satisfies compactness and the Lowenheim-Skolem theorems. One can go to higher order logics and capture more aspects of mathematics (one gains expressive power), at the huge expense of losing compactness.

peter ramus 03.11.05 at 2:44 pm

walt pohl: thanks for your answer. I take it that Euclidean geometry and its alternates aren’t sufficiently formal in the Gödelian sense to meet the requirements of his theorem, and therefore can’t be broken on the hasp of his neat argument.

My question to brock sides was about “they aren’t” in the phrase “if we can prove that the axioms are consistent, then they aren’t.” Did it mean they aren’t consistent, or they aren’t “axioms” or a little of both?

Sorry if my curious question baffled you. I don’t mind showing off my hard-won ignorance but I do regret any confusion it engenders.

Daryl McCullough 03.11.05 at 2:45 pm

“Quiggin’s Metatheorem: Any interesting conclusion derived with reference to Godelâ€™s theorem is unfounded.”

That’s almost certainly right, if by “interesting conclusion” you mean of practical interest. Godel’s theorem (trying to make an umlaut obviously causes browsers to spit out garbage, so I’m not going to try) just tells us that certain things are in principle impossible, but we don’t need Godel’s theorem to know that they are in

practiceimpossible. I find, though, that in principle impossibility is interesting in itself—like perpetual motion, exceeding the speed of light, trisecting an angle, etc.With all respect, dsquared, Penrose and Lucas are

mistaken. Godel’s theorem doesn’t say anything at all about whether AI is possible. It says that computers can never do certain things, but there is absolutely no reason to believehumanscan do them, either.Andrew Boucher 03.11.05 at 2:52 pm

“Goedelâ€™s second incompleteness theorem states that no consistent axiom system can prove its own consistency.”

This is a popular way of expressing it, but as expressed, it’s not true. For one thing, the axioms and rules of inference must be of a particular sort (basically, a machine must be capable of verifying instances). For another, the system must be sufficiently strong. Systems which are ontologically weak (basically, which don’t assume the Successor Axiom) may prove their own consistency.

John Quiggin 03.11.05 at 3:09 pm

I managed to cut and paste an umlaut in the original post, but subsequent attempts seem nÃ¶t tÃ¸ bÃ© wÃ´rking so well, though these lÃ¸Ã¸k fine in preview

Alan Bostick 03.11.05 at 3:38 pm

Aside to spelling pedants: if your character set doesn’t include umlauts, the name is better spelled as “Goedel”.

Brock Sides 03.11.05 at 3:42 pm

My question to brock sides was about “they arenâ€™t” in the phrase “if we can prove that the axioms are consistent, then they aren’t.” Did it mean they aren’t consistent, or they aren’t “axioms” or a little of both?Aren’t consistent.

Clark Goble 03.11.05 at 3:50 pm

Pasting in non regular ASCII characters screws up HTML. Go to this site paste in your text and it’ll convert it to properly formatted HTML. I wish most bloggers would do this as it really becomes apparent when Mac folks read PC blogs or vice versa. Technically doing HTML with 8bit ASCII is a no-no.

novalis 03.11.05 at 9:33 pm

Randolph Fritz, CT has already recommended Ted Chiang — that’s where I heard of him, IIRC.

Still, I think Divide By Zero is his weakest, and is not worth reading. I don’t know anyone who likes it. But I do recommend that everyone buy that collection and read the rest of the stories. Chiang is simply smarter than other authors.

Dell Adams 03.11.05 at 10:10 pm

(2^n)-1st!

John Quiggin 03.11.05 at 11:47 pm

Brock and Brian, given that we can prove 2+2=4â‰ 5, if it were true that we could prove 2+2=5, this would mean that the axioms were inconsistent, in which case, we can prove anything. Put this way, it looks less interesting to me that we can’t prove that we can’t prove consistency. Of course, if we could prove that arithmetic was inconsistent, that would be

veryinteresting, in the sense of the fictitious Chinese curse.At this point, my recollection of my logic courses becomes hazy, but it’s my impression that we can avoid inconsistency as long as we accept incompleteness.

R.Mutt 03.12.05 at 4:20 am

Heâ€™s been to a conference full of lunatic French philosophers, and is now using everything from GÃ¶delâ€™s Theorem to the Axiom of Choice as arguments for his historical theses.That must be the influence of Badiou! In his opus magnum L’Ãªtre et l’Ã©vÃ©nement he dedicated several chapters to the ontology of ZFC, GÃ¶del’s theorems and Cohen’s “forcing”. I’m not completely sure Badiou is a lunatic, though.

Robert Vienneau 03.12.05 at 5:04 am

Here’s an interesting reference to Goedel, Sraffa, and Einstein:

http://ssrn.com/abstract=608642

I find it highly questionable, to be nice.

Brock Sides 03.12.05 at 10:22 am

Brock and Brian, given that we can prove 2+2=4≠5, if it were true that we could prove 2+2=5, this would mean that the axioms were inconsistent, in which case, we can prove anything. Put this way, it looks less interesting to me that we can’t prove consistency.Interesting is in the eye of the beholder, I suppose. Given the interesting fact that you can express “the axioms of arithmetic are consistent” in the language of arithmetic, one naturally would wonder whether you can prove this from the axioms of arithmetic. G&oml;del’s Second Incompleteness Theorem tells us we can’t. (Unless, of course, the axioms are inconsistent, in which case we can prove anything.)

Far more interesting and surprising to me is Löb’s Theorem, which states that the seemingly obvious statements of the form “Provable(P)->P” are not provable from the usual axioms of arithmetic. (Again, provided that the axioms are consistent.)

At this point, my recollection of my logic courses becomes hazy, but itâ€™s my impression that we can avoid inconsistency as long as we accept incompleteness.Yes. The ususal way of stating Gödel’s First Incompleteness Theorem is “Any sufficiently strong axiomatic theory is either incomplete or inconsistent.” (Sufficiently strong is usually cashed out as “As least as strong as Robinson’s Arithmetic Q, which consists of the Peano axioms minus the axioms of induction.) Of course, this doesn’t tell us whether the theory in question is incomplete or inconsistent, only that it is one or the other.

Again, nobody really thinks that the usual axioms of arithmetic are inconsistent. After all, I can describe a model in which they are all true! But you might think, “It would be nice if the axioms could prove themselves consistent.” G&oml;del’s answer: “No, it wouldn’t.”

anatoly 03.12.05 at 3:20 pm

But you might think, â€œIt would be nice if the axioms could prove themselves consistent.â€ Godelâ€™s answer: â€œNo, it wouldnâ€™t.â€Think about it: if the axioms proved themselves consistent, what would that tell you? After all, if they are inconsistent, they could prove anything at all, including their consistency! So why would their proof of their own consistency give you any more grounds to trust them?

It’s not the fact that

a system can’t prove its own consistencythat’s really interesting; it’s the fact thata system that seemingly formalises our intuitive finitistic reasoning about numberscan’t do it.Thatis what buried the formalit program, or at least has been widely considered to have done so.Walt Pohl 03.12.05 at 7:54 pm

Anatoly: The significance was that Hilbert hoped that a weaker system could prove the consistency of a stronger system, that something like Peano arithmetic could be used to prove the consistency of real analysis. Goedel’s second incompleteness theorem shows that that’s impossible.

The fact that a system can’t prove its own consistency is used frequently in set theory. One way to prove that a mathematical statement is not a theorem of ZFC (the name for usual set theory) is to prove that the statement can be used to prove the consistency of ZFC.

John Quiggin 03.12.05 at 10:16 pm

Can you confirm my interpretation of your last remark, brock?

Do we know that there exists is a system which can be proved (presumably in some higher-order system) to be consistent and which includes the usual axioms of arithmetic?

Jay 03.13.05 at 7:46 am

Quiggan’s metatheorem is just a restatement of an earlier postulate of mine: “There is nothing more boring than non-mathematicians discussing the implications of Godel’s theorem except non-physicists discussing the philosophical ramifications of quantum physics.”

Daniel 03.13.05 at 3:46 pm

Cosma and Brian noticed by attempt to subvert the dominant paradigm by cunningly typing “syntactic” instead of “semantic” …

My understanding is that Searle’s current position (which which I agree, and I don’t agree that the Systems Reply is a “devastating critique”, or that the Lucas/Penrose argument has been refuted by anything Putnam’s published) is that there is no such thing as a syntactic system which is not a semantic system, because syntactic systems are only syntactic in as much as we interpret their output as having content.

In other words, what a computer (or a Chinese room) does is to turn switches on and off, and this can only be called “syntactic manipulation” if there is somebody around to interpret it as such; a symbol isn’t a symbol unless it signifies. So I’d argue that Brian’s “connected up to the world in the right way” has to mean “connected up to some part of the world which has ‘real’, non-derived intensionality”. I do think that there is such a thing as “intrinsic semanticness”, because I’ve got it and so (I presume) has my wife. My son appears to be developing it.

But we Searleans, rather like we Welsh, are a small and unpopular nation, more keen on backbiting against our more powerful neighbours than taking them on in open combat.

On the Axiom of Choice, I just don’t like it because I think it’s at the root of a lot of the difficult paradoxes in probability; I’m not happy with the idea of being able to select a set of points on the basis of no particular criterion of selection. In particular, a lot of the “sadistic angel” problems previously posted on CT disappear if you assume the negation of the AoC, as it becomes clear that the angel is offering you a pretend-gamble based on pretend-probabiliies.

Meanwhile, the particlar ethical conclusions from Special Relativity relate to a weak version of consequentialism; I think that the role of c in special relativity, based on the requirement to preserve the order of causation in all frames of reference, rules out “backward-causal” moral principles like, for example, the view that murders of Kurds in 1989 can be part of the rationale for a war in 2003.

Andrew Boucher 03.13.05 at 5:06 pm

“Do we know that there exists … a system which can be proved (presumably in some higher-order system) to be consistent and which includes the usual axioms of arithmetic?”

Yes. Z1 (first-order Peano Arithmetic, which contains the usual axioms of arithmetic) can be proven consistent in ZF set theory, not to mention Z2 (second-order Peano Arithmetic).

Jay 03.13.05 at 5:48 pm

” On the Axiom of Choice, I just donâ€™t like it because I think itâ€™s at the root of a lot of the difficult paradoxes in probability; Iâ€™m not happy with the idea of being able to select a set of points on the basis of no particular criterion of selection. In particular, a lot of the â€œsadistic angelâ€ problems previously posted on CT disappear if you assume the negation of the AoC, as it becomes clear that the angel is offering you a pretend-gamble based on pretend-probabiliies.”

Actually, no. The “sadistic angel” paradoxes, as I recall them, don’t have anything to do with the AoC. For instance, on the one where you are choosing one point out of the unit interval you could replace the unit interval with a countable dense subset and the single point with, well, any finite set, and the paradox would be the same, but now the AoC wouldn’t be necessary to choose your points.

Luc 03.13.05 at 8:07 pm

But this isn’t that relevant once you accept a form of strong AI, i.e. that non-humans can produce intensionality. That is, just as a (group of) person(s) on it’s own can be conscious, so can any other “strong AI” entity.

Thus once you start from the other side, the symbol shifters can produce their own semantics.

But Searle excludes this notion by describing it for example in the following way

“At the biological level there are actual causal mechanisms that produce consciousness, intentionality, and all the rest of it.”and then insisting that those “causal powers of the brain” must be duplicated, not simulated.That is why I’m entirely prejudiced against Searleans. Their interpretations of intelligence, consciousness, intensionality etc. seem always to revolve around the fuzzy feelgood notion that humans aren’t computers. Which is true, but not a very good basis for advancing AI.

dsquared 03.14.05 at 4:05 am

Luc, this looks more like the position Dennett wrongly attributes to Searle than his actual work. Apologies if I am wrong, but experience has led me to generally suspect that when I see the words “fuzzy feelgood notion”, then a) I’m talking to someone whose main exposure to Searle’s argument has been through Dennett’s summaries and b) the argument is going to get really personal and unpleasant pretty soon, because lots of people who take on board Dennett’s arguments also appear to adopt his polemic style.

Just as a set of preliminaries, I would like to make it clear that the phrase “strong AI” is just as fuzzy as anything in Searle, and that whatever makes me feel good, I suspect that the possibility of intensional computers makes you feel just as good. So can we please not use phrases like “fuzzy feelgood notion”, which don’t advance anything and really only serve as a form of intellectual insult.

Searle’s actual point (and to be hoenst, he hasn’t helped matters by changing his mind on the importance of syntax/semantics, or by some of his examples like the one about simulated fires) is one that can be put into terms that don’t look particularly objectionable to anyone who believes that intensionality is important. Viz:

Brian talks about things being “connected up to the world in the right way”. But a Turing machine can’t be connected up to the world at all, in any way, because it’s an abstract entity[1]. An

instantiationof a particular Turing machine can be connected up to the world (and thus, potentially, connected up to the world in the right way), but if it is, then it is connected up to the world as a physical object, not as a Turing machine, and a similarly constructed physical object which was not (which we did not choose to view as) a Turing machine would also be “connected up to the world in the right way”. Therefore, while some physical instantiations of Turing machines might be intensional, nothing is intensionalby virtue of being a Turing machine.[1] This point is arguable, but I would personally defend the view that a connection to the world via some predicate of the kind “is an instantiation of” is not really much of an advance from the mind/body problem.

Brock Sides 03.14.05 at 7:09 am

Do we know that there exists is a system which can be proved (presumably in some higher-order system) to be consistent and which includes the usual axioms of arithmetic?Sure. You can prove the Peano axioms consistent using set theory.

Brock Sides 03.14.05 at 7:16 am

For those interested in Goedel’s theorems, Prof. Peter Smith of Cambridge has a partial draft of his book

An Introduction to Goedel’s Theoremsonline at http://www.godelbook.net.The chapters posted take you all the way through both of Goedel’s incompleteness theorems. The book does require a background in symbolic logic.

Skippy McGee 03.14.05 at 11:15 pm

If I wanted to destroy a society from within, I’d change the educational system so it turned out minds like those above. I’d train them using self-referential systems and solipsist logic until they could barely even remember to flush the toilet behind them when finished. It’s basically taking the human intellectual output jack and plugging it into the input jack to create a totally contained feedback loop which discusses the noise it hears which is created by discussing the noise it hears.

Why kill your enemy when you can reduce him to a vegetable babbling away in a corner picking lint from his own navel?

Luc 03.15.05 at 12:37 am

Daniel,

You’re right about the fuzzy thing, though a. is not the case and b. is not my intention.

But a dispute where after years and years of debate the different positions just grow further apart, is bound towards somewhat more emotional responses, as reason is unable to prevail.

The easy way out of this dispute is to just stick with weak AI, call a chess program a database with a search algorithm, and move on. But that doesn’t give much satisfaction. Just as I as i can say I have money in my bank account, and I can use it to trade in objects in role playing games, i would call at some point automated systems intelligent. Artificial, not human, but intelligent none the less.

But this gets close to a statement like a TM can’t send any email. So what? What is the relevance of it? Do we need to create another model? Or do we regress to the other end of the spectrum with Searle’s opinion that it is linked with biology?

I referred in my previous message to an interview from 2001 so this opinion is his, and fairly recent.

Quote in full (as the website is somewhat unreliable)

Daryl McCullough 03.15.05 at 9:24 am

skippy mcgee writes:

If I wanted to destroy a society from within, Iâ€™d change the educational system so it turned out minds like those above. Iâ€™d train them using self-referential systems and solipsist logic until they could barely even remember to flush the toilet behind them when finished.Do you really have any evidence that training in Godelian self-reference makes a person unable to function? If you are using discussions about Godelian self-reference as evidence, then you are being self-referential.

dsquared 03.15.05 at 1:05 pm

But this gets close to a statement like a TM canâ€™t send any email.I’ll go a bit further; a Turing machine can’t do anything at all. Turing machines are abstract entities.

A physical machine can act in a way that can be interpreted as an instantiation of a Turing machine, but this is very different. In particular, my view is that the passive-voice “can be interpreted” is covering up a big problem here; any syntactic manipulation (still less semantic) carried out by such a physical machine is entirely parastic on the decision to interpret particular physical events as having a formal role, by someone whose intensionality is not “second-hand” in this way.

Comments on this entry are closed.