Probability 0 Conditions

Although I initially intended this blog to be mainly about philosophy of math and metaphysics, I suppose it was inevitable that I’d eventually mention probability here, given the paper I presented at FEW in Austin a month ago and will present again in a week and a half at the AAP in Sydney.

When I finished the first version of that paper in December, I had noticed some claims in van Fraassen’s “Fine-Grained Opinion, Probability, and the Logic of Full Belief” that I thought were a little odd. He suggests dealing with conditionalizing on events of probability 0 by having a well-ordered sequence of probability functions, and just switching to the first function in the list where the conditionalizing event has non-zero probability. I seem to remember (the paper doesn’t seem to be online, and I left my photocopy in my office) he also suggested that this was a substantially better method than using infinitesimal probabilities to represent possible events that seem to have probability 0. But I convinced myself (and probably managed to prove) that in fact, a system using infinitesimal probabilities would be identical to the one van Fraassen endorses, rather than worse. I was going to write this up, but Branden Fitelson mentioned to me that Vann McGee had proven this already, and said it was mentioned in Ernest Adams’ A Primer of Probability Logic.

I finally got around to glancing through the relevant portions of that book a couple weeks ago, and found citations to the article “Learning the Impossible”, in Ellery Eels and Brian Skyrms, Probability and Conditionals. I finally read that article this afternoon, and saw that in fact McGee hadn’t proved the identity of the systems I had thought, but had rather shown that infinitesimals and Popper functions were the same!

So I was about to write up my proof and put it on my website, but I decided to search for van Fraassen’s article first, to remember just what it was I was arguing against there. But on Google Scholar, though I didn’t get the article itself, the first thing that came up that cited it was “Lexicographic Probability, Conditional Probability, and Nonstandard Probability”, by Joseph Halpern, from the CS department at Cornell. I haven’t read the whole thing yet, but it looks like he proves all three systems of conditionalizing on probability 0 to be equivalent using countable additivity, and shows which ones are more general when not making this assumption, or a few others. So it looks like there’s no need for me to write anything up at all, which is too bad I guess. But it looks like a good paper that all philosophers interested in this debate should look at.

Note that all three of these forms of conditionalizing are in general different from the solution I advocate in my paper linked above. I argue that Popper functions overgenerate conditional probabilities, just as Kolmogorov’s ratio analysis undergenerates, and suggest that some probabilities conditional on events of probability 0 should be defined only relative to a set of relevant alternatives to the condition, rather than absolutely as all these approaches require. Teddy Seidenfeld has pointed out in his joint paper “Improper Regular Conditional Distributions” that the method I advocate (initially proposed by Kolmogorov, in fact) runs into some problems in certain spaces. But I think that this just means that in some of these cases there are in fact no conditional probabilities, rather than that they are given by Popper functions.

On What There Is (Or Might Be)

In Quine’s essay “On What There Is”, he suggests that the sorts of entities we are ontologically committed to are all and only the ones that our best scientific theories of the world quantify over existentially, when spelled out in the fullest and most rigorous terms. So if our best theories say that water exists (and I’m pretty sure that no revolution is going to overturn that statement), then we are committed to the existence of water. And if they go on to say that all water contains hydrogen atoms, and all hydrogen atoms contain protons, then we are also committed to the existence of protons (though those two steps are both more conceivable revisable). And if they don’t mention the little green men that push the electrons around the nuclei of the atoms, then we should be committed to the non-existence of those little green men. Anyway, on this view, in developing our best scientific theories, we end up with a large set of axioms and theorems in some formal language. Our ontological commitment is just the sum total of the existential claims in that set, and nothing else.

