The Axiom of Choice
The axiom of choice is a fascinating bugger. It's probably the most controversial statement in mathematics in the last century - which is pretty serious, considering the kinds of things that have gone on in math during the last century.
The axiom itself is quite simple, and reading an informal description of it, it's difficult to understand how it managed to cause so much trouble. For example, wikipedia has a rather nice informal statement of it:
given a collection of bins each containing at least one object, exactly one object from each bin can be picked and gathered in another bin
There are also a bunch of statements that are equivalent to that - some of which can be pretty astonishingly different, so that it can be quite difficult to see why they're equivalent. So, for example, here are a few equivalent formulations:
- Given any two sets, one set has cardinality less than or equal to that of the other set -- i.e., one set is in one-to-one correspondence with some subset of the other.
- Any vector space over a field F has a basis -- i.e., a maximal linearly independent subset -- over that field.
- Any product of compact topological spaces is compact.
- Any set of non-empty sets has a non-empty cross-product.
The first of those alternative formulations shows why the axiom of choice is so important - and why it's so controversial. It's the axiom of set theory that lets us compare the cardinality of sets, and therefore (among other things) makes Cantor's diagonalization work in axiomatic set theory.
How do we get from the simple statement that given a collection of non-empty bins, we can select one item from each bin, to the seemingly more profound statement that for any two sets - even infinite ones, one has cardinality less than or equal to the cardinality of the other?
Let's start with the simple statement, but add a bit of detail: Given a collection of not-empty bins, it's possible to select one item from each bin. One added detail is that this works even if there's an infinite number of sets. Another one is that you don't need to be able to specify a rule to describe how to do the selection.
Now, with that restatement, we can, instead say: for any class of non-empty sets X, there exists a choice function f such that for each x∈X, f(x)∈x.
Next, we can go from that statement to something a little closer, by saying that for anf set X of non-empty sets, where S∈X, and p∈S, then there is a choice function f on X such that f(S)=p. And further, for any set of values {pi : i∈X and pi∈i}, there is a choice function f on X where f(i)=pi.
From that, it's relatively straightforward to get an infinite set of choice functions assigning a relationship between members of different sets of X. And that in turn gives us the result that we want: if we have a pair of sets S and T, then one of two things can happen: either there's a set of choice functions that creates a one-to-one map between S and T, or there isn't. If there is, then the two sets have the same cardinality. If not, then one set is smaller than the other.
That argument shows why the axiom of choice has been so controversial: it's all about arguments for existence, with no way to construct the things that we argue must exist. In fact, there are cases where we can prove that something exists, and also prove that there is no algorithm to tell us how to construct it. In fact, these cases are exactly the ones that require the axiom of choice. If we know how to construct the choice functions, we don't need the axiom: the axiom buys us the ability to work without the ability to construct specific choice functions.
So the problem with it is that it embodies the things about set theory that many people disliked from the start. When Cantor was originally formulating what became set theory, one of the extremely popular mathematical philosophies was constructionism. Constructionism basically argues that something only exists if you can construct it: that existence proofs that don't tell you how to create something, but only argue that it must exist, are artifacts of logic. So by this argument, all of the things that the axiom of choice are completely meaningless artifacts of silly logic.
To give you a sense of the environment in which this was born: Leopold Kronecker, one of the early critics of set theory was famously quoted as responding to a paper describing the properties of π by saying, roughly, "Why are you wasting your time studying something which doesn't exist?" The idea behind that criticism is that you can't write the precise definition of π; and you can't draw a perfect circle where the ratio between diameter and circumference is really precisely the theoretical value of π. So π only exists in theory.
If a finitist/constructivist like Kronecker had disagreements with the existence of π, then you can imagine just how much trouble he'd have with something whose entire purpose was to let people write non-constructivist proofs!
To make matters worse, the first major application of the axiom of choice was
to prove that different infinities have different sizes. But according to finitist/constructivist arguments, infinity doesn't actually exist: it's just
a concept. How do you compare the sizes of non-existant concepts? It's like asking who smells better: the invisible pink unicorn, or the great purple arklesnesure? From the constructivist point of view, it's a meaningless question. So what do you make out of an argument that uses this axiom to describe non-constructable functions to prove differences between non-existent abstractions?
But in the end, Cantor and his successors won out. Now the axiom of choice is pretty much universally acknowledged as valid, and the constructivists - and particularly the finitist/constructivists - were just plain wrong. Constructivism still comes up in analysis, where the point is to find answers, but it's mostly a dead issue in abstract math. In the words of Hilbert, "No one shall expel us from the Paradise that Cantor has created."
- Log in to post comments
From Thomas Pynchon's Against the Day (2006):
My personal favorite formulation: every onto function has a section.
Maybe you meant "things that depend on the axiom of choice"?
I for one will be very content when we only have to deal with computable numbers.
Maybe the kids might find math more comprehensible and enjoyable in such a setting. They can allow themselves to be brainwashed later on if they want.
Infinities of infinities should be assigned to the research lab where they belong.
The arklesnesure. Obviously.
Could you clarify a couple of points, please?
Do you mean the statement |S| < |P(S)| for any set S? Because you certainly don't need AC for that. The function f: S -> P(S), f(x) = {x}, is a well-defined injection, and Cantor's argument guarantees that there is no bijection. AC guarantees that any two sets are comparable, but some pairs of sets (like S and P(S)) have to be comparable anyway.
Of course, constructivists may not have accepted P(S) as an object, but that has nothing to do with AC as such.
Also, I'm not following your logic at all for the proof that any two sets S and T are comparable. What is the collection X to which you're applying AC, for example? The only proofs I can recall involve well-ordering both sets and using that to build the injection, or looking at the collection of partial injections from S to T and using Zorn's Lemma.
Let's try that first paragraph again:
Do you mean the statement |S| < |P(S)|? Because that doesn't require AC at all. The function f: S -> P(S), f(x) = {x}, is a well-defined injection, and Cantor's argument guarantees that there is no bijection. (etc.)
What. The hell.
Do you mean the statement |S| < |P(S)|? Because that doesn't require AC at all. The function f: S -> P(S), f(x) = {x}, is a well-defined injection, and Cantor's argument guarantees that there is no bijection. etc.
I'm surprised you didn't mention the Banach-Tarski paradox.
I'd just like to point out that it's the Great Green Arkelseizure. I may not know as much math as most of these folks (though I'm working on it!) but I can darn well prove my geekiness in other ways!
It's not so much that the intuitionists are wrong, but that they want to play a game with very differnet rules. I prefer ZF with AC, because it's what lets me prove the results I want (when I can prove'em). But their game has a certain spare elegance that I can appreciate from afar, so long as it's afar enough.
I have a list of complaints/corrections of varying importance.
(1) As Chad Groft says, you don't need AC for Cantor's diagonalization arguments to work. It isn't true that one of the first uses of AC was to prove that there are infinite sets with different cardinalities, because AC is not needed to prove that.
There's a good book by somebody Moore called "Zermelo's Axiom of Choice", if you want to get some history. I suppose the first explicit use of AC was by Zermelo to prove that every set admits a well-ordering. According to Moore's book, IIRC, one of the first implicit uses of AC (i.e. no-one realized a fundamentally new assumption was being made) was to prove that "sequential continuity" is the same as "delta-epsilon continuity", which I will not write definitions for here but maybe you get the gist. (Coincidentally (?), the proof was given by Cantor.)
(2) I don't understand your proof that AC implies the comparability of all cardinals. First of all, you said one-to-one map where I believe you meant bijection. Now, either there exists a bijection between S and T, or not. You need to show that in the latter case, AC implies the existence of a one-to-one function from S to T or vice versa. I don't really see any hint of how you think that goes.
(3) I don't know what you mean by saying that you can't write the precise definition of pi. I mean, you can't very well write down the decimal expansion, but you can certainly write precisely defined sequences which you can prove converge, and use one something like that as a definition. One could also give more geometric definition in a precise way.
(4) I don't think you are being fair to AC skeptics by using Kronecker and finitists to represent them. Lebesgue is probably a more credible AC denier from those bygone days, although clearly he had some misunderstandings. I know of mathematicians who doubt AC today. (Not many, and some are happy to admit certain weak forms of AC like countable or dependent choice). They tend to be doing some kind of applied math where full-strength-AC is pretty much irrelevant anyway.
(5) To say that constructivists are "just plain wrong" about AC strikes me as funny! I mean, this isn't science here!
I "believe" AC to be true myself, but I recognize that I don't believe in it as strongly as I do the axiom of pairing, or the axiom of infinity. The matter does not seem "plain".
Oh, I forgot...
(6) The existence of a basis in every vector space is a popular consequence of AC, but in ZF it is strictly weaker than AC, not equivalent.
Actually, I can be more precise about the issues in trying to prove from AC that any two sets have comparable cardinality: I don't think I've ever seen a proof that didn't somehow involve transfinite induction (you could use Zorn's lemma, or some lemma about ordinals, but you'd use transfinite induction to prove these lemmas). If you can give a good short argument which avoids transfinite induction, neato!
The existence of a basis in every vector space is a popular consequence of AC, but in ZF it is strictly weaker than AC, not equivalent.
Thanks. I had seen the other equivalences, but I was racking my brain trying to prove this one.
To Bill Mill:
The Banach Tarski Paradox depends on the ax. of c; namely that you can chop up an orange into 5 or 6 pieces and reassemble them into two oranges identical to the first.
I've always been meaning to try that but can't get a sharp enough knife.
Mark, I thought that constructivism (or at least the form made popular by Brouwer) started later than Cantor's formulation of transfinite integer; it was Kroneker (who was not a constructivist strictu sensu) who bashed Cantor (before 1900), while Brouwer started constructivism after the turn of the century. Could you explain better?
The axiom of choice is a tool; we can use it since it is independent of ZF. I guess if somebody had a use for its opposite, they would also be allowed to do so, but it has never happened to me.
I actually use AC even when I don't need to, if it leads to a clearer proof. A colleague once was less than enthousiastic about it, on the grounds that "I heard Deligne doesn't like it". When having to choose between an AC-including proof and two pages of very delicate arguments for a much less general result, they gave up.
Maya: computable doesn't mean easy. I find squareroot of 2 easier to manipulate than 1.4142, and I already did as a child. On the other hand, I hope schoolchildren are not routinely exposed to the axiom of choice :-).
mau,you are essentially correct.
Kronecker was more a finitist.
Brouwer was an intuitionist and it was a reaction to "Paradise".
Constructivism (modern version) uses intuitionist logic and is just as consistent (but more restrictive) as classical plus ZFC.
A constructivist is category rather than set, NSA rather than classical analysis, intuitionist rather than classical logic, etc etc.
"The axiom of choice is a tool; we can use it since it is independent of ZF."
So is CH, do you use that as well?
"I guess if somebody had a use for its opposite, they would also be allowed to do so, but it has never happened to me."
You can use whatever your chosen set of axioms and logic permits.
"I actually use AC even when I don't need to, if it leads to a clearer proof."
Clearer for who? C is now "in" ZFC, independant or not.
"A colleague once was less than enthousiastic about it, on the grounds that "I heard Deligne doesn't like it". When having to choose between an AC-including proof and two pages of very delicate arguments for a much less general result, they gave up."
I rather think that most mathematicians are at least a little suspicious about AC (and the rest ought to be). Constructive proofs always feel better (to me), more convincing than assertions of existence.
"Maya: computable doesn't mean easy. I find squareroot of 2 easier to manipulate than 1.4142, and I already did as a child."
Who said it was easy?
Square root of 2 is just a representation as is 1.4142 as is the continued fraction or the number in any base you choose. Personally I don't care which representation my computer uses as long as it provides the correct output.
"On the other hand, I hope schoolchildren are not routinely exposed to the axiom of choice :-)."
That's the trouble, they are (it's just not called that).
"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" -- Jerry Bona
I think that it's the well-ordering principle that makes modern mathematicians iffy about the AC, and touchy about when it's used.
One of the things I really liked about Wagon's book "The Banach-Tarski Paradox" is that he was very explicit about marking which theorems depended on the AC and which didn't throughout the book. (Namely, he'd put [AC] after the theorem number if it depended on the AC)
(I don't see why people are picky about it when the B-T paradox is clearly a Biblical principle - look at Mark 6:38-44. What, you have a different interpretation of the loaves and fishes thing?)
(1) A couple of times Mark says "constructionism" when I think he means "constructivism". (Zero hits on "constructionism" at MathSciNet.)
(2) Lebesgue and the other French skeptics, while perhaps more reasonable than Kronecker, were also shown to have implicitly used nonconstructive arguments equivalent to weak forms of choice (countable) in their own work.
Although Maya Is right in saying that Kronecker was principally a finitist who rejected all mathematical arguments based on an actual infinity he is also regarded as the spiritual father of the modern intuitionists and constructivists. The following quotes from Morris Klien's MATHEMATICS The Loss of Certainty express why, better than I could:
Sorry for falling behind on this comment thread!
Some general responses:
(1) Yes, I know that Kronecker wasn't really a constructivist; but he's a particularly extreme and amusing example of the roots of what grew into constructivism. I didn't want to spend too much time explaining the various philosophical movements within late 19th/early 20th century math; using Kronecker as a vivid example of the strict constructionist approach seemed reasonable.
(2) I thought that AC was required for Cantor's argument; I'm still not sure how to get to the infinite set of mappings between infinities showing different cardinalities without AC. I'll take another look in my books when I have some time, and see if I can figure out what I'm missing.
(3) Yes, saying that people accept the truth of AC was seriously sloppy wording. Sorry about that.
More later...
I see. Gödel's incompleteness theorems were not controversial. Hilbert's problems were just idle musings, and statements that may negate one of them are of no great consequence.
When people say they are "suspicious" of this axiom (as some have here) what do they suspect it of?
Brian:
What they're suspicious of is that the axiom is invalid - that is, that it can be used to derive results that are inconsistent with the rest of the axioms. If that were to happen, that would mean that every proof that used the axiom of choice would be invalid.
It's a legitimate concern: the AoC is a seemingly innocuous statement that can be used to prove a lot of extremely deep and counterintuitive statements - and it frequently does it by using intangible, unconstructable functions or sets. So it's understandable that people find it worrying. But at this point, a result that it was inconsistent with ZF set theory would be a shock on the order of incompleteness.
As in demonstrating the existence of non-measurable, yet finitary, sets that enables the H-B-T paradox?
I like Jonathan Vos Post's e, reminder about Terrence Tao's characterization:
Personally I would call the later "idealized" math, if it's not too presumptuous.
One may put the similar, or same, question if there are any "real" infinities and similar non-measurables behind any physics, say string/M theory or inflationary multiverses, that our observable Hubble volume may depend on.
But IMHO it is a different question, perhaps in the end philosophical, than admitting that idealizations and models are darn practical.
"When people say they are "suspicious" of this axiom (as some have here) what do they suspect it of?"
Whole books have been written about this,for and against and over many years (and continue to be).
Perhaps in the end, it comes down to what you believe; an axiom is, after all, only an assertion eg there exists an infinite set ---- says who?
If I asserted the existence of a purple and green striped peacock your natural reaction might be to ask me to show you one; I could say the same about an infinite set.
Now if these axioms were put up as definitions rather than masquerading as some kind of universal truths then the matter would be less fraught.
If people can demonstrate a proof of something useful using some "definitions" that are not ZFC (this has been done in constructive mathematics), why should there be anything wrong with that?
Sorry for the repost, I forgot my name.
"When people say they are "suspicious" of this axiom (as some have here) what do they suspect it of?"
Whole books have been written about this,for and against and over many years (and continue to be).
Perhaps in the end, it comes down to what you believe; an axiom is, after all, only an assertion eg there exists an infinite set ---- says who?
If I asserted the existence of a purple and green striped peacock your natural reaction might be to ask me to show you one; I could say the same about an infinite set.
Now if these axioms were put up as definitions rather than masquerading as some kind of universal truths then the matter would be less fraught.
If people can demonstrate a proof of something useful using some "definitions" that are not ZFC (this has been done in constructive mathematics), why should there be anything wrong with that?
Sorry, bad formatting: "I like Jonathan Vos Post's e, reminder" - I like Jonathan Vos Post's reminder.
But at this point, a result that it was inconsistent with ZF set theory would be a shock on the order of incompleteness.
You realize that Gödel showed the relative consistency of AC, right? So the only way ZFC can be inconsistent is if ZF is inconsistent to start with.
Antendren's right. Mark, are you confusing truth with provability again? Also:
"Infinite set of mappings"? I'm not sure how you read that into Cantor's argument. All Cantor does is show that no function from a set S to its powerset P(S) could possibly be onto, which together with the injection sending x to {x} implies that S is smaller than P(S). S and P(S) could very well be finite.
"Infinite set of mappings"? I'm not sure how you read that into Cantor's argument."
Which argument?
http://en.wikipedia.org/wiki/Cardinal_Number
Infinite sets obviously can contain fewer members than other infinite sets. For example, let A be { the positive integers }; let B be { all positive numbers to four fractional places } and let C be { everything from 0.0001 to 100.0000 to four fractional places }. A is clearly infinite, but it is also clearly a subset of B. C is a subset of B but is clearly finite (it has 1 million members).
Kronecker's statement about integers is just plain absurd. Though, it does demonstrate a useful mathematical technique: Find something you want to prove, assume the opposite, and show an absurdity which then invalidates the original assumption.
Re #34: Most mathematicians would not use "contain[s] fewer members than" as a synonym for "is a (proper) subset of".
I've got about a dozen books on set theory (including Herrlich's volume in Springer's Lecture Notes in Mathematics), and not a single one asserts that the Axiom of Choice is needed for Cantor's proof of the uncountability of the reals. Would those of you who claim that it is needed provide a reference for that fact?
I've just walked over to the campus library to consult Howard and Rubin's exhaustive list of Consequences of the Axiom of Choice. Cantor's Theorem on the uncountability of the reals isn't listed.
AJS: Um, the first two sets you talk about are both countably infinite, and thus the same size. Though A is clearly a subset of B, B is also provably a subset of A. Only C is smaller than the other sets, and that's because it is finite.
Re #25 and #26:
These days (since 1940), when people say they are suspicious of the axiom of choice, they usually do NOT mean that they are suspicious that AC might be inconsistent with ZF. As has already been pointed out, Gödel proved that if ZF+AC is inconsistent, then ZF by itself is inconsistent.
So what do people mean when they say they are suspicious of AC or some such thing? Sometimes, in my experience, it seems to mean they are suspicious that AC might not be true. Sometimes I think it means that they are more comfortable with some statements contradicting AC than they are with AC, and they'd rather adopt axioms like "all sets of reals are Lebesgue measurable" than full-strength AC.
In #38, you need to insert something like "equipotent to" after "provably".
EJ:
I find the distinction between "AC is false" and "AC causes ZFC to be inconsistent" to be difficult to understand. There's a subtle distinction, but not one that most people are going to really get.
The AC is a formal statement about sets: if it's false, what does that mean in terms of its use as an axiom? It basically means that any proof that depends on it becomes invalid. If the AC is *not* false but inconsistent, it means that any proof that uses it in ZFC is invalid.
The distinction between "false" and "inconsistent" is really one outside of the formal system. And the meaning of the difference implied by that kind of meta-issue - truth outside the system versus provability inside the system - is a hard thing to explain.
Personally, most of the people that I've know who don't like AC *seem* to handwave their way past that distinction, and use truth and proof-consistency as rough equivalents.
Russell had a neat way of explaining countable choice-- Suppose you have an infinite number of pairs of shoes and an infinite number of pairs of socks. The collection of 'left shoes' is a set without any further assumptions because left and right shoes are distinguishable. However, the collection of 'left socks' is not a set unless you assume AC.
It is a matter of convention to point out in a proof that AC has been used.
This convention is not customary for the other axioms.
Of itself this should indicate the distinctive nature of this axiom.
MarkCC: "Personally, most of the people that I've know who don't like AC *seem* to handwave their way past that distinction, and use truth and proof-consistency as rough equivalents"
If it's been proven consistent, I'd expect them to do the opposite.
Brian:
As would I. That's part of why I tend to think that while people are sometimes uncomfortable with it, in the end, most people do basically accept that it's both true and consistent. Because when a group of people as picky as mathematicians don't bother to make a distinction, it's usually because they don't think that the distinction has any actual effect. If people believed that ZFC was completely consistent, but AC was *false*, then they'd be very careful to distinguish between the consistency and truth of AC. But they don't.
AC has, with absolutely no controversy, been proven relatively consistent with ZF. The theorem, due to Godel, is precisely "If ZF is consistent, then so is ZF + AC (aka ZFC)". This is as much as we can hope for, using ZF or any weaker theory as a meta-theory, since due to Godel's 2nd Incompleteness Theorem, an outright proof (in ZF) that "ZFC, and hence ZF, is consistent", would in fact show that ZF is inconsistent (and hence ZF would prove ANY statement). And this 2nd incompleteness theorem argument has nothing to do with AC.
The issues with AC are (1) the weird consequences, like Banach-Tarski and well-orderings of the reals (aka R), and (2) the specialnature of AC as an axiom: unlike the other existence axioms of ZF (e.g. pairs, union, power set, infinity, replacement), AC asserts the existence of a set which is not explicitly defined by the axiom.
I've sometimes thought that the weirdness people feel about well-orderings of R is that we expect that a well-ordering of R should somehow be definable if it exists, whereas the existence of a choice set which is undefinable is less bothersome. Maybe it's easier to imagine the choice set, since you can think "locally" about picking one element from each set in the family, but picturing the well-ordering does not come together by focusing on local parts of it. Of course, a choice set on the family of non-empty sets of reals is no more definable than a well-ordering of the reals, but it seems to be intuitively more believable without an explicit definition.
And Mark, I really enjoy your blog.
Are there current debates in mathematics of a similarly heated nature?
Hm. Aren't these arguments over the consistency of ZF vs ZFC moot? I thought the late Paul Cohen proved the other half of Gödel's theorem w.r.t AC, finally showing that AC is completely independent of the rest of ZF.
He won the Fields Medal for showing the continuum hypothesis to be independent, but he did AC while he was at it.
"Aren't these arguments over the consistency of ZF vs ZFC moot? I thought the late Paul Cohen proved the other half of Gödel's theorem w.r.t AC, finally showing that AC is completely independent of the rest of ZF."
Perhaps the easiest way of thinking about it is one produced a proof saying it could be true and the other produced a proof saying it could be false and ZF can't say one way or the other.
So if you want to have it, then it can be an axiom or an assumption; they decided (rather arbitrarily) on axiom.
Since we have many proofs starting off with "If the Riemann hypothesis is true...." maybe we should make RH an axiom as well!
Anyway nowadays anything not ZFC is considered "research" but to my way of thinking its ALL research once you get past Peano.
Mark: Whoa! The difference between "AC is true" and "AC is consistent (with ZF)" is huge. It's reasonable to doubt that AC is true (although one is in danger of raising philisophical questions about what mathematical truth is). It's really pretty unreasonable to doubt that AC is consistent (unless one doubts that ZF is consistent, but I don't know anyone who argues for such a position), because it has been proven to be consistent.
I'm surprised that you say that mathematicians who doubt AC are not careful about the distinction! That almost sounds embarrassing, and I'm tempted to say that an AC denier who is inclined to conflate "AC is true" with "AC is consistent" is simply lacking in credibility on the subject. But maybe that's too strong. Such an AC doubter may be simply attempting to describe private intuitions about problems with AC, which is okay as long as they know they are not making an argument which is remotely compelling.
Is the difference between "false" and "inconsistent" really so hard to explain? I guess I would start by explaining it this way: AC may be true, or it may be false. "Inconsistent" would mean we can hope to prove it to be false, but we know that such a proof is impossible.
Ned Rosen: Interesting that you say that we expect a well-ordering of R to be definable if it exists. The intuition of most set theorists seems to be that a well-ordering of R exists but would not be definable. It is an unusual feature of Gödel's constructible universe L that it is sort of easy to define a well-ordering of R in L, and may be one reason (but not the biggest reason) it is generally held that L is not the "real" universe of sets.
Paul: I don't think there are currently similarly heated debates in mathematics.
scottb: I guess no one here is arguing about whether AC is consistent relative to ZF. We seem to be arguing about whether *other people* argue about whether AC is consistent relative to ZF. When I put it like that, it seems like maybe not the best use of our time.
Maya, in #43:
No, not for a while now. Most fields of mathematics have their share of "obvious" facts that require AC to prove. Algebra has "every vector space has a basis", as Mark pointed out. Geometry has "every smooth manifold carries a Riemannian metric". Analysis has the Hahn-Banach Theorem: every functional T on a subspace of a normed vector space V where T has finite norm extends to a functional on all of V with the same norm. The textbooks generally make explicit the use of AC or an equivalent, but only because they must to make the proof correct. Outside of descriptive set theory, where the whole point is to see how much you can say about sets of reals without the full strength of AC, almost nobody worries about it anymore.
EJ: Mark does seem to be a bit confused, but I think his major point is that most mathematicians don't bother with the distinction because they believe AC is true, which is in fact the case. Also, I think the main reason that most set theorists don't accept V = L is that it's incompatible with large cardinal axioms, and set theorists love them some large cardinals. There is a project to generalize the ideas of L to get a sort of "generalized" constructible universe that is compatible with all the large cardinal axioms; Hugh Woodin is working on it, among others. If that ever completely succeeds, it may well be accepted as the "correct" definition of the universe.
Paul "Are there current debates in mathematics of a similarly heated nature?"
You know the one about the frogs in a pan of water being slowly heated up.....:-)
EJ Nice post.
Chad: I agree re the biggest reason for rejecting V=L.
But re "most mathematicians don't bother with the distinction because they believe AC is true"... Well, I agree with the statement I just quoted, but in #41 Mark was talking about people who "don't like" AC.
So he did. Sorry about that.
Once again, sorry for falling behind on the comments. Aside from the personal grief, it's been an extraordinarily busy week. (But at least busy in a good way; I got to sit on a defense committee yesterday and see a former summer student of mine successfully defend his thesis, which grew partly out of the work he did with me in his summer at IBM.)
Anyway..
WRT to my being a little confused. Yes, absolutely. Set theory is fascinating to me, but often more than a little bit mystifying. The degree of abstraction - particularly when you're dealing with things as non-constructive as AC - does often manage to throw me off. Just when I think I've really got it, I always find more subtleties to throw me off. I've tried to always be honest about things like that in my writing on GM/BM - I do my best, and I admit it when I screw up. That's the best I can do.
WRT the AC and Cantor's proof: this is probably my cluelessness at work once again. But I distinctly remember back in college talking about how the AC is what makes cardinality comparisons of infinite sets possible. Cantor's proof relies on the fact that there every possible mapping from the set N of natural numbers to the set R of reals will miss real numbers - and that fact implies that R is bigger than N. My understanding was that that last step - the step of saying that we can conclude that N is smaller than R - relied on the fact, derived from the AC, that the cardinalities are comparable.
Also relating to the above: I'm *sure* that I screwed this up.. But my understanding of how the mapping from N to Z worked was by the repeated application of the axiom of choice to create the mappings between members of different infinite sets. So by that understanding, you need the AC to create the mapping that Cantor's diagonalization uses. I'm pretty sure I understand what I blew in that reasoning chain, but it's interesting and important enough that I think it should be a top-level post of its own, which I'll write when I have time.
With respect to the soundness/truth of AC: Maybe I just know strange people. But I have definitely noticed that even among people who are uncomfortable with AC, there's a tendency to blur the lines between "AC is true" and "ZF with AC is sound". And ultimately, all of them, both the AC-likers and the AC-haters end up using the AC as if it were true.
Finally, WRT the distinction between truth and consistency of AC: I still find it somewhat fuzzy in terms of what the effect of AC falsity or ZF+AC inconsistency would be. The AC is a very abstract statement about non-constructable abstract objects of mathematical reasoning. If it's not true, what does that really *mean*? How different is it from just saying that ZF+AC is not sound or valid? In either case, what you're really talking about is whether proofs written using ZF+AC are valid or not. There's a theoretical distinction between the *truth* of ZF and the consistency of ZF, but for pretty much everyone but professional set theorists, how much difference does that disticntion make *in practice*?
In theory, the truth or falsehood of AC is a very different thing from the validity of ZF+AC. But in practice, proving AC is false isn't particularly any better or worse that proving ZF+AC is inconsistent.
In the following intriguing paper, "GR" abbreviates General Relativity.
arXiv:0705.3902
Title: A Derivation of Einstein Gravity without the Axiom of Choice: Topology Hidden in GR
Authors: M. Spaans
Comments: minor edits, acknowledgement added
A derivation of the equations of motion of general relativity is presented that does not invoke the Axiom of Choice, but requires the explicit construction of a choice function q for continuous three-space regions. The motivation for this (seemingly academic) endeavour is to take the background independence intrinsic to Einstein gravity one step further, and to assure that both the equations of motion and the way in which those equations of motion are derived are as self-consistent as possible. That is, solutions to the equations of motion of general relativity endow a three-space region with a physical and distinguishing geometry in four-dimensional space-time. However, in order to derive these equations of motion one should first be able to choose a three-space region without having any prior knowledge of its physically appropriate geometry. The expression of this choice process requires a three-dimensional topological manifold Q, to which all considered three-space regions belong, and that generates an equation of motion whose solutions are q. These solutions relate the effects of curvature to the source term through the topology of Q and constitute Einstein gravity. Q is given by 2T^3+3S^1xS^2, and is embedded in four dimensions. This points toward a hidden topological content for general relativity, best phrased as: Q and q provide a structure for how to choose a three-space region irrespective of what geometric properties it has, while at the same time Q and q determine that only GR can endow a three-space with those geometric properties. In this sense, avoiding the Axiom of Choice allows one to gain physical insight into GR. Possible links with holography are pointed out.
AC is what makes cardinality comparisons of infinite sets possible.
AC guarantees that any two infinite sets can have their cardinality compared. Without AC, you'll still have some sets that can be compared, the naturals and the reals being one example. You don't need choice to make an injection from the naturals to the reals, and you don't need choice to prove that there is no injection from the reals to the naturals.
You can create a map from N to Z as follows: f(n) = n/2 if n is even, f(n) = (n+1)/(-2) if n is odd. I've written this explicitly, so it doesn't require choice.
To make sense of claims about AC being true or false, you need to make the assumption that there is some sort of "real world" in which sets exist. This is a very philosophically heavy assumption, and not one I'm sure I would grant you (and to think, I was once a platonist).
Once you've made that assumption, saying AC is true is saying that this real world of sets has choice functions. Similarly, saying that AC is false would be saying that this real world doesn't always have choice functions.
Mark, it doesn't surprise me that your college course addressed the question that way. I think mine did the same, and just didn't worry about whether AC was necessary.
What Antendren said about the truth of ZF or ZFC is correct. Saying that ZF or ZFC is true is usually understood as a statement about the entire universe of mathematical objects; in particular, saying "ZFC is true" is stronger than saying "ZF is true". Saying that ZF or ZFC is consistent is much weaker; it says that there is no formal derivation of a contradiction from the axioms of the given theory. Initially this is metamathematical, but Godel was able to show that statements about provability can be understood as statements about the natural numbers (this is the key to the Incompleteness Theorems). He later showed that "ZF is consistent", which is a priori weaker than "ZFC is consistent", is actually equivalent.
Looked at from this perspective, the incompleteness theorems as applied to set theories isn't a huge surprise, at least for a set Platonist. If they were false, it would mean that statements about the entire universe of sets could be reduced to statements about a much smaller fragment, which would be bizarre.
I can say that, among the mathematicians I know, there is nobody who thinks choice is false. In my own field (algebraic geometry/representation theory) choice is in fact required -- without choice one cannot prove that all rings have maximal ideals, for example, since Zorn's Lemma is equivalent to AC. Also there is quite a lot of categorical algebra going on in algebraic geometry and representation theory, and without choice much of this gets thrown out the window -- there are absolutely no constructivist arguments to be found here! It is never mentioned in an argument when choice is being used (and it is often used, implicitly) because it is assumed true.
I certainly believe that choice is true, because I believe that algebraic geometry makes sense. From an algebraic geometry perspective, choice simply says: the geometric objects in algebraic geometry have (closed) points. This is a statement I have no trouble believing.
>I am interested in people's opinions about how a "new axiom" gains
>acceptance. [I guess this is asking for the mathematical version of "how
>does a bill become a law?".]
We don't have that many examples to learn from.
With the axiom of choice, we have the following phenomena:
1. It is trivial to see what it says in the context of set theory.
2. It is easy to use.
3. It is useful for general treatments of important subjects. E.g.,
for the general theory of fields, for the general theory of topology
(general topology), for general algebra of various kinds (general
theory of groups), etc. In these subjects, very little can be proved
without the axiom of choice.
4. It is not useful for concrete treatments of important mathematical
subjects. I.e., continuous functions between Polish spaces, theory of
finite field extensions of the rationals, semialgebraic geometry in
the reals, algebraic geometry in the complex numbers, number theory,
etc. In particular, the uses of the axiom of choice in these contexts
are easily removed. But not in 3.
5. There are very simple fundamental sounding philosophies that suggest it.
With 5, there is the simple fundamental sounding philosophy that
suggests the axiom of choice:
*anything imaginable whatsoever, subject to the well known size
limitation, forms a set.*
In particular, a set which meets every one of a set of pairwise
disjoint nonempty sets, is at least IMAGINABLE, and therefore, by
this principle, exists.
It appears that we have run out of fundamental sounding philosophies
of set theory that seem compelling to working set theorists.
http://cs.nyu.edu/pipermail/fom/2003-June/006890.html
ISTR that, as long as you stick to Noetherian rings, you can avoid most choice arguments, but I'm not sure I'm remembering so well.
About vector spaces and AC...
Sorry! I need to make a correction.
Mark was right: AC is equivalent to "Every vector space has a basis". I was wrong in a comment above. I looked it up before I posted before, but I looked it up wrong!