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
0 answers
20 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....
Dmytro Taranovsky's user avatar
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 ...
Dmytro Taranovsky's user avatar
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, ...
Zuhair Al-Johar's user avatar
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 ...
Ynir Paz's user avatar
  • 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 ...
Ynir Paz's user avatar
  • 285
11 votes
1 answer
393 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 ...
Holo's user avatar
  • 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." ...
Kristian Berry's user avatar
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 ...
Dominic van der Zypen's user avatar
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)$, ...
Dominic van der Zypen's user avatar
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 ...
Noah Schweber's user avatar
6 votes
1 answer
377 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
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 (...
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
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] \} \...
Beau Madison Mount's user avatar
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\...
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
246 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
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 ...
Zuhair Al-Johar's user avatar
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 ...
Alex Appel's user avatar
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) \...
Zuhair Al-Johar's user avatar
7 votes
1 answer
862 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
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 ...
Zuhair Al-Johar's user avatar
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 ...
C7X's user avatar
  • 1,308
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:}...
Zuhair Al-Johar's user avatar
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)$ ...
Hanul Jeon's user avatar
  • 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 $\...
Tim Campion's user avatar
  • 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 ...
Michael Hardy's user avatar
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 ...
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
  • 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 ...
Zuhair Al-Johar's user avatar
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 ...
Gro-Tsen's user avatar
  • 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}\...
bof's user avatar
  • 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 $...
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
266 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
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 ...
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
  • 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 ...
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
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 ...
Calliope Ryan-Smith's user avatar
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 ...
wlad's user avatar
  • 4,853
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$...
Dominic van der Zypen's user avatar
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$....
THC's user avatar
  • 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 ...
Rupert's user avatar
  • 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 ...
Arbuja's user avatar
  • 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}$, ...
Calliope Ryan-Smith's user avatar
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 ...
user171348's user avatar
3 votes
0 answers
186 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

1
2 3 4 5
12