I think I might have been clinically insane

Judge for yourself, from ten years ago:

http://web.archive.org/web/20001110112300/www.saunalahti.fi/~zaphod/

Testing Emacs mode for blogging

A quick google revealed that there are indeed Emacs lisp hacks that allow one to write blog posts in the comfort of all things Emacsy.

One of them, which I'm currently testing, is available at http://code.google.com/p/e-blog/. We'll see if this gets posted, and how the formatting turns out. A quick look at the Emacs lisp code suggests that while this text is auto-filled as I write it, e-blog will reformat it before submitting it to blogger.com. Well, as said, we'll see.

UPDATE: The post got happily through, as you can see. The lisp code seems to be working just fine for posting -- I'm now testing whether updating existing posts works -- and a one-line insertion to e-blog.el gave me ispell based on-the-fly spell-checking (i.e. I enabled the flyspell-mode minor mode as default for the blog posting mode). Wonderful. No longer must I suffer the horrible Google interface. One less reason to ever leave Emacs.

Pohlers versus Girard

I recently received my copy of Pohlers' Proof Theory: The First Step into Impredicativity from Amazon. Alas, I can only second Peter Smith's complaint, that the book is not particularly well written. It's stated in the back of the book Pohlers' intent was to "write a book on proof theory that needs no previous knowledge of proof theory". If so, the book quite falls short of its stated goal. It is at the same time too abstract, and too involved with irrelevant formal details, to be really approachable to those who have not yet been exposed to proof theory. This said, there's much good in the book. The systematic use of Tait-calculi in particular is something to be applauded. One finds in this book also the "quantitative" side to the Schütte-Feferman analysis of predicative explained in detail. (For the "qualitative" side Torkel's Inexhaustibility is much to be preferred -- indeed, reading Pohlers' book one will certainly learn the ordinal bounds, but quite why they should count as an analysis of predicativity in particular and not just these or those random formal theories is left almost unexplained.) Those into technical proof theory will welcome too the systematic sustained exposition of operator controlled derivations, the application of "impredicative" techniques to predicative theories, etc.

I wouldn't recommend Pohlers' text as the first introduction to proof theory. But then, I wouldn't recommend any existing text as a first introduction to proof theory. Proof theory is, it seems, an inherently messy subject, requiring bits and pieces from recursion theory, model theory, general set theory, the theory of the constructible hierarchy, descriptive set theory, and so on. Not necessarily the most profound bits, but bits nevertheless. It is possibly this dependence on in themselves rather technical fields that renders proof theory more difficult for elementary introductory expositions. (Concepts and results are necessarily pulled out of a hat, so to speak.) Nevertheless, if I absolutely had to pick a text, it would be Girard's Proof Theory and Logical Complexity. It is not that the text is necessarily any more forgiving than Pohlers', but rather that Girard is quite forthright about the tedious formalities -- and indeed explains in banal terms the point to these and those formalities, and why they're relevant or irrelevant, as the case may be, for this or that purpose -- and does not indulge in gratuitous abstraction. Experience teaches that in proof theory it is necessary to get one's hands dirty at some point. (After which one may prudently refrain from touching an actual formal proof unless absolutely necessary.) So be it. Experience also teaches that in proof theory only certain kinds of abstractions actually pay off, perhaps because we haven't found the right kind of general abstractions yet. I believe Girard manages to strike an agreeable compromise between concreteness and abstraction -- it's an empirical observation that in proof theory we raise the level of generality not by introducing abstractions and precise definitions, but rather by developing a sense of when the formal details are relevant and when they're just irrelevant fluff that can be safely ignored. Going through Girard's text one will certainly develop the relevant kind of intuition for these things. Not so with Pohlers'.

