Extensions and Limits of the Specker-Blatter Theorem

arXiv2206.12135MaRDI QIDQ6403040FDOQ6403040

Eldar Fischer, Johann A. Makowsky

Publication date: 24 June 2022

Abstract: The original Specker-Blatter Theorem (1983) was formulated for classes of structures $mathcalC$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol $c$, there are $n$ possible interpretations on $[n]$ for $c$. We say that a constant $c$ is {em hard-wired} if $c$ is always interpreted by the same element $jin[n]$. In this paper we show: 1. The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. 2. The Specker-Blatter Theorem does not hold already for $mathcalC$ with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers $B_{r,A}$, restricted Stirling numbers of the second kind $S_{r,A}$ or restricted Lah-numbers $L_{r,A}$. Here $r$ is an non-negative integer and $A$ is an ultimately periodic set of non-negative integers.

Mathematics Subject Classification ID

Partitions of sets (05A18) Model theory of finite structures (03C13) Enumeration in graph theory (05C30) Applications of model theory (03C98) Combinatorics (05-XX) Mathematical logic and foundations (03-XX)

This page was built for publication: Extensions and Limits of the Specker-Blatter Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403040)