Theoria Online (Including Back Issues!)

The venerable Swedish philosophy journal Theoria is published by Blackwell since this past March, and that means it is online, including the back issues. I’m not sure of the exact dates, but in the 70s, when Krister Segerberg was the editor-in-chief of that journal, Theoria was the place to publish modal logic and formal philosophy. Just go and browse the back issues, lots of interesting stuff there!

(The latest issue has a new paper by Kripke.)

Tarski on Gödel’s Theorem and the Deductive Method

One very common informal statement of Gödel’s theorem is that it shows that for any (sufficiently strong consistent blah blah) formal system, there are truths that it can’t prove. And if you don’t formulate Gödel’s incompleteness theorem that way, at least you state this as a corollary: Gödel’s theorem shows that truth and provability (in any one formal system) come apart. But if you read Gödel”s original paper(s) on incompleteness, you are probably struck by the fact that Gödel doesn’t say this. In fact, the word “wahr” doesn’t even appear in Gödel’s 1931 paper. I think Gödel doesn’t note this consequence until the 1934 Princeton lectures (p. 363 of Collected Works I). A number of reasons have been offered for this: a) he was reacting against Hilbert, so he wanted to keep everything purely finitary, b) he was working in the context of the Vienna Circle, and they considered “truth” to be a suspect, metaphysical notion. This is an aspect that people interested in Gödel’s platonism have written extensively about, since Gödel claimed that even at the time of writing the 1931 paper he was a platonist.

So who was the first to note this consequence in print? My money is on the guy who made truth respectable among the logical empiricists. Here’s the end of Tarski’s “Einige Betrachtungen über die Begriffe der ω-Widerspruchsfreiheit und der ω-Vollständigkeit“, Monatshefte für Mathematik und Physik 40 (1933) 97-112 (the paper was received in July 1932), translated as “Some observations on the concepts of ω-completeness and ω-consistency”, Logic, Semantics, Metamathematics, 2nd ed., pp. 279-295:

[T]he following is worthy of emphasis: the profound analysis of Gödel’s investigations shows that whenever we have undertaken a sharpening of the rules of inference, the facts, for the sake of which this sharpening was felt to be necessary, still persist, although in a more complicated logical structure. The formalized concept of consequence will, in extension, never coincide with the ordinary one, the consistency of that system will not prevent the possibility of ‘structural falsehood’. However liberally we interpret the concept of the deductive method, its essential feature has always been (at least hitherto) that in the construction of the system and in particular in the formulation of its rules of inference, use is made exclusively of general logical and structurally descriptive concepts. If now we wish to regard as the ideal of deductive science the construction of a system in which all the true statements (of the given language) and only such are contained, then this ideal unfortunately cannot be combined with the above view of the deductive method.

Now here’s something puzzling. The translation has a footnote to this passage which is not in the original:

The validity of the remarks stated in the last paragraph essentially depends on the decision not to use in metamathematical discussion any devices which cannot be formalized within the framework of the theory of types of Principia Mathematica. But as soon as we abandon this decision and allow ourselves to use stronger devices in metamathematical discussion, most of the remarks as originally formulated lose their validity and the whole paragraph requires a thorough revision.

What in the passage quoted depends for its validity on metamathematics being formalizable in PM? Maybe that if the metatheory is stronger than PM, you can define a “formalized notion of consequence” which characterizes the true statements of PM, e.g., using an ω rule. But Tarski just did that immediately before the quoted passage and says that the resulting formalized notion of consequence is not “in harmony with the current view of the deductive method”. So what can he have in mind here?

New Modal Logic Books

Update on my old post on modal logic textbooks: Two new modal logic books I have recently come across:

Anyone already read these and have an opinion? The Carnielli/Pizzi text looks especially interesting–and the full text is available online! (Not free, of course. It’s Springer, after all.)

I also noticed that a few classic books/collections of classical papers on modality are now online at Oxford Scholarship Online, including:

Logic and Category Theory

Since I’m hanging out with a bunch of category theorists every Wednesday, web finds with “category theory” in them keep attracting my attention. A couple of weeks ago, I came across this book draft posted on arXiv:

Atish Bagchi and Charles Wells, Graph-based Logic and Sketches

At first I thought, cool!, a new book on logic of diagrams or something. But then I read the abstract and intro, and it’s of course not about that at all. A sketch is a certain kind of graph that lets you define mathematical structures categorically. They were introduced by Charles Ehresmann. I’d links to an introduction on the web, but the only introductory thing I could find is a short paper by Wells. (The MacTutor biography of Ehresmann doesn’t even mention sketches…) So: still cool, but a lot harder for me to understand.

The other item was

Michael A. Shulman, Set theory for category theory

which ‘summarizes and compares a number of set-theoretic foundations for category theory, and describes their implications for the everyday use of category theory.’ More elementary, and I look forward to reading it. Alas, I don’t know when I’ll find the time.

Jobs for Logicians

Are you sitting in front of the computer, hitting the “reload” button every two seconds to see if the October Jobs for Philosophers is posted on the APA website yet? Why not check out the job that we have right here: Assistant Professor with AOS in Logic?

UPDATE: Hm, looks like there aren’t many logic jobs this year. Irvine has a TT logic job (223), UMD has a linguistics/logic (99), and a formal epistemology/logic/decision theory job (100). That’s it. BU (14), Yale (15), Stanford (232) list logic as one among several areas in the AOS.

Why is Every Σ1 Function a Composition of Two Δ0 Functions?

Today I taught Ch. 13 of Peter Smith‘s book. We showed that every Σ1 function can be written as a composition of two Δ0 functions (p. 108). In his proof of this, Peter’s following Boolos Burgess & Jeffrey (Lemma 16.12 on p. 206 of the 4th & 5th ed.; it’s not in the 3rd so I’m guessing it’s due to John Burgess). Until today I really didn’t understand why (as opposed to that) this works or how you’d come up with it. Peter calls it “clever trickery.” But standing up there at the blackboard I realized that there’s a way to think of it which makes it completely straight-forward—and which results (maybe?) in a simpler solution.

Suppose f is Σ1, i.e., there is a formula ∃z F(x, y, z) so that f(x) = y iff ∃z F(x, y, z) (in N). How close to Δ0 can you get? [NB: I’m using F instead of Peter’s R, and different variables, but I think it’s clearer this way.]

Note first of all that if f is total (as all functions are in Peter’s book), then for any x, there will be exactly one y so that ∃z F(x, y, z).

The ∃z is the problem, you want to put a bound on that. How far do you have to go to find z so that F(x, y, z) when y is the value of f(x), i.e., there is a z so that F(x, y, z)? Trivially, as far as

the least u so that ∃zu F(x, y, z).

But that function still depends on y; obviously you can’t really bound z by it. You’d like the bound to be a function of x only. Well, we can put in a quantifier to get rid of the free y. Naturally you want a bounded quantifier and the obvious bound is u:

g(x) = the least u so that ∃yuzu F(x, y, z)

If f is total, then for any x, there is such a u, so g is total.

g(x) might be further than you have to go to find a witness for the ∃z, but that’s ok. And it’s a Δ0 function since

g(x) = u iff ∃yuzu F(x, y, z) ∧ ∀v≤u (∃y≤vz≤v F(x, y, z) → u = v)

So f(x) = y iff ∃z≤g(x) F(x, y, z). Let’s see if the formula we get by removing the g(x) defines a function:

h(x, u) = y iff ∃z≤u F(x, y, z)

For any pair x, u, there’s at most one y with ∃z≤u F(x, y, z), since for any x there’s at most one y with ∃z F(x, y, z). Hence, h is functional. It might not be total, since for some pairs x, u (in particular u less than g(x)) there might not be a z≤u with F(x, y, z). So let’s fix that:

h(x, u) = y iff ∃z≤u F(x, y, z) ∨ (¬∃z≤u F(x, y, z) ∧ y = 0)

Now we have that f(x) = h(x, g(x)) since the only cases where h(x, u) might be different from f(x) are those where h(x, u) = 0 because u is less than g(x).

My definition of h is a bit simpler than John and Peter’s: they have “the least yu” where I just have “the y“. Did I overlook some subtlety?

CfP: Computability in Europe 2009

NB: History and philosophy of computation explicitly part of the scope. Note also the philosophers on the program committee and the special session on philosophical and mathematical aspects of hypercomputation.

Mathematical Theory and Computational Practice
Heidelberg, Germany
19 – 24 July 2009

Deadline for submissions: 20 JANUARY, 2009

CiE 2009 is the fifth in a series of conferences organised by CiE (Computability in Europe), a European association of mathematicians, logicians, computer scientists, philosophers, physicists and others interested in new developments in computability and their underlying significance for the real world. Previous meetings took place in Amsterdam (2005), Swansea (2006), Siena (2007) and Athens (2008).

