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

2
votes
1answer
105 views

Cluster point of a sequence $\{x_n\}$ is the limit of some subsequence - Axiom of Choice? [duplicate]

In a metric space, a cluster point of a sequence $\{x_n\}$ is the limit of some subsequence. The only proof that I know works like this: Construct a sequence $\delta _k \to 0$. For each $\delta _k$ ...
9
votes
1answer
176 views

Proof of Zorn's Lemma using the Axiom of Choice. Why is $\mathscr U$ a tower?

I am reading a proof of Zorn's Lemma using the Axiom of Choice in Halmos' classical text, and I fail to see how to prove$\mathscr U$ satisfies the third condition of the definition of a tower. I will ...
4
votes
3answers
507 views

Why is the well ordering principle counter-intuitive?

I read here that while 'The Axiom of Choice agrees with the intuition of most mathematicians; the Well Ordering Principle is contrary to the intuition of most mathematicians'. I don't understand why ...
8
votes
3answers
357 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is ...
0
votes
1answer
118 views

Need help in Proofwiki of Axiom of choice implies Zorn's Lemma

I don't understand some point in proofwiki. (Here is link to the current revision of the ProofWiki article.) Firstly, it introduces $\mathbb{X}$ be the set of all chains in $(X,\preceq)$ while ...
1
vote
1answer
82 views

Can Zorn's lemma be applied to a class that is not a set?

I know that Zorn's lemma or its equivalent axiom of choice and so on can be applied to a set - but I am not sure if it can be applied to a class. I think I've seen an usage of axiom of choice to a ...
1
vote
1answer
105 views

Infinite Cartesian Product minus AC example

I've been looking for an example of an empty Cartesian product whose factors are non-empty. From what I've gathered so far, this statement is equivalent to the negation of AC, ie. AC fails. So ...
6
votes
0answers
218 views

A few standard results (on metrizability and relative separation strength) without choice?

I've been going back over some results from Munkres's Topology, and I'm curious about some things.... I know that Choice principles have some connection to the separation axioms (in ZF, at ...
4
votes
2answers
217 views

Cardinality of an ultrafilter

If $\mathscr F$ is an ultrafilter on an infinite set $M$, then it can be shown that $|\mathscr F|=2^{|M|}$. We know that for each subset $A\subseteq M$ we have $A\in\mathscr F$ or $M\setminus A \in ...
8
votes
1answer
157 views

If $B\not\prec A$, does $A\preceq {\cal P}(B)$ or $A\preceq {\cal P}{\cal P}(B)$, etc in ${\sf ZF}$?

