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

7
votes
2answers
526 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
250 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
337 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
85 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 ...
1
vote
1answer
24 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
63 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 ...
2
votes
2answers
91 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
59 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 ...
0
votes
1answer
54 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
35 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
37 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
66 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 ...
4
votes
1answer
185 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
52 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
50 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
138 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
66 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 ...
0
votes
1answer
46 views

Defining relations without axiom of choice

One can show that the axiom of choice is equivalent to: "the product of a family of non-empty sets $\{ X_i \}_{i \in I}$ is never empty". Now, I've always seen a relation being defined via $R \subset ...
1
vote
2answers
71 views

Why does this formulation of Choice not follow from the Comprehension Schema?

I have been thinking about the following formulation of the Axiom of Choice.: For any relation $R$, there is a function $H$, which is a subset of $R$, and such that ...
1
vote
0answers
31 views

ID with ACCP implies atomic domain

PID implies Atomic domain or ID with Ascending chain condition for principal ideals. I know proof using DC. But are these facts really dependent on DC?
1
vote
2answers
46 views

Is this use of Zorn's lemma in the proof that every infinite set has a non-principal ultrafilter correct?

I just want to quickly confirm that I am using Zorn's correctly in this short proof. There is a non-principal ultrafilter on any infinite set $X$. Consider the filter $\mathcal{F}$ of of ...
0
votes
1answer
42 views

on some standard formulations of the axiom of choice

One of the standard statements of the axiom of choice is the following: Let S be a given nonvoid `universal' set. To each i in a nonvoid set I associate a nonvoid subset X_i of S. (Other ...
1
vote
1answer
49 views

Axiom of choice, proving a function is onto

I had some questions about the Axiom of choice. suppose I have a function f:A->B, where A and B are infinite sets, and I have to prove f is onto. So as a general strategy I pick an arbitrary element ...
2
votes
1answer
30 views

Equivalence of two order-theoretic notions without Choice?

A question occurred to me as I was considering an earlier question of mine, and wasn't closely enough related for me to feel I could to include it. Let's say that a partial order $\langle ...
8
votes
1answer
94 views

How to show that the event that a prisoner does no go free is not measurable

I was reading this webpage a few months ago about the following problem- A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone ...
6
votes
1answer
53 views

In $ZF+ \neg C$ can we always find a bijection from a given set $A$ to a transitive set?

Let us write $|A| = |B|$ iff there is a bijection $f \colon A \rightarrow B$. Working in $\operatorname{ZF + \neg C}$, can we prove that for any $A$ there is a transitive $B$ with $|A| = |B|$? This ...
10
votes
4answers
314 views

Countable choice and term extraction

The constructive Axiom of Countable Choice (ACC) is widely accepted due to its computational content. It states that: $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: ...
4
votes
1answer
55 views

Consistency of the Failure of Choice without Foundation

I'm working through the 2013 edition of Kunen's Set Theory, and I'm having some trouble with Exercise II.9.10, which shows the consistency of $ZF$ without Foundation and the negation of the axiom of ...
4
votes
1answer
108 views

Hidden usage of countable choice

Axiom of Countable Choice is a weaker form of the famous Axiom of Choice which is usually accepted even by constructivists. Following the famous book by Bishop & Bridges, Countable Choice in ...
1
vote
1answer
97 views

Proof of Closest Point Theorem in Hilbert Space

The theorem: Let $C$ be a non-empty closed convex subset of a Hilbert space $X$, and let $x \in X$. Then there exists a unique $y_0 \in C$ such that $||x-y_0|| \le ||x - y||$ all $y \in C$. In other ...
3
votes
1answer
61 views

Closure in a topological product: is AC needed?

I'm working on a proof of $\prod_{\alpha\in\Lambda}\overline{A_\alpha}=\overline{\prod_{\alpha\in\Lambda}A_\alpha}$ in the product topology. This has been asked before, i.e. Closure in a product of ...
2
votes
2answers
85 views

Proof that $(a,b)\subset\mathbb{R}$ is not countable. Does it use Axiom of Choice?

I used this proof to show $(a,b)$ is uncountable, but looking at it, I don't really see if it uses AC or not. Until recently I was thinking it does use AC (In the choice of the $a_n,b_n$), now I think ...
3
votes
1answer
40 views

Does every set have choice sequences as long as the original set?

Given a set $X$, we say that $X$ has choice sequences of length $|I|$, denoted $CS(|X|,|I|)$, if for any $f:I\to{\cal P}(X)\setminus\{\emptyset\}$ there is a function $g:I\to X$ such that $g(x)\in ...
3
votes
2answers
96 views

How can choice fail in ZF?

I don't see how the Axiom of Choice can fail in ZF. By transfinite induction you can demonstrate larger and larger ordinals, using union and pairing to show the successor and limit steps, so that for ...
0
votes
0answers
63 views

A question regarding a theorem of Erdos and Hajnal

Consider the following theorem of Erdos and Hajnal: Definition. For any set $x$, a function $f$ is called ${\omega} $-Jonsson iff $f$: $^{\omega}x$ $\rightarrow$ x and whenever $y$$\subseteq$$x$ and ...
0
votes
2answers
29 views

CC for finite sets and equivalent condition

If we assume for all sequence of sets od cardinality exactly 2, there exist choice function. Can we prove Countable choice for finite sets
1
vote
1answer
65 views

Countable choice and totally bounded metric spaces

Can we prove that the following statement is equivalent to the axiom of countable choice (CC)? If every sequence in a metric space $X$ has a Cauchy subsequence, then $X$ is totally bounded. ...
0
votes
0answers
16 views

CC and one of its equivalent condition [duplicate]

How we can prove: CC is equivalent to for all sequence(Xn) of non empty sets there exist (xn) which meets infinitely many (Xn) One side assuming CC is obvious. But what about converse. How we can ...
0
votes
1answer
38 views

Infinite set which is Dedekind finite and Weierstrass compactness

Weierstrass compactness states that each infinite set has a limit point. Why Infinite set which is Dedekind finite with discrete metric not Weierstrass compact.
17
votes
5answers
1k views

Is axiom of choice necessary for proving that every infinite set has a countably infinite subset?

Is it possible to prove the following fact without axiom of choice ? " Every infinite set has a countably infinite subset". Can it be proved that axiom of choice is necessary here ?
0
votes
0answers
53 views

every infinite bounded subset of X has an limit point in X and CC

Related to questions and definitions used in question: Nearest point property and WeistrassB copactness of each infinite bounded set Proof of one side of theorem: every bounded infinite bounded ...
1
vote
2answers
97 views

Does the “special continuum hypothesis” imply the axiom of choice?

In $\mathsf{ZF}$ set theory, does the "special continuum hypothesis" imply the axiom of choice, or is the axiom of choice independent of it? Here, by the "special continuum hypothesis" we mean the ...
4
votes
1answer
134 views

Can the generalized continuum hypothesis be disguised as a principle of logic?

A cool way to formulate the axiom of choice (AC) is: AC. For all sets $X$ and $Y$ and all predicates $P : X \times Y \rightarrow \rm\{True,False\}$, we have: $$(\forall x:X)(\exists y:Y)P(x,y) ...
1
vote
2answers
77 views

The generalized Axiom of Dependent Choice (DC) - is this a valid generalization?

After studying the axiom of dependent choice, I tried to think of a possible generalization of the axiom that would work in a similar way on infinite uncountable sets: by replacing the binary relation ...
5
votes
2answers
122 views

Is there a turing machine for which halting is equivalent to the Axiom of Choice or its negation?

As seen in "A Turing machine for which halting is outside ZFC", Gödel's incompletness theorem can that there a turing machines for which halting can not be decided. My question is, is there a turing ...
2
votes
1answer
129 views

Topological properties of $[0,\omega_1)$ without choice.

Reading this wikipedia article, I arrived at the fact that $\omega_1$ can exist without choice. Since the proof I know of the fact that $[0,\omega_1)$ is sequentially compact depends on the fact that ...
3
votes
1answer
83 views

Why does a proof of $\exists f: X\to Y$ injection $\iff \exists g: Y \to X$ surjection requires the axiom of choice?

Why does a proof of $\exists f: X\to Y$ injection $\iff \exists g: Y \to X$ surjection requires the axiom of choice? This question is answered here: There exists an injection from $X$ to $Y$ if and ...
2
votes
1answer
40 views

Can it be proved without the axiom of choice that every cardinal is comparable with every finite cardinal?

Can it be proven in ZF, without using the axiom of choice, that every finite set is a universal size comparator, meaning, is comparable with every set in terms of size? And what is the proof?