structural:reformatting, structural:summarization
Fragments

By default, the citations in the section are from Pratt-Hartmann (2023).

The classical Entscheidungsproblem asks that, given a first-order formula, whether it is true in all models. The finitary problem asks whether it is true in all finite models. Trakhtenbrot's theorem shows that this is also undecidable.

Some notations: S a t (Φ) {\displaystyle {\rm {{Sat}(\Phi)}}} means the problem of deciding whether there exists a model for a set of logical formulas Φ {\displaystyle \Phi }. F i n S a t (Φ) {\displaystyle {\rm {{FinSat}(\Phi)}}} is the same problem, but for finite models. The S a t {\displaystyle {\rm {Sat}}} -problem for a logical fragment is called decidable if there exists a program that can decide, for each Φ {\displaystyle \Phi } finite set of logical formulas in the fragment, whether S a t (Φ) {\displaystyle {\rm {{Sat}(\Phi)}}} or not.

There is a hierarchy of decidabilities. On the top are the undecidable problems. Below it are the decidable problems. Furthermore, the decidable problems can be divided into a complexity hierarchy.