First-order logic

related topics
{math, number, function}
{theory, work, human}
{language, word, form}
{woman, child, man}
{food, make, wine}
{style, bgcolor, rowspan}

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic. First-order logic is distinguished from propositional logic by its use of quantifiers; each interpretation of first-order logic includes a domain of discourse over which the quantifiers range. Briefly, first-order logic is distinguished from higher-order logics in that quantification is allowed only over atomic entities (individuals but not sets).

There are many deductive systems for first-order logic that are sound (only deriving correct results) and complete (able to derive any logically valid implication). Although the logical consequence relation is only semidecidable, much progress has been made in automated theorem proving in first-order logic. First-order logic also satisfies several metalogical theorems that make it amenable to analysis in proof theory, such as the Löwenheim–Skolem theorem and the compactness theorem.

First-order logic is of great importance to the foundations of mathematics, where it has become the standard formal logic for axiomatic systems. It has sufficient expressive power to formalize two important mathematical theories: Zermelo–Fraenkel set theory (ZF) and first-order Peano arithmetic. However, no axiom system in first order logic is strong enough to fully (categorically) describe infinite structures such as the natural numbers or the real line. Categorical axiom systems for these structures can be obtained in stronger logics such as second-order logic.

A history of first-order logic and an account of its emergence over other formal logics is provided by Ferreirós (2001).


Full article ▸

related documents
Gödel's incompleteness theorems
Vector space
Model theory
Fourier transform
Propositional calculus
Lisp (programming language)
C (programming language)
Vienna Development Method
Group (mathematics)
Geometric algebra
Generic programming
Clifford algebra
Floating point
Euclidean vector
Ordinal number
Mathematical logic
Regular expression
Emmy Noether
Surreal number
Prime number
Singular value decomposition
Radix sort
Natural deduction