Year: 2013

An open problem about Rosser sentences?

Gödel's theorems, Logic / 4 Comments / May 24, 2013

Fix on a provability predicate Prov for a suitable theory T (there’s a lot of choices to make here, starting of course with a choice of Gödel coding). Then any Gödel sentence in the sense of a fixed point for Prov is provably equivalent in T to the consistency sentence not-Prov(0=1). So these Gödel sentences are all equivalent. That’s all familiar.

Now Rosserize the provability predicate in the usual way, and consider Rosser sentences, meaning fixed points for this doctored predicate. The question was recently asked on math.stackexchange: are these Rosser sentences also provably equivalent with each other?

I knew there was a relevant paper by D. Guaspari and R. Solovay, ‘Rosser Sentences’, Annals of Math. Logic vol 16 (1979), pp. 81-99. And their key relevant result about Rosser sentences is this. There are some ‘standard’ provability predicates whose Rosser sentences are all equivalent, and there are other ‘standard’ provability predicates whose Rosser sentences are not all equivalent. (Being standard is a matter of satsifying two of the usual derivability conditions.)

The proofs of these results need quite a bit of apparatus: and the authors remark that the situation with respect to the “usual” provability predicate constructed in the normal way without fancy tweaking “seems to be very difficult” and is [or rather was at that time of publication, 1979] unsettled. But is the question still unsettled?

Well, I note that in Buss’s Handbook of Proof Theory (1998), p. 496, it is still reported as an open question whether there is a reasonable notion of “usual” provability predicate for which it can be settled whether or not all Rosser sentences for such a predicate are equivalent. It is interesting that the problem should be this intractable. I just don’t know whether there is any more recent work which sheds further light. Any offers?

Revisiting an old result of Hintikka’s

Logic / 2 Comments / June 1, 2013

The pedagogic habit dies very hard. In recent months I’ve been hanging out quite a bit at math.stackexchange.com, and answering logicky questions when the mood has taken me (which seems to have been quite often …). You can find over 250 (oops!) of my answers here. But a lot of them are really concerned with baby logic and/or clearing up horrible confusions and won’t be of any interest at all to readers of Logic Matters.

However, a few questions on math.stackexchange have raised more interesting issues, and I’m going to start occasionally posting about some of them here. For example, recently someone posed a question which came to this:

Can we do without equality in first order logic, and get something equally expressive using a language with the semantics for quantifiers tweaked so that different variables get assigned different values?

Unbeknownst to the questioner, who conjectured (on the basis of some examples) that the answer is ‘yes’, the proposal here in fact goes back to Wittgenstein’s Tractatus 5.53, where he writes, ‘Identity of the object I express by identity of the sign and not by means of a sign of identity. Difference of the objects by difference of the signs.’ OK: can this proposal, not really developed out by Wittgenstein, be made to work?

The answer is it that it can, as I recalled was shown by Hintikka in 1956 (‘Identity, Variables, and Impredicative Definitions’, Journal of Symbolic Logic). Hintikka distinguishes the usual ‘inclusive’ reading of the variables (i.e. we are allowed to assign the same object to distinct variables) from the ‘exclusive’ reading, and then proves the key theorem (summarized on his p. 235):

[E]verything expressible in terms of the inclusive quantifiers and identity may also be expressed by means of the weakly exclusive quantifiers without using a special symbol for identity.

So the questioner’s conjecture is right. This result is nice and probably deserves to be better known, but what was new to me — googling around as you then do — is that Hintikka’s result has of late been revisited (in the context of the seemingly never-ending project of interpreting the Tractatus, of course). See for example. Kai F. Wehmeier’s interesting ‘How to Live without Identity – And Why’, Australasian Journal of Philosophy, 2012, downloadable here.

 

The consistency of NF: meeting in Cambridge

This and that / 1 Comment / April 25, 2013

Back in October, I posted a slightly mysterious message noting that Thomas Forster was “in the process of assembling funding for a meeting to discuss and broadcast recent developments in NF” here in Cambridge this Easter. Then in November I was able to reveal more, for Randall Holmes had by then announced “I believe that I am in possession of a fairly accurate outline of a proof of the consistency of New Foundations” and it was this which was to be the topic of the Easter gathering. So: how did the meeting go? For various reasons, I wasn’t there, but here’s a report from Thomas Forster:

It went very well.  It didn’t achieve everything I dreamed of, in that I didn’t come away from the meeting understanding the proof — not entirely.  I understand the strategy and I can see why the strategy should work, but I am a long way from understanding the details.

It involves a Ramsey argument like that used by Randall in his ‘tangled types’ paper (which reduces the consistency problem for NF to the task of finding a model of ZFU with some very delicate combinatorial properties).  It then uses an iterated Fraenkel-Mostowski construction to obtain the desired model of ZFU.

My Ph.D. students and I have a weekly meeting in which we press on with “our exagmination round his factification”.  Meanwhile people ask “Do you believe the proof?” and my reply is  “Not yet, but I believe that I will believe it”.  It is a very large proof.  When written out properly it will be 50-60 pages – possibly more — and certainly not 10-15.

