Finite conformal hypergraph covers and Gaifman cliques in finite structures
Finite conformal hypergraph covers and Gaifman cliques in finite structures
复制标题
有限共形超图覆盖和有限结构中的盖夫曼团
作者：
I. Hodkinson;M. Otto
我们为有限的超图提供了共同覆盖物的规范结构，并在关系结构的有限模型理论中呈现了两个直接应用。作为通常无限守卫的有限模型理论的部分模型。 Hypergraph在关系结构方面接受有限的保形超透明仪，我们表明，每个有限的关系结构都可以通过有限的掩护，该覆盖有限的掩护。 Hrushovski，Herwig和Lascar的局部自动形态（EPPA）的扩展特性的限制。通过将CGF中的（有限）满意度降低到（有限的）满意度的一阶逻辑CGF的有限模型属性（FMP）的证明。 ，03B70，05C65，05C69。
We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques ‐ thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a finite conformal hypergraph. In terms of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF. AMS 2000 classification: primary 03C13, secondary 03B45, 03B70, 05C65, 05C69.