Is the axiom of choice useful?

[schrodingasdawg]

This was brought up in another thread. Here is a post by W.D.Clinger.

As an occasional skeptic, I don't think axioms should be multiplied beyond necessity. To my knowledge, there are no practical applications for which the axiom of choice is actually necessary; the axiom is hardly self-evident, and is in fact controversial; it is inconsistent with axioms that are just as elegant and no less plausible, such as the axiom of determinacy^WP; in short, its implicit assumption by many mathematicians during the 20th century appears to have been an unfortunate accident of history. I have no objection to theorems whose proof requires the axiom of choice, but I argue that a correct statement of such a theorem would include the axiom of choice as an explicit hypothesis.

If anyone really wants to discuss that, we should start another thread.

Wikipedia has a list of equivalent statements and theorems that follow from ZF+AC. I've heard of Tychonoff's theorem being important, but I've never really known why. The law of trichotomy for cardinal numbers and the theorem that the Cartesian product of non-empty sets is itself non-empty seem like they "should be" true (though that hardly means they are).

I don't really know about any special requirements that one may wish to impose that are inconsistent with AC other than that every subset of R^n is measurable. But how useful is this requirement?

And W.D.Clinger said particularly that "there are no practical applications for which the axiom of choice is actually necessary." I suppose the realm of "practical applications" may be disjoint from pure math-theoretic applications. So, I suppose I really have two questions:

(1) Is AC "useful" in the sense that it can be used to derive as theorems statements we want to be true?
(2) Is AC useful for any "practical" applications, e.g. physics?

 

[Paul C. Anagnostopoulos]

Some theorems that utilize AC:

• For every infinite set A, A x A has the same cardinality.
• For every infinite set A, the set of finite subsets of A has the same cardinality.
• Zorn's lemma.
• Well-ordering principle.
• Every vector space has a basis.

~~ Paul

 

[Perpetual Student]

Is there a way to prove the uncountability of the rational real numbers without the axiom of choice?

 

[jsfisher]

Is there a way to prove the uncountability of the rational numbers without the axiom of choice?

Did you mean the countability?

 

[Perpetual Student]

Did you mean the countability?

Sorry, I meant the real numbers. I will edit my post.

 

[W.D.Clinger]

And W.D.Clinger said particularly that "there are no practical applications for which the axiom of choice is actually necessary." I suppose the realm of "practical applications" may be disjoint from pure math-theoretic applications. So, I suppose I really have two questions:

(1) Is AC "useful" in the sense that it can be used to derive as theorems statements we want to be true?
(2) Is AC useful for any "practical" applications, e.g. physics?

The answer to (1) is yes, there are sentences that some people want to be true that can be proved using the axiom of choice. On the other hand, there are other sentences that some people want to be true that can be proved using axioms that are inconsistent with the axiom of choice. For example, some people would like for every subset of the reals to be Lebesgue-measurable, which is consistent with ZF but inconsistent with ZFC. So question (1) is not determinative; as phrased, it creates a bias toward the axiom of choice.

Some theorems that utilize AC:

• For every infinite set A, A x A has the same cardinality.
• For every infinite set A, the set of finite subsets of A has the same cardinality.
• Zorn's lemma.
• Well-ordering principle.
• Every vector space has a basis.

Although the first two of those "theorems" sound appealing, many questions about the structure of infinite cardinals (including the most natural question, the continuum hypothesis) are independent of the axiom of choice. If you're hoping to simplify the subject of infinite cardinals, the axiom of choice is not your answer.

With respect to that last "theorem", it holds for constructive vector spaces even without the axiom of choice. In particular, the theories of separable Hilbert spaces and commutative Banach algebras can be developed without using the axiom of choice. That takes care of the usual objections to schrodingasdawg's question (2).

Is there a way to prove the uncountability of the rational numbers without the axiom of choice?

The rational numbers are countable, with or without the axiom of choice.

Likewise, the real numbers are uncountable, with or without the axiom of choice.

To give you some idea of the delicacy of this subject, Skolem's original proof of the Löwenheim-Skolem theorem^WP used the axiom of choice. That theorem tells us that every first-order formalization of the reals has a countable model. Skolem later proved a version of the theorem without using the axiom of choice, so we get countable models for the first-order reals with or without AC. Some people would say the AC-free version is slightly weaker than the AC version. I would say a correct statement of the AC-using version should include the AC among its explicit hypotheses, so neither version immediately entails the other.

 

