The axiom of choice is a common set-theoretic axiom with many equivalents and consequences. This tag is for questions on where we use it in certain proofs, and how things would work without the assumption of this axiom.

learn more… | top users | synonyms

177
votes
1answer
6k views

Does the open mapping theorem imply the Baire category theorem?

A nice observation by C.E. Blair1, 2, 3 shows that the Baire category theorem for complete metric spaces is equivalent to the axiom of (countable) dependent choice. On the other hand, the three ...
84
votes
4answers
7k views

What are the Axiom of Choice and Axiom of Determinacy?

Would someone please explain: What does the Axiom of Choice mean, intuitively? What does the Axiom of Determinancy mean, intuitively, and how does it contradict the Axiom of Choice? as simple ...
67
votes
6answers
5k views

Why can't you pick socks using coin flips?

I'm teaching myself axiomatic set theory and I'm having some trouble getting my head around the axiom of choice. I (think I) understand what the axiom says, but I don't get why it is so 'contentious', ...
66
votes
8answers
19k views

Can you explain the “Axiom of choice” in simple terms?

As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get. I went to Wikipedia to see what the Axiom of ...
56
votes
2answers
18k views

Predicting Real Numbers

Here is an astounding riddle that at first seems impossible to solve. I'm certain the axiom of choice is required in any solution, and I have an outline of one possible solution, but would like to ...
53
votes
3answers
2k views

Explicit norm on $\mathcal{C}^0(\mathbb{R},\mathbb{R})$

Do you know an explicit norm on $\mathcal{C}^0(\mathbb{R},\mathbb{R})$? Using the axiom of choice, every vector space admits a norm but have you an explicit formula on ...
46
votes
2answers
2k views

Axiom of choice and automorphisms of vector spaces

A classical exercise in group theory is "Show that if a group has a trivial automorphism group, then it is of order 1 or 2." I think that the straightforward solution uses that a exponent two group is ...
44
votes
2answers
7k views

Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
37
votes
2answers
2k views

Is there an explicit isomorphism between $L^\infty[0,1]$ and $\ell^\infty$?

Is there an explicit isomorphism between $L^\infty[0,1]$ and $\ell^\infty$? In some sense, this is a follow-up to my answer to this question where the non-isomorphism between the spaces $L^r$ ...
35
votes
1answer
541 views

Over ZF, does “every Hilbert space have a basis” imply AC?

I know there is a similar result due to Blass [1] that over ZF, "every vector space has a (Hamel) basis" implies AC. Looking around, however, I can't find any results on the question for Hilbert ...
34
votes
4answers
2k views

Does every set have a group structure?

I know that there is no vector space having precisely $6$ elements. Does every set have a group structure?
34
votes
2answers
2k views

Is the axiom of choice really all that important?

According to this book: The Axiom of Choice is the most controversial axiom in the entire history of mathematics. Yet it remains a crucial assumption not only in set theory but equally in modern ...
33
votes
5answers
2k views

Advantage of accepting the axiom of choice

What is the advantage of accepting the axiom of choice over other axioms (for e.g. axiom of determinacy)? It seems that there is no clear reason to prefer over other axioms.. Thanks for help.
31
votes
6answers
3k views

Foundation for analysis without axiom of choice?

Let's say I consider the Banach–Tarski paradox unacceptable, meaning that I would rather do all my mathematics without using the axiom of choice. As my foundation, I would presumably have to use ZF, ...
29
votes
2answers
2k views

Continuity and the Axiom of Choice

In my introductory Analysis course, we learned two definitions of continuity. $(1)$ A function $f:E \to \mathbb{C}$ is continuous at $a$ if every sequence $(z_n) \in E$ such that $z_n \to a$ ...
27
votes
4answers
1k views

Is Banach-Alaoglu equivalent to AC?

The Banach-Alaoglu theorem is well-known. It states that the closed unit ball in the dual space of a normed space is $\text{wk}^*$-compact. The proof relies heavily on Tychonoff's theorem. As I have ...
26
votes
2answers
895 views

A few questions about intuitionistic mathematics

I have to write a paper on Intuitionism for my Philosophy of Science class and I'm struggling with a few concepts I have encountered in my self-study. The (intuitive) characterization of valid ...
25
votes
5answers
911 views

Axiom of choice - to use or not to use

I was wondering if there are examples of results in mathematics that were first proven using axiom of choice and later someone found a proof of the result without using the axiom of choice.
25
votes
4answers
905 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of ...
24
votes
2answers
942 views

W. Mückenheim claims a severe inconsistency of transfinite set theory; true? [closed]

