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

Uncountable dense sets of reals without the axiom of choice

In the absence of AC, can there be an uncountable dense set $S\subset\mathbb R$ such that $S\cap(-\infty,a)$ is countable for each real number $a$? (Of course, since $S$ is a countable union of ...
0
votes
2answers
59 views

Choice function without AC in special case [duplicate]

I read the Jech, Set theory, and saw following proposition. (☆) If S is a finite family of nonempty sets, existence of choice function of S can be proved without axiom of choice. I tried to prove ...
2
votes
1answer
42 views

If every partitioning of $X$ has a choice function, is $X$ necessarily well-orderable?

Working over the ZF axioms, it's clear that if $X$ is a well-orderable set, then every partitioning of $X$ has a choice function, by choosing the minimum of each cell. Question. Does the converse ...
0
votes
1answer
31 views

Equivalence of Taylor series and its corresponding function and Axiom for infinite summation

Given a function $f(x)$ with a taylor series expansion, is it valid to say that $$f(x)=\sum_{n=0}^{\infty}\frac{1}{n!}f^{(n)}(a)(x-a)^n$$ for all values of x irrespective of whether the taylor series ...
2
votes
0answers
54 views

Is it really necessary to choose a basis to prove that every element of a comodule is contained in a finite-dimensional subcomodule?

Let $C$ be a coalgebra over a field and $M$ be a $C$-comodule. Then it's well-known that every element of $M$ is contained in a finite-dimensional subcomodule $M' \subset M$. This is for example an ...
0
votes
0answers
23 views

Impossibility of constructing a continuum-size linearly independent set in $\Bbb R$ [duplicate]

This is a response to the following exchange at Is there a quick proof as to why the vector space of $\mathbb{R}$ over $\mathbb{Q}$ is infinite-dimensional? [Bill constructs a $\aleph_0$ ...
2
votes
0answers
40 views

Existence of extension of linear map and existence of subspace complement

Great answer by Asaf Karagila to my question leads me to further questions. Let say we deal with vector spaces over $\mathbb{R}.$ Here are three sentences: For every $V$ and its subspace $E\subset ...
1
vote
1answer
52 views

Existence of vector space complement and axiom of choice

Let say we live in the category of vector spaces over $\mathbb{R}$ or $\mathbb{C}.$ Here are three sentences: Axiom of choice Every vector space has a base. For every vector space $V$ and its ...
1
vote
1answer
26 views

Does this proof of $x\in E'\rightarrow \exists \{x_n\}\subseteq E : x_n\to x$ use the axiom of choice?

Let $(X,d)$ be a metric space. Let $E$ be a subset of $X$. If $x$ is a limit point of $E$, then there exists a sequence $x_n\in E$, $n= 1,2,\dots$ such that $x_n\to x$. Proof. Pick $...
1
vote
1answer
52 views

A set that satisfies the hypothesis of Zorn's Lemma

A set $x$ satisfies the hypothesis of Zorn's Lemma. Let $k \in x$. $\textbf{Prove:}$ There is a $z \in x$ such that $z$ is $S$-maximal in $x$ and $z=k \vee kSz $ $\textbf{Attempt:}$ ...
4
votes
1answer
70 views

When can “$j: V \rightarrow M$ is an elementary embedding” be defined in ZF?

This regards elementary embeddings of inner models of set theory. It seems that it is in general "stated" via an axiom schema each member of which states that the class function is elementary with ...
0
votes
1answer
42 views

Bolzano-Weierstrass Theorem Proof Abbott (Ax. of Choice)

In Abbott's Proof of the Bolzano-Weierstrass Theorem, does Abbott use any form of the Axiom of Choice ? I think he is since he chooses an $a_{n_k} \in I_k$ where there are multiple such $a_{n_k}$.
1
vote
1answer
49 views

Axiom of choice is equivalent to every relation includes a function with the same domain

The axiom of choice asserts that for any set $X$ there exists a function $f : (2^X − \{\emptyset\}) \rightarrow X$ such that for any nonempty $A \subseteq X$, $f(A) \in A$. Show that this is ...
11
votes
2answers
284 views

Can a basis for $\mathbb{R}$ be Borel?

Work in ZF (so no choice). Then it is consistent that there is no (Hamel) basis for $\mathbb{R}$ as a $\mathbb{Q}$-vector space. My question is about models where $\mathbb{R}$ does have a basis, but ...
1
vote
2answers
55 views

Do the relative consistency results involving the axiom of choice use completeness of FOL?

The proof of the Completeness Theorem for first order logic uses the axiom choice and is a central result in model theory. Chang and Keisler claim that model theory has important applications to set ...
13
votes
0answers
333 views

Spanning the reals with a small set - choicelessly

Working in ZF (so, no choice): is it possible that there is a set of reals $X$ such that $\vert X\vert<\mathbb{R}$, but $X$ generates $\mathbb{R}$ as a subgroup under addition? This seems ...
0
votes
1answer
38 views

Axiom of choice for subsets

I'm trying to solve following problem. Let $A_{i,j}$ be subsets of a set $X$ for $i,j\in \mathbb{N}$. Show that $$\bigcap_{i=0}^\infty \bigcup_{j=0}^\infty A{i,j}=\bigcup_{(a_{i})}\bigcap_{i=0}^\infty ...
1
vote
2answers
56 views

Set Theory - Prove that there is a function $f:\omega\to X$ such that $f(n)<f(n+)$ when $X$ has no maximal element.

Suppose that $X$ is non-empty strictly ordered set, and that $X$ has no maximal element in a sense that for every $x\in X$ there exist $y\in X$ such that $x<y$. By using AC, show that there exists ...
1
vote
1answer
22 views

Does this minimum exist? Modified Ascoli theorem without countable choice

I am trying to work through a proof on a modification of the ascoli theorem that is supposed to hold in ZF (even without assuming countable choice). My problem is within the part (1) $\Rightarrow$ (...
2
votes
2answers
91 views

Hausdorff Maximal Principle and Axiom of Choice

I need to show that Hausdorff Maximal Principle is equivalent to the Axiom of Choice. Suggested is to use Tukeys Lemma. So far I have that Hausdorff Maximal Principle states that whenever < is a ...
3
votes
1answer
58 views

If $X$ is a metric, then $X$ is compact if and only if $X$ is sequentially compact - axiom of choice usage

I'm going through a proof for the theorem: If $X$ is a metric, then X is compact if and only if X is sequentially compact. I have already posted this here. However this time I'm looking at the ...
2
votes
1answer
68 views

Partitioning an infinite set into two equinumerous subsets

Let $X$ be an infinite set. Then there exists a partition $\lbrace A, B \rbrace$ of $X$ such that $A, B, X$ are equinumerous. Can you prove it in $\mathrm{ZFC}$? Can you prove it in $\mathrm{ZF}$?
1
vote
1answer
43 views

Proof that well-ordering implies choice

Is the following argument correct to show that if every set $S$ can be well-ordered, then for any disjoint indexed family of non-empty sets $(X_{\alpha})_{\alpha \in A}$ there exists a map $f: \{ X_{\...
2
votes
0answers
67 views

A doubt in the proof of “AC implies law of excluded middle”

i dont understand why axiom of choice is needed for the proof, since X is finite and (if i haven't misunderstand anything) we don't need axiom of choice to define a choice function for a finite set. ...
1
vote
0answers
22 views

Is the axiom of countable choice needed for the proof of this special case of equivalence of limit definitions? [duplicate]

In this link, a proof of the equivalence between the $\delta-\epsilon$ definition and the one with the convergent sequences is given. I'm interested in the proof of this theorem simply for the metric ...
0
votes
1answer
48 views

How to avoid the Axiom of Choice in proving Higman's Lemma?

In this paper (pp 2-3) Friedman proves a version of Higman's Lemma for infinite sequences of finite words on a finite alphabet. Such a sequence $S$ is called "bad" if no element of $S$ occurs as a ...
11
votes
1answer
110 views

How does equality $\mathfrak{m}^\mathfrak{m} = 2^\mathfrak{m}$ in $\sf{ZF}$ relate to the axiom of choice?

Usually, the equality $\mathfrak{m}^\mathfrak{m} = 2^\mathfrak{m}$ for infinite cardinal $\mathfrak{m}$ is proved like that: $$ 2^\mathfrak{m} \leqslant \mathfrak{m}^\mathfrak{m} \leqslant (2^\...
0
votes
0answers
28 views

Surjective iff right invertible. Bijective iff invertible [duplicate]

Let $f:X \to Y$ be a mapping. Its known that choice implies $f$ is surjective iff $f$ is right invertible. Are the following statements true? Surjective iff right invertible is equivalent to choice. ...
5
votes
2answers
521 views

Does the axiom of choice have any use for finite sets?

It is well known that certain properties of infinite sets can only be shown using (some form of) the axiom of choice. I'm reading some introductory lectures about ZFC and I was wondering if there are ...
1
vote
3answers
73 views

Axiom of choice - Equivalence relation - Representatives

Let $ X $ be a set and $ \sim $ an equivalence relation on $ X $. In many proofs, a set of representatives of equivalence classes of $ X $ is used (e.g. coset or orbit representatives in groups, ...
1
vote
0answers
26 views

Every set of pairwise disjoint sets has a choice function implies AC

Suppose that for every collection $A$ of non empty pairwise disjoint sets has a choice function. I need to prove that this implies the axiom of choice. Let $S$ be a collection of sets. For every $B$ ...
1
vote
1answer
70 views

Why is the statement “all vector space have a basis” is equivalent to the axiom of choice? [duplicate]

I'm reading a section in an abstract algebra book, where it reviews vector spaces and suddenly comments that "all vector space have a basis" is equivalent to the axiom of choice...I haven't studied ...
2
votes
1answer
48 views

Ordinal enumeration in ordered Mostowski model - does it not need the global choice?

In Jech's axiom of choice he proves following lemma (lemma 4.5(b) in his book): There is a injective mapping from $M$ to $\mathrm{Ord}\times \operatorname{fin}(A)$, where $A$ is a set of atoms and ...
0
votes
1answer
21 views

Show that the sets of isolated point of $E$ is a countable set - Axiome of choice

Let $E \subset \mathbb{C}$. Show that the sets of isolated point of $E$ is a countable set. That question is related to this question. However, my question somewhat different. Define $Acc(E)^c$ ...
2
votes
2answers
70 views

Does the following condition implies full outer measure?

Let $X \subseteq 2^{\omega}$ be a set of positive Lebesgue measure. Suppose that for every $\eta, \nu \in 2^{<\omega}$ of the same length, the measure of $X$ above $\eta$ is the same as the measure ...
1
vote
3answers
59 views

What does Axiom of Choice mean [duplicate]

So this a fundamental assumption in mathematics. Can someone explain informally what it actually is please. My guess is that its when we say in proofs that "Let $x \in X$". But I am not sure.
0
votes
1answer
39 views

Prob. 9, Sec. 19 in Munkres' TOPOLOGY, 2nd edition: Equivalence of the choice axiom and non-emptyness of Cartesian product

The Axiom of Choice is as follows: Given a collection $\mathcal{A}$ of disjoint non-empty sets, there exists a set $C$ consisting of exactly one element from each element of $\mathcal{A}$; that ...
6
votes
1answer
258 views

Well-foundedness of cardinals and the axiom of choice

Without axiom of choice it is not generally true that the class of all cardinal (in this question we consider Scott cardinal rather than cardinals as ordinals) is not well-founded under the ordinary ...
4
votes
1answer
67 views

Algebraic closure with no nontrival automorphism

In Milne's notes on Galois theory, Chapter 7, p.91 he remarked that it is consistent without the axiom of choice that there exists an algebraic closure $L$ of $\mathbb{Q}$ with no nontrivial ...
1
vote
1answer
105 views

Proof of the Axiom of Choice

This exercise is from Bloch's book and can be found here. Bloch introduces equivalent variations of the axiom of choice where the one that will be proven is stated in terms of functions: AC1 Let $...
4
votes
1answer
90 views

Is there a choice homomorphism?

Let $\pi : \mathbb{R} \to \mathbb{R}/ \mathbb{Q}$ be the canonical projection. With the axiom of choice we "know" that there are choice functions $\alpha : \mathbb{R}/ \mathbb{Q} \to \mathbb{R}$ with $...
2
votes
1answer
52 views

Different Zorn's lemma statements

Given a chain-complete poset $P$, every $x\in P$ lies below some maximal element. Every inductive poset has enough maximal elements a maximal element. Chain-complete means every chain has a least ...
1
vote
1answer
51 views

Surjective function from a countable set

In Lang "Real and Functional analysis" is demonstrated that given a countable set $A$ and a function $f: A \rightarrow B$ which is surjective on $B$, then $B$ is finite or countable. Proof: Consider $...
4
votes
2answers
329 views

Hahn-Banach Theorem for separable spaces without Zorn's Lemma

I was reading about the Hahn-Banach Theorem, its many versions and their proofs. It's known that in the proofs we need Zorn's Lemma. But in the book that I'm reading, the author said if $X$ is a ...
1
vote
2answers
61 views

How does any map have a “pseudosection” (assuming axiom of choice)?

In the Lawvere and Rosebrugh book, Sets for Mathematics, exercise 4.34 is to show that the following is equivalent to the axiom of choice (every epimap has a section aka right inverse): If $f:X\to ...
2
votes
1answer
110 views

Can a large $V_\alpha$ satisfy Comparability but not be well-orderable?

Say that a set satisfies Comparability if any two of its subsets are comparable: one is injectable into the other. Are there models of ZF containing ranks $V_\alpha$ which satisfy Comparability but ...
0
votes
0answers
17 views

Is this Lindeloff theorem using AC? [duplicate]

Theorem: the following are equivalent: 1) The metric space $X$ is separable. 2) $X$ is second-countable (it has a countable basis) proof: $1 \Rightarrow 2: \lbrace B(d,r) : d\in D, r \in \mathbb{Q}...
1
vote
1answer
52 views

Lebesgue-measurable sets requiring the Axiom of Choice to construct

Every known construction of the Vitali set relies on the Axiom of Choice. It happens to not be Lebesgue-measurable. Must every set whose construction relies on the Axiom of Choice not be ...
2
votes
1answer
38 views

Alternate definitions of width (of a partial order) without Choice?

Say an antichain of a poset $P$ is a set of pairwise incomparable elements of $P.$ Typically, the width of a partial order is defined to be the supremum of the cardinalities of antichains of $P.$ When ...
6
votes
1answer
100 views

How can one prove the axiom of collection in ZFC without using the axiom of foundation?

Say I want to prove the axiom(s) of collection from the axiom(s) of replacement. If you have the axiom of foundation, then you can use Scott's trick to do this. But suppose I'm working in a context ...