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

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 ...
4
votes
1answer
82 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
120 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
87 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 ...
2
votes
2answers
42 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 ...
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
77 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 ...
8
votes
1answer
120 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
90 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
67 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. ...
-1
votes
1answer
125 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
414 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
544 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
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
354 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
90 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
29 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
108 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
75 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
67 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
79 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
199 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
140 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
60 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
57 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
114 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
60 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
352 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
121 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
156 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
74 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
90 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 ...