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

2
votes
1answer
28 views

If $a\sqcup b$ and $a\times b$ biject, then $b$ either injects or surjects in-/onto $a$

Let $a$ and $b$ be sets such that there is a bijection $a\sqcup b\to a\times b$. Show, without assuming the Axiom of Choice, that there is either a surjection $b\to a$ or an injection $b\to a$. ...
0
votes
2answers
47 views

Axiom of Choice and LEFT inverse [duplicate]

I am aware of why the Axiom of Choice is equivalent to the the statement that every surjection splits. However, I don't see why we don't also need AC to show that every injection splits. In ...
2
votes
1answer
59 views

Sum of measurable functions is measurable: countable choice required?

The standard proof that the sum of measurable functions is measurable uses countable choice, via the countable subadditivity of outer measure ($\implies$ measurable sets are closed under countable ...
1
vote
0answers
49 views

A classification of the types of poset extensions that raise local-global principle is equivelent to the axiom of choice?

EDIT: Completely overhauled the question, remove category theory from it (stated in plain set theory): The original question Adding relations to a partial order Let $X$ be a set and let $P: Pow(X) ...
2
votes
1answer
32 views

Proving cardinality of coproduct presentation is unique without choice?

The definition of an extensive category immediately implies that given two coproduct decompositions indexed by sets of equal cardinality, if the coproduct objects are isomorphic compatibly with their ...
2
votes
1answer
39 views

Can the unit interval be the disjoint union of countably many “super-dense” parts?

I'm curious about this question in the case where $f$ is not necessarily measurable. I think what it comes down to is this: Is there an $\varepsilon<1$ and a partition of $[0,1]$ in countably ...
1
vote
1answer
52 views

Need this transfinite construction reach a closed set in the absence of the Axiom of Choice? Or Hartogs' theorem?

In this question I'm primarily concerned with the workings of a set theory that lacks both Foundation and Choice. Given a set $X$ and a function $\sigma:\mathcal{P}(X)\to\mathcal{P}(X)$, we have a ...
6
votes
2answers
74 views

Original proof of Zorn's Lemma

On the wiki page for Zorn's Lemma it says that this lemma was Proved by Kuratowski in 1922 and independently by Zorn in 1935 but then it says: Zorn's lemma is equivalent to the well-ordering ...
14
votes
3answers
1k views

What is an example of two sets which cannot be compared?

In set theory, if we do not assume the Axiom of Choice, we cannot prove the Trichotomy Law between cardinals. That is, we cannot prove that for any two sets, there exists an injection from one to the ...
22
votes
2answers
2k views

Why do people accept the axiom of choice given the well ordering principle?

We know without any doubt that the axiom of choice implies (in fact is equivalent to) the well ordering principle. The well ordering principle can't be true! If we take the open interval $(0,1)$ for ...
1
vote
1answer
50 views

Non-principal ultrafilters on a set [duplicate]

Let $X$ be a set. If $X$ is finite then all ultrafilters on $X$ are principal, i.e. have the form $\{A \subseteq X : x \in A\}$ for some $x\in X$. But now suppose $X$ is infinite, say $X=\mathbb N$. ...
4
votes
1answer
275 views

Soft Question: Why does the Axiom of Choice lead to the weirdest constructions?

I hope this is not too off-topic / soft for math.stackexchange. My basic question is: why does the Axiom of Choice allow for some of the weirdest constructions in math? I'll make a list of the weird ...
0
votes
1answer
49 views

Are there any large cardinals that are not ordinals? [closed]

In ZF, are there any useful large cardinal that cannot be well-ordered? I think that some of the partition cardinals are that way, since with AC, we cannot have $\kappa \to (\omega)^{\omega}$. Are ...
2
votes
1answer
39 views

Axiom of Choice implies the Well-Ordering Principle

I am trying to understand the proof of this implication we were taught in my set theory module. I cannot seem to tie it together with the final line of the argument... We used this lemma: Given ...
1
vote
2answers
36 views

Can every poset be toplogically sorted?

A partial ordering $\preceq'$ on $S$ is said to be compatible with another partial ordering $\preceq$ if for all $a,b,\in S$, $$ a \preceq b \Rightarrow a \preceq' b$$ Given a poset $(S, \preceq)$, ...
3
votes
1answer
54 views

The well-ordering principle implies Zorn's Lemma

I have read and understood proofs for each implication between $AC$, $ZL$, $WO$ except this one. These proofs need about 10 lines each. Can someone share a neat, hopefully short, proof for $WO\implies ...
1
vote
1answer
40 views

Proving the Axiom of Choice is equalivalent to the statement “If $A$ can be well-ordered, then so can $\mathcal{P}(A)$.”

I am still not completely confident in proving equivalence between the Axiom of Choice and statements such as the one posed in the title, so I want to make sure that I am on the right track. So ...
2
votes
1answer
53 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 ...
0
votes
2answers
51 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 ...
0
votes
1answer
98 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 ...
1
vote
1answer
43 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
36 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
40 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 ...
2
votes
1answer
64 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
18 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
44 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
31 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
30 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 ...
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 ...
2
votes
1answer
83 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)?
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 ...
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
90 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 ...
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 ...
2
votes
1answer
43 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 ...
0
votes
2answers
56 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

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 ...
0
votes
1answer
26 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 ...
2
votes
0answers
52 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
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
37 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
48 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
48 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
63 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 ...
0
votes
1answer
36 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
1answer
48 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 ...
10
votes
2answers
177 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
2answers
53 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
250 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 ...