120 votes

Axiom of choice, Banach-Tarski and reality

There are two ingredients in the Banach-Tarski decomposition theorem: The notion of space, together with derived notions of part and decomposition. The axiom of choice. Most discussion about the ...
Andrej Bauer's user avatar
  • 47.7k
58 votes
Accepted

Zorn's lemma: old friend or historical relic?

I agree with almost everything in your post. But still, I believe I know why people use Zorn's lemma. My answer. Zorn's lemma encapsulates succinctly many of the consequences of AC via transfinite ...
Joel David Hamkins's user avatar
45 votes
Accepted

Do vector spaces without choice satisfy Cantor-Schroeder-Bernstein?

Without the axiom of choice, it is possible that there is a vector space $U\neq 0$ over a field $k$ with no nonzero linear functionals. Let $V$ be the direct sum of countably many copies of $U$, and $...
Jeremy Rickard's user avatar
42 votes

Axiom of choice, Banach-Tarski and reality

It's notable that most of the "bread and butter" mathematical consequences of the axiom of choice are actually consequences of countable choice. (Every infinite set contains a countable subset, a ...
Nik Weaver's user avatar
41 votes

Unnecessary uses of the axiom of choice

Sometimes people prove the Schröder–Bernstein theorem by saying it follows easily from the well-ordering theorem, which is equivalent to the axiom of choice. But it can be proved without the axiom of ...
41 votes

Zorn's lemma: old friend or historical relic?

I agree with the existing answers, but I personally like Zorn's lemma both pedagogically and mathematically for an additional reason: the "poset of partial solutions" that it introduces is a ...
Noah Schweber's user avatar
39 votes
Accepted

Can a countable union of two-element sets be uncountable?

Yes, it is possible. This phenomenon is sometimes called Russell's socks, named after an analogy due to Russell about how one can pick out a shoe from an infinite set of pairs of shoes, but not for ...
Wojowu's user avatar
  • 27.4k
36 votes

Axiom of choice, Banach-Tarski and reality

The other answers don't seem to have said much about why the axiom of choice is widely regarded as plausible. Let me try to address that question. First let's dispose of some non-reasons. In ...
Timothy Chow's user avatar
  • 78.1k
36 votes
Accepted

Can one show that the real field is not interpretable in the complex field without the axiom of choice?

An interpretation of $(\mathbb R,+,\cdot)$ in $(\mathbb C,+,\cdot)$ in particular provides an interpretation of $\DeclareMathOperator\Th{Th}\Th(\mathbb R,+,\cdot)$ in $\Th(\mathbb C,+,\cdot)$. To see ...
Emil Jeřábek's user avatar
34 votes
Accepted

Does the "three-set-lemma" imply the Axiom of Choice?

The three-set lemma is listed as form 285 in Howard and Rubin's "Consequences of the axiom of choice". According to their book, the earliest appearance seems to be a problem in a 1963 issue of the ...
godelian's user avatar
  • 5,642
34 votes

Unnecessary uses of the axiom of choice

It's common to use the axiom of choice to prove that nonzero commutative rings have the invariant basis number property: in other words, that for a nonzero commutative ring $ R $, the $ R $-modules $ ...
33 votes
Accepted

A Krull-like Theorem and its possible equivalence to AC

Nice question ! I believe the homework exercise implies AC. Indeed, assume its conclusion holds, and let $R$ be a ring with no maximal ideal. I'm going to prove that $R$ is zero, thus proving Krull's ...
Maxime Ramzi's user avatar
  • 13.3k
32 votes
Accepted

Chromatic number of a topological space

The chromatic number $\chi(X)$ of a topological space $X$ is related to the separation dimension $t(X)$ introduced and studied by Steinke. The separation dimension $t(X)$ is defined inductively: $\...
Taras Banakh's user avatar
  • 40.8k
32 votes
Accepted

How much of the axiom of choice do you need in mathematics?

Your hypothesis is in a sense stronger than just assuming ZFC outright. Namely, if we have $\lambda$-DC for some inaccessible cardinal $\lambda$, and ZF in the background, then in particular, we will ...
Joel David Hamkins's user avatar
32 votes
Accepted

How much of mathematical General Relativity depends on the Axiom of Choice?

The dependence on AC through the use of Zorn's lemma in the proof of the Choquet-Bruhat–Geroch theorem on the existence of a maximal globally hyperbolic development for solutions of the Einstein ...
Igor Khavkine's user avatar
31 votes
Accepted

Axiom of Choice for collections of Equinumerous sets

