Matrix hierarchies of first-order languages and their applications (Q1803010)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Matrix hierarchies of first-order languages and their applications |
scientific article |
Statements
Matrix hierarchies of first-order languages and their applications (English)
0 references
29 June 1993
0 references
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\).
0 references
variety of all semigroups
0 references
first-order languages
0 references
infinite matrices
0 references
theories with subtheories of given Turing degrees
0 references
hierarchy
0 references
r.e. degree of unsolvability
0 references