Les théories mathématiques

 

1) Introduction

Qu'est-ce qu'une théorie mathématique ? C'est en voulant répondre à cette question que l'on va décrire les règles du raisonnement, en partant de son aspect purement mécanique. Et à bien y regarder, il s'agit plus précisement d'une mécanique classique.

Les mathématiques sont un jeu de construction, un jeu de légo, où chaque pièce s'encastre exactement dans un édifice servant de démonstration. Rien ne relève du mystère, tout est trivial..., c'est l'aspect exacte de la science. Le démonstrateur n'est finalement qu'une machine, une machine idéale, composée de rouages parfaitement emboités et sans aucun jeu. Ces machines sont décrites à l'aide du langage formel.

Les règles du raisonnement se fondent sur le langage formel et sur son aspect purement calculatoire.

Le processus de démonstration s'inscrit dans un processus plus général de construction. Ainsi une démonstration est une construction n'utilisant que des règles de raisonnement que nous allons décrire.

La logique est la science du raisonnement exacte. Et on ne peut concevoir de raisonnement exacte sans langage exacte ni règles de démonstration exactes. Le langage exacte s'appelle langage de propositions, l'ensemble des règles de démonstration exactes s'appelle système de démonstration. La conclusion d'une démonstration sans hypothèse s'appelle une tautologie.

Il existe donc un processus de construction de toutes les propositions exprimables. Autrement dit, il existe une machine qui énumère toutes les propositions exprimables dans le langage en question. Et de même il existe un processus de construction de toutes les démonstrations. Autrement dit, il existe une machine qui énumère toutes les démonstrations faisables dans le langage en question. Et comme l'extraction de la conclusion d'une démonstration se fait également par un procédé trivial, il existe donc une machine qui énumère toutes les tautologies.

Pour résumer nous dirons que le langage des tautologies, qui est inclus dans le langage des propositions, est engendré mécaniquement par le système de démonstration.

L'élémentarisme se construit à partir du fait essentiel que quelque soit le langage des propositions choisi et quelque soit le système de démonstration choisi, l'ensemble des tautologies est énumérable.

Nous allons construire petit à petit, et en parallèle, le langage des propositions et le système de démonstration en ajoutant une à une les règles de démonstration et en s'assurant à chaque fois qu'elles sont toutes nécessaires c'est à dire qu'elles forment une sorte d'axiomatique, et qu'elles sont suffisantes c'est à dire qu'elles démontrent toutes les propositions vrais selon une sémantique choisie.

Le symbole de départ que nous utiliserons, sera le prédicat binaire de démontrabilité `"⊢"`, appellé aussi relation de démontrabilité. Il s'applique dans le langage des propositions. Et il est défini mécaniquement par le système de démonstration.

A ce stade, même si on utilise un vocabulaire propre à la logique, la matière étudiée n'est pas encore celle de la logique mais plutôt celle des langages. Car il manque des éléments essentiels que sont les valeurs de vérité vrai et faux et ce qu'est la négation, une symétrie qui permet de passer de l'une à l'autre, c'est à dire la capacité expressive totale de dire « non ».

2) Langage et méta-langage

Pour étudier les théories, il faut être en dehors de celles-ci, en dehors de leur langage propre. Pour cela on utilise un autre langage que celui des théories étudiées, un langage mathématique que l'on formalise sous l'appellation de méta-langage. Le système de démonstration, qui constitue en quelque sorte le pilote de toutes les théories, est écrit dans ce méta-langage.

Une théorie est une proposition. Et il n'y a pas de différence entre théorie et proposition. Elles doivent appartenir au langage de proposition, et donc en particulier être de taille finie, être concrètement écrivables.

