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).
2,181
questions
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 ...
- 611
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 ...
- 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 ...
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) ...
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$...
- 63
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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\...
- 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}}$ ...
- 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 ...
- 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,...
- 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^...
- 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 ...
- 4,631