The abstract for a paper on arxiv.org (http://arxiv.org/pdf/math/0408089v3.pdf) reads (with my emphasis): "Transfinite set theory including the axiom of choice supplies the following basic theorems: ...
23
votes
4answers
2k views

Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice?

I know the usual proof of the existence of an algebraic closure for any field using Zorn's Lemma. The answer to this previous question makes it clear that in general, some nonconstructive axiom (not ...
22
votes
2answers
2k views

Why do people accept the axiom of choice given the well ordering principle?

We know without any doubt that the axiom of choice implies (in fact is equivalent to) the well ordering principle. The well ordering principle can't be true! If we take the open interval $(0,1)$ for ...
22
votes
2answers
2k views

For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

How to prove the following conclusion: [For any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice. Can you give a proof without the theory of ordinal ...
20
votes
4answers
2k views

Why is the axiom of choice separated from the other axioms?

I don't know much about set theory or foundational mathematics, this question arose just out of curiosity. As far as I know, the widely accepted axioms of set theory is the Zermelo-Fraenkel axioms ...
20
votes
3answers
1k views

Defining cardinality in the absence of choice

Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any ...
20
votes
3answers
1k views

Is there a constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$?

Assuming the Axiom of Choice, every vector space has a basis, though it can be troublesome to show one explicitly. Is there any constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$, the ...
19
votes
1answer
1k views

Vector Spaces and AC

I know that the proof that every vector space has a basis uses the Axiom of Choice, or Zorn's Lemma. If we consider an axiom system without the Axiom of Choice, are there vector spaces that provably ...
18
votes
6answers
953 views

Implication and Interpretation of Banach Tarski

As I understand, the Banach-Tarski paradox says a ball in 3-space may be decomposed into finitely many pieces and reassembled into two balls each of the same size as the original. Despite being called ...
18
votes
3answers
795 views

For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$

Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally: $$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$ If this statement is true, ...
18
votes
2answers
353 views

Without the Axiom of Choice, does every infinite field contain a countably infinite subfield?

Earlier today I asked whether every infinite field contains a countably infinite subfield. That question quickly received several positive answers, but the question of whether those answers use the ...
18
votes
1answer
1k views

About a paper of Zermelo

This about the famous article Zermelo, E., Beweis, daß jede Menge wohlgeordnet werden kann, Math. Ann. 59 (4), 514–516 (1904), available here. Edit: Springer link to the ...
18
votes
1answer
1k views

Proving “every set can be totally ordered” without using Axiom of Choice

It is known that the statement "every set can be totally ordered" is strictly weaker than Axiom of choice. How does one go about proving without using AC?
18
votes
1answer
440 views

Infinite prisoners with hats — is choice really needed?

The problem is this (recently asked about here): A countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces ...
17
votes
5answers
1k views

Is axiom of choice necessary for proving that every infinite set has a countably infinite subset?

Is it possible to prove the following fact without axiom of choice ? " Every infinite set has a countably infinite subset". Can it be proved that axiom of choice is necessary here ?
17
votes
5answers
2k views

Importance of Axiom of Choice

First a quick question regarding the definition of the axiom of choice. Do the sets have to be mutually disjoint nonempty sets or just non-empty? One source states: "For any set X of nonempty sets, ...
17
votes
3answers
1k views

The Use of the Axiom of Choice in an Elementary Proof

I wanted to give some of the new undergrad analysis students the following problem: given the real numbers (with the standard topology, as they'd expect) one cannot have an uncountable set such that ...
17
votes
3answers
690 views

Where do we need the axiom of choice in Riemannian geometry?

A friend of mine is a differential geometer, and keeps insisting that he doesn't need the axiom of choice for the things he does. I'm fairly certain that's not true, though I haven't dug into the ...
17
votes
1answer
534 views

How to formulate continuum hypothesis without the axiom of choice?

Please correct me if I'm wrong but here is what I understand from the theory of cardinal numbers : 1) The definition of $\aleph_1$ makes sense even without choice as $\aleph_1$ is an ordinal number ...
17
votes
1answer
3k views

The cardinality of a countable union of countable sets, without the axiom of choice

One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $\aleph_2$. My solution shows that it does not have ...
16
votes
3answers
5k views

What is a basis for the vector space of continuous functions?

A natural vector space is the set of continuous functions on $\mathbb{R}$. Is there a nice basis for this vector space? Or is this one of those situations where we're guaranteed a basis by invoking ...
16
votes
1answer
2k views

Constructing a subset not in $\mathcal{B}(\mathbb{R})$ explicitly

While reading David Williams's "Probability with Martingales", the following statement caught my fancy: Every subset of $\mathbb{R}$ which we meet in everyday use is an element of Borel ...
16
votes
1answer
437 views

Cardinality of a locally compact Hausdorff space without isolated points

I am interested in the following result: Theorem. A locally compact Hausdorff topological space $X$ without isolated points has at least cardinality $\mathfrak{c}$. To prove it, one can find two ...
15
votes
2answers
788 views

Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF

Special Aleph Hypothesis AH(0) is the claim $2^{\aleph_0}=\aleph_1$, i.e. there is a bijection from $2^{\aleph_0}$ to $\aleph_1$. Continuum Hypothesis CH is the claim $\aleph_0 \leq \mathfrak{a}< ...
15
votes
2answers
733 views

Do we know that we can't define a well-ordering of the reals?

Folklore has it that it is impossible to define a well-ordering of the reals explicitly. There exist pointwise definable models of ZFC where every set is definable without parameters: it is the ...
15
votes
2answers
2k views

Axiom of Choice Examples

In the wikipedia article, two examples are given which use/ do not use the axiom of choice. They are: Given an infinite pair of socks, one needs AC to pick one sock out of each pair. Given an ...
15
votes
1answer
1k views

Infinite Set is Disjoint Union of Two Infinite Sets

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite. In ZF, can you prove that every infinite set is the union of two ...
15
votes
2answers
414 views

A question about a two player game and axiom of choice

Suppose two players 1 and 2 play the following game: Player 1 starts by playing the set of reals $\mathbb{R}$. Player 2 plays an uncountable subset $Y_1$ of $\mathbb{R}$. Then player 1 plays an ...
14
votes
3answers
1k views

What is an example of two sets which cannot be compared?

In set theory, if we do not assume the Axiom of Choice, we cannot prove the Trichotomy Law between cardinals. That is, we cannot prove that for any two sets, there exists an injection from one to the ...
14
votes
3answers
489 views

Topology and axiom of choice

It it an easy exercise to show that if $X$ is first-countable then for every point $x$ and every subset $A$ we have $x \in \text{cl}A$ iff there exists a sequence $(x_n)_n$ that converges to $x$. ...
14
votes
1answer
891 views

Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Math people: It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. ...