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
17 votes
2 answers
3k views

Does ZFC prove the universe is linearly orderable?

It is consistent with ZFC that the universe is well-ordered, e.g. in $V=L$ where global choice holds. I also know that it is consistent that global choice fails (although I have no immediate example ...
Asaf Karagila's user avatar
  • 38.1k
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
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
18 votes
0 answers
854 views

Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal number line is universal for all class linear orders, or in other words, that every linear order (including proper-class-sized) linear ...
Joel David Hamkins'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 ...
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
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
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
14 votes
4 answers
2k views

What can be preserved in mathematics if all constructions are carried out in ZF?

This is inspired by this discussion. I see that the debates about the necessity of the axiom of choice in this or that statement are still ongoing. In this regard, I became interested in whether there ...
Sergei Akbarov's user avatar
10 votes
2 answers
982 views

Relationship between fragments of the axiom of choice and the dependent choice principles

The dependent choice principle ${\rm DC}_\kappa$ states that if $S$ is a nonempty set and $R$ is a binary relation such that for every $s\in S^{\lt\kappa}$, there is $x\in S$ with $sRx$, then there ...
Victoria Gitman's user avatar
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 ...
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
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
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
12 votes
5 answers
6k views

Subset of the plane that intersects every line exactly twice

In a comment to this question, Tim Gowers remarked that using the axiom of choice, one can show that there exists a subset of the plane that intersects every line exactly twice (although it has yet to ...
Tony Huynh's user avatar
  • 31.5k
12 votes
3 answers
4k views

Existence of prime ideals and Axiom of Choice.

One of the must obvious equivalences of Axiom of Choice is the converse of Krull Theorem. Bernhard Banaschewski in the Article titled by A New Proof that “Krull implies Zorn” showed a very simple ...
Ali Reza's user avatar
  • 1,778
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
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
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
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
23 votes
5 answers
6k views

Hahn-Banach without Choice

The standard proof of the Hahn-Banach theorem makes use of Zorn's lemma. I hear that, however, Hahn-Banach is strictly weaker than Choice. A quick search leads to many sources stating that Hahn-Banach ...
Mark Kim's user avatar
  • 1,162
20 votes
2 answers
3k views

What is a Choice Principle, really?

This question is quite soft, and I apologize in advance if it borderline off-topic. When working in theories between ZF and ZFC the term "choice principle" is heard quite often. For example: $\quad$ ...
Asaf Karagila's user avatar
  • 38.1k
9 votes
2 answers
1k views

Are there known examples of sets whose power set is equal in size to power set of larger sets only in absence of choice?

The question of existence of sets $x,y$ such that $$|x|<|y| \wedge |P(x)|=|P(y)|$$ is known to be independent of $\text{ZFC}$! But are there known examples of sets fulfilling the above condition ...
Zuhair Al-Johar's user avatar
1 vote
0 answers
722 views

Finding a unique and finite expected value for almost all measurable functions?

Let $(X,d)$ be a metric space. If set $A\subseteq X$, let $H^{\alpha}$ be the $\alpha$-dimensional Hausdorff measure on $A$, where $\alpha\in[0,+\infty)$ and $\text{dim}_{\text{H}}(A)$ is the ...
Arbuja's user avatar
  • 1
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
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
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
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
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
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
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
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
24 votes
1 answer
2k views

In what ways is ZF (without Choice) "somewhat constructive"

Let me summarize what I think I understand about constructivism: "Constructive mathematics" is generally understood to mean a variety of theories formulated in intuitionist logic (i.e., not assuming ...
Gro-Tsen's user avatar
  • 29.9k
23 votes
3 answers
3k views

Half Cantor-Bernstein without choice

I had a discussion with one of my teachers the other day, which boiled to the following question: Assume ZF. Let $A,B$ be sets such that there exist $f\colon A\to B$ which is injective and $g\colon A\...
Asaf Karagila's user avatar
  • 38.1k
21 votes
4 answers
3k views

What sort of large cardinal can $\aleph_1$ be without the axiom of choice?

Assuming the axiom of choice it is very easy to see that $\aleph_1$ is a regular Joe of a successor cardinal. It is not very large in any way except the fact that it is the first uncountable cardinal. ...
Asaf Karagila's user avatar
  • 38.1k
20 votes
2 answers
1k views

Without choice, can every homomorphism from a profinite group to a finite group be continuous?

In ZFC, some homomorphisms from profinite groups to finite groups are discontinuous. For instance, see the examples in this question. However, all three constructions given use consequences of the ...
Will Sawin's user avatar
  • 135k
16 votes
1 answer
705 views

The axiom $I_0$ in the absence of $AC$

It is well-known that if $AC$ holds and if $j: L(V_{\lambda+1}) \to L(V_{\lambda+1})$ is a non-trivial elementary embedding with $crit(j) < \lambda,$ then $\lambda$ has countable cofinality (and in ...
Mohammad Golshani's user avatar
15 votes
2 answers
2k views

Can an infinite number of mathematicians guess the number in a box with only one error?

In this question the following observation was made: Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened. Define ...
user44653's user avatar
  • 251
14 votes
3 answers
1k views

Axiom of choice for sets of finite sets

The question I am going to ask is really to satisfy my curiosity, as I am not at all an expert of the subject and do not plan to really work on it. Hence, if you think the question is not suitable for ...
Mathieu Baillif's user avatar
12 votes
0 answers
449 views

Does Hahn-Banach for $\ell^\infty$ imply the existence of a non-measurable set?

Working over ZF but without the Axiom of Choice (AC), assume that the Hahn–Banach Theorem holds for $\ell^\infty$. Does it follow that there exists a set of real numbers that is not Lebesgue ...
Timothy Chow's user avatar
  • 78.1k
12 votes
5 answers
1k views

Does k(X) have a k-basis for every set X, without AC?

This question is inspired by Pace Nielsen's recent question Does a left basis imply a right basis, without AC?. For any field $k$, the field $k(x)$ of rational functions in one variable has an ...
Jeremy Rickard's user avatar
11 votes
2 answers
639 views

Non smallness of the set of anafunctors without AC?

Trying to construct a model category constructively is difficult. One often mention the fact that without the axiom of choice one cannot prove that the localization of the category of small categories ...
Simon Henry's user avatar
  • 39.9k
11 votes
0 answers
437 views

Does Sageev's result need an inaccessible?

In 1981, building on work by Ellentuck in 1974, Sageev showed ("A model of ZF + there exists an inaccessible, in which the Dedekind cardinals constitute a natural non-standard model of arithmetic," ...
Noah Schweber's user avatar
11 votes
2 answers
1k views

Is sigma-additivity of Lebesgue measure deducible from ZF?

Is sigma-additivity (countable additivity) of Lebesgue measure (say on measurable subsets of the real line) deducible from the Zermelo-Fraenkel set theory (without the axiom of choice)? Note 1. ...
Mikhail Katz's user avatar
  • 15.1k
8 votes
2 answers
467 views

Constructively, are all fibrations cloven?

A "cloven fibration" is a fibration for which we have an explicit choice of cartesian liftings; this is often phrased as, "We can pick a lifting without using the axiom of choice". Firstly, I'm a bit ...
Jonathan Sterling's user avatar
8 votes
2 answers
3k views

Compact Hausdorff spaces without isolated points in ZF

$S$ is uncountable := $\vert\mathbb{N}\vert<\vert S\vert$ $S$ is noncountable := $\vert S\vert \not\leq \vert\mathbb{N}\vert$ $(X,T)$ is a nice space := $(X,T)$ is a compact Hausdorff space ...
user avatar