Skip to main content

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
0 answers
53 views

Countable Choice from Finite Sets

Consider the following 4 statements: Axiom of countable choice Axiom of countable choice from finite sets Axiom of countable choice from Dedekind finite sets Existence of a choice function for any ...
svq0231's user avatar
  • 11
3 votes
0 answers
83 views

A union of unions needn't be a union? (Sans AC) [duplicate]

For any collection $\mathscr C$ of sets, write $\Upsilon(\mathscr C)$ for the collection of arbitrary unions in $\mathscr C$. Now, I ask the innocent question of idempotency of $\Upsilon$: Is $\...
Atom's user avatar
  • 4,119
2 votes
1 answer
77 views

Does $A$-fold choice imply $|A| + |A| = |A|$ and $|A|\cdot |A| = |A|$?

Let $A$ be an infinite set. Then Zorn's lemma can be used to conclude that $A\times\{0, 1\}$, $A\times A$ and $A$ are all equinumerous (a proof is presented here). However, I am aware that for $A$ ...
Atom's user avatar
  • 4,119
0 votes
0 answers
41 views

Is there a model of ZF not C where not every set of reals is Lebesgue measurable? [duplicate]

I know that there is a model of ZF set theory plus the negation of the axiom of choice where every set of reals is Lebesgue measurable. But is there also a model where not every set of reals is ...
user107952's user avatar
  • 21.5k
2 votes
0 answers
65 views

Principle in between BPI and AC

I have searched extensively in the literature, but all references I have consulted always place BPI (the Boolean Prime Ideal Theorem) as a sort of "cover" of the Axiom of Choice as far as ...
Rodrigo Nicolau Almeida's user avatar
6 votes
1 answer
77 views

Is every (infinite) permutation the composition of 2 involutions in ZF?

It is well known that any permutation on a finite set is the product of two involutions. I've wondered about what can happen in infinite sets. Asuming the axiom of choice, every permutation is still a ...
Carla_'s user avatar
  • 457
3 votes
0 answers
43 views

Discontinuous linear map and AC

The question arises when I am constructing an elementary proof for the following claim: Given a normed vector space $V$, the following are equivalent: $V$ is finite dimensional Every linear map $T:V\...
Akira Satou's user avatar
0 votes
1 answer
26 views

Axiom of Choice in characterizing openness in subspace

Below is the typical characterization of open sets in a subspace $Y$ of a metric space $X$. $E$ is $Y$-open iff there exists an $X$-open $S$ such that $E = S \cap Y$. The forwards direction usually ...
n1lp0tence's user avatar
2 votes
0 answers
133 views

Why is the Axiom of Choice Necessary in ZFC

Within the framework of Zermelo-Fraenkel set theory with the Axiom of Choice $(ZFC)$, when we considered the method of constructing the set of natural numbers, we regarded it as the smallest inductive ...
Bezina Taki's user avatar
1 vote
2 answers
138 views

Are the sets of the form $a=\{a\}$ different?

Suppose we adopt all the ZF axioms except the axiom of foundation. I suppose even adding the AC would not harm my question. Somewhere on the internet, I read that in this case, the axiom of ...
Bumblebee's user avatar
  • 18.4k
0 votes
2 answers
63 views

Truncated Tarski's theorem without axiom of choice

I read there that the fact about equivalence of $A$ and $A^2$ for any infinite set $A$ and the axiom of choice are equivalent. But what if we prove it only for sets that have cardinality of $\aleph_n,...
nyekitka's user avatar
  • 103
1 vote
1 answer
41 views

uniform well-ordering and constructibility

When comparing between V=L and AC, one of the things that gets my attention is that, if we switch to an external perspective and don't care about first-order expressibility, in models of V=L we have a ...
Raczel Chowinski's user avatar
0 votes
1 answer
64 views

Is ACC implicitely involved in a construction?

