Questions tagged [axiom-of-choice]
An important and fundamental axiom in set theory sometimes called Zermelo's axiom of choice. It was formulated by Zermelo in 1904 and states that, given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets. The axiom of choice is related to the first of Hilbert's problems.
557
questions
249
votes
16
answers
67k
views
Why worry about the axiom of choice?
As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...
111
votes
2
answers
15k
views
Does every non-empty set admit a group structure (in ZF)?
It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary ...
95
votes
16
answers
33k
views
Most 'unintuitive' application of the Axiom of Choice?
It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
72
votes
4
answers
22k
views
Non-Borel sets without axiom of choice
This is a simple doubt of mine about the basics of measure theory, which should be easy for the logicians to answer. The example I know of non Borel sets would be a Hamel basis, which needs axiom of ...
65
votes
9
answers
13k
views
Axiom of choice, Banach-Tarski and reality
The following is not a proper mathematical question but more of a metamathematical one. I hope it is nonetheless appropriate for this site.
One of the non-obvious consequences of the axiom of choice ...
63
votes
14
answers
6k
views
Unnecessary uses of the axiom of choice
What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
...
57
votes
6
answers
5k
views
Is the non-triviality of the algebraic dual of an infinite-dimensional vector space equivalent to the axiom of choice?
If $V$ is given to be a vector space that is not finite-dimensional, it doesn't seem to be possible to exhibit an explicit non-zero linear functional on $V$ without further information about $V$. The ...
51
votes
1
answer
6k
views
Does $2^X=2^Y\Rightarrow |X|=|Y|$ imply the axiom of choice?
The Generalized Continuum Hypothesis can be stated as $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. We know that GCH implies AC (Jech, The Axiom of Choice, Theorem 9.1 p.133).
In fact, a relatively weak ...
49
votes
7
answers
7k
views
Zorn's lemma: old friend or historical relic?
It is often said that instead of proving a great theorem a mathematician's fondest dream is to prove a great lemma. Something like Kőnig's tree lemma, or Yoneda's lemma, or really anything from this ...
48
votes
1
answer
4k
views
When does $A^A=2^A$ without the axiom of choice?
Assuming the axiom of choice the following argument is simple, for infinite $A$ it holds: $$2\lt A\leq2^A\implies 2^A\leq A^A\leq 2^{A\times A}=2^A.$$
However without the axiom of choice this doesn't ...
48
votes
0
answers
2k
views
How many algebraic closures can a field have?
Assuming the axiom of choice given a field $F$, there is an algebraic extension $\overline F$ of $F$ which is algebraically closed. Moreover, if $K$ is a different algebraic extension of $F$ which is ...
47
votes
0
answers
2k
views
Concerning proofs from the axiom of choice that ℝ³ admits surprising geometrical decompositions: Can we prove there is no Borel decomposition?
This question follows up on a comment I made on Joseph O'Rourke's
recent question, one of several questions here on mathoverflow
concerning surprising geometric partitions of space using the axiom
of ...
45
votes
4
answers
8k
views
Does the fact that this vector space is not isomorphic to its double-dual require choice?
Let $V$ denote the vector space of sequences of real numbers that are eventually 0, and let $W$ denote the vector space of sequences of real numbers. Given $w \in W$ and $v \in V$, we can take their "...
45
votes
2
answers
2k
views
Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?
Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few ...
42
votes
2
answers
2k
views
Do vector spaces without choice satisfy Cantor-Schroeder-Bernstein?
If $V \hookrightarrow W$ and $W \hookrightarrow V$ are injective linear maps, then is there an isomorphism $V \cong W$?
If we assume the axiom of choice, the answer is yes: use the fact that every ...
41
votes
2
answers
2k
views
On the difference between two concepts of even cardinalities: Is there a model of ZF set theory in which every infinite set can be split into pairs, but not every infinite set can be cut in half?
An interesting question has arisen over at this
math.stackexchange
question
about two concepts of even in the context of infinite
cardinalities, which are equivalent under the axiom of
choice, but ...
40
votes
3
answers
5k
views
How much of mathematical General Relativity depends on the Axiom of Choice?
One of the cornerstones of the mathematical formulation of General Relativity (GR) is the result (due to Choquet-Bruhat and others) that the initial value problem for the Einstein field equations is ...
40
votes
1
answer
4k
views
Dual Schroeder-Bernstein theorem
This question was motivated by the comments to Dual of Zorn's Lemma?
Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement
For any sets $A$ and $B$, if there are ...
38
votes
6
answers
7k
views
Why can't proofs have infinitely many steps?
I recently saw the proof of the finite axiom of choice from the ZF axioms. The basic idea of the proof is as follows (I'll cover the case where we're choosing from three sets, but the general idea is ...
38
votes
3
answers
3k
views
Can one show that the real field is not interpretable in the complex field without the axiom of choice?
We all know that the complex field structure $\langle\mathbb{C},+,\cdot,0,1\rangle$ is interpretable in the real field $\langle\mathbb{R},+,\cdot,0,1\rangle$, by encoding $a+bi$ with the real-number ...
38
votes
5
answers
6k
views
Probabilities in a riddle involving axiom of choice
The question is about a modification of the following riddle (you can think about it before reading the answer if you like riddles, but that's not the point of my question):
The Riddle:
We assume ...
36
votes
6
answers
3k
views
Distinct well-orderings of the same set
An easy consequence of the Erdős-Dushnik-Miller theorem $\kappa\to(\kappa,\omega)^2$ is the following, that will denote $(*)$ (it appears as an exercise in Kunen's book, it was probably mentioned ...
35
votes
15
answers
2k
views
Objects which can't be defined without making choices but which end up independent of the choice
It happens a lot of times that when one defines a new object (ring, module, space, group, algebra, morphism, whatever) out of given data, one first chooses some additional structure. And sometimes (...
35
votes
4
answers
8k
views
Are all sets totally ordered ?
The question is the title.
Working in ZF, is it true that: for every nonempty set X, there exists a total order on X ?
If it is false, do we have an example of a nonempty set that has no total ...
35
votes
3
answers
2k
views
How much choice is needed to show that formally real fields can be ordered?
Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...
35
votes
1
answer
1k
views
Chromatic number of a topological space
Here is a question I asked myself years ago. Since it is not really in my field, I hope to find some (partial) answers here... Since it was unclear, I precise that I am looking for an answer in ZFC, ...
35
votes
2
answers
3k
views
Is Lagrange's Theorem equivalent to AC?
Lagrange's Theorem is most often stated for finite groups, but it has a natural formation for infinite groups too: if $G$ is a group and $H$ a subgroup of $G$, then $|G| = |G:H| \times |H|$.
If we ...
34
votes
1
answer
3k
views
Is the theory Flow actually consistent?
Recently the paper
Adonai S. Sant'Anna, Otavio Bueno, Marcio P. P. de França, Renato Brodzinski, Flow: the Axiom of Choice is independent from the Partition Principle, arXiv:2010.03664
appeared on ...
33
votes
3
answers
2k
views
Wiki for consequences of axiom of choice?
I raised the following question as part of another MO question, but I am following the suggestion of Nate Eldredge to make it a question in its own right.
For many years, there has a been a valuable ...
32
votes
3
answers
6k
views
Is the statement that every field has an algebraic closure known to be equivalent to the ultrafilter lemma?
The existence and uniqueness of algebraic closures is generally proven using Zorn's lemma. A quick Google search leads to a 1992 paper of Banaschewski, which I don't have access to, asserting that ...
31
votes
2
answers
4k
views
Hahn's Embedding Theorem and the oldest open question in set theory
Hans Hahn is often credited with creating the modern theory of ordered algebraic systems with the publication of his paper Über die nichtarchimedischen Grössensysteme (Sitzungsberichte der ...
30
votes
8
answers
3k
views
Unique existence and the axiom of choice
The axiom of choice states that arbitrary products of nonempty sets are nonempty.
Clearly, we only need the axiom of choice to show the non-emptiness of the product if
there are infinitely many ...
28
votes
11
answers
7k
views
Does the Axiom of Choice (or any other "optional" set theory axiom) have real-world consequences? [closed]
Or another way to put it: Could the axiom of choice, or any other set-theoretic axiom/formulation which we normally think of as undecidable, be somehow empirically testable? If you have a particular ...
28
votes
2
answers
3k
views
Can a countable union of two-element sets be uncountable?
I am thinking about the Axiom of Choice and I am trying to understand the Axiom with some but a little progress. Many questions are arising in my head. So, I know that there exists a model of ZF set ...
28
votes
0
answers
809
views
Can one divide by the cardinal of an amorphous set?
This question arose in a discussion with Peter Doyle.
It is provable in ZF that one can divide by any positive finite cardinal $k$: if $X \times \{1,\ldots,k\} \simeq Y \times \{1,\ldots,k\}$ then $X \...
28
votes
0
answers
2k
views
Supercompact and Reinhardt cardinals without choice
A friend of mine and I ran into the following question while reading about proper forcing, and have been unable to resolve it:
Definition. A cardinal $\kappa$ is supercompact if for all ordinals $\...
27
votes
4
answers
9k
views
Finite axiom of choice: how do you prove it from just ZF?
The axiom of choice asserts the existence of a choice function for any family of sets F. Suppose, however, that F is finite, or even that F just has one set. Then how do we prove the existence of a ...
27
votes
4
answers
11k
views
Does constructing non-measurable sets require the axiom of choice?
The classic example of a non-measurable set is described by wikipedia. However, this particular construction is reliant on the axiom of choice; in order to choose representatives of $\mathbb{R} /\...
27
votes
1
answer
7k
views
Are there any non-linear solutions of Cauchy's equation $f(x+y)=f(x)+f(y)$ without assuming the Axiom of Choice?
Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be s.t. $f(x+y) = f(x) + f(y), \ \forall x, y$
It is quite obvious that this implies $f(cx)=cx$ for all $c \in \mathbb{Z}$ and even further: $\forall c \in \...
27
votes
2
answers
4k
views
Does Arzelà-Ascoli require choice?
Inspired by a recent Math.SE question entitled Where do we need the axiom of choice in Riemannian geometry?, I was thinking of the Arzelà--Ascoli theorem. Let's state a very simple version:
...
27
votes
5
answers
4k
views
What are the known implications of "There exists a Reinhardt cardinal" in the theory "ZF + j"?
This is, alas, in large part a series of questions on unpublished work of Hugh Woodin; it's also quite frivolous if Reinhardt cardinals turn out inconsistent.
Definitions:
Call $\kappa$ an $I-1(\...
27
votes
1
answer
3k
views
If $V$ is a vector space with a basis. $W\subseteq V$ has to have a basis too?
Suppose $V$ is a vector space, we say that $\mathcal B$ is a basis for $V$ if:
Every $v\in V$ can be written as a linear combination of elements of $\mathcal B$;
If $\sum\alpha_i b_i = 0$, where $\...
26
votes
3
answers
2k
views
Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?
The question is: if I assert in ZF that there exists a Reinhardt cardinal, do I really get a theory of higher consistency strength than when I assert in ZFC that there exists an I0 cardinal (the ...
26
votes
4
answers
3k
views
Nilradicals without Zorn's lemma
It's well known that the nilradical of a commutative ring with identity $A$ is the intersection of all the prime ideals of $A$.
Every proof I found (e.g. in the classical "Commutative Algebra" by ...
26
votes
2
answers
1k
views
Is Global Choice conservative over Zermelo with Choice?
To be explicit, by Zermelo set theory with Choice, ZC, I mean the theory with the same language and axioms as ZFC except not Foundation (also called Regularity) and with the axiom scheme of Separation ...
26
votes
2
answers
2k
views
Axiom of choice: ultrafilter vs. Vitali set
It is well known that from a free (non-principal) ultrafilter on $\omega$ one can define a non-measurable set of reals. The older example of a non-measurable set is the Vitali set,
a set of ...
26
votes
2
answers
3k
views
Sizes of bases of vector spaces without the axiom of choice
Assuming the axiom of choice does not hold we have that there is a vector space without a basis. The situation can be, in some sense, worse. It is consistent that there are vector spaces that have two ...
25
votes
4
answers
1k
views
Is Monsky's theorem dependent on the axiom of choice?
The extension of the 2-adic valuation to the reals used in the usual proof clearly uses AC. But is this really necessary? After all, given an equidissection in $n$ triangles, it is finite, so it ...
25
votes
2
answers
4k
views
Can a Vitali set be Lebesgue measurable? (ZF)
Here is the definition of Lebesgue measure.
The standard proof that Vitali sets are not Lebesgue measurable uses countable additivity of Lebesgue measure, which is not a theorem of ZF. (In ...
24
votes
8
answers
6k
views
Choice vs. countable choice
This question arose after reading the answers (and the comments to the answers) to Why worry about the axiom of choice?.
First things first. In my intuitive conception of the hierarchy of sets, the ...