Pohlers' philosophical and historical interludes are rather telegraphic and sometimes peculiar. In contrast, while Girard too professes but the working logicians knowledge of history, his discussion of Hilbert's programme, the classification problem, the (ab)use of the incompleteness theorems by non-mathematicians, and so on, are insightful and readable. One terminological point that leaves me completely baffled is Pohlers' use of the word "folklore". The term is usually taken, if I'm not completely mistaken, to refer to results known by those in the know but not explicitly stated in the literature. Most results Pohlers terms "folklore" are certainly not folklore in this sense! (Or so I think, I haven't bothered to actually check this...)

Logic put to good use

It is very good to see wild fantasies about superintelligent machines, consciousness and what not supported by bandying about random Gödelian formalities. Very impressive stuff indeed.

Fictionalism and existence

The Stanford Encyplopedia of Philosophy article on Fictionalism in the Philosophy of Mathematics gives the following definition of fictionalism

Fictionalism, on the other hand, is the view that (a) our mathematical sentences and theories do purport to be about abstract mathematical objects, as platonism suggests, but (b) there are no such things as abstract objects, and so (c) our mathematical theories are not true.

There's much going for fictionalism. For example, it seems it makes no difference, as far as mathematical arguments are concerned, whether or not mathematical objects "really" exist or not. That is, in mathematics we never reason "Since mathematical objects are just figments of our imagination, it follows that..." or "Since mathematical objects exist in some independent Platonic realm, we have that...". As far mathematics is concerned, it seems there is no observable difference between, say, naturals really existing and our pretending they exist. Of course, mathematics is not a hermetic realm. We make observations such as

(*) Even if Goldbach's conjecture is true, it might be that there is no proof of Goldbach's conjecture using mathematical principles we accept, or could come to accept.

all the time. Similarly, we draw conclusions about the behaviour of computer programs from mathematical statements. And so on. In (*) "Goldbach's conjecture is true" -- the use of "true" is inessential, since we may just replace the phrase with the statement of the conjecture -- is used factually, so to speak. Obviously, on any usual understanding, the observation does not mean

(*') Even if it is inherent in the stories we tell about naturals that Goldbach's conjecture is true, it might be that there is no proof of Goldbach's conjecture using mathematical principles we accept, or could come to accept.

(Indeed, it is not even clear whether (*') makes any sense at all.) This is, essentially, "the problem of objectivity in mathematics". As Kreisel famously noted -- though where he noted this is obscure, as is the case with many an observation usually attributed to Kreisel; apparently it's from a review of Wittgenstein's notes on philosophy of mathematics -- in the question of objectivity in mathematics the real issue is the objectivity of mathematical statements, not existence of mathematicsl objects. But let's set this question aside for a moment.

Fictionalism is so named because in many forms it derives its appeal from an analogy with fiction. That is, we may make sense of the claim that Captain Planet is formed by combining the powers of the rings of the Planeteers, and agree that he is not instead formed by combining the powers of Harry Potter and Tristram Shandy, while also agreeing that, in reality, Captain Planet does not exist at all. Similarly, we may be tempted to say that mathematical objects (and possibly other abstracta as well) don't really exist. This is problematic, however. In case of Captain Planet what we deny when we deny that there is any such entity is entirely clear, just as it is clear what we deny in denying that Sherlock Holmes, Harry Potter, and so on, really exist. There simply are, in the real world, no such people. What of mathematical objects? In denying that they exist, just what it is we are denying? The suggestion that mathematical objects might exist but it simply happens they don't is on the face of it rather baffling. We are owed some account of what their existing, if they did exist, would amount to. (And, in absence of such an account, the sometimes suggested solution to the problem of objectivity, that mathematical statements are objective in the sense that it is determined as a matter of fact whether they would be true if mathematical objects existed and were such that the stories we tell about them would be true, is meaningless as well.)

A natural answer suggests itself: mathematical objects (and possibly other purely abstract things) are a degenerate case of fiction. That is, for such objects, there is simply no existence they could have in addition to being parts of our mathematical and abstract stories. If we take this view we naturally reject the claim (b) in the definition of fictionalism quoted above. That is, rather than denying that mathematical objects exist, we instead gleefully accept that they exist -- after all, presumably we accept many mathematical statements that trivially imply the existence of mathematical objects, e.g. "There is a prime smaller than 10" -- but that this existence is not at all analogous to the existence of physical objects in any sense. (We might here recall Kreisel's caution against thinking of large infinite sets as akin to humongous physical objects.) We may of course also accept usual statements expressing the Platonist position as metaphorical or poetic expressions of our natural attitude towards mathematical statements, something like Hardy's tautology "317 is prime because it is".

So far so good, but we're still left with the problem of objectivity. If mathematical objects exist only as parts of our mathematical stories, indeed can only exist as parts of such stories, how do we account for our natural inclination to regard truth of such as statements as "n is prime" as a factual matter. The answer, that truth of such statements amounts to nothing more than their being in some sense inherent in the stories is obviously unpalatable. It is after not true even in the stories themselves, and in asking whether Goldbach's conjecture holds, or whether there is a measurable cardinal we are not, on the face of it, asking anything about any stories at all, but rather about naturals and sets.

I don't have any good answer to the problem of objectivity, but will instead offer some general reflections, in my characteristically frustrating style. Kreisel in his hilariously rambling Second Thoughts Around Some of Gödel's Writings writes:

Subjectively speaking, the most striking general object lesson I believe I have learnt from logic is really little more than a confirmation of common sense, the distinction between

bright ideas and germs of theories;

in the sense that the former function best as remarks (constatations in French, Konstatierungen in German), and simply do not lend themselves to much theoretical elaboration, while the latter do. (NB. The latter need not be more useful than the former, by any realistic measure of usefulness.)

It is not at all given that either the observation that mathematical stories seem to be a degenerate case of fiction, or that our natural attitude is to take at least some mathematical statements as factual (and this observation applies just as well to intuitionism), are of the latter sort rather than the former, that is, that they are more than interesting observations, insightful remarks about mathematics. We must milk them in some interesting way, in various practical contexts, before it becomes apparent whether they have any theoretical import in the philosophy of mathematics (understood as the philosophical study of actual mathematics, and the concepts implicit in actual mathematics, instead of study of classical ontological, epistemological, metaphysical questions when formulated about mathematical entities and mathematical statements). It is sterile to put forth philosophical theories and systems, arguments against and for such systems, counter-arguments to such arguments, enumerating all logically possible combinations of these or those stances, and so on, at this point. (It is not sterile in the sense of producing an endless stream of disseratations, papers, talks, and such like, of course.)

Dummett on strict finitism

Recently, I've been going through (some of) the writings of Michael Dummett. Dummett is indubitably a master of philosophical argumentation, but often one feels he's "insufficiently profound", and his masterful weaving of different threads of reasoning amounts merely to the philosophical equivalent of "logic chopping". Nevertheless, there is much food for thought in his writings, and, of the modern philosophers of mathematics who might actually taken to have a project -- and not only primarily a technical project -- in the old grandiose sense of the term, of basing all of philosophy on the theory of meaning, and related considerations, he's possibly the most worthy of serious consideration. I'll later have something to say about all that, but in this post I wish to address just a single point.

In the 1970 paper Wang's Paradox Dummett takes on the task of defending intuitionistic anti-realism of his kind from the counter-argument that meaning-theoretic considerations (of the sort he adduces) should lead one to adopt rather the stance of "strict finitism". In contrast to Dummett's anti-realistic intuitionism, in strict finitism we demand that the meaning of mathematical language be explained in terms of our actual abilities. Dummett for example happily accepts that (n)(n is a prime \/ n is not a prime), since we may, "if we so choose", for any given n go through every m < sqrt(n) and check whether it divides n. We are, in Dummettian terminology, in possession of an effective method of deciding whether a given natural is a prime or not. Of course, this is a theoretical ability -- in reality, if given a sufficiently large natural I'm not at all capable of deciding its primality. Thus we may say that Dummettian anti-realism is a theoretical sort of anti-realism, explaining the meaning of mathematical language not in terms of our actual practice and abilities but rather in terms of a theoretical and idealised account, a conceptual picture, of that practice and those abilities. The question, then, is how, on the Dummettian account of meaning, we can learn to understand statements the meaning of which hinges on such a theoretical account? Shouldn't we rather take seriously the idea that meaning is grounded in our practice and abilities, investigating the real limitations of these abilities?

In Wang's paradox Dummett writes

But, even if no one were disposed to accept arguments in favour of the strict finitist position, it would remain of greatest interest , not least for the question whether constructivism, as traditionally understood, is tenable position. It can so only if, despite surface similarity, there is a disanalogy between the arguments which the strict finitist uses against the constructivist and those which constructivist uses against the platonist. If strict finitism were to prove internally coherent, then either such disanalogy exists or the argument for traditional constructivism is unsound, even in absence of any parallel incoherence in the constructivist position.

Dummett then goes on to consider what is involved in the strict finitist account of the naturals -- this is by far the most interesting part of the paper -- and finally concludes that strict finitism is incoherent, on basis of an argument ("Wang's paradox") to the effect that reasoning about vague predicates in general is literally inconsistent or incoherent.

Let's set aside the question of whether Dummett's argument is convincing (it is not). The curious thing is that after presenting this conclusion Dummett seems content. However, the argument against Dummettian anti-realist intuitionism is not addressed at all! That is, it might well be that strict finitism is incoherent. It doesn't at all follow that Dummettian anti-realist intuitinism is coherent -- for the counter-argument, arguing that strict finitism rather than anti-realist intuitionism in fact follows on meaning theoretic grounds might well be valid even if strict finitism is incoherent.

Now, Dummett does not formulate the argument against anti-realist intuitionism quite as I did in the above. Rather, as he sees things, it is the analogue of his argument against "the Platonist". (At that time Dummett apparently took it for granted that the only reason someone would hold that the law of excluded middle is true for mathematical statements is belief in "Platonism", existence of mathematical objects in some sense analogous to existence of physical objects.) Still, it remains baffling that while he notes that in order for anti-realist intuitionism to be coherent there must be some disanalogy he does not in fact locate any such disanalogy, seemingly happy to merely establish the incoherence of strict finitism to his satisfaction. It is of course possible that the purpose of the paper was merely to report some philosophical arguments against vague predicates, some seemingly unpalatable observations about phenomenal properties and observational preciates, and so on. Still, one would have expected at least some comment on the seemingly pressing question of the validity of the meaning-theoretic argument for anti-realist intuitionism...

Justifying schemata

An old and now well-familiar adage of Kreisel's has it that our justification for the induction schema in PA, replacement schema in ZFC, and so on, must necessarily come from acceptance of the corresponding second-order principles. There is something very obvious to this observation: it seems difficult to imagine any natural way of justifying the instances of the shcemata, involving arbitrarily complex formulas in this or that formal language, without going through the second-order principle, and noting that the instances of the first-order schema all trivially follow. In such a justification we would presumably use in some ingenious way the syntactic structure of the formulas, and so on. Setting imaginings aside, it might be simply observed there is at the moment anything resembling such a justification. (We can of course imagine a justification of sorts, e.g. by means of some restricted form of transfinite induction, as in Gentzen's proof of (1-)consistency of Peano arithmetic -- but it is difficult to imagine such a justification for the truth of all the instances.)

Many have observed, though, that it is not obvious in just what sense the induction principle, replacement, and so on, are "second-order principles". For, in their natural formulations in ordinary mathematical English

Whenever P is a well-defined determinate property of naturals, if it holds of 0, and whenever it holds of n, of n + 1 also, it holds of all naturals.

Whenever R is a well-defined determinate functional binary relation between sets, for any set A, the image of A, i.e. the set {y | (Ex in A) R(x,y)}, exists.

they involve a notion, of a property being "well-defined" and "determinate", that has no apparent mathematical definition. So, we may say they are faithfully captured by their second-order formulations if we stipulate the higher-order quntifiers range over "well-defined and determinate" properties (and relations, functions and so on). But since this is not a mathematical notion we have achieved nothing, and it is not at all obvious what these principles so formulated have to do with their second-order formulations on the more usual set-theoretic semantics, at least in so far as the epistemological use we make of them is concerned. Perhaps more natural approach is to regard these principles not as formal principles at all, but as informal principles that have, strictly speaking, no definite set of consequences, that are not necessarily captured by any formalisation at all, but rather have an indefinite range of mathematical applications we regard as correct. This range is indefinite, since we can't beforehand restrict the totality of properties we recognise as determinate and well-defined to any mathematically defined definite totality -- it is dependent on our decisions on what properties we regard as determinate and well-defined, and there is no reason to think that there must always be some matter of fact on which such decisions turn. (And even if there are in fact always such matters of fact, and some determined totality of properties that are, in some idealised sense, recognisable by us as determined and well-defined, for Gödelian reasons we can never recognise this totality as such.)

So, disregarding the notion the "informal" induction principle or replacement are "second-order principles", we may describe the resulting picture in the following not very precise terms. Whenever, for whatever reason, we recognise some language defined with mathematical precision, a formal language, as meaningful, so that formulas in the language define well-defined and determinate properties, and sentences meaningful statements that are either true or false as a matter of mathematics, we get, from the "informal" principles, a principle of mathematical precision, by restricting "well-defined and determinate property" in these "informal" principles to range over properties definable in the formal language. Of course, the resulting mathematical principle does not cover all the applications of the informal principle recognisable by us as valid, since, given we recognise the formal language as meaningful, we must surely recognise the notion of a sentence in the language being true, and a formula being true of given objects, as determinate and well-defined (on the picture painted here, we regard this observation not as something to be argued for, but as a triviality, since it is not obvious what sort of meaningfuless of a formal language would license the conclusion of the applicability of the induction principle for the language that did not involve accepting the determinateness and well-definedness of the formal language); but, by well-known results in mathematical logic, these notions are not expressible in the formal language itself.

So far, so standard. There is, however, a small glitch in our development. Recall the replacement schema as formalised in ZFC

(*) (x)(E!y)R(x,y) implies (x)(Ey)(z)(z in y iff (Ew in x)R(x,z))

On the face of it, it's easy to see every instance of the scheme is true given the informal replacement principle and the meaningfulness of the language of set theory. Alas, the instances of the schema (*) are in fact universal closures of sentence obtained by replacing R with formulas possibly with more free variables than just two. That is, they have in fact the form

(*') (a1)(a2) ... (an)(x)(E!y)R(x,y,a1, ..., an) implies (x)(Ey)(z)(z in y iff (Ew in x)R(x,z, a1, ..., an))

The same of course applies to the induction schema, its instances, and their justification given the informal induction principle (except that the language of arithmetic has a name for every natural, so in so far as we're dealing with naturals only the problem has a rather trivial solution, using substitutional quantification). The problem here is that a formula R(x,y, z1, ..., zn) in the language of set theory does not define a well-defined determinate functional binary relation of sets -- it does not define a binary relation at all. We need some further argument to justify the truth of (*') given the informal replacement principle and the meaningfulness of the language of set theory. One would be to argue that the language of set theory augmented with a constant for every set is meaningful, and formulas in it express properties. For this language, there is no difference between schemas (*) and (*'). Alas, if we go this way, we must explain what it means for a language the size of a proper class to be meaningful, why we should recognise the extended language of set theory as such given the usual conception of the world of sets (the cumulative hierarchy, sets as arbitrary extensional collections, and so on), why the meanigfulness of such language guarantees that all formulas define determinate well-defined properties (are there a proper class of properties?), and so on and so forth. Fortunately, we may shift the burden directly to the informal principles themselves, so we get

Whenever P is a well-defined determinate m-ary relation between a natural and j = m-1 objecs of any sort, if given some objects a1, ..., aj if it holds of 0 and a1, ..., aj, and whenever it holds of n and a1, ..., aj, of n + 1 and a1, ..., aj also, it holds of every natural n and a1, ..., aj.

Whenever R is a well-defined determinate functional 2+n-ary relation between two sets and n objects a1, ..., an, given any objects a1, ..., an, for any set A, the image of A under R(x, y, a1, ..., an), i.e. the set {y | (Ex in A) R(x, y, a1, ..., an)}, exists.

These principles are just as evident (on the relevant mathematical picture) as the originals, and have the nice property that they in fact directly yield the corresponding formal schemata. (We have used the notion of natural in the formulation of the induction principle, in referring to relations of arbitrary arity. This is not in itself worrying, since there is no pretence that the induction principle serves in a definition of what a natural is in any non-circular sense. Rather, it functions as a part of explanation or explication of this notion, and in our conceptual and philosophical analysis of the justification of various mathematical principles. Such an analysis need not in any way justify the correctness of that justification, or refrain from making use of concepts justified or explained by what is under analysis.)