---
tag: 4H7DF303WF
kind: definition
name: Determinacy
msc: ["03E60", "91A44", "03E15"]
defines: QXECDPAYTN
uses: [0G9EKM0E15, P2WS16HKD7]
sources:
  - url: https://en.wikipedia.org/wiki/Determinacy
---

## Definition

Let $A$ be a nonempty set and let $X \subseteq A^{\N}$ be a set of infinite [[sequences|0G9EKM0E15]] of elements of $A$.
The game $G(A, X)$ is played by two players, I and II.
Player I chooses $a_0 \in A$, then player II chooses $a_1 \in A$, then player I chooses $a_2 \in A$, and so on forever.
Player I wins the play $x = (a_0, a_1, a_2, \dots)$ if $x \in X$, and player II wins it otherwise.

1. A *strategy* for player I is a map $\sigma$ from the finite sequences of elements of $A$ of even length to $A$.
A strategy for player II is a map $\tau$ from the finite sequences of odd length to $A$.
2. A play *follows* $\sigma$ if $a_{2n} = \sigma(a_0, \dots, a_{2n-1})$ for all $n \ge 0$, and similarly for $\tau$ and the odd positions.
3. A strategy for a player is *winning* if that player wins every play that follows it.

The game $G(A, X)$, and the set $X$, is *determined* if player I or player II has a winning strategy.

## Remarks

Example: let $A = \N$ and $X = \set{x \in \N^{\N} : x_0 = 0}$.
The strategy of player I that plays $0$ at the first move, and anything later, is winning, so $X$ is determined.

Non-example: under the axiom of choice there is a set $X \subseteq \set{0, 1}^{\N}$ for which neither player has a winning strategy.
It is built by a diagonal argument against a well-ordering of all strategies.

At most one player can have a winning strategy: two winning strategies $\sigma$ and $\tau$ would produce a single play that both players win.
The case $A = \N$ is the main one; then $A^{\N}$ is the [[Baire space|P2WS16HKD7]] with its product topology.