Questions tagged [determinacy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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. ...
PyRulez's user avatar
  • 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 ...
Noah Schweber's user avatar
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^{<\...
Noah Schweber's user avatar
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 ...
user42761's user avatar
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 ...
Noah Schweber's user avatar
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(\...
Noah Schweber's user avatar
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, ...
Joel David Hamkins's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 $\...
Noah Schweber's user avatar
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 ...
saolof's user avatar
  • 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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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})$,...
Beau Madison Mount's user avatar
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 ...
Lorenzo's user avatar
  • 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 ...
喻 良's user avatar
  • 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 ...
喻 良's user avatar
  • 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 ...
David Roberts's user avatar
  • 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 ...
Dmytro Taranovsky's user avatar
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 $...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Asaf Karagila's user avatar
  • 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 ...
Dmytro Taranovsky's user avatar
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 ...
Corey Bacal Switzer's user avatar
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: ...
user-1's user avatar
  • 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 ...
Fedor Pakhomov's user avatar
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 ...
Dmytro Taranovsky's user avatar
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)^\...
Jing Zhang's user avatar
  • 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. ...
Morteza Azad's user avatar
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 (...
Julian Barathieu's user avatar
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 ...
Alex Kruckman's user avatar
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 "...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 $\...
Keith Millar's user avatar
  • 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 ...
Dmytro Taranovsky's user avatar
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}(\...
Keith Millar's user avatar
  • 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 ...
Noah Schweber's user avatar
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.
Julian Barathieu's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Dan Saattrup Nielsen's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Ben E's user avatar
  • 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" ...
Noah Schweber's user avatar
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 ...
konewka's user avatar
  • 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 ...
Noah Schweber's user avatar
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 ...
Maxtimax's user avatar
  • 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: ...
Noah Schweber's user avatar
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" ...
Maxtimax's user avatar
  • 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$ ...
John Gowers's user avatar