Index sets for ω‐languages
Douglas Czenzer, Jeffrey B. Remmel · Mathematical logic quarterly · 2003
Abstract An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the $ \Sigma ^0 _2 $ languages, may enumerated as P0, P1, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.