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
47 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
55 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 ...
9
votes
2answers
357 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
91 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
194 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
35 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
83 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
61 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
206 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
194 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
161 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
446 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
73 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 ...
10
votes
1answer
123 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
194 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
62 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
119 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
93 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
252 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
282 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
198 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
75 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
198 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
111 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
82 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 ...
6
votes
2answers
154 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 ...
1
vote
1answer
51 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
142 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
305 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
115 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
107 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 ...
2
votes
1answer
53 views

well ordering principle implies Zorn's Lemma

In here: Proving that well ordering principle implies Zorn's Lemma. I asked how to finish a proof of this statement. After a few helpful remarks, I think I have managed to finish it. What do you ...
4
votes
1answer
121 views

Proving that well ordering principle implies Zorn's Lemma.

I am trying to prove that well ordering principle implies Zorn's Lemma. I think that I'm close but don't quite know to make the last step of my proof. Here is what I wrote so far: Given that on every ...
7
votes
1answer
136 views

Can Tarski's circle squaring problem be solved with measurable sets and/or without the Axiom of Choice?

Tarski asked whether a disk can be decomposed into finitely many pieces which can be rearranged into a square (necessarily of the same area by the failure of the Banach-Tarski paradox in two ...
4
votes
2answers
79 views

Does the dualizing process on vector spaces necessarily terminate?

It's well-known (assuming the axiom of choice) that the inclusion $\ell^1 \subset (\ell^1)^{**}$ is proper as a simple corollary of the Hahn-Banach theorem. But is this the end of the dualizing ...
9
votes
3answers
145 views

Can $\mathbb{R}$ be written as an ascending union of proper additive subgroups?

Can the group $\mathbb{R}$ be written as countable ascending union of proper subgroups? (i.e. does there exists a series of proper subgroups $H_1\leq H_2\leq \cdots $ such that $\cup ...
6
votes
1answer
219 views

Can we prove that every ordered space is normal without choice?

In ZFC, every linear ordered space respect to the order topology is completely normal. I saw the this proof and proof of this statement in the book "Counterexamples of topology" (Example 39). But as I ...
3
votes
1answer
76 views

The union of a countable set of countable sets is countable

Here is the proof provided in my lecture notes: Let $A = \{B_n | n < \omega =\mathbb{N}\}.$ Assume each $B_n$ is countable. For each $n < \omega,$ let $E_n$ be set of all bijections between ...
1
vote
1answer
79 views

Relative Consistency proof for the Axiom of Choice

I've been reading about relative consistency proofs in Kunen's latest Set Theory text and going over which Axioms hold in certain classes. To get my hands dirty, I've been working on an exercise that ...
1
vote
1answer
65 views

Extending a Filter in a Well-Ordered Boolean Algebra to an Ultrafilter WITHOUT the Axiom of Choice

Hypothesis: Let $B$ be a well-ordered boolean algebra and let $F \subseteq B$ be a filter on $B$. Goal: Show that $F$ can be extended to an ultrafilter without the axiom of choice (or any equivalent ...
4
votes
1answer
68 views

Inductive definition with choice for sequence

In topology there is a very common way to define a sequence. This usually go something like: "Define $\{z_{n}\}$ to be a sequence such that $z_{0}$ is <blah blah blah>, and $z_{n}$ is such that ...
0
votes
2answers
73 views

Do we need the axiom of choice in here?

Axiom of choice: Given $\mathbb{F}$ is a set of non-empty sets. Then, there is a function $f$ with $\text{Dom}(f)=\mathbb{F}$ such that, for every $A \in \mathbb{F}$, $f(A) \in A$. The ...
2
votes
5answers
160 views

Axiom of countable choice

I apologize in advance for my neophytic question. Let $(A_n)$ be a countable family of disjoint sets. Why is it not possible define a sequence $(x_n)$ with $x_n\in A_n$ using recursion? It seems clear ...
4
votes
2answers
355 views

Well-ordering theorem and second-order logic

I am confused by this sentence in the Wikipedia article for "Well-ordering theorem": ...the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with ...
2
votes
4answers
149 views

Boolean prime ideal theorem and the axiom of choice

The Boolean prime ideal theorem is strictly stronger than ZF, and strictly weaker than ZFC. I'm looking for nice examples (like the existence of non-measurable set) that request at least that theorem ...
4
votes
4answers
138 views

Proving that without the axiom of choice there is a set with an accumulation point that isn'tthe limit of a convergeant sequence

I've been reading the simple parts of Thomas Jech's book on the Axiom of Choice and came across the following proof on page 141. The proof assumes a mathematical model without the axiom of choice. ...
3
votes
2answers
195 views

Why is the measure of the reals not zero?

I have followed the argument that rationals, being countable and ordered, can be covered by a convergent sequence of decreasing intervals. I am trying to understand why the same argument can’t be ...
3
votes
2answers
124 views

Proving Zermelo's Theorem implies the Axiom of Choice

I thought it would be fun to try and prove this. It turned out to be pretty simply and maybe too simple so I was wondering if anybody could verify if this proof is correct. Suppose we have a family ...