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.

Filter by
Sorted by
Tagged with
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 ...
Konrad Swanepoel's user avatar
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 ...
Anweshi's user avatar
  • 7,272
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 ...
ThiKu's user avatar
  • 10.3k
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 ...
Konrad Swanepoel's user avatar
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 ...
Asaf Karagila's user avatar
  • 38.1k
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 ...
Pace Nielsen's user avatar
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 ...
Asaf Karagila's user avatar
  • 38.1k
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 ...
Asaf Karagila's user avatar
  • 38.1k
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 ...
Joel David Hamkins's user avatar
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 "...
Amit Kumar Gupta's user avatar
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 ...
Peter LeFanu Lumsdaine's user avatar
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 ...
Tim Campion's user avatar
  • 60.6k
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 ...
Joel David Hamkins's user avatar
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 ...
Pelota's user avatar
  • 573
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 ...
Andrés E. Caicedo's user avatar
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 ...
David Corwin's user avatar
  • 15.1k
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 ...
Joel David Hamkins's user avatar
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 ...
Denis's user avatar
  • 1,291
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 ...
Andrés E. Caicedo's user avatar
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 ...
Steven's user avatar
  • 463
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 ...
Pete L. Clark's user avatar
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, ...
N. de Rancourt's user avatar
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 ...
Ben E's user avatar
  • 643
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 ...
Jem's user avatar
  • 721
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 ...
Timothy Chow's user avatar
  • 78.1k
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 ...
Qiaochu Yuan's user avatar
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 ...
Philip Ehrlich's user avatar
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 ...
Michael Greinecker's user avatar
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 ...
DoubleJay's user avatar
  • 2,353
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 ...
Ivan Feshchenko's user avatar
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 \...
François G. Dorais's user avatar
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 $\...
Noah Schweber's user avatar
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 ...
user7758's user avatar
  • 287
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} /\...
Mark Bell's user avatar
  • 3,125
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 \...
Ignas's user avatar
  • 583
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: ...
Nate Eldredge's user avatar
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(\...
Ekki's user avatar
  • 291
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 $\...
Asaf Karagila's user avatar
  • 38.1k
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 ...
Tim Campion's user avatar
  • 60.6k
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 ...
Daniele Turchetti's user avatar
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 ...
Colin McLarty's user avatar
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 ...
Stefan Geschke's user avatar
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 ...
Asaf Karagila's user avatar
  • 38.1k
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 ...
Feldmann Denis's user avatar
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 ...
user avatar
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 ...
G. Rodrigues's user avatar
  • 1,828

1
2 3 4 5
12