Le cadre pour définir les théories est d'abord posé en choisissant un langage de proposition `ccL` et un système de démonstration `ccD` appelé aussi méta-théorie qui définie mécaniquement la relation de démontrabilité `"⊢(.,.)"` qui s'applique dans l'ensemble `ccL`. Le système de démonstration peut être vu comme associé à un moteur qui constitue son aspect dynamique. Le moteur est un programme informatique capable d'énumérer toutes les déductions possibles à partir d'une proposition de départ appartenant à `ccL` et de l'ensemble des données appartenant à `ccD`.

Le suffixe `"(.,.)"` apposé à un opérateur ou un prédicat, est utilisé pour rappeler que l'opérateur ou le prédicat est d'arité 2, c'est à dire qu'il prend 2 arguments appartenant à `ccL`.

On pose un langage `ccL` et une méta-théorie `ccD` toutes deux vides au départ. Et on se propose d'ajouter les éléments de construction du langage et de construction des démonstrations petit à petit selon un ordre, si j'ose dire, presque « naturel ».

3) Principe pré-logique

Déjà, sans avoir besoin de définir la négation dans `ccL`, un certain nombre de principes peuvent être dévoilés. On les qualifiera de pré-logiques.

Par convention, dans une règle de démonstration, toute nouvelle variable apparaissant sera quantifiée universellement sur l'ensemble `ccL`. C'est à dire que la règle s'appliquera pour toutes les valeurs possibles de ces nouvelles variables dans les limites de `ccL`.

On adopte deux principes qui parraissent incontournables concernant les règles de démonstration :

Identité : `A"⊢"A`
Composition des démonstrations : `(A"⊢"B)` et `(B"⊢"C) => (A"⊢"C)`

A partir de ces deux principes qui ne font pas intervenir la négation, on peut définir la relation d'équivalence logique. Le principe d'identité correspond à la reflexivité de la relation `"⊢"`, et le principe de composition des démonstrations correspond à la transitivité de la relation `"⊢"`.

4) La relation d'équivalence

A partir de la relation de démontrabilité `"⊢(.,.)"` on définie sa symétrisée, la relation d'équivalence `"↔(.,.)"` :

`A harr B` si et seulement si `(A|--B)` et `(B|--A)`

La relation `"↔"` constitue bien une relation d'équivalence :

La relation `"↔"` est réflexif : `A"↔"A`
La relation `"↔"` est symétrique : `(A"↔"B) => (B"↔"A)`
La relation `"↔"` est transitive : `(A"↔"B)` et `(B"↔"C) => (A"↔"C)`

La relation `|--` constitue un préordre sur `ccL` :

La relation `"⊢"` est réflexif : `A"⊢"A`
La relation `"⊢"` est transitive : `(A"⊢"B)` et `(B"⊢"C) => (A"⊢"C)`

Et donc la relation `|--` constitue un ordre sur la structure quotient `ccL"/↔"` :

La relation `"⊢"` est réflexif : `A"⊢"A`
La relation `"⊢"` est antisymétrique : `(A"⊢"B)` et `(B"⊢"A) => (A"="B)`
La relation `"⊢"` est transitive : `(A"⊢"B)` et `(B"⊢"C) => (A"⊢"C)`

Dans ces expressions, on considère que les opérations `<=>` et `=>` ont une priorité syntaxique inférieur à l'opération et, ce qui nous permet d'omettre un certain nombre de parenthèses sans introduire d'ambiguïté.

L'ordre dont il est question est évidement partiel (non total).

On associe à chaque théorie `T` sa cloture `"<"T">"` qui est l'ensemble de toutes les propositions qu'elle peut démontrer. Ainsi `T|--A` qui signifie que `T` démontre `A`, est équivalent à l'appartenance `A in "<"T">"`, et est aussi équivalente à l'inclusion `"<"A">" sub "<"T">"`.

`A ↔ B` si et seulement si `"<"A">"="<"B">"`
`A ↔ B` si et seulement si `("<"B">" sub "<"A">")` et `("<"A">" sub "<"B">")`
`A ↔ B`
si et seulement si `(A|--B)` et `(B|--A)`

