Questions tagged [axiom-of-choice]

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. Use this tag in tandem with (set-theory).

Filter by
Sorted by
Tagged with
1
vote
1answer
29 views

Applications of the axiom of choice to non-existence proofs

I've been thinking about Monsky's Theorem that it is impossible to partition a square into an odd number of triangles of equal area. The proof depends on a theorem of Chevalley to extend the $2$-adic ...
2
votes
1answer
47 views

$\mathsf{AC}_{\omega_1}$ and $L(\mathbb R)$

Assume that the Axiom of Choice holds in $V$, the von Neumann universe. As Andreas Blass explained, $\mathsf{DC}$ holds in $L(\mathbb R)$. Is this the case for $\mathsf{AC}_{\omega_1}$ too? That ...
1
vote
1answer
35 views

Why is AC needed to assert the existence of some infinite sets but not others?

In my undergraduate review for topology, we use axiom of choice to prove a result about the surjectivity of projection mappings. I have also read through a number of posts about AC on the site, and ...
5
votes
0answers
64 views

Čech functions and the axiom of choice [migrated]

A Čech closure function on $\omega$ is a function $\varphi:\mathcal P(\omega)\to\mathcal P(\omega)$ such that (i) $X\subseteq\varphi(X)$ for all $X\subseteq\omega$, (ii) $\varphi(\emptyset)=\emptyset$,...
7
votes
1answer
89 views

On some Hahn-Banach equivalents

This question is about some equivalents of the Hahn-Banach theorem in $\textsf{ZF}$ set theory. As far as I know, the definitive reference for this sort of thing is Howard & Rubin's Consequences ...
0
votes
1answer
46 views

Is there a way of proving that if $A$ is an infinite set and $x\not\in A$ then $|A|=|A\cup\{x\}|$ without relying on the axiom of choice. [duplicate]

Let $A$ be an arbitrary infinite set and $x\not\in A$. I want to find a bijection between $A$ and $A\cup\{x\}$. Proof 1: A possible proof of that is to play with cardinal numbers as follows: Let $\...
2
votes
3answers
74 views

Would mathematics based on lists obviate the need for the axiom of choice?

I'm trying to wrap my head around the axiom of choice and its equivalent well-ordering theorem. Imagine a mathematics founded on ordered lists rather than sets. So by construction, wouldn't every ...
4
votes
1answer
85 views

Determinacy and Choice

I know that Kechris proved $$\text{Con}(\text{ZF} + \text{AD})\Rightarrow \text{Con}(\text{ZF} + \text{AD} + \text{DC})$$ And that $\text{DC}$ and $\text{AC}_\omega$ are independent from $\text{AD}$, ...
5
votes
2answers
149 views

Encounters with Zorn's lemma early in study of mathematics

Many mathematics students encounter the axiom of choice relatively early in their studies. For example, they see the claim that if we have a surjection $g\colon B\to A$, then there is one sided ...
1
vote
1answer
51 views

Nowhere dense sets and metric space [closed]

Excuse me can you see this question Prove that in a metric space the frontier of an open set is the set of accumulation points of a discrete set ... It wrote that " this requires the axioms of choice ...
0
votes
0answers
35 views

What is the strength of a stationary costationary subset of $\omega_1$? [duplicate]

It is known that it consistent with $\mathsf{ZF}$ that there are no disjoint stationary subsets of $\omega_1$. Is the assertion "there exist a stationary costationary subset of $\omega_1$" ...
2
votes
0answers
55 views

On Axiom of Choice and the principle of Explosion (ex contradictione sequitur quodlibet)

