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

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 ...
1
vote
1answer
21 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
73 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
56 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 ...
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: \{ ...
2
votes
0answers
62 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
38 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
108 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 ...
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
515 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
72 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
24 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$ ...
0
votes
1answer
56 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
45 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 ...
2
votes
2answers
69 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
55 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
257 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
64 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
99 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 ...
3
votes
1answer
83 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
48 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
271 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
58 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 ...
1
vote
1answer
48 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
37 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
96 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
966 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
55 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
104 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
70 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 ...
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
62 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 ...
7
votes
3answers
212 views

Existence of mathematical objets constructed using the axiom of choice

Let consider the Vitali set $V \subset \mathbb R$, which is constructed using the axiom of choice. (I could take any other mathematical "object" that can be constructed using the axiom of choice, but ...
2
votes
0answers
37 views

How Does the Following Definition of the Axiom of Choise Entail that Elements Are Simultaneously Chosen from an Infinite Collection of Nonempty Sets [duplicate]

The following excerpt is from Ethan Bloch, Proofs and Fundamentals: A First Course in Abstract Mathematics (2nd ed, 2011 : page 121) and concerns one of the motivations for introducing the axiom of ...
6
votes
2answers
157 views

Does the law of the excluded middle imply the existence of “intangibles”?

First off, I'm not sure if "intangible" is standard terminology, Wikipedia defines an intangible object to be: "objects that are proved to exist, but which cannot be explicitly constructed". So if ...
1
vote
1answer
45 views

Axiom Of Choice to create a sequence of right inverses

I want to construct a sort of sequence of right inverses. My question is whether the construction uses the Axiom Of Choice correctly. Suppose I have a sequence of surjective functions $$ ...
8
votes
2answers
196 views

What's an example of a vector space that doesn't have a basis if we don't accept Choice?

I've read that the fact that all vector spaces have a basis is dependent on the axiom of choice, I'd like to see an example of a vector space that doesn't have a basis if we don't accept AoC. I'm ...
0
votes
0answers
32 views

Prob 2(d) Sec 9 in Munkres' TOPOLOGY 2nd edition: Is it possible to construct a choice function? [duplicate]

Here's Lemma 9.2 in Topology by James R. Munkres, 2nd edition: Given a collection $\mathscr{B}$ of non-empty sets (not necessarily disjoint), there exists a function $$c \colon \mathscr{B} \to ...
8
votes
2answers
275 views

Axiom of Choice needed to “categorify” the cardinals?

I was playing around in $\mathsf{Set},$ trying to reduce it modulo isomorphisms to make a category $\mathsf{Card},$ letting the objects of $\mathsf{Card}$ be the isomorphism classes of $\mathsf{Set}$ ...
5
votes
1answer
85 views

Is it consistent that every set is the countable union of sets with smaller cardinality, or is it just alephs?

(note: in what follows by "consistent" I mean "consistent relative to large cardinals") My question regards the exact statement of result which Gitik has proven in his paper "All Uncountable ...
4
votes
1answer
179 views

Existence of Hamel basis, choice and regularity

Blass (1984) shows that the existence of Hamel basis for arbitrary vector space over any field implies the axiom of choice. However such implication needs the axiom of regularity. As in Blass' ...