Mathematics – Logic
Scientific paper
2007-08-30
Annals of Pure and Applied Logic 2, 160 (2009) 163-191
Mathematics
Logic
Final Version, published in A.P.A.L. This paper is an extended version of a conference paper which appeared in the Proceedings
Scientific paper
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].
Finkel Olivier
Lecomte Dominique
No associations
LandOfFree
Classical and Effective Descriptive Complexities of omega-Powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Classical and Effective Descriptive Complexities of omega-Powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical and Effective Descriptive Complexities of omega-Powers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-206132