Questions tagged [determinacy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
56 views

Uniformization and functions on Turing degrees

Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ? $\mathcal{D}_t$ is the set of Turing ...
6 votes
0 answers
108 views

From HODs to corresponding models of AD

If $M$ is HOD of a model $N$ of $\text{AD}^+ + V=L(P(ℝ))$, what kind of forcing construction in $M$ gives back such an $N$? HODs for $\text{AD}^+ + V=L(P(ℝ))$ are conjectured (and under anti-large ...
6 votes
0 answers
146 views

Complexity of transfinite 5-in-a-row and other games

Suppose that 5-in-a-row is played on an infinite board, and after an infinite number of moves, if no one won yet and there is an empty square, the game just continues. At limit steps, it is the first ...
4 votes
0 answers
103 views

Closure of a pointclass under universal real quantification

Let us assume $\mathsf{AD}^+$ and let $\Gamma$ be a pointclass such that $P(\mathbb{R})\cap L(\Gamma)=\Gamma$ and $L(\Gamma)\models\mathsf{AD}_\mathbb{R}+\mathsf{DC}$. Since the cofinality of $o(\...
7 votes
3 answers
427 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 ...
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 votes
0 answers
178 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 ...
10 votes
1 answer
221 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 ...
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 ...
13 votes
1 answer
449 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. ...
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, ...
2 votes
0 answers
257 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 ...
7 votes
0 answers
247 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^{<\...
4 votes
1 answer
966 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 ...
5 votes
1 answer
472 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 ...
8 votes
0 answers
162 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 ...
12 votes
1 answer
426 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 ...
4 votes
1 answer
144 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(\...
9 votes
0 answers
243 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 ...
8 votes
0 answers
164 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 ...
9 votes
0 answers
234 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 $\...
10 votes
0 answers
209 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 ...
2 votes
0 answers
136 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 ...
9 votes
0 answers
301 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 ...
2 votes
0 answers
95 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})$,...
17 votes
1 answer
750 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 $...
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 ...
6 votes
1 answer
246 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 ...
7 votes
1 answer
332 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 ...
3 votes
1 answer
147 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 ...
7 votes
0 answers
220 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 ...
12 votes
0 answers
492 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 ...
14 votes
1 answer
803 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 ...
2 votes
1 answer
194 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 ...
3 votes
1 answer
286 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 ...
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 ...
12 votes
0 answers
349 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 ...
9 votes
0 answers
253 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 "...
2 votes
0 answers
189 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: ...
5 votes
0 answers
239 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 ...
6 votes
1 answer
255 views

Forcing over models of determinacy

Consider a ctm $\mathfrak{M}$ of $ZF+AD^+$. Is it possible to force over $\mathfrak{M}$ to get a model of ZFC which satisfies further the following: Every projectively definable family of sets of ...
12 votes
2 answers
686 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 ...
0 votes
0 answers
157 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 ...
4 votes
1 answer
231 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)^\...
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. ...
3 votes
3 answers
676 views

Determinacy interchanging the roles of both players

Let me refer to Jech's "Set Theory" Chap. 33 Determinacy: "With each subset A of $\omega^\omega$ we associate the following game $G_A$, played by two players I and II. First I chooses a natural ...
11 votes
1 answer
645 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 ...
2 votes
1 answer
311 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 (...
9 votes
1 answer
705 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 ...
3 votes
2 answers
358 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 $\...