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

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
179 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
202 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
123 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
202 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
159 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
278 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}$ ...
12
votes
2answers
249 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
101 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
273 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
110 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
197 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
301 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
105 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
188 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
329 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
148 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
530 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
125 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
138 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
191 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
149 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 ...
10
votes
1answer
234 views

Does a nonlinear additive function on R imply a Hamel basis of R?

A function is additive if $f(x+y) = f(x) + f(y)$. Intuitively, it might seem that an additive function from R to R must be linear, specifically of the form $f(x) = kx$. But assuming the axiom of ...
5
votes
2answers
221 views

Intuition behind the Axiom of Choice

Why is it different to make one choice or many choices than to make infinite choices from a theoretical point of view in which indeed you are not going to do any? How could that be different from ...
4
votes
3answers
243 views

Why the need of Axiom of Countable Choice?

Two theorems: $(1)$ Countable Union of Countable Sets is Countable $(2)$ Cartesian Product of Countable Sets is Countable Linked are the formal proofs on Proofwiki. I do not understand why they ...
2
votes
3answers
128 views

$\mathbb{R^+}$ is the disjoint union of two nonempty sets, each closed under addition.

I saw Using Zorn's lemma show that $\mathbb R^+$ is the disjoint union of two sets closed under addition. and have a question related to the answer (I'm not sure if this is the right place to post ...
4
votes
2answers
102 views

Are there versions of the axiom of choice that restrict the size of the factors?

One formulation of the axiom of choice is that an arbitrary product of nonempty sets must be nonempty. The axiom of countable choice AC$_\omega$ is known to be strictly weaker than AC, but still ...
10
votes
1answer
204 views

Stone's Representation Theorem and The Compactness Theorem

If you're working on $\mathsf {ZF}$ and you assume the compactness theorem for propositional logic, then you have the prime ideal theorem, and thus you can show that the dual of the category of ...
4
votes
2answers
67 views

Does the existence of this quotient set depend on the Axiom of Choice?

We know the familiar equivalent relation on $\mathbb{R}$, which is $$ x\sim y\Leftrightarrow x-y\in\mathbb{Q} $$ After quoting this relation, we have the quotient set $$ \mathbb{R}/_\sim = \{x + ...
3
votes
1answer
136 views

well-ordering principle

I'm confused by the well-ordering principle . The proof is clear but I don't have any idea why is it true . It says that every non-empty set can be well-ordered but $C^{1}$ is a non-empty set but ...
6
votes
3answers
126 views

Proof of $CFE \implies BPI$

(CFE): Every filter of closed sets can be extended to a maximal one. (BPI): Every Boolean algebra contains a prime ideal. I am reading Herrlich's and Stepran's paper "Maximal filters, continuity and ...