tag:blogger.com,1999:blog-73248053515177406832018-08-22T02:41:42.814+03:00PerhapsErratic rambling and pointless maundering.Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.comBlogger10125truetag:blogger.com,1999:blog-7324805351517740683.post-1838088661144586732009-04-16T03:55:00.001+03:002009-04-16T03:57:16.986+03:00I think I might have been clinically insaneJudge for yourself, from ten years ago:<br /><br /><a href="http://web.archive.org/web/20001110112300/www.saunalahti.fi/%7Ezaphod/">http://web.archive.org/web/20001110112300/www.saunalahti.fi/~zaphod/</a>Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com11tag:blogger.com,1999:blog-7324805351517740683.post-28686129802208908152009-03-15T16:56:00.001+02:002009-03-15T17:04:51.377+02:00Testing Emacs mode for blogging<div xmlns='http://www.w3.org/1999/xhtml'><p>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.</p><p>One of them, which I'm currently testing, is available at <a href='http://code.google.com/p/e-blog/'>http://code.google.com/p/e-blog/</a>. 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.</p><p><strong>UPDATE:</strong> 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.</p></div>Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com3tag:blogger.com,1999:blog-7324805351517740683.post-73890037670798186242009-03-15T15:40:00.004+02:002009-03-15T16:15:06.815+02:00Pohlers versus GirardI recently received my copy of Pohlers' <span style="font-weight: bold; font-style: italic;">Proof Theory: The First Step into Impredicativity</span> from Amazon. Alas, I can only second <a href="http://logicmatters.blogspot.com/2009/02/pohlers-proof-theory.html">Peter Smith's complaint</a>, 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 <span style="font-weight: bold; font-style: italic;">Inexhaustibility</span> 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 <span style="font-style: italic;">predicativity</span> 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.<br /><br />I wouldn't recommend Pohlers' text as the first introduction to proof theory. But then, I wouldn't recommend <span style="font-style: italic;">any</span> 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 <span style="font-weight: bold; font-style: italic;">Proof Theory and Logical Complexity</span>. 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'.<br /><br />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...)Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com0tag:blogger.com,1999:blog-7324805351517740683.post-19134189328836776272009-02-16T15:19:00.002+02:002009-02-16T15:22:39.590+02:00Logic put to good useIt is very good to see wild fantasies about superintelligent machines, consciousness and what not supported by <a href="ftp://ftp.idsia.ch/pub/juergen/gm6.pdf">bandying about random Gödelian formalities</a>. Very impressive stuff indeed.Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com2tag:blogger.com,1999:blog-7324805351517740683.post-53069748919314873522009-02-16T11:02:00.007+02:002009-02-16T14:40:18.480+02:00Fictionalism and existenceThe <span style="font-style: italic;">Stanford Encyplopedia of Philosophy</span> article on <span style="font-style: italic;"><a href="http://plato.stanford.edu/entries/fictionalism-mathematics/">Fictionalism in the Philosophy of Mathematics</a> </span>gives the following definition of fictionalism<blockquote>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.</blockquote><blockquote></blockquote>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<blockquote>(*) 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.<br /><blockquote></blockquote></blockquote>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<blockquote>(*') 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.<br /></blockquote>(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.<br /><br />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.)<br /><blockquote></blockquote>A natural answer suggests itself: mathematical objects (and possibly other purely abstract things) are a <span style="font-style: italic;">degenerate case</span> 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".<br /><br />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 "<span style="font-style: italic;">n</span> 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.<br /><br />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 <span style="font-style: italic;">Second Thoughts Around Some of Gödel's Writings</span> writes:<blockquote>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<br /><br /> bright ideas and germs of theories;<br /><br />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.)</blockquote>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.)<br /><blockquote></blockquote>Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com4tag:blogger.com,1999:blog-7324805351517740683.post-32674083908396280982009-02-11T20:26:00.005+02:002009-02-16T11:44:00.568+02:00Dummett on strict finitismRecently, 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 <span style="font-style: italic;">technical</span> 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.<br /><br />In the 1970 paper <span style="font-style: italic;">Wang's Paradox</span> 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 <span style="font-style: italic;">actual</span> 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 <span style="font-style: italic;">n</span> go through every <span style="font-style: italic;">m</span> < sqrt(<span style="font-style: italic;">n</span>) and check whether it divides <span style="font-style: italic;">n</span>. 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 <span style="font-style: italic;">theoretical</span> and <span style="font-style: italic;">idealised</span> 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?<br /><br />In <span style="font-style: italic;">Wang's paradox</span> Dummett writes<br /><blockquote>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.<br /></blockquote>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.<br /><br />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.<br /><br />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...Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com1tag:blogger.com,1999:blog-7324805351517740683.post-64143455416139272262009-01-09T07:36:00.004+02:002009-01-09T08:29:47.703+02:00Justifying schemataAn 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 <span style="font-style: italic;">truth</span> of all the instances.)<br /><br />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<br /><blockquote>Whenever <span style="font-style: italic;">P</span> is a well-defined determinate property of naturals, if it holds of <span style="font-style: italic;">0</span>, and whenever it holds of <span style="font-style: italic;">n</span>, of <span style="font-style: italic;">n</span> + <span style="font-style: italic;">1</span> also, it holds of all naturals.<br /><br />Whenever <span style="font-style: italic;">R</span> is a well-defined determinate functional binary relation between sets, for any set <span style="font-style: italic;">A</span>, the image of <span style="font-style: italic;">A</span>, i.e. the set <span style="font-style: italic;">{y | (Ex in A) R(x,y)}</span>, exists.<br /></blockquote>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.)<br /><br />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.<br /><br />So far, so standard. There is, however, a small glitch in our development. Recall the replacement schema as formalised in ZFC<br /><blockquote>(*) (x)(E!y)R(x,y) implies (x)(Ey)(z)(z in y iff (Ew in x)R(x,z))<br /></blockquote>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<br /><blockquote>(*') (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))</blockquote>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<br /><blockquote>Whenever <span style="font-style: italic;">P</span> is a well-defined determinate<span style="font-style: italic;"> m</span>-ary relation between a natural and <span style="font-style: italic;">j = m-1</span> objecs of any sort, if given some objects <span style="font-style: italic;">a1, ..., aj</span> if it holds of <span style="font-style: italic;">0</span> and <span style="font-style: italic;">a1, ..., aj</span>, and whenever it holds of <span style="font-style: italic;">n</span> and <span style="font-style: italic;">a1, ..., aj</span>, of <span style="font-style: italic;">n</span> + <span style="font-style: italic;">1</span> and <span style="font-style: italic;">a1, ..., aj </span>also, it holds of every natural <span style="font-style: italic;">n</span> and <span style="font-style: italic;">a1, ..., aj</span>.<br /><br />Whenever <span style="font-style: italic;">R</span> is a well-defined determinate functional <span style="font-style: italic;">2+n</span>-ary relation between two sets and <span style="font-style: italic;">n</span> objects <span style="font-style: italic;">a1, ..., an</span>, given any objects <span style="font-style: italic;">a1, ..., an,</span> for any set <span style="font-style: italic;">A</span>, the image of <span style="font-style: italic;">A</span> under <span style="font-style: italic;">R(x, y, a1, ..., an)</span>, i.e. the set <span style="font-style: italic;">{y | (Ex in A) R(x, y, a1, ..., an)}</span>, exists.<br /></blockquote>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 <span style="font-style: italic;">definition</span> of what a natural is in any non-circular sense. Rather, it functions as a part of <span style="font-style: italic;">explanation</span> or <span style="font-style: italic;">explication</span> 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.)Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com2tag:blogger.com,1999:blog-7324805351517740683.post-34222055986974608612009-01-05T20:33:00.005+02:002009-01-06T21:52:51.770+02:00On the force of "in principle"<div style="text-align: left;"><blockquote>"<span style="font-style: italic;">But even if -- imagining a man quite exempt from all influences, examining only his momentary action in the present unevoked by any cause -- we were to admit so infinitely small a remainder of inevitability as equalled zero, we should even then not have arrived at the conception of complete freedom in man, for a being uninfluenced by the external world, standing outside time, and independent of cause, is no longer a man.</span>"<br /><span style="font-weight: bold;"></span></blockquote><span style="font-weight: bold;"> </span><blockquote><span style="font-weight: bold;">Count Leo tolstoy<br /><span style="font-style: italic;"> Second epilogue to War and Peace</span></span><br /><span style="font-weight: bold;"><br /><span style="font-style: italic;"></span></span></blockquote>It strikes some people as perverse that some, such as Edward Nelson, seriously doubt the consistency of Peano arithmetic (and even weaker theories such as EFA). Such doubts, and Nelson not only doubts the consistency of EFA but is serious about finding a contradiction, are indeed perverse from any ordinary point of view, but they are not unprincipled, that is, they are not examples of arbitrary skepticism. It is an instructive philosophical exercise to make sense of these doubts, not to address or refute them, but rather to articulate the basic preconceptions inherent in our thinking, to see what rests on what. To that end, I'll say a few words about the force of "in principle" in such turns of phrases as "in principle, we can find a counter-example to Goldbach's conjecture if there is one", "if <span style="font-weight: bold;">ZFC</span> is inconsistent we can in principle find this out" and so on.<br /><br />We are <span style="font-style: italic;">in principle</span> capable of wonderful feats. Perusing texts in logic and the philosophy of mathematics we learn for example that we are in principle capable of verifying the correctness of arbitrarily complex formal proofs, of finding a counter-example to Goldbach's conjecture if there is one, of finding a contradiction in <span style="font-weight: bold;">ZFC</span> should it be inconsistent, of multiplying arbitrarily large natural numbers, of normalising arbitrarily complex intuitionistic proofs to extract witnesses for existential statements, and so on. It is not a particularly original observation that even though we are in principle able to do all these things, we are, in reality, quite incapable of doing so. It is nevertheless an instructive exercise to examine this apparent tension, and ask just what is the force of ``in principle'', and how it is that we are, so it seems, in principle capable of doing all sorts of things it is utterly fantastic to consider to lie within our actual abilities.<br /><br />Let's call abilities such as ours of factoring arbitrarily large numbers ("in principle") counterfactual abilities. Such abilities are counterfactual in being counter to actual facts about our abilities. In contrast, I have the real ability to factor any number less than 1000, in that, should I so choose, I could in fact, with some patience or with the aid of a computer or a calculator, go through all numbers less than 1000 and check whether any of them divides the given number. In case of arbitrarily large naturals, my counterfactual ability is obviously not grounded in any such facts about my real abilities. So, what is it grounded in? The answer is rather trivial: we are in principle capable of factoring arbitrarily large naturals in the sense that we are in possession of an algorithm for doing so, an algorithm of which we can mathematically prove that it returns the factors of any given number, and a model of mechanical computability on which it is obvious that in any step of computation we are not required to do anything that is beyond our actual capabilities. That is, even though we will never find ourselves in the position of having carried out 2^65536 long divisions, what is required of us in the hypothetical situation is something we can actually do, such as writing down a single digit, striking out a symbol and so on. (In contrast, with such notions as "a mathematical principle in principle acceptable to us" or "unassailably true arithmetical statement" we have no idea what the relevant counterfactual situations are, or what sort of idealisations regarding our abilities are in question.)<br /><br />There is a strong intuition that the truth or falsity of Goldbach's conjecture is determined as a matter of mathematical fact, that either there is a natural with these or those properties or not (and, for the intuitionistically minded reader, that either there is a canonical proof of this or that or there is not -- Dummett is one of the few thinkers who have seriously rejected an implicit sort of realism about intuitionistic proofs, leading in the good philosophical tradition to many very obscure musings he blithely ignores when going on about other matters). One source of this intuition is our image of ourselves going through the naturals, carrying out computations and so on. It seems almost unintelligible to suppose there is no fact to unearth, since we can picture ourselves having found out that an even number greater than two is not the sum of two primes, by calculation. (I don't recall who it was, but it has been observed that talk about "metaphors" and "pictures" in philosophy is usually metaphorical...) But, since we are not dealing with our actual abilities, all of our reasoning about arbitrarily complex calculations and such like is necessarily theoretical, grounded on some conception of what it would be like if we were not limited the way we are. On closer inspection, it turns out that in fact this conception does not turn on our nature, that is, it is not based on any physiological, psychological, neurological analysis. Rather, it is based on a mathematical image. In other words, the claim that if Goldbach's conjecture is false we can in principle find a counter-example is not really about us at all, but is merely a restatement of the fact that being a counter-example to Goldbach's conjecture is a decidable property.<br /><br />Let us return to radical finitism, or ultra-finitism. The rejection of the "in principle" is nicely captured by Gandy in <span style="font-style: italic;">Limitations of Mathematical Knowledge</span><br /><blockquote>In discussions about the foundations of mathematics it's usual to suppose that the inscriptions which are used to communicate mathematics (e.g. numerals, formulae, proofs) form a potentially innite totality. Despite the fact that this suppostion runs directly counter to everyday experience, no effort is made to justify it. It is of course admitted that in practice concrete inscriptions are limited in length; but an author who has made this assertion is likely to claim in the very next sentence that in principle arbitrarily long inscriptions may be written and the operations and tests of elementary syntax can in principle effectively performed on them. This seems to me as objectionable as to say that in principle pigs can fly while admitting that in practice they have no wings.</blockquote>The rejection of the "in principle" is not non-sensical or unprincipled. As noted, our abilities "in principle" to do this or that in fact depend on mathematical theorems, on mathematical pictures. We can't address the ultra-finitist doubts by these "in principles" without running foul of circularity. Of course, this is not to say there is something objectionable or dubious in claims about our counterfactual abilities of this sort -- as noted, it is obvious in what sense we have the ability to factor arbitrarily large naturals etc. The point is rather to make the ultra-finitist position understandable, and to note that our reasoning about counterfactual abilities presupposes a substantial amount of mathematics. It therefore cannot serve as a justification of our mathematical thinking, even though it is undoubtedly very useful in <span style="font-style: italic;">explaining</span> our thinking, and making it palatable. We should be thankful for such people as Wittgenstein and Nelson for providing us with actual examples of real anti-realism, of really taking the notion that understanding of mathematics should be grounded in our actual practice seriously. They serve as a healthy corrective to such thinkers as Dummett, who happily go about "our" abilities and "our" reasoning while obviously describing some unknown species of immortal and indefatigable demi-gods.<br /><br />Incidentally, Peter Smith now has a link to this blog in <a href="http://logicmatters.blogspot.com/">his</a>. Peter's blog is recommended to everyone interested in logic and philosophy.<br /></div>Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com1tag:blogger.com,1999:blog-7324805351517740683.post-60711813707791037162009-01-05T19:44:00.005+02:002009-01-06T17:25:22.779+02:00Consistency and existence, with some random rantingThe idea that the completeness theorem vindicates the very natural notion that in mathematics consistency implies existence, that mathematics is a free creation, subject only to the requirement of consistency, and so on, crops up now and then. Some time ago it did just that in sci.logic, but I failed to subject the poor poster bringing it up to my characteristic tedious pedantry and obnoxiousness. Happily, I can do that here in this blog.<br /><br />The completeness theorem, proven in the usual Henkin style, establishes that if a theory is consistent it has a model, the domain of which is the set of naturals, constant symbols naming particular naturals, and the interpretations of the relation and function symbols being horribly complex random configurations of naturals. Consider now the claim that infinite sets exist if the story we tell about them, as formalised in e.g. ZFC, is consistent. As noted, this is a very natural idea. Alas, the completeness theorem does nothing to support it, because even though it does guarantee the existence of <span style="font-style: italic;">something</span> for a consistent theory, this something is not what we'd like to have. For certainly the claim that infinite sets exist does not mean that there is some horribly complex configuration of naturals under which the axioms of ZFC come out true. It is also apparent that for example inaccessible cardinals do not exist if ZFI = ZFC + "there are inaccessible cardinals" is consistent but proves "ZFI is inconsistent". If we wish to take the natural idea seriously and flesh it out in some philosophically fruitful way, we must explain just what sort of consistency is at issue here, as it is apparent, at least in light of rather trivial observations such as the above, that it is not consistency of formal theories in the technical sense.<br /><br />The confused idea at issue is a perfect illustration of a very real danger in philosophy of mathematics, of reading philosophical significance into technical results without special argument. Before we get very worked up over and excited about this or that piece of mathematics in a philosophical context, we must carefully figure out just how it is related to the notions under philosophical scrutiny. Usually, the answer is that, despite superficial similarities -- sometimes on terminological level! -- the technical result is just that, a technicality. Another aspect the confused idea nicely illustrates is a sort of intellectual equivocation very common when thinking about mathematics: we wish to view claims about sets and what not from a distance, instead of taking them at face value, as something requiring explanation, philosophical justification and so on, while simultaneously interpreting a technical mathematical result -- in this case, the completeness theorem -- in the usual straightforward manner. This leads to nothing but confusion and bad philosophy, but has its appeal for those of certain bent, in that it seemingly allows us to wax philosophical with mathematical precision.<br /><br />This is not to say that the completeness theorem is devoid of philosophical significance, or that mathematical results never have philosophical relevance. Perhaps the most famous example of "informal rigour" (if we don't count Turing's analysis of mechanical computability) is Kreisel's proof (in the sense of compelling piece of reasoning, not in the mathematical sense -- hence the "informal" in "informal rigour") that logical validity in the "informal" sense is coextensive with validity in the technical sense. (There's a bit about this in my sci.logic <a href="http://groups.google.com/group/sci.logic/msg/1cf3026be617d644">post</a> on formalisation.) In case of completeness and the idea that consistency implies existence what is missing is just such a proof, a piece of compelling reasoning, a careful explanation and analysis. What we have instead is simply a wonderful philosophical revelation, of mathematical clarity, that unfortunately evaporates when subjected to scrutiny. Beware of revelations! Most real insights turn out to be rather dull and not at all exciting, the way things we are intimately familiar and comfortable with are. I suggest that instead of seeking exciting revelations we seek dullness of this kind, that is, dullness that is the opposite of bewilderment; this without any suggestion that philosophy should be dull the way a phonebook is.Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com6tag:blogger.com,1999:blog-7324805351517740683.post-42093424572803293312009-01-05T16:28:00.007+02:002009-01-05T17:41:01.188+02:00Wise words from yesteryearPeter J. Ross, a notorious poet and a troll, once claimed my posts in Usenet are almost always either enjoyable or informative, and often both. I wouldn't know about such matters, but it is certainly true that Torkel Franzén's contributions, in the news and on various mailing lists, were virtually always enjoyable and informative. I've been scrounging the archives of <a href="http://www.cs.nyu.edu/mailman/listinfo/fom/">FOM</a> for nuggets of insight and wisdom, and stumbled upon an <a href="http://www.cs.nyu.edu/pipermail/fom/1997-December/000504.html">old message</a> from Torkel. Neil Tennant repeated the standard line, that in order for a theory to be epistemologically relevant axiomhood must be decidable, which prompted the following reflections from Torkel:<br /><blockquote><pre> Although I've said similar things myself often enough, it<br />only now occurs to me that this isn't really convincing, if<br />one takes the epistemological motivation seriously.<br /><br />The basic premise is that we need to able to decide whether<br />a proposed proof is a proof. I will accept this basic premise,<br />although it is not an immediate consequence of the necessity<br />of avoiding an infinite regress in proving theorems. (Merely<br />being able to verify that a correct proposed proof is a proof,<br />while coming to no conclusion in the case when it is not a<br />proof, would be sufficient to avoid such a regress.)<br /><br />But then it's not enough that the set of axioms *is* recursive.<br />To be able to check a proposed proof we also need to know that<br />the set of axioms is recursive, and in fact we need to have an<br />algorithm for deciding whether or not a formula is an axiom.<br />Such an algorithm, then, is an implicit part or parameter of<br />the proof, from an epistemological point of view.</pre></blockquote>To understand what Torkel's on about, consider the following example, which he himself provided in a later post. Let <span style="font-style: italic;">T</span> be the theory with all arithmetical truths with less than <span style="font-style: italic;">k</span> symbols as axioms. Since there are only finitely many such truths, axiomhood is obviously recursive (and hence decidable). This fact is however of no help whatsoever in deciding whether a given sentence is an axiom or not, and consequently whether a sequence (or a labeled tree or whatever) <span style="font-style: italic;">p</span> is a proof or not -- for sentences with less than <span style="font-style: italic;">k</span> symbols deciding whether it is an axiom or not is equivalent to finding out whether it's true.<br /><br />The upshot of this is that the usual epistemological argument for requiring theories to be recursively axiomatisable is in fact wanting; by the argument we are only warranted to require recursive enumerability of the axioms. That is, in order to recognise a formal proof <span style="font-style: italic;">p</span> as a proof in a recursively axiomatised theory <span style="font-style: italic;">T</span>, we must have at hand an algorithm for deciding axiomhood (and apply that algorithm to the premises of <span style="font-style: italic;">p</span>, verifying they are indeed axioms) -- the recursiveness of the axioms of <span style="font-style: italic;">T</span> and <span style="font-style: italic;">p</span> in itself are insufficient. Similarly, in order to recognise a formal proof <span style="font-style: italic;">p</span> in a theory <span style="font-style: italic;">T</span> with a recursively enumerable set of axioms, we must have at hand an algorithm for listing the axioms, and a computation that in fact yields the axioms used in <span style="font-style: italic;">p</span>. There is no apparent epistemologically relevant distinction between these cases. As Torkel writes<br /><blockquote><pre> If the set of axioms is not recursive, but recursively<br />enumerable, the property of being a proof will still be<br />decidable, if we regard as part of the proof the generation,<br />using an algorithm for enumerating axioms, of the axioms<br />actually used in the proof. The basic premise, then, is<br />satisfied even if we only require the axioms to be<br />recursively enumerable.<br /><br />I therefore think that what the epistemological argument<br />supports is only the need for the set of axioms to be<br />recursively enumerable. A slightly different formal model<br />of proofs is presupposed - one in which a proof incorporates<br />an algorithm for generating axioms together with computations<br />generating the axioms used, rather than just incorporate an<br />algorithm for deciding axiomhood - but I see no good reason<br />why the latter model should be preferred.</pre></blockquote>Of course as everyone knows we can always replace a recursively enumerable set of axioms with a (very unnatural) recursive set with the same deductive closure, by Craig's trick. It is still of independent interest whether epistemological considerations alone justify restricting our attention to recursively axiomatised theories.<br /><br />Many an interesting observation may be found buried in the archives of FOM and those of Usenet newsgroups. (Alas, it seems Google has decided to utterly wreck its Usenet search function, rendering it almost unusable.)<br /><a href="http://www.cs.nyu.edu/mailman/listinfo/fom/"></a>Aatu Koskensiltahttp://www.blogger.com/profile/10999226899475411504noreply@blogger.com1