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

1
vote
1answer
35 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
50 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
31 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
41 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
37 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
570 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
49 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
58 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
31 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
54 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
65 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
32 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
37 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
167 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 ...
3
votes
2answers
62 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
173 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
30 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
141 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
39 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
81 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
64 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
77 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
55 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
65 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
61 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
104 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 ...
9
votes
0answers
74 views

Choice in a Particular HOD Type Model

Let $V \models ZFC$. Let $P$ be a forcing and $G \subseteq P$ be generic over $V$. Let $x \in V[G]$. Let $M$ be the class of set that are hereditarily definable (in $V[G]$) using as parameters $x$ ...
4
votes
0answers
45 views

Strength of “Every finite dimensional subspace of a vector space has a complement”

Does the following choice principle have a name? Every finite dimensional subspace of a vector space has a complement. Equivalently, every line inside a vector space has a complementary ...
4
votes
1answer
64 views

Regarding Thomas Jech's demonstration of Zorn's lemma via induction

Thomas Jech, such as many other mathematicians, demonstrates $AC \rightarrow ZL$ via transfinite induction. He says: Proof. We construct (using a choice function for nonempty sets of P), a chain ...
4
votes
2answers
93 views

Proof that $\omega_1$ is countable (where is the flaw?)

I have discovered a "proof" of the fact, that $\omega_1$ can be countable, contradicting its definition. It mustn't assume axiom of choice, so I guess there are some parts of this construction which ...
3
votes
1answer
49 views

Unique ultrafilter on $\omega$

We know that from axiom of choice (or just BPIT) we can deduce ultrafilter lemma, which states that every filter can be extended to an ultrafilter. From this lemma we can derive existence of at least ...
1
vote
4answers
71 views

How do I tell whether axiom of choice is used or not?

I am having a hard time understanding the Axiom of Choice(AC). Say I have an index set $A$ , and a collection of indexed sets {${V_\alpha}$}, where $\alpha$ is a member of $A$. Then, does the ...
5
votes
1answer
87 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 ...
4
votes
1answer
102 views

A question regarding the status of CH in the Gitik model

Consider models of ZF+"Every uncountable cardinal is singular" (eg. Moti Gitik: "All uncountable cardinals can be singular", Israel journal of Mathematics, 35(1-2): 61-88, 1980). How should CH be ...