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

8
votes
3answers
983 views

The smallest infinity and the axiom of choice

The short version of this question is: which (natural) axiom should be added to ZF so that the statement "$\aleph_{0}$ is the smallest infinity" becomes true? A set $A$ is called infinite if it can ...
1
vote
0answers
57 views

$|A^2|=|A|$ for every infinite $A$ iff Axiom of Choice holds. [duplicate]

I've seen this assertion in a few comments around the site, and I found the answer to the $\rightarrow$ implication here. Does anyone know a (hopefully simple) proof of the $\leftarrow$ implication?
1
vote
1answer
108 views

What is the first order formulation of Zorn's lemma in the language of set theory?

Very often in notes of courses in set theory you find the assertion that in ZF the Axiom of choice (AC) is equivalent to Zorn's Lemma (ZL) (which is equivalent to Well Ordering Principle which it ...
1
vote
0answers
48 views

Proving implication on well ordered set implies AC

Consider the following statement: If $A$ is a well-ordered set such that every nonempty subset of $A$ has a maximal element, then $A$ is finite. I am trying to prove that this statement implies ...
4
votes
1answer
74 views

Countable cartesian product and Axiom of Choice

In the A taste of Topology book, when talking about Cartesian product $\prod\{S:S\in\mathcal{S}\}$, the author writes the following: It is straightforward that $\prod\{S:S\in\mathcal{S}\}\neq\...
1
vote
3answers
176 views

Ordinal with given cardinality (without AC)

Is it possible to show that every cardinality has an ordinal with this cardinality (without the axiom of choice)? If so, how?
1
vote
0answers
65 views

Proof: Every lattice has a maximal filter iff AC

I'm working through a proof of Herrlich's book Axiom of Choice, p.58 (Google books): Equivalent are Every lattice has a maximal filter. Axiom of Choice. In this book, a lattice is ...
7
votes
3answers
221 views

Existence of mathematical objets constructed using the axiom of choice