But this doesn’t fully settle the question of what there is. A theory like Peano arithmetic states the existence of zero, a successor to zero, a successor to the successor to zero, and many other things. But it doesn’t fully specify what there is. As Gödel made painfully clear (though it was already clear before), PA has many different models. The standard model just has the quantifiers range over the natural numbers. In non-standard models, there are extra elements that are strictly greater than any standard natural number, and these elements come in Z-chains (ie, chains whose order type is the same as that of the integers, since each of these extra elements will have to have both an immediate successor and an immediate predecessor). By the Löwenheim-Skolem theorem, there are models of each infinite cardinality. Even if we take the complete theory of the natural numbers (which Gödel showed we can’t access in any computable manner), we have many non-isomorphic models. Each one of them says that different things exist. So what are we committed to?

In this case, it seems fairly obvious. We are committed to the existence of the standard natural numbers, because the standard model embeds elementarily into every other model. That is, not only is every model isomorphic to an extension of the standard model, but also any formula with free variables is true of some elements in the standard model just in case it’s true of their counterparts in any of these other models, so that it’s not just a submodel that happens to satisfy all the same sentences. (An example of the latter is the model of PA where the symbol “0” is interpreted as referring to the number one, and every other numeral is interpreted as referring to the successor of the number it standardly refers to. This model including only the positive integers is a submodel of the standard one, and is isomorphic to it, but the object referred to by “0” in the submodel has the property of being the least element there, but not in the standard model.)

But although we’re only committed to the elements of the standard model here, we should be open to the possibility of the existence of elements from any of the other models. But we shouldn’t be open to the existence of anything beyond these elements. That is, we should be committed to the existence of the standard natural numbers, agnostic about the possibility of further Z-chains, and committed to the non-existence of anything between the standard natural numbers, or less than zero, or otherwise not satisfying the axioms.

To generalize to other theories, I’ll point out that the property I relied on for the standard model of PA here was not merely the fact that it was in fact the standard model, but rather the fact that it embeds elementarily into any other model of PA. In general, for any theory T, if there is a model of T that embeds elementarily into all other models of T, then we call this model a prime model. So I propose an amendment to Quine’s criterion stating that we should be committed to the existence of all the elements of the prime model for our theory (assuming such a model exists), and only the elements that appear in some model for our theory. Thus, on my proposed amendment, the “all” and “only” parts of Quine’s thesis can come apart. Specifying a complete theory doesn’t necessarily specify a unique model, so we can still have some uncertainty in our ontological commitments, though I agree with him that this is the way to find them.

Of course, many theories don’t have prime models, like for instance, any incomplete theory, like PA, as opposed to complete number theory. In such cases I’m less sure what we should be committed to, because there is no “minimum” set of commitments to hold. If there’s some way to determine which objects exist in all the models, then we could be committed to those, even though they won’t themselves form a model of the theory (or else that model would be prime). But of course, there’s not in general any natural way to identify elements of distinct models, unless one model has a canonical elementary embedding in the other. But even if there is no prime model, we can at least look at the domains of all these distinct models and recognize that these objects are the ones that we should be open to, and not anything else.

Quine seems to have been worried only about which ontological categories there are, and these tend not to vary from one model to another of a given theory. But which particular objects exist does, and I think we can use the notion of a prime model to make Quine’s thesis more specific.

Mathematicians Don’t Care About Foundations

This seems to be a largely accurate statement, though of course the existence of dozens and dozens (ok, maybe even hundreds) of mathematicians actively working in set theory, model theory, recursion theory, and proof theory shows that it’s not totally true. It’s interesting that logic seems to have a slightly higher (though still quite low) status within philosophy than in mathematics. And things like modal logic and intuitionist logic seem to be far more widely known in philosophy than mathematics, even among logicians.

Anyway, an interesting post in a mathematics blog I just discovered on the list of academic blogs at Crooked Timber tries to introduce some more logic to mathematicians. Even more interestingly for me, the commenter sigfpe writes:

Mathematicians don’t care about about foundations because they don’t matter! It’s like using a well encapsulated software library. You don’t care what the inner workings are as long as the library performs as specified. If someone came along and completely rewrote the library, only the users who had been exploting the pathological cases might actually notice anything had changed. Same goes for foundations. Even if someone came along and found a contradiction in ZF, say, it would probably be in some really abstruse area, someone would come along with a ‘patch’, we’d have a new set of axioms and 99.99% of published mathematics would remain unaltered.

