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
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