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

9
votes
0answers
114 views

Over ZF, does “every Hilbert space have a basis” imply AC?

I know there is a similar result due to Blass [1] that over ZF, "every vector space has a (Hamel) basis" implies AC. Looking around, however, I can't find any results on the question for Hilbert ...
0
votes
0answers
38 views

Existence of a basis in constructive vector spaces

As I was trying to review forgotten knowledge on Vector Spaces in wikipedia, I read that the existence of a basis follows from Zorn lemma, hence equivalently from the axiom of choice. Actually, the ...
0
votes
1answer
42 views

Dedekind finite set and a special well ordered set

In ZFC, Dedekind finite set and finite set are same things. So I have a set say A(which is equal to N in ZFC) all Dedekind finite set are equivalent to proper subsets of A and A is well ordered set. ...
0
votes
1answer
45 views

Basis in topology and AC

Let S ⊂ ℘(X). Let T be the coarsest topology on X which contains S. Then we call T the topology generated by S. Let S ⊂ ℘(X). Then we can easily prove using (generalised distributive law) the ...
0
votes
1answer
19 views

Countable union of countable sets is countable and AC(or axiom of countable choice)

It is written in tag page of Axiom of choice in MSE that Countable union of countable sets is countable is a theorem which follows from AC. Do we really need AC to prove this. Please see following ...
5
votes
1answer
69 views

What is needed to make Euclidean spaces isomorphic as groups?

Consider the abelian groups $G_n=(\mathbb R^n,+)$ for $n\geq1$. Claim: For any $n$ and $m$ the groups $G_n$ and $G_m$ are isomorphic. This claim is true if one assumes the axiom of choice, and I ...
0
votes
1answer
44 views

Existence of non measurable set and ZF theory?

Does statement: 'Existence of non measurable set' consistent with ZF theory. or if I throw Axiom of choice from ZFC theory. Can I prove or disprove existence of a countably additive measure function ...
3
votes
1answer
41 views

Does there exist a connected 2-regular uncountable graph, or an uncountable path?

Does there exist a connected 2-regular uncountable graph? Can I use the axiom of choice to construct an uncountable path of elements from the reals? The question arose when reading this: Also, ...
2
votes
2answers
100 views

How does one prove $ZF\vDash MC\Rightarrow AC$?

This is somewhat adressed to Andreas Blass, whose papers I have read, in particular I make reference to an old paper of his »Existence of Basis implies the Axiom of Choice« (84). Anyone who happens to ...
-1
votes
0answers
108 views

Is the axiom of choice constructive in the constructible universe?

Even ZF has some non-constructive elements mostly due to contradiction proofs. For example one may be able to construct a sequence of objects some of which have a given property without being able to ...
1
vote
0answers
62 views

First Order Model Existence without Weak Konigs Lemma or Choice

In studying Godel's Completeness Theorem and its various related formulations like the Model Existence Theorem and the Lowenheim-Skolem Theorem there is one rather subtle point that I have not yet ...
2
votes
1answer
69 views

Infinite Set has greater or equal cardinality that of N

For any infinite set, we can find a 1-1 function (not necessary onto) from N (set of natural no.) to that set. The proof of this theorem I know using axiom of choice. Can we prove it without using ...
0
votes
1answer
39 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 ...
2
votes
1answer
65 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
54 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 ...
1
vote
1answer
45 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
33 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 ...
3
votes
1answer
46 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
107 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
37 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 ...
3
votes
1answer
105 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
40 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
71 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
59 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
33 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$ ...
1
vote
2answers
44 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
95 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
66 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
41 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 ...
8
votes
1answer
156 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
26 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
50 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
36 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
107 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
75 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
95 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
116 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
67 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 ...
2
votes
0answers
35 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? ...
10
votes
1answer
109 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
2answers
69 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
47 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
35 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$ ...
8
votes
5answers
620 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 ...
1
vote
1answer
61 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 ...
1
vote
1answer
44 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 ...
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 ...