Something like this is a position I proposed a few months ago when I wanted to come up with a controversial position to take for a panel discussion with some of my fellow graduate students in logic at Berkeley on new axioms in mathematics. After working it out a little bit more, I actually think I believe something like this, though perhaps at a slightly lower level than this person. That is, the reason that we have any standard axiomatizations of mathematics at all is so that mathematicians don’t have to resolve all their disagreements about the philosophy of mathematics. If the platonist, nominalist, and structuralist can all agree that ZFC is a good set of axioms, then they can all return to being productive mathematicians – but if we didn’t have ZFC (or something like it), then they’d have to convince each other that their methods were valid and didn’t presuppose something about the nature of mathematical entities.

As for mathematicians not caring about the mathematical foundations (set theory, proof theory, recursion theory, model theory), that’s a different question. My account predicts that they should care about this stuff at least slightly more than the ontological and epistemological questions. But since specific results in set theory and proof theory are almost never applicable elsewhere, and only restricted amounts of proof theory and model theory seem to have applications, it seems that mathematicians outside of foundations may be able to apply my strategy at an even higher level and ignore what goes on beneath their axioms. Of course, in this case there isn’t disagreement beneath their shared axioms, unlike at the philosophical level.

Fortunately, model theorists seem to be making contact with algebraic geometers and number theorists these days, so maybe some day mathematicians will start caring about the rest of logic again.

(There’s also a connection to Penelope Maddy’s naturalism here – she suggests that mathematicians really shouldn’t care about the philosophical issues behind the axioms, for mathematical reasons. I suggest that the reasons are slightly more sociological.)

Types of Realism in Mathematics

The issues noted in my “Eight Views of Mathematics” have of course been noted by other people before (after all, I was talking about the programs of Field, Steel/Woodin/Martin et al, and Dummett). However, it seems that at least the second one of these questions has been somewhat overlooked in past. Some people (I don’t recall who off the top of my head) refer to the first position as “anti-realism in ontology” and the third as “anti-realism in truth value”, but they don’t seem to have a name for the middle one. Similarly, Mark Colyvan (on p. 2 of his The Indispensability of Mathematics) talks about “metaphysical realism” and “semantic realism”. I suppose I’m tempted to call the third a sort of question of “epistemological realism”, or “realism in evidence” or something of the sort.

The first question is about what objects mentioned in mathematical statements exist, the second is about what mathematical statements we can know, and the third is about what mathematical statements are true or false. Dummett seems to want to link the first and third question. But it seems that most people try to assimilate the middle question to one of the other two. I suppose that’s where it falls to me to defend my position that we can know (or believe or accept) mathematical statements much beyond ZFC without being committed to mathematical objects, or to the claim that all mathematical statements are either true or false. (Though I’m probably agnostic about that last claim, rather than opposed.)

More on Gödel, Structuralism, and Machines

I was just talking to Fabrizio Cariani (one of the other students in my program here) about my earlier post on a version of structuralism that treats elementarily equivalent structures as the same, rather than just isomorphic ones. But he pointed out that although this would avoid the problems of the Löwenheim-Skolem theorems, it still wouldn’t avoid the problem of Gödel’s incompleteness theoresm. That is, we need to have a complete theory to specify a structure completely in this sense, but Gödel’s incompleteness theorems show that no recursive theory extending Peano arithmetic or ZFC is complete, so we can’t even pin down the natural numbers or the sets to this extent. It’s sort of nice that the platonist account of mathematical objects runs afoul of isomorphic models, the standard structuralist account runs afoul of the Löwenheim-Skolem theorems, and the “elementary equivalence structuralist” account runs afoul of the Gödel theorems.

