Finite base property and guarded fragments
Go to home page
There are many examples of finite relation
algebras that are representable but which only have infinite
same holds for n-dimensional cylindric algebras (n>2). However, if
weaken the notion of representation, by relativising the relation
(such as relative product, or cylindrification/quantification) to some
distinguished relation, more positive results can be obtained.
See papers 1, 2 below. The arguments use a combinatorial theorem
of Herwig from model theory.
Herwig's theorem was modified in (3) below to prove that the packed
fragment of first-order logic (similar to the clique-guarded fragment)
has the finite model property. In (4) a much simpler proof is
given. It uses Grädel's result that the guarded fragment has
the finite model property (which he proved using Herwig's theorem).
Currently (June 00) available from Herwig's
home page or via Freiburg
Logik preprints page.
- Bernhard Herwig, Extending partial isomorphisms for the
small index property of many omega-categorical structures, Israel
J. Math. 107 (1998), 93-124.
- B. Herwig and D. Lascar, Extending partial isomorphisms and
the profinite topology on the free groups, Trans. Amer. Math. Soc.
352 (2000), 1985-2021.
- E. Grädel, On
the restraining power of guards, J. Symbolic Logic 64 (1999)
Robin Hirsch, Ian Hodkinson, Maarten Marx, Szabolcs
In: Logic at Work, Essays dedicated to the memory of Elena
Orlowska (ed), Studies in Fuzziness and Soft Computing, vol. 24,
Physica-Verlag, Heidelberg/New York, 1998, ISBN 3-7908-1164-5, pp.
We give a proof of completeness, decidability and finite base property
for the modal logic corresponding to the n-variable fragment of
logic, with modal semantics relativised to 'locally cubic' sets of
(worlds). All these results were already known, but the proofs we give
new and use a combinatorial theorem of Herwig.
H. Andréka, I. Hodkinson, I. Németi
J. Symbolic Logic 64 (1999) 243-267.
Using a combinatorial theorem of Herwig on extending partial
isomorphisms of relational structures, we give a simple proof that
certain classes of
algebras, including Crs, polyadic Crs, and WA, have the `finite base
and have decidable universal theories, and that any finite algebra in
class is representable on a finite set. These results were first
by Andréka and Németi.
Studia Logica 70 (2002) 205-240.
We show that the loosely guarded and packed fragments of first-order
logic have the finite model property. We use a construction of
Herwig. We point out some consequences in temporal predicate
logic and algebraic logic.
I. Hodkinson and M. Otto
Bull. Symbolic Logic 9 (2003) 387-405.
Every finite hypergraph is shown to admit a cover by a finite conformal
hypergraph. The notion of a hypergraph cover is based on homomorphisms
induce a bisimulation like back-and-forth system of local bijections
hyperedges. It is here introduced to capture the essential features of
bisimulations in the hypergraph setting. The classical hypergraph
of conformality, defined by the requirement that all induced cliques be
contained within hyperedges, thus corresponds to the collapse of clique
to plain guardedness. As far as conformality is concerned, our
can serve as a substitute in finite model theory for the
but generally infinite unravelling of hypergraphs or relational
Two immediate applications to the finite model theory of relational
structures are presented:
- The construction is used to solve an open problem about a clique
constrained strengthening of the extension property for partial
automorphisms (EPPA) of
Hrushovski, Herwig and Lascar. EPPA is thus established for the class
finite conformal structures, of any relational type. This also gives a
route to the known EPPA for the class of finite Kn-free
- Finite conformal covers can be used in a straightforward
reduction from the clique guarded fragment CGF (and the loosely guarded
fragment LGF) to the guarded fragment GF, which is adequate for finite
This gives a new simple and direct proof of the finite model property
for CGF and LGF.