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$. ...
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
1answer
29 views

A $\sigma$-algebra equivalent to the Lebesgue algebra under CC

Working in $\sf ZF$, is there a natural definition of an algebra $\Sigma$ with the following properties: $\Sigma$ is a $\sigma$-algebra on $\Bbb R$, i.e. it is closed under complement and countable ...
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 ...
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 ...
25
votes
4answers
906 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of ...
10
votes
4answers
352 views

Countable choice and term extraction

The constructive Axiom of Countable Choice (ACC) is widely accepted due to its computational content. It states that: $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: ...
2
votes
1answer
41 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 ...
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 ...
8
votes
2answers
688 views

No uncountable ordinals without the axiom of choice?

In Uncountable ordinals without power set axiom Francois Dorais explains that without the Power-set Axiom we cannot prove the existence of uncountable ordinals. I am guess that the power set of an ...
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 ...
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 ...
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 ...
44
votes
2answers
7k views

Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
4
votes
1answer
276 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 ...
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$. ...
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 ...
2
votes
1answer
54 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 ...
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 ...
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 ...
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
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
44 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 ...
10
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 ...
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 ...
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)?
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
91 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
82 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
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
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 ...
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 ...
2
votes
0answers
53 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
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 ...
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 ...