Polish group actions and computability

2009/03/05 by А. А. Иванов, Aleksander Ivanov, Ivanov, Aleksander +3
Computer Science · Mathematics · #03D45 #03E15 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D45 #msc:03E15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0903.1070

AMS LaTeX file, Section 2.2 is corrected, there are some minor changes in other places

openalex publication_date 2009/03/05 · arxiv created 2009/08/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a closed subgroup of the group of all permutations of a countably infinite set. Let X be a Polish G-space with a countable basis A of clopen sets. Each x from X defines a characteristic function f on A by f(U)=1 iff x belongs to U (where U is from A). We consider computable complexity of f and some related questions.

Related

• Complexity classes of Polishable subgroups
• Computably locally compact groups and their closed subgroups
• Descriptive complexity of subsets of the space of finitely generated groups
• Polish group actions and admissible sets
• The descriptive complexity of the set of all closed zero-dimensional\n subsets of a Polish space