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

Choice function to obtain all elements of an infinite set

I'm following a proof of "Axiom of Choice implies Well Ordering Theorem" (from a not-well-known book we use for class), and the author uses this procedure: First, he takes any non-empty set $X$ and ...
1
vote
1answer
38 views

Proof of one instance of the Axiom of Choice from another.

I'm trying to show (i) $\implies$ (ii): (i) For any relation $R$, there exists a function $H\subseteq R$, with $\newcommand{\dom}{\mathrm{dom} \ } \dom H = \dom R$. (ii) For any set $I$ and any ...
2
votes
1answer
58 views

Does this argument rely on countable choice?

Consider the following Theorem: Any algebraic field extension $K|F$ of infinite degree contains finite subextensions of arbitrarily high degree. Proof: We'll prove that, for any n, there's a ...
1
vote
1answer
40 views

Proving equivalence of Axiom of Choice

I am working on the following question concerning the axiom of choice and one of its many equivalences. Advice as to whether I am on the right track would be appreciated. As a preface, I have looked ...
1
vote
0answers
32 views

divisible subgroup without axiom of choice

the theorem asserting that the divisible subgroup of an Abelian group is a direct summand depends on Zorn's lemma. in ZF without AC is there a construction which yields a model of an Abelian group ...
2
votes
1answer
40 views

Absolute coequalizers in $\mathbf {Set} $

Let $ A $ be a set and let $ R\subseteq A\times A $ be an equivalence relation on $ A $. Denote by $ p, q $ the projections $ R\longrightarrow A $ on the first and second factor, respectively. The ...
1
vote
1answer
96 views

Miller's Construction, Partition Principle and Failure of Axiom of Choice

Partition Principle ($PP$) is the following statement: For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$ It is known that $ZF\vdash ...
2
votes
0answers
36 views

Is this an equivalent form of Axiom of Choice? [duplicate]

It is known that Axiom of Choice implies the following statement: For each two sets $A$ and $B$, there is a one to one function from $A$ to $B$ iff there is a function from $B$ onto $A$ Is above ...
2
votes
1answer
96 views

Why is the powerset axiom more acceptable than the axiom of choice?

The key step in Zermelo's proof of the well ordering theorem is to use $\text{AC}$ to simultaneously choose the next elelment for all possible partial chains in prospective well orderings, but that ...
2
votes
1answer
38 views

Existence of a Set Function Axiom of Choice

I have the following problem. Let $A$ be a set and $B\neq\emptyset$ be a proper subset. Prove the existence of a function $f:A\to A$ such that $f\circ f=f$ and $\text{im}~f=B$. In the case where $A$ ...
0
votes
2answers
62 views

Does the Cartesian product of an infinite family have all the elements we expect?

Given the axiom of choice, we know that the Cartesian product of an infinite family of non-empty sets is non-empty. However, this doesn't tell us whether the Cartesian product contains every element ...
4
votes
1answer
51 views

Does the converse of Tychonoff's theorem hinge on the axiom of choice?

Tychonoff's theorem:$\phantom{---}$ If $A$ is a non-empty index set and $X_{\alpha}$ is a non-empty compact topological space for every $\alpha\in A$, then $X\equiv\times_{\alpha\in A} X_{\alpha}$ is ...
1
vote
1answer
31 views

Disjoint $AC$ equivalent to $AC$

I want to show that these two forms of $AC$ are equivalent: $(1)$ For each collection of nonempty sets $X$ there is a choice function. $(2)$ For each collection of pairwise disjoint nonempty sets $X$ ...
3
votes
3answers
153 views

The equivalence of “Every surjection has a right inverse” and the Axiom of Choice

This is a problem from Tao's Analysis I. We are asked to show that the axiom of choice is equivalent to the statement that for any sets $A$ and $B$ for which a surjection $g:B\to A$ exists, an ...
1
vote
2answers
43 views

Axiom of choice variants [duplicate]

Is there any good book where the equivalence of AC to the statement "Any surjection has a right inverse" is proved (and maybe other equivalences)? I could do $AC \Rightarrow$ "Any surjection has a ...
2
votes
2answers
83 views

Formal approach to (countable) prisoners and hats problem.

I've found this nice puzzle about AC (I'm referring to the countable infinite case, with two colors). The puzzle has been discussed before on math.SE, but I can't find any description of what is ...
2
votes
1answer
63 views

Characterization of dense open subsets of the real numbers

Does the complement of every dense open subset of the real numbers have Lebesgue measure $0$? This is certainly not a characterization of dense open subsets of reals, since the complement of the ...
0
votes
0answers
38 views

