Questions tagged [axiom-of-choice]
An important and fundamental axiom in set theory sometimes called Zermelo's axiom of choice. It was formulated by Zermelo in 1904 and states that, given any set of mutually disjoint nonempty sets, there exists at least one set that contains exactly one element in common with each of the nonempty sets. The axiom of choice is related to the first of Hilbert's problems.
576
questions
-6
votes
1
answer
124
views
Actual infinitesimals for solving Vitali paradox
Has anyone tried to use actual infinitesimals to solve paradoxes about non-measurability? In Vitali paradox, for example, they divide a set with measure 1 into $\infty$ subsets of zero measure and ...
- 111
10
votes
1
answer
363
views
Hereditarily countable sets in Antifounded ZF
A set $x$ is hereditarily countable when every membership-descendant of $x$ (including $x$ itself) is countable.
In this paper, Jech proved in ZF that the class of all hereditarily countable sets is a ...
- 1,382
14
votes
2
answers
1k
views
Proof/Reference to a claim about AC and definable real numbers
I’ve read somewhere on this site (I believe from a JDH comment) that an argument in favor of AC (I believe from Asaf Karagila) is that without AC, there exists a real number which is not definable ...
- 243
10
votes
1
answer
613
views
Infinitary logics and the axiom of choice
Suppose we want to enhance ZF by allowing for infinitary formulas instead of just first-order ones in our axiom schema of separation and/or replacement. It seems that we don't need much power in our ...
- 4,857
1
vote
0
answers
85
views
Everywhere-defined unbounded operators between Banach spaces
In this post, it is said that there are no constructive examples of everywhere-defined unbounded operators between Banach spaces; every example furnished must use the axiom of choice. This seems like ...
- 141
-2
votes
1
answer
162
views
Is discriminative choice provable in ZFC?
Let $\phi$ be a formula defining an equivalence relation.
Definitions:
The $\phi$-cardinality of a set $X$ be the cardinality of $X/\phi$. That is, the cardinality of the set of all equivalence ...
- 10.2k
9
votes
1
answer
295
views
Complexity of definable global choice functions
It is well-known that $L$ has a $\Sigma_{1}$-definable global choice function; it is also known that there are other transitive class models of ZFC with this property.
I wonder about the complexity ...
- 93
5
votes
1
answer
238
views
Is a weak version of the three sets Lemma provable in ZF?
The Three Sets Lemma is the following Lemma:
Lemma: Let $f(x)$ be a function from $X$ to $X$ where $f(x)$ has no fixed points. Then there exists a partition of $X$ into three disjoint sets $X_1$, $X_2$...
- 6,819
10
votes
1
answer
488
views
Must strange sequences wear Russellian socks?
This is an attempt to make more precise a vague guess at the end of this answer of mine. We work in $\mathsf{ZF}$ throughout.
Say that a sequence $\mathcal{A}=(A_i)_{i\in\omega}$ of disjoint sets is ...
- 20.7k
6
votes
2
answers
458
views
Does Well-Ordered Interval Power Set "WOIPS" principle , prove $\sf AC$ in $\sf ZFA$?
Does $\sf ZFA + WOIPS$ prove $\sf AC$?
Where $\sf WOIPS$ is phrased as: for every infinite set $X$ the set of intervening cardinals between $|X|$ and $|\mathcal P(X)|$ is well-ordered.
In $\sf ZF$, I ...
- 10.2k
3
votes
1
answer
149
views
Turning linear ordering into well-ordering
Work in ZF + DC. Assume that there is an uncountable $A \subseteq \mathbb{R}$ and a linear order $\prec$ on $A$ such that for every $x \in A$, $\{y \in A: y \prec x\}$ is countable. Must there exist ...
- 33
5
votes
1
answer
149
views
The equivalence of Dedekind-infinite and dually Dedekind-infinite as a weak form of (AC)
A set $X$ is Dedekind-infinite if there is an injective map $f: X\to X$ that is not surjective.
A set $X$ is dually Dedekind-infinite if there is a surjective map $f: X\to X$ that is not injective.
In ...
26
votes
1
answer
897
views
A cardinal inequality for finiteness
Nearly ten years ago, I explained in a blog post that, assuming only ZF, a cardinal number $\mathfrak{n}$ is finite if and only if it satisfies this monstrous inequality:
$$2^{2^{2^{2^{\mathfrak{n}}}}}...
- 43.8k
12
votes
1
answer
838
views
Partition of unity without AC
Several existence theorems for partition of unity are known. For example (source),
Proposition 3.1. If $(X,\tau)$ is a paracompact topological space,
then for every open cover $\{U_i \subset X\}_{i \...
- 223
6
votes
1
answer
160
views
Does $\mathsf{SVC}^\ast$ exist?
$\mathsf{SVC}(S)$ is the assertion that for all sets $X$ there is an ordinal $\eta$ and a surjection $f\colon\eta\times S\to X$. I would like to denote by $\mathsf{SVC}^\ast(S)$ the same assertion but ...
- 1,479
1
vote
1
answer
298
views
Proof of the axiom of choice for finite sets in ZF [closed]
Let the set $A$ be finite and $\emptyset \notin A$. How can I, without using the axiom of choice, prove by mathematical induction that there exists a function $f : A \rightarrow \bigcup A$ satisfying $...
- 21
12
votes
1
answer
419
views
Did Gödel possess a proof of the independence of $\mathsf{AC}$?
We all know Gödel proved the consistency of the Axiom of Choice with $\mathsf{ZF}$ using his constructible universe, and Cohen proved the consistency of $\neg \mathsf{AC}$ using his new method of ...
- 1,303
3
votes
0
answers
161
views
Periodicity in the cumulative hierarchy
Under Reinhardt cardinals in ZF, the cumulative hierarchy exhibits a periodicity in that for large enough $λ$, certain properties of $V_λ$ depend on whether $λ$ is even vs odd. See Periodicity in the ...
- 6,365
7
votes
0
answers
180
views
Large cardinals beyond choice and HOD(Ord^ω)
Are Reinhardt and Berkeley cardinals (and even a stationary class of club Berkeley cardinals) consistent with $V=\mathrm{HOD}(\mathrm{Ord}^ω)$ ?
It seems natural to expect no, but I do not see a proof....
- 6,365
4
votes
0
answers
144
views
Consistency of definability beyond P(Ord) in ZF
Is it consistent with ZF that the satisfaction relation of $L(P(Ord))$ is $Δ^V_2$ definable? More generally, is it consistent with ZF that there is a $Δ^V_2$ formula (taking $α$ as a parameter) that ...
- 6,365
5
votes
1
answer
270
views
Would strengthening Foundation and Choice in NBG, make it equi-consistent with MK?
This is a follow up to an earlier question about strengthening of foundation in relation to proving the consistency of ZFC. It was shown that it would achieve that, but it may fail short of MK. Here, ...
- 10.2k
5
votes
1
answer
230
views
Long chains of Dedekind finite sets
This is a variation on this question with amorphous cardinals replaced with dedekind finite sets.
Dedekind finite sets are sets that have no countable subset, and it is well known that this is a ...
- 384
13
votes
1
answer
549
views
Long chains of amorphous cardinalities
An amorphous set is an infinite set that cannot be partitioned into 2 infinite subsets. An amorphous cardinality is the cardinality of an amorphous set. Working in $\sf ZF$, it is consistent that ...
- 384
12
votes
1
answer
506
views
Building the real from Dedekind finite sets
It is well known that the real numbers can be countable union of countable sets by starting with GCH and taking a finite support permutations while collapsing all of $\aleph_n$ for natural $n$.
The ...
- 1,654
3
votes
1
answer
255
views
A possible ${\sf (ZF)}$-theorem in the spirit of the $3$-set-lemma
The number $3$ plays an interesting role in the following statement:
$\newcommand{\S}{\sf(S_3)}\S$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in ...
4
votes
1
answer
199
views
Weak Power Hypothesis and Dependent Choice
Consider in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$ the following statement:
Weak Power Hypothesis (WPH): if $X,Y$ are sets and there is a bijection between $\newcommand{\P}{{\cal P}}\P(X)$ and $\P(Y)$, ...
2
votes
0
answers
115
views
Adding partitions of one but not the other kind
Say that two partitions $(P_i)_{i\in I}, (Q_j)_{j\in J}$ are isomorphic iff there is a bijection $f: I\rightarrow J$ such that $\vert P_i\vert=\vert Q_{f(i)}\vert$ for all $i\in I$. (Note that in the ...
- 20.7k
7
votes
1
answer
400
views
How much choice is needed to prove the completeness of equational logic?
All the proofs of the completeness of (Birkhoff's) equational logic I have read seem to pick representatives for equivalence classes of terms and hence require the axiom of choice. Is AC (or a weak ...
- 93
13
votes
1
answer
921
views
Cantor-Bernstein with "weakly injective" functions
Let us call a map $f: X \to Y$ between non-empty sets a "weak injection" if $f^{-1}(\{y\})\subseteq X$ is finite for every $y \in Y$.
Recall that the (Schroeder-)Cantor-Bernstein-Theorem (...
17
votes
2
answers
1k
views
Axiom of Choice for collections of Equinumerous sets
Let ACE (Axiom of Choice for Equinumerous sets) be the following choice principal:
If $S$ is a set of non-empty sets such for any $X,Y\in S$ there is a bijection from $X$ to $Y$, then $S$ has a choice ...
- 488
8
votes
0
answers
188
views
Reference request: choiceless cardinality quantifiers
There is a substantial literature on the logic of cardinality quantifiers. (E.g., the quantifier $Q_\alpha$ where $M \vDash Q_\alpha x \, \varphi (x)$ iff $\vert \{a \in M : M \vDash \varphi[a] \} \...
- 1,155
14
votes
1
answer
781
views
Does completeness of the theory of a bijection without finite orbits depend on choice?
Consider the following sentences in a first-order language with one unary function symbol $f$:
$\forall x \exists y (fy=x)$
$\forall y\forall z(fy=fz\to y=z))$
$\forall x (\underbrace{f\dotsb f}_{n\...
- 163
1
vote
0
answers
274
views
Can the following definition of choice principle salvage the prior attempts?
In prior postings 1 , 2, I've presented a definition of choice principle as what is equivalent to a selection principle. However, it was proved that it is inadequate in the sense that it admits ...
- 10.2k
5
votes
1
answer
266
views
Does weak countable choice imply that the Cauchy reals are Dedekind complete?
Assuming the axiom of weak countable choice, is the set of modulated Cauchy reals Dedekind complete?
The second theorem on this ncatlab page claims something equivalent, but it doesn't contain a proof ...
- 6,298
2
votes
1
answer
579
views
Is there a strict limit on choice principles in $\sf ZFC$?
Is there a principle $\sf P$ that $\sf ZFC$ [or some suitable extension of it] proves to be a strict limit on choice principles?
By a choice principle I mean a sentence (or scheme) that is equivalent ...
- 10.2k
7
votes
3
answers
447
views
How much Dependent Choice is provable in $Z_2$? And what about Projective Determinacy?
So, second order arithmetic, $Z_2$, is capable of proving quite a few things. One thing which would be of use is dependent choice for $\mathbb{R}$.
Basically, dependent choice on $\mathbb{R}$ says ...
- 323
3
votes
2
answers
518
views
Is the Ordering Principle equivalent to a selection principle?
Working in the context of set theory $\sf ZF$, selection may be defined as a function from nonempty sets to their elements. Formally:
$\operatorname {selective}(c) \iff \operatorname {function}(c) \...
- 10.2k
7
votes
1
answer
873
views
Logical strength of a statement about vector spaces
[Apologies if this is a really trivial question, I know virtually nothing about set theory, and the following came up while preparing undergraduate linear algebra lectures.]
I'm asking about the ...
- 36.5k
3
votes
1
answer
247
views
Is the Class Well Ordering principle "CWO" the maximal choice principle?
In a prior posting, the Class Well-Ordering principle "$\sf CWO$" was presented, which simply states that there is a well-ordering over all classes of $\sf MK$. On the other hand, it is ...
- 10.2k
3
votes
0
answers
190
views
Reverse-mathematical strength of Banach-Tarski
What is the reverse mathematical strength of the Banach-Tarski paradox?
The usual proof of Banach-Tarski should carry out in $\mathrm{ZF}+\mathrm{AC}_\kappa$, where $\kappa$ is the supremum of the ...
- 1,696
5
votes
1
answer
421
views
Is there a class choice principle over MK that is equivalent to class well ordering over MK?
$\sf MKCWO$ is the theory obtained by adding a new primitive binary relation $\prec$ to the signature of $\sf MK$ and axiomatize that $\prec$ is a well order on classes, that is:
$\textbf{Transitive:}...
- 10.2k
4
votes
2
answers
207
views
Does $\mathsf{ZF}$ prove $\operatorname{Col}(\lambda,\kappa)$ preserves cardinals below $\lambda$?
Let $\lambda<\kappa$ be cardinals and consider the forcing $\operatorname{Col}(\lambda,\kappa)$ adding a generic surjection $\lambda\to\kappa$. More formally, $\operatorname{Col}(\lambda,\kappa)$ ...
- 2,910
9
votes
0
answers
134
views
Locally presentable and accessible categories without the axiom of choice?
Is there a good reference for the study of locally presentable and accessible categories without the axiom of choice? For instance, it seems one will need to understand:
What is a good notion of $\...
- 62.6k
-1
votes
2
answers
333
views
An equivalent of the axiom of choice? [closed]
There is such a thing as a math course for relatively non-mathematically inclined people that is intended to challenge students' intelligence more than to teach them some mathematics. (It is true that ...
- 12.3k
3
votes
1
answer
226
views
Is Morse-Kelley set theory with Class Choice bi-interpretable with itself after removing Extensionality for classes?
Let $\sf MKCC$ stand for Morse-Kelley set theory with Class Choice. And let this theory be precisely $\sf MK$ with a binary primitive symbol $\prec$ added to its language, and the following axioms ...
- 10.2k
14
votes
1
answer
1k
views
Are Berkeley cardinals easier to refute in ZFC than Reinhardt cardinals?
Kunen showed that Reinhardt cardinals are inconsistent in ZFC. But his proof is a bit technical for a non-set-theorist to follow. Berkeley cardinals are stronger than Reinhardt cardinals. You can ...
- 62.6k
3
votes
0
answers
144
views
Can well-ordering of the universe due to global choice survive extensive failure of Extensionality?
That axiom of global choice leads to the well-ordering of the universe given the other axioms of Zermelo set theory is a famous result.
Now, if we weaken the power set axiom to the axiom stating that ...
- 10.2k
12
votes
2
answers
411
views
Trading Choice for Comprehension (or Replacement)
This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
- 30.8k
9
votes
3
answers
416
views
Exponentiation of Dedekind cardinals
Question: Let $\mathfrak n$ be an infinite cardinal. In ZF (set theory without the axiom of choice) can either of the implications
$$\mathfrak n=\mathfrak n+1\implies2^\mathfrak n=2^{\mathfrak n+1}\...
- 12.7k
6
votes
1
answer
277
views
The Parity Principle and $\mathbf{C}_2$ (choice for $2$-sets)
The Parity Principle states that
if $X\neq \emptyset$ is a set, then there is $\mathcal B\subseteq \mathcal P(X)$ such that whenever $a,b\in \mathcal P(X)$ with $a\mathbin\Delta b = \{x\}$ for some $...