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

6
votes
1answer
62 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
356 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
71 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
126 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
175 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
91 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 f(x)...
3
votes
2answers
99 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
31 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
67 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. Note:...
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
60 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 ...
5
votes
1answer
161 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
83 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
137 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
136 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
107 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
60 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 ...
1
vote
2answers
72 views

Does construction of infinite product measure require axiom of choice?

I am learning about infinite (countable) product measure, which the exact statement of the theorem I write below. I was wondering if the theorem requires axiom of choice or not. I would appreciate any ...
0
votes
0answers
19 views

Indexed sum of cardinals [duplicate]

Let $\{ \kappa_i | i\in I \}$ be an indexed set of cardinals. We define the sum as: $\sum\limits_{i\in I}\kappa_i = \left\vert \bigcup\limits_{i\in I}X_i \right\vert$, where $\left\vert X_i \right\...
5
votes
1answer
72 views

Approximating nice functions with wild ones

Let $X$ and $Y$ be toplogical spaces, and call a function $f:X\to Y$ wild if the preimage $f^{-1}(\{y\})$ is dense in $X$ for every $y\in Y$ -- or, equivalently, if the image of every nonempty open ...
5
votes
2answers
143 views

Explicit construction of a nonmeasurable set, where only the proof of correctness uses choice?

By Solovay's theorem, assuming the existence of an inaccessible cardinal, the axiom of choice is necessary to prove the existence of nonmeasurable sets. In the past, I've thought that one consequence ...
4
votes
1answer
122 views

Does Lowenheim-Skolem theorem depend on axiom of choice?

The proofs of Lowenheim-Skolem I have seen all depended on the use of choice functions. Is there any proof not dependent on axiom of choice? Or is Lowenheim-Skolem a result of axiom of choice?
3
votes
1answer
133 views

Prob. 9, Sec. 4.3 in Kreyszig's Functional Analysis Book: Proof of the Hahn Banach Theorem without Zorn's Lemma [duplicate]

Here's Theorem 4.3-2 (i.e. the Hahn Banach theorem for normed spaces): Let $f$ be a bounded linear functional defined on a subspace $Z$ of a normed space $X$. Then there exists a bounbed linear ...
2
votes
1answer
57 views

Find a uniquely defined element in this $\aleph_1$-indexed Cartesian product

Denote by $A$ the set of all ordinals with cardinality exactly equal to ${\aleph}_0$, and for $\alpha\in A$ let $B_{\alpha}$ denote the set of all bijections between $\alpha$ and $\omega$ ; finally ...
11
votes
3answers
511 views

Does this proposition from complex analysis depend on AC?

I was reading III vol. of Princeton lectures on analysis. Proposition 1.4: "If $\Omega_{1}\supset\Omega_{2}\supset\ldots\supset\Omega_{n}\supset\ldots $ is a sequence of non-empty compact sets in $\...
1
vote
2answers
184 views

Where is the axiom of choice used in Rudin's proof of “the countable union of countable sets is countable”?

Baby Rudin proves that the countable union of countable sets is countable. From reading other proofs online, the axiom of choice has to be invoked; however, I'm not seeing immediately where that is ...
25
votes
2answers
948 views

W. Mückenheim claims a severe inconsistency of transfinite set theory; true? [closed]

The abstract for a paper on arxiv.org (http://arxiv.org/pdf/math/0408089v3.pdf) reads (with my emphasis): "Transfinite set theory including the axiom of choice supplies the following basic theorems: (...
9
votes
1answer
86 views

If a set $S$ has a choice function, does $\bigcup S$ have one too?

I have an exercise in a book that asserts that if a set $S$ has a choice function on it, then so does the union of all its elements $\bigcup S$ (without assuming the axiom of choice). I, however, have ...
2
votes
2answers
50 views

If $n < \aleph^*(m)$, then $n < 2^m$.

Without $AC$ Let $\aleph^*(m)$ be the least aleph that $\not\leq^* m$. I need a help or hint that if $n < \aleph^*(m)$, then $n < 2^m$. $a \leq^* b$ means we can define a surjective map from $...
3
votes
3answers
125 views

Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice)

I am interested in proving the titular claim: Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice) My approach: Let $R$ be a well-founded relation. We ...
9
votes
2answers
406 views

Does the definition of the fundamental group implicitly assume the Axiom of Choice?

Okay, I'm a little foggy around the axiom of choice, so help me out here. The standard way the fundamental group of a connected space $X$ is defined is as follows. You consider the set of all loops ...
8
votes
2answers
191 views

Good resources for studying independence proofs

I've finished most of Enderton's set theory. And I intend to spend some time studying independence proofs. I'm more interested in independence of axiom of choice not CH. From I know so far, there ...
2
votes
1answer
103 views

A Banach space of (Hamel) dimension $\kappa$ exists if and only if $\kappa^{\aleph_0}=\kappa$

A Banach space of (Hamel) dimension $\kappa$ exists if and only if $\kappa^{\aleph_0}=\kappa$. How will we prove the converse implication. One sided implication for Hilbert Space is proved in ...
7
votes
1answer
175 views

What is the significance of having Prime Ideal Theorem in models for failure of Axiom of Choice?

Prime Ideal Theorem says: PIT: Every ideal on a Boolean algebra can be extended to a prime ideal. It follows from Axiom of Choice but is weaker than it. In many cases I saw that people check ...
2
votes
1answer
71 views

Basis for $\mathbb{R}^{\infty}$ [duplicate]

It follows from Zorn's Lemma that every vector space $V$ has a basis (this means, a subset $B$ of $V$ that generate any $v \in V$ by means a finite linear combination, and such that $B$ is LI) . But, ...
2
votes
1answer
27 views

The least $\aleph$ that has no surjective map from $m$ to it.

Without $AC$. Let $\aleph^*(m)$ be the least aleph that $\not\leq^* m$. How to show that $\aleph^*(m)$ exists and $\aleph^*(m)= \{\alpha\in ON\mid\ \alpha\leq^*m\}$. $ON$ is the class of all ...
1
vote
1answer
72 views

dual Dedekind-infinity may not imply Dedekind-infinite without AC

It is written in wikipedia: https://en.wikipedia.org/wiki/Dedekind-infinite_set It is not provable (in ZF without the AC) that dual Dedekind-infinity implies that A is Dedekind-infinite. (For ...
2
votes
2answers
76 views

Does the principle of schematic dependent choice follow from ZFCU?

Let ZFCU be ZFC modified in the usual way to allow for urelements but without an axiom stating that there is a set of all urelements. Let the principle of Schematic Dependent Choice (SDC) be: $\...
3
votes
1answer
100 views

Are there weak versions of the axiom of choice equivalent to weak versions of Zorn's lemma and similar principles?

I recalled reading about other weaker forms of $AC$, for example countable choice, where we could make choices from a sequence $(S_{k})_{k \in \mathbb{N}}$ of non-empty sets. I also recalled mention ...
4
votes
1answer
67 views

Does there exist a model of $ZF¬C$ in which there is a function on $\mathbb R$ which is sequentially continuous at a point where it is not continuous? [duplicate]

Does there exist a model of $ZF¬C$ in which there is a function $f:\mathbb R \to \mathbb R$ such that $f$ is sequentially continuous at some $a \in \mathbb R$ but not $\epsilon-\delta$ continuous , i....
2
votes
1answer
109 views

“Sequential continuity is equivalent to $\epsilon$-$\delta $ continuity ” implies Axiom of countable choice for collection of subsets of $\mathbb R$?

"A function $f: \mathbb R \to \mathbb R$ is continuous at $x \in \mathbb R$ , if and only if it is sequentially continuous " , does this statement imply "the Axiom of Choice for countable collections ...
3
votes
1answer
112 views

Proof that every field $F$ has an algebraic closure $\bar F$

I am reading the book A First Course in Abstract Algebra written by Fraleigh and I do not really understand the proof of theorem 31.22, that every field $F$ has and algebraic closure $\bar F$. I ...