Les prédicats `↔` et `|--` sont tous deux des fonctions de `ccL^2->{`vrai`, `faux`}`, et donc la définition du prédicat `↔` peut se noter par l'égalité suivante :

`A"↔"B  =  (A"⊢"B)` et `(B"⊢"A)`

Dans cette expression, on considère que l'opération `"="` a une priorité syntaxique infèrieur aux opérations et, `"↔"`.

L'expression `A"⊢"B` signifie que `A` démontre `B`. L'expression `A"↔"B` signifie que `A` démontre `B` et que `B` démontre `A`. Ces deux prédicats `"↔"` et `"⊢"` vont nous servir pour définir les règles de démonstrations.

5) Les modèles pré-logiques

Le langage ne se suffit pas à lui-même car sa raison d'être est justement de désigner autre chose que lui-même. Il y a donc une distinction nécessaire, qu'il faut établir d'emblés, entre le signifiant et le signifié, entre la proposition désignante et la réalité désignée. La proposition désignante fait partie du langage, la réalité désignée fait partie d'un modèle, qui est ici pré-logique puisque la négation n'y est pas encore définie.

Une proposition externe est caractérisée par son nom, `X`, opérateur d'arité zéro qui appartient au langage, et par ce qu'elle désigne, `X`, qui est une partie d'un modèle, ou qui caractérise un monde qui réalise justement et concrètement ce que désigne cette proposition, `X`. Dans un cas, c'est la syntaxe, le nom `X` qui désigne.... Dans l'autre cas c'est la sémantique, une réalité `X` qui est désignée dans un monde la réalisant.

Ce monde, qui peut réaliser ce que désigne une proposition du langage, s'appelle classiquement un modèle. L'ensemble de tous les mondes possibles s'appel l'univers. Il est dit pré-logique car la négation n'existe pas encore.

La syntaxe préside le langage tandis que la sémantique préside l'univers.

6) Les propositions externes `X,Y,Z,...`

Les premiers éléments de langage que nous incorporons sont des propositions externes que l'on ajoute en nombre fini `X,Y,Z...`

Le nombre `n` de propositions externes rajoutées s'appelle la dimension du langage ou la dimension de l'univers. A chaque langage, est associé un univers.

A ce stade, le langage de dimension `3` devient :

`ccL="{"X, Y, Z"}"`

Et la seul règle de démonstration dont nous avons besoin est la règle d'identité :

`ccD={A"⊢"A}`

Rappelons que dans la méta-théorie entre crochet, toute nouvelle variable est implicitement quantifiée universellement sur `ccL`. Le système de démonstration s'écrit donc explicitement comme suit :

`ccD={AA A in ccL,  A"⊢"A}`

7) Le paradigme conjonctif

On considère qu'une théorie est un ensemble fini de petites théories. Pour cela, il nous faut formaliser une opération logique fondamentale que nous n'avons pas encore définie dans notre langage des propositions, qu'est la conjonction et`"(.,.)"`, avec comme principe qu'elle est commutative, associative et possède un élément neutre, faisant qu'une conjonction correspond à un ensemble.

Ce paradigme nous fait rajouter l'opérateur et`"(.,.)"` au langage des propositions, et nous fait aussi rajouter la théorie vide `Ø` qui est l'élément neutre, au langage des propositions.

Par commodité on définie dans un langage plus générale l'opérateur d'arité variable `{...}` pour désigner une conjonction. Ainsi étant donnée des propositions quelconques `A,B,C,...` appartenant à `ccL`, nous avons :

`A = {A}`
`A` et `B = {A,B}`
`A` et `B` et `C = {A,B,C}`
...

Notez que dans ces expressions, l'opérateur `=` a une priorité syntaxique inférieur à l'opérateur et.

Mais cet opérateur `{...}` est d'arité variable. Aussi on ne l'ajoute pas au langage `ccL` afin de rester dans un type de langage d'opérateurs d'arité fixe plus apte a possèder des propriétés qui nous serons utiles par la suite.