Let consider the Vitali set $V \subset \mathbb R$, which is constructed using the axiom of choice. (I could take any other mathematical "object" that can be constructed using the axiom of choice, but ...
2
votes
0answers
37 views

How Does the Following Definition of the Axiom of Choise Entail that Elements Are Simultaneously Chosen from an Infinite Collection of Nonempty Sets [duplicate]

The following excerpt is from Ethan Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics (2nd ed, 2011 : page 121) and concerns one of the motivations for introducing the axiom of ...
6
votes
2answers
158 views

Does the law of the excluded middle imply the existence of “intangibles”?

First off, I'm not sure if "intangible" is standard terminology, Wikipedia defines an intangible object to be: "objects that are proved to exist, but which cannot be explicitly constructed". So if ...
1
vote
1answer
47 views

Axiom Of Choice to create a sequence of right inverses

I want to construct a sort of sequence of right inverses. My question is whether the construction uses the Axiom Of Choice correctly. Suppose I have a sequence of surjective functions $$ \ldots\...
9
votes
2answers
203 views

What's an example of a vector space that doesn't have a basis if we don't accept Choice?

I've read that the fact that all vector spaces have a basis is dependent on the axiom of choice, I'd like to see an example of a vector space that doesn't have a basis if we don't accept AoC. I'm ...
0
votes
0answers
32 views

Prob 2(d) Sec 9 in Munkres' TOPOLOGY 2nd edition: Is it possible to construct a choice function? [duplicate]

Here's Lemma 9.2 in Topology by James R. Munkres, 2nd edition: Given a collection $\mathscr{B}$ of non-empty sets (not necessarily disjoint), there exists a function $$c \colon \mathscr{B} \to \...
8
votes
2answers
278 views

Axiom of Choice needed to “categorify” the cardinals?

I was playing around in $\mathsf{Set},$ trying to reduce it modulo isomorphisms to make a category $\mathsf{Card},$ letting the objects of $\mathsf{Card}$ be the isomorphism classes of $\mathsf{Set}$ ...
5
votes
1answer
90 views

Is it consistent that every set is the countable union of sets with smaller cardinality, or is it just alephs?

(note: in what follows by "consistent" I mean "consistent relative to large cardinals") My question regards the exact statement of result which Gitik has proven in his paper "All Uncountable ...
4
votes
1answer
183 views

Existence of Hamel basis, choice and regularity

Blass (1984) shows that the existence of Hamel basis for arbitrary vector space over any field implies the axiom of choice. However such implication needs the axiom of regularity. As in Blass' article,...
0
votes
2answers
73 views

Difference Between Axiom of choice and axiom of countable choice.

My question is: In particular, does the result that every surjective (continuous or even linear if it matters) function has a pre-inverse depend on the full axiom of choice or just the axiom of ...
0
votes
0answers
34 views

In $ZF$, $AC$ is equivalent to $\forall \alpha (\mathscr P(\alpha)$ can be well-ordered) [duplicate]

This is an exercise from Kunen - An introduction to independence proofs that I have hard time to solve. In $ZF$, $AC$ is equivalent to $\forall \alpha (\mathscr P(\...
4
votes
1answer
84 views

$\neg \textsf{AC}+ \neg\textsf{CH}$

Is there some interesting\surprising results that have only been proven by assuming $\neg \textsf{AC}$ and $\neg\textsf{CH}$ ? Is there some interesting\surprising results implying both $\neg \...
2
votes
6answers
121 views

What is some simple to prove very counter-intuitive result obtained by Choice?

I'm aware of some theorems like the Banach-Tarski's which yield very counter-intuitive results, however, it's proof is far beyond my knowledge, so I'm looking for some result that is easy to prove ...
6
votes
1answer
90 views

What is a projective object in $\rm Set$?

What property of a set in $\sf{ZF}$ is equivalent to its being a projective object in the category $\rm Set$? Since all sets are projective assuming $\sf AC$ my guess is that it is equivalent to well-...
2
votes
2answers
43 views

Representing a vector space as a sum of subspaces

In a linear algebra book I'm reading now, there was the following exercise: Let $W\subseteq V$ be a subspace of vector space $V$. Do there always exist two subspaces $W_1,W_2\subseteq V$ such that:...
1
vote
0answers
37 views

On Cantor's argument [duplicate]

What axioms of set theory are needed for Cantor's diagonalization argument to work and why? What happens if we do away with some of these axioms (for instance Axiom of Choice)?
1
vote
2answers
78 views

Proving the Axiom of Choice for countable sets

I am new to the axiom of choice, and currently working my way through some exercises. I am struggling with the following exercise: Exercise - Prove the Axiom of Choice (every surjective $f: X \to Y$ ...
3
votes
2answers
70 views

Does this proof make use of the Axiom of Choice?

Theorem Let $X$ be uncountable. Let $A$ be countable. Then $|X\cup A| = |X|$. Proof As $|X|>\aleph_0 \rightarrow \exists f: \Bbb N \to X$ injective. Note that $\operatorname {Im}(f)=\...
8
votes
1answer
123 views

Do the ZF-provable forcing principles differ from the ZFC-provable forcing principles?

In "The Modal Logic of Forcing", Joel David Hamkins and Benedikt Löwe show that the ZFC-provable forcing principles are exactly those of the modal logic S4.2 (interpreting $\Diamond \phi$ as asserting ...
0
votes
2answers
54 views

Axiom of choice and the empty set

Could someone explain to me why it is important for a set to be non-empty when working with a choice function?
3
votes
1answer
91 views

Why isn't there a total order of $\cal P(\Bbb R)$?

I have heard that, in some models of ZF, $\cal P(\Bbb R)$ has no total order. How could one prove this? I already know that $\Bbb R$ isn't necessarily well-ordered. I'm guessing that one could reduce ...
1
vote
2answers
68 views

Context for Russell's Infinite Sock Pair Example

I wanted to verify the following considerations on the context of Russell's infinite sock pair conundrum. The conundrum pointed out that a rule for choosing from pairs of shoes is possible a-priori. ...
0
votes
1answer
127 views

Axiom of choice in HoTT without sethood requirement

3.8.3 of the HoTT book gives the following as a variant of the axiom of choice: $\Pi$ (X : U) (Y : X $\rightarrow$ U), (isSet X) $\rightarrow$ ($\Pi$ (x : X), isSet (Y x)) $\rightarrow$ ($\Pi$ (x :...
6
votes
6answers
418 views

When using an axiom scheme, are we implicitly using a choice principle?

I heard an interesting argument from a colleague recently that went something like this. Whenever we are using an axiom scheme, we are essentially choosing one of the instances of this scheme, and ...
7
votes
2answers
550 views

Cardinality of the Euclidean topology and the axiom of choice

It is relatively straightforward to prove that the Euclidean topology has the same cardinality as the space itself. I have sketched a proof below. The proof seems to rely quite heavily on the axiom of ...
13
votes
1answer
262 views

Is there a group with countably many subgroups, but is not countable in ZF?

Inspired by this question, although I don't think it was the OP's intention, hence this separate question: Is there a group $G$ with countably many subgroups, but is a not a countable group itself ...
18
votes
2answers
360 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 ...
2
votes
3answers
91 views

If a certain kind of object exists and is unique, can we prove its existence and uniqueness without axiom of choice?

Suppose that using Zorn's lemma, we have proven that an object with some properties exists and then we've proven that such object is unique. Can we always conclude that we can prove the existence (...
1
vote
1answer
34 views

A $\sigma$-algebra equivalent to the Lebesgue algebra under CC

Working in $\sf ZF$, is there a natural definition of an algebra $\Sigma$ with the following properties: $\Sigma$ is a $\sigma$-algebra on $\Bbb R$, i.e. it is closed under complement and countable ...
4
votes
0answers
66 views

Codimensions of $\mathbb{Q}$-subspaces of $\mathbb{R}$

Under the Axiom of Choice, we can pick a Hamel basis $H$ for $\mathbb{R}$ as a vector space over $\mathbb{Q}$. Adjoining all but some elements of $H$ to $\mathbb{Q}$ shows that for any cardinality $1\...
2
votes
2answers
119 views

On Fraenkel-Mostowski choiceless set theory

I have been trying to solve an exercise from Kunen (1980) on Fraenkel and Mostowski's construction of a choiceless model of set theory. I have a couple of questions: The model is constructed from ...
0
votes
1answer
87 views

Showing that a measurable set contains a subset that is not Lebesgue measurable.

This is the last part of my homework assignment for Measure Theory. Let $\lambda^d$ be the Lebesgue measure on the $\sigma$-algebra $\Lambda^d$ of Lebesgue measurable sets of $\mathbb{R}^d$. We know ...
1
vote
0answers
34 views

The Axiom of Choice, and the statement that whenever there is a surjection $A \to B$ there is an injection $B \to A$ [duplicate]

Is there a model of $\mathsf{ZF}$ in which the Axiom of Choice fails but the following statement holds for arbitrary sets $A, B$: there is an injection $A \to B$ if there is a surjection $B \to A$...
0
votes
1answer
70 views

every function has an injective extension that respects its order

I'm told that for every real-valued function $f$ there is an injective function $f'$ that respects the ordering given by $f$ in that $$f(a) < f(b) \implies f'(a) < f'(b)$$ and $$a \neq b \text{ ...
1
vote
2answers
37 views

Does this proof that $\chi(\mathbb{Q}^2) = 2$ rely on choice?

I'm teaching a course on discrete math and came across a paper related to the Hadwiger-Nelson problem. The question asks how many colors are needed to color every point in $\mathbb{Q}^2$ such that no ...
0
votes
1answer
41 views

Axiom of Choice with randomized choice function

Does the axiom of choice require the choice function to be deterministic or can it be a random function (i.e., its image under some probability space is the set under considertation?)
3
votes
1answer
93 views

Infinite prisoners with hats where the prisoners do not know their position.

The infinite prisoners with hats puzzle runs as follows. We have a countably infinite group of prisoners numbered $\{1, 2, \dots\}$, each of whom is wearing either a white hat or a black hat. The $n$...
5
votes
1answer
210 views

On the Axiom of Choice for Conglomerates and Skeletons

Say that $\mathcal{X}$ is a conglomerate if $\mathcal{X} = \{X_i: i \in I\}$, where each $X_i$ and $I$ are classes. The Axiom of Choice for Conglomerates is the statement: Whenever $\mathcal{X}$ and $\...
1
vote
0answers
26 views

(Ordinal number)How to prove that epsilon-naught is countable without using Axiom of Choice? [duplicate]

How to prove that epsilon-naught is countable without using Axiom of Choice? or, Can we explicitly show that there is isomorpism between epsilon naught and subset of rational number?
1
vote
3answers
55 views

Is there an explicit function / no-axiom-of-choice construction $f:[0,1] \to [0,1]$ so that uncountably many disjoint subsets map onto $[0,1]$?

So if I asked: "Is there an explicit function / no-axiom-of-choice construction $f:[0,1] \to [0,1]$ so that COUNTABLY many disjoint subsets of $[0,1]$ map onto $[0,1]$?" The answer would be yes, ...
4
votes
1answer
54 views

Representation of $\mathbb{R}$, drop continuity assumption, Axiom of Choice.

A representation, for instance, of $\mathbb{R}$ is a group homomorphism $f: \mathbb{R} \to \text{GL}_n(\mathbb{R})$. If we assume that $f$ is continuous, then there is a very nice formula for all such ...
3
votes
3answers
144 views

Elementary theorems that require AC

It seems that AC is hiding (maybe concealed?) even in some elementary results. An example: Theorem: Let $X \subseteq \mathbb R$ and let $x_0 \in \mathbb R$ be an accumulation point of $X$. Then ...
4
votes
2answers
69 views

Conditions that topologies must have if (only if) the condition “$G_\delta$ iff (open or closed)” holds?

Consider the class of topological spaces $\langle X,\mathcal T\rangle$ such that the following are equivalent for $A\subseteq X$: $A$ is a $G_\delta$ set with respect to $\mathcal T$ $A\in\mathcal T$...