TUTORIALS: Pavel Pudlak, Luca Trevisan.

INVITED SPEAKERS: Manindra Agrawal, Jeremy Avigad, Phokion Kolaitis, Peter Koepke, Andrea Sorbi, Vijay Vazirani.

SPECIAL SESSIONS on Algorithmic Randomness (E. Mayordomo, W. Merkle), Computational Model Theory (J. Knight, A. Morozov), Computation in Biological Systems – Theory and Practice (A. Carbone, E. Csuhaj-Varju), Optimization and Approximation (M. Halldorsson, G. Reinelt), Philosophical and Mathematical Aspects of Hypercomputation (J. Ladyman, P. Welch), Relative Computability (R. Downey, A. Soskova)

CiE 2009 has a broad scope and bridges the gap from the theoretical methods of mathematical and meta-mathematical flavour to the applied and industrial questions of computational practice. The conference aims to bring together researchers who want to explore the historical and philosophical aspects of the field.

We particularly invite papers that build bridges between different parts of the research community. Since women are underrepresented in mathematics and computer science, we emphatically encourage submissions by female authors. The Elsevier Foundation is supporting the CiE conference series in the programme “Increasing representation of female researchers in the computability community”. This programme will allow us to fund child-care support, a mentoring system for young female researchers, and also a small number of grants for female researchers, covering their registration fees.

The dates around the submission process are as follows:

Submission Deadline: 20 January 2009
Notification of Authors: 16 March 2009
Deadline for Final Version: 17 April 2009

CiE 2009 conference topics include, but not exclusively:

  • Admissible sets
  • Analog computation
  • Artificial intelligence
  • Automata theory
  • Classical computability and degree structures
  • Computability theoretic aspects of programs
  • Computable analysis and real computation
  • Computable structures and models
  • Computational and proof complexity
  • Computational complexity
  • Computational learning and complexity
  • Concurrency and distributed computation
  • Constructive mathematics
  • Cryptographic complexity
  • Decidability of theories
  • Derandomization
  • Domain theory and computability
  • Dynamical systems and computational models
  • Effective descriptive set theory
  • Finite model theory
  • Formal aspects of program analysis
  • Formal methods
  • Foundations of computer science
  • Games
  • Generalized recursion theory
  • History of computation
  • Hybrid systems
  • Higher type computability
  • Hypercomputational models
  • Infinite time Turing machines
  • Kolmogorov complexity
  • Lambda and combinatory calculi
  • L-systems and membrane computation
  • Mathematical models of emergence
  • Molecular computation
  • Natural computing
  • Neural nets and connectionist models
  • Philosophy of science and computation
  • Physics and computability
  • Probabilistic systems
  • Process algebra
  • Programming language semantics
  • Proof mining
  • Proof theory and computability
  • Quantum computing and complexity
  • Randomness
  • Reducibilities and relative computation
  • Relativistic computation
  • Reverse mathematics
  • Swarm intelligence
  • Type systems and type theory
  • Uncertain reasoning
  • Weak arithmetics and applications

Contributed papers will be selected from submissions received by the PROGRAMME COMMITTEE consisting of:

Klaus Ambos-Spies (Heidelberg, co-chair), Giorgio Ausiello (Rome), Andrej Bauer (Ljubljana), Arnold Beckmann (Swansea), Olivier Bournez (Nancy), Vasco Brattka (Cape Town), Barry Cooper (Leeds), Anuj Dawar (Cambridge), Jacques Duparc (Lausanne), Pascal Hitzler (Karlsruhe), Rosalie Iemhoff (Utrecht), Margarita Korovina (Siegen/Novosibirsk), Hannes Leitgeb (Bristol), Daniel Leivant (Bloomington), Benedikt Loewe (Amsterdam), Giancarlo Mauri (Milan), Elvira Mayordomo (Zaragoza), Wolfgang Merkle (Heidelberg, co-chair), Andrei Morozov (Novosibirsk), Dag Normann (Oslo), Isabel Oitavem (Lisbon), Luke Ong (Oxford), Martin Otto (Darmstadt), Prakash Panangaden (Montreal), Ivan Soskov (Sofia), Viggo Stoltenberg-Hansen (Uppsala), Peter van Emde Boas (Amsterdam), Jan van Leeuwen (Utrecht), Philip Welch (Bristol), Richard Zach (Calgary)

The Programme Committee cordially invites all researchers in the area of the conference to submit their papers (in PDF-format, at most 10 pages) for presentation at CiE 2009.

The best of the accepted papers will be published in the conference proceedings within the Lecture Notes in Computer Science (LNCS) series of Springer, which will be available at the conference. Authors of accepted papers are expected to present their work at the conference. Submitted papers must describe work not previously published, and they must neither be accepted nor under review at a journal or at another conference with refereed proceedings.

All papers need to be prepared in LNCS-style LaTeX. Papers should not exceed 10 pages; full proofs may appear in a technical appendix which will be read at the reviewers’ discretion. The title page must contain: title and authors; physical and e-mail addresses; identification of corresponding author, if not the first author; an abstract of no more than 200 words; a list of keywords.

Submissions authored or co-authored by members of the Programme Committee are not allowed.

Blog Changes

So I got fed up with Bloglines one time too many, and I switched to Google Reader. It maybe it’s just that I’m still getting used to it, but I find the user interface of Bloglines a bit more intuitive. And it has served me well for years. Wait–Why do I feel bad about switching feed readers? Anyway. Google Reader has this “shared item” thingy where you can mark posts as you read them and Google Reader will put them on a separate (public) page. So instead of writing a post pointing to someone else’s post, I can now just put it in the “Elsewhere” box to the left. You can’t see that box if you’re reading this blog through a reader, and chances are you’re subscribed to many or most of the blogs in my blogroll anyway. But if you really care a lot about which other posts I find interesting but can’t bring myself to post about because I wouldn’t have any thing more to say than “look over there!”–then you can subscribe to the feed.

Hájek/Pudlák for Cheap

If you’re a member of the ASL,* you recently received the September Newsletter. In it–maybe easy to miss–this nice opportunity to acquire some logic books for cheap:

For a limited time, the ASL is making available the following volumes from its book series at an additional discount.

Lecture Notes in Logic (each volume $12 for ASL members, $16 for non-members): LNL vol. 11, Logic Colloquium ’95; Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Haifa, Israel, August 9-18, 1995; LNL vol. 12, Logic Colloquium ’96; Proceedings of the Colloquium held in San Sebastian, Spain, July 9-15, 1996.

Perspectives in Logic (each volume $18 for ASL members, $24 for non-members): Essential Stability Theory by S. Buechler; Metamathematics of First Order Arithmetic by P. Hajek and P. Pudlak.

To order these specially discounted volumes, contact the ASL Business Office: ASL, Box 742, Vassar College, 124 Raymond Avenue, Poughkeepsie, New York 12604, USA; Tel: 1-845-437-7080; Fax: 1-845-437-7830; email:

There are more discounts available, including on subscriptions to History and Philosophy of Logic, Philosophia Mathematica, Studia Logica.

* You’re not? Shame on you. Go here to join.

Belnap, Art and Science of Logic

From Theorem(e):

Nuel Belnap now has two logic texbook drafts on his webpage :

Notes on the Art of Logic (.pdf, 310 p.)
Notes on the Science of Logic (.pdf, 237p.)

The first is an intro to logic, with truth table method, natural deduction proofs, etc., the second a course on metalogic, with completeness proofs.

I did mention it a short while ago, but there it may easily have been missed, and it’s a wonderful resource: Henri Galinon has a page with links to logic texts available online.

Effective finite-valued approximations of general propositional logics

Baaz, Matthias, and Richard Zach. 2008. “Effective Finite-Valued Approximations of General Propositional Logics.” In Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, edited by Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich, 107–29. LNCS 4800. Berlin: Springer. DOI:10.1007/978-3-540-78127-1_7

Propositional logics in general, considered as a set of sentences, can be undecidable even if they have “nice” representations, e.g., are given by a calculus. Even decidable propositional logics can be computationally complex (e.g., already intuitionistic logic is PSPACE-complete). On the other hand, finite-valued logics are computationally relatively simple—at worst NP. Moreover, finite-valued semantics are simple, and general methods for theorem proving exist. This raises the question to what extent and under what circumstances propositional logics represented in various ways can be approximated by finite-valued logics. It is shown that the minimal m-valued logic for  which a given calculus is strongly sound can be calculated. It is also investigated under which conditions propositional logics can be characterized as the intersection of (effectively given) sequences of finite-valued logics.

Continue reading