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