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
79 views

Under what choice assumptions is there a monoid structure on every set?

The question arose when discussing possible cardinalities of hom-sets of whether it's any weaker than the axiom of choice that there exists a monoid of every cardinality. It's well known, or at least ...
6
votes
0answers
110 views

AC iff $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$ [duplicate]

I'm trying to do the following exercise: Exercise. Assume ZF. Then AC is equivalent to the statement that $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$. I'm struggling with the ...
3
votes
2answers
199 views

Axiom of Choice, Continuity and Intermediate Value Theorem

I am trying to understand a proof I read in Herrlich's book Axiom of Choice. For those who know the book, it is theorem 4.54 on page 74. The part I am interested in reads: (9) A function $f:X ...
6
votes
2answers
110 views

Axiom of dependent choice and $\aleph_1$

Assume we have to make a construction on countable sets, which requires choice. If we need to repeat the same construction up to cardinal $\aleph_1$ (for example to construct a chain of elementary ...
4
votes
3answers
213 views

We cannot write this function

I'm a new user so if my question is inappropriate, please comment (or edit maybe). If we accept axiom of choice, we can find a choice function for $\mathbb{R} / \mathbb{Q} $ , this is obvious. But we ...
2
votes
1answer
76 views

Back and forth and the axiom of choice

Is the axiom of choice a necessary condition for the application of "back and forth construction" in model theory?
2
votes
1answer
105 views

(Revisited$_2$) Injectivity Relies on The Existence of an Onto Function Mapping Back to Its Preimage

QUEST: For any sets $X$ and $Y$, there exists an injective function $f:X\rightarrow Y$ if and only if there exists a surjective function $g:Y\rightarrow X$. QUESTION$_1$: How do you people ...
-2
votes
1answer
91 views

Axiom of Choice: An Invocation Necessary for A Proof on Surjectivity [closed]

Prove that if $f\colon X\rightarrow Y$ is surjective, then there must exist a function $g\colon Y\rightarrow X$ such that $f\circ g=1_Y$, where $1_Y$ is the identity map on $Y$.
1
vote
1answer
107 views

equivalence between axiom of choice and Zorn's lemma in a particular case.

Define $A(x)$ and $Z(x)$ as follows. $A(x)\Leftrightarrow $for every indexed family $(S_i)_{i\in I}$ of nonempty sets s.t. $\# I =x$, there exists an indexed family $(s_i)_{i\in I}$ s.t. $s_i \in ...
1
vote
2answers
100 views

Is there a deductive system for second-order logic that is complete with respect to Henkin semantics?

I have heard that second-order logic with Henkin semantics is a lot like first-order logic. Does this mean it has a complete deductive system? If so, what's an example of such a deductive system, and ...
1
vote
1answer
115 views

Extending our language with a new function symbol

Given an arbitray first-order theory (not necessarily a set theory) and definable predicates $P(*)$ and $Q(*,*)$ in the language of that theory, if we adjoin a new function symbol $f$ together with ...
-1
votes
2answers
188 views

The intersection of an infinite descending chain of non-empty sets [closed]

I am trying to prove something by contradiction and I am stuck as described below: From the (false) assumption, I have shown that for any $i \in \mathbf{N}$, $A_i \neq \emptyset$ and that $A_1 ...
0
votes
1answer
100 views

proof of equivalence of continuity and continuity in terms of limits of sequences

I am currently working on the axiom of choice and was looking for easy applications. A common example is the proof of the equivalence of continuity with continuity in terms of limits of sequences. ...
2
votes
1answer
108 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
189 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
522 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
363 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
121 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
85 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
107 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 ...
7
votes
0answers
226 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
219 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
158 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
183 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
213 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
175 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
174 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
126 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
207 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
164 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
287 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
257 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
134 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
155 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
105 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
226 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
275 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
117 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
208 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
305 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
109 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
200 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
145 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
341 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
125 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
136 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
130 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 ...