Who doesn’t like self-referential paradoxes? There is something about them that appeals to all and sundry. And, there is also a certain air of mystery associated with them, but when people talk about such paradoxes in a non-technical fashion indiscriminately, especially when dealing with Gödel’s incompleteness theorem, then quite often it gets annoying!
Lawvere in ‘Diagonal Arguments and Cartesian Closed Categories‘ sought, among several things, to demystify the incompleteness theorem. To pique your interest, in a self-commentary on the above paper, he actually has quite a few harsh words, in a manner of speaking.
“The original aim of this article was to demystify the incompleteness theorem of Gödel and the truth-definition theory of Tarski by showing that both are consequences of some very simple algebra in the cartesian-closed setting. It was always hard for many to comprehend how Cantor’s mathematical theorem could be re-christened as a“paradox” by Russell and how Gödel’s theorem could be so often declared to be the most significant result of the 20th century. There was always the suspicion among scientists that such extra-mathematical publicity movements concealed an agenda for re-establishing belief as a substitute for science.”
In the aforesaid paper, Lawvere of course uses the language of category theory – the setting is that of cartesian closed categories – and therefore the technical presentation can easily get out of reach of most people’s heads – including myself. Thankfully, Noson S. Yanofsky has written a nice paper, ‘A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points’, that is a lot more accessible and fun to read as well.Yanofsky employs only the notions of sets and functions, thereby avoiding the language of category theory, to bring out and make accessible as much as possible the content of Lawvere’s paper. Cantor’s theorem, Russell’s Paradox, the non-definability of satisfiability, Tarski’s non-definability of truth and Gödel’s (first) incompleteness theorem are all shown to be paradoxical phenomena that merely result from the existence of a cartesian closed category satisfying certain conditions. The idea is to use a single formalism to describe all these diverse phenomena.
(Dang, I just found that John Baez had already blogged on this before, way back in 2006!)
Todd and Vishal's blog 
17 comments
Comments feed for this article
July 11, 2010 at 10:57 pm
Todd Trimble
Thanks, Vishal! Both papers are very nice, although I had never read Noson Yanofsky’s paper before today. I second your recommendation! A few scattered remarks:
I basically agree with your assessment about accessibility. Lawvere tends to express himself in highly concentrated form, and it can be difficult to decipher what he’s saying. To lay it on the line: Lawvere is one of the, if not the, greatest category theorist of all time — his insights are way, way ahead of his time — but there is a real danger that many of his insights will be lost unless others make the effort to understand, and explain them again.
Hence the great service that people like Noson perform for the community. Noson has a nice pedagogical touch: among other things, he has coauthored a nice gentle introductory book on quantum cryptology, accessible I would guess to most undergraduate sophomores or juniors. The present paper is similarly gentle and thoughtful, but at the same time there’s plenty of meat in there. And one very nice feature is his intellectual honesty: when he’s stuck on something, he simply says so, and has generously included a bunch of open problems to whet the reader’s further interest.
He seems to be trying to elicit interest in some of Kripke’s ruminations on modal logic. Are you thinking about modal logic these days?
July 12, 2010 at 2:13 am
Vishal Lama
You are welcome, Todd! I am really glad you like my recommendation. Indeed, the machinery of category theory is so powerful – I would dub it industrial-scale machinery – that it is inevitable it would be extremely abstract for most people. On the other hand, one useful service that expositors can perform is to it scale down all that machinery, keeping the essential meat (to borrow your word) intact, and present all the beautiful mathematics to the general lay people in a way that would entice and motivate them to learn more category theory.
I am not thinking about modal logic these days. Rather, I think I am gradually gravitating toward mathematical biology but of a category-theoretic flavor, if you will. One reason for such a motivation is a personal one, but more generally biological systems are very complex and rich and yet concrete enough for study. In particular, I have the human immune system in mind.
July 16, 2010 at 1:12 pm
Vishal Lama
Todd,
I just realized that when you mentioned “Kripke’s ruminations on modal logic” earlier, you may have wanted to express a few things that may have been on your mind, and that my previous comment probably put a dampener on your train of thoughts. Please, do forgive me. Is there something on modal logic that you would like to share? I would love to hear it!
July 17, 2010 at 1:56 pm
Todd Trimble
No problem, Vishal — I knew that you were studying modal logic for a while there, and thought maybe you were following up on Noson’s remarks. I personally am not thinking much these days about modal logic.
I did think a bit about some of his other problems, and thought that the Knaster-Tarski fixed point theorem might be ripe for picking, but didn’t quite nail it down a connection. Maybe I’ll try again in the near future.
So much math, so little time… 🙂
August 23, 2010 at 4:42 pm
El Duderino
I don’t see what Lawvere can mean by his comment on Gödel’s theorem. Of course many people may find it “hard to comprehend” that some call it “the most significant result of the 20th century”, to the extent that such a title does not make sense in a field as diverse as mathematics. But Lawvere doesn’t sound as if he’s making THAT point; rather he seems to be saying that Gödel’s theorem is in some sense simple or not deep.
Of course, it is anachronistic to make such a judgement based on the ease with which today’s machinery can derive the result. Otherwise, pretty much all of 19th-century math would be essentially trivial, from quadratic reciprocity to the fundamental theorem of algebra to elliptic function theory to the prime number theorem.
Today’s machinery and perspective developed only because of these earlier insights. In particular, the whole idea that fixpoints were good for anything in logic was developed by Gödel, Tarski and Kleene. One must be very ill-informed to advance the claim that Gödel’s theorem is simple because it can be proved easily exploiting fixpoints; it’s as if I claimed a SAT instance was easy because an assignment, found by other people after a lot of work, satisfied it.
To end with the obvious, Gödel’s theorem(s) are easily, easily the most significant results in the study of “non-tame” theories;it establishes their existence and strongest properties. Their existence, in turn, has profoundly informed and influenced all of model theory and mathematical logic.
October 16, 2010 at 4:20 pm
Todd Trimble
El Duderino, I’m not sure that’s quite Lawvere’s point. Gödel’s Incompleteness Theorem has two aspects: one a highly non-trivial technical component in which it is shown that provability in the formal system PA can be encoded arithmetically, and the other a softer conceptual component in which a “fixed point” is constructed, an arithmetical sentence which encodes its own unprovability in PA. It is the latter conceptual component which is typically explained to general non-technical audiences, and I think Lawvere’s point is that *this* component has been over-hyped by certain philosophers: his article is pointing out the commonality of this basic conceptual diagonal construction elsewhere in mathematics, wherever one has cartesian closure together with feedback (Cantor’s theorem, the Y combinator in lambda calculus, etc.). It is clear that his concern is *not* with the hard technical component of Gödel’s proof which is quite rightly celebrated as a technical tour de force, and I am sure that Lawvere would never deny that the repercussions of Incompleteness are felt all over model theory and mathematical logic as you say.
September 18, 2010 at 1:30 am
Xena
Hi Vishal. I am SO not a mathy person. I have no clue what this stuff is about. I was just wondering where you diappeared to.
Your name just came up in a discussion on feministphilosophers. Remember that little concern troll, Nemo? The one that tried to accuse you of delivering Straw Man arguments? I can’t believe I defended that git. JJ told him off the other day. I told him off just now. Blah blah blah…
So anyway, the conversation just reminded me that you’ve effectively disappeared. Is everything ok with you? Are you coming back to say hi soon?
April 16, 2019 at 8:02 am
tinincu
these are very interesting
September 26, 2010 at 4:45 pm
Jonathan Vos Post
Spelling correction for 1st sentence: “self-referential” — rather than “self-referential”
See my:
“This sentence contains ten words, eighteen syllables, and sixty-four letters.”
[Jonathan Vos Post, Scientific American, reprinted in
“Metamagical Themas: Questing for the Essence of Mind and Pattern”, by Douglas R. Hofstadter, paperback reprint March 1996, pp.26-27]
October 15, 2010 at 1:34 pm
Todd Trimble
Jonathan: yes, I see your example quoted approvingly in Metamagical Themas. This was one of his earliest columns in Scientific American, but there is a rich mine of ideas there he keeps coming back to in later columns.
He mentions for instance Lee Sallows’s magnificent
(Nice extra little nugget of self-reference in substituting ‘his’ for ‘this’ as the tenth word!)
Then Raphael Robinson proposed a fun little puzzle: complete the sentence
Each blank is to be filled with a numeral in decimal notation. There are exactly two solutions.
In his chapter 16, he revisits such self-reference by showing how to solve Robinson’s puzzle and generate Sallows-like sentences by using convergence to fixed points!!
November 30, 2010 at 1:23 am
notedscholar
Do you fellows blog anymore? I haven’t seen a post since July? Am I the only math/science wonk remaining from the old guard? Time flies so fast!
Cheers,
NS
March 3, 2019 at 12:16 pm
pampiu
so that there exist an old guard observe prof dr mircea orasanu and prof drd horia orasanu but in case of GALOIS Groups
March 3, 2019 at 12:16 pm
pampiu
,
June 8, 2019 at 3:08 pm
notedscholar
Thank you! I have still been wondering.
February 22, 2012 at 4:53 pm
secretmagazine99
Having a vacation is really fun especially if you are already that stressed out from your job, you will really have to go out and have fun and have some time by your self.key west vacation rentals
March 3, 2019 at 12:11 pm
pasadiu
indeed there are incompleteness of fixed points observed prof dr mircea orasanu and prof drd horia orasanu and followed with Algebra and equations
April 7, 2019 at 4:32 am
ootundu
and so