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

8
votes
1answer
130 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
23 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 ...
2
votes
1answer
36 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
23 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
93 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
68 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
83 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
106 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
36 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
55 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
33 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
52 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
106 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
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
31 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
576 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
52 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
42 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
98 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
59 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
56 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 ...
5
votes
1answer
68 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 ...
1
vote
3answers
68 views

Is this proof legal?

Let $\left(P,\le\right)$ denote a poset. Statement: if every sequence $p_{1}\leq p_{2}\leq\cdots$ in $P$ stabilizes (in the sense that for some $n$ we have $k>n\Rightarrow p_k=p_n$) then every ...
0
votes
1answer
33 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
38 views

Are there any purely semantic proofs of the compactness theorem that don't use the full axiom of choice? [duplicate]

Using Godel's completeness theorem, it can be shown that the compactness theorem is equivalent to the ultrafilter lemma. The compactness theorem can also be proven using ultraproducts and Los's ...
9
votes
0answers
183 views

Paradoxical models of $\sf ZF$ without choice [closed]

There are some models of $\sf ZF$ without the Axiom of choice, where some paradoxical statements hold that are not possible in $\sf ZFC$ (we do not require that all those statements necessarily hold ...
6
votes
0answers
172 views

Is Kunen's claim about non-equivalent forms of Axiom of Choice, true?

Consider the following forms of the axiom of choice: $AC_1:\forall F\neq \emptyset~~~(\emptyset\notin F~\wedge~\forall x,y\in F~~~(x\neq y\rightarrow x\cap y= \emptyset))\rightarrow \exists C~\forall ...
2
votes
2answers
65 views

On those behaviors of continuum function which imply the axiom of choice

It is a folklore fact that within $\text{ZF}$ the generalized continuum hypothesis ($\text{GCH}$) implies the axiom of choice ($\text{AC}$), namely: $$ZF+\forall \kappa\in ...
9
votes
2answers
177 views

Examples of theorems that haven't been proven without AC in practice but can be proven without it in principle

It is possible to prove theorems of the form "if $\phi$ is provable in ZFC, then $\phi$ is provable in ZF". For example, let $\phi$ be a statement that is absolute between $V$ and $L$. If $\phi$ were ...
1
vote
0answers
31 views

Continuous is sequentially continuous [duplicate]

Is it possible to prove $f: \mathbb{R} \to \mathbb{R}$ is continuous everywhere iff it is sequentially continuous everywhere without the axiom of choice?
5
votes
0answers
64 views

Connectedness of parts used in the Banach–Tarski paradox

A quote from the Wikipedia article "Axiom of choice": One example is the Banach–Tarski paradox which says that it is possible to decompose the 3-dimensional solid unit ball into finitely many ...
7
votes
2answers
142 views

Is it possible that $2^n=3^n$ for some Dedekind-finite cardinal $n\gt0$?

Is it possible that $2^n=3^n$ for some Dedekind-finite cardinal $n\gt0$? I think the question speaks for itself, but let me try and satisfy the "quality standards" algorithm by padding it. Yes, I ...
1
vote
1answer
40 views

factorial of infinite Cardinals

Let $S_A$ be set of all bijections over $A$ such that $Card(A)=\kappa$. Define foctorial as $\kappa!:=Card(S_A)$. Show that if $\kappa$ is infinite, then : $\kappa!=2^\kappa$ First, I've ...
1
vote
2answers
82 views

What do you need to know about ordinals to understand Zorn's Lemma's proof?

I'm trying to understand the proof of Zorn's Lemma but the one which does not use ordinals (Halmos' proof) is extremely long and I really feel I get lost somewhere along the way. On the other hand, ...
8
votes
1answer
69 views

Is there such a thing as “completion with respect to the axiom of choice?”

Completions abound in mathematics. For example: the completion a metric space with respect to Cauchy sequences the algebraic closure of a field the Stone-Čech compactification of a topological ...
2
votes
0answers
66 views

Fields whose algebraic closure cannot be constructed without the axiom of choice

One can show that the statement that every field has an algebraic closure requires the axiom of choice. However, for almost all "everyday" fields, it seems that one can actually produce an algebraic ...
1
vote
0answers
38 views

Hilbert space without the projection theorem

One succinct statement of the projection theorem in Hilbert space is $A+A^\bot=\scr H$, where $A\in\scr C$, the set of closed subspaces of $\scr H$. (We will also denote the set of all subspaces by ...
2
votes
1answer
36 views

If $|X|<|Y|$ then $|Y|=|Y-X|$ (with $Y$ infinite)

Like the title says, I would like to prove that if $|X|<|Y|$ then $|Y|=|Y-X|$. (with $Y$ infinite) I know I have to use the axiom of choice, but I've no idea about how to proceed. Any help is ...
2
votes
1answer
14 views

If $A$ is D-Infinite then $|P_{\infty}(A)|=|P(A)|$

I want to prove that if $A$ is a D-Infinite set (i.e. it contains a countable subset $X$), then the set of the infinite parts of $A$, $P_{\infty}(A)$ has the same cardinality of $P(A)$. I know that ...
1
vote
1answer
80 views

Hall's marriage Theorem and Tychonoff Theorem

I was reading this paper. In particular the second point. He proves the Hall's marriage Theorem for infinite family using the Tychonoff theorem on topological product of compact $T_2$ spaces and the ...
1
vote
1answer
56 views

Ultrafilter Lemma and Dimension Theorem

Reading on Wikipedia I find out that (the uniqueness in) the Dimension Theorem for arbitrary Vector Spaces can be proved using just the Ultrafilter Lemma (a strictly weaker version of Axiom of ...
1
vote
2answers
66 views

Axiom of Choice (Naive Set Theory, Halmos)

I'm currently reading Naive Set Theory by Paul Halmos and I'm not quite understanding what he means in sec. 15, The Axiom of Choice. Suppose that $\mathscr{C}$ is a non-empty collection of ...
1
vote
0answers
62 views

Hilbert projection theorem without countable choice

All the proofs of the Hilbert projection theorem, existence part, that I have seen so far use countable choice (usually implicitly). Is this necessary? It seems like you might be able to leverage the ...
3
votes
1answer
69 views

Automorphisms of abelian groups and Choice

The latest question to be asked at the Group Pub Forum is a classic: can every group be realised as the automorphism group of a group? The answer is no, and the canonical answer is the infinite cyclic ...
0
votes
0answers
25 views

A Sequnce from an infinte set [duplicate]

We know if $A$ is infinite set then we can choose a sequence from $A$. But I don't know how this requires AC.(or countable AC?) Thanks in advance for any suggestion. Maybe the approach depend on ...
3
votes
3answers
106 views

Confused about Axiom of Choice

(1) I understand that if I have a non-empty set $A$, choosing an element $\alpha$ from $A$ does not require the Axiom of Choice. (2) I also understand that if I have a finite collection of ...