Questions tagged [determinacy]
The determinacy tag has no usage guidance.
81
questions
13
votes
1
answer
362
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.
...
- 4,675
2
votes
0
answers
242
views
Is determinacy of (some) very long open games consistent?
For $\varphi$ a first-order sentence in the language of set theory and $\kappa$ an ordinal, let $G_\varphi^{\kappa}$ be the game of length $\kappa$ in which players $1$ and $2$ alternately play ...
- 18.2k
7
votes
0
answers
240
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^{<\...
- 18.2k
5
votes
1
answer
376
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 ...
- 81
8
votes
0
answers
157
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 ...
- 18.2k
4
votes
1
answer
140
views
Can these alternating series games be undetermined?
To each pair $(S,\mathcal{X})$ where $S=(s_i)_{i\in\mathbb{N}}$ is a decreasing sequence of positive real numbers and $\mathcal{X}\subseteq\mathbb{R}$, we can associate the alternation game $A_S(\...
- 18.2k
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, ...
- 216k
9
votes
0
answers
236
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 ...
- 18.2k
8
votes
0
answers
161
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 ...
- 18.2k
9
votes
0
answers
226
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 $\...
- 18.2k
9
votes
0
answers
202
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,783
2
votes
0
answers
130
views
Weakening of open determinacy for uncountably long games
For a cardinal $\kappa$ I'll use the phrase "$(\kappa,\kappa)$-game" to mean "two-player, perfect-information, deterministic game on $\kappa$ of length $\kappa$."
Say that a ...
- 18.2k
9
votes
0
answers
268
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 ...
- 18.2k
2
votes
0
answers
91
views
Strong determinacy principles
It seems to be a well-known result that $\mathrm{AD}_{\omega_1}$ and $\mathrm{AD}_{\mathscr{P}(\mathbb{R})}$ (determinacy of $\omega$-length games with moves in $\omega_1$ or $\mathscr{P}(\mathbb{R})$,...
6
votes
1
answer
238
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 ...
- 1,668
7
votes
1
answer
310
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,076
3
votes
1
answer
133
views
Analytic sets and Turing determinacy
I wonder whether the following question have a positive answer within $ZFC$.
Question If $\{A_n\}_{n\in \omega}$ is a sequence of analytic sets so that $\bigcup_n A_n=2^{\omega}$, then there must be ...
- 4,076
4
votes
1
answer
937
views
I can't believe it's not Replacement!
(I feel like I might have to apologise in advance for this question, but oh well..)
I just rediscovered a comment from Asaf K here on MO that states that full Replacement is not needed for Borel ...
- 32.9k
7
votes
0
answers
215
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 ...
- 5,742
17
votes
1
answer
706
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 $...
- 18.2k
12
votes
0
answers
486
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 ...
- 18.2k
12
votes
1
answer
417
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 ...
- 18.2k
14
votes
1
answer
767
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 ...
- 37.5k
3
votes
1
answer
279
views
Pointwise definable models of determinacy
Suppose that the Axiom of Determinacy (AD) holds in $L(ℝ)$, and for some statement φ, $α$ is minimal such that $L_α(ℝ)⊨φ$. Do definable (in $L_α(ℝ)$) elements of $L_α(ℝ)$ form an elementary ...
- 5,742
8
votes
1
answer
203
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,812
2
votes
0
answers
180
views
An analytic game and Ramsey's theorem
Let $$P=\{(l_n, m_n)_{n=1}^t: l_n, m_n,t\in\mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}$$ and suppose that $T$ is some subset of $P$. Suppose that $T$ also has the following properties: ...
- 59
5
votes
0
answers
233
views
Forcing absoluteness in the setting of second-order arithmetic
There are some results about (set-size) forcing absoluteness for first-order properties in $L(\mathbb{R})$ and for $\mathbf{\Pi}^1_{\infty}$ properties when one works over $\mathsf{ZFC}$. My question ...
- 5,383
0
votes
0
answers
156
views
Strength of $Δ^1_{2n}$ determinacy
According to Lightface mice with finitely many Woodin cardinals from optimal determinacy hypotheses by Yizheng Zhu, theorem 1.1, over $\mathbf{Σ^1_{2n+1}}$ determinacy, $Δ^1_{2n+2}$ determinacy is ...
- 5,742
4
votes
1
answer
215
views
Strong partition property + DC + existence of non-principal ultrafilter on $\omega$
It was mentioned after Theorem 30.27 in Kanamori's Higher Infinite that Woodin constructed a model of $DC$ + there exists unboundedly many many $\kappa<\Theta$ such that $\kappa \to (\kappa)^\...
- 3,098
2
votes
0
answers
1k
views
The Rise and Fall of Dictators & How it Depends on Our Choice
This question is loosely inspired by the following paper of Shelah on Arrow property in which he answered a question of Gil Kalai affirmatively.
Shelah, Saharon, On the Arrow property. Adv. in Appl. ...
2
votes
1
answer
301
views
Is $Z_3+{\rm AD}$ equiconsistent with $\text{ZFC+AD}^{L(\mathbb{R})}$
Let $Z_2$ and $Z_3$ be second and third order arithmetics respectively.
In $Z_2$'s language, $\text{AD}$ (the axiom of determinacy) and $\text{PD}$ (projective determinacy) are stated the same way (...
- 615
11
votes
1
answer
615
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 ...
- 4,203
9
votes
0
answers
251
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 "...
- 18.2k
9
votes
1
answer
668
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 ...
- 18.2k
3
votes
2
answers
343
views
Strong limit cardinals in AD
In this question, I will be working in ZF.
Let $h(\kappa)$ for a cardinal $\kappa$ (not necessarily an ordinal) be the smallest ordinal $\alpha$ such that there is no surjection from a set of size $\...
- 1,224
2
votes
1
answer
184
views
Determinacy and polynomial time degrees
Is there a function $f:2^{<ℕ}→\{0,1\}$ such that for all $X∈{2^ℕ}$ with $X_{2i+1}=f(X_0,...,X_i)$ all hyperarithmetical properties of the polynomial time degree of $X$ are independent of $X$?
The ...
- 5,742
1
vote
1
answer
309
views
Under ZF + DC + AD, is it known what the properties are of the Hartogs number for $\mathcal{P}(\kappa)$ for some $\kappa>\aleph_0$?
It is a well-known result by Woodin that the Hartogs number $h(\mathbb{R})$ (more commonly known as $\Theta$) is a Woodin cardinal (in HOD) assuming ZF + AD + DC. This is equivalent to $h(\mathcal{P}(\...
- 1,224
12
votes
0
answers
348
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 ...
- 18.2k
3
votes
1
answer
259
views
Does determinacy in $L(\mathbb{R})$ implies projective determinacy (in $V$)?
Does $AD^{L(\mathbb{R})}$ directly implies projective determinacy? At least it certainely implies $PD$'s consistency.
- 615
25
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 ...
- 216k
7
votes
1
answer
499
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,162
11
votes
1
answer
434
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 ...
- 18.2k
11
votes
1
answer
526
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
6
votes
1
answer
368
views
How much real determinacy can live in $L(\mathbb{R})$?
It's well-known that AD$_\mathbb{R}$ fails in $L(\mathbb{R})$, provably in ZFC. This is because:
AD$^{L(\mathbb{R})}$ implies DC$^{L(\mathbb{R})}$.
Over ZF+DC, AD + "Every set of reals has a scale" ...
- 18.2k
2
votes
0
answers
106
views
Forgetful Determinacy and Gale-Stewart theorem
I have been studying a 1969 article by Rabin that proofs his apparently very influential Tree Theorem (that says the monadic second-order theory of 2 successors, S2S, is decidable).
To give a bit of ...
- 171
5
votes
0
answers
188
views
The club filter in definable preorders
So this is an embarrassing question. Call a preorder $\mathbb{P}$ good if it has the following properties:
Every countable chain in $\mathbb{P}$ has a least upper bound.
$\mathbb{P}$ is directed (any ...
- 18.2k
1
vote
1
answer
348
views
Defining cones and Turing cones
In Set Theory Jech defines a cone to be a subset of the Baire Space $\mathcal{N}$ of the form
$$\operatorname{cone}(x_0)= \{x : x_0 \in L[x]\}$$
where $x_0 \in \mathcal{N}$. Jech then defines the ...
- 180
3
votes
1
answer
299
views
Getting measures (especially on $\omega_2$) from potential clubs
This is a spinoff of this earlier question of mine.
Short version:
What measures in $L(\mathbb{R})$ can be gotten from "potentially club" filters, under appropriate hypotheses?
Long version: ...
- 18.2k
6
votes
1
answer
366
views
$\operatorname{AD}$ and the measurability of $\omega_1$
Are there proofs of the measurability of $\omega_1$ (under $\operatorname{AD}$) that do not use Turing degrees nor the $\Sigma_1^1$ boundedness lemma?
I've been struggling to find an "elementary" ...
- 180
5
votes
0
answers
378
views
Why is this transfinite game not determined?
This question originates from the paper On the Axiom of Determinateness by Jan Mycielski, section 7. Given a set $X$ and an ordinal $\alpha$, the author defines a transfinite game of length $\alpha$ ...
- 877