On Some Sets of Dictionaries Whose omega-Powers Have a Given Complexity

Abstract

A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [Omega-powers and descriptive set theory, JSL 2005] the complexity of the set of dictionaries whose associated omega-powers have a given complexity. In particular, he considered the sets $W({\bf\Si}^0_{k})$ (respectively, $W({\mathbf{\Pi }}_k^0)$, $W({\mathbf{\Delta }}_1^1)$) of dictionaries $V\subseteq 2^{\star }$ whose omega-powers are ${\bf\Si}^0_{k}$-sets (respectively, ${\mathbf{\Pi }}_k^0$-sets, Borel sets). In this paper we first establish a new relation between the sets $W({\mathbf{\Sigma }}_2^0)$ and $W({\mathbf{\Delta }}_1^1)$, showing that the set $W({\mathbf{\Delta }}_1^1)$ is "more complex" than the set $W({\mathbf{\Sigma }}_2^0)$. As an application we improve the lower bound on the complexity of $W({\mathbf{\Delta }}_1^1)$ given by Lecomte. Then we prove that, for every integer $k\ge 2$, (respectively, $k\ge 3$) the set of dictionaries $W({\mathbf{\Pi }}_{k+1}^0)$ (respectively, $W({\bf\Si}^0_{k+1})$) is "more complex" than the set of dictionaries $W({\mathbf{\Pi }}_k^0)$ (respectively, $W({\bf\Si}^0_{k})$) .

To appear in Mathematical Logic Quarterly