×

On representing concepts in finite models. (English) Zbl 0992.03043

Summary: We present a method of transferring Tarski’s technique of classifying finite order concepts by means of truth-definitions into finite model theory. The other question considered is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree \(\leq \mathbf{0}{\mathbf '}\). Finally, we consider theories of sufficiently large finite models. For a given theory \(T\) we define \(\text{sl}(T)\) as the set of all sentences true in almost all finite models for \(T\). For theories of sufficiently large models, our version of Tarski’s technique becomes practically the same as the classical one. We investigate also degrees of undecidability for theories of sufficiently large finite models. We prove for some special theory ST that its degree is stronger than \(\mathbf{0}{\mathbf '}\) but still not more than \(\Sigma^0_2\).

MSC:

03C13 Model theory of finite structures
03D25 Recursively (computably) enumerable sets and degrees
03B15 Higher-order logic; type theory (MSC2010)
03C85 Second- and higher-order model theory
03D40 Word problems, etc. in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI