![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslI'd like to see probability and measure theory reformulated in a theory where the Axiom of Choice isn't used. Non-measurable sets would never come up.
http://en.wikipedia.org/wiki/Non-measurable_set
Now every subset of the reals is measurable, and has the Baire property. Thus: a lot fewer concepts to worry about! And no more Banach-Tarski paradox.
Do we lose anything, really?
The idea that the only objects that exist are the constructible ones is, I think, a central idea in the worldview of computer scientists, who are, afterall, the current bearers of the intuitionistic flame; besides being central figures in ideas like cognition is computation, and so is the universe. To me, it's a direct consequence of thinking of the world (including ourselves) as machines; and the alternative borders on mysticism (a.k.a. metaphysics).
Coming back to mathematics, why don't I see any computer scientists working on Choice-free mathematics? And why don't I see mathematical librarians cataloging which bits of mathematics are still kosher, according to constructivists? I'd love to see a choice-free graduate mathematics curriculum, but I'd be happy to just see a book on Probability.
http://en.wikipedia.org/wiki/Non-measurable_set
<< In 1965, Solovay constructed Solovay's model, which shows that it is consistent with standard set theory, excluding uncountable choice, that all subsets of the reals are measurable. >>
Now every subset of the reals is measurable, and has the Baire property. Thus: a lot fewer concepts to worry about! And no more Banach-Tarski paradox.
Do we lose anything, really?
The idea that the only objects that exist are the constructible ones is, I think, a central idea in the worldview of computer scientists, who are, afterall, the current bearers of the intuitionistic flame; besides being central figures in ideas like cognition is computation, and so is the universe. To me, it's a direct consequence of thinking of the world (including ourselves) as machines; and the alternative borders on mysticism (a.k.a. metaphysics).
Coming back to mathematics, why don't I see any computer scientists working on Choice-free mathematics? And why don't I see mathematical librarians cataloging which bits of mathematics are still kosher, according to constructivists? I'd love to see a choice-free graduate mathematics curriculum, but I'd be happy to just see a book on Probability.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Computable Mathematics & Metaphysics
Date: 2010-09-13 10:49 am (UTC)I do not think of myself as a computer scientist, but I have had similar thoughts cross my mind on many occasions...
I had been thinking about it more in terms of real numbers. If we believe ZFC, then most reals are uncomputable, which seems very odd. It means there are real numbers out there which we look like quite ordinary say: 15.73632221097... but there is no algorithm capable of predicting to an arbitrary degree of accuracy what the next digit is going to be! Isn't that just weird?
You can only compute these non-computable reals if one starts using oracle machines! But there you have it! All of a sudden you have to postulate the existence of something mystical! Granted oracle machines are just turing machines with an added strip in which there is a non-computable sequence of 0 and 1's. But once again, you have to postulate the existence of one uncomputable number in order to start computing other uncomputable numbers!
Also, are these non-computable reals useful to us in any way? They certainly don't play any role in engineering or the natural sciences. At best, it makes things look elegant because you can prove the completeness of the Reals. I wonder how much we would actually lose if we restricted ourselves to computable reals. Would the Bolzano Weirstrass Theorem still be true? My guess would be yes, but I am not entirely sure...
Ultimately, I think we do mathematics the way we do, with the axiom of choice and so forth because of behavioral momentum. One generation of mathematicians passes on the historical way in which things have been done to the next generation and so forth.
There is one way in which one could perhaps reconcile non-computable mathematics without going down the path of "mysticism". There are non-standard models of computation such as analog computation and biological computation. If you are willing to believe that objects in the physical world are not digital and exist on a continuum just like the real numbers from ZFC, then by engaging in analog computing you could conduct computations on non-computable numbers! You would in essence have a real life oracle machine!
The problem once again is that by hypothesizing that the universe is continuous or digital, you are already making a fairly strong metaphysical claim about how the universe actually is!
Alas, as much as I am a logical postivist at heart, there seems to be no escape from metaphysics!
Henrik Nordmark.
Re: Computable Mathematics & Metaphysics
Date: 2010-09-13 02:13 pm (UTC)If you limit yourself to only computable reals, you don't even have the Intermediate Value Theorem. It's fairly easy to give computable functions whose only roots are noncomputable.
Ultimately, I think we do mathematics the way we do, with the axiom of choice and so forth because of behavioral momentum. One generation of mathematicians passes on the historical way in which things have been done to the next generation and so forth.
Mathematicians use the axiom of choice because it captures the way of reasoning they use. I think most mathematicians would like (within the bounds of what is possible) for an axiom system to be determined by the way they reason about mathematics, not the other way around. In general, there is a big difference between "I know something exists" and "I can build a copy of it." If you don't think these are different, you should probably reject, say, astrophysics while you're at it. You aren't going to build a black hole in your basement either. (I hope.)
Re: Computable Mathematics & Metaphysics
Date: 2010-09-13 05:11 pm (UTC)Hmmmm... I must admit that not having the Intermediate Value Theorem would be counterintuitive.
:-S
I guess it is something one could get used to, but it might not be worth the trouble to do so for the sake of adhering to a philosophical view that favors the computable.
Mathematicians use the axiom of choice because it captures the way of reasoning they use.
Yes, I agree. What I am pointing out though is that mathematicians reason the way they do because they have been trained to reason in a certain way and this way of reasoning developed within a certain socio-historical context.
After all, we could teach limits and real analysis using infinitesimals and some of the proofs might even seem more intuitive to students than using epsilon-delta definitions. Nevertheless, the traditional way of reasoning about this and of teaching this to the next generation of mathematicians is by using good old epsilon-delta definitions.
In general, there is a big difference between "I know something exists" and "I can build a copy of it."
Generally speaking, yes that is true. In the specific case of mathematics, that depends on your philosophical views. If you are an intuitionist like Brouwer then the only mathematical objects that exist are those that can be "constructed" using certain valid processes.
Mind you, I am not advocating intuitionism! Brouwer's mathematical universe is very strange indeed... Natural numbers exist, but the set of all natural numbers doesn't. And when you get into real analysis things become even more bizarre... All functions are continuous! It is an interesting curiosity, but I am not sure I would have the patience to relearn whole branches of mathematics in an intuitionistic setting!
@ Gustavo: Would you prefer if we lived in a world where mathematicians only used intuitionistic mathematics?
Re: Computable Mathematics & Metaphysics
Date: 2010-09-13 05:24 pm (UTC)While I think it would be a good thing for mathematicians to think about foundational underpinnings more, it's not like the usual formalizations were arrive at in a random way. For a substantial part of the 20th century, the axiom of choice was definitely view with varying degrees of skepticism, and it took a while for it to become something resembling the consensus view. In this regard, I view it like many of the other underpinnings of modern mathematics -- it's worth thinking about from time to time, to convince yourself they are the right choices. But in the day to day work of doing math, being obsessed with these issues is more of a distraction than a help.
After all, we could teach limits and real analysis using infinitesimals and some of the proofs might even seem more intuitive to students than using epsilon-delta definitions. Nevertheless, the traditional way of reasoning about this and of teaching this to the next generation of mathematicians is by using good old epsilon-delta definitions.
The trouble with the infinitesimal approach is that to make it rigorous requires a lot more high powered math. There are more pedagogical advantages as well: delta-epsilon arguments make students grapple with limits in a concrete way, and to deal with the interplay between formal definitions and there more geometric intuitions. I'm not sure if I'm sold on the value of delta-epsilon arguments for introductory calculus courses, but in a first real course in analysis, I think it's definitely the right choice.
Re: Computable Mathematics & Metaphysics
Date: 2010-09-13 05:50 pm (UTC)Once again, we are in agreement. Clearly, there are factors that have led to the sociological agreement that exists within the mathematical community today. And these factors are not merely happenstance. Within the historical context in which mathematics developed, there were good reasons for the choices that were made.
Having said that, we could imagine history developing slightly differently... And although the core of mathematics would probably be the same, there are some things that we might be doing differently. I could certainly imagine a world in which set theory did not become the dominant foundational system.
In this regard, I view it like many of the other underpinnings of modern mathematics -- it's worth thinking about from time to time, to convince yourself they are the right choices. But in the day to day work of doing math, being obsessed with these issues is more of a distraction than a help.
Agreed.
Re: Computable Mathematics & Metaphysics
Date: 2010-10-01 10:27 pm (UTC)But maybe that leads to some very clunky formulation of things that are done more elegantly by using the standard axioms, à la some mathematical version of Greenspun's Tenth Rule.
(no subject)
Date: 2010-09-13 02:04 pm (UTC)You lose all sorts of things, like the Hahn-Banach thereom.
Now every subset of the reals is measurable, and has the Baire property. Thus: a lot fewer concepts to worry about! And no more Banach-Tarski paradox.
There aren't fewer concepts to worry about. You've suddenly walled off a hole host of very natural arguments because you've decided there's something immoral about nonmeasurable sets.
The idea that the only objects that exist are the constructible ones is, I think, a central idea in the worldview of computer scientists, who are, afterall, the current bearers of the intuitionistic flame;
I'm not sure what you mean by constructible (and I'm suspicious that you don't either). If you mean it the way set theorists mean it, then limiting yourself to such a universe tends to encourage pathologies, not remove them. (E.g. in the constructible universe, there are definable well orderings of the reals and definable nonmeasurable sets.)
To me, it's a direct consequence of thinking of the world (including ourselves) as machines; and the alternative borders on mysticism (a.k.a. metaphysics).
On some implicit level, I think I do buy into the idea that the universe is mechanical and predictable. But there's a big leap from this to the fact that it is completely deterministic and computable. If nothing else, quantum mechanics already tells us that.
Coming back to mathematics, why don't I see any computer scientists working on Choice-free mathematics?
I'm not sure why you linked to LEM free mathematics when referring to choice freeness. But in any case, there are plenty of cases where reasoning about infinite objects yields information about very concrete and finite ones. E.g. the application of ergodic theory in combinatorics has been very fruitful (see here).
(no subject)
Date: 2010-09-13 06:15 pm (UTC)There are in fact some new concepts to worry about. For instance, there's a difference between the existence of an injection from A to B and a surjection from B to A. (The existence of an injection one way guarantees a surjection the other way, but not vice versa.) There's a distinction between well-orderable cardinals and non-well-orderable cardinals.
In fact, one argument that some intuitionists give is that by working with LEM and AC we collapse many distinctions that they feel should be important.
(no subject)
Date: 2010-09-13 09:12 pm (UTC)This seems to accord better with the intuitions of people working in the field; people seem to find it easier to start with all conceivable tools, and then once you have an argument, pare it down to ask what's really necessary. Often the result is that one starts with a proof using choice, and then discovers that the use of choice was non-essential.
(no subject)
Date: 2010-09-13 09:47 pm (UTC)Hang on... aren't you working on proof-mining??
(no subject)
Date: 2010-09-13 09:54 pm (UTC)Conversely, unlike with cut-elimination, one isn't often guaranteed that a choice-free proof exists. Instead, it's a matter of doing some additional real mathematics to verify that there is such a proof. (And yes, I'm working on proof-mining, which is why I spend a lot of time thinking about these concerns; and yes, there's some overlap with ideas from descriptive set theory, which is part of why I'm in Los Angeles, the world capital of descriptive set theory.)