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.
560
questions
4
votes
0
answers
121
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,112
5
votes
1
answer
263
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, ...
- 9,276
5
votes
1
answer
200
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 ...
- 285
13
votes
1
answer
532
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 ...
- 285
11
votes
1
answer
392
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,645
-5
votes
0
answers
86
views
Can ur-elements be used as/to construct infinitesimals?
Background material:
Truss[95], "The structure of amorphous sets."
Harrison-Trainor and Kulshreshtha[22], "The Logic of Cardinality Comparison Without the Axiom of Choice."
...
-4
votes
0
answers
181
views
CH vs Not CH, What is the Consequence?
EDIT: Altered (3) to say that $\beth_1$ can't be $\aleph_{\omega}$ or $\aleph_0$ but removed statement that it must be less than $\aleph_{\omega}$.
Let us assume ZFC. We now consider 2 transfinite ...
- 99
2
votes
1
answer
223
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 ...
- 45.5k
4
votes
1
answer
193
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)$, ...
- 45.5k
2
votes
0
answers
113
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 ...
- 19.3k
6
votes
1
answer
375
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 ...
- 83
13
votes
1
answer
915
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 (...
- 45.5k
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
183
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,135
14
votes
1
answer
769
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\...
- 143
1
vote
0
answers
272
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 ...
- 9,276
5
votes
1
answer
245
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 ...
- 5,831
2
votes
1
answer
567
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 ...
- 9,276
7
votes
3
answers
433
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 ...
- 173
3
votes
2
answers
514
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) \...
- 9,276
7
votes
1
answer
861
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.2k
3
votes
1
answer
246
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 ...
- 9,276
3
votes
0
answers
179
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,298
5
votes
1
answer
414
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:}...
- 9,276
4
votes
2
answers
196
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,774
9
votes
0
answers
129
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 $\...
- 61.6k
-1
votes
2
answers
239
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 ...
- 11.9k
3
votes
1
answer
223
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 ...
- 9,276
13
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 ...
- 61.6k
3
votes
0
answers
138
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 ...
- 9,276
12
votes
2
answers
400
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.2k
9
votes
3
answers
407
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}\...
- 11.9k
6
votes
1
answer
265
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 $...
- 45.5k
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
- 45.5k
6
votes
0
answers
265
views
Models of ZF (without Inaccessible cardinals) where only the full Axiom of Choice fails, but the Axiom of Countable Choice remains true?
Solovay's model (which assumes $I$ = "existence of inaccessible cardinal") will be a well-known construction to produce a model of ZF where only the full Axiom of Choice ($AC$) fails, but ...
3
votes
1
answer
251
views
What are some "easy" violations of $\mathsf{SVC}$?
By $\mathsf{SVC}$, I mean "small violations of choice", which is the statement
$$(\exists S)(\forall X)(\exists f)``f\colon S\times\text{Ord}\to X\text{ is a surjection}".$$
Such an $S$ is ...
- 1,251
40
votes
3
answers
5k
views
How much of mathematical General Relativity depends on the Axiom of Choice?
One of the cornerstones of the mathematical formulation of General Relativity (GR) is the result (due to Choquet-Bruhat and others) that the initial value problem for the Einstein field equations is ...
- 593
21
votes
4
answers
4k
views
How much of the axiom of choice do you need in mathematics?
Say we have DC-λ where λ is some inaccessible cardinal. Is that enough to develop all of ordinary mathematics? If not, is there a strengthening that is but that nevertheless does not assume full ...
- 347
4
votes
0
answers
146
views
The monochromatic principle and the axiom of choice
For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...
- 45.5k
7
votes
0
answers
163
views
"Minimal-ish" Dedekind-finite cardinalities of models
Throughout, we work in $\mathsf{ZF}+$ "There is an infinite Dedekind-finite set."
Say that a Dedekind-finite cardinality $\kappa$ is $\Sigma^1_1$-isolated iff there is some first-order ...
- 19.3k
3
votes
2
answers
201
views
Posets such that the collection of principal down-sets does not have property ${\bf B}$
We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $S\cap e \neq \emptyset \neq e \setminus S$.
Let $(P,\leq)$ be a ...
- 45.5k
5
votes
1
answer
127
views
References for the axiom of surjective comparability
The axiom $W_\kappa$, for $\kappa$ a cardinal, is the statement that for all sets $X$, either $|X|\leq\kappa$ (that is, there is an injection $X\to\kappa$) or $\kappa\leq|X|$. Is there literature on ...
- 1,251
3
votes
0
answers
169
views
Do the difficulties in generalising Henstock-Kurzweil still exist if every subset of $\mathbb R^n$ is Lebesgue measurable?
There are apparently some difficulties generalising the Henstock-Kurzweil integral from functions of signature $\mathbb R\to\mathbb R$ to functions of signature $\mathbb R^n \to \mathbb R$. One ...
- 4,843
8
votes
1
answer
239
views
Non-Ramsey functions $c:[\omega]^\omega\to\{0,1\}$ and the Axiom of Choice
Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$, and let $c:[\omega]^\omega\to\{0,1\}$ be a function. We say that $a\in [\omega]^\omega$ is monochromatic with respect to $c$...
- 45.5k
7
votes
2
answers
594
views
Involutions in the absolute Galois group (and the Axiom of Choice)
It is known that the only elementary abelian $2$-groups (finite and nonfinite) in $\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ are in fact finite and cyclic – that is to say, they are of order $2$....
- 4,353
4
votes
0
answers
218
views
stating large cardinal axioms in ZF
Can I ask whether there is a good reference for how to state the standard large cardinal axioms in the context of $ZF$? My concern is that it seems that the usual proof that embeddings defined from ...
- 2,005
1
vote
0
answers
723
views
Finding a unique and finite expected value for almost all measurable functions?
Let $(X,d)$ be a metric space. If set $A\subseteq X$, let $H^{\alpha}$ be the $\alpha$-dimensional Hausdorff measure on $A$, where $\alpha\in[0,+\infty)$ and $\text{dim}_{\text{H}}(A)$ is the ...
- 1
9
votes
1
answer
613
views
Small Violations of Choice: Can we force AC without collapsing the cardinalities of ordinals?
We say that a model $M$ of $\mathsf{ZF}$ satisfies Small Violations of Choice ($\mathsf{SVC}$) if all (any) of the following apply:
There is a model $V\subseteq M$ such that $V\vDash\mathsf{ZFC}$, ...
- 1,251
10
votes
2
answers
696
views
Class-theoretic division paradox
The Division Paradox is the fact that there are models of ${\sf ZF \neg C}$ in which a set can be partitioned into a set that is bigger than it — equivalently, in which there are sets $X$ and $Y$ such ...
- 103
3
votes
0
answers
185
views
Basic cardinal arithmetic without choice
Do we know everything about addition and multiplication of cardinalities in choiceless set theory?
For example, let $M$ be a model of $\textsf{ZF}+\textsf{AD}+V=L(\mathbb{R})$, consider the sets $\...
- 727