Wadge hardness in Scott spaces and its effectivization

Mostrar todas las versiones(2)

We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (ite...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Grigorieff, S.
Formato: JOUR
Materias:
Hardness
Topology
Continuous domain
Difference hierarchies
Hausdorff
Natural number
One chain
Scott topology
Chains
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_09601295_v39_n11_p_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_09601295_v39_n11_p_Becher
record_format dspace
spelling todo:paper_09601295_v39_n11_p_Becher2023-10-03T15:53:40Z Wadge hardness in Scott spaces and its effectivization Becher, V. Grigorieff, S. Hardness Topology Continuous domain Difference hierarchies Hausdorff Natural number One chain Scott topology Chains We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain. Copyright © Cambridge University Press 2014. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_09601295_v39_n11_p_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Hardness
Topology
Continuous domain
Difference hierarchies
Hausdorff
Natural number
One chain
Scott topology
Chains
spellingShingle Hardness
Topology
Continuous domain
Difference hierarchies
Hausdorff
Natural number
One chain
Scott topology
Chains
Becher, V.
Grigorieff, S.
Wadge hardness in Scott spaces and its effectivization
topic_facet Hardness
Topology
Continuous domain
Difference hierarchies
Hausdorff
Natural number
One chain
Scott topology
Chains
description We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain. Copyright © Cambridge University Press 2014.
format JOUR
author Becher, V.
Grigorieff, S.
author_facet Becher, V.
Grigorieff, S.
author_sort Becher, V.
title Wadge hardness in Scott spaces and its effectivization
title_short Wadge hardness in Scott spaces and its effectivization
title_full Wadge hardness in Scott spaces and its effectivization
title_fullStr Wadge hardness in Scott spaces and its effectivization
title_full_unstemmed Wadge hardness in Scott spaces and its effectivization
title_sort wadge hardness in scott spaces and its effectivization
url http://hdl.handle.net/20.500.12110/paper_09601295_v39_n11_p_Becher
work_keys_str_mv AT becherv wadgehardnessinscottspacesanditseffectivization
AT grigorieffs wadgehardnessinscottspacesanditseffectivization
_version_ 1807315212868517888

Ejemplares similares