4 votos

Juego de cobertura en Borel. Prueba de determinación.

Estaba leyendo la introducción a la prueba real de Borel Determinación en Kechris' "Clásica Descriptivo de la Teoría de conjuntos". Aquí hay un extracto: enter image description here

Lo que no entiendo es por qué definimos $\varphi$ , de esta manera ¿por qué debería ser substancially diferente de $\pi$. Que por supuesto son diferentes, ya que, como voy a explicar, su dominio es muy diferente, pero su imagen es básicamente el mismo, como voy a argumentar. En primer lugar vamos a definir con precisión qué es una estrategia (wlog para el primer jugador I) en $G(T,X)$. Una estrategia de $\sigma$ es una poda subárbol $\sigma \subseteq T$, tal que:

  • $\exists! s_0$ s.t. $(s_0) \in \sigma$
  • $\forall (s_0,s_1,\dots,s_{2n}) \in \sigma \ [(s_0,s_1,\dots,s_{2n},s_{2n+1}) \in T \Rightarrow (s_0,s_1,\dots,s_{2n},s_{2n+1}) \in \sigma]$
  • $\forall (s_0,s_1,\dots,s_{2n-1}) \in \sigma \ \exists! (s_0,s_1,\dots,s_{2n-1},s_{2n}) \in T [(s_0,s_1,\dots,s_{2n-1},s_{2n}) \in \sigma]$

Intuitivamente, la estrategia de el primer jugador debe tomar en cuenta cada posible movimiento del segundo jugador y debe tener una única respuesta a cada movimiento de su. Vamos a denotar por $ \Sigma(T)$ el conjunto de todas las estrategias más $T$ y $\Sigma_n (T)$ el conjunto de todos los parciales de las estrategias de longitud $n$. A continuación, podemos ver $\varphi$ como una función de $$\varphi: \Sigma(T') \cup \Sigma_n (T') \rightarrow \Sigma(T) \cup \Sigma_n (T)$$

de tal forma que:

  1. $\varphi(\Sigma_n (T')) \subseteq \Sigma_n (T)$ (que se envía parcial de estrategias de longitud n parcial de las estrategias de la misma longitud)
  2. $\varphi(\Sigma (T')) \subseteq \Sigma(T)$
  3. Dado $\sigma_n \in \Sigma_n (T')$ e $\sigma_m \in \Sigma_m (T')$ con $\sigma_n \subseteq \sigma_m$ entonces tenemos $\varphi(\sigma_n) \subseteq \varphi(\sigma_m)$
  4. Dado $\sigma \in \Sigma(T')$ entonces $\varphi(\sigma) = \bigcup_n \varphi(\sigma|_n)$ con $\sigma|_n$ denota el n-ésimo parcial de la estrategia inducida por $\sigma$.

Condición iv) del texto también pide que:

  1. Para todas las estrategias de $\sigma \in \Sigma(T')$ tenemos $[\varphi(\sigma)] \subseteq \pi([\sigma])$

Así que sé que yo reclamo que, dado lo que acabo de escribir (que representan fielmente lo que está escrito en Kechris libro), para todas las estrategias (y parcial de estrategias) $\sigma$ tenemos $\varphi(\sigma) = \pi(\sigma)$. De hecho, tenemos que por 5) $[\varphi(\sigma)]\subseteq \pi([\sigma]) = [\pi(\sigma)]$. A continuación, vamos a notar que, dado $s \in \varphi(\sigma)$, ya que cada estrategia es una poda de árbol, entonces tenemos que $\exists x \in [\varphi(\sigma)]$ s.t. $s = x|_n$. Por otra parte, desde la $x$ también pertenece a $[\pi(\sigma)]$ tenemos que $x|_n \in \pi(\sigma)$ y, por tanto, $s \in \pi(\sigma)$. Así que hemos de mostrar que $$\varphi(\sigma) \subseteq \pi(\sigma)$$. Now we notice also that $$\pi(\Sigma(T')) \subseteq \Sigma(T)$$ So also $\pi$ sends (partial) strategies to (partial) strategies. This is not a direct consequence of the definition of $\pi$, which by itself does not guarantee this, but by the requirement iv) of the text (the fifth point I've written) we need to assume this. Otherwise the only way $\pi(\sigma)$ has to not be a strategy is to avoid to specify some possible player II's moves (in some odd layer), but in this case $\varphi(\sigma)$, given what we've just said ($\varphi(\sigma) \subseteq \pi(\sigma)$), needs to avoid to specify those same moves, in contradition with its being a strategy (by 2.). Said this I claim that, given two strategies $\sigma \theta \en \Sigma (T)$ with $\sigma \subseteq \theta$ then $\sigma = \theta$. Esto es fácil de demostrar por inducción:

  • $(a_0) \in \theta \Rightarrow (a_0) \in \sigma$, esta es la base para la inducción
  • Dado que $\sigma|_{n-1} = \theta|_{n-1}$ , y dada la definición de la estrategia y que por hipótesis de $\sigma \subseteq \theta$, es evidente que, tanto al $n$ es incluso (jugador que tiene que jugar) o impar, $\sigma|_n = \theta|_n$

Así que terminamos con $\varphi(\sigma) = \pi(\sigma)$ para todas las estrategias de $\sigma \in \Sigma(T')$. Entonces, si lo que he escrito en la derecha, ¿por qué no podemos definir un Juego que Cubre de la siguiente manera:

Una cubierta de $T$ es un par $(\tilde{T}, \pi)$ donde:

  1. $\tilde{T}$ es un no-vacío poda de árboles (en algunos $\tilde{A}$)
  2. $\pi: \tilde{T} \rightarrow T$ es monotono con $length(s) = length(\pi(s))$. Por lo tanto $\pi$ da lugar a un continuo (en realidad de Lipschitz) la función de $[\tilde{T}]$ a $[T]$ también se denota como $\pi$.

Estrategias de $\tilde{\sigma} \in \Sigma(\tilde{T})$ son enviados a $\pi(\tilde{\sigma})$ que va a ser una estrategia en la $T$. $\pi$ en estrategias de asignación satisface todos los requisitos especificados en la definición anterior con respecto a $\varphi$. Así

  • $\pi$ mapas parciales estrategias parcial de estrategias en un tono monótono y longitud de la preservación de la forma.
  • De curso $[\pi(\tilde{\sigma})] = \pi([\tilde{\sigma}])$

Lo que está mal con esta nueva definición de la cobertura?

EDITAR: E incluso si lo escribí antes de la introducción de esta nueva definición es errónea, ¿por qué no usar esta nueva definición, sin embargo? Mi intuición con respecto a la definición de Juego que Cubre es que las peticiones de más de $\pi$ (continua y la longitud de la conservación) son necesarios para tratar con k-revestimientos y unravelings, pero cuando se trata de a $\varphi$ nuestra única preocupación es que los mapas de estrategias en las estrategias y, más importante, la ganancia de estrategias en estrategias ganadoras. Por lo tanto, incluso si mi argumento es erróneo, y $\pi$ no cubre todos los posibles $\varphi$ que satisface el libro de la definición, ¿por qué nos preocupamos? La estrategia de asignación proporcionada por $\pi$ ya que hace el trabajo.

2voto

Uno de los problemas con su argumento es que, en general, $\pi$ no necesita enviar estrategias para estrategias. Una de las $\pi$s que aparecen en la prueba de Martin del teorema en Kechris (Lema 20.7, en el caso de $0$-revestimientos) tiene la siguiente forma: $$ \pi((x_0,A),(x_1,B),x_2,\dots,x_l)) = (x_0,\dots,x_l). $$ No es en absoluto evidente que la imagen directa por $\pi$ de una estrategia de $\sigma$ para el Jugador I en $T'$ es una estrategia, ya que el segundo movimiento de la I en juego en $T'$ más probablemente depende de lo que el objeto de $B$ es. Esta información es ignorada por la proyección de $\pi$, y, por tanto, $\pi(\sigma)$ probablemente contendrá dos sucesores de $(x_0,x_1)$.

Otra cosa es que no está tan claro es el de la igualdad $[\pi(\sigma)] = \pi([\sigma])$; desde el principio, se sospecha que la imagen de un conjunto cerrado es nuevo cerrado. Más concretamente, no me sentido tan obvio el hecho de que una obra de teatro en $[\pi(\sigma)]$ debe surgir como la imagen de una obra de acuerdo a $\sigma$.

En una nota de lado, de nuevo su especificación de $\phi$ es imprecisa; debe ser como esto: $$ \estilo de texto\varphi: \Sigma(T') \cup \bigcup_n\Sigma_n (T') \rightarrow \Sigma(T) \cup \bigcup_n\Sigma_n (T). $$

Por último, debe ser digno de mirar en Gowers' de la cuenta de la prueba en su blog; el esclarecimiento de la función de $\varphi$ (llamado $\psi$ no) tiene lugar en el tercer post de la serie.


Nota: voy a dejar mi mayor respuesta de abajo; la pregunta era un poco desfigurado, por lo que no es relevante, pero me siento reacio a borrar mi anterior trabajo.


Permítanme en primer lugar señalar que la definición del dominio de $\varphi$ se ve un poco extraño. Parece que lo que se está utilizando a continuación es algo así como $$ \mathcal{U}(T) = \estilo de texto\bigcup\{\{\sigma\}\times\sigma : \sigma \en \Sigma(T)\}, $$ desde que escribir $\varphi(s)=\varphi(\sigma,s)$ donde $s\in\sigma$. Creo que aquí es donde la confusión radica: $\varphi$ no puede ser interpretado como un mapa de secuencias de secuencias. Realmente envía finito árboles (como en el parcial de estrategias en Kechris) a lo finito árboles de la misma altura. Por tanto, no tiene sentido escribir algo como "$\varphi((s_0,s_1))$."

Un ejemplo de esto podría ser dada de la siguiente manera. Considere la posibilidad de un juego en $\mathbb{N}$, y dos estrategias para el Jugador I: $\sigma$ instruye a "jugar a la 1 siempre;" e $\sigma'$ estados "si el primer movimiento de su oponente es de 2, mover 2 en adelante; de lo contrario, jugar 1 siempre". Ahora $\varphi$ pueden mapa de estrategias de acuerdo a "cambiar la mueve en respuesta a un 0 en la primera jugada del Jugador II con aquellos en respuesta a un 2 en el que se mueven." Esta definición es monotono como sea necesario, pero teniendo en cuenta $\varphi(\sigma)$ e $\varphi(\sigma')$ debe quedar claro que no existe una opción para algo como "$\varphi((1,0,1))$."

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X