On the Wadge Reducibility of k-Partitions

Selivanov V.L.

Novosibirsk Pedagogical University (Novisibirsk)

Abstract:

We establish some results on the Wadge degrees and 
on the Boolean hierarchy of k-partitions of some spaces, 
where $k$ is a natural number. The main attention is paid 
to the Baire space, Baire domain and their close relatives. 
For the case of $Delta^0_2$-measurable k-partitions 
the structures of Wadge degrees are characterized completely. 
For many degree structures, undecidability of the first-order 
theories is shown, for any k>2. We also exdend the main facts 
about the Wagner hierarchy of regular omega-languages 
to the case of omega-regular k-partitions.