Locally finite ω‐languages and effective analytic sets have the same topological complexity

Local sentences and the formal languages they define were introduced by Ressayre in [28][J. P. Ressayre, 1988]. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal α < ω 1 CKthere exist someΣ α 0 ‐complete and someΠ α 0 ‐complete locally finite ω‐languages, and the supremum of the set of Borel ranks of locally finite ω‐languages is the ordinal γ 2 1 , which is strictly greater than the first non‐recursive ordinal ω 1 CK . This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet [30][P. Simonnet, 1992] and also by Duparc, Finkel, and Ressayre in [5][J. Duparc, 2001]. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system ZFC . Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are Π 2 1 ‐complete, hence highly undecidable.