First-order logic

First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of <a href="/facts/Formal_system/KaeDAjK7">formal systems</a> used in <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, <a href="/facts/Philosophy/zAH5PVD6">philosophy</a>, <a href="/facts/Linguistics/oQuamvf2">linguistics</a>, and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>. First-order logic uses <a href="/facts/Quantification_(logic)/bgmvwxoo">quantified variables</a> over non-logical objects, and allows the use of sentences that contain variables. Rather than propositions such as "all humans are mortal", in first-order logic one can have expressions in the form "for all x, if x is a human, then x is mortal", where "for all x" is a quantifier, x is a variable, and "... is a human" and "... is mortal" are predicates. This distinguishes it from <a href="/facts/Propositional_logic/MNt5v31V">propositional logic</a>, which does not use quantifiers or <a href="/facts/Finitary_relation/JkNnVYNj">relations</a>;: 161  in this sense, propositional logic is the foundation of first-order logic.
A theory about a topic, such as <a href="/facts/Set_theory/1ptfsvUP">set theory</a>, a theory for groups, or a formal theory of <a href="/facts/Arithmetic/hvHwkbMV">arithmetic</a>, is usually a first-order logic together with a specified <a href="/facts/Domain_of_discourse/T1WRQxx6">domain of discourse</a> (over which the quantified variables range), finitely many functions from that domain to itself, finitely many <a href="/facts/Predicate_(mathematical_logic)/5WazAvKF">predicates</a> defined on that domain, and a set of axioms believed to hold about them. "Theory" is sometimes understood in a more formal sense as just a set of sentences in first-order logic.
The term "first-order" distinguishes first-order logic from <a href="/facts/Higher-order_logic/hdUhry6m">higher-order logic</a>, in which there are predicates having predicates or functions as arguments, or in which quantification over predicates, functions, or both, are permitted.: 56  In first-order theories, predicates are often associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets.
There are many <a href="/facts/Deductive_system/KaeDAjK7">deductive systems</a> for first-order logic which are both <a href="/facts/Soundness/ndpamd2A">sound</a>, i.e. all provable statements are true in all models; and <a href="/facts/Completeness_(logic)/GzK9zLnu">complete</a>, i.e. all statements which are true in all models are provable. Although the <a href="/facts/Logical_consequence/AyDXp4dn">logical consequence</a> relation is only <a href="/facts/Semidecidability/17SHPMo0">semidecidable</a>, much progress has been made in <a href="/facts/Automated_theorem_proving/vKGvuKFI">automated theorem proving</a> in first-order logic. First-order logic also satisfies several <a href="/facts/Metalogic/zfooQjCo">metalogical</a> theorems that make it amenable to analysis in <a href="/facts/Proof_theory/kopBdQn9">proof theory</a>, such as the <a href="/facts/L%25C3%25B6wenheim%25E2%2580%2593Skolem_theorem/pb72J40H">Löwenheim–Skolem theorem</a> and the <a href="/facts/Compactness_theorem/8tHVkdeK">compactness theorem</a>.
First-order logic is the standard for the formalization of mathematics into <a href="/facts/Axiomatic_system/dwMz70d5">axioms</a>, and is studied in the <a href="/facts/Foundations_of_mathematics/yjpbbUkt">foundations of mathematics</a>. <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a> and <a href="/facts/Zermelo%25E2%2580%2593Fraenkel_set_theory/UYIsPbXw">Zermelo–Fraenkel set theory</a> are axiomatizations of <a href="/facts/Number_theory/zhoa7zrc">number theory</a> and set theory, respectively, into first-order logic. No first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> or the <a href="/facts/Real_line/6eq42xX5">real line</a>. Axiom systems that do fully describe these two structures, i.e. <a href="/facts/Categorical_theory/gTmQNu12">categorical</a> axiom systems, can be obtained in stronger logics such as <a href="/facts/Second-order_logic/C138cGXQ">second-order logic</a>.
The foundations of first-order logic were developed independently by <a href="/facts/Gottlob_Frege/FXyStVYj">Gottlob Frege</a> and <a href="/facts/Charles_Sanders_Peirce/z76dNqhM">Charles Sanders Peirce</a>. For a history of first-order logic and how it came to dominate formal logic, see José Ferreirós (2001).

First-order logic open-in-new

First-order logic