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
1answer
40 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
31 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
62 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
58 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
56 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
56 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
123 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
228 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 ...
0
votes
0answers
101 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
144 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
115 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
215 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
92 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
67 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
53 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
40 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
49 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 ...
6
votes
2answers
268 views

Constructiveness of Proof of Godel's Completeness Theorem

As a mathematician interested in novel applications I am trying to gain a deeper understanding of (the non-constructiveness of) Godel's Completeness Theorem and have recently studying two texts: ...
3
votes
1answer
60 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
165 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
30 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
68 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
58 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
186 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
139 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
121 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
295 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
60 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
90 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
173 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
59 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
104 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 ...
0
votes
0answers
143 views

Axiom of choice required? [duplicate]

I read that Wiles's proof of Fermat’s Last Theorem has been presented in a heavily set-theoretic framework. (The fact that is hasn’t been challenged is given as evidence that set-theoretic methods ...
8
votes
2answers
87 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
86 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
210 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
247 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
157 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.
1
vote
1answer
64 views

If AC is false , is this statement about the halting problem true?

Assume AC is false. (AC = axiom of choice ) Let $n,m$ be positive integers. Let $f: \Bbb N \rightarrow \Bbb N$ and $f(m)=m$. Let $g(n,m)=1$ if the iterations $f(n),f(f(n)),...$ converges to $m$. ...
1
vote
0answers
46 views

Is there a connection between contravariant functors and the axiom of choice?

Given that both can be seen as talking about reversing arrows between two objects: Is there a connection between contravariant functors and the axiom of choice? I'm initially motivated geometrical ...
4
votes
2answers
145 views

Existence of surjection implies existence of injection? [duplicate]

Let $A$ and $B$ be sets. If there exists a surjection $f : A \to B$ then there exists an injection $g : B \to A$. Proof: given $b \in B$ select an element $a \in f^{-1}(b)$. Denote this element by ...
6
votes
1answer
92 views

If a filter has a unique ultrafilter extending it, then it is that ultrafilter (prove without $\sf{AC}$)

I am not certain if $\sf AC$ (or more conservatively, $\sf UF=$ there is an ultrafilter extending any given filter) is necessary to prove the following statement: For filters $F,G$ with $\bigcup ...
1
vote
1answer
74 views

$\aleph(X) < \aleph(\mathcal{P}(\mathcal{P}(\mathcal{P}(X))))$

Prove: $\aleph(X) < \aleph(\mathcal{P}(\mathcal{P}(\mathcal{P}(X))))$ With $W(X)=\{\langle A,R\rangle: A \in \mathcal{P} (X),R \in \mathcal{P}(X \times X)$ and $ R $ wellorders $ A \}$ And ...
4
votes
2answers
101 views

Zorn's Lemma and Injective Modules

In my study of injective modules over commutative rings, i noticed that Zorn's Lemma is often employed in the proofs. Here are three examples: 1) Baer's Criterion 2) the characterization of injective ...
0
votes
0answers
44 views

A theorem of Tarski [duplicate]

A theorem of Tarski says that if it is so that, for all infinite sets $X$, $\;\operatorname{card}(X^2)=\operatorname{card}(X),\,$ then the axiom of choice applies. I would like to see a proof of ...
1
vote
1answer
48 views

What does the Axiom of Choice have to do with right inversibility?

I have encountered an exercise that asks to prove that, these two statements are equivalent: every surjective function has a right inverse. Axiom of choice. Definition: Given a function $f$, we ...
3
votes
2answers
135 views

Canonical Vitali set

The axiom of choice implies that there is a subset $E$ of $\mathbb R$ that are Vitali sets : this means that $E$ is a transversal with respect to the additive subgroup $\mathbb Q$ of $\mathbb R$, ...
5
votes
1answer
160 views

Compact metric spaces is second countable and axiom of countable choice

Why we need axiom of countable choice to prove following theorem: every compact metric spaces is second countable? In which step it's "hidden"? Thank you for any help.
1
vote
1answer
94 views

Axiom of choice and vector space bases

Is this: for every vector space $V$, if $B$ and $C$ are bases of $V$, then there is a bijection: $B\to C$ iff the axiom of choice holds true? Or, perhaps, if axiom of choice is replaced by ...
3
votes
1answer
104 views

Is there anything wrong with this use of the axiom of choice?

I have a proof of the following theorem: Let A be a finite set and X be a perfectly normal topological space, and let $\{(A,\succsim_x): x\in X\}$ be a family of binary relations on $A$ satisfying ...