Calculation of the predicates

The calculation of the first order predicates , or calculation of the relations , or logical first order , or quite simply calculation of the predicates is a formalization of the language of mathematics suggested by the logicians of the beginning of the 20th century.

The feature characteristic of first order logic is the introduction of a whole of symbols indicating of the variable , of an indicating whole of symbols of the functions , of an indicating whole of symbols of the Prédicats , as well as logical connectors and two symbols $\ forall$ and $\ exists$ called quantifiers. That thus makes it possible to formulate statements such as, “Any X is P” and “There exists X such as for all there xRy”, in symbols, $\ forall X (Px)$ and $\ exists X \ forall there (X R there)$ .

The purpose of the logical formulas deduced from this calculation of the predicates are to apply to any model, i.e. any unit in which the variables, the functions, the predicates of calculation represent elements of the unit respectively, functions of this whole in itself, and the parts of this unit. The predicates represent qualities, if they are in a place (unary), or relations N - surfaces, between N individuals of this unit. These concepts will be specified in the continuation of this article.

The Calcul of the proposals is a reduced version of the calculation of the predicates, without the quantifiers $\ forall$ and $\ exists$ . It is very useful in particular in data processing but is not enough to formalize all the reasoning.

One speaks about first order logic in opposition to the Logiques of a higher nature, where one can quantify as well the variables as the predicates or the functions.

Formation of a formula of the calculation of the first order predicates

Syntax

This section gives a short presentation of the grammar of the calculation of the predicates in a formal language usually used in traditional Logique by the majority of the mathematicians. But the calculation of the predicates is not limited to the purely mathematical theories. The article Prédicat gives a less formal presentation, in a semi-natural language, which shows more clearly why the grammar of the predicates is universal.

One gives oneself a definite language $L$ by:

$V$ a whole of symbols called variable , always infinite.
$C$ a whole of symbols called constant , possibly vacuum.
$P$ a whole of symbols of predicates
$F$ a whole of symbols of functions , possibly empty.

Each symbol of predicate or function has a arite (a strictly positive entirety) which determines the number of arguments or objects to which it is applied.

the symbols $\ forall$ ( whatever the ) and $\ exists$ ( there exists ), called quantifiers
the symbols $\ lnot$ ( not ), $\ land$ ( and ), $\ lor$ ( or ) and $\ to$ ( implies ), which is the logical connectors calculation of the proposals.
symbols of punctuation ")" and " (".

One could be satisfied with only one quantifier $\ forall$ and two logical connectors $\ lnot$ and $\ land$ by defining the other connectors and quantifier from those. For example $\ exists X \; P$ is defined like $\ lnot (\ forall X \; \ lnot P)$ .

One will call terms the formulas composed as follows:

$x$ , element of $V$ , is a term,
$x$ , element of $C$ , is a term,
if $f$ is a symbol of function N - surface and $t_1, t_2, \ dowries, t_n$ are terms, then $f (t_1, t_2, \ dowries, t_n)$ is a term.

A term is closed if it does not contain a name of variable.

The purpose of the terms are to represent the objects to which will apply predicates. Let us call $T$ the whole of the terms.

The stated or formulas of the calculation of the first order predicates are the following, and only the following (call $E$ the whole of the statements):

$p (t_1, t_2, \ dowries, t_n)$ if $(t_1, t_2, \ dowries, t_n) \ in T^n$ , $p \ in P$ and $p$ is N - surface (such a formula is called a atom or a atomic formula )
$(e_1 \ Land e_2)$ if $e_1, e_2 \ in E$
$(e_1 \ lor e_2)$ if $e_1, e_2 \ in E$
$(e_1 \ to e_2)$ if $e_1, e_2 \ in E$
$\ lnot e$ if $e \ in E$
$\ forall X \; e$ if $e \ in E$ and $x \ in V$
$\ exists X \; e$ if $e \ in E$ and $x \ in V$

The purpose of the statements are to represent proposals likely to be true or false.

Examples

; Example 1

If one gives oneself for constants two symbols 0 and 1, for binary symbols of functions + and. , and for binary symbols of predicates the symbols = and <, then the language used can be interpreted as being that of the arithmetic one. X and there indicating variables, X +1 is a term, 0+1+1 is a closed term, X < +1 is there a formula, 0+1+1<0+1+1+1 is a closed formula.

; Example 2

If an unspecified whole of variables is given, a noted constant E , a binary symbol of function noted *, a unary symbol of noted function ^-1, a binary symbol of relation =, then the language used can be interpreted as being that of the theory of the groups. If X and indicates variables there, X * is there a term, E * E is a closed term, X = * is there there a formula, E = E * E ^-1 is a closed formula.

Predicates, closed formulas, free variables, dependant variables

When a variable

x

belongs to a subformula preceded by a quantifier,

\ forall X

\ exists X

, it known as is bound by this quantifier. If a variable is bound by no quantifier, it is free.

The distinction between free variable and dependant variable is important. A dependant variable does not have clean identity and can be replaced by any other name of variable which does not appear in the formula. Thus, $\ exists X (X < there)$ is identical to $\ exists Z (Z < there)$ but not to $\ exists X (X < Z)$ and even less with $\ exists there (there < there)$ .

A closed formula is a formula of which all the variables are dependant. A predicate is a formula which contains one or more free variables. One can regard the predicates as concepts (see Prédicat). Thus, $\ forall X \ exists (X < there)$ is there a closed formula of the language of the arithmetic one. $\ forall X (X < Z)$ is a bearing predicate on the variable Z .

Goal of the calculation of the predicates

Like the Calculation of the proposals, the calculation of the predicates is given for goal to define which are the statements which are valid and which are those which are not it. And as for the calculation of the proposals, there exist two ways of tackling this question, the semantic aspect and the syntactic aspect. A theorem of complétude watch equivalence between these two aspects.

Semantics of the calculation of the first order predicates

The theory of the truth of the formulas of the calculation of the predicates was called by Tarski its semantics. It is presented in the article Théorie of the models. A model of a first order language is a unit in which one gives a direction to the symbols of the language. One can then allot a value of truth ( true or false ) to the formulas of the language in this model. It is said that a formula F of the language is a theorem if this formula is true in very model of the language, which one notes

\ vDash F

. For example, if P indicates a binary predicate, the formula

\ exists X \ forall P (X, there) \ to \ forall \ exists X P (X, there)

is a theorem there there. Indeed, any model M will be a nonempty unit in which the predicate P will be represented by a unit has M × Mr. the variables X and will be seen there affected like value of the elements of M, and to say that P ( X , there ) is true will mean that ( X , there ) is element of A. There are then two cases.

Or there exists an element has M such as

\ {(has, there), there \ in M \} \ subset A

and, in this case, the two proposals

\ exists X \ forall there \; (X, there) \ in A

and

\ forall there \ exists X \; (X, there) \ in A

is true (it is enough to take X = has ), and the implication is true.

Or such a has does not exist and the proposal

\ exists X \ forall there \; (X, there) \ in A

is false. But then, whatever the value of truth of

\ forall there \ exists X \; (X, there) \ in A

, the implication will be true.

The implication being true in very model, the formula is valid.

On the other hand, the formula $\ forall \ exists X P (X, there) \ to \ exists X \ forall P (X, there)$ is not valid there there. It is enough for that to take for model a whole with two elements { has , B } and to model P by the equality. In this structure, the sentence $\ forall there \ exists X \; (x=y)$ is true whereas $\ exists X \ forall there \; (x=y)$ is false. The implication is thus false and the formula is invalid.

Syntax of the calculation of the predicates

In the calculation of the predicates, one can also deduce from the formulas by means of deductions concerned with a calculation. A deduction consists starting from assumptions, or of axioms, and to progress by logical stages until a conclusion according to preset rules. There exist several possible presentations of these axioms and these rules.

