En la teoría descriptiva de conjuntos , dentro de las matemáticas , los grados de Wadge son niveles de complejidad para conjuntos de números reales . Los conjuntos se comparan mediante reducciones continuas . La jerarquía de Wadge es la estructura de los grados de Wadge. Estos conceptos reciben su nombre de William W. Wadge.
Supóngase 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 de Wadge es el preorden o cuasiorden en los subconjuntos del espacio de Baire. Las clases de equivalencia de conjuntos bajo este preorden se denominan grados de 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 de Wadge incluyen su consistencia 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 determinación . Otro interés en los grados de Wadge proviene de la ciencia informática , donde algunos artículos han sugerido que los grados de Wadge son relevantes para la complejidad algorítmica .
El lema de Wadge establece que bajo el axioma de determinación ( 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 ordenación semilineal para Γ o SLO(Γ). CualquierEl orden semilineal define un orden lineal en las clases de equivalencia módulo complementos. El lema de Wadge se puede aplicar localmente a cualquier clase puntual Γ, 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 las diferencias de conjuntos en Γ. Dado que la determinación de Borel se prueba en ZFC , ZFC implica el lema de Wadge para los conjuntos de Borel.
El lema de Wadge es similar al lema del cono de la teoría de computabilidad.
El juego de Wadge es un juego infinito simple utilizado 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 solo mucho más tarde en su tesis doctoral. En el juego de Wadge , el jugador I y el jugador II juegan por turno 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á en si y solo si está en . El jugador I gana si el resultado es diferente. A veces, esto también se llama juego de Lipschitz , y la variante donde el jugador II tiene la opción de pasar un número finito de veces se llama juego de Wadge.
Supóngase que el juego está determinado . Si el jugador I tiene una estrategia ganadora, entonces esto define una función continua (incluso Lipschitz ) que se reduce al complemento de , y si por otro lado el jugador II tiene una estrategia ganadora entonces tienes una reducción de a . Por ejemplo, supóngase que el jugador II tiene una estrategia ganadora. Asigna 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 una función continua f con la propiedad de que x está en si y solo si f ( x ) está en .
Martin y Monk demostraron en 1973 que AD implica que el orden de Wadge para el espacio de Baire está bien fundado . Por lo tanto, bajo AD, los complementos módulo de las clases de Wadge forman un buen orden. El rango de Wadge de un conjunto es el tipo de orden del conjunto de grados de Wadge módulo complementos estrictamente por debajo de [ ] W . Se ha demostrado que la longitud de la jerarquía de 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 en base ω 1 (en lugar del ω habitual).
En cuanto al lema de Wadge, esto es válido para cualquier clase puntual Γ, suponiendo el axioma de determinación . Si asociamos con cada conjunto la colección de todos los conjuntos estrictamente por debajo en la jerarquía de Wadge, esto forma una clase puntual. De manera equivalente, para cada ordinal α ≤ θ la colección W α de conjuntos que aparecen antes de la etapa α es una clase puntual . A la inversa, cada clase puntual es igual a algún α . Se dice que una clase puntual es autodual si está cerrada bajo complementación. Se puede demostrar que W α es autodual si y solo 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 . Escriba ≤ F si 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 las funciones de Lipschitz se denominan grados de Lipschitz , y los grados de las funciones de Borel se denominan grados de Borel–Wadge .
![{\displaystyle A=f^{-1}[B]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e9a5bdfb323be7b7e7abf1373e8ec2472113e57)
