4. CALCUL DES PRÉDICATS



THÉORIE DE LA DÉMONSTRATION

1. Crise des fondements

1.1.Paradoxes

2. Raisonnement hypothético-déductif

3. Calcul propositionnel

3.1. Propositions

3.2. Connecteurs

3.3. Procédures de décision

3.3.1. Procédures de décision non axiomatisées

3.3.2. Procédures de décision axiomatisées

3.4. Quantificateurs

4. Calcul des prédicats

4.1. Grammaire

4.2. Langages

4.2.1. Symboles

4.2.2. Termes

4.2.3. Formules

5. Démonstrations

5.1. Règles de démonstration

Dans un cours de mathématiques (d'algèbre, d'analyse, de géométrie, ...), nous démontrons les propriétés de différents types d'objets (entiers, réels, matrices, suites, fonctions continues, courbes, ...).  Pour pouvoir prouver ces propriétés, il faut bien sûr que les objets sur lesquels nous travaillons soient clairement définis (qu'est-ce qu'un entier, un réel, ...?).

En logique du premier ordre et, en particulier, en théorie de la démonstration, les objets que nous étudions sont les formules et leurs démonstrations. Il faut donc donner une définition précise de ce que sont ces notions. Les termes et les formules forment la grammaire d'une langue, simplifiée à l'extrême et calculée exactement pour dire ce que nous voulons sans ambiguïté et sans détour inutile.

4.1. GRAMMAIRE

Définitions:

D1. Les "termes", désignent les objets dont nous voulons prouver des propriétés (nous reviendrons un peu plus loin beaucoup plus en détail sur ces derniers) :

- En algèbre, les termes désignent les éléments d'un groupe (ou anneau, corps, espace vectoriel, etc.). Nous manipulons aussi des ensembles d'objets (sous-groupe, sous-espace vectoriel, etc). Les termes qui désignent ces objets, d'un autre type, seront appelés "termes du second ordre".

- En analyse, les termes désignent les réels ou (par exemple, si nous nous plaçons dans des espaces fonctionnels) des fonctions.

D2. Les "formules", représentent les propriétés des objets que nous étudions (nous reviendrons également beaucoup plus en détail sur ces dernières) :

- En algèbre, nous pourrons écrire des formules pour exprimer que deux éléments commutent, qu'un sous-espace vectoriel est de dimension 3, etc.

- En analyse, nous écrirons des formules pour exprimer la continuité d'une fonction, la convergence d'une suite, etc.

- En théorie des ensembles, les formules pourront exprimer l'inclusion de deux ensembles, l'appartenance d'un élément à un ensemble,...

D3. Les "démonstrations", elles permettent d'établir qu'une formule est vraie. Le sens précis de ce mot aura lui aussi besoin d'être défini. Plus exactement, elles sont des déductions sous hypothèses, elles permettent de "mener du vrai au vrai", la question de la vérité de la conclusion étant alors renvoyée à celle des hypothèses, laquelle ne regarde pas la logique mais repose sur la connaissance que nous avons des choses dont nous parlons.

4.2. LANGAGES

En mathématique, nous utilisons, suivant le domaine, différents langages qui se distinguent par les symboles utilisés. La définition ci-dessous exprime simplement qu'il suffit de donner la liste de ces symboles pour préciser le langage.

Définition: Un "langage" est la donnée d'une famille (pas nécessairement finie) de symboles. Nous en distinguons trois sortes : symboles, termes et formules.

Remarques:

R1. Nous utilisons quelques fois le mot "vocabulaire" ou le mot "signature" à la place du mot "langage".

R2. Le mot "prédicat" peut être utilisé à la place du mot "relation". Nous parlons alors de "calcul des prédicats" au lieu de "logique du premier ordre" (ce que nous avons étudié précédemment).

4.2.1 SYMBOLES

Il existe différents types de symboles que nous allons tâcher de définir :

D1. Les "symboles de constante" (voir remarque plus bas)

exemple Exemple:

Le n pour l'élément neutre en théorie des ensembles (cf. chapitre de Théorie Des Ensembles)

D2. Les "symboles de fonction" ou "foncteurs" . A chaque symbole de fonction est associé un entier strictement positif que nous appelons son "arité" : c'est le nombre d'arguments de la fonction. Si l'arité est 1 (resp. 2, ...,n), nous disons que la fonction est unaire (resp. binaire, ..., n-aire)

exemple Exemple:

Le foncteur binaire de multiplication * dans les groupes (cf. chapitre de Théorie Des Ensembles).

D3. Les "symboles de relation". De la même manière, à chaque symbole de relation est associé un entier positif ou nul (son arité) qui correspond à son nombre d'arguments et nous parlons de relation unaire, binaire, n-aire (comme par exemple le symbole de relation "=").

D4. Les "variables individuelles". Dans toute la suite, nous nous donnerons un ensemble infini V de variables. Les variables seront notées comme il l'est par tradition : x, y, z (éventuellement indexées: equation).

D5. A cela il faut rajouter les connecteurs et quantificateurs que nous avons longuement présenté plus haut et sur lesquels il est pour l'instant inutile de revenir.

Remarques:

R1. Un symbole de constante peut être vu comme un symbole de fonction à 0 argument (d'arité nulle).

R2. Nous considèrons (sauf mention contraire) que chaque langage contient le symbole de relation binaire = (lire "égal") et le symbole de relation à zéro argument dénoté equation (lire "bottom" ou "absurde") qui représente le faux. Dans la description d'un langage, nous omettrons donc souvent de les mentionner. Le symbole equation est souvent redondant. Nous pouvons en effet, sans l'utiliser, écrire une formule qui est toujours fausse. Il permet cependant de représenter le faux d'une manière canonique et donc d'écrire des règles de démonstration générales.

R3. Le rôle des fonctions et des relations est très différent. Comme nous le verrons plus loin, les symboles de fonction sont utilisés pour construire les termes (les objets du langage) et les symboles de relation pour construire les formules (les propriétés de ces objets).

4.2.2. TERMES

Les termes (nous disons aussi "termes du premier ordre") représentent les objets associés au langage.

Définitions:

Soit equation un langage :

D1. L'ensemble equation des termes sur equation est le plus petit ensemble contenant les variables, les constantes et stable (on ne sort pas de l'ensemble) par l'application des symboles de fonction deequation à des termes.

D2. Un "terme clos" est un terme qui ne contient pas de variables (donc par extension, seulement des constantes).

D3. Pour obtenir une définition plus formelle, nous pouvons écrire :

equation   (1.23)

t est une variable ou un symbole de constante et, pour tout equation :

equation   (1.24)

f est une fonction d'arité n (rappelons que l'arité est le nombre d'arguments de la fonction). Ainsi, pour chaque arité, il y a un degré d'ensemble de termes. Nous avons finalement :

equation   (1.25)

D4. Nous appellerons "hauteur" d'un terme t le plus petit k tel que equation

Remarques : 

R1. la définition D4 signifie que les variables et les constantes sont des termes et que si f est un symbole de fonction n-aire et equation sont des termes alors equation est un terme en soi aussi. L'ensemble equation des termes est défini par la grammaire:

equation   (1.26)

Cette expression se lit de la manière suivante : un élément de l'ensemble equation que nous sommes en train de définir est soit un élément de V (variables), soit un élément de equation (l'ensemble des symboles de constantes), soit l'application d'un symbole de fonction equation à n éléments (constantes ou variables) de equation.

Attention : le fait que f soit de la bonne arité est seulement implicite dans cette notation. De plus, l'écriture equation ne signifie pas que tous les arguments d'une fonction sont identiques mais simplement que ces arguments sont des éléments de equation.

R2. Il est souvent commode de voir un terme (expression) comme un arbre dont chaque noeud est étiqueté par un symbole de fonction (opérateur ou fonction) et chaque feuille par une variable ou une constante.

Dans la suite, nous allons sans cesse définir des notions (ou prouver des résultats) "par récurrence" sur la structure ou la taille d'un terme.

Définitions:

D1. Pour prouver une propriété P sur les termes, il suffit de prouver P pour les variables et les constantes et de prouver equation à partir de equation. Nous faisons ainsi ici une "preuve par induction sur la "hauteur"" d'un terme. C'est une technique que nous retrouverons dans les chapitres suivants.

D2. Pour définir une fonction equation sur les termes, il suffit de la définir sur les variables et les constantes et de dire comment nous obtenons equation à partir de equation. Nous faisons ici encore une "définition par induction sur la hauteur d'un terme".

exemple Exemple:

La taille (nous disons aussi la "longueur") d'un terme t (notée equation) est le nombre de symboles de fonction apparaissant dans t. Formellement:

- equation si x est une variable et c est une constante

- equation

Remarque: La preuve par induction sur la hauteur d'un terme sera souvent insuffisante. Nous pourrons alors prouver une propriété P sur les termes en supposant la propriété vraie pour tous les termes de taille equation et en la démontrant ensuite pour les termes de taille n. Il s'agira alors d'une "preuve par récurrence sur la taille du terme" (voir de tels exemples dans le chapitre de Théorie Des Nombres).

4.2.3. FORMULES

Les formules sont construites à partir de "formules atomiques" en utilisant des connecteurs et des quantificateurs. Nous utiliserons les connecteurs et les quantificateurs suivants (qui nous sont déjà connus) :

- connecteur unaire de négation : equation

- connecteurs binaires de conjonction et disjonction ainsi que d'implication : equation , equation , equation

- quantificateurs : equation qui se lit "il existe" et equation qui se lit "pour tout"

Cette notation des connecteurs est standard (elle devrait du moins). Elle est utilisée pour éviter les confusions entre les formules et le langage courant (le métalangage).

Définitions:

