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.
553
questions
2
votes
1
answer
219
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
189
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
111
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 ...
6
votes
1
answer
361
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 ...
13
votes
1
answer
911
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 ...
8
votes
0
answers
178
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] \} \...
14
votes
1
answer
765
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\...
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 ...
5
votes
1
answer
229
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 ...
2
votes
1
answer
565
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 ...
7
votes
3
answers
425
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 ...
3
votes
2
answers
507
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) \...
7
votes
1
answer
856
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 ...
3
votes
1
answer
242
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 ...
3
votes
0
answers
176
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 ...
5
votes
1
answer
410
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:}...
4
votes
2
answers
187
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)$ ...
8
votes
0
answers
123
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 $\...
-1
votes
2
answers
232
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 ...
3
votes
1
answer
220
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 ...
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 ...
3
votes
0
answers
133
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 ...
12
votes
2
answers
396
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 ...
9
votes
3
answers
403
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}\...
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 $...
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\...
6
votes
0
answers
257
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
243
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
5
votes
1
answer
126
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 ...
3
votes
0
answers
163
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 ...
8
votes
1
answer
238
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$...
7
votes
2
answers
591
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
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 ...
1
vote
0
answers
722
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 ...
9
votes
1
answer
611
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}$, ...
10
votes
2
answers
685
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 ...
3
votes
0
answers
176
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 $\...
14
votes
1
answer
1k
views
Stone-Weierstrass Theorem without AC
To what extent does the usual Stone-Weierstrass Theorem depend on some form of the Axiom of Choice? There seems to be a lot of literature on constructive versions in toposes, but I have been unable ...
2
votes
0
answers
112
views
Elementary abelian 2-subgroups of $\mathrm{Aut}(\overline{\mathbb{Q}}/\mathbb{Q})$ (with and without choice)
Consider the absolute Galois group $G_{\mathbb{Q}} := \mathrm{Aut}(\overline{\mathbb{Q}}/\mathbb{Q})$.
As I understand it, the only torsion elements have order $2$ (by Artin-Schreier), and they are ...
7
votes
0
answers
307
views
What is the strongest form of the Axiom of Choice available in $\mathsf{Z}_{2}$?
$\mathsf{Z}_{2}$ denotes second-order arithmetic. Some forms of AC are expressible in $\mathsf{Z}_{2}$; for example the $\mathsf{\Sigma}_{1}^{1}$ axiom of choice is part of the theory $\mathsf{ATR}_{0}...
5
votes
1
answer
470
views
Large cardinals in ZF + DC + AD
The Axiom of Dependent Choice (DC) is often considered to be an "intuitive and non-controversial" version of choice used in the proofs of many theorems in Analysis. Similarly, the Axiom of ...
6
votes
1
answer
477
views
Automorphisms of algebraically closed fields without the Axiom of Choice
In the paper Algebraische Konsequenzen des Determiniertheits-Axioms (U. Felgner – K. Schulz, Arch. Math. (Basel) 42 (1984), pp. 557–563), the authors show that in models of Zermelo-Fraenkel set theory ...
6
votes
0
answers
152
views
Weak trichotomy principle in the absence of choice
It is well known that the trichotomy property of cardinals ($∀κ,λ\in\operatorname{Card}(κ<λ∨κ=λ∨κ>λ)$) is equivalent to the axiom of choice.
D. Feldman and M. Orhon had defined in [1] a ...
-2
votes
1
answer
196
views
Does cardinal definable choice imply AC?
Recall the definition of cardinal definable sets, to re-iterate:
$Define: X \text { is cardinal definable} \iff \\\exists \text { cardinal } \kappa \, \exists \text { cardinals } \lambda_1,.., \...