Fabrizio had been thinking about this because he had just been looking at the result that there are continuum-many non-equivalent countable models of PA. This is because for any recursive, consistent theory T extending PA, Gödel shows that T+Con(T) and T+~Con(T) are both recursive, consistent theories extending PA. Thus, there is a complete binary tree of such theories, and by the compactness theorem, each infinitary branch of the tree is a consistent theory extending PA. Since any two such branches differ at some stage over whether they add Con(T) or ~Con(T), the models of the theories are going to be non-equivalent, so there are continuum many non-isomorphic models. (This is also the theoretical upper bound on the number of countable models for any theory in a finite language, because there are only countably many objects and tuples of objects, and for each of the finitely many predicates and relations in the language, there are two choices for each tuple of the appropriate size.)

Now, returning to yesterday’s post on mechanism, I think Lewis’ point is stronger than I had thought originally. In the comments, Peter McB suggests that there is a machine that takes any consistent, recursive theory T extending PA and outputs the sentence Con(T). Now that I think about it, I think the procedure Gödel himself used is amenable to this sort of recursive construction. Now, for any countable string of 0’s and 1’s, we can use this machine to recursively enumerate an axiomatization for some consistent extension of PA, by letting T_0 be PA, and using the machine to enumerate the axioms Con(T_i) or ~Con(T_i), depending on whether the ith bit of the string is 1 or 0. The fact that these enumerations are recursive in the string doesn’t violate Gödel’s theorem, because it just means that the theory PA + Con(PA) + Con(PA+Con(PA)) + … is itself not a complete theory. And similarly for the theory PA + ~Con(PA) + ~Con(PA+~Con(PA)) + …, and so on for any other theory given by some recursive string of 0’s and 1’s.

Now, it seems intuitive to me that no such theory is going to be complete, but Gödel’s theorem only tells us that the ones produced by recursive strings of 0’s and 1’s aren’t complete. Is it possible that some non-recursive string of 0’s and 1’s gives a complete theory? That would be weird. I suppose recursion theorists might have a better idea about this.

Lewis on Lucas on Gödel

I recently bought David Lewis’ Papers in Philosophical Logic and have been reading some of the essays recently, starting with the shorter ones. I hadn’t remembered how engaging his writing style is.

Anyway, I should probably read Roger Penrose again some time, but from what I remember of his theses in The Emperor’s New Mind and Shadows of the Mind, it looks like they were pretty soundly refuted long before he wrote the books. This was by Lewis in his two papers “Lucas against Mechanism” and “Lucas against Mechanism II”. The first one just makes the point that the inference rule from a theory to its consistency statement is in general infinitary, and thus can’t clearly be run in general. But the second one faces a tougher argument, because of the way Lucas seemed to moderate his position. (I haven’t actually read Lucas, or even heard of him before reading these two papers by Lewis, but it sounds like he was advocating the same position that Penrose did, that our ability to recognize Gödel statements proves that humans are not Turing machines.)

In the second paper, Lewis phrases Lucas’ argument as a challenge to the mechanist to produce a Turing machine that generates exactly the set of truths that Lucas recognizes to be true. Lucas can then find the Gödel statement of this machine and recognize it to be true, which shows Lucas not to be this actual machine. But Lewis points out that since this allows Lucas to respond to challenges, the machines proposed must also be the sort that can respond to challenges. So if the mechanist proposes that Lucas is the machine M, then Lucas might either be responding with the Gödel number of the machine M, or with the Gödel number of the machine M would turn into in response to a challenge with the number M. But Lewis claims that there are many machines that make the former response to any true accusation that they are M, and there are many machines that (falsely) make the latter response to any true accusation that they are M, so Lucas’ ability to give such a response doesn’t prove him not to be a machine.

This is where I would like a bit more clarification. At first Lewis’ claim sounded ridiculous, because it sounded like his response to the former was a machine that takes any input and responds with the Gödel number for that input, which sounds impossible to me. (Maybe I’m wrong about that?) Now I think that he actually meant something more like a machine that gives the same response to any challenge, and this response just happens to be its own Gödel number. After all, Lewis only required it to function right on true challenges to its identity. I wish I could link to the text of the article (it’s just 4 pages), but the Canadian Journal of Philosophy seems not to have its issues from 1979 online.