Randall is rejigging the presentation in the light of the audience reaction in Cambridge; there is a cunning plan to get one of the theorem-proving communities to embark on a mechanisation  … and the lads and I have a project to write out a version for our own satisfaction.

I expect that by the end of this year I will understand it, and Randall will have sent off a paper to the JSL.

TYL, #15. A major update to the Guide

Study Guide / 11 Comments / March 31, 2013

The new April version of the Teach Yourself Logic Guide is now available for downloading. This is re-organized and half as long again as the previous version. After the Introduction there is a short new Chapter 1 on Logical Geography saying more about how the field of logic (and hence the Guide) can be carved up. Chapter 2 on The Basics is much as it was. But Chapter 3, Exploring Further, is much expanded and (at least to a first approximation) a complete draft: there are over a dozen new pages here. The chapter of a rather different character reviewing some of the Big Books now comes at the end, as an Appendix, but is otherwise unchanged in this version.

Most of the new sections of Chapter 3 are not only new to the Guide but haven’t appeared in draft form here on the blog either. So comments, corrections and suggestions will be particularly welcome, either below or by email.

Imogen Cooper plays Schubert, again

Music / Leave a Comment / March 31, 2013

I have written here before about Imogen Cooper’s Schubert playing, and in particular about the wonderful series of three double-CDs from live concerts, released some three or more years ago. Well, on Wednesday we had the chance to hear her playing an all-Schubert programme at the Wigmore Hall: a stunning evening.

She began with the 16 German Dances D783, played with even more alternating zest and poignant grace than in those live recordings. What was she saying? That even in these miniatures, there is so much humanity? And then the three Klavierstücke, played as well as I have heard them. The Guardian reviewer wrote “the seriousness with which the Drei Klavierstücke D946 were treated created something as substantial and searching as any sonata”: well, yes, but it isn’t somehow optional, a matter of creative license, to treat these late pieces “seriously” — they are substantial and searching, and Imogen Cooper’s was a true response.

After the interval, the six Moments Musicaux D780, again played with perhaps even more emotional contrasts than on the live recording — the fifth Allegro Vivace really attacked, and the sixth Allegretto magically poised and ending with perfect calm (‘over-leisurely’ playing according to the Guardian — no!). Finally, the great G major Sonata D894. I’m not sure if we were too drained from what went before, or whether Imogen Cooper had herself given too much, but this was the one performance that seemed less wonderfully successful than the recorded version — but it was still astonishing, with quite magical episodes. The audience response was rightly rapturous.

One of the great concerts to remember then.  I’ve been listening again to those earlier performances on the live CDs. If you don’t have them, then you are missing some of the greatest Schubert playing of our age, of any age.

IGT2 … and now available as an ebook

Gödel's theorems / Leave a Comment / March 17, 2013

IGT2 is now available from here as an ebook (don’t ask me why it should be a trifle more expensive that the UK paperback … publishers’ pricing policies for e-editions generally is a mystery). Anyway, according to info on the site, with the appropriate app, the Abobe ebook works on iPad and Android tablets, Kindle Fire, Windows, Mac and Linux computers, and any other device that will run Adobe Digital Editions.

I’ll be interested to hear from anyone who buys this version about how well the e-version has been done. I assume it should be pretty closely related to the PDF I sent for printing. I originally sent the publishers a version with internal live-links (for cross-references) so I hope those have been preserved.

Anyway, for all you who desperately want to be able to read IGT2 any time, any place, when you have your iPad, MacBook Air, or some lesser device to hand (and why wouldn’t you?), your dearest wish has now been granted …

TYL, #14. Alternative set theories

Study Guide / 10 Comments / March 18, 2013

I’ve been doing quite a bit of work over the last couple of weeks for a major April update of the Teach Yourself Logic Guide (you can download the current March version here). And I’ve got to a subsection where I could do with advice and comments. I’m working on a new section on more advanced readings on set theory. The subsection on ZFC with all the bells and whistles (large cardinals, forcing, and other excitements) writes itself, and there’s a shorter subsection on the Axiom of Choice. But now I’m drafting a subsection on Alternative Set Theories. Here’s what I have so far written:

From earlier reading you should have picked up the idea that, although ZFC is the canonical modern set theory, there are other theories on the market. I will mention just six(!) here, which I find interesting:

SP This is by way of reminder: earlier in the Guide, we very warmly recommended

  • Michael Potter, Set Theory and Its Philosophy (OUP 2004).

This presents a version of an axiomatization of set theory due to Dana Scott — hence Scott-Potter set theory. This axiomatization  is consciously guided by the conception of the set theoretic universe as built up in levels (the conception that, supposedly, also warrants the axioms of ZF). What Potter’s book aims to reveal is that we can get a rich hierarchy of sets, more than enough for mathematical purposes, without committing ourselves to all of ZFC. If you haven’t read Potter’s book before, now is the time to look at it.

