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

5
votes
1answer
61 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
41 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
39 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
98 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
105 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
66 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
64 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
51 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
42 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
104 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
102 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
68 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
55 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
65 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
39 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
153 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
49 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
34 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
104 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
72 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
114 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
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? ...
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
42 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
610 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
60 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 ...
0
votes
2answers
78 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$. ...
2
votes
1answer
59 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
99 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 ...
5
votes
1answer
75 views

Partial order on cardinalities without the axiom of choice

Cardinality can still be defined without choice, e.g. as equivalence class of equipotent sets, see Defining cardinality in the absence of choice. Injections define partial order on cardinalities by ...