For any set $A$ and nonempty subset $B \subseteq A$, $B \times A^\omega$ is equinumerous with $A^\omega$: there is an injection from $B \times A^\omega$ to $A^\omega$ because $B \subseteq A$, and ...
paste bee's user avatar
  • 1,346
30 votes
Accepted

How to construct a basis for the dual space of an infinite dimensional vector space?

It is consistent with the axioms of $\sf ZF$ that this is impossible. Specifically, if you consider $\Bbb R[x]$, then its dual space is just $\Bbb{R^N}$. And it is consistent with $\sf ZF$ that $\Bbb{...
Asaf Karagila's user avatar
  • 38.1k
30 votes

Do vector spaces without choice satisfy Cantor-Schroeder-Bernstein?

There are models of ZF+DC in which every subset of every Polish space has the property of Baire (I can try to add references later, I think to Solovay and Shelah, but these are pretty well known). ...
Nate Eldredge's user avatar
29 votes

Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

On the one hand, one might expect that there can be no fully satisfactory example of the phenomenon, in light of the observations mentioned in the comments, namely, that every partial order fulfilling ...
Joel David Hamkins's user avatar
28 votes

Bishop quote stating that axiom of choice is constructively valid

According to the BHK interpretation of intuitionistic logic we have that: A proof of $\exists x \in A . \phi(x)$ consists of a pair $(a, p)$ where $a \in A$ and $p$ is a proof of $\phi(a)$. A proof ...
Andrej Bauer's user avatar
  • 47.7k
27 votes

Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?

The answer to your question is (almost) yes (almost is because of the addition of DC to the statement). Recently Gabriel Goldberg has proved ''Con(NBG+DC+Reinhardt)$ \implies$ Con(ZFC+I0)''. ...
Mohammad Golshani's user avatar
27 votes

Axiom of choice, Banach-Tarski and reality

Are there reasons why it is plausible (for physicists, philosophers, mathematicians) to believe that not all sets should be measurable? Yes. If every set of reals is Lebesgue measurable, then you ...
Burak's user avatar
  • 4,115
27 votes
Accepted

Does the axiom of choice follow from the statement "Every simple undirected graph is either connected, or its complement is connected"?

(S) is a theorem of ZF. Proof: Let $G$ be a graph, and let $v$ be a vertex of $G$. Define $$P_v = \{w \,:\, \text{there is a path from } v \text{ to } w\}.$$ If $P_v$ is the vertex set of $G$, then $...
Will Brian's user avatar
  • 17.4k
26 votes
Accepted

Are classes still "larger" than sets without the axiom of choice?

Yes, your remarks about incomparability of sets and classes without the axiom of choice are correct. Yes, in ZF (or in GB), the axiom of choice is equivalent to the assertion that every set injects ...
Joel David Hamkins's user avatar
25 votes
Accepted

Wiki for consequences of axiom of choice?

Sorry I just saw this, and thank you @martin-sleziak for informing me of this question! I'm still investigating what went wrong, but cgraph is back online: https://cgraph.inters.co About the original &...
Ioanna's user avatar
  • 1,252
24 votes

Does the "three-set-lemma" imply the Axiom of Choice?

To complement godelian’s answer, the three-set lemma is not provable in ZF alone, as it implies the axiom of choice for families of pairs. This holds even if we allow any finite (or even just well ...
Emil Jeřábek's user avatar
24 votes

Is the theory Flow actually consistent?

I am one of the authors of this preprint. Concerning the Grothendieck Universe, my first answer is this. Some terms of Flow are called ZF-sets. Through the use of our restriction axiom we are able to ...
Adonai Sant'Anna's user avatar
24 votes

Unnecessary uses of the axiom of choice

A good number of theorems in Ramsey theory and related areas are what logicians call $\Pi^1_2$ statements—those of the form "for every set of integers $X$ there is a set of integers $Y$ ...
24 votes

Absolute Galois group, number theory and the Axiom of Choice

In the absence of the axiom of choice, it is still possible to define the "usual" algebraic closure of $\mathbb{Q}$ because you can just explicitly enumerate all polynomials with integer ...
Timothy Chow's user avatar
  • 78.1k
23 votes

Can one show that the real field is not interpretable in the complex field without the axiom of choice?

(1) $\mathbb{C}$ is stable, (2) $\mathbb{R}$ is unstable, and (3) stability is preserved under interpretations. Of course the usual development of stability uses a lot of choice, but (2) and (3) are ...
Erik Walsberg's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible