Search

Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be inter- preted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced sub- graph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.

We present a new proof of the generalized Łoś-Tarski theorem (\(\mathsf {GLT}({k})\)) from [6], over arbitrary structures. Instead of using \(\lambda \)-saturation as in [6], we construct just the “required saturation” directly using ascending chains of structures. We also strengthen the failure of \(\mathsf {GLT}({k})\) in the finite shown in [7], by strengthening the failure of the Łoś-Tarski theorem in this context. In particular, we prove that not just universal sentences, but for each fixed k, even \(\varSigma ^0_2\) sentences containing k existential quantifiers fail to capture hereditariness in the finite. We conclude with two problems as future directions, concerning the Łoś-Tarski theorem and \(\mathsf {GLT}({k})\), both in the context of all finite structures.

We present a logic-based combinatorial property of classes of finite structures that allows an effective generalization of the Łoś-Tarski preservation theorem to hold over classes satisfying the property. The well-studied classes of words and trees, and structures of bounded tree-depth are shown to satisfy the property. We also show that starting with classes satisfying this property, the classes generated by applying composition operations like disjoint union, cartesian and tensor products, inherit the property. We finally show that all classes of structures that are well-quasi-ordered under the embedding relation satisfy a natural generalization of our property.

We investigate a model-theoretic property that generalizes the classical notion of preservation under substructures. We call this property preservation under substructures modulo bounded cores, and present a syntactic characterization via \(\Sigma_2^0\) sentences for properties of arbitrary structures definable by FO sentences. Towards a sharper characterization, we conjecture that the count of existential quantifiers in the \(\Sigma_2^0\) sentence equals the size of the smallest bounded core. We show that this conjecture holds for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the conjecture fails, but for which the classical Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.