En la teoría descriptiva de conjuntos , dentro de las matemáticas , los grados Wadge son niveles de complejidad para conjuntos de reales . Los conjuntos se comparan mediante reducciones continuas . La jerarquía de Wadge es la estructura de los grados de Wadge. Estos conceptos llevan el nombre de William W. Wadge.
Supongamos que y son subconjuntos del espacio de Baire ω ω . Entonces Wadge es reducible a o ≤ W si hay una función continua en ω ω con . El orden Wadge es el preorden o cuasiorden de los subconjuntos del espacio de Baire. Las clases de equivalencia de conjuntos bajo este preorden se llaman grados Wadge , el grado de un conjunto se denota por [ ] W . El conjunto de grados de Wadge ordenados por el orden de Wadge se denomina jerarquía de Wadge .
Las propiedades de los grados Wadge incluyen su coherencia con medidas de complejidad expresadas en términos de definibilidad. Por ejemplo, si ≤ W y es una intersección contable de conjuntos abiertos , entonces también lo es . Lo mismo funciona para todos los niveles de la jerarquía de Borel y la jerarquía de diferencias . La jerarquía de Wadge juega un papel importante en los modelos del axioma de determinabilidad . Un mayor interés en los títulos de Wadge proviene de la informática , donde algunos artículos han sugerido que los títulos de Wadge son relevantes para la complejidad algorítmica .
El lema de Wadge establece que bajo el axioma de determinabilidad ( AD ), para dos subconjuntos cualesquiera del espacio de Baire, ≤ W o ≤ W ω ω \ . [1] La afirmación de que el lema de Wadge es válido para conjuntos en Γ es el principio de ordenamiento semilineal para Γ o SLO(Γ). CualquierEl orden semilineal define un orden lineal en los complementos de módulo de las clases de equivalencia. El lema de Wadge se puede aplicar localmente a cualquier clase de puntos Γ, por ejemplo los conjuntos de Borel , los conjuntos Δ 1 n , los conjuntos Σ 1 n o los conjuntos Π 1 n . Se deduce de la determinación de diferencias de conjuntos en Γ. Dado que la determinación de Borel se demuestra en ZFC , ZFC implica el lema de Wadge para conjuntos de Borel.
El lema de Wadge es similar al lema del cono de la teoría de la computabilidad.
El juego Wadge es un juego infinito simple descubierto por William Wadge (se pronuncia "salario"). Se utiliza para investigar la noción de reducción continua para subconjuntos del espacio de Baire. Wadge había analizado la estructura de la jerarquía de Wadge para el espacio de Baire con juegos en 1972, pero publicó estos resultados sólo mucho más tarde en su tesis doctoral. En el juego Wadge , el jugador I y el jugador II juegan cada uno con números enteros, y el resultado del juego se determina comprobando si las secuencias x e y generadas por los jugadores I y II están contenidas en los conjuntos A y B , respectivamente. El jugador II gana si el resultado es el mismo para ambos jugadores, es decir, está dentro si y sólo si está dentro . El jugador I gana si el resultado es diferente. A veces esto también se llama juego de Lipschitz , y la variante en la que el jugador II tiene la opción de pasar un número finito de veces se llama juego Wadge.
Supongamos que el juego está determinado . Si el jugador I tiene una estrategia ganadora, entonces esto define un mapa continuo (incluso Lipschitz ) que se reduce al complemento de , y si, por otro lado, el jugador II tiene una estrategia ganadora, entonces tiene una reducción de a . Por ejemplo, supongamos que el jugador II tiene una estrategia ganadora. Asigne cada secuencia x a la secuencia y en la que juega el jugador II si el jugador I juega la secuencia x y el jugador II sigue su estrategia ganadora. Esto define un mapa continuo f con la propiedad de que x está en si y sólo si f ( x ) está en .
Martin y Monk demostraron en 1973 que AD implica que la orden de Wadge para el espacio de Baire está bien fundada . Por lo tanto, bajo AD, los complementos de módulo de las clases Wadge forman un orden de pozo. El rango Wadge de un conjunto es el tipo de orden del conjunto de complementos de módulo de grados Wadge estrictamente por debajo de [ ] W . Se ha demostrado que la longitud de la jerarquía Wadge es Θ . Wadge también demostró que la longitud de la jerarquía de Wadge restringida a los conjuntos de Borel es φ ω 1 (1) (o φ ω 1 (2) dependiendo de la notación), donde φ γ es la γésima función de Veblen con base ω 1. (en lugar del habitual ω).
En cuanto al lema de Wadge, esto es válido para cualquier clase de puntos Γ, asumiendo el axioma de determinabilidad . Si asociamos con cada conjunto la colección de todos los conjuntos estrictamente debajo de la jerarquía Wadge, esto forma una clase de puntos. De manera equivalente, para cada ordinal α ≤ θ la colección W α de conjuntos que aparecen antes de la etapa α es una clase de puntos . Por el contrario, cada clase de puntos es igual a algún α . Se dice que una clase de puntos es autodual si está cerrada bajo complementación. Se puede demostrar que W α es autodual si y sólo si α es 0, un ordinal sucesor par o un ordinal límite de cofinalidad contable .
Nociones similares de reducción y grado surgen al reemplazar las funciones continuas por cualquier clase de funciones F que contenga la función identidad y esté cerrada bajo composición . Escribe ≤ F si es para alguna función en F . Cualquier clase de funciones de este tipo determina nuevamente un preorden en los subconjuntos del espacio de Baire. Los grados dados por funciones de Lipschitz se denominan grados de Lipschitz y los grados de funciones de Borel grados de Borel-Wadge .
![{\displaystyle A=f^{-1}[B]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e9a5bdfb323be7b7e7abf1373e8ec2472113e57)
