**First-order predicate calculus** or **first-order logic** (**FOL**) permits the formulation of *quantified* statements such as "there exists an *x* such that..." () or "for any *x*, it is the case that..." (), where *x* is a member of the domain of discourse. A **first-order theory** is a theory that can be axiomatised as an extension of first-order logic by adding a recursive set of first-order sentences as axioms. In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. ...
First-order logic is distinguished from higher-order logic in that it does not allow quantification over properties; i.e. it cannot express statements such as "for every *property* P, it is the case that..." () or "there exists a property P such that..." (). In mathematics, higher-order logic is distinguished from first-order logic in a number of ways. ...
Nevertheless, first-order logic is strong enough to formalize all of set theory and thereby virtually all of mathematics. Its restriction to quantification over individuals makes it difficult to use for the purposes of topology, but it is the classical logical theory underlying mathematics. It is a stronger theory than sentential logic, but a weaker theory than second-order logic. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...
History Main article: History of mathematics In addition to recognizing how to count concrete objects, prehistoric peoples also recognized how to count abstract quantities, like time -- days, seasons, years. ...
Topology (Greek topos, place and logos, study) is a branch of mathematics concerned with the study of topological spaces. ...
A propositional calculus is a formal, deduction system, or proof theory for reasoning with propositional formulas as symbolic logic. ...
In mathematical logic, second-order logic is an extension of either propositional logic or first-order logic which contains variables in predicate positions (rather than only in term positions, as in first-order logic), and quantifiers binding them. ...
## Defining first-order logic
A predicate calculus consists of - formation rules (i.e. recursive definitions for forming well-formed formulas).
- transformation rules (i.e. inference rules for deriving theorems).
- a (possibly countably infinite) set of axioms or axiom schemata.
There are two types of axioms: *logical axioms* which are valid with respect to the predicate calculus and *non-logical axioms* which are true under a special, i.e. the standard, interpretation of the theory of which they are part. For example, the non-logical Peano axioms are true under the standard interpretation of the symbolism of arithmetic, but they are not valid with respect to the predicate calculus. In logic, especially in mathematical logic, a rule of inference is a scheme for constructing valid inferences. ...
In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ...
When the set of axioms is infinite, it is required that there is an algorithm which can decide for a given well-formed formula whether it is an axiom or not. Furthermore, there should be an algorithm which can decide whether a given application of an inference rule is correct or not. Flowcharts are often used to represent algorithms. ...
## Vocabulary The "vocabulary" is composed of - Uppercase letters P, Q, R,... which are predicate variables.
- Lowercase letters a, b, c,... which are (individual) constants.
- Lowercase letters x, y, z,... which are (individual) variables.
- Lowercase letters f, g, h,... which are function variables.
- Symbols denoting logical operators: ¬ (logical not), (logical and), (logical or), → (logical conditional), ↔ (logical biconditional).
- Symbols denoting quantifiers: (universal quantification), (existential quantification).
- Left and right parenthesis.
Some symbols may be omitted as primitive and taken as abbreviations instead; e.g. (P ↔ Q) is an abbreviation for (P → Q) (Q → P). The minimum number of operators and quantifiers needed is three; for example, ¬, , and suffice. A **term** is a constant, variable, or function symbol of n≥0 arguments. Negation, in its most basic sense, changes the truth value of a statement to its opposite. ...
AND Logic Gate Logical conjunction (usual symbol and) is a logical operator that results in true if both of the operands are true. ...
OR Logic Gate Logical disjunction (usual symbol or) is a logical operator that results in true if either of the operands is true. ...
In logical calculus of mathematics, the logical conditional (also known as the material implication, sometimes material conditional) is a binary logical operator connecting two statements, if p then q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ...
In logical calculus of mathematics, logical biconditional is a logical operator connecting two statements to assert, p if and only if q where p is a hypothesis (or antecedent) and q is a conclusion (or consequent). ...
In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ...
In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ...
## Formation rules The set of well-formed formulas (*wff*s) is recursively defined by the following rules: **Simple and complex predicates** If P is an *n*-adic (*n* ≥ 0) predicate, then *P**a*_{1},...,*P**a*_{n} is well-formed. If *n* ≤ 1, P is atomic. **Inductive Clause I:** If φ is a *wff*, then ¬ φ is a *wff*. **Inductive Clause II:** If φ and ψ are *wff*s, then , , (φ → ψ), (φ ↔ ψ) are *wff*s. **Inductive Clause III:** If φ is a *wff* containing a free instance of variable *x*, then and are *wff*s. (Then any instance of *x* is said to be bound — not free — in and .) **Closure Clause:** Nothing else is a *wff*. Binding is: A type of knot, see binding (knot). ...
## Transformation (inference) rules Modus ponens suffices as the sole rule of inference. If there are axiom schemata, then a rule of substitution is also required. Modus ponens (Latin: mode that affirms) is a valid, simple argument form (often abbreviated to MP): If P, then Q. P. Therefore, Q. or in logical operator notation: where represents the logical assertion. ...
## Calculus The predicate calculus is an extension of the propositional calculus. If the propositional calculus is defined with eleven axioms and one inference rule (modus ponens), not counting some auxiliary laws for the logical equivalence operator, then the predicate calculus can be defined by appending four additional axioms and one additional inference rule. The propositional calculus is a formal deduction system whose atomic formulas are propositional variables. ...
Modus ponens (Latin: mode that affirms) is a valid, simple argument form (often abbreviated to MP): If P, then Q. P. Therefore, Q. or in logical operator notation: where represents the logical assertion. ...
In logic, statements p and q are logically equivalent if they have the same logical content. ...
### Axiomatic extension The following four logical axioms characterize a predicate calculus: - PRED-1:
- PRED-2:
- PRED-3:
- PRED-4:
These are actually axiom schemata, because the predicate letters *W* and *Z* in them can be replaced by any other predicate letters, without altering the validity of these formulae. In symbolic logic, it is sometimes inconvenient or impossible to express an axiomatic system in a finite number of axioms. ...
### Inference rule The inference rule called Universal Generalization is characteristic of the predicate calculus. It can be stated as Generalization is an inference rule of Predicate Calculus which states that: If is true (valid) then so is . ...
where *Z(x)* is supposed to stand for an already-proven theorem of predicate calculus and ∀xZ(x) is its closure with respect to the variable x. The predicate letter Z can be replaced by any other predicate letter. Notice that Generalization is analogous to the Necessitation Rule of modal logic, which is Modal logic, or (less commonly) intensional logic is the branch of logic that deals with sentences that are qualified by modalities such as can, could, might, may, must, possibly, and necessarily, and others. ...
- .
## Metalogical theorems of first-order logic Some important metalogical theorems are listed below in bulleted form. - Unlike the Propositional calculus, first-order logic is undecidable. There is provably no decision procedure for determining for an arbitrary formula P, whether or not P is valid (see Halting problem). (Results came independently from Church and Turing.)
- The decision problem for validity is semidecidable. As Gödel's completeness theorem shows, for any
**valid** formula P, P is provable. - Monadic predicate logic (i.e., predicate logic with only predicates of one argument) is decidable.
The propositional calculus is a formal deduction system whose atomic formulas are propositional variables. ...
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of an algorithm and its initial input, determine whether the algorithm, when executed on this input, ever halts (completes). ...
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ...
Alan Turing, often considered the father of modern computer science. ...
Gödels completeness theorem is a fundamental theorem in mathematical logic proved by Kurt Gödel in 1929. ...
## See also - Gödel's incompleteness theorem
In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...
## References - Article on classical logic (
*http://plato.stanford.edu/entries/logic-classical/*) by Stewart Shapiro at the Stanford Enclyclopedia of Philosophy, which covers the definition, model theory and soundness and completness results for first-order logic characterised in a natural deduction style. - Introduction to mathematical logic (
*http://www.ltn.lv/~podnieks/*) by Karl Podnieks. - Metamath (
*http://us.metamath.org/index.html*): a project to construct mathematics using an axiomatic system based on propositional calculus, predicate calculus, and set theory |