I've heard it said that theorems based on choice are also available in ZF "a few powersets away", and I think this is one of them, but I'm not sure how to prove it. (I'm also interested to hear of ...
2
votes
1answer
180 views

How do we know we need the axiom of choice for some theorem?

I have been working through Munkres Topology book and in an exercise he says that there was a theorem he proved in a previous section that relied on the axiom of choice and the task is to find it. I ...
6
votes
1answer
203 views

Do proper dense subgroups of the real numbers have uncountable index

Just what it says on the tin. Let $G$ be a dense subgroup of $\mathbb{R}$; assume that $G \neq \mathbb{R}$. I know that the index of $G$ in $\mathbb{R}$ has to be infinite (since any subgroup of ...
1
vote
1answer
58 views

Cardinality and surjective functions

Let $A$ denote a set and $P(A)$ be the power set. By definition for cardinalities $|A|\le|B|$ iff there exists an injection $A \hookrightarrow B$. Note that there is an obvious surjection $P(A) \to ...
8
votes
1answer
172 views

Nonatomic vs. Continuous Measures

Here is an old measure theory exercise I remember solving, but I'm now a bit fuzzy on the details. Let $(X,\Sigma,\mu)$ be a finite measure space. Call $\mu$ nonatomic if for any $A\in\Sigma$ ...
5
votes
1answer
172 views

In ZF, does there exist an ordinal of provably uncountable cofinality?

Question is in the title. In ZFC, one can prove that $\aleph_{\alpha+1}$ is regular, so there is a large source of cardinals with uncountable cofinality, but in ZF, it is consistent that ${\rm ...
3
votes
1answer
124 views

Is it possible to prove $|V_\kappa|=\kappa$ for strongly inaccessible $\kappa$ without AC?

First, let me note that my definition of "strongly inaccessible" is that a nonzero ordinal $\kappa$ is strongly inaccessible if ${\rm cf}(\kappa)=\kappa$ and $\forall\alpha<\kappa, {\cal ...
5
votes
2answers
204 views

Astonishing and innocent results with the axiom of choice

The product of nonempty sets is nonempty. I am fascinated that such a simple and seemingly intuitive statement can lead to rather astonishing results such as the Banach-Tarski paradox or the solution ...
4
votes
5answers
160 views

Does 'let x be a member of S…' require axiom of choice? [duplicate]

A lot of proofs start like this 'Let x be some member of the set S, then...' (If S are the natural numbers, this is especially common) Do all of those proofs ...
7
votes
3answers
279 views

Do maximal proper subfields of the real numbers exist?

To clarify the problem, consider the field ${\Bbb R}$ as a field extension of ${\Bbb Q}$ using some sort of Hamel basis. Does there exist a field $F\subsetneq{\Bbb R}$ such that $F(\sqrt{2})={\Bbb R}$ ...
13
votes
2answers
253 views

Is every vector space basis for $\mathbb{R}$ over the field $\mathbb{Q}$ a nonmeasurable set?

The existence of subsets of the real line which are not Lebesgue measurable can be argued using the Axiom of Choice. For example, define an equivalence relation on $[0, 1]$ by $a \thicksim b$ if and ...
4
votes
2answers
133 views

Axiom of Choice in Logic

The completeness and compactness theorems of first-order logic are well known to be equivalent to the ultrafilter lemma. Are there any theorems of logic that are similarly equivalent to the full axiom ...
14
votes
2answers
152 views

How far is it true that statements dependent on Axiom of Choice are not constructive.

Axiom of Choice is often used in mathematics to construct various objects, such as basis of $\mathbb{R}$ as a vector space over $\mathbb{Q}$, unmeasurable subset of $\mathbb{R}$, or a non-principal ...
5
votes
2answers
102 views

Reference request, self study

I'm looking for references (books/lecture notes) for : Cardinality without choice, Scott's trick; Cardinal arithmetic without choice. Any suggestions ? Thanks in advance.
4
votes
3answers
221 views

Countable ordinals are embeddable in the rationals $\Bbb Q$ — proofs and their use of AC

Yesterday, Asaf Karagila's answer to my question sparked an extensive discussion on ways of proving that all countable ordinals are embeddable in $\Bbb Q$, and whether particular solutions to this use ...
6
votes
2answers
274 views

Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the ...
4
votes
1answer
111 views

The “set” of equivalence classes of things.

This question might be silly. I was wondering wether some form of choice is needed to be on firm footing when talking about the set of equivalence classes of certain things. For instance, when one ...
2
votes
2answers
199 views

Zorn's lemma implies the well-ordering principle

I am little confused about the proof given here http://euclid.colorado.edu/~monkd/m6730/gradsets05.pdf On the second page, when defining $P$, the author says that $B\subset A$ and $(B,<)$ is a ...
15
votes
1answer
302 views

How to formulate continuum hypothesis without the axiom of choice?

Please correct me if I'm wrong but here is what I understand from the theory of cardinal numbers : 1) The definition of $\aleph_1$ makes sense even without choice as $\aleph_1$ is an ordinal number ...
3
votes
2answers
62 views

Two questions about implications between $\mathsf{DC}, \mathsf{BPI}$ and $\mathsf{AC}_\omega$

Does the implication $\mathsf{DC} \implies \mathsf{BPI}$ hold? And does the implication $\mathsf{BPI} \implies \mathsf{AC}_\omega$ hold? I checked with Howard/Rubin's "Consequences of the Axiom of ...
0
votes
1answer
106 views

Axiom of choice and function with empty codomain

I'm having a little problem here, namely if the axiom of choice (Wikipedia) is $$\forall X \left[ \emptyset \notin X \implies \exists f: X \to \bigcup X \quad \forall A \in X \, ( f(A) \in A ) ...
6
votes
3answers
197 views

Questions on Fraenkel models

Halbeisen on page 172 contains a section entitled "The Second Fraenkel Model". The original paper by Fraenkel containing this model can be found here. I have several questions regarding this model and ...
7
votes
1answer
144 views

Nielsen-Schreier and the Axiom of Choice

The Nielse-Schreier (NS) Theorem says that every subgroup of a free group is free. The proof uses the Axiom of Choice, and Läuchli showed in 1962 that the negation of NS is consistent with ZFA (ZF ...
8
votes
2answers
333 views

Is the compactness theorem (from mathematical logic) equivalent to the Axiom of Choice?

Or more importantly, is it independent of the axiom of choice. The compactness theorem states the given a set of sentences $T$ in a first order Language $L, T$ has a model iff every finite subset of ...
11
votes
2answers
177 views

The relationship of ${\frak m+m=m}$ to AC

Two simple questions: (Of course ${\frak m}$ denotes a cardinal in the weak sense in the claims below.) Can we prove in ZF that $\aleph_0\le{\frak m\Rightarrow m+m=m}$? If not, what is the ...
3
votes
1answer
123 views

(Non) equivalence of regular cardinal definitions

The usual definition of a regular cardinal is "$\kappa$ is regular if $cf(\kappa) = \kappa$", which, assuming the axiom of choice, is equivalent to this definition: "$\kappa$ is regular iff it cannot ...
6
votes
2answers
133 views

Zorn's lemma and maximal linearly ordered subsets

Let $T$ be a partially ordered set. We say $T$ is a tree if $\forall t\in T$ $\{r\in T\mid r < t\}$ is linearly ordered (such orders can be considered on connected graphs without cycles, i.e. on ...
6
votes
2answers
129 views

Axiom of Choice-esque argument to show that a proof of a statement exists without actually giving a proof

What if the set of all well-formed statements in ZFC formed a kind of pseudo-category where a morphism f between objects A, B represented a formal proof that A implied B? What if that category could ...
2
votes
1answer
102 views

Jech: Set Theory exercise 3.13, how do I avoid Choice?

In an effort to finally learn set theory rigourously, I've decided to start plowing through Jech's Set theory, making sure to do each of the exercises. Here is Jech's problem 3.13 (pg. 34 in the ...
2
votes
1answer
149 views

Can we write every uncountable set $U$ as $V∪W$, where $V$ and $W$ are disjoint uncountable subsets of $U$? [duplicate]

Is it true that for every uncountable set $U$, we can write $U=V∪W$, where $V$ and $W$ are disjoint uncountable subsets of $U$ ?
5
votes
0answers
121 views

Is dependent choice necessary to prove every perfect compact Hausdorff space is uncountable?

The answer to Cardinality of a locally compact space without isolated point shows that AC is required to show that if $X$ is a compact Hausdorff space with no isolated points then $|X| \ge ...
10
votes
6answers
534 views

Can every infinite set be divided into pairwise disjoint subsets of size $n\in\mathbb{N}$?

Let $S$ be an infinite set and $n$ be a natural number. Does there exist partition of $S$ in which each subset has size $n$? This is pretty easy to do for countable sets. Is it true for ...
3
votes
1answer
126 views

Dissecting a proof of the $\Delta$-system lemma (part II)

This is part II of this question I asked yesterday. In the link you can find a proof of the $\Delta$-system lemma. In case 1 it uses the axiom of choice (correct me if I'm wrong). Now one can also ...
2
votes
2answers
131 views

Isomorphic Free Groups and the Axiom of Choice

When I read about free group, the proof which concerns about two free groups $F(X)$ and $F(Y)$ are isomorphic only if $\operatorname{card}(X) = \operatorname{card}(Y)$ has a sentence going as follows: ...
6
votes
1answer
140 views

Understanding a proof of Diaconescu's theorem

I am trying to walk through the proof of Diaconescu's theorem that the axiom of choice implies the law of excluded middle at http://plato.stanford.edu/entries/intuitionism/#ChoAxi. To paraphrase: ...
4
votes
1answer
79 views

Dependent choice and Zorn's Lemma

How much of Zorn's lemma can be saved if we assume only ZF+DC without full choice? More precisely: assume we have a partially ordered (inductive) set which is of size continuum. Then can we apply ...
6
votes
2answers
192 views

The Axiom of Choice and definability

I've seen a lot of relations between the notion of the existence of a definable set with a given property and the necessity of AC is proving that there is a set with the property. For example: Under ...
2
votes
1answer
151 views

Tychonoff Theorem and the axiom of choice

How to show that The Tychonoff Theorem and the axiom of choice are equivalent? Here I want to collect ways to prove it. Thanks for your help.
47
votes
3answers
15k views

Predicting Real Numbers

Here is an astounding riddle that at first seems impossible to solve. I'm certain the axiom of choice is required in any solution, and I have an outline of one possible solution, but would like to ...
1
vote
1answer
59 views

Cauchy functional equation with non choice

Assume ZF+ not AC. Then how many solutions are there for Cauchy functional equation? Thank you
2
votes
2answers
65 views

Mapping on cardinal without Axiom of Choice

Define $|A|\le|B|$ iff there exists injective mapping $A \to B$. If Axiom of Choice is assumed then this is equivalent as $|A|\le|B|$ iff there exists surjective mapping $B \to A$. But: If Axiom of ...