Want Mail?

The first two people to email me their address get a postcard with a special Gödel Centennial stamp.

Gödel Centennial, Day 2

Day 2, Friday, was Gödel's birthday. I showed up for the panel discussion on unknowability, which wasn't particularly enlightening. Then Piergiorgio Odifreddi gave a very entertaining talk, in which he speculated on what philosophical writings may have served as inspiration for Gödel's results. He focussed on three figures: Aristotle, Kant, and Leibniz and drew some vague analogies between things Aristotle wrote in the Metaphysics and intuitionistic logic, between the antinomies of reason in Kant's first Critique and incompleteness, and Leibniz's calculus universalis and Gödel numbering. The latter was the most specific and interesting, I thought. Odifreddi reported that Sacks once told him that he heard Gödel say that he got the idea of arithmetization from Leibniz. Odifreddi went back to Leibniz' papers to see what was in there and said that the coding Leibniz used doesn't work -- the code of a string is just the product of the codes of the symbols in it. So this is an answer to the question prompted by Coffa I mentioned a while back, but at some point I should really figure out to what extent exactly Gödel coding was anticipated by Leibniz. Then Petr Hájek gave a survey of Gödel's ontological proof for the existence of God and the literature surrounding it. Hilary Putnam's talk was a follow-up to his paper "Reflexive Reflections" (Erkenntnis 22, 1985, 143-154). In that paper, he gave an argument that, if human language and scientific competence can be represented by a Turing machine, we can never know that this is so. It required an assumption, viz., that no mathematical falsehood can be justified by empirical evidence, and in this talk he attempted to get rid of that assumption.

I skipped the second panel discussion to get ready for the gala dinner that night in the Belvedere's Marble Hall. It was a very opulent affair. Here's a picture of the place setting, so you can see just how opulent:

The galleries were open, cocktails were served, Gary Kasparov spoke, we ate, then the Young Investigator Awards were presented:

• 1st prize: Justin Moore: The continuum and aleph-2
• 2nd prize: Mark van Atten: Gödel and German Idealism
• 3rd prize: Eli Ben-Sasson: Searching for a conditional answer to Gödel's question

After dessert, the string quartet performed the Barcarole from Offenbach's Tales of Hoffman, which was Gödel's favorite piece of music, and Paul Cohen gave an emotional closing speech which ended with everyone singing Happy Birthday.

Peter Smith blogs

Thanks, Peter, for telling me about your blog. Not.

Watch Logic Matters! And thanks (seriously) to Martijn Vermaat.

Computational Logician Gottlob from Vienna to Oxford

Here's where I channel Brian Leiter:

Distinguished logician and computer scientist Georg Gottlob, former chair of the Department of Information Systems at the University of Technology, Vienna, moves to Oxford University. This is a great loss for the TU Wien and the Viennese logic community. It is to be hoped that Gottlob will continue to be affiliated with the TU in some form or another.

(Georg was one of my teachers as an undergraduate -- why don't I hear about this sooner, I ask? Hello? Is noone in Vienna reading my blog?)

Nothing of Consequence

A new logic blog, from Ole Hjortland, St. Andrews: Nothing of Consequence.

(I collect logic blogs. If you have one and it's not on my blogroll, tell me!)

Happy 100, Kurtele!

Gödel would have turned 100 years old today. Happy Birthday, Kurtele! Merry Gödelmas, everyone else! I'm going to report on today's sessions (well, on Hajek's and Putnam's) at the Gödel Centennial conference tomorrow, since I have to get ready now for the fancy Gala Dinner at the Belvedere Palace. ("Black Tie Optional". I guess I'll wear a black tie, since I still don't own a tux.)

Logic Joke

Dana Scott just told this joke, which he heard from Ray Smullyan:

Two professors at a math conference stand in front of a blackboard, on which is written the sentence "Only an idiot would believe a sentence like this!" The first professor asks the second, "Do you believe that?" The second answers, "Of course not! Only an idiot would believe a sentence like this!"

Gödel Centennial, Day 1

I'm in Vienna for the Gödel Centennial conference, Horizons of Truth. Day 1 featured talks by:

• Angus MacIntyre, How much has mathematics been affected by Gödel's work? His answer: not much (yet). He surveyed the developments arising from Gödel's work (recursion theory, definability theory, results on noncomputability of classical problems such as the undecidability of the word problem for groups and Hilberts 10th problem). Then he talked about the reactions of "real" mathematicians to these results and pointed out that: a. the dimensions of the number theoretic varieties we get from, e.g., the results on Hilbert's 10th problem are higher than anything number theorists are usually interested in, and b. the unsolvability statements obtained from consistency and the like have no interesting arithmetical or geometric structure. He said that the Birch/Swinnerton-Dyer conjecture implies that logical independence results are irrelevant to number theory, and that this was shown by Manin -- anyone know what he meant and where Manin proved this? There was a little exchange between him and Sol Feferman, with MacIntyre claiming that it's "clear" that the Weil ocnjectures can be proved in PA, and Feferman saying that it's "conjecture". He went on to talk about group theory, and talked about how the group theorists (Higman, Gromov) transformed the original logical results into group theoretic results which exhibited useful algebraic structures. On set theory, he said that it's a new branch of advanced mathematics, but its impact on most older areas of mathematics is negligible. He concluded by saying that for a statement to "merely to involve sin, or polynomials, or a Ramsey Principle is no guarantee of relevance." It's "too soon to say" what the impact of Gödel's work on mathematics is.
• Georg Kreisel. Logical hygiene, foundations, and abstractions. Kreisel didn't have slides, so I had a bit of trouble following him. Well, it might just have been that it was Kreisel talking. He talked about foundations, Hilbert's program, consistency proofs as "purification rituals", etc. He did say two things which stuck in my head, though: a. He said that Gödel dictated the material on the second incompleteness theorem in Hilbert-Bernays, vol. 2, to Bernays -- so the derivability conditions are reall due to Gödel himself? and b. he said that Bernays told him, in the 70s, that he had asked Hilbert before his stroke in the 1920s whether he meant his [Hilbert's] claims about consistency to be taken literally. Hilbert, according to Kreisel, laughed, and said "Of course not. They are just to attract the attention of mathematicians."
• Ivor Grattan-Guinness. The Reception of Gödel's Work by Logicians and Mathematicians. Ivor gave a tour of general works (textbooks, popular expositions) of important figures up to the late 1950s whith an eye to who talked about Gödel's theorem. In the immediate vicinity of the results (the 1930s), he pointed to four striking examples of logicians who failed to mention Gödel's work, even though it would have been important and relevant to what they were doing: Hans Hahn, in a popular lecture in Vienna in the early 1930s, Quine in his System of logicistic of 1934, MacLane in his 1934 dissertation (written in Göttingen under Weyl in 19934, when Gentzen and Bernays were still there -- when asked, MacLane responded, "I did not mention the [incompleteness] theorems because noone told me about it" !), and Russell). He went on to talk about lots of other mathematicians and expositors -- the conclusion was that it took a good while until Gödel's theorems made it into mainstream expositions, that this was faster and more complete in the English-speaking world, and that the Bourbakis were especially guilty of not even mentioning Gödel's accomplishments in their work. Note to self: must look up Dubislav's 1931 review of Gödel's paper in the Jahrbuch fuer Fortschritte der Mathematik).
• Juliette Kennedy, Three Moments in the Philosophical Life of Kurt Gödel. The three moments were the remarks at the beginning of his dissertation, the 1964 supplement to "What is Cantor's continuum problem", and conversations from 1975 with Sue Toledo. The last one was especially interesting: Gödel and Toledo talked, among lots other things, about Plato's Eutyphro -- Juliette said that he noticed something that experts on ancient philosophy have missed, but then didn't get around to talking about that; I hope she'll tell me today what that was!
• Sol Feferman. Lieber Herr Bernays! Lieber Herr Gödel! Sol talked about the correspondence between Gödel and Bernays, starting with the first letter from 1930 requesting an offprint of the incompleteness paper, and spanning their respective careers, with emphasis on the question of what the reach of finitism is. Read the correspondence and Sol's introduction in the Collected Works, vol. 4. (Sol dedicated his lecture to the memory of Torkel Franzen.)
• Christos Papadimitriou. Computation and Intractability. Echoes of Kurt Gödel. Christos started with a bit of history on the influence of Gödel's work on the development of computation and complexity theory, including the letter to von Neumann where he anticipated the P =? NP problem. The second part of the talk was about some of Christos' recent work on complexity of games, specifically computation of Nash equilibria. Turns out that Nash's proof reduced the problem of the existence to Brouwer's fixed point theorem; Christos (and his students) give a reduction in the other direction -- and that requires constructing certain games which operate on real numbers, a sort of arithmetization. He also sang us a few bars from Bobby Darin's "Multiplication" and told us this funny story at the beginning of his talk: He started by saying "I don't know how many of you in the audience have actually talked to Gödel -- I have!" -- and went on to tell the story of his converstaion with Gödel: Christos was a graduate student at Princeton in the 70's. His office mate once left a note on his desk with his phone number and a second number, next to which was written "Gödel number". Since the number wasn't large enough to be the actual Gödel number of anything, Christos didn't quite know what to make of it, so he picked up the phone dialled it. An elderly gentleman answered, "Hello?" Christos replied, "Sorry, wrong number."
• B. Jack Copeland. From the Entscheidungsproblem to the Personal Computer. This was mainly a story about the development of electronic computers in Britain in the 40s and 50s -- the story of Turing, and Bletchley Park, Colossus, ACE, and the engineers behind their development, especially Tommy Flowers.

I forgot to write down all the good comments made by Dana Scott in discussion, sorry.

I skipped the last talk, but went back for the Young Scholars Competition, where the 10 finalists for the 20,000 EUR prize each gave super-stressful 10-minute talks. The finalists are: Lorenzo Carlucci, Andrey Bovykin, Lutz Strassburger, Laurentiu Leustean, Mark van Atten, Hannes Leitgeb, Itay Neeman, Justin Moore, Eli Ben-Sasson, and Russell O'Connor. They were all excellent! I'm rooting for Mark and Hannes, but if I had to place a bet, I guess I would go with Itay. We'll know tonight who the lucky winners are.

Proof-theoretic Semantics in Synthese

The February issue of Synthese is a special issue on proof-theoretic semantics, edited by Reinhard Kahle and Peter Schröder-Heister. It's papers from a conference in Tübingen in 1999.

• Dag Prawitz, Meaning Approached Via Proofs
• Peter Schroeder-Heister, Validity Concepts in Proof-theoretic Semantics
• Patrizio Contu, The Justification of the Logical Laws Revisited
• Lars Hallnäs, On the Proof-theoretic Foundation of General Definition Theory
• William W. Tait, Proof-theoretic Semantics for Classical Mathematics
• Göran Sundholm, Semantic Values for Natural Deduction Derivations
• Kosta Dosen, Models of Deduction
• Reinhard Kahle, A Proof-theoretic View of Necessity
• Gabriele Usberti, Towards a Semantics Based on the Notion of Justification
• Grigori Mints, Notes on Constructive Negation
• Michael Rathjen, Theories and Ordinals in Proof Theory

Uncertainty: Reasoning about probability and vagueness, Prague, Sept 5-8, 2006

Call for Papers:

Uncertainty: Reasoning about probability and vagueness

September 5 to 8, Prague

Uncertainty is a ubiquitous phenomenon in everyday life, but it is also a topic of fundamental significance to many scientific disciplines. Uncertainty taken here in a broad sense, has many facets - among them probability and vagueness, including possibility, confidence, fuzziness etc. These are captured by different theories which often seem to be conceptually and technically incompatible. Therefore there is no universally accepted theory covering all this area and there are many reasons why we shall neither expect nor want to have one. On the other hand there have been attempts to cross the borders - there are theories trying to bridge gaps between rival approaches and looking for their common background.

The aim of the conference is to provide a platform for an open discussion between proponents of the main theories of uncertainty and vagueness on the market. Special attention shall be paid to the comparison of theories, analyzing differences and similarities of the respective concepts of uncertainty. Of particular interest are logical aspects and formal models of reasoning about vague information.

The scope of interest contains, but is not limited to the following topics:

• reasoning under uncertainity
  
• theories of vagueness
  
• supervaluationism
  
• foundations of fuzzy logic
  
• concepts of probability
  
• possibility and trust
  
• epistemic and pragmatic aspects of uncertainty

The invited speakers of the colloquium: Patrick Greenough (St. Andrews), Rosanna Keefe (Sheffield), Peter Milne (Edinburgh), Richard Zach (Calgary).

The colloquium uses an abstract processing service kindly provided by Atlas Conferences Inc. If you are interested in presenting a paper, please submit an abstract at http://atlas-conferences.com/cgi-bin/abstract/submit/casu-01. Your submission will be confirmed automatically on the e-mail address you provide. The accepted abstracts will be available on-line after the final decision of the program committee. If you have any problems to submit an abstract, please contact us at colloquium@ flu.cas.cz.

The deadline for contributions is 6 June 2006, the notification of acceptance/rejection will be sent until 30 June 2006.

Programme committee: Didier Dubois, Christian Fermüller, Ondrej Majer, Peter Milne, Richard Zach.

The conference fee is EUR 150, it covers conference materials, coffee breaks and the banquet at Villa Lanna. Participants unable to pay the conference fee are encouraged to apply for a reduction. Those who wish to apply for the reduction should explicitly state this when submitting their abstract, which should be extended to 2-4 pages. The official language of the symposium is English.

The authors will be offered to submit the papers presented at the colloquium to a special issue of Studia Logica on vagueness and uncertainty (their publication will be subject to the journal's regular refereeing process). Details on the special issue will be distributed at a later point by its editors.

The workshop starts one day after the Studia Logica International Conference Towards Mathematical Philosophy in Torun; the participants can consider taking part in both conferences (the journey to Prague from Torun takes less than one day).

The Prague International Colloquium continues the series of annual international meetings on topics in logic, epistemology and analytic philosophy organized in Prague by the Department of Logic of the Institute
of Philosophy (see previous colloquia).

The official web page of the colloquium is http://www.flu.cas.cz/Logica/konf/col2006.html. All correspondence should be directed to colloquium@flu.cas.cz .

Ondrej Majer*, Libor Běhounek°, Petr Cintula°

Organising Committee

*Institute of Philosophy, °Institute of Computer Science,
Academy of Sciences of the Czech Republic

Torkel Franzén

Sad news: Torkel Franzén has died yesterday. I've known Torkel since my undergraduate days, when he was tirelessly setting people straight on logical and philosophical matters in the newsgroup sci.logic. He wrote two wonderful books, a technical book on incompleteness (Inexhaustibility: A Non-Exhaustive Treatment) and one on misconceptions and misuses of Gödel's Theorems. He will be missed.

Torkel Franzén, well known for his many Usenet posts, died of skeleton cancer at Wednesday, April 19, at the age of 56.

Torkel Franzén worked as a university lecturer at the department of Computer Science and Electrical Engineering, at Luleå University of Technology, Sweden. He taught programming courses, mostly using Java and Prolog. He earned his PhD in 2004. His thesis (in philosophy) was titled "Provability and Truth". He also wrote books, such as "Gödel's Theorem. An Incomplete Guide to Its Use and Abuse", which appeared in 2005.

Gödel's Theorem was indeed one of his major interests. He wrote many Usenet posts on this and related subjects, but he did also write posts on many other subjects.

Torkel's too early death is a great loss for his family, colleagues,
and Usenet friends.

Erland Gadde
Department of Mathematics
Luleå University of Technology
Sweden

See also Sol Feferman's post on FOM.

Incompleteness of Second-Order Logic

One of the corollaries that easily follow from Gödel's first incompleteness theorem for arithmetic is the incompleteness of second-order logic: there can be no proof system that generates all and only the validities of second-order logic. It follows from the incompleteness of arithmetic because for any sentences φ of first-order arithmetic, there is a sentence of second-order logic φ′ which is valid iff φ is true in the standard model. So if second-order logic was recursively enumerable (r.e.) then true arithmetic (the sentences true in the standard model) would be r.e. Now you may ask (and students regularly do ask): but what if Gödel's theorem had been false? What if arithmetic were complete? Would second-order logic then be complete, too? This question is usually not answered in the usual textbooks (at least I wasn't able to find it covered in the ones I looked). Now a conditional with a necessarily false antecedent is true, so "if arithmetic were complete, second-order logic would still be incomplete" is trivially true. But there's of course a way to give a non-trivial answer: There is no Turing machine that churns out all the valid sentences of second-order logic, even if that machine has access to an oracle which answers "yes" or "no" according to whether any given sentence of arithmetic is true in the standard model. (The function of such an oracle, of course, cannot itself be performed by a Turing machine, since the set of Gödel numbers of true arithmetic sentences is undecidable, and not even r.e.) That this is so is most easily seen by thinking of computability in terms of definability.

A set V of numbers is Σ⁰₁-definable if there is a Σ⁰₁ formula ψ(x) of arithmetic (one existential quantifier, then only bounded quantifiers) with a free variable x so that ψ(n) is true in the standard model iff n ∈ V. V is r.e. iff it is Σ⁰₁-definable. (In one direction: ψ(x) says "there is a number k which codes a computation of a Turing machine started on input l ≤ k and with output n.") If W is a set of numbers, we say that V is Σ⁰₁(W)-definable if there is a formula ψ(x, Y) with a second-order variable Y so that n ∈ V iff ψ(n, Y) is true in the standard model when Y is interpreted as the set W. V is enumerable by a Turing machine with access to an oracle for W iff it is Σ⁰₁(W)-definable.

If we let TA be the set of Gödel numbers of the true sentences of arithmetic and Val² the set of Gödel numbers of valid sentences of second-order logic, our question:

Is Val² enumerable by a Turing machine with an oracle for TA?

can be restated as:

Is Val²   Σ⁰₁(TA)-definable?

It isn't: the class {TA} is definable in arithmetic, that is, there is an arithmetical formula σ(Y) with a free second-order variable Y so that σ(Y) is true iff Y = TA (see Theorem 23.2 in Boolos, Burgess, Jeffrey, Computability and Logic, 4th ed.). So if Val² were Σ⁰₁(TA)-definable by some formula ψ(n, Y), it would then also be definable in second-order arithmetic by the formula ∃ Y(σ(Y) ∧ ψ(n, Y)). And if Val² were definable in second-order arithmetic, then TA², the set of Gödel numbers of true sentences of second-order arithmetic would be definable in second-order arithmetic, since the Gödel number of a sentence α of second-order arithmetical sentence is in TA² iff the Gödel number of P^II → α is in Val² (where P^II is the conjunction of the the second-order Peano axioms, as in Example 22.6 of BBJ). But by Tarski's Theorem, TA² is not definable in second-order arithmetic (see Theorem 41C of Enderton's A Mathematical Introduction to Logic).

Logic Conferences

A whole bunch of conference announcements came in over the Proof Theory and FOM lists the other day:

Logic Colloquium. July 27-August 2, Nijmegen, Netherlands. Submission deadline: April 17.

Workshop on Hybrid Logics. August 11, Seattle (part of FLoC). Submission deadline: May 26.

Computer Science Logic. September 25-29, Szeged, Hungary. Submission deadline: abstracts April 24, full papers May 1.

Congress on Tools for Teaching Logic. September 26-30, Salamanca, Spain. Submission deadline: May 15.

Conference on Logic, Navya-Nyaya, and Pallications. January 3-7, 2007, Calcutta, India. Submission deadline: August 31.

He Blinded Me With Science

Thomas Dolby has a blog. And so do the UConn philosophy grad students.

Kurt Gödel: The Album

Amazon.de emailed me today, suggesting that I preorder Kurt Gödel: The Album. There's not that much info on the amazon.de page, nor on the Vieweg page, but it's the book to accompany the exhibition the editors (Karl Sigmund, John Dawson and Kurt Mühlberger) are putting on for the Gödel Centenary in Vienna.

New Blog: Yarden Katz

Don't know how I missed this: Yarden Katz has a blog, CrunchyLogic.

Notices Issue on Gödel

The new issue of the Notices of the American Mathematical Society is devoted to Kurt Gödel's life and work.