Q-Wadge degrees as free structures

Issue title: Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018

Guest editors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone and Arno Pauly

Article type: Research Article

Authors: Selivanov, Victor^{; *}

Affiliations: Theoretical Programming Lab., A.P. Ershov Institute of Informatics Systems SB RAS, Russia. vseliv@iis.nsk.su

Correspondence: [*] Corresponding author. vseliv@iis.nsk.su.

Abstract: A natural extension of the Wadge hierarchy is obtained if we consider k-partitions (or even Q-partitions for a countable better quasiorder Q) of the Baire space instead of sets (i.e., 2-partitions). Natural initial segments of the Q-Wadge hierarchy were recently characterised in terms of the so called h-quasiorder on suitably iterated Q-labeled countable well founded forests. Though these characterisations are natural and constructive, their definitions are rather long and technical. In this paper, we find clear shorter characterizations as (reducts of) a kind of free structures satisfying some natural axioms. Informally, we provide short and clear axiomatisations of the initial segments.

Keywords: Wadge degree, better quasiorder, semilattice, labeled forest, free structure

DOI: 10.3233/COM-180241

Journal: Computability, vol. 9, no. 3-4, pp. 327-341, 2020