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

13
votes
1answer
258 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
350 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
87 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
25 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
65 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
106 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
72 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
62 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
38 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
74 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
196 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
52 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
139 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
67 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
48 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
74 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
34 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
54 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
43 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
54 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
113 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
58 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
340 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
68 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
119 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
143 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
73 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
89 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
98 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
17 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
39 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
59 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
99 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
136 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
79 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
130 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
133 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
93 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
46 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?
5
votes
0answers
59 views

Over ZF does “every non-seperable Hilbert space has an orthonormal basis” imply “there exists a non-Lebesgue measurable set”?

I know from this question that it's an open problem whether or not the existence of a dense orthonomral basis for every real or complex Hilbert space $(\text{B}_\text{orth})$ implies the axiom of ...