D1. Soit equation un langage, les "formules atomiques" de equation sont les formules de la forme equation où R est un symbole de relation n-aire de equation et equation sont des termes de equation. Nous notons "Atom" l'ensemble des formules atomiques. Si nous notons equation l'ensemble des symboles de relation, nous pouvons écrire l'ensemble des termes mis en relations par l'expression :

equation   (1.27)

L'ensemble F des formules de la logique du premier ordre de equation est donc défini par la grammaire (où x est une variable) :

equation   (1.28)

où il faut lire : l'ensemble des formules est le plus petit ensemble contenant les formules et tel que si equation et equation sont des formules alors equation, etc. sont des formules et qu'elles peuvent être en relation entre elles.

exemple Exemple:

Les symboles de relation du langage propositionnel sont des relations d'arité 0 (même le symbole "=" est absent), les quantificateurs sont alors inutiles (puisqu'une formule propositionnelle ne peut pas contenir des variables). Nous obtenons alors le calcul propositionnel défini par :

equation   (1.29)

Remarquons la présence du symbole "botton" signifiant le "faux" que nous n'avions pas mentionné lors de notre étude de la logique propositionnelle.

Nous ferons attention à ne pas confondre termes et formules. equation est un terme (fonction), equation est une formule. Mais equation n'est rien : nous ne pouvons, en effet, mettre un connecteur entre un terme et une formule (aucun sens).

Remarques:

R1. Pour définir une fonction equation sur les formules, il suffit de définir equation sur les formules atomiques.

R2. Pour prouver une propriété P sur les formules, il suffit de prouver P pour les formules atomiques.

R3. Pour prouver une propriété P sur les formules, il suffit de supposer la propriété vraie pour toutes les formules de taille equation et de la démontrer pour les formules de taille n.

D2. Une "sous-formule" d'une formule (ou expression) F est l'un de ses composants, in extenso une formule à partir de laquelle F est construite. Formellement, nous définissons l'ensemble SF(F) des sous-formules F par:

- Si F est atomique:equation

- Si equation (soit une composition!) avecequation

- Si equation ou equation avec equation

D3. Une formule F de equation n'utilise qu'un nombre fini de symboles de equation. Ce sous-ensemble est appelé le "langage de la formule" et noté equation.

D4. La "taille (ou la longueur) d'une formule" F (notée equation) est le nombre de connecteurs ou de quantificateurs apparaissant dans F. Formellement :

- equation si F est une formule atomique

- equationequation

- equation avec equation

D5. "L'opérateur principal" (nous disons aussi le "connecteur principal") d'une formule est défini par :

- Si A est atomique, alors elle n'a pas d'opérateur principal

- Si equation, alors equation est l'opérateur principal de A

- Si equation où equation, alors equation est l'opérateur principal de A

- Si equationequation, alors equation est l'opérateur principal de A

D6. Soit F une formule. L'ensemble equation des variables libres de F et l'ensemble equation des variables muettes (ou liées) de F sont définis par récurrence sur equation.

Une occurrence d'une variable donnée est dite "variable liée" ou "variable muette" dans une formule F si dans cette même formule, un quantificateur y fait référence. Dans le cas contraire, nous disons avoir une "variable libre".

Remarque: Une occurrence d'une variable x dans une formule F est une position de cette variable dans la formule F. Ne pas confondre avec l'objet qu'est la variable elle-même.

Pour préciser les variables libres possibles d'une formule F, nous noterons equation. Cela signifie que les variables libres de F sont parmi equation in extenso si y est libre dans F, alors y est l'un des equation mais les equation n'apparaissent pas nécessairement dans F.

Nous pouvons définir les variables muettes ou libre de manière plus formelle :

1. Si equation est atomique alors equation est l'ensemble des variables libres apparaissant dans les equation et nous avons alors pour les variables muettes equation

2. Si equation où equation: equation alors equation

3. si equation alors equation et equation

4. si equation avec equation et equation

exemple Exemples:

E1. Soit F : equation alors equation et equation

E2. Soit G : equation alors equation et equation

D7. Nous disons que les formules F et G sont "equation-équivalentes" si elles sont (syntaxiquement) identiques à un renommage près des occurrences liées des variables.

D8. Une "formule close" est une formule sans variables libres.

D9. Soit F une formule, x une variable et t un terme. equation est la formule obtenue en remplaçant dans F toutes les occurrences libres de x par t, après renommage éventuel des occurrences liées de F qui apparaissent libres dans t.

Remarques:

R1. Nous noterons dans les exemples vus qu'une variable peut avoir à la fois des occurrences libres et des occurrences liées. Nous n'avons donc pas toujours equation

R2. Nous ne pouvons pas renommer y en x dans la formule equation et obtenir la formule equation: la variable x serait "capturée". Nous ne pouvons donc pas renommer des variables liées sans précautions : il faut éviter de capturer des occurrences libres.


page suivante : 5. Démonstrations