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
8
votes
1
answer
390
views
Are there known ways to posit definable global choice in ZF without positing V=L?
I need a global choice function defined by a formula in (a fragment of) ZF. There is no harm in assuming V=L for my purposes. But I wonder if there are any familiar alternative ways to get this?
...
- 10.8k
8
votes
1
answer
405
views
Compatibility of $\mathsf{SVC}$ and Reinhardtness
Can we prove the consistency of $\mathsf{ZF+SVC}$ + "There is a Reinhardt cardinal?" (Preferably from the consistency of $\mathsf{ZF}$ with a Reinhardt cardinal, but using a stronger ...
- 2,774
8
votes
1
answer
408
views
Automorphisms of projective spaces, and the Axiom of Choice
It is known that upon not accepting the Axiom of Choice (AC), there exist models of ZF in which there are projective spaces (over a division ring) with a trivial automorphism group. (This is a truly ...
- 4,353
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.4k
8
votes
1
answer
245
views
Some relevant questions about the consistency strength of singularity of $\omega_1$ and $\omega_2$
The following question was asked years ago on MSE, but let me recap it:
Question: Is there anything currently known about the exact consistency strength of "$\mathsf{ZF}$ + both $\omega_1$ and $\...
- 2,774
8
votes
1
answer
222
views
Aronszajn Trees when AC fails
This question may be easy and indicative of my ignorance about the failure of the axiom of choice. If so, I apologize. Below assume $\mathsf{DC}$ but not $\mathsf{AC}$. Suppose we have a partial order ...
- 1,832
8
votes
1
answer
242
views
Minimal selector for a family of finite sets
A colleague is refereeing a paper in which the following
lemma appears implicitly:
For any family $\mathcal G$ of nonempty sets let us call
a set $B$ a "selector" if $B$ meets all $F\in\mathcal G$...
- 13.9k
8
votes
1
answer
415
views
Undetermined games of "overdetermined" type
This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of ...
- 19.1k
8
votes
1
answer
1k
views
If a vector space has a basis then its dual vector space has a basis
Consider the following statement:
If a vector space has a basis then its dual vector space also has a basis.
It is not an axiom of ZF. It clearly follows from the Axiom of Choice. But it is also ...
- 4,116
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
8
votes
0
answers
307
views
A $\mathsf{ZF}$ example of a nonreflexive group which is isomorphic to its double dual?
Given a group $G$ denote by $G^\ast=\mathrm{Hom}(G,\Bbb Z)$ its dual and by $j\colon G\to G^{\ast\ast}$ the canonical homomorphism $g\mapsto (f\mapsto f(g))$. A group is reflexive iff $j$ is an ...
- 2,904
8
votes
0
answers
362
views
Can the set of endomorphisms of $(\mathbb R,+)$ have cardinality strictly between $\frak c$ and $\frak{c^c}$?
Let $\frak c$ be the cardinality of the reals. I know that in ZF the set of endomorphisms of $(\mathbb R,+)$ can have at least two different cardinalites:
If we allow the axiom of choice, you can ...
user35370
8
votes
0
answers
170
views
Non-wellorderable ultrafilters with wellorderable bases
There are some models in which $2^\omega$ is not wellorderable but there is a free ultrafilter over $\omega$. What about the consistency of: $2^\omega$ is not wellorderable + AC for countable sets of ...
- 2,321
8
votes
0
answers
529
views
A Banach-Tarski game
This is partially inspired by the question https://math.stackexchange.com/questions/1383397/cutting-a-banach-tarski-cake, which I find intriguing if unclearly written.
A paradoxical family of subsets ...
- 19.1k
7
votes
8
answers
1k
views
Result that follows from ZFC and not ZF but are strictly weaker than choice
A number of results that people use that require the axiom of choice (i.e. do not follow from ZF alone) are known to actually imply the axiom of choice. Therefore, one might naturally wonder whether ...
- 15.1k
7
votes
3
answers
432
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
7
votes
3
answers
874
views
BCT equivalent to DC
Do you know where I can find proof of equivalence Baire Category Theorem and DC (Axiom of Dependent Choice)? It is well known fact but I can't find appropriate literature with the proof.
- 133
7
votes
5
answers
1k
views
Is Lebesgue/Borel non-measurability actually caused by non-uniqueness?
In ZFC, every construction of a Lebesgue or Borel non-measurable set uses the axiom of choice. None of them that I've seen use choice to define a unique set, even though it's entirely possible to do ...
- 619
7
votes
2
answers
957
views
Exponentiation and Dedekind-finite cardinals
It is known that the sum and the product of two Dedekind-finite cardinals are also Dedekind-finite cardinals. What about cardinal exponentiation ?
Question: Let A and B be two Dedekind-finite ...
- 2,617
7
votes
2
answers
2k
views
A question about fields of real numbers
Assume that the continuum hypothesis holds. If $F$ is an uncountable field of real numbers, does $F$ always contain a proper uncountable subfield? Are there many specific uncountable fields of real
...
- 6,105
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
7
votes
2
answers
704
views
Consistency of a strange (choice-wise) set of reals
Consider a set $X\subseteq \mathbb{R}$ such that
$X$ is not separable wrt its subspace topology
For all $r\in\mathbb{R}$ there exists a sequence $(x_n)_{n\in\omega} \subset X$ converging to $r$
In a ...
- 2,134
7
votes
1
answer
789
views
author of a paradoxical decomposition of the interval
I am looking for the original author and the date of publication of the following result.
Theorem
There exist subsets $E_i\subset [0,1)$, $i\in {\bf Z}$, pairwise disjoints and real numbers $a_i$ ...
- 18.5k
7
votes
2
answers
965
views
When does Skolemization require the axiom of choice?
Skolemization is often used for eliminating existential quantifiers, which is often useful for proving theorems, especially in automated resolution theorem proving. Skolemization in first order ...
- 223
7
votes
1
answer
313
views
Notions of infinity in $\mathsf{ZF}$ without choice
Consider the following statements about a given set $X$ in in $\mathsf{ZF}$:
(1) There is $x_0\in X$ such that there is a surjective map $\varphi: X\setminus\{x_0\}\to X$.
(2) There is an injective ...
- 45.4k
7
votes
1
answer
860
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.1k
7
votes
1
answer
581
views
Relations of axioms of choice
We start with $ZF$.
The axiom of countable choice, $AC_\omega$, says that any set product of nonempty sets with a countable index set is nonempty. For any $ZF$-definable set $A$, we should be able ...
- 4,961
7
votes
1
answer
493
views
Totally bounded spaces and axiom of choice
Wikipedia article on totally bounded spaces states "... the completion of a totally bounded space might not be compact in the absence of choice." Where is the axiom of choice used, and do you need it ...
- 251
7
votes
2
answers
432
views
Possible Choices for Cofinality of $\aleph_n$ without Choice
$\text{ZFC}$ proves that each $\aleph_{n}$ for $n\in \omega$ is a regular cardinal. But it seems without the Axiom of Choice there are many consistent possible choices for cofinality of such cardinals....
user42090
7
votes
2
answers
1k
views
Can iterating countable unions give every set? (ZF)
Does ZF prove that there exists a set S such that S is not in the closure of {{s} : s in S} under at-most-countable unions?
user5810
7
votes
1
answer
522
views
Partitioning a set of cardinality $\kappa$ into more than $\kappa$ disjoint subsets
There is an old result due to Mycielski and Sierpiński, and popularized in a Monthly article by Taylor and Wagon (A Paradox Arising from the Elimination of a Paradox; see also this MO answer), that ...
- 78.3k
7
votes
2
answers
664
views
Can second-order logic identify "amorphous satisfiability"?
Recall that a set is amorphous iff it is infinite but has no partition into two infinite subsets. I'm interested in the possible structure (in the sense of model theory) which an amorphous set can ...
- 19.1k
7
votes
1
answer
386
views
Logical strength of "choice functions exist for well-ordered families"?
A colleague of mine suggested the following weakening of the axiom of choice:
If $\mathscr{F} := \{F_\alpha\}$ is a well-ordered family of non-empty sets (i.e., there is a bijection between $\...
- 78.3k
7
votes
2
answers
273
views
Minimal blocks for a family of finite sets
In this question I asked for a reference for the following lemma:
Lemma X: For every family $\mathcal G$ of nonempty finite sets there
is a minimal "blocking set" $B$. By a "blocking set" $B$ I ...
- 13.9k
7
votes
1
answer
620
views
Cardinal characteristics of amorphous sets
In a universe where the continuum hypothesis ($CH$) fails we can ask about combinatorial cardinal characteristics of the continuum, but in a universe where $CH$ is true no such cardinals exist so this ...
- 9,009
7
votes
1
answer
754
views
Does ZF bound countable unions of countable sets?
ZF proves that whenever a countable union of countable sets can be well ordered then its cardinality is at most $\aleph_1$. But what if it cannot be well ordered? The Feferman-Levy model shows the ...
- 10.8k
7
votes
1
answer
857
views
Symmetric extensions and class forcing
Suppose $V\models ZFC$ and $P\in V$ is a poset of forcing conditions.
It is a basic theorem in forcing that $V[G]\models ZFC$ for any generic extension by a $V$-generic filter $G$.
It is also known ...
- 38.2k
7
votes
1
answer
433
views
For models of ZF, if for some $A$ we have $L[A] = L$, what can we deduce about $A$?
Suppose $V$ is a model of ZF. Within $V$ we have $L$ which is a model of ZFC, furthermore $L[A]$ is a model of choice for every $A\in V$.
Suppose $A=\emptyset$ then clearly $L[A]=L$, furthermore if $...
- 38.2k
7
votes
3
answers
893
views
Construction of a maximal ideal
Hello,
Let R denote the ring of continuous functions defined on the real line, let I in R be the ideal consisting of functions with compact support. Obviously, I is not maximal, and by Zorn's Lemma ...
- 71
7
votes
1
answer
338
views
How hard is it to get "absolutely" no amorphous sets?
A beautiful and surprising (to me at least) result around the axiom of choice is that, while full $\mathsf{AC}$ is preserved by forcing, a model of $\mathsf{ZF}$ + "There are no amorphous sets&...
- 19.1k
7
votes
1
answer
497
views
Darboux property of non-atomic sigma-additive nonnegative measures equivalent to the AC?
A result commonly, and probably erroneously, attributed to W. Sierpiński is that every non-atomic, countably additive, nonnegative measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on ...
- 9,636
7
votes
1
answer
678
views
Existence of model of ZF without AC, but with many choice function
Question 1: Does there exist models of the Zermelo-Fraenkel set theory without the axiom of choice, but such that every indexed family of non-void sets whose index set has a well-orderable cardinal ...
- 2,617
7
votes
1
answer
460
views
Exterior powers and choice
Under the assumption that any vector space has a basis (so under the assumption of the axiom of choice), we can prove the following algebraic statements :
1) If $\varphi:V\to W$ is an injective ...
- 975
7
votes
1
answer
332
views
Intermediate submodels which do not satisfy AC
The following is known:
Theorem. Suppose $V[G]$ is a generic extension of $V$ by a set forcing, and let $N$ be a model of $ZFC$ with $V\subseteq N\subseteq V[G].$ Then $N$ is a generic extension of $...
7
votes
1
answer
888
views
Strictly order preserving maps into the integers
If $P$ and $P'$ are partial orders, a strictly order preserving map from $P$ to $P'$ is an $f:P\to P'$ satisfying that $x\lt y$ implies $f(x)\lt f(y)$ for all $x,y\in P$.
An interval in $P$ is a set ...
- 32.2k
7
votes
1
answer
346
views
Sets of cardinalities of bases without choice
For a vector space $V$, let $BS(V)$ be the set of cardinalities (not necessarily $\aleph$s) of bases of $V$. Of course, in ZFC each $BS(V)$ is a singleton, but supposing the axiom of choice fails, it ...
- 19.1k
7
votes
1
answer
451
views
$\Theta$ and the Hartogs of $2^\mathbb R$
Let $a,b$ be sets, we write $a\leq^\ast b$ if either $a=\varnothing$ or there exists a surjection $f\colon b\to a$. With the axiom of choice this is a linear ordering equivalent to the usual ordering ...
- 38.2k
7
votes
1
answer
282
views
Is the hereditary version of this weak finiteness notion nontrivial?
Say that a set $X$ is $\Pi^1_1$-pseudofinite if every first-order sentence $\varphi$ with a model with underlying set $X$ has a finite model. The existence of infinite $\Pi^1_1$-pseudofinite sets is ...
- 19.1k
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.1k
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}...
- 2,076