Suppose that $X$ is a (edit: separable) complete metric space and $\{X_j:j\ge 1\}$ is a partition of $X$ (each $X_j\ne \emptyset$). Given a (continuous) function $f:X\to \mathbb{R}$, I construct $$ h(...
Robert W.'s user avatar
  • 724
1 vote
0 answers
38 views

The relation between the cardinality of Bore $\sigma$-algebra and axiom of choice

Under axiom of choice, the cardinality of Borel $\sigma$-algebra $B$ is $\mathfrak{c}$. In this proof axiom of choice is used three times: To prove $\omega_1$-times recursion is sufficient, each $|B_{...
Gizerst Nanari's user avatar
0 votes
3 answers
71 views

Construction of Proof: Zorn's lemma implies Axiom of choice

I have come across the prove that [Zorn's Lemma ==> AC] but am confused about the central statement, namely that we can take a set of all choice functions on subsets of X (lets just call it X, I ...
CopperCableIsolator's user avatar
4 votes
2 answers
113 views

Cantor-Bendixson theorem and AC

For context, the Cantor-Bendixson theorem states that a closed subset $A$ of a Polish space can be written as the union of a perfect subset and a countable set $A=P\cup C$. Now, I know two proofs of ...
Akira Satou's user avatar
0 votes
0 answers
76 views

Why can't $\mathbb{R}/\mathbb{Q}$ be linearly-ordered without Axiom of Choice?

This Question has an answer which is the only source that I can find about how $\mathbb{R}/\mathbb{Q}$ cannot be linearly ordered. I couldn't manage to open either of the source links provided in the ...
Adam's user avatar
  • 335
3 votes
0 answers
63 views

Is the Axiom of Dependent Choice necessary in this proof?

While typically, the Axiom of Choice and its peripheral arguments are not emphasized in one's first exposure to Real Analysis, I am trying to be as rigorous as possible in my learning as an axiomatic ...
n1lp0tence's user avatar
7 votes
1 answer
167 views

Use of (weak forms of) AC for elementary embeddings proof

I encounter this issue when going through equivalent characterizations of measurable cardinals. For completeness, let me reproduce the statement: For ordinal $\kappa$, the following are equivalent. ...
Raczel Chowinski's user avatar
2 votes
1 answer
85 views

Is the existence of a discontinuous linear map from a Hilbert space equivalent to the Axiom of Choice?

All constructions of a discontinuous linear map from an Hilbert Space, that i have seen, rely on using the Axiom of Choice. A lot of theorems that heavily rely on AC are equivalent to AC itself so i ...
screamingToad's user avatar
1 vote
1 answer
74 views

Could the Axiom of Choice be viewed as a restricted version of the Axiom of Union?

Given the ZFC Axiom of Union in the form : $$\forall x \exists y \forall z (z \in y \iff \exists w (z \in w \land w \in x)) $$ or consider : $$\forall x \exists y \text{ ("separate" every element ... ...
Confusdius's user avatar
1 vote
1 answer
49 views

Point-separating fields of clopen sets on compact spaces without Choice

In Matthew Dirk's Paper on Stone's representation theorem there is a proof of Lemma 3.8. If X is a Stone space and F is a separating field of clopen subsets of X, then F is the dual algebra of X; that ...
Daniel Weichhart's user avatar
2 votes
0 answers
106 views

How does one prove without the axiom of choice that the product of a collection of nonempty well-ordered sets is nonempty?

Suppose $\{X_{\alpha}\}_{\alpha\in\mathcal A}$ is an indexed family of nonempty well-ordered sets, where $X_{\alpha}=(E_{\alpha},\le_{\alpha})$ for each $\alpha$. It seems intuitively obvious that we ...
Joe's user avatar
  • 20.8k
1 vote
1 answer
109 views

Linear independence of tensor products $\{v_i \otimes w_j\}$ without choice

Let $V$, $W$ be vector spaces. Suppose $\{v_i\} \subseteq V$ and $\{w_j\} \subseteq W$ are linearly independent. Then $\{v_i \otimes w_j\} \subseteq V \otimes W$ is linearly independent. The usual ...
ViHdzP's user avatar
  • 4,764
1 vote
0 answers
34 views

Exterior and symmetric powers without choice

Let $R$ be a commutative ring, $F$ a free $R$-Module and $n\in \mathbb{N}$. Can it be proven in ZF that the canonical projections $F^{\otimes n}\twoheadrightarrow \bigwedge^n(F)$ and $F^{\otimes n}\...
Lucina's user avatar
  • 657
7 votes
0 answers
144 views

Is every set an image of a totally ordered set?

It is known that the statement "Every set admits a total order" is independent of ZF. See here, for example. However, can it be proven in ZF that for every set $Y$, there exists a totally ...
Lucina's user avatar
  • 657
0 votes
1 answer
41 views

How to construct a countable series of sets in $\mathbb{R}$ with no rational differences and complete coverage

I had this question in the test and unfortunately I didn't know how to prove it, I would appreciate some help: Assuming Axiom of Choice, show that there exists a countable series of sets $A_0,A_1,A_2,...
eitan.sh21's user avatar
4 votes
2 answers
296 views

Proof Without Axiom of Choice: Infiniteness of Union

Without using any form of the axiom of choice, prove that if $A$ is infinite, then the set $\bigcup A$ is also infinite. I have encountered this proposition in my studies and find it intriguing, yet I'...
Maria S.'s user avatar
2 votes
1 answer
308 views

Dependence of the equation $a+1=a$ for infinite cardinals $a$ on the axiom of choice

let $A$ be a set such that for all $n \in $ N $ A ≉ N_n$ where $N_n = \{ 0 ,1 ,2 ...... n-1\} $ and $a$ be the Cardinality of $A$ meaning ($|A| = a$) is it possible to prove that $a+1=a$ without ...
theorem 28's user avatar
2 votes
3 answers
124 views

Intuition for why the Power Set Axiom can not be used to derive the Axiom of Choice

Using the Axiom of Replacement, every set E, with elements e, has a mirror set E' with the property : $$ E' := \{\langle E,e\rangle \mid e \in E \} $$ Again using the Axiom of Replacement, for any set ...
Confusdius's user avatar
6 votes
1 answer
190 views

Why is homological algebra nonconstructive?

In the Introduction to Weibel's homological algebra book, he states that homological algebra gives nonconstructive results. He doesn't elaborate on this further, so I wanted to know where exactly the ...
Hyunbok Wi's user avatar
2 votes
0 answers
50 views

Prove The class Recset of recursive sets is the same as the class of all sets.

This is from spring18 mcs.pdf. recursive set definition Definition 8.3.1. The class of recursive sets Recset is defined as follows: Base case: The empty set $\varnothing$ is a Recset. Constructor ...
An5Drama's user avatar
  • 416
0 votes
2 answers
74 views

Implied proof of axiom of choice

As I understand it the axiom of choice is: For any set (A) a collection of non empty disjoint sets there exists (at least one set) that contains (exactly) one element of each of those sets. If we let ...
Howard Cary Morris's user avatar
6 votes
1 answer
297 views

How to construct a nonzero real number between two given nonzero real numbers?

Statement: Let $$X=$$ $$\{(a,b) \in \mathbb{R} \setminus \{0\} \times \mathbb{R}\setminus \{0\}:a<b\}$$ There exists a function $f:X \rightarrow \mathbb{R} \setminus \{0\}$ such that for all $(a,b) ...
Mohammad tahmasbi zade's user avatar
1 vote
1 answer
93 views

How does this proof that for every infinite set $A$ there exists an injection $f : \mathbb{N} \rightarrow A$ rely on the axiom of choice?

I'm currently taking a course in proof-writing, and the following question came up on a problem set: Prove that for every infinite set $A$, there is a one-to-one function $f : \mathbb{N} \rightarrow A$...
Wabberjockey's user avatar
3 votes
2 answers
120 views

What is the most general form of the distributive law for $\cup$ and $\cap$?

The following forms of one of the distributive laws increase in generality as we move down the list: \begin{align} (A\cup B)\cap C &= (A\cap C)\cup(B\cap C)\\\\ &\,\Uparrow\\\\ (\bigcup_{a\in ...
John's user avatar
  • 4,432
1 vote
0 answers
66 views

Can the separability of a space depend on the axiom of choice?

Does there exist a topological space $X$ such that in $\mathsf{ZFC}$, $X$ is separable, but such that it is consistent with $\mathsf{ZF}$ that $X$ is not separable? The motivation behind this question ...
Smiley1000's user avatar
  • 1,649
5 votes
2 answers
125 views

No 3 vectors independent over $\mathbb{Z}$ in $\mathbb{Z}^2$, without AoC

Q: Are there three $\mathbb{Z}^2$ vectors independent over $\mathbb{Z}$ ? Context: This problem arise naturally when I'm characterizing possible sub-"latice" in $\mathbb{Z}^2$. Formally let ...
Lab's user avatar
  • 635
1 vote
1 answer
61 views

How Can I Finish off this Proof on Axiom of Choice?

Question Prove that the following is equivalent to the Axiom of Choice: Every surjective map has a right inverse. Attempt I already showed that if the Axiom of Choice holds, then every surjective map ...
Mr Prof's user avatar
  • 451
3 votes
1 answer
102 views

Can a subset of $\mathbb R$ of size $\aleph_1$ be explicitly constructed?

The Continuum Hypothesis claims that $|\mathbb R|=\aleph_1$. This has already been proven unprovable within ZFC. However, we can prove within ZFC that $|\mathbb R|\ge\aleph_1$ and thus there exists $S\...
Alma Arjuna's user avatar
  • 3,881
0 votes
1 answer
87 views

Is there a way to construct larger cardinals without choice axiom?

From Cantor's Theorem, we know that $|\mathcal{P}(X)| > |X|$. So, we can define inductively a set with cardinality $\aleph_n, \forall n \in \mathbb{N}$. Let $\lbrace A_i\rbrace_{i \in \mathbb{N}}$ ...
Edwin's user avatar
  • 31
4 votes
1 answer
93 views

The negation of countable choice for reals is consistent

Full disclosure (in order to forestall indignation): I'm going to be using this result in my upcoming paper (I have a statement which I show to be equivalent to $\neg CC(\mathbb R)$ and which I want ...
Cloudscape's user avatar
  • 5,146
10 votes
1 answer
196 views

Equal number of finite and infinite subsets implies amorphous

We work in $\sf ZF$. An amorphous set is a set that cannot be partitioned into $2$ disjoint infinite sets. If $A$ is an amorphous set then it has an equal number of finite subsets and infinite subsets,...
Ynir Paz's user avatar
  • 607
17 votes
2 answers
402 views

Combinatorial proof, without axiom of choice, that for any set $A$, there is no surjection from $A^2$ to $3^A$

The well known proof of Cantor's theorem (stating that $A<2^A$ for any set $A$) does not make any use of the axiom of choice. I have now spent some time wondering if the analogous result $A^2<3^...
Tim Seifert's user avatar
  • 2,243
0 votes
1 answer
78 views

How to prove consistency with choice for large cardinal extensions?

How can we know if an extension of $\sf ZF$ by some large cardinal property that results in a consistency strength beyond $0^{\#}$ is compatible with choice or not? I mean the easiest way to know if ...
Zuhair's user avatar
  • 4,631
4 votes
1 answer
151 views

Without choice, what can be the (finite) automorphism groups of $\mathbb F_2$-vector spaces?

My motivation for this question is similar to the one in this question. However, that question only asks about the possibility of an infinite $\mathbb F_2$-vector space having trivial automorphism ...
Carla_'s user avatar
  • 41
2 votes
1 answer
76 views

How much choice is needed to prove that $|G| \nless |G/ \sim|$ for any equivalence relation $\sim$ on set $G$?

$G/ \sim$ is the set of $\sim$-equivalence classes in $G$ and $|G/ \sim|$ is the cardinality of $G/ \sim$. $|A| \leq |B|$ means that there is an injective function from $A$ to $B$. $|A| < |B|$ ...
Hussein Aiman's user avatar
1 vote
2 answers
89 views

If $f$ is surjective, it has a right inverse

I've been struggling to understand how the surjection of a function $f : X \rightarrow Y$ implies that it has a right inverse. My questions basically reside on the application of the axiom of choice ...
TylerD007's user avatar
  • 621
-2 votes
2 answers
137 views

How to prove that CC($\mathbb R$) is true in permutation models [closed]

I've familiarised myself with models of set theory and am beginning to understand the basics, but am still very far away from being a proper model theorist. I currently live under the impression that ...
Cloudscape's user avatar
  • 5,146
1 vote
1 answer
86 views

Finite Content Not Continuous on the Empty Set

I have come across a lemma which states: Let $\mu$ be a finite content on an algebra $\mathcal{A}$. $\mu$ is a pre-measure if and only if $\mu$ is continuous on the empty set, i.e., for every sequence ...
SineOfTheTimes's user avatar

1
2 3 4 5
44