Matrix hierarchies of first-order languages and their applications (Q1803010)

The first-order languages considered here are not closed under (first- order) subformulas, but are closed under other operations defined in terms of infinite matrices. This allows to construct examples of theories with subtheories of given Turing degrees. Theorem 2. There exists a hierarchy \(H\) such that for any r.e. degree of unsolvability \(\alpha\) there exists a language \(L_ \alpha\in H\) for which the \(L_ \alpha\)- theory of the variety \(\mathfrak L\) of all semigroups belongs to \(\alpha\).