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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references