NBG This is also by way of a reminder if you have read Potter. We know that the universe of sets in ZFC is not itself a set — but isn’t it some sort of collection? Should we recognize, then, two sorts of collection, sets and (as they are called in the trade) proper classes which are ‘too big’ to be sets?  NBG (named for von Neumann, Bernays, Gödel) is one such theory of collections. So NBG recognizes proper classes, objects having members but that cannot be members of other entities. NBG’s principle of class comprehension is predicative; quantified variables in the defining formula can range only over sets, and we get a conservative extension of ZFC (nothing in the language of sets can be proved in NBG which can’t already be proved in ZFC). For more on this and on other theories with classes as well as sets, see (briefly) Appendix C of Potter’s book. Also, for a  more extended textbook presentation of NBG, see

  • Elliott Mendelson, Introduction to Mathematical Logic (CRC, 4th edition 1997), Ch.4.

ZF- + AFA Here again is the familiar iterative conception of the set universe. We start with some non-sets (maybe zero of them in the case of pure set theory). We collect them into sets (as many different ways as we can). Now we collect what we’ve already formed into sets (as many as we can). Keep on going, as far as we can. On this `bottom-up’ picture, the Axiom of Foundation is compelling (any downward chain linked by set-membership will bottom out, and won’t go round in a circle).

Here, however, is another conception of the set universe. Take a set. It (as it were) points to its members. And those members point to their members. And so on and so forth. On this ‘top-down’ picture, the Axiom of Foundation is not so compelling. As we follow the pointers, can’t we come back to where we started?

It is well known that in the development of mathematics inside ZFC the Axiom of Foundation is usually non-critical. So what about considering a theory of sets which has an Anti-Foundation Axiom, which allows self-membered sets? The very readable classic here is

  • Peter Aczel, Non-well-founded sets .(CSLI Lecture Notes 1988).
  • Luca Incurvati, `The graph conception of set’ Journal of Philosophical Logic (published online Dec 2012), illuminatingly explores the motivation for such set theories.

NF Now for a much more substantial departure from ZF. Standard set theory lacks a universal set because, together with other standard assumptions, the idea that there is a set of all sets leads to contradiction. But by tinkering with those other assumptions, there are coherent theories with universal sets. For very readable presentations concentrating on Quine’s NF (‘New Foundations’), and explaining motivations as well as technical details, see

  • T. F. Forster, Set Theory with a Universal Set Oxford Logic Guides 31 (Clarendon Press, 2nd edn. 1995).
  • M. Randall Holmes, Elementary Set Theory with a Universal Set (Cahiers du Centre de Logique No. 10, Louvain, 1998). This can now be freely downloaded from the author’s website.

IST Leibniz and Newton invented infinitesimal calculus in the 1660s: a century and a half later we learnt how to rigorize the calculus without invoking infinitely small quantities. Still, the idea of infinitesimals has a strong intuitive appeal, and in the 1960s, Abraham Robinson created a theory of hyperreal numbers, based on ultrafilters: this yields a rigorous formal treatment of infinitesimal calculus. Later, a simpler and arguably more natural approach, based on so-called Internal Set Theory, was invented by Edward Nelson. As Wikipedia puts it, ”IST is an extension of Zermelo-Fraenkel set theory in that alongside the basic binary membership relation, it introduces a new unary predicate standard which can be applied to elements of the mathematical universe together with some axioms for reasoning with this new predicate.” Starting in this way we can recover features of Robinson’s theory in a simpler framework.

  • Edward Nelson, ‘Internal set theory: a new approach to nonstandard analysis’ Bulletin of The American Mathematical Society 83 (1977), pp. 1165–1198. Now freely available from projecteuclid.org.
  • Nader Vakin, Real Analysis through Modern Infinitesimals (CUP, 2011). A monograph developing Nelson’s ideas whose early chapters are quite approachable and may well appeal to some.

ETCS  Famously, Zermelo constructed his theory of sets by gathering together some principles of set-theoretic reasoning that seemed actually to be used by working mathematicians (engaged in e.g. the rigorization of analysis or the development of point set topology), hoping to a theory strong enough for mathematical use while weak enough to avoid paradox. But does he overshoot? Could we manage with less?

  • Tom Leinster, ‘Rethinking set theory‘,  gives an advertising pitch for the merits of Lawvere’s Elementary Theory of the Category of Sets, and …
  • E. William Lawvere and Robert Rosebrugh, Sets for Mathematicians (CUP 2003) gives a very accessible presentation which doesn’t require that you have already done any category theory.

Though perhaps to fully appreciate what’s going on, you will have to go on to dabble in category theory (see the next section of the Guide!).

More?  Finally, for a brisk (and somewhat tough) overview of many other alternative set theories, including e.g. Mac Lane set theory, see

So what readings at a comparable level should I also have mentioned? What other deviant set theories should I have mentioned? Comments are open …!

Scroll to Top