(The reason I filed this under the category “set theory” is because of the last few lines of the first “Lucas against Mechanism”:

We do not know how Lucas verifies theoremhood in Lucas arithmetic, so we do not know how many of its theorems he can produce as true. He can certainly go beyond Peano arithmetic, and he is perfectly justified in claiming the right to do so. But he can go beyond Peano arithmetic and still be a machine, provided that some sort of limitations on his ability to verify theoremhood eventually leave him unable to recognize some theorem of Lucas arithmetic, and hence unwarranted in producing it as true.

This is I think exactly what set theorists are doing – trying to see just how far beyond PA (and in fact, beyond ZFC) they can go.)

Naturalism in Mathematics?

Warning: the views expressed here are caricatured representations of papers that I’ve read through somewhat, but not carefully enough yet. They’re probably not actually the views of the philosophers mentioned.

Penelope Maddy makes a distinction in the philosophy of mathematics between questions that are “methodological” and ones that are “philosophical”. On her preferred view (which she calls “naturalism”), it is primarily the former that are actually interesting questions. The idea is that questions that tell us which sets of axioms to pursue are useful to actual mathematical practice, whereas questions about how we can know that 2+2=4 don’t seem to be. (That is, if they tell us that we don’t know this fact, then we can’t really do any math, and if they tell us that we do, then we’re right back where we started.) However, these methodological questions are principally the domain of mathematicians and “naturalistic philosophers of math”, who have basically become real mathematicians without the occasional philosophical worries. In a sense, this would suggest that philosophical questions properly stated can’t be relevant to mathematical practice.

However, during FEW I came up with what seems to be a reductio of this position:

1. If mathematicians care about question Q, then the answer should be relevant to their practice. (This seems clear if we’re talking about mathematicians caring about the question qua mathematician, and if they’re doing their job right.)

2. Philosophical questions can’t be relevant to mathematical practice. (This is my caricature of Maddy’s naturalism.)

Therefore,

3. No question mathematicians care about is philosophical.

However, this seems clearly false. I recently stumbled upon an article in the 1994 Mathematical Intelligencer by Bonnie Gold that basically just lists dozens of philosophical questions about mathematics that are interesting to mathematicians (and in many cases, much more interesting to mathematicians to philosophers). For example, “What is common to those subjects (e.g., algebra, analysis, topology, geometry, combinatorics, category theory) that are classified as mathematics which causes us to classify them, but not other subjects, as mathematics?” Or “Is mathematical knowledge more sure than other forms of knowledge? It seems so …, but is that simply an illusion?” Many of the other questions in the article seem more directly sociological than philosophical, but these ones seem philosophical to me. And I don’t think she’s being derelict in her duties as a mathematician to wonder about these questions.

I think premise 1 seems pretty clear. If we were to come up with a good classification of some subjects as mathematics and some as not, it seems that this would provide some insight into useful methods for mathematical work, and ideas for new fields of mathematics that haven’t been studied yet. And if mathematical knowledge can be shown to be no more sure than other forms of knowledge, this would increase the importance of alternate proofs and double-checking in mathematics. So the fault must lie with premise 2, which I’m guessing is therefore a misreading of Maddy’s position. Perhaps it’s because she’s using “philosophical” as almost a technical term, separating off all the “methodological” questions from it. If philosophical questions are just defined to be the ones that have no relevance to the working mathematician, then there’s no problem. But the questions mentioned above do strike most people as at least somewhat philosophical.

I think the real answer is that I’ll have to re-read some of Maddy’s more recent papers, and actually read her book “Naturalism in Mathematics”. I think she’s right to reject at least some seeming questions in the philosophy of mathematics, but it does generally seem to me that she goes a bit farther than I’d like.