Riducibilita generali per insiemi di reali

摘要

Intuitivamente, un insieme di reali A e piu semplice di un insieme di reali B se il problema di verificare l'appartenenza di un reale x ad A e riconducibile a quello di determinare l'appartenenza di x (o di un altro reale ad esso collegato) a B. In par-ticolare, diciamo che A e riducibile (con continuita) a B se esiste una funzione continua f tale che x ∈ A = f(x) ∈ B per ogni reale x, in simboli A ≤w B. (II simbolo W si deve a Wadge che inizio lo studio sistematico di questa relazione in [4].) Dunque in questo caso le funzioni continue sono usate come riduzioni tra insiemi di reali. Le classi di equivalenza della relazione di equivalenza indotta da ≤w sullo spazio di Baire (1)ω_ω vengono dette gradi di Wadg e , e il preordine ≤w induce un su di essi un ordine parziale ≤. Usando tecniche derivanti dalla teoria dei giochi infiniti, Wadge dimostro un semplice (ma fondamentale) lemma che ha giocato un ruolo importantissimo in Teoria Descrittiva degli Insiemi: AD, l'Assioma di Detertninatezza, implica che se A, B ∈ ω_ω allora (* )A ≤wB oppure ω_ω B ≤w A.Il Lemma di Wadge implica che ≤w e un ordine semi-lineare, e quindi ( *) a di solito denotata con SLO~w. Partendo da questo risultato (e grazie al successivo contribute di vari altri logici e matematici) venne data una descrizione completa della struttura dei gradi di Wadge assumendo AD + DC(R), dove DC(R) e un frammento dell'Assioma di Scelta note come Assioma delle Scelte Dipendenti sui Reali. Quest'analisi, nota oggi come Teoria di Wadge, ha portato a diverse applicazioni sia in Teoria degli Insiemi, sia in Informatica Teorica (in particolare nel campo degli automi deterministici).