Classical and Effective Descriptive Complexities of omega-Powers

Abstract : We prove that, for each non null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers, extending previous works on the topological complexity of omega-powers. We prove effective versions of these results. In particular, for each non null recursive ordinal alpha, there exists a recursive finitary language A such that A^omega is Sigma^0_alpha-complete (respectively, Pi^0_alpha-complete). To do this, we prove effective versions of a result by Kuratowski, describing a Borel set as the range of a closed subset of the Baire space by a continuous bijection. This leads us to prove closure properties for the classes Effective-Pi^0_alpha and Effective-Sigma^0_alpha of the hyperarithmetical hierarchy in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered by the second author in [Omega-Powers and Descriptive Set Theory, Journal of Symbolic Logic, Volume 70 (4), 2005, p. 1210-1232].
Type de document :
Article dans une revue
Annals of Pure and Applied Logic, Elsevier Masson, 2009, 160 (2), pp.163-191
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00168644
Contributeur : Olivier Finkel <>
Soumis le : mardi 4 août 2009 - 15:13:21
Dernière modification le : mardi 24 avril 2018 - 13:52:32
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 13:16:44

Fichiers

omega-powers.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00168644, version 2
  • ARXIV : 0708.4176

Collections

Citation

Olivier Finkel, Dominique Lecomte. Classical and Effective Descriptive Complexities of omega-Powers. Annals of Pure and Applied Logic, Elsevier Masson, 2009, 160 (2), pp.163-191. 〈ensl-00168644v2〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

86