Forbidden induced subgraphs and the Łoś-Tarski theorem (Q6545087)

A result of Los and Tarski implies that if \(C\) is the class of (finite and infinite) models of a first-order sentence \(\varphi\) and \(C\) is closed under substructures, then there is a universal sentence \(\psi\) such that \(C\) is also the class of models of \(\psi\). It is known that the result does not hold if we instead let \(C\) be the class of finite models of \(\varphi\). This paper strengthens this later ``negative'' result by proving that there is a first-order sentence \(\varphi\) in the language of graphs such that the class \(\mathrm{Graph}_{fin}(\varphi)\) of finite undirected graphs that are models of \(\varphi\) is closed under induced subgraphs but not aximatized by any universal sentence, which is equivalent to the nonexistence of a finite set of finite graphs \(F\) such that \(\mathrm{Graph}_{fin}(\varphi)\) is the class of finite graphs that do not have an induced subgraph isomorphic to a member of \(F\).\N\NThe authors then show that there is no algorithm which, for any first-order sentence \(\varphi\) such that \(\mathrm{Graph}_{fin}(\varphi)\) is closed under induced subgraphs, decides whether \(\varphi\) is equivalent, on finite graphs, to a universal sentence. Even if such a universal sentence exists, it is hard to find, since the authors also prove: There is no algorithm that, for any first-order sentence \(\varphi\) that is equivalent to a universal sentence \(\psi\) on finite graphs computes such \(\psi\). Finally, they prove that there is no computable function \(f\) such that, for all \(\varphi\) and \(\psi\) as above, \(|\psi| \leq f(|\varphi|)\) where \(|\psi|\) and \(|\varphi|\) are the lengths of \(\psi\) and \(\varphi\), respectively.