Finite \(H\)-dimension does not imply expressive completeness (Q1337512)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Finite \(H\)-dimension does not imply expressive completeness
scientific article

    Statements

    Finite \(H\)-dimension does not imply expressive completeness (English)
    0 references
    9 November 1994
    0 references
    The monadic first-order language (formulas in this language are called monadic) is obtained from a given first-order language by adding a set of monadic predicates. A monadic first-order formula with a single free variable is called connective. A class of first-order structures \(K\) has \(H\)-dimension \(d\) if \(d\) is the least number such that every monadic formula is \(K\)-equivalent to a monadic formula using at most \(d\) bound variables. It is known that if a class of structures has a finite basis of connectives, then it has finite \(H\)-dimension. In this paper the other direction (a conjecture of D. Gabbay) is refuted.
    0 references
    0 references
    expressive completeness
    0 references
    monadic first-order language
    0 references
    monadic predicates
    0 references
    first-order structures
    0 references
    \(H\)-dimension
    0 references
    0 references

    Identifiers