Proof of “Every vector space has a basis $\implies$ AC” without mentioning von Neumann hierarchy

I am writing a short (30-50 pages) report on AC for an exam. I really would like to include the proof that "Every vector space has a basis $\implies$ AC". Actually, every proof I could find proves ...
2
votes
1answer
341 views

Can a vector subspace have a unique complement in absence of choice?

Let $V$ be a vector space (not necessarily finite dimensional and over some arbitrary field), and $W$ a proper non-zero subspace. If we assume existence of bases, it is easy to show that $W$ can be ...
8
votes
1answer
151 views

Is “PA has no non-standard models” consistent with ZF?

I have seen several proofs that there exist nonstandard models of arithmetic, but they all seem to rely on the compactness theorem, which is not implied by ZF. So are there any proofs in ZF that ...
1
vote
1answer
24 views

Writing the ZF formula for the choice function (given Well-ordering)

If every set has a well order, then the axiom of choice follows: Given a well order on $\bigcup_{i \in I} A_i$ we define the choice function in this way $f(i) =$ "the first element of $\bigcup_{i \in ...
3
votes
1answer
44 views

What is the definition of the Feferman-Levy model?

Any (reference to) definition of Feferman-Levy model in set theory? I cannot find any... Though I know what is Levy collapse.
2
votes
2answers
31 views

Proof of: $X$ is finite $\iff X$ is Tarski-finite

I am self-studying Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876). In the fourth chapter, he deals with different definitions of finite set. Here is the classical one: ...
2
votes
2answers
103 views

Examples of figures whose area depend on axiom of choice

Many times I have heard that there are some 'figures' whose area is not fixed and they depend on axiom of choice. For example, In this answer. In this lecture about probabilty. I did not know ...
4
votes
1answer
71 views

An explicit construction for an everywhere discontinuous real function with $F((a+b)/2)\leq(F(a)+F(b))/2$?

