Trakhtenbrot's theorem
Encyclopedia
In logic
(usually computational) and finite model theory
, Trakhtenbrot's theorem (due to Boris Trakhtenbrot
) states that the problem of validity
in the class of all finite models is undecidable
. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
(usually computational) and finite model theory
Finite model theory
Finite Model Theory is a subarea of model theory . MT is the branch of mathematical logic which deals with the relation between a formal language and its interpretations . FMT is a restriction of MT to interpretations of finite structures, i.e...
, Trakhtenbrot's theorem (due to Boris Trakhtenbrot
Boris Trakhtenbrot
Boris Avraamovich Trakhtenbrot or Boaz Trakhtenbrot is an Israeli and Russian mathematician in mathematical logic, algorithms, theory of computation and cybernetics. He worked at Akademgorodok, Novosibirsk during the 1960s and 1970s...
) states that the problem of validity
Validity
In logic, argument is valid if and only if its conclusion is entailed by its premises, a formula is valid if and only if it is true under every interpretation, and an argument form is valid if and only if every argument of that logical form is valid....
in the class of all finite models is undecidable
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
. In fact, the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable).