Logblog: Richard Zach's Logic Blog

University of Calgary

UofC Navigation

Submitted by Richard Zach on Wed, 07/19/2006 - 7:49am

Ever tried reading logical texts from the 20s or before (e.g., C. I. Lewis's Symbolic Logic)? Confused by the absence of parentheses and all the dots and colons? Here's Carnap's explanation of the notation (from Abriss der Logistik):

4 c. The Dot RulesThe dot symbols (. : :. :: etc.) replace the bracketing of propositions. The dot signs fall into three distinct levels, depending on whether they occur

- between two propositions in a conjunction,
- after an operator (x), (? x), [(?x)(?x)],
- after |-, before and after the sign ?, ? ?, |, =
_{Df}.Dot rules for reading: The scope of a dot symbol (for 1, to the left and to the right, for 2 to the right, for 3 to left or right, depending) extends either to the end of the proposition or to a dot symbol with more dots or to a symbol of the same or a higher level with the same number of dots.

Dot rules for writing: If the scope of a dot sybol is to extend beyond that of another, it must, if it is of a higher level than the latter, contain at least as many dots, and otherwise more dots.

Examples:

p ? . q . r means p ? (q . r) |- : (p, q) : p ? q . ? . q ? p " |- {(p, q) . [(p ? q) ? (q ? p)]} p : ? : q . ? . q ? p " p ? [q ? (q ? p)] (x) . ?x . ? . p ? q " [(x) . ?x] ? (p ? q) (x) : ?x . ? . p ? q " (x) . [?x ? (p ? q)] (x) : ?x ? p . ? q " (x) . [(?x ? p) ? q] (x) : ?x ? p : ? q " [(x) . (?x ? p)] ? q

Submitted by Richard Zach on Wed, 07/19/2006 - 7:41am

50 years ago this summer, McCarthy, Minsky, Rochester, and Shannon organized a summer conference at Dartmouth which turned out to be a milestone in Artificial Intelligence research. For the logically minded, this item in the funding proposal to the Rockefeller Foundation is perhaps most interesting:

4.

Theory of the Size of a CalculationIf we are given a well-defined problem (one for which it is possible to test mechanically whether or not a proposed answer is a valid answer) one way of solving it is to try all possible answers in order. This method is inefficient, and to exclude it one must have some criterion for efficiency of calculation. Some consideration will show that to get a measure of the efficiency of a calculation it is necessary to have on hand a method of measuring the complexity of calculating devices which in turn can be done if one has a theory of the complexity of functions. Some partial results on this problem have been obtained by Shannon, and also by McCarthy.

Submitted by Richard Zach on Mon, 07/10/2006 - 2:25pm

Last week I had the pleasure of attending the Computability in Europe conference in the lovely seaside town of Swansea, Wales. Lots of interesting talks on all kinds of aspects of computation, including a number of talks on the (limits of) hypercomputation, a tutorial on proof complexity by Sam Buss, and special sessions on Gödel's legacy for computability theory with talks by Arnon Avron, John Dawson, Andrew Hodges, and Wilfried Sieg. I won't talk about the details--the abstracts are up on the website, the slides for many of the talks should be up very soon, and the proceedings volumes (invited, contributed [big PDF!] talks) are online as well.

Oh, and this guy stopped by to visit the building across from the conference site:

I also had an enjoyable bus ride back to Heathrow with Bob Meyer, talking about relevant logic and the epsilon calculus.

Submitted by Richard Zach on Thu, 06/29/2006 - 12:46pm

Reading over my previous post, I was wondering if a group of scholars can be referred to as a "gaggle". So I did some research (i.e., I asked google) and happened upon this wiki page, which lists the appropriate collective noun for logicians as "sequitur", and attributes this to Bertrand Russell. Anyone got a reference for this? (It doesn't list a special collective noun for scholars, though--maybe "a school of scholars" would be appropriate?)

UPDATE: The wikipedia page for Quine has him saying it, but maybe he got it from Russell?

Submitted by Richard Zach on Thu, 06/29/2006 - 6:34am

I mentioned it in comments on the other post already, but I thought of a few solutions to my question: how do you keep a gaggle of scholars jointly working on a publication project organized? They are outlined in a wiki page. Comments welcome (you can edit the wiki, of course, or write something on the talk page).

Submitted by Richard Zach on Thu, 06/29/2006 - 6:28am

Greg is reporting from the Realism/Anti-Realism Workshop in Nancy, and Yarden from the CMU Summer School in Logic. Stay tuned for reports from Computability in Europe next week from yours truly.

Submitted by Richard Zach on Fri, 06/23/2006 - 12:58pm

Friendster reminded me that today is Alan Turing's birthday.

Submitted by Richard Zach on Thu, 06/22/2006 - 12:59pm

If you've ever coauthored a paper, you know what a hassle it is to send versions back and forth, keep track of changes, avoid conflicts when you're simultaneously changing things, and so on. Now software engineers have the same problems when working on large development projects and have developed very sophisticated Revision Control Systems. I've used the most well-known of these, CVS, for collaborating on a couple of papers. But CVS is not exactly easy to use, and for a larger project with more people who all use different systems (Linux, Mac, Windows) and who aren't as geeky as I, CVS is not a good choice. So: I'm looking for an easy way to collaborate on editing text documents. It should work cross-platform, it should have version control (keeping track of changes, ways of telling what parts of a document were edited by whom and when, reverting to previous versions), it should be easy to use (graphical user interface), it should be easy to install (preferably it should be completely distributed with the client programs doing all the work). It doesn't have to have fancy security, support for branching and merging projects, include a build environment, and all the other stuff that's important to programmers. I also don't want to have to set up a server or persuade my university's IT people to give accounts to my collaborators. Anyone have any ideas?

Submitted by Richard Zach on Thu, 06/22/2006 - 12:50pm

On June 22, 1936, Moritz Schlick, influential philosopher and center of the Vienna Circle of logical empiricists, was gunned down on the steps of the University of Vienna. The Institute Vienna Circle is holding a small memorial event at the University of Vienna today, which will include the presentation of the first two volumes of Schlick's Collected Works.

Submitted by Richard Zach on Wed, 06/21/2006 - 2:05pm

There will be two interesting workshops following GAP 6 in Berlin (September 14 & 15): one on Carnap, and one with the promising title "Towards a New Epistemology of Mathematics".

Submitted by Richard Zach on Thu, 06/15/2006 - 5:13pm

I'm at HOPOS, which is loads of fun. All my history of analytic/history of logic buddies are here. But more to the point:

Paolo Mancosu just gave the most amazing talk about the debate within the Vienna Circle about Tarski's theory of truth, in particular, the opposition that Neurath had voiced against it from the mid 1930s onward. I had always thought that the Vienna Circle wholeheartedly accepted Tarski's theory, and that Tarski's paper made truth an "acceptable" notion (from a logical empiricist standpoint). What Paolo showed, using correspondence between Carnap, Neurath, Tarski and others from 1935 and later, was that there was a debate raging over it. Neurath was opposed not, as one might suppose, because of the set theoretic metalanguage in which Tarski's theory was couched, but because he feared that people would use Tarski's theory in areas where it wasn't applicable, i.e., in non-formalized languages, and that it would lead people to return to "metaphysics". (I guess, that has actually happened decades later in the whole thing about deflationary conceptions of truth!) Moreover, we now know why no-one is aware about the tensions within the Vienna Circle around the theory of truth: at the Congrès Descartes in Paris in 1937, there was a private meeting with Carnap, Tarski, Neurath, Naess, Lutman-Kokoszynska, Hempel, and others where the proponents and opponents of Tarski's theory put forward their arguments. It was agreed (or, decreed by Carnap) that noone was to bring up the differences within the Circle regarding this issue in print.

Paolo's talk was followed by Johannes Hafner on the origins of model theory in Hilbert and Tarski. Johannes' main point was that whereas Tarski's notion of interpretation of an axiom system was a lot clearer about the syntax of the language (precise recursive definition of syntax in meta-language), Hilbert's notion of interpretation was a lot closer to the modern one--Tarski's notion of truth in the 1935 paper did not allow for varying domains. It wasn't until the 1950s in Tarski's and Vaught's work on model theory that the modern notion of truth in a structure emerged.

Submitted by Richard Zach on Wed, 06/07/2006 - 5:28pm

Peter has posted a new version of the first 22 chapters of his Gödel Book.

Submitted by Richard Zach on Thu, 06/01/2006 - 9:39pm

The new issue of Philosophia Mathematica is devoted to Gödel. There are essays by Sol Feferman, Peter Koellner, Wilfried Sieg, Bill Tait, Rick Tieszen, and Mark van Atten, as well as a review of Torkel Franzén's *Gödel's Theorem: An Incomplete Guide to its Use and Abuse.*

Submitted by Richard Zach on Thu, 06/01/2006 - 5:11pm

After a week in Singapore and a week in Melbourne, I'm back in cold and rainy Vienna, nursing a cold and trying to finish two papers. Thanks to John and Belle, who I got to hang out with in Singapore, and to Allen, Conrad, Graham, Greg, Kate, Maren, Tama, and Zach for making it a thoroughly enjoyable visit to Melbourne.

Submitted by Richard Zach on Sat, 05/13/2006 - 3:04pm

A few more upcoming conferences marking Gödel's 100th birthday:

- The Annual Meeting of the ASL in Montreal next week will include a Special Gödel Symposium featuring Jeremy Avigad, Steve Awodey, Bill Tait, John Burgess, Akihiro Kanamori, and Sy Friedman.
- The Dutch Graduate School in Logic is putting on a Gödel Centenary Celebration in Utrecht, on May 26. The speakers are Mark van Atten, Dennis Dieks, Dick de Jongh, Juliette Kennedy, Benedikt Löwe, and Albert Visser.
- The Logic Colloquium in Nijmegen will include a 2-hour plenary discussion on the legacy of Kurt Gödel on August 2.

Submitted by Richard Zach on Fri, 05/12/2006 - 5:43pm

I was talking to a friend of mine who works at the Technisches Museum Vienna the other day about Enigma and Colossus, since I had just heard Jack Copeland's talk at the Gödel Centennial about the history of Colossus. So I did some Googling and found some interesting books which I should get: *Action This Day*, edited by Michael Smith and Ralph Erskine (2001), about code breaking at Bletchley Park; and the new *Colossus. The Secrets of Bletchley Park's Code-breaking Computers*, edited by Jack Copeland (2006).

Other things which Google spat out:

- A review of
*Action This Day*from the CIA. - Wikipedia entries on Tommy Flowers, who built Colossus; Tunny, the coding machine Colossus was used against; and an entry on the cryptanalysis of Enigma.
- An article on Colossus by Copeland.

Submitted by Richard Zach on Fri, 05/05/2006 - 3:45pm

On Saturday, I unfortunately missed Ulrich Kohlenbach's talk, since the banquet the night before went a little long and I overslept. That was a pity, since I really like and admire his work. The second talk was by Harvey Friedman, "My 40 Years on His Shoulders". He as the title suggests, he gave a survey of his work on finding mathematically "natural" or "interesting" statements which are independent of strong theories. The three areas he focussed on was the theory of well quasi-orders (Kruskal's theorem, the graph minor theorem), Borel selection theory, and Boolean relation theory. If you've followed Harvey's posts on FOM, this was familiar territory. It was too bad that there wasn't more of a Friedman-MacIntyre discussion at the end. Then came the session on set theory: first, Paul Cohen reminisced about how he proved the independence of CH and his relationship to Gödel. He related how his interest in number theory as a graduate student at Chicago led him to think about developing a decision procedure for Diophantine equations. His colleagues there mentioned that what he tried to do onflicted with results of a certain Gödel--and this was confirmed by Kleene, when he gave a talk at Chicago during that time. This led Cohen to read Gödel's paper. He mentioned the story that circulates about how he [Cohen] allegedly asked Hartley Rogers in Princeton around 1958 what the hardest open problem in logic was, and that Rogers said it was the independence of CH--which Cohen then set to prove. Cohen said it rings a dim bell, but even if it hadn't happend the way it's been told, it would still continue to be told that way, because it's a good story. In any case, he attempted to read the Princeton monograph on the consistency of CH, but said he didn't understand it. He also said that he once asked Gödel if he had proved the independence of AC, and that Gödel had said, yes. Asked by what method, Gödel replied, "Well, it was somewhat similar to yours." At that time, Cohen reported, Gödel already seemed quite exhausted, and never wanted to talk about details of proofs. Cohen did want to debunk one claim made about him: that he at one point attempted to show that arithmetic was inconsistent (claimed, e.g., by Anil Nerode here)--he tried to find a decision procedure for Diophantine equations, which there isn't (see above). Dana Scott was up next. He gave an explanation for why Gödel's Princeton monograph is so hard to read: According to Kreisel, Gödel began the lectures upon which the monograph was based with a longish introduction where he explained the idea of the proof--but the notetaker though it was just chit chat and didn't write it down! Scott's talk was technical, on parametric sets and geometry, and I didn't quite follow it, I must admit. The third talk in the set theory session was Hugh Woodin on the large cardinal program. That was exciting and interesting, but I don't trust my notes enough to confidently report what he said. I think I've heard him give something like it at Berkeley already, so maybe there's a written version of it somewhere? In any case, here's a way to get a job in the Berkeley math department: Hugh bet that in the next 10,000 years no-one will prove ZFC + "there are infinitely many Woodin cardinals" inconsistent. If he loses, he will resign his job and insist that whever finds the contradiction be appointed in his place. In the afternoon, Avi Wigderson gave a talk on complexity, randomness, and game theory. It's up at his website. The last event of the meeting was Roger Penrose's public lecture at City Hall. The place was packed--probably 600 people or more. Since it was aimed at a general audience, there wasn't much detail. As far as I could tell, there wasn't that much new, either. Funnily enough, he seemed not to remember his own argument against strong AI using Gödel's theorems. Penrose's talk was followed by a screening of Jimmy Schimanovich and Peter Weibel's movie about Gödel's life and work, "Kurt Gödel--Ein mathematischer Mythos." The End.

Submitted by Richard Zach on Tue, 05/02/2006 - 6:20pm

Four interesting papers by Phillip Wadler:

- The unreasonable effectiveness of logic
- As Natural as 0,1,2
- From Frege to Gosling: 19'th century logic and 21'st century programming languages
- Proofs are Programs: 19th Century Logic and 21st Century Computing

available on his history of logic and programming languages page. (Hat tip: Lambda the Ultimate)