La règle de démonstration qu'il faut ajouter est très simple. Elle affirme qu'une conjonction démontre ce qu'elle contient.

Ce paradigme nous fait rajouter dans le système de démonstration, la commutativité et l'associativité de l'opérateur et`"(.,.)"`, l'élément neutre qu'est la théorie vide `Ø`, ainsi qu'un principe de démontrabilité, à savoir, qu'une conjonction démontre ce qu'elle contient. Règles de démonstrations pré-logiques associées à l'introduction du et  :

L'opérateur et`"(.,.)"` est commutatif : `A` et `B  ↔  B` et `A`
L'opérateur et`"(.,.)"` est associatif : `A` et `(B` et `C)  ↔  (A` et `B)` et `C`
Définition de la théorie vide `Ø` : `A` et `Ø  ↔  A`
Démontrabilité du contenu : `A` et `B  |--  A`

Dans ces expressions, on considère que les opérateurs `"↔"` et `"⊢"` ont une priorité syntaxique inférieur à l'opérateur et.

On remarquera que le principe d'identité `A"⊢"A` y est inclus si on ajoute le principe de composition des démonstrations, puisque `A⊢A` et `Ø` et que `A` et `Ø⊢A`. On remarquera que le principe de composition de démonstration n'est pas encore utile à ce stade, mais y est inclus en quelque sorte, et correspond à la transitivité de l'inclusion.

Le choix de commencer par introduire cet opérateur logique et`"(.,.)"` qui est commutatif et associatif, qui a un élément neutre et qui démontre ce qu'il contient, relève d'une conception accumulative des connaissances désignées sous le nom de paradigme conjonctif.

A ce stade, le langage de dimension 3 devient :

`ccL="<"Ø,X,Y,Z,`et`"(.,.)>"`

Les crochets `"< >"` signifient la cloture par composition close, c'est à dire l'ensemble de tous les termes clos construcibles à partir des opérateurs générateurs présentés entre ces crochets.

Et le système de démonstration est  :

`ccD={`
    `A` et `B  ↔  B` et `A,`
    `A` et `(B` et `C)  ↔  (A` et `B)` et `C,`
    `A` et `Ø  ↔  A,`
    `A` et `B  |--  A`
`}`

Notez que implicitement toute nouvelle variable apparaissant dans la méta-théorie est quantifiée universellement sur le langage `ccL`. Donc il faut entendre que ces règles de démonstrations sont valables quelques soient `A, B, C`, trois propositions quelconques appartenant à `ccL`.

On remarquera alors, que l'ensemble `ccL` quotienté par la relation d'équivalence est identifiable à l'ensemble des sacs (multi-ensembles) de support `E`, avec `E={X,Y,Z}`, ce qui se note :

`ccL"/↔"  ~=  ccS(E)`

Puis si on ajoute au système de démonstration `ccD` l'axiome d'invariance suivant :

Invariance : `A` et `A  ↔  A`

Alors l'ensemble `ccL` quotienté par la relation d'équivalence devient identifiable à l'ensemble des parties de `E`, avec `E={X,Y,Z}`, ce qui se note :

`ccL"/↔"  ~=  ccP(E)`

Tout langage est le reflet d'une réalité hypothètique désigné sous le nom d'univers. A quoi ressemble donc ici l'univers ? à `ccP(E)`.

8) Une axiomatique du système de démonstration

Nous nous intéressons à la recherche d'une axiomatique, c'est à dire à un ensemble de règles génératrices dans lequel aucune ne peut être supprimée sans réduire le pouvoir de démonstration du système. On trouve en élaguant le système de démonstration, une première solution qu'est l'axiomatique suivante :

`r_1` L'opérateur et est commutatif : `A` et `B  |--  B` et `A`
`r_2` L'opérateur et est associatif à gauche : `A` et `(B` et `C)  |--  (A` et `B)` et `C`
`r_3` L'opérateur et est associatif à droite : `(A` et `B)` et `C  |--  A` et `(B` et `C)`
`r_4` Définition de la théorie vide `Ø` : `A  |--  A` et `Ø`
`r_5` Démontrabilité du contenu : `A` et `B  |--  A`
`r_6` Invariance : `A  |--  A` et `A`

9) Application des règles de démonstration

Une règle de démonstration comprend une entête qu'est la proposition à gauche du symbole `"⊢"` et un corps qui est la proposition à droite du symbole `"⊢"`. Par exemple la règle `r_1` : `A` et `B  |--  B` et `A` possède une entête qu'est la proposition `A` et `B` et possède un corps qui est la proposition `B` et `A`.

Pour appliquer la règle à une proposition `H`, on procède à l'unification de `H` avec l'entête de la règle. Si l'unification réussie, on retourne le corps de la règle avec les variables affectée par l'unification. Par exemple, appliquons la règle `r_1` à la proposition `X` et `(Y` et `X)`. L'unification fonctionne et affecte `A=X` et `B=(Y` et `X)` puis retourne le corps `B` et `A` en remplaçant les variables par leur valeur d'affectation `(Y` et `X)` et `X`.

Pour énumérer toutes les déductions possibles, on passe en revue chaque règle de déduction que l'on applique à l'hypothèse et à chacune de ses déductions.

Par exemple voici une démonstration de `(A` et `A)` et `A` à partir de `A` :

`r_6` : `A  |--  A` et `A`
`r_6` : `A` et `A  |--  (A` et `A)` et `(A` et `A)`
`r_2` : `(A` et `A)` et `(A` et `A)  |--  ((A` et `A)` et `A)` et `A`
`r_5` : `((A` et `A)` et `A)` et `A  |--  (A` et `A)` et `A`

La démonstartion semble complexe car elle détaille toutes les opérations jusqu'aux plus petites. Démontrer qu'un ensemble est inclus dans un autre peut demander de vérifier que chaque élément du premier ensemble appartient bien au second. Et cette vérification peut constituer un processus trés long qui sera exécuté par un programme. Ce processus est la démonstration.

10) Définition du faux et du vrai  `"⊥","⊤"`

Comme nous l'avons précisé en introduction, pour que notre étude soit celle de la logique et non seulement celle des langages, il faut ajouter les valeurs de vérité vrai et faux, et ce qu'est la négation, une symétrie qui permet de passer de l'une à l'autre, c'est à dire la capacité totale de dire « non ».

Il existe un moyen intérieur au langage pour définir de façon absolue, le faux, grâce au concept d'incohérence. Une théorie `T` est dite incohérente si et seulement si `T` démontre tout, `"<"T">"=ccL`. Et donc elle est dite cohérente si et seulement si il existe au moins une proposition `A` que `T` ne peut pas démontrer `T⊬A`.

On définie le faux comme une proposition incohérente, et on définie le vrai comme une proposition nécessaire. Ainsi nous avons :

Une proposition sera dite fausse si et seulement si elle démontre tout.
Une proposition sera dite vrai si et seulement si elle est démontrée par toute proposition.

On définie la proposition `"⊥"` avec comme seul définition d'être fausse c'est à dire telle que quelque soit une proposition `A`, la proposition `"⊥"` démontre la proposition `A`, ce qui se note :

`AA A,  "⊥⊢"A`

On définie la proposition `"⊤"` avec comme seul définition d'être vrai c'est à dire telle que quelque soit une proposition `A`, la proposition `A` démontre la proposition `"⊤"`, ce qui se note :

`AA A,  A"⊢⊤"`

Dans un langage de dimension 3, `ccL="<"Ø,X,Y,Z,`et`"(.,.)>"`, la proposition vide `Ø` est démontrée par toutes les propositions, et la proposition pleine `{X,Y,Z}` démontre tous les autres propositions. Donc nous avons :

`"⊥"= {X,Y,Z}`
`"⊤"= Ø`

