All Questions
Tagged with determinacy set-theory
86 questions
35
votes
3
answers
5k
views
Counterintuitive consequences of the Axiom of Determinacy?
I just read Dr Strangechoice's explanation that if all subsets of the real numbers are Lebesgue measurable, then you can partition $2^\omega$ into more than $2^\omega$ many pairwise disjoint nonempty ...
- 7,633
26
votes
3
answers
2k
views
Does ZF+AD settle the original Suslin hypothesis?
Everyone knows that the real line $\langle\mathbb{R},<\rangle$ is
the unique endless complete dense linear order with a countable
dense set. Suslin's
hypothesis is
the question whether we can ...
- 236k
24
votes
2
answers
1k
views
What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?
Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.
Red wins after infinite play, ...
- 236k
18
votes
1
answer
822
views
What sets can be unraveled?
A set $X\subseteq\omega^\omega$ is unravelable iff there is a possibly larger set $A$ and a clopen set $Y\subseteq A^\omega$ (with respect to the product topology coming from the discrete topology on $...
- 21.1k
16
votes
1
answer
697
views
How to prove projective determinacy (PD) from I0?
Martin and Steel (in 1987?) showed that if there are infinite many Woodin cardinals then every projective set of reals is determined (PD).
However, it is mentioned in many texts that in 1983/1984 ...
- 779
14
votes
1
answer
840
views
Is there a minimal inner model for determinacy?
Assume $\sf ZF+AD$. Is there some inner model $M$ containing all the ordinals such that $M\models\sf ZF+AD$ as well?
What if we require $\omega_1$ and/or $\omega_2$ to be computed correctly?
Can we ...
- 39.7k
13
votes
1
answer
791
views
Consistency strength of projective determinacy (PD)
Let PD stand for projective determinacy, and consider the two claims:
(1) For each n=1,2,..., Con(ZFC+PD) implies Con(ZFC + there are n Woodin cardinals)
(2) Con(ZFC+PD) implies Con(ZFC + there are ...
- 205
13
votes
1
answer
524
views
How much determinacy do you need for second order arithmetic to be as strong as ZFC?
From Wikipedia (I couldn't find the original source):
$\text{ZFC} + \{\text{there are $n$ Woodin cardinals: $n$ is a natural number}\}$ is conservative over $\text{Z}_2$ with projective determinacy.
...
- 6,353
12
votes
1
answer
805
views
Coding a model of $0^\sharp$ from a $\Pi^1_1$ Gale-Stewart game
As a preface to this question, this is my first time asking on Math overflow, and this seemed like the sort of question that would be acceptable here. However, I apologize if it is not.
A method for ...
- 333
12
votes
1
answer
477
views
Is there a natural inner model of AD$_\mathbb{R}$?
The question is as in the title, but let me explain a bit.
Assuming a proper class of Woodin cardinals, $L(\mathbb{R})$ satisfies AD (and DC). And $L(\mathbb{R})$ is a very natural inner model. I'm ...
- 21.1k
12
votes
1
answer
448
views
Comparing generic versions of $\mathbb{R}$
This question was previously asked and bountied at MSE, unsuccessfully.
I'm currently interested in the behavior of cardinalities in generic extensions of models of $\mathsf{ZF+\neg AC}$, and ...
- 21.1k
12
votes
0
answers
505
views
Can a generic $\mathbb{R}$ have a new cardinality?
This question was asked and bountied at MSE, without success.
My main question is whether, starting with a model of determinacy, a "generic $\mathbb{R}$" could be different in cardinality ...
- 21.1k
12
votes
0
answers
357
views
Undetermined copy/diagonalize games without CH
This question was the motivation behind an earlier question of mine; having thought about it some more, that question seems nontrivial and the connection is actually pretty tenuous anyways, so I've ...
- 21.1k
11
votes
1
answer
581
views
Is determinacy on an infinite Dedekind finite set consistent?
Consider $\mathrm{AD}_X$, determinacy for games where players pick moves from $X$. We know that it is consistent for $X = \omega$ or $\mathbb{R}$ (under large cardinal assumptions), but inconsistent ...
- 643
11
votes
2
answers
708
views
Which forcings preserve (some) determinacy?
The question is exactly as in the title. I'm interested in general in all questions of the form "which forcings preserve property P?" for any P, but determinacy assumptions occupy a special place in ...
- 21.1k
11
votes
1
answer
686
views
The Axiom of Determinacy and the Banach-Mazur game
The Wikipedia article on the Axiom of Determinacy (AD) claims:
Equivalent to the axiom of determinacy is the statement that for every subspace X of the real numbers, the Banach–Mazur game BM(X) is ...
- 5,031
11
votes
0
answers
374
views
A game of harmonic series(s)
Given a set $A\subseteq\mathbb{R}_{>0}$, consider the following (two-player, perfect-information, length-$\omega$) game $H_A$:
Players $1$ and $2$ alternately play strictly increasing natural ...
- 21.1k
10
votes
5
answers
1k
views
Measurable cardinals under Axiom of Determinacy
I seem to remember reading somewhere that ZF+AD proves that $\omega_1$ and $\omega_2$ are measurable cardinals.
Is that right?
If so, can someone [point me to or give here] a [sketch or proof] of ...
user5810
10
votes
2
answers
564
views
Cardinal arithmetic under determinacy
Work in a reasonable theory of determinacy such as $\mathsf{ZF+DC+AD}$. Which of the following identities are true for arbitrary infinite sets?
$|A^2|=|A^3|$ (motivated by an MSE question that asks ...
- 667
10
votes
1
answer
255
views
How much of second-order arithmetic do you need for $\mathbf{\Sigma}^1_1$-determinacy to give you countable transitive models of $\mathsf{ZFC}$?
This is in some sense a follow-up to this question.
The answer there says that over $\mathsf{Z}_2$ (second-order arithmetic), (boldface) $\mathbf{\Sigma}^1_1$-determinacy is enough to entail the ...
- 12.4k
10
votes
1
answer
419
views
Assuming AD, is every infinite cardinal closed under power set in a choice model?
Assume AD+DC. Assume $\kappa$ is an infinite cardinal and $N$ is a (set or class) transitive model of ZFC containing $\kappa$.
Is it true that for all $\alpha<\kappa$, $N$ thinks that the power ...
- 685
10
votes
0
answers
222
views
Is any choice axiom other than WISC inherited by Grothendieck topoi?
It is well known that even if one works with say ZFC as a base theory, Grothendieck topoi do not in general satisfy even fairly weak axioms like countable choice or small violations of choice and one ...
- 1,947
10
votes
0
answers
306
views
The Chang model after collapsing an inaccessible limit of Woodins
If $\kappa$ is an inaccessible cardinal and $G \subset \operatorname{Col}(\omega,\mathord{<}\kappa)$ is a $V$-generic filter, then in $V[G]$ the Chang model $L(\text{Ord}^\omega)$ satisfies "every ...
- 5,471
9
votes
2
answers
455
views
Determinacy and Woodin cardinals
I am looking for a reference for the following result:
Theorem Assume $\kappa$ is a Woodin cardinal. Then after forcing with the Levy collapse $\mathbb{P}=Col(\omega, \kappa)$, the $\Sigma^1_2$-...
- 32.1k
9
votes
1
answer
739
views
Can the Turing degrees be linearly ordered?
Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
- 21.1k
9
votes
2
answers
1k
views
Martin's cone theorem and recursion theory
Martin's remarkable cone theorem in the theory of determinacy says the following:
Suppose $A\subseteq \omega^\omega$ is Turing invariant and determined. If $\forall x\exists y(x\le_T y\& y\in ...
- 32.5k
9
votes
1
answer
306
views
$\Sigma^0_1\wedge\Pi^0_1$-Determinacy holds in the second admissible above the game
Let $T$ be a game tree and $T\in N\in M$, where $N,M$ are the two least admissibles containing $T$. Let $A$ be a boolean combination of two lightface open sets in $[T]$, or alternatively, a boolean ...
- 437
9
votes
1
answer
677
views
Consistency strengths related to the perfect set property
I want a model of $\mathrm{MA}_{\sigma\mathrm{-centered}}+\neg\mathrm{CH}$ in which every set of reals in $L(\mathbb{R})$ has the perfect set property. In terms of consistency strength, it is known ...
- 1,101
9
votes
1
answer
229
views
n odd: $\bf\Delta^1_n$ wadge degrees are $< \bf\delta^1_{n+1}$
My adviser is out of town and there is a comment in the Van Wesep paper "wadge degrees and descriptive set theory" that I can't figure out.
Work in ZF+AD throughout.
As stated in the title, the ...
- 603
9
votes
0
answers
251
views
Another determinacy-related cardinal characteristic
This question is a kind of "dual" to an earlier one of mine.
Although I don't know a reference for this, it's easy to show the following result:
Suppose $G$ is a game in which neither ...
- 21.1k
9
votes
0
answers
178
views
Does determinacy imply unravellability for the Borel sets (over a weak base theory)?
As far as I know, the only way we currently know how to prove Borel determinacy in $\mathsf{ZFC}$ is to go through unravelability (a rather technical property whose definition can be found in Martin's ...
- 21.1k
9
votes
0
answers
242
views
Is this cardinal characteristic trivial? (Number of strategies needed to guarantee at least one win)
(Previously asked at MSE.)
Let the determinacy number, $\mathfrak{g}$ (for "game"), be the smallest cardinal such that for every (two-player, perfect-information, length-$\omega$) game on $\...
- 21.1k
9
votes
0
answers
256
views
A bi-modal logic related to determinacy
The short version of my question is as follows. There is a natural (I hope!) way to associate a bimodal theory to a game (two-player, perfect-information, length-$\omega$, on $\omega$); are there "...
- 21.1k
9
votes
0
answers
271
views
Which forcing types preserve the axiom of determinacy?
Do we have some rudimentary understanding of some properties that a forcing can have in order to guarantee that it doesn't violate the axiom of determinacy?
To be more specific, in Which forcings ...
- 39.7k
8
votes
1
answer
412
views
Universal $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ set
Does anyone know of a reference for the fact that if $\lambda$ is a limit of Woodin cardinals, then the pointclass $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ is $\omega$-parameterized? By ...
- 5,471
8
votes
0
answers
169
views
Upper-bounding determinacy
While the converse of Borel determinacy ("If a set of reals is determined, then it is Borel") is boringly disprovable, I'm curious if there is a sense in which something like it is ...
- 21.1k
7
votes
3
answers
460
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 ...
- 353
7
votes
2
answers
547
views
Weakly homogeneous trees under AD
If AD$_\mathbb{R}$ holds and $\kappa < \Theta$ then every tree $T$ on $\kappa$ is weakly homogeneous (Martin–Woodin, "Weakly homogeneous trees.") I recall hearing that the hypothesis can be ...
- 5,471
7
votes
1
answer
349
views
Uniformization under AD
Can the following uniformization statement be proved by $ZF+AD+DC$?
For any binary relation $R\subseteq \mathbb{R}^2$ with the property that $\forall x (\{y\mid R(x,y)\}\mbox{ is at most countable ...
- 4,201
7
votes
1
answer
555
views
Limitations of determinacy hypotheses in ZFC
When considering (set-theoretic) games, we have three parameters we can adjust:
Definability of the payoff set
The set of legal moves
The length of the game
When working in $\textsf{ZFC}$, what are ...
- 1,170
7
votes
1
answer
588
views
Determinacy from $\omega_1\rightarrow(\omega_1)^{\omega_1}$
Assuming the Axiom of Determinacy (abbreviated AD), Martin showed how to derive a rather strong partition on $\omega_1$, namely that $\omega_1\rightarrow(\omega_1)^{\omega_1}$. In "Infinitary ...
- 333
7
votes
0
answers
259
views
A version of determinacy for all sets
Under ZF + AD, some games are undetermined because of lack of choice. In fact, the axiom of choice is equivalent to determinacy of games of length 2. However, we can ask whether the lack of choice ...
- 7,545
7
votes
0
answers
198
views
Strengthening Determinacy in constructive set theory?
Recall how games work. Let $X$ be a set (the "game space") and $\alpha$ an ordinal (the "game clock"). Alice and Bob take turns naming elements of $X$. We write them down in order ...
- 63.9k
7
votes
0
answers
258
views
Is this determinacy principle consistent?
Let $\mathsf{ODet}_{\omega_1}(L(\mathbb{R}))$ be the following principle ("determinacy for simple open length-$\omega_1$ games"):
If $\kappa$ is any ordinal and $X\subseteq \kappa^{<\...
- 21.1k
7
votes
0
answers
231
views
Determinacy of symmetric games
Is it consistent that for all ordinals $α$ and $λ$ and infinite regular cardinals $κ$, games on $V_λ$ with game length $κα$ and $\mathrm{OD}(\mathrm{On}^κ)$ payoff that depends only on the set of all ...
- 7,545
7
votes
0
answers
239
views
Countable choice in $L(\mathbb{R}^*_G)$
Let $\lambda$ be a singular strong limit cardinal and let $G \subset \text{Col}(\omega,\mathord{<}\lambda)$ be a $V$-generic filter. Let $\mathbb{R}^*_G = \bigcup_{\alpha < \lambda} \mathbb{R}^{...
- 5,471
6
votes
1
answer
302
views
Ordinal-definable witnesses to the perfect set property?
This possibly a very basic descriptive set-theory question; if it is too basic for MO, feel free to migrate.
Throughout we work in ZF+AD. My question is:
If $A$ is an uncountable OD set of reals, ...
- 21.1k
6
votes
1
answer
587
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 ...
- 463
6
votes
1
answer
260
views
Existence of a winning strategy in the $\boldsymbol{\Delta}_2^0$ game
Consider the following infinite perfect information game with two players (the name I gave in the title of the post it totally made up): at each round $i \in \omega$, player $\mathrm{I}$ picks a ...
- 2,286
6
votes
1
answer
531
views
sigma-algebra generated by OD sets
Assume $V=L(\mathbb{R})$ and the Axiom of Determinacy. Is every set of reals generated by ordinal-definable sets of reals under the operations of countable union and intersection?
The class of sets ...
- 5,471