Math Links Roundup

16 09 2007

First, I’ll mention that I’ve updated my blogroll – there’s been a real burst in math blogs over the summer, at least in part instigated by my friends at the Secret Blogging Seminar, but also by the spurt of Fields Medalists with blogs. (Are we up to 10% of the total number now?) I’ve also added a few philosophy blogs that I’ve been reading for a while, and a couple that I should have been reading, but of course I’m sure I’m missing others.

Anyway, there’s new math job search gossip stuff going on on the web – I think the discussion on that post is interesting and relevant across disciplines for people trying to figure out whether this is generally a good thing or not.

Tim Gowers discusses the way logarithms and other abstract things should be taught. He advocates a way that’s a bit more formalist than some others suggest, but it sounds reasonable to me. There’s also interesting discussion of formalism there in the comments, though some of it sounds more like structuralism to me. See for example Terence Tao’s comment, “I guess there is a fundamental transition in mathematical learning when one realises that what mathematical objects are (and how they are constructed) may be less important than what mathematical objects do (e.g. what properties they obey).”

Also, a discussion about the Axiom of Choice at The Everything Seminar (I may add that one to my links later too), focusing on a puzzle I first heard from my friend Lukas Biewald. There’s interesting discussion in the comments that reveals implicit ideas about platonism and formalism among mathematicians. I think the anti-platonist majority there should be a bit more careful though, because similar issues apply in arithmetic, thanks to Gödel’s results. I think we should be much more hesitant to say that the natural numbers are just something we make up than they are with the universe of ZFC (or a topos, or whatever), as I mentioned before.

Mathematical Existence

2 05 2007

Last night, I mentioned to my roommate (who’s a mathematician) the fact that some realist philosophers of mathematics have (perhaps in a tongue-in-cheek kind of way) used the infinitude of primes to argue for the existence of mathematical entities. After all, if there are infinitely many primes, then there are primes, and primes are numbers, so there are numbers.

As might be expected, he was unimpressed, and suggested there was some sort of ambiguity in these existence claims. He wanted to push the idea that mathematically speaking, all that it means for a statement to be true (in particular, an existence statement) is that it be provable from the relevant axioms. I was eventually able to argue him out of this position, but it was surprisingly harder than expected, and made major use of the Gödel and Löwenheim-Skolem-Tarski theorems.

The picture that is appealing to the mathematician is that we’re just talking about any old structure that satisfies the axioms, just as is the case when we talk about groups, graphs, or topological spaces. However, I pointed out that the relevant axioms for the natural numbers can’t just be Peano Arithmetic, because we’ll all also accept the arithmetical sentence Con(PA), once we’ve figured out what it’s saying. This generalizes to whatever set of axioms we accept for the natural numbers. As a result, Gödel’s theorem says that we don’t have any particular recursive set of axioms in mind.

To make things worse for the person who wants to think of the natural numbers as just given by some set of axioms, there’s also the fact that we only mean to count the members of the smallest model of PA, not any model. By the LST theorem, any first-order set of axioms that could possibly characterize the natural numbers will also have uncountable models. In order to pick out the ones we really mean, we either have to accept some mathematical class of pre-existing entities (the models of PA, so we can pick out the smallest one), or accept a second-order axiomatization, or give up any distinction between standard and non-standard natural numbers.

Of course, the same argument can be run for set theory, and at this point, accepting a second-order axiomatization causes trouble. Some philosophers might argue a way around this using plural quantification, but at least on its face, it seems that second-order quantification requires a prior commitment to sets, so it can’t underlie set theory. And we really don’t want to admit non-standard models of set theory either, because they give rise to non-standard models of arithmetic, which include certain infinite-sized members as “natural numbers”.

So it seems, for number theory and set theory at least, the mathematician has to admit that something other than just axioms underlies what they’re talking about. I’ve argued that the existence of and agreement on these axioms means that mathematicians don’t often have to think about what’s going on there. And from what I can see so far, the mathematician could take a platonist, fictionalist, or some other standpoint without any trouble. And in fact, most of the reasoning is going on at a high enough level that even if there’s some problem with the axioms (say, ZFC turns out to be inconsistent) this will have almost no effect on most other areas of mathematics, just as a discovery that quantum mechanics doesn’t correctly describe the behavior of subatomic particles will have relatively little effect on biology. But the mathematician can’t insist that existence in mathematics just means provability from the axioms – she can insist on some distinction between mathematical existence and ordinary physical existence, but it will be something like the minor distinction that the platonist recognizes, or possibly something like the distinction between real and fictional existence.

Structural Axioms and Terminological Disputes

28 09 2006

When I presented my paper on the role of axioms in mathematics in Berlin, one comment I got from several people (which I’ve also gotten from some mathematician friends) was that the project falls apart in my second footnote. Basically, they want to treat all sets of axioms as structural, rather than allowing for a class of foundational axioms, encompassing something like Peano Arithmetic or possibly ZFC or some replacement. The idea is that any consistent system of axioms describes some mathematical structure (of course, only some of those structures are actually of interest to us), but there isn’t an intended model (like the actual natural numbers, or actual sets) to fall back on to extend these sets in a natural way. The Peano axioms show us some results that are useful when counting, but there isn’t some unique structure beyond this practice that fills in truth values for further claims. So the project of wondering whether we should look for new axioms falls apart. I wasn’t able to really say anything terribly convincing at the time, but I think I’ve got some general ideas now.

About a week later, I was discussing David Chalmers’ talk on terminological disputes with some friends in the department here, and I realized that this is a useful way to motivate the distinction between foundational and structural axioms. Consider any dispute over some axiom – say one mathematician says that in every ring there is an element such that multiplying it by any other element fixes the other element, while another mathematician denies that this is in general true. Consider another dispute – say one mathematician says that in the natural numbers, every element has a successor, while another denies that this is in general true. In the former case, it seems that there’s just a disagreement in terms of what we mean by “ring” – some people build in commutativity and identities, while others don’t. The disagreement is merely terminological. However, the ultrafinitist who denies the successor axiom isn’t engaged in a merely terminological dispute. We both intend to be talking about the counting process. We know what the other means by natural numbers, and say that they’re wrong in terms of what they claim. This dispute is not merely terminological.

The fact that there can be disputes like this, that aren’t about logical consequence and aren’t merely terminological, suggests that the axioms involved are in fact of this other “foundational” type. This doesn’t necessarily mean that they provide a foundation for the rest of mathematics, but just that they play a different sort of role. And this is the role that I am concerned with.

Structuralism and Application

2 02 2006

One form of structuralism says that mathematics is just the proving of theorems from axioms, which may or may not hold of (or approximate) various real systems. Something like this is clearly right for things like topology, group theory, and the like – when we prove something about topological spaces (or better yet, about compact hausdorff spaces), we don’t mean to prove it of any particular thing, but rather just know that whenever we find some entity that satisfies the axioms of topology (plus the compact hausdorff axioms), the theorem will be true of this entity. Whether or not there is such an entity is almost a side concern, though the fact that they seem to arise in various areas of mathematics convinces us that the theorems are likely to be useful.

The structuralist says that this is the case with Peano arithmetic, and set theory as well. We’re not proving anything about actual numbers or sets (like the platonist claims) – we’re just proving theorems that will hold of any entities that happen to satisfy the axioms we use. Something like this seems to be the position of Saunders Mac Lane in his 1997 paper “Despite Physicists, Proof is Essential in Mathematics” (Synthese 111:147-154),

However, this position seems problematic, because it doesn’t explain how we are justified in many of our applications of mathematics. (Platonism and fictionalism don’t obviously work much better, but I think I can sketch an account of how they at least partially justify us in these applications.) If our theorems about real numbers are just theorems about whatever happens to satisfy the real number axioms, rather than about anything independently existing entities, then to apply the theorems, we would need to show that the system we’re applying it to satisfies the axioms. So in order to apply the intermediate value theorem to distances, we’d need to show that distances are dense, linearly ordered, have no endpoints, and are topologically complete. In order to apply them to probabilities, temperatures, electric charges, masses, times, and the like, we’d need to show that these axioms apply to each of those domains. However, it seems unlikely to me that we’ve actually shown that any of these quantities satisfies the real number axioms, much less all of them.

