In mathematical logic, a logic L has the finite model property (fmp for short) if any non-theorem of L is falsified by some finitemodel of L. Another way of putting this is to say that L has the fmp if for every formulaA of L, A is an L-theorem if and only ifA is a theorem of the theory of finite models of L.
If L is finitely axiomatizable (and has a recursive set of inference rules) and has the fmp, then it is decidable. However, the result does not hold if L is merely recursively axiomatizable. Even if there are only finitely many finite models to choose from (up to isomorphism) there is still the problem of checking whether the underlying frames of such models validate the logic, and this may not be decidable when the logic is not finitely axiomatizable, even when it is recursively axiomatizable. (Note that a logic is recursively enumerable if and only if it is recursively axiomatizable, a result known as Craig's theorem.)
^Leonid Libkin, Elements of finite model theory, chapter 14
January 09, 2023
finite, model, property, mathematical, logic, logic, finite, model, property, short, theorem, falsified, some, finite, model, another, putting, this, that, every, formula, theorem, only, theorem, theory, finite, models, finitely, axiomatizable, recursive, infe. In mathematical logic a logic L has the finite model property fmp for short if any non theorem of L is falsified by some finite model of L Another way of putting this is to say that L has the fmp if for every formula A of L A is an L theorem if and only if A is a theorem of the theory of finite models of L If L is finitely axiomatizable and has a recursive set of inference rules and has the fmp then it is decidable However the result does not hold if L is merely recursively axiomatizable Even if there are only finitely many finite models to choose from up to isomorphism there is still the problem of checking whether the underlying frames of such models validate the logic and this may not be decidable when the logic is not finitely axiomatizable even when it is recursively axiomatizable Note that a logic is recursively enumerable if and only if it is recursively axiomatizable a result known as Craig s theorem Example EditA first order formula with one universal quantification has the fmp A first order formula without function symbols where all existential quantifications appear first in the formula also has the fmp 1 See also EditKripke semanticsReferences EditPatrick Blackburn Maarten de Rijke Yde Venema Modal Logic Cambridge University Press 2001 Alasdair Urquhart Decidability and the Finite Model Property Journal of Philosophical Logic 10 1981 367 370 Leonid Libkin Elements of finite model theory chapter 14 Retrieved from https en wikipedia org w index php title Finite model property amp oldid 1012093485, wikipedia, wiki, book, books, library,
