Editing First-order logic (section)

===Completeness and undecidability===
[[Gödel's completeness theorem]], proved by [[Kurt Gödel]] in 1929, establishes that there are sound, complete, effective deductive systems for first-order logic, and thus the first-order logical consequence relation is captured by finite provability. Naively, the statement that a formula φ logically implies a formula ψ depends on every model of φ; these models will in general be of arbitrarily large cardinality, and so logical consequence cannot be effectively verified by checking every model. However, it is possible to enumerate all finite derivations and search for a derivation of ψ from φ. If ψ is logically implied by φ, such a derivation will eventually be found. Thus first-order logical consequence is [[semidecidable]]: it is possible to make an effective enumeration of all pairs of sentences (φ,ψ) such that ψ is a logical consequence of&nbsp;φ.

Unlike [[propositional logic]], first-order logic is [[Decidability (logic)|undecidable]] (although semidecidable), provided that the language has at least one predicate of arity at least 2 (other than equality). This means that there is no [[decision procedure]] that determines whether arbitrary formulas are logically valid. This result was established independently by [[Alonzo Church]] and [[Alan Turing]] in 1936 and 1937, respectively, giving a negative answer to the [[Entscheidungsproblem]] posed by [[David Hilbert]] and [[Wilhelm Ackermann]] in 1928. Their proofs demonstrate a connection between the unsolvability of the decision problem for first-order logic and the unsolvability of the [[halting problem]].

There are systems weaker than full first-order logic for which the logical consequence relation is decidable. These include propositional logic and [[monadic predicate logic]], which is first-order logic restricted to unary predicate symbols and no function symbols. Other logics with no function symbols which are decidable are the [[guarded fragment]] of first-order logic, as well as [[two-variable logic]]. The [[Bernays–Schönfinkel class]] of first-order formulas is also decidable. Decidable subsets of first-order logic are also studied in the framework of [[description logics]].