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
3answers
109 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
98 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
79 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
43 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
44 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 ...
10
votes
0answers
210 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
189 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
70 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
273 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 ...
12
votes
1answer
256 views

Inner product on $C(\mathbb R)$

With Axiom of choice it is possible to construct an inner product on $C(\mathbb R)$. My question is, is it possible to explicitly construct an inner product on $C(\mathbb R)$? I.e. to give a closed ...
1
vote
0answers
33 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?
6
votes
0answers
80 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 ...
9
votes
2answers
176 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
54 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
112 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
73 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 ...
4
votes
0answers
86 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
46 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
40 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
17 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
98 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
62 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
93 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
66 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
78 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
26 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
115 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
84 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
55 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
100 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
121 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
56 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
87 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
92 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
111 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 ...
3
votes
1answer
103 views

Does existence of a non-continuous linear functional depend on Axiom of Choice?

Well, it is easy to construct a non-continuous linear functional on an arbitrary infinite-dimensional vector space (assuming Choice, and taking a basis etc.). I think it is intuitive to say that: ...
5
votes
1answer
98 views

Do we need choice to prove that $|\mathbb{N} \times A| = |A|$ for all infinite sets $A$?

I can't think of any way to prove it without choice.
2
votes
1answer
63 views

Zorich's misinterpretation of “Axiom of Choice”?

I'm reading Zorich'es "Mathematical Analysis I", Ed 4, 2004, and wonder if this is a trifle misinterpretation of "Axiom of Choice". Ch 1.4 "Supplementary Material" says: 8°. (A x i o m o f c h o i ...
9
votes
2answers
422 views

Is the Axiom of Choice implicitly used when defining a binary operation on a quotient object?

Let's say you have a group $(G,\cdot)$ and you have a normal subgroup $N$ (note we are considering this only as a set). And now we want to define a binary operation $\star$ on $G/N$ such that $(G/N, ...
1
vote
2answers
788 views

Proof that a product of two quasi-compact spaces is quasi-compact without Axiom of Choice

A topological space is called quasi-compact if every open cover of it has a finite subcover. Let $X, Y$ be quasi-compact spaces, $Z = X\times Y$. The usual proof that $Z$ is quasi-compact uses a ...
1
vote
1answer
51 views

What is wrong with the following proof saying Zorn's lemma implies Hausdorff maximum principle?

I am reading 'Topology' by J.R. Munkres's first chapter on set theory. In the exercises 5-7 on page 72 he asks the reader to show that Zorn's lemma implies Hausdorff maximum principle via the ...
-3
votes
1answer
228 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.
0
votes
1answer
104 views

“Hidden” axiom of choice?

Let $\mu$ be a measure on $S$ such that: $\mu\left(\emptyset\right)=0$ and $\mu(S)=1$ if $X\subseteq Y$, then $\mu(X)\leq\mu(Y)$ $\mu\left(\{a\}\right)=0$ for all $a\in S$ if $X_n$, ...
8
votes
1answer
147 views

Can all theorems of $\sf ZFC$ about the natural numbers be proven in $\sf ZF$?

I know a proof of Hindman's theorem that uses ultrafilters on the natural numbers, and ultimately, the axiom of choice. But the theorem itself is essentially a combinatorial property of the natural ...
0
votes
2answers
37 views

Does defining the closure of a set as the intersection of all closed set that contain it requires the axiom of choice?

Given a set $S$, the closure of $S$ is sometimes defined as the intersection of all the closed sets that contain it. This type of argument is pervasive in mathematics when one want to construct the ...
2
votes
2answers
71 views

An equivalence of AC

I have to prove the following: In $ZF^-$ the axiom of choice implies: For every set X there exist $Y \subseteq \bigcup X$ such that: Y has at most one element in common with each of X Y is maximal ...
0
votes
2answers
64 views

Is this a basis for the dual space?

There is an example on Wikipedia that I don't understand and I'd appreciate some help. They define $\mathbb R^\infty$ to be the space of all sequences that are zero except for finitely many indexes. ...
5
votes
1answer
103 views

Existence of a regular uncountable $\aleph_{\alpha}$ without $\mathsf{AC}$

Set theory (Jech) $\text{p.}\;27:$ It is an open problem whether one can prove without the axiom of choice that there exists a regular uncountable $\aleph_{\alpha}\;($the informed guess is that ...
3
votes
1answer
77 views

Book/Books leading up to the the axiom of choice?

I am familiar with the axioms of ZF set theory and some basic uses of them to completely formally construct more complex objects such as natural numbers etc. However I have pretty much no background ...
1
vote
2answers
102 views

Confusion regarding one formulation of the Axiom of Choice.

One formulation of the Axiom of Choice is: The Cartesian product of non-empty sets is always non-empty. Cartesian product is defined as making "every possible pair" between elements of two sets. ...