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

167
votes
1answer
5k views

Does the open mapping theorem imply the Baire category theorem?

A nice observation by C.E. Blair1, 2, 3 shows that the Baire category theorem for complete metric spaces is equivalent to the axiom of (countable) dependent choice. On the other hand, the three ...
3
votes
1answer
42 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
79 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
30 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
90 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 ...
9
votes
6answers
729 views

Countable axiom of choice: why you can't prove it from just ZF

This is a follow-up question to the discussion about the finite axiom of choice here. Suppose we have a countable collection of non-empty sets $\{A_1, A_2, A_3,\cdots\}$ Reasoning as indicated in ...
0
votes
0answers
57 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
26 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
53 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
14 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 ...
2
votes
2answers
52 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 ...
0
votes
1answer
30 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.
14
votes
5answers
948 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 ?
13
votes
2answers
427 views

What's the difference between saying that there is no cardinal between $\aleph_0$ and $\aleph_1$ as opposed to saying that…

... $\aleph_1$ is the immediate successor of $\aleph_0$? I was reading the wiki article on $\aleph_1$ where a distinction is made between the two. If there's isn't a cardinal between $\aleph_1$ and ...
0
votes
0answers
18 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
76 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
128 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) ...
3
votes
4answers
1k views

(ZF) Prove 'the set of all subsequential limits of a sequence in a metric space is closed.

Let $X$ be a metric space. Let $\{p_n\}$ be a sequence in $X$. Let $E$ be a set of all subsequential limits of $\{p_n\}$. How do i prove that $E$ is closed in ZF? Is there a well-ordering of ...
5
votes
2answers
97 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
116 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
64 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
30 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?
4
votes
0answers
45 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 ...
8
votes
2answers
122 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 ...
1
vote
2answers
61 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
15 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 ...
5
votes
1answer
64 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
120 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 ...
12
votes
1answer
570 views

Strength of the statement “$\mathbb R$ has a Hamel basis over $\mathbb Q$”

I would like to know if there are "interesting" equivalences to the statement "$\mathbb R$ has a Hamel basis over $\mathbb Q$". I am not interested in more general statements, like "every vector space ...
18
votes
3answers
919 views

Is there a constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$?

Assuming the Axiom of Choice, every vector space has a basis, though it can be troublesome to show one explicitly. Is there any constructive way to exhibit a basis for $\mathbb{R}^\mathbb{N}$, the ...
2
votes
1answer
49 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 ...
4
votes
1answer
71 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?
12
votes
3answers
497 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
123 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 ...
24
votes
2answers
858 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
62 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
44 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
71 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
368 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 ...
7
votes
1answer
160 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
52 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 ...
2
votes
1answer
58 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
23 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 ...
0
votes
0answers
18 views

onto map implies existence of one one map and AC [duplicate]

Let us assume the fact: $f: A \to B$ onto function implies there exist $1-1$ function from $B$ to $A$. Would it imply AC? I know every surjective function has right inverse this fact is ...
1
vote
1answer
58 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 ...
1
vote
2answers
59 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
72 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
55 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 , ...
6
votes
0answers
96 views

(Non-Hopfian) groups that only have quotients that are themselves or the trivial group.

A group is non-Hopfian provided it is isomorphic to a proper quotient. The classic, finitely presented, example of such a group is the Baumslag-Solitar group $$BS(2,3)= \langle x,t \mid t^{-1}x^2 t ...
3
votes
1answer
65 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 ...