the natural Deduction. The logical principles are presented there in a way as close as possible to the natural reasoning. It consists of a list of thirteen rules. They could be reduced with more a small number, but the obviousness of the principles would be less natural.
the logical axioms. Several systems of equivalent axioms can be proposed. This approach adopted by almost all the logicians since Principia Mathematica of Whitehead and Russell has a great importance at the same time Métamathématique and history. One of the systems of axioms shortest consists of:

axioms of the Calculation of the proposals

f \ to (G \ to F)

(F \ to (G \ to H)) \ to ((F \ to G) \ to (F \ to H))

(\ lnot F \ to G) \ to ((\ lnot F \ to \ lnot G) \ to F)

axioms relating to the quantifier

\ forall

\ forall X (F \ to G (X)) \ to (F \ to \ forall X G (X))

where X is not free in F

\ forall X F (X) \ to F (a)

where X does not have free occurrence in a well formed part of F of the form

\ forall has, h

(this to avoid an embarrassing substitution if for example, F ( X ) is form

\ forall has, has < x

the rule of the modus ponens: if one proved

f \ to g

and

f

, then one proved

g

the rule of generalization: if one proved

f (X)

, then one proved

\ forall X F (X)

(since the X of the first proof plays an arbitrary part). But if the search for systems of minimal axioms highlights the elementary principles on which can be based all the reasoning, it does not show the character obviously natural of the more general logical principles.

the Logique of the dialog also brings another lighting on the nature of the logical laws.
See also correspondence of Curry-Howard.

Whatever the presentation approached, the axioms and rules can be coded so that a machine can check the validity or not deduction leading to a formula F. If the deduction is correct, the formula F is known as provable, which one notes $\ vdash F$ .

Arises then the following question: is there equivalence between the semantic presentation and the syntactic presentation? $\ vDash is F$ are equivalent to $\ vdash F$ ? In other words:

is Any provable formula a theorem? If the validity of F is attested by a syntactic calculation, F is it validates in very model of the language used?

Reciprocally, if F is a theorem, valid in very model, can one show his validity following a syntactic calculation?

It is with this question that the theorem of complétude answers who follows.

Complétude and indecidability

Emmanuel Kant believed wrongly that the logic of its time, that of Aristote, was a complete and definitively completed science (foreword of the second edition of the criticism of the pure reason, 1787). The logicians of the nineteenth century realized that the theory of Aristote does not say anything or almost on the logic of the relations. Gottlob Frege and much of others filled this gap by defining the calculation of the predicates in the first order.

Kurt Gödel proved in 1929 (in its thesis of doctorate) that the calculation of the predicates is complete, with the direction where one can give a finished number of principles (logical axioms, diagrams of logical axioms and rules of deduction) which are enough to deduce in a mechanical way all the logical laws (see the Théorème of complétude of Gödel). There is equivalence between the semantic presentation and the syntactic presentation of the calculation of the predicates. Any tautology (true property in very model of the language used) is a theorem i.e. it can be deduced from a calculation, either by means of the natural Déduction, or by means of the logical axioms, and reciprocally. First order logic is thus completed with the direction where the problem of the logical correction of the demonstrations is solved there. It however continues to be the subject of important research: Theory of the models, cylindrical algebras, mechanization of the reasoning… One will note that there exist other theories which are not complete. Thus, Gödel proved into 1930 that the all mathematical theory, set theories and, more generally which contain certain elementary arithmetic truths, are not complete, with the direction where they do not make it possible to prove all the truths which they however make it possible to state (see Théorème of incomplétude of Gödel).

The calculation of the predicates is semi-décidable, in the direction where a machine can draw up, the ones after the others, the list of the theorems of this logic. But, contrary to the Calculation of the proposals, it is not décidable in the direction where, if a formula F is given, it is not possible to decide if F is a theorem or not, if one does not have his proof. Indeed, the confrontation of F with the list of the theorems will finish if F is indeed a theorem, but in waiting of the termination, one does not know if the calculation of the theorems were not carried out to identify F like theorem rather far or if this calculation does not finish because F is not a theorem. On the other hand the calculation of the monadic predicates (having only unary symbols of proposals and not of symbol of function) is décidable.