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.

Filter by
Sorted by
Tagged with
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 ...
Dominic van der Zypen's user avatar
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)$, ...
Dominic van der Zypen's user avatar
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 ...
Noah Schweber's user avatar
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 ...
ralphS16's user avatar
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 (...
Dominic van der Zypen's user avatar
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 ...
Brian Pinsky's user avatar
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] \} \...
Beau Madison Mount's user avatar
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\...
George Hayduke's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Christopher King's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Alex Appel's user avatar
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) \...
Zuhair Al-Johar's user avatar
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 ...
David Loeffler's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
C7X's user avatar
  • 1,176
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:}...
Zuhair Al-Johar's user avatar
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)$ ...
Hanul Jeon's user avatar
  • 2,774
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 $\...
Tim Campion's user avatar
  • 60.5k
-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 ...
Michael Hardy's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Tim Campion's user avatar
  • 60.5k
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 ...
Zuhair Al-Johar's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.8k
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}\...
bof's user avatar
  • 11.5k
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 $...
Dominic van der Zypen's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Yauhen Yakimovich's user avatar
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 ...
Calliope Ryan-Smith's user avatar
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 ...
Pelota's user avatar
  • 573
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 ...
Someone211's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Calliope Ryan-Smith's user avatar
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 ...
wlad's user avatar
  • 4,792
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$...
Dominic van der Zypen's user avatar
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$....
THC's user avatar
  • 4,313
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 ...
Rupert's user avatar
  • 1,985
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 ...
Arbuja's user avatar
  • 1
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}$, ...
Calliope Ryan-Smith's user avatar
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 ...
user171348's user avatar
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 $\...
new account's user avatar
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 ...
Bruce Blackadar's user avatar
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 ...
THC's user avatar
  • 4,313
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}...
Victor's user avatar
  • 2,076
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 ...
Anindya's user avatar
  • 371
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 ...
THC's user avatar
  • 4,313
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 ...
Holo's user avatar
  • 1,533
-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,.., \...
Zuhair Al-Johar's user avatar

1
2 3 4 5
12