Au stade pré-logique, il existe donc déjà le vrai et le faux.

`AA A,  "⊥⊢"A` `AA A,  A"⊢⊤"`
`"<⊥>"=ccL`   C'est l'ensemble des propositions. `"<⊤>"`   C'est l'ensemble des tautologies.
`AA A,  "<"A">" sub "<⊥>"` `AA A,  "<⊤>" sub "<"A">"`

Le faux `"⊥"` est ainsi défini intérieurement au langage comme étant l'incohérence, et représente la borne supérieure d'un treillis.

Le vrai `"⊤"` est ainsi défini intérieurement au langage comme engendrant le nécessaire c'est à dire l'ensemble des tautologies, et représente la borne inférieure d'un treillis.

Conventionellement, l'expresssion `"⊢"A` correspondra à l'expression `Ø"⊢"A`. Et comme la proposition vide correspond à la proposition vrai notée `"⊤"`, l'expression `"⊢"A` correspondra à l'expression `"⊤⊢"A`.

11) Définition de l'implication

L'ajout de l'opérateur de négation va engendrer toute la logique propositionnelle car tous les opérateurs booléens peuvent être définis à partir des deux opérateurs booléens `{¬"(.)", `et`"(.,.)"}`. Il est possible néanmoins de choisir une voie plus progressive et de commencer par l'ajout de l'opérateur d'implication `"⇒(.,.)"` qui n'a pas cette conséquence d'engendrer tous les opérateurs logiques.

La définition de l'implication traduit dans le langage `ccL` la relation de démontrabilité `"⊢"`.

Modus ponens `(A"⇒"B)⊢(A"⊢"B)`
Réciproque du modus ponens `(A"⊢"B) ⊢ (A"⇒"B)`

L'expression `(A"⊢"B)` est une règle de démonstration qui peut s'ajouter au système de demonstartion, tandis que l'expression `(A"⇒"B)` représente une proposition du langage `ccL`. Ainsi en adoptant ces nouvelles règles, les déductions se font aussi bien dans `ccL` par l'ajout de propositions déduites que dans `ccD` par l'ajout de règles de déduction déduites.

.....

 

 

A ce stade, le langage de dimension 3 devient :

`ccL="<"Ø,X,Y,Z,`et`"(.,.)","⇒(.,.)>"`

Pour l'étudier plus simplement on commence par en étudier une partie plus simple nommée `ccL_1` que sont les propositions ne contenant qu'au plus une seul occurence de l'opérateur d'implication `"⇒"`, c'est à dire les propositions de la forme `A` ou de la forme `A"⇒"B` `A` et `B` sont des propositions appartenant à `ccL_0="<"Ø,X,Y,Z,`et`"(.,.)>"`.

`ccL_1="<"Ø,X,Y,Z,`et`"(.,.)","⇒(.,.)"_1">"`

L'indice 1 suffixé à l'opérateur comme suit `"⇒(.,.)"_1` signifie qu'il ne doit être utilisé qu'au plus une fois dans chaque terme. Dans ce langage `ccL_1`, les règles de démonstration sont plus simples à percevoir. Elles doivent avoir une hypothèse et une conclusion toutes deux appartenant à `ccL_1`.

 

Démonstration `(A"⊢"B) ⊢ (Ø⊢(A"⇒"B))`

 

Les premières règles de démonstration à rajouter sont la reflexivité et la transitivité de l'implication :

Identité : `A"⇒"A`
Composition des démonstrations : `(A"⇒"B)` et `(B"⇒"C)` `=>` `(A"⇒"C)`

Notez que le méta-langage est écrit en noir tandis que le langage `ccL_1` est écrit en bleu.


Tout se passe comme si nous étions dans un jeu de dominos deux sorte de pièce des dominos simple qui ne comporte qu'une proposition externe, des domino double qui comporte

 

 

---- 9 février 2017 ----

 


Dominique Mabboux-Stromberg

 

src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=AM_HTMLorMML-full">