We prove that for every countable ordinal $\alpha$ one cannot decide whether a given infinitary rational relation is in the Borel class ${\Sigma }_{\alpha }^{\mathbf{0}}$ (respectively ${\Pi }_{\alpha }^{\mathbf{0}}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a ${\Sigma }_{\mathbf{1}}^{\mathbf{1}}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether...

We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class ${\Sigma }_{\alpha }^{\mathbf{0}}$ (respectively ${\Pi }_{\alpha }^{\mathbf{0}}$). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a ${\Sigma }_{\mathbf{1}}^{\mathbf{1}}$-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide...