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

1
vote
1answer
51 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
67 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
40 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
263 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
54 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 ...
12
votes
0answers
304 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
37 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
55 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
85 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
65 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
517 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
25 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
66 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
46 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
58 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
65 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
102 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
86 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
49 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
49 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
302 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
60 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
51 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
99 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 ...
8
votes
3answers
978 views

The smallest infinity and the axiom of choice

The short version of this question is: which (natural) axiom should be added to ZF so that the statement "$\aleph_{0}$ is the smallest infinity" becomes true? A set $A$ is called infinite if it can ...
1
vote
0answers
56 views

$|A^2|=|A|$ for every infinite $A$ iff Axiom of Choice holds. [duplicate]

I've seen this assertion in a few comments around the site, and I found the answer to the $\rightarrow$ implication here. Does anyone know a (hopefully simple) proof of the $\leftarrow$ implication?
1
vote
1answer
107 views

What is the first order formulation of Zorn's lemma in the language of set theory?

Very often in notes of courses in set theory you find the assertion that in ZF the Axiom of choice (AC) is equivalent to Zorn's Lemma (ZL) (which is equivalent to Well Ordering Principle which it ...
1
vote
0answers
48 views

Proving implication on well ordered set implies AC

Consider the following statement: If $A$ is a well-ordered set such that every nonempty subset of $A$ has a maximal element, then $A$ is finite. I am trying to prove that this statement implies ...
4
votes
1answer
72 views

Countable cartesian product and Axiom of Choice

In the A taste of Topology book, when talking about Cartesian product $\prod\{S:S\in\mathcal{S}\}$, the author writes the following: It is straightforward that $\prod\{S:S\in\mathcal{S}\}\neq\...
1
vote
3answers
175 views

Ordinal with given cardinality (without AC)

Is it possible to show that every cardinality has an ordinal with this cardinality (without the axiom of choice)? If so, how?
1
vote
0answers
63 views

Proof: Every lattice has a maximal filter iff AC

I'm working through a proof of Herrlich's book Axiom of Choice, p.58 (Google books): Equivalent are Every lattice has a maximal filter. Axiom of Choice. In this book, a lattice is ...