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
2answers
134 views

surjective map and cardinality

I work in $\mathsf{ZF}$(without the axiom of choice). Let $A, B$ be sets such that $\left| A \right |$ and $\left|B \right |$ are both defined and let $f \colon A \to B$ a surjective function. Can I ...
2
votes
2answers
63 views

Is the well-ordering in the well-ordering axiom required to be definable?

It is well-known that Axiom of Choice is equivalent to the statement that every set can be well-ordered. Now, to show that $M\models AC$, is it sufficient to show that there exists some well-order of ...
0
votes
4answers
81 views

Intuitive idea of axiom of choice

I'm currently reading a book on set theory and it gives the following formulation of the axiom of choice: Let $X$ be a non-empty set. Then there is a function $g: ...
4
votes
1answer
70 views

Does restricting the range of a collection of nonempty sets to one dominated by the index set require the Axiom of Choice?

The title was difficult to write, because it is hard to say the property I am looking for in words. Here it is in symbols: $$\forall i\in I\ A_i\ne\emptyset\implies\exists X\preceq I\ \forall i\in I\ ...
2
votes
2answers
70 views

The axiom of countable choice.

There seem to be many questions along the same line but none of them seem to be quite what I am asking, so here goes: If a set is countable, then we know that a bijection exists between it and the ...
5
votes
2answers
175 views

Is (countable) AC necessary for a useful theory of Lebesgue measure?

I am working through some notes on the Lebesgue measure, and I noticed that the proof that $\lambda^*$ (the outer measure) is countably sub-additive requires countable choice. (Short version of the ...
1
vote
0answers
41 views

How is it possible that the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic? [duplicate]

If I am not wrong, the well-ordering theorem is strictly stronger than the axiom of choice in second-order logic. I am not sure to understand how this is possible. The reason is that second order ...
9
votes
6answers
501 views

Countable axiom of choice: why you can't prove it from just ZF

This is a follow-up question to the discussion about the finite axiom of choice here. Suppose we have a countable collection of non-empty sets $\{A_1, A_2, A_3,\cdots\}$ Reasoning as indicated in ...
2
votes
1answer
117 views

Axiom of Choice and Zorn's Lemma Equivalence: some intuition

$$ \text{Axiom of Choice $\Rightarrow$ Zorn's Lemma } $$ $$\text{Axiom of Choice $\Leftarrow$ Zorn's Lemma } $$ I feel mathmatically immature to go through these proofs now. My quesiton therefore is: ...
60
votes
6answers
5k views

Why can't you pick socks using coin flips?

I'm teaching myself axiomatic set theory and I'm having some trouble getting my head around the axiom of choice. I (think I) understand what the axiom says, but I don't get why it is so 'contentious', ...
3
votes
2answers
158 views

Can we prove that a quasi-compact locally noetherian space is noetherian without Axiom of Choice?

I will state some definitions to clarify my question. Definition 1 Let $X$ be a topological space. If every open cover of $X$ has a finite subcover, $X$ is called quasi-compact. Definition 2 Let $X$ ...
6
votes
2answers
182 views

How can I explain to my professor his argument invokes the AC?

This is not the standard definition, but my topology professor restricted contexts in metric spaces. Definition An open set $U$ in a metric space $X$ is a subset of $X$ such that the interior ...
5
votes
1answer
146 views

Intuition for “the existence of a basis for every vector space is equivalent to the Axiom of Choice”?

Is there a intuitive way to understand "the existence of a basis for every vector space is equivalent to the Axiom of Choice"?
1
vote
1answer
44 views

What is necessary for having a free ultrafilter?

Without any choice axioms, are there free ultrafilters on the natural numbers? If not, can we prove the existence of ANY free ultrafilters, on any set?
4
votes
1answer
35 views

Do we need AC to prove Principle of Dependent Choices

For any nonempty set $X$ and any entire binary relation $R$ on $X$, there is a sequence $(x_n)$ in $X$ such that $x_nRx_{n+1}$ for each $n \in \mathbb{N}$. (Here an entire binary relation on $X$ is ...
3
votes
2answers
65 views

Assuming the axiom of choice, how to find explicit group structure of a given set

Let us assume the axiom of choice. This is equivalent to every nonempty set having group structure. My question is, given some nonempty set, can we define the binary operator in a constructive way ...
3
votes
1answer
62 views

existence of spanning trees in complete graphs implies choice?

it is known that the existence of spanning trees in arbitrary (connected) graphs implies the Axiom of Choice. I was wondering if this result still holds if we restrict ourselves to spanning trees of ...
2
votes
1answer
85 views

Cardinality of union of pairwise disjoint elements needs choice?

If there is an indexed family $(i\mapsto A_i)_{i\in I}$ of pairwise disjoint sets $A_i$, why do we need choice to show that $$ \left|\textstyle{\bigcup_{i\in I}A_i}\right| = \sum_{i\in I}|A_i|? $$ It ...
2
votes
0answers
67 views

Axiom of choice in proof of Wigner's theorem?

In Appendix A of chapter 2 of "The Quantum Theory of Fields," vol. 1, Weinberg presents a proof of Wigner's theorem: given a symmetry transformation $T$ of rays, one can extend this to a symmetry ...
4
votes
2answers
129 views

The regularity of successor cardinal

I was looking at two different proofs of the fact that successor cardinals are regular. It struck me as odd that both proofs used AC. Looking at the concepts involved in defining cofinality I feel as ...
5
votes
3answers
241 views

Uncountable Cardinals without AC

I am doing an exercise, proving that without AC or Replacement that there are uncountable cardinals. As a point of reference I looked at the proof in Kunen's "The Foundations of Mathematics" that ...
1
vote
0answers
122 views

Set Theory , Konig's Lemma and Infinite Graph Theory

I am trying to understand the basics of Infinite Graph theory and various preconditions in Konig's Lemma. The texts I have studied tend to use the Axiom of Choice (usually Zorn's Lemma) as a tool of ...
0
votes
1answer
232 views

Infinite dimensional vector space. Linearly independent subsets and spanning subsets

This question is a follow up to this question: The dimension of the real continuous functions as a vector space over $\mathbb{R}$ is not countable? I realized that the answer I accepted used an ...
0
votes
1answer
118 views

Noetherianess of a locally noetherian affine scheme without axiom of choice

I use the definition of a noetherian ring given by Qiaochu in this: A commutative ring is noetherian if, for any nonempty collection of ideals $\mathcal{I}$, there is some $I \in \mathcal{I}$ which is ...
6
votes
2answers
290 views

Understanding Zorn's lemma.

A lot of authors assume Zorn's lemma. I am told it is not an obvious mathematical fact, but I am having problems understanding why that is. Zorn's lemma states that if every chain in a partially ...
0
votes
1answer
101 views

Axiom of choice and an example of a Well-ordered $\Bbb R$

From the axiom of choice we get that every set can be ordered in a way that will make it a well ordered set, including $\Bbb R$. However, since the ordinal of such a well-ordered set of $\Bbb R$ will ...
2
votes
1answer
75 views

A well ordering on $\mathbb{R}$ and bigger sets

Consider the set of sequences $S = \{f:\mathbb{N}\to\mathbb{N}\}$, define an order on $S$ by the following: Based on the well-ordering of $\mathbb{N}$ and induction, either $f_1 = f_2$ or there is a ...
1
vote
1answer
57 views

Riemann Integration and the Axiom of Choice

In Riemann's definition of integration in $[a,b]$, a step in the process consists of choosing one point from each part of the "current" partition for further a partition, and again choose one point ...
1
vote
1answer
44 views

Zorn's lemma problem

Let $n$ be a positive natural number. Prove using Zorn's lemma that there is a set A of points in the plane that satisfies: 1. Any line in the plane does not contain $n+1$ points of A. 2. For every ...
0
votes
1answer
54 views

On Counted Languages

In my recent question on Godel Completeness I mentioned that there was a related question I wanted to ask, but would keep separate. I have been recently studying "non-well ordered sets" and Chapter 7 ...
8
votes
2answers
333 views

Constructiveness of Proof of Gödel's Completeness Theorem

As a mathematician interested in novel applications I am trying to gain a deeper understanding of (the non-constructiveness of) Gödel's Completeness Theorem and have recently studying two texts: ...
3
votes
1answer
79 views

When do surjections split in ZF? Two surjections imply bijection?

We have that the Axiom of Choice is equivalent to the principle that every surjection has a right inverse. However, without the Axiom of Choice we can determine for some $X$ that $X\succeq Y\implies ...
5
votes
2answers
185 views

Which sets are well-orderable without Axiom of Choice?

I know that, assuming Axiom of Choice, every set is well-orderable. I know also that the assertion that $\mathbb{R}$ is NOT well-orderable is consistent with ZF. How can I find other sets such that, ...
2
votes
1answer
34 views

Existence of transversals of subgroups implies axiom of choice?

If $G$ is a group and $H\leq G$ is a subgroup, then a transversal of $H$ is a subset $T\subseteq G$ which meets every coset of $H$ in a unique point. The axiom of choice clearly implies that every ...
3
votes
1answer
77 views

Jech's axiom of choice, problem 2 first chapter

I have a question stemming from Jech's book on the axiom of choice., chapter 1 exercise 2. We are asked to show that a family of sets of natural numbers has a choice function. Now the version of the ...
2
votes
1answer
60 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 ...
2
votes
0answers
201 views

Hahn-Banach via Hamel Basis

my question for tonight: Is there a proof for Hahn-Banach using a Hamel Basis? I know, the proof for existence of Hamel Bases uses already Axiom of Choice, but I'd like to apply this without refering ...
2
votes
1answer
180 views

Statements equivalent to the Axiom of Choice

The Axiom of Choice reads: The product of a collection of non-empty sets is non-empty. As you know well, this axiom is equivalent to many other statements. A few examples (probably the most ...
1
vote
2answers
154 views

does the mean value theorem implicitly assume the axiom of choice?

in real analysis, including some of the theory of transcendental numbers, the mean value theorem is an essential tool. I was wondering if its dependence on the existential quantifier, $\exists$, at ...
2
votes
3answers
421 views

Axiom of Choice and Cartesian Products

According to Wikipedia one formulation of AC is The Cartesian product of any family of nonempty sets is nonempty. If I consider an cartesian product $\prod_{i} X_i$ of nonempty sets $X_i$, then ...
1
vote
1answer
71 views

Kuratowski-Zorn Lemma with pre-order (quasi-order, proset) instead poset?

What would happen if we would use pre-order (there is no weak-antisymmetry, only reflexivity and transitivity) in Kuratowski-Zorn Lemma instead of partial order? Suppose that we have set P which ...
9
votes
1answer
114 views

Zorn's lemma in categorical language

The axiom of choice, which is equivalent to Zorn's Lemmma, has a nice categorical "translation": in the category of sets, every epi is a retraction. So the axiom of choice says something about the ...
7
votes
2answers
188 views

Plausibility argument for Zorn's Lemma

In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a ...
1
vote
1answer
60 views

Multiple context available for the AC?

I am surprised at the language used in connection with the axiom of choice. From the answer to a question a made (which turned out to be duplicate) about involvement of AC in Wiles’ proof of Fermat’s ...
1
vote
2answers
114 views

Set Theory and Zorn Lemma

Prove that there is a set $B\subseteq P(\mathbb N)$ such that for all $n\in \mathbb N:\mathbb N- n\in B$, every finite intersection of elements in B is not empty and for all $C\subseteq\mathbb N$ such ...
8
votes
2answers
88 views

How should one think about results that depend on AC?

I just encountered this: "(Theorem of A. H. Stone) Every metric space is paracompact... Existing proofs of this require the axiom of choice... It has been shown that neither ZF theory nor ZF ...
5
votes
1answer
90 views

Does the existence of products in the category of sets imply the Axiom of Choice?

If for every family $(X_i)_{i\in I}$ of sets, there exists a categorical product in the category $\mathbf{Set}$ of sets, does this imply that the set-theoretic construction $\left\{(x_i)_{i\in ...
6
votes
1answer
245 views

Real guessing puzzle

Allow me to propose a modification of a previously asked puzzle. I would like to replace 100 in that puzzle by $\omega$ and replace $99$ by "all but one". A version of the puzzle was also discussed on ...
8
votes
1answer
274 views

Axiom of Choice - Type Theory (Proof)

Background In Intuitionistic Type Theory (p. 27-28), Martin Löf provides a proof of the axiom of choice that is constructively valid. This version is considerably weaker than the ordinary set theory ...
1
vote
2answers
193 views

The Axiom of choice

I'm a little lost with this proof: If every set is equipotent to an ordinal, then we have the axiom of choice And I want to know if someone can help or maybe give me a hint of how to proceed.