I would like to know an explicit method on constructing an everywhere discontinuous real function $F$ with the property: $$F((a+b)/2)\leq(F(a)+F(b))/2.$$ There is a non-constructive example (with the ...
3
votes
2answers
94 views

How do we get a simplicial homology functor?

The $n$-th simplicial homology group $H_n(A)$ of an abstract simplicial complex $A$ depends on the choice of an orientation for $A$ (but for different orientations, the homology groups are ...
2
votes
2answers
112 views

Is the Axiom of Choice necessary to prove $\mathbb R \approx \mathcal P(\omega)$?

I am self-studying Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876), and I'm getting quite confused about cardinal arithmetic without AC. Here (Which sets are well-orderable ...
1
vote
1answer
38 views

Why do we need the axiom of choice in showing the non-emptiness of an infinite Cartesian product

Given $I$ a set of indexes and $X_i$ a set of topological spaces, define The Cartesian product: $\prod_{i \in I}X_i = \{ f:I \rightarrow \bigcup X_i | f(i) \in X_i \}$ I have read that we need ...
1
vote
1answer
60 views

infinite Cartesian products

Quote from Wikipedia, infinite set: The Cartesian product of an infinite number of sets each containing at least two elements is either empty or infinite. I know that this is the regime where we ...
3
votes
2answers
577 views

The Continuum Hypothesis & The Axiom of Choice

Does anyone here know of a reference to an analysis on a proposed relationship between The Continuum Hypothesis and The Axiom of Choice?
8
votes
5answers
602 views

Do we need Axiom of Choice to make infinite choices from a set?

According to the answers to this question, we do not need choice to pick from a finite product of nonempty sets, even if each of the sets is infinite. The axiom of choice is required to ensure that a ...
10
votes
1answer
107 views

Partitions of the Cantor space into parities

Call a partition of $2^\mathbb{N} = A\cup B$ a parity partition if, for any $n\in\mathbb{N}$, flipping the $n$th bit of any element of $A$ results in an element of $B$, and vice-versa. Given a choice ...
2
votes
0answers
34 views

Is the Axiom of Choice restricted to $\Bbb R$ independent of ZF? [duplicate]

This is really a yes-no question, and I am hundred percent certain that the answer is "yes". I simply have not found it written directly anywhere. True, the Axiom of Choice is independent of ZF if we ...
1
vote
1answer
53 views

Could induction give us an infinite sequence of sets $X_1 \subseteq X_2 \subseteq \cdots$ or do we need the axiom of choice?

Suppose at each step $n$ of a proof by induction, we have a set $X_n$. Also, $X_{n} \subseteq X_{n+1}$. Is induction enough to give us $\bigcup_{n \in \mathbb{N}} X_n$? Or rather, when is it enough? ...
2
votes
2answers
65 views

Can we prove without the axiom of choice that subspaces of finite dimensional vector spaces are finite dimensional as well?

Let $E$ be a vector space and $F$ a subspace of $E$. Show that if $E$ is finite dimensional then $F$ is finite dimensional too. It's easy to prove by contradiction by taking a family linearly ...
0
votes
2answers
42 views

Bernstein sets, Well-Ordering theorem vs Axiom of Choice

In the construction of Bernstein sets (see here), is it necessary to use the well-ordering theorem? Why can't you just use the Axiom of Choice to pick two points?
2
votes
1answer
38 views

Does Vitali set imply the axiom of choice

I know that the construction of Vitali set needs the axiom of choice, but this only states that $AC \implies V$. Is it also true that $V \implies AC$? If $\neg AC \implies \neg V$, then what ...
0
votes
0answers
34 views

Tarski's theorem follows from choice [duplicate]

It is known that Tarski's theorem and axiom of choice are equivalent. Implication $\Rightarrow$ follows from considering bijection $(A+\aleph(A))^2\rightarrow(A+\aleph(A))$. Implication $\Leftarrow$ ...
12
votes
2answers
643 views

Transfinite Induction and the Axiom of Choice

My question is essentially this: Why does the principle of transfinite induction not suffice to show the axiom of choice when the sets to be chosen from are indexed by a well ordered set? I have read ...
7
votes
6answers
1k views

Axiom of Choice and finite sets

So I am relatively familiar with the Axiom of Choice and a few of its equivalent forms (Zorn's Lemma, Surjective implies right invertible, etc.) but I have never actually taken a set theory course. I ...
-4
votes
1answer
205 views

Can we prove that a bounded closed subset of $\mathbb R^n$ is compact without Axiom of Choice?

Can we prove that a bounded closed subset of $\mathbb R^n(n \ge 1)$ is compact without using Axiom of Choice? This is a related question which was closed.
1
vote
1answer
58 views

Proving Equivalence of Two Version of Axiom of Choice

I am working on an assignment that requires proving the equivalence of two versions of the axiom of choice. (1st form): For any relation $R$, there is a function $H \subseteq R$ with dom $H =$ dom ...
9
votes
1answer
99 views

Choosing elements of linear orders

Is it consistent with ZF that there can be a countable family of linear orders, each isomorphic to $\mathbb Z$ (that is, every element has a unique predecessor and successor, and any two elements have ...
1
vote
1answer
43 views

What is the role of induction in the proof of König's Lemma?

I am looking at this version of König's Lemma: let $T$ be a tree with countably infinite nodes, and each node has finite degree. Then, $T$ has a simple path containing countably infinite number of ...
5
votes
1answer
90 views

Cardinality of all $\mathbf{\Sigma}^0_\alpha$-sets over Baire space without full choice

It is well-known that the set of all open (or closed) sets on Baire space has cardinality of the continuum. In context of choice, we can prove that the set of all $\mathbf{\Sigma}^0_\alpha$-sets over ...
0
votes
2answers
65 views

Theorem 4.15 page 22, Real and Abstract Analysis, Hewitt and Stromberg

Following is Theorem 4.15 from Real and Abstract Analysis, Hewitt and Stromberg Theorem: Every infinite set has a countably infinite subset. Proof: Let $A$ be a infinite set. We show by induction ...
1
vote
1answer
32 views

Application of the axiom of choice

I would like to prove the following statement. If $A$ is a bounded, infinite subset of $\mathbb{R}$, then there is an element $a \in A$ such that $A-\{a\}$ contains a sequence which converges to $a$. ...
0
votes
1answer
38 views

Are ACF and Ultrafilter Lemma/BPIT equivalent?

$\mathsf{ACF}$ is the proposition that every set of nonempty finite sets has a choice function. It can be shown that $\mathsf{BPIT} \Rightarrow \mathsf{ACF}$, because $\mathsf{BPIT}$ implies that ...
2
votes
1answer
58 views

Confusion Regarding the Axiom of Countable Choice

My current understanding of the Axiom of Countable Choice is that the following example needs it in order to work: Let $X$ be a countable family of finite sets. Then there exists a choice function ...
1
vote
3answers
95 views

Proof that $\mathbb{N}\times \mathbb{N}\cong \mathbb{N}$ without $AC_\omega$ or Arithmetic

Proving that $\mathbb{N}\times \mathbb{N} \cong \mathbb{N}$ is incredibly useful for proving that the countable union of countable sets is countable and the fact that finite cartesian products of ...