Editing First-order logic (section)

==Metalogical properties==
One motivation for the use of first-order logic, rather than [[higher-order logic]], is that first-order logic has many [[metalogic]]al properties that stronger logics do not have. These results concern general properties of first-order logic itself, rather than properties of individual theories. They provide fundamental tools for the construction of models of first-order theories.

===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]].

===The Löwenheim–Skolem theorem===
The [[Löwenheim–Skolem theorem]] shows that if a first-order theory of [[cardinality]] λ has an infinite model, then it has models of every infinite cardinality greater than or equal to λ. One of the earliest results in [[model theory]], it implies that it is not possible to characterize [[countable set|countability]] or uncountability in a first-order language with a countable signature. That is, there is no first-order formula φ(''x'') such that an arbitrary structure M satisfies φ if and only if the domain of discourse of M is countable (or, in the second case, uncountable).

The Löwenheim–Skolem theorem implies that infinite structures cannot be [[categorical theory|categorically]] axiomatized in first-order logic. For example, there is no first-order theory whose only model is the real line: any first-order theory with an infinite model also has a model of cardinality larger than the continuum. Since the real line is infinite, any theory satisfied by the real line is also satisfied by some [[nonstandard model]]s. When the Löwenheim–Skolem theorem is applied to first-order set theories, the nonintuitive consequences are known as [[Skolem's paradox]].

===The compactness theorem===
The [[compactness theorem]] states that a set of first-order sentences has a model if and only if every finite subset of it has a model.<ref>Hodel, R. E., ''An Introduction to Mathematical Logic'' ([[Mineola, New York|Mineola NY]]: [[Dover Publications|Dover]], 1995), [https://books.google.com/books?id=SxRYdzWio84C&pg=PA199 p. 199].</ref> This implies that if a formula is a logical consequence of an infinite set of first-order axioms, then it is a logical consequence of some finite number of those axioms. This theorem was proved first by Kurt Gödel as a consequence of the completeness theorem, but many additional proofs have been obtained over time. It is a central tool in model theory, providing a fundamental method for constructing models.

The compactness theorem has a limiting effect on which collections of first-order structures are elementary classes. For example, the compactness theorem implies that any theory that has arbitrarily large finite models has an infinite model. Thus, the class of all finite [[Graph (discrete mathematics)|graphs]] is not an elementary class (the same holds for many other algebraic structures).

There are also more subtle limitations of first-order logic that are implied by the compactness theorem. For example, in computer science, many situations can be modeled as a [[directed graph]] of states (nodes) and connections (directed edges).  Validating such a system may require showing that no "bad" state can be reached from any "good" state. Thus, one seeks to determine if the good and bad states are in different [[connected component (graph theory)|connected components]] of the graph. However, the compactness theorem can be used to show that connected graphs are not an elementary class in first-order logic, and there is no formula φ(''x'',''y'') of first-order logic, in the [[logic of graphs]], that expresses the idea that there is a path from ''x'' to ''y''. Connectedness can be expressed in [[second-order logic]], however, but not with only existential set quantifiers, as <math>\Sigma_1^1</math> also enjoys compactness.

===Lindström's theorem===
{{Main|Lindström's theorem}}

[[Per Lindström]] showed that the metalogical properties just discussed actually characterize first-order logic in the sense that no stronger logic can also have those properties (Ebbinghaus and Flum 1994, Chapter XIII). Lindström defined a class of abstract logical systems, and a rigorous definition of the relative strength of a member of this class. He established two theorems for systems of this type:
* A logical system satisfying Lindström's definition that contains first-order logic and satisfies both the Löwenheim–Skolem theorem and the compactness theorem must be equivalent to first-order logic.
* A logical system satisfying Lindström's definition that has a semidecidable logical consequence relation and satisfies the Löwenheim–Skolem theorem must be equivalent to first-order logic.