Effective Wadge Hard sets

VERÓNICA BECHER; SERGE GRIGORIEFF

Luminy, Marseille, France

Congreso; Computability Complexity and Randomness; 2009

CIRM, FRANCE

The classical Wadge theory on totally discontinuous Polish spaces has been extended to $T_0$ topological spaces with Scott topologies by V. Selivanov. We present an effectivization of Wadge theory in the framework of $omega$-continuous  d.c.p.o., i.e. Scott domains. Wadge theory was originally defined with no considerations on computable strategies. The reason being that Martin´s Determinacy gives highly non computable strategies. Though Wadge Duality theorem  and the non-trivial part of the Wadge Hardness theorem fail in an effective context, an interesting part of Wadge theory still remains after effectivization. We prove that  there is an effectively Wadge hard set for each level of the Arithmetical Hierarchy,and one for each level of the Effective Difference Hierarchy. We also give, for each level, a topological characterization of effectively hard sets, and we illustrate with particularexamples. To develop the results of the paper we commit to the space $P(N)$ of all subsets of $N$ with the Scott topology, and then we transfer them to any Scott domain.