[schrodingasdawg]

With respect to that last "theorem" [every vector space has a basis], it holds for constructive vector spaces even without the axiom of choice. In particular, the theories of separable Hilbert spaces and commutative Banach algebras can be developed without using the axiom of choice. That takes care of the usual objections to schrodingasdawg's question (2).

This is quite useful to know.

Does it happen that the Hahn-Banach theorem is true for separable Banach spaces without the axiom of choice? I have a functional analysis book (Kolmorogov and Fomin) that proves it for separable spaces and assures the reader it's "true in general," and doesn't make any explicit mention of the axiom of choice, but it could be that it's just not stating all its premises. The most Wikipedia says is that it "follows from WKL0, a weak subsystem of second-order arithmetic," but I don't really know what WKL0 is. Plus, I've heard that the Banach-Tarski paradox follows from Hahn-Banach, and Banach-Tarski is incompatible with the axiom of determinacy (or just with the axiom that all subsets of R^n are Lebesgue measurable), so I would think that Hahn-Banach could not be proved except if some axiom that was incompatible with AD were assumed.

Sorry if my question seems a bit silly, I'm really just still learning this axiomatic math stuff.

 

[W.D.Clinger]

Does it happen that the Hahn-Banach theorem is true for separable Banach spaces without the axiom of choice?

Yes.

I have a functional analysis book (Kolmorogov and Fomin) that proves it for separable spaces and assures the reader it's "true in general," and doesn't make any explicit mention of the axiom of choice, but it could be that it's just not stating all its premises. The most Wikipedia says is that it "follows from WKL0, a weak subsystem of second-order arithmetic," but I don't really know what WKL0 is.

WKL₀ consists of the usual system for constructive mathematics plus the Weak König's Lemma, which is implied by ZF without AC. The WKL is a weak alternative to the axiom of choice; when restricted to ordered binary trees, which is all you need for most practical applications, the Weak König's Lemma is fully constructive: the ordering provides the choice, so you don't need to assume the existence of a choice function.

Plus, I've heard that the Banach-Tarski paradox follows from Hahn-Banach, and Banach-Tarski is incompatible with the axiom of determinacy (or just with the axiom that all subsets of R^n are Lebesgue measurable), so I would think that Hahn-Banach could not be proved except if some axiom that was incompatible with AD were assumed.

Yes. The Hahn-Banach theorem, in its full non-constructive glory, can be proved using the ultrafilter lemma, which is strictly weaker than AC. The (full non-constructive) Hahn-Banach theorem and Banach-Tarski paradox fail if every subset of the reals is Lebesgue-measurable, which follows from AD.

Sorry if my question seems a bit silly, I'm really just still learning this axiomatic math stuff.

Not silly at all. I didn't know most of what I wrote above until I looked it up in Wikipedia. (By the way, I noticed an error in Wikipedia's current article on the axiom of choice^WP: It misstates Gödel's completeness theorem, apparently by confusing it with Lindenbaum's lemma.)

The standard reference for this stuff is Errett Bishop's Foundations of Constructive Analysis, Academic Press, 1967. (A revised and extended version appeared in 1985: Errett Bishop and Douglas Bridges, Constructive Analysis, Springer.) I don't own a copy of that book, but I read most of it during the late 1970s, shortly after I had taken graduate-level courses on classical functional analysis and differential geometry, and while I was taking courses on set theory and set-theoretic topology. The best summary of its contents that I've been able to find online is Gabriel Stolzenberg's review for the Bulletin of the AMS.

 

[W.D.Clinger]

I ran across this online "hyper-textbook for students" that covers the history and content of the axiomatic method and foundations of mathematics:

Karlis Podnieks. What is Mathematics: Gödel's Theorem and Around.
http://www.ltn.lv/~podnieks/gt.html

I recommend this short online book to people who crave more technical content and less fluff than is found in Douglas Hofstadter's Gödel, Escher, Bach^WP: an Eternal Golden Braid. It contains complete proofs of Gödel's incompleteness theorems, together with the historical and technical context needed to appreciate those theorems.

Section 2.4, which is about the continuum problem, also contains a balanced exposition of the axioms of choice, constructibility, and determinacy.

Notational warning: He eschews non-ASCII characters. For example, he writes "w" instead of "ω", and the letter "U" to indicate union.