The platonist has a way out by saying that (somehow) we’ve discovered facts about these entities we call real numbers, which aren’t the physical entities we’re talking about. Instead, we see that in each of these physical situations, our investigation reveals that there is some sort of abstract entity involved, and we can use inductive reasoning to suggest that the real numbers are the appropriate ones. Thus, even if we can’t directly support the infinite divisibility, or the topological completeness, of any of these realms, we might be able to inductively support them by inferring that the reals (a structure we already know about) would give the best explanation of the phenomena we’re observing. If we had to restrict ourselves to a set of structural axioms that we knew to hold, we’d have to convince ourselves that some closely related set of axioms wouldn’t be better. If the platonist has a reason for thinking that the real numbers are a special set of entities, then we could infer this convergence on one set of axioms without having to establish it completely independently each time.

Resnik’s “Euclidean Rescues”

11 01 2006

Mike Resnik’s book Mathematics as a Science of Patterns gives a picture of mathematics that I generally agree with. He takes something like a Quinean position, saying that mathematics, logic, science, and observation are all together in our web of belief, and the process of confirmation is always global. Any statement in the web is in principle revisable. However, we still have the intuition that particular experiments test particular components of our theory individually, because a change in that component wouldn’t reverberate as much through our web of belief. We are free to make the larger changes if further experiments eventually suggest that it would be correct, but the changes involved would often be so drastic as to be effectively ruled out. Thus, we get the illusion of non-holism in our practice of confirmation.

Resnik denies that mathematics is in some absolute sense a priori – instead, it is just more general than any science and therefore less susceptible to refutation, due to the greater effects any change on it would have in all our other beliefs. “The relative apriority of mathematics is thus due to its role as the most global theory science uses rather than to some purely logical considerations that shield it from experiential refutation. The same good sense counsels us to use Euclidean rescues to save our mathematical hypotheses from empirical refutation, that is, to save them by holding that a putative physical application failed to exhibit a structure appropriate to the mathematics in question.” (p. 173) He calls such a move a “Euclidean rescue” by analogy with the case of Euclidean geometry – when Einstein and others gave evidence showing that physical space did not obey Euclidean geometry, geometry was reinterpreted as being about abstract points and lines, ratehr than physical ones as had always been presupposed. Every non-Euclidean geometry contains within it models of Euclidean geometry, so we can save the truth of Euclid’s theorems by saying that he was talking about these models, rather than actual space.

However, it’s not clear if his notion of a Euclidean rescue really allows us to shield our web of belief from the repercussions of a change. Let’s consider an example. Say at some hypothetical future point in time, people have been led to adopt some axiom A of number theory that goes beyond PA (since PA is relatively weak, this might even be some consequence of ZFC, but it might not be). Because this axiom will be taken to be true of our concept of number, it will end up having an impact on various complicated computations in the natural sciences. But then let’s say that our notion of physics has also progressed to the extent that we have theoretical justification for saying that a particular machine can carry out a hypercomputation. (That is, it can carry out steps in exponentially decreasing amounts of time, so that it can go through an entire sequence of omega steps in a finite amount of time.) We can then use such a machine to check a simple universally quantified statement of number theory, let’s say C, and assume that C is a consequence of PA+A. If the machine tells us that C is false, then we can either say that our physical theory was wrong in saying that the machine accurately models hypercomputation, or reject PA+A as our correct number theory, or possible revise logic in some way so that C is no longer a consequence of PA+A.

Clearly, the last option is going to be unpalatable, because this will have repercussions throughout our entire web of belief. Ordinarily, we would use this experiment to reject our physical theory (as we reject the theory that a calculator is built in a certain way, if it tells us that 3+5=7), but in this case it seems that the justification for A is likely to be much weaker than that for PA, and possibly even weaker than that for our physical theory. In that case, the right thing to do is reject A.

Resnik suggests that then, for purposes of minimal mutilation of our overall theory, we should perform a Euclidean rescue on PA+A, and say that it’s not meant to be a theory of the actual notion of number, but just some other structure (say, “schmumber”). That’s fine as far as it goes, but it doesn’t prevent us from having to take back many of the other empirical consequences of A that we derived earlier – all of those were derived from A’s role as an axiom about number, not schmumber. So performing the Euclidean rescue doesn’t save us from having to revise large parts of our web of belief. Of course, revising the physical theory might be just as bad (especially if it’s a fairly far-reaching theory, and the number-theoretic statement is of relatively limited application), so we’ll have to make drastic changes of this sort no matter what choice we make. But I’m just suggesting that Resnik is wrong to say that the Euclidean rescue can prevent most of this revision.

“Because one can always save a consistent branch of mathematics via a Euclidean rescue (and we have assumed that our mathematicians have excluded this), for them to reject the axioms of ZFC+A would be to take them to be inconsistent!” (p. 134) He’s right that we probably won’t want to say just because of this calculation that PA+A is inconsistent. But saying that it is consistent but false is not the same as attempting a Euclidean rescue – we don’t automatically have a structure that realizes the axioms, the way we actually did in the Euclidean case as a subset of physical space.

His statement that a Euclidean rescue is possible for any consistent theory presumes Gödel’s completeness theorem, which guarantees that every consistent theory has a model. If ZFC is true (or a certain fragment of it at least) then we have the completeness theorem. In fact, even if ZFC is false as a set of statements about sets (the way four dimensional Euclidean geometry is false as a set of statements about actual space-time), but we have performed a Euclidean rescue on it to say that it talks about some domain other than the “actual sets”, then we can use the rescued completeness theorem to give us a domain (not necessarily among the actual sets) for any consistent theory we want to talk about.

But this means that if some piece of empirical evidence were to challenge ZFC (or some principle of the weaker system that proves the completeness theorem), we wouldn’t immediately be justified in performing a Euclidean rescue on it, the way we can be for another theory in the context of ZFC. We would either have to be rejecting it in favor of some theory that proves ZFC has a model, or else we would have to have other reason to believe that a structure supporting the rescue exists.

One reason Resnik might presuppose all of ZFC is that it seems to be necessary for an adequate (Tarskian) account of first-order logical validity. But in the very difficult section 8.3 of his book, he endorses something like a relativist view about logic. (Not that the truth of logical sentences is relative, but merely their status as logical truths, rather than other sorts, is relative.) I’ll have to read this section again more closely, and I’d be glad if any readers could help clarify it for me. But at any rate, it doesn’t seem clear to me that a role in explicating logic would make ZFC indispensable on Resnik’s account, so it’s not clear how he gets ZFC off the ground to perform his Euclidean rescues later on. (Unless he just means that for us (ie, people who believe in ZFC) a Euclidean rescue is always possible for mathematical theories.)

The only way a Euclidean rescue can prevent large-scale mutilation of our web of belief is if we can find a structure closely related to the original one, for which the theory actually is true. But the only way to be sure we can always provide a Euclidean rescue seems to be through the completeness theorem, which doesn’t guarantee that the new structure is at all related to the old one. So his two uses of Euclidean rescues seem to work at cross purposes with one another.

On What There Is

13 07 2005

In thinking about an idea that I had earlier about just what entities we might be committed to, I was rereading Quine’s essay “On What There Is”. On going through it again though, I realize that he seems to endorse another idea I once had about a form of structuralism more extreme than the standard one. He seems to shy away from saying that we’re committed to the existence of certain entities, instead saying that we’re committed to the existence of entities satisfying certain properties. Thus, he seems to be advocating a much more linguistically-driven picture of the world than one might have supposed otherwise. Although this paper is often considered the one that restored metaphysics to philosophy, he seems to restore it only in an extremely deflated way. He suggests that we use science and philosophy (and the rest of our means of explaining the world) to come up with the best theory of the world, and that we merely endorse that theory. All that it means for us to say something exists is for an existential claim of appropriate form to appear in that theory. Thus, we aren’t in a sense talking about the thing itself (because any object could play the same role in an appropriate model of the theory), and we can’t even say anything about how many objects of a certain type there are unless there are finitely many. So in a sense it can’t make sense on this picture to say there are countably many natural numbers and uncountably many reals. We can just say there is no function pairing them up.

Also, for this same project I’m working on (about analyzing whether a Quinean view like this can even say what sorts of things there are) I’d like to use a many-sorted logic. I basically know how this sort of logic works (and can refer to my notes from my model theory class in case i forget), but I’d like to have some sort of reference I can cite. Does anyone know of a logic book that talks about many sorted logic as well as traditional one-sorted first-order logic?

More on Gödel, Structuralism, and Machines

4 06 2005

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.