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

0
votes
2answers
40 views

Existence of how many sets is asserted by the axiom of choice in this case?

Applying the axiom of choice to $\{\{1,2\}, \{3,4\}, \{5,6\},\ldots\}$, does only one choice set necessarily exist, or all of the $2^{\aleph_0}$ I "could have" chosen? Or something in between? It ...
2
votes
0answers
28 views

A puzzle concerning the axiom of choice and the reals

Recently I was told the following riddle: Let $A=(a_1,...a_n,...a_{2n},a_{2n+1})$ a 2n+1-tuple of real numbers with the following property: Whatever number $a_i$ is removed from $A$ the remaining 2n ...
16
votes
1answer
2k views

Constructing a subset not in $\mathcal{B}(\mathbb{R})$ explicitly

While reading David Williams's "Probability with Martingales", the following statement caught my fancy: Every subset of $\mathbb{R}$ which we meet in everyday use is an element of Borel ...
0
votes
1answer
86 views

Does the regularity of $\omega_{\alpha+1}$ need Axiom of Choice?

Many books indicate yes to this question. However, I found the only lemma they claim to use AC is the following statement: If $\{A_i\}_{i\in I}$ is a family of sets, then $|\bigcup_{i\in ...
-4
votes
0answers
11 views

does there exist a choice function always for a family of set? [on hold]

there exist a choice function always for a family of set is that true or false and if it is true what is the prove and if it is false give me an example
1
vote
1answer
42 views

For every cardinal $\kappa$, $\kappa^+$ is regular

Again I'm struggling with a proof from this introduction to cardinals. Lemma 2.6. For every cardinal $\kappa$, $\kappa^+$ is regular. Proof. If not, then there would be a cofinal map ...
1
vote
1answer
30 views

Using the axiom of choice to choose bijections

I couldn't think of a better question title. I am trying to understand the proof of theorem 1.8 in this introduction to cardinals. Theorem 1.8. Let $\kappa\in CARD$. Let ...
1
vote
1answer
37 views

Regarding Choice in fields outside set theory.

When authors say stuff like The equivalence of continuity and sequential continuity in metric spaces uses(/requires) some version of the axiom of choice. Are they assuming that we are working ...
9
votes
2answers
1k views

Maximal ideals in $C(X)$ and Axiom of Choice

The following result are true if we assume full axiom of choice: A. If $X$ is a compact Hausdorff space, then every maximal ideal of the ring $C(X)$ has the form $A_p=\{f\in C(X); f(p)=0\}$. B. If ...
3
votes
1answer
61 views

Without the Axiom of Choice, $\aleph_0<2^{\aleph_0}$ implies $\aleph_1\le 2^{\aleph_0}$?

Question: In ZF (so AC does not necessarily hold) does the following claim hold? $\aleph_0<2^{\aleph_0}$ implies $\aleph_1\le 2^{\aleph_0}$ This question arose to me when reading the top ...
3
votes
1answer
15 views

Comparability of a set and a subset of power set.

It's well known that for any set $A$, $A < P(A)$. But now, I have some question that, WITHOUT AC, can we guarantee that $A \leq X$ or $X \leq A$ whenever $X \subseteq P(A)$? Thank you.
1
vote
1answer
38 views

Does König's inequality require axiom of choice?

König's inequality: If $\kappa_\alpha<\lambda_\alpha$ for all $\alpha<\mu$, then $\sum\kappa_\alpha<\prod\lambda_\alpha$. In order to prove this inequality, we need to provide an injection ...
3
votes
3answers
29 views

Is the equivalence of the ascending chain condition and the maximum condition equivalent to the axiom of dependent choice?

Assuming the axiom of dependent choice, for a partially ordered set $(X,\le)$, the following statements are equivalent: $X$ fulfils the ascending chain condition, i. e. every chain $x_1\le ...
1
vote
1answer
28 views

Does the relationship between Jonsson Cardinals and Jonsson Algebras require the axiom of choice?

Using Skolem functions, one can see in ZFC that a cardinal $\kappa$ is Jonsson iff there are no Jonsson algebras on $\kappa$. (I.e. every algebra of size $\kappa$ has a proper subalgebra of size ...
2
votes
1answer
76 views

Proving Hahn-Banach theorem directly

Is is possible to find an example of nonreflexive Banach space for which one can establish Hahn-Banach theorem directly (not referring to the axiom of choice)?
0
votes
0answers
23 views

Hyperplanes without Axiom of Choice

For any projective space that contains more than one point, is it possible to prove that it contains a hyperplane without using the Axiom of Choice? It's easy enough to prove that there exists a ...
1
vote
1answer
40 views

Hausdorff Maximal Principle

"Hausdorff's Maximal Principle" says that any partial order P has a maximal chain (chain = linear suborder). It is equivalent to the axiom of choice. If we restrict Hausdorff's Maximal Principle to ...
9
votes
0answers
324 views

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
7
votes
1answer
65 views

Does $\operatorname{card}(X) < \operatorname{card}(Y)$ imply $\operatorname{card}(X^2) < \operatorname{card}(Y^2)$ without choice?

I looked to see if this question was already posted, but did not find anything. Please let me know if this is a duplicate. Assume $X, Y$ are infinite sets such that there is an injection $X \to Y$ ...
6
votes
2answers
81 views

Is the axiom of induction constructively verifiable for a non-standard model of Peano arithmetic?

There exist models of the natural numbers which include infinite numbers. Such models are called non-standard models of arithmetic. (Proof: by the compactness theorem, there exist models of Peano ...
2
votes
1answer
81 views

Bourbaki and AC: How does he proves ZL?

In the book Set theory, Chapter 3 N.Bourbaki, I would like to understand how Bourbaki proves ZL. I wrote the proof. It uses Zermelo's principle (which is okay since they are equivalent), so I tried to ...
4
votes
3answers
1k views

Why can't Axiom of Choice be proven by Rule C

Rule C is appeared in the textbook: Introduction to mathematical logic by Mendelson (Page 81 in the fourth edition). It is said "It is very common in mathematics to reason in the following way. Assume ...
0
votes
2answers
55 views

Choice function without AC in special case [duplicate]

I read the Jech, Set theory, and saw following proposition. (☆) If S is a finite family of nonempty sets, existence of choice function of S can be proved without axiom of choice. I tried to prove ...
2
votes
1answer
41 views

Uncountable dense sets of reals without the axiom of choice

In the absence of AC, can there be an uncountable dense set $S\subset\mathbb R$ such that $S\cap(-\infty,a)$ is countable for each real number $a$? (Of course, since $S$ is a countable union of ...
2
votes
1answer
40 views

If every partitioning of $X$ has a choice function, is $X$ necessarily well-orderable?

Working over the ZF axioms, it's clear that if $X$ is a well-orderable set, then every partitioning of $X$ has a choice function, by choosing the minimum of each cell. Question. Does the converse ...
2
votes
0answers
51 views

Is it really necessary to choose a basis to prove that every element of a comodule is contained in a finite-dimensional subcomodule?

Let $C$ be a coalgebra over a field and $M$ be a $C$-comodule. Then it's well-known that every element of $M$ is contained in a finite-dimensional subcomodule $M' \subset M$. This is for example an ...
0
votes
1answer
25 views

Equivalence of Taylor series and its corresponding function and Axiom for infinite summation

Given a function $f(x)$ with a taylor series expansion, is it valid to say that $$f(x)=\sum_{n=0}^{\infty}\frac{1}{n!}f^{(n)}(a)(x-a)^n$$ for all values of x irrespective of whether the taylor series ...
0
votes
0answers
22 views

Impossibility of constructing a continuum-size linearly independent set in $\Bbb R$ [duplicate]

This is a response to the following exchange at Is there a quick proof as to why the vector space of $\mathbb{R}$ over $\mathbb{Q}$ is infinite-dimensional? [Bill constructs a $\aleph_0$ ...
2
votes
0answers
36 views

Existence of extension of linear map and existence of subspace complement

Great answer by Asaf Karagila to my question leads me to further questions. Let say we deal with vector spaces over $\mathbb{R}.$ Here are three sentences: For every $V$ and its subspace $E\subset ...
1
vote
1answer
46 views

Existence of vector space complement and axiom of choice

Let say we live in the category of vector spaces over $\mathbb{R}$ or $\mathbb{C}.$ Here are three sentences: Axiom of choice Every vector space has a base. For every vector space $V$ and its ...
1
vote
1answer
25 views

Does this proof of $x\in E'\rightarrow \exists \{x_n\}\subseteq E : x_n\to x$ use the axiom of choice?

Let $(X,d)$ be a metric space. Let $E$ be a subset of $X$. If $x$ is a limit point of $E$, then there exists a sequence $x_n\in E$, $n= 1,2,\dots$ such that $x_n\to x$. Proof. Pick ...
1
vote
1answer
47 views

A set that satisfies the hypothesis of Zorn's Lemma

A set $x$ satisfies the hypothesis of Zorn's Lemma. Let $k \in x$. $\textbf{Prove:}$ There is a $z \in x$ such that $z$ is $S$-maximal in $x$ and $z=k \vee kSz $ $\textbf{Attempt:}$ ...
4
votes
1answer
62 views

When can “$j: V \rightarrow M$ is an elementary embedding” be defined in ZF?

This regards elementary embeddings of inner models of set theory. It seems that it is in general "stated" via an axiom schema each member of which states that the class function is elementary with ...
10
votes
2answers
169 views

Can a basis for $\mathbb{R}$ be Borel?

Work in ZF (so no choice). Then it is consistent that there is no (Hamel) basis for $\mathbb{R}$ as a $\mathbb{Q}$-vector space. My question is about models where $\mathbb{R}$ does have a basis, but ...
1
vote
1answer
41 views

Axiom of choice is equivalent to every relation includes a function with the same domain

The axiom of choice asserts that for any set $X$ there exists a function $f : (2^X − \{\emptyset\}) \rightarrow X$ such that for any nonempty $A \subseteq X$, $f(A) \in A$. Show that this is ...
0
votes
1answer
35 views

Bolzano-Weierstrass Theorem Proof Abbott (Ax. of Choice)

In Abbott's Proof of the Bolzano-Weierstrass Theorem, does Abbott use any form of the Axiom of Choice ? I think he is since he chooses an $a_{n_k} \in I_k$ where there are multiple such $a_{n_k}$. ...
1
vote
2answers
49 views

Do the relative consistency results involving the axiom of choice use completeness of FOL?

The proof of the Completeness Theorem for first order logic uses the axiom choice and is a central result in model theory. Chang and Keisler claim that model theory has important applications to set ...
12
votes
0answers
195 views

Spanning the reals with a small set - choicelessly

Working in ZF (so, no choice): is it possible that there is a set of reals $X$ such that $\vert X\vert<\mathbb{R}$, but $X$ generates $\mathbb{R}$ as a subgroup under addition? This seems ...
0
votes
1answer
37 views

Axiom of choice for subsets

I'm trying to solve following problem. Let $A_{i,j}$ be subsets of a set $X$ for $i,j\in \mathbb{N}$. Show that $$\bigcap_{i=0}^\infty \bigcup_{j=0}^\infty A{i,j}=\bigcup_{(a_{i})}\bigcap_{i=0}^\infty ...
1
vote
2answers
51 views

Set Theory - Prove that there is a function $f:\omega\to X$ such that $f(n)<f(n+)$ when $X$ has no maximal element.

Suppose that $X$ is non-empty strictly ordered set, and that $X$ has no maximal element in a sense that for every $x\in X$ there exist $y\in X$ such that $x<y$. By using AC, show that there ...
1
vote
1answer
21 views

Does this minimum exist? Modified Ascoli theorem without countable choice

I am trying to work through a proof on a modification of the ascoli theorem that is supposed to hold in ZF (even without assuming countable choice). My problem is within the part (1) $\Rightarrow$ ...
2
votes
2answers
63 views

Hausdorff Maximal Principle and Axiom of Choice

I need to show that Hausdorff Maximal Principle is equivalent to the Axiom of Choice. Suggested is to use Tukeys Lemma. So far I have that Hausdorff Maximal Principle states that whenever < is a ...
3
votes
1answer
54 views

If $X$ is a metric, then $X$ is compact if and only if $X$ is sequentially compact - axiom of choice usage

I'm going through a proof for the theorem: If $X$ is a metric, then X is compact if and only if X is sequentially compact. I have already posted this here. However this time I'm looking at the ...
2
votes
1answer
68 views

Partitioning an infinite set into two equinumerous subsets

Let $X$ be an infinite set. Then there exists a partition $\lbrace A, B \rbrace$ of $X$ such that $A, B, X$ are equinumerous. Can you prove it in $\mathrm{ZFC}$? Can you prove it in ...
4
votes
0answers
109 views

Theorem's relying on algebraic closures

When working with fields, it's a usual method to work on an algebraic closure of a field to obtain results about that field. In general (i. e. unless you're explicitly considering "well-behaved" ...
1
vote
1answer
42 views

Proof that well-ordering implies choice

Is the following argument correct to show that if every set $S$ can be well-ordered, then for any disjoint indexed family of non-empty sets $(X_{\alpha})_{\alpha \in A}$ there exists a map $f: \{ ...
2
votes
0answers
58 views

A doubt in the proof of “AC implies law of excluded middle”

i dont understand why axiom of choice is needed for the proof, since X is finite and (if i haven't misunderstand anything) we don't need axiom of choice to define a choice function for a finite set. ...
64
votes
8answers
18k views

Can you explain the “Axiom of choice” in simple terms?

As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get. I went to Wikipedia to see what the Axiom of ...
6
votes
1answer
234 views

Well-foundedness of cardinals and the axiom of choice

Without axiom of choice it is not generally true that the class of all cardinal (in this question we consider Scott cardinal rather than cardinals as ordinals) is not well-founded under the ordinary ...
1
vote
0answers
22 views

Is the axiom of countable choice needed for the proof of this special case of equivalence of limit definitions? [duplicate]

In this link, a proof of the equivalence between the $\delta-\epsilon$ definition and the one with the convergent sequences is given. I'm interested in the proof of this theorem simply for the metric ...