My question is on the relation of this two principles. For instance, in the of Intuitionistic set theory we can prove Zorns Lemma (but Zorns Lemma will not be equivalent to the axiom of choice, since ...
4
votes
1answer
78 views

Not Assuming Choice, Nilradical Not Equal to Intersection of Prime Ideals

Every proof I’ve seen that, for a commutative ring $A$, $$\newcommand{\Nil}{\operatorname{Nil}}\Nil(A)=\bigcap_{x\in \newcommand{\Spec}{\operatorname{Spec}}\Spec(A)}x$$ assumes Zorn’s lemma. So my ...
3
votes
1answer
69 views

Dependent choice and $L(\mathbb R)$.

I am curious what is the relation between the inner model $L(\mathbb R)$ and the axiom of dependent choice $\mathsf{DC}$. Do we have $$L(\mathbb R)\models \mathsf{DC},$$ when $V\models \mathsf{DC}$?
2
votes
1answer
43 views

How much choice is needed to prove that every compact metric space is a continuous image of the Cantor set?

Having inspected the proof of the fact that for every compact metric space $X$ there exists a continuous surjection from $\{0,1\}^{\mathbb N}$ onto $X$, it looks to me it is a theorem of ZF + DC (...
9
votes
2answers
116 views

How much choice follows from the existence of derangement?

We can show that every set has a derangement (that is, a bijection $f$ from itself to itself such that $f(x)\neq x$ for all $x$) if we assume the axiom of choice. In fact, the full axiom of choice is ...
1
vote
2answers
44 views

If there exists a surjection $f:A\to B$, can you construct an injection $f:B\to P(A)$? [duplicate]

With the axiom of choice this is trivial, but is there any way to construct this injection explicitly in the ZF system?
2
votes
1answer
59 views

Axiom of Choice and fullness of the class of terms of the forcing language

It is well-known that when doing forcing over some ground model $M$, if we assume the Axiom of Choice in $M$, then the class of terms of the language of forcing has the property that for any $p \in \...
2
votes
0answers
36 views

Are finite projective modules locally free without axiom of choice?

Let $A$ be a commutative ring. An $A$-module $M$ is called a finite projective module if there exists a module $N$ and a natural number $n\in\mathbb N$ such that $M\oplus N\cong A^n$, and an $A$-...
1
vote
2answers
77 views

If $x$ is a set of cardinality $\kappa$ and $\lambda<\kappa$, do we need the axiom of choice to prove that there is a subset of $x$ of size $\lambda$?

Suppose we have a set $x$ of cardinality $\kappa$. If $\lambda$ is a cardinal lower then $k$, normally we can say that there exists a subset $y$ of $x$ of size $\lambda$. To prove this - I believe - ...
8
votes
2answers
163 views

There is a $\Sigma^1_1$ universal set and this is not Borel. Where did we use the axiom of choice?

It is well-known that there is a $\boldsymbol{\Sigma}^1_1$ universal set $U \subset \omega^\omega \times \omega^\omega$. That is, there is a $\boldsymbol{\Sigma}^1_1$ subset $U$ of $\omega^\omega \...
0
votes
1answer
32 views

Am I using the axiom of choice in the measure-theory proof?

Since I started to learn a bit about set theory, I am paying more attention as where I am or not using the axiom of choice in analysis. I had a small exercise about measure that asks me to show that ...
0
votes
3answers
55 views

Bypassing the axiom of choice when there are infinitely many sets but there are constraints on the sets

In the accepted response in this thread, Asaf Karagila wrote that Note that it is perfectly possible to choose from infinitely many sets without the axiom of choice under a severe constraint that ...
0
votes
0answers
24 views

Strange applications of the Axiom of Choice [duplicate]

I've heard a lot of differing opinions about the Axiom of Choice (AOC): some don't mind it, some hate it. Yet, so far every time I've seen the axiom of choice being applied, it doesn't seem too crazy ...
4
votes
1answer
43 views

How can I prove that every infinite set has a countably infinite subset using only the Axiom of Countable Choice?

I'm trying to prove that any infinite set $X$ contains a countable (denumerable) set. Please note that I want to prove this using countable choice. All I ccould show by induction is that for each $n\...
2
votes
2answers
156 views

Why does axiom of choice not imply the set of real numbers is countable?

The axiom of choice implies all sets can be well ordered. If that is true, you can well order the set of real numbers and the set of the integers. Now, why can one not just pair the set of real ...
2
votes
1answer
39 views

Separating a point and a compact subset in a Hausdorff space without Choice

Let $K$ be a compact subset of a Hausdorff space $X$, and $x \not \in K$. Then there are disjoint open sets $U,V$ with $K \subseteq U$ and $x \in V$. The proof of this result that I have seen uses ...
2
votes
1answer
48 views

What Choice Axiom allows you to choose from a set-sized collection of Classes?

The standard axiom of choice states that every set of non-empty sets has a choice function. And the axiom of global choice states that every class of non-empty sets has a choice function. But I’m ...
1
vote
1answer
65 views

How to show that $f:\mathbb{R}\to \mathbb{R}$ defined as $f(x)=x$ can be decomposed as a sum of two periodic functions?

I read somewhere that the proof depends on AC. But how about showing it explicitly i.e finding an explicit example that satisfies this? I would like to see both proofs, the one that depends on AC ...
2
votes
1answer
52 views

Is there a specific term for a function that exists solely as a set of ordered pairs and cannot be described by a mathematical formula?

I've been reading about the Axiom of Choice, and my current understanding is that we can assert a choice function exists even in cases where it may be impossible to construct a deterministic formula ...
0
votes
0answers
22 views

Let A be an infinite set. Show that there exists a proper subset B of A such that |A| = |B|. Does your proof use the Axiom of Choice? [duplicate]

Let A be an infinite set. Show that there exists a proper subset B of A such that |A| = |B|. Does your proof use the Axiom of Choice? Any ideas on how to prove this?
0
votes
1answer
55 views

Question on a step of “A Simple Proof of Zorn's Lemma” by Lewin

I'm reading Jonathan Lewin's "A Simple Proof of Zorn's Lemma" and cannot see the justification for one statement (which I've labeled Lemma 3 below). I'll summarize the proof below (adding a few lemma ...
8
votes
2answers
154 views

(Long) Detailed Proof of Kőnig's Lemma (Explicit, Down to Axiom of Choice)

Kőnig's Lemma states that in an infinite, locally finite, connected graph $G$, there exists an infinite one-way path (a ray). The proof of it in my graph theory book (Introduction to Graph Theory, 4th ...
1
vote
0answers
73 views

Non-uniqueness of (Galerkin) approximations and convergent subsequences without the axiom of choice?

Suppose I have an equation in some reflexive separable Banach space $X$: $$Au=f$$ for given data $f$ and $A\colon X \to X^*$ a pseudo-monotone operator. Existence can be proved via Galerkin ...
4
votes
1answer
52 views

Relationship between different versions of AoC in the context of a specific set (in ZF)

We can show that various versions of AoC, restricted to a specific set, are equivalent. For example, the following are equivalent for any set, $X$ (in ZF): [$A_X$] $X$ is well-orderable [$B_X$] ...
2
votes
0answers
62 views

Explicit isomorphism between $L^\infty[0,1]$ and its hyperplanes

The Banach space $L^\infty[0,1]$ is isomorphic to all its hyperplanes (closed linear subspaces of codimension one). One way of seeing this is the following: all hyperplanes of a Banach space are ...
1
vote
1answer
42 views

Understanding where my naive attempt to prove Countable Choice out of Finite Choice fails

I am aware of this and this topic, but I would like to receive a clarification concerning the foregoing naive attempt to prove Countable Choice, to see if I understood properly the question. Assume ...
1
vote
0answers
31 views

Is the axiom of choice necessary for “a set is open iff it is a neighborhood of all its points”? [duplicate]

Note: by neighborhood of $x$ we mean a set $N$ s.t. there exists open $U$ s.t. $x \in U \subseteq N$. We only care about the "if" as the "only if" is trivial. The usual proof goes as follows. ...
1
vote
0answers
23 views

Exercise about the axiom of choice [duplicate]

Prove that the following statements are equivalent: If $A$ is a non empty set, there exists a function $f:\mathcal{P}(A) \setminus \{\emptyset\} \rightarrow A$ such that $f(X) \in X$ for every $X \in ...
0
votes
1answer
45 views

Understanding typical use of Zorn's lemma

I am taking a ring theory class (the class is online...), and we just proved that every ring has a maximal ideal. Anyone who is familiar with the proof knows that in order to prove it, we have to use ...
0
votes
0answers
46 views

Does $\operatorname{card} \operatorname{ran} f \leq \operatorname{card} \operatorname{dom} f$ imply choice? [duplicate]

I am considering the following statement: If $f$ is a function, then $\operatorname{card} \operatorname{ran} f \leq \operatorname{card} \operatorname{dom} f$. This can be proved using the axiom of ...
3
votes
1answer
60 views

A question about Dedekind-infinite sets and Peano natural integers.

I've doubt about Dedekind-infinite sets, sets which are in bijection with a proper part, in the ZF axiomatic framework, without Axiom of Choice. Assume a Dedekind-infinite set X exists. Then it can ...
5
votes
1answer
53 views

Basic Fraenkel model in Jech's “The Axiom of Choice”

I'm reading about the basic Fraenkel permutation model in Jech's The Axiom of Choice, Section 4.3. We are working in ZF + Atoms + Axiom of Choice. $A$ is the set of atoms, assumed here to be ...
1
vote
1answer
62 views

Is well-ordered Dedekind-finite set finite?

In $ZF$ without any form of $AC$, is it true the following statement: "A well-ordered set $S$ is Dedekind-infinite iff it is finite" ? I know that a finite set is always Dedekind-finite, and that if $...
2
votes
1answer
66 views

Maximal principles

Prove that Hausdorff's Maximal Principle is equivalent to the following: If $(A,\preceq)$ is a partially ordered set and $B$ is a chain of $A$, then $A$ has a maximal chain $\mathfrak{C}$ such that $B\...
4
votes
1answer
46 views

Does proving that closed subset of Polish space is Polish require axiom of countable choice?

Let $C$ be a closed subset of polish space $P$. It is trivial that $C$ is also completely metrizable, but how do we prove that $C$ is separable? I came up with this method: We can prove that separable ...
3
votes
1answer
62 views

$AC_\omega(^\omega\omega)$ implies that $\omega_1$ is regular.

So this statement was something I had skipped before, and I tried to prove it, but I am still not sure if I am sneaking in some choice somewhere, so I would be glad if anyone could point an error in ...
0
votes
1answer
43 views

equivalent formulation of axiom of choice (Analysis 1 by Tao)

(Analysis 1 by Tao) Exercise 8.4.1. Show that the axiom of choice implies Proposition 8.4.7. (Hint: consider the sets $Y_x : = \{ y\in Y : P(x, y) \text{is true}\}$ for each $x \in X$.) Conversely, ...
0
votes
0answers
30 views

Countable union of disjoint finite sets is countable [duplicate]

This statement seems probably true, and for particular examples (e.g. 'all strings of length N in a given alphabet', union over all N) it holds, but I can't find any proof that doesn't rely on the ...
0
votes
0answers
35 views

Axiom of choice and first order logic [duplicate]

All explanations I found on the axiom of choice seem to say more or less the following: Although the axiom of choice is "intuitively obvious," it is necessary because making infinitely many choices is ...

1
2 3 4 5
32