Logique d'égalité

1) Introduction

La logique est dite boolénne ou d'ordre zéro si elle ne consiste qu'en la résolution d'équations boolénennes.

La logique est dite du premier ordre lorsqu'elle ne met en oeuvre qu'un seul type de variable élémentaire susceptible de désigner une infinité d'éléments.

Il est possible de définir des logiques n'utilisant pas de variable élémentaire qui soient plus complexe que la simple logique booléennes, car basée sur des langages d'opérateurs disposant ainsi d'une infinité d'éléments pouvant Ítre égaux entre eux, alors que dans la logique booléennes il n'y a qu'un nombre fini d'inconnnus booléens.

La logique de l'égalité dans un langage d'opérateurs simples peut ne pas utiliser de variable, et constitue une telle logique. Est-elle d'ordre zéro ? c'est à dire peut-on la ramener à la logique booléenne ?.

Une telle logique sans variabe possède un système de déduction assez simple que nous allons décrire : Dans cette logique, nous n'utilisons pas de prédicat autre que l'égalité, et nous n'utilisons pas de variable.

2) Logique et modèle

La logique et les mathématiques sont en fait deux matières distinctes. La logique ne traite pas de la nature des éléments mais uniquement de leurs propriétés logiques, écrites dans des langages logiques et mises sous forme de théories. Alors que les mathématiques, plus vastes, vont construirent les éléments, les ensembles et les modèles qui pourront satisfaire ou non ces théories. La syntaxe du raisonnement revient à la logique tandis que la sémantique du raisonnement revient aux mathématiques.

Mais les fondements mathématiques posent toujours problèmes. Soit on se restreint à un domaine étroit dans une logique du premier ordre pouvant satisfaire des modèles mathématiques. Soit on ne se restreint pas et on reste alors confronté à des paradoxes innombrables rendant toute théorie incohérente si elle ne s'inscrit pas rigoureusement dans un processus constructif. Et il y a d'innombrables processus constructifs, le choix reste arbitraire et détermine à chaque fois une sémantique nouvelle...

Remarquez qu'il y a une différence de nature entre une construction et une hypothèse. Une construction est toujours vrai dans le cadre de la mécanique classique, tandis qu'une hypothèse peut être fausse. Le raisonnement hypothético-déductif est une construction, et l'hypothèse en n'est qu'une de ses parties.

Quelle est la plus petite logique qui ne soit pas triviale c'est à dire ramenée à une logique booléenne ? On peut commencer par la logique de l'égalité dans un langage d'opérateurs, sans prédicat autre que l'égalité et sans variable. Est-ce vraiment une logique ? avec un système de déduction ? et qui ne soit pas trivial ou ramené à une équation booléenne c'est à dire ramenée à une logique d'ordre zéro ? C'est ce à quoi nous allons répondre.

On construit notre logique sur un langage d'opérateurs tel que par exemple :

`{a, f"(.)", g"(.,.)"}`

Auquel cas les éléments considérés par cette logique, que l'on regroupe dans un ensemble noté `Omega`, sont désigné par les termes du langage que l'on regroupe dans un ensemble noté :

`{a, f"(.)", g"(.,.)"}^• =  {a, f(a), g(a,a),f(f(a)), g(a,f(a)),...}`

Autrement dit, l'application qui associe à chaque terme, l'élément qu'il désigne, est une surjection de cet ensemble des termes vers `Omega`. Les propriétés sont des combinaisons logiques d'égalités entre termes telle que par exemple :

`(g(a,f(a))"="a vv g(f(a),a)"="a) <=> f(g(a,a)"="f(a))`

Il n'y a pas de différence entre une propriété et une théorie. La théorie définie une structure. La théorie décrit la syntaxe tandis que la structure décrit la sémantique. C'est pourquoi, on parle de l'une comme de l'autre selon que l'on se focalise sur la syntaxe ou la sémantique.

4) Langage de donnée

La présentation d'un langage est un ensemble énumérable d'opérateurs. Exemple :

`L = {a,f"(.)",g"(.,.)"}`

Les arités sont précisées à l'aide des suffixes `"(.)"` pour l'arité `1`, `"(.,.)"` pour l'arité `2` , etc.., et par absence de suffixe pour l'arité `0`.

La présentation `L` engendre un langage noté `L^•`, par emboitement clos de ses opérateur. Le symbole `•` mis en exposant d'un ensemble d'opérateurs construit cette clôture par emboitement clos.

La présentation `L` engendre une structure notée `"<"L">"` par composition close de ses opérateurs. Les symboles `"<>"` encadrant un ensemble d'opérateurs construisent cette clôture par composition close. Mais attention, la présentation d'une structure est plus complète que la présentation du langage, elle comprend en plus la définition des opérateurs en question ou bien une théorie sur ces opérateurs.

La composition des opérateurs se distingue de l'emboitement des opérateurs par la phase d'évaluation des opérateurs qui sont supposés calculables. Par exemple, en prenant`a=2`, `f(x)=x+4 [8]`, `g(x,y)=x**y [8]` où le symbole `[8]` signifie « compris entre `0` et `7` modulo `8` », nous avons :

Langage :   `L^• = {a,f(a),g(a,a),g(a,f(a)),g(f(a),a), g(f(a),f(a)), g(a,g(a,a)),...}`
Structure :   `"<"L">" = {0,2,4,6}`

On adopte la terminologie suivante :

Un opérateur satisfait deux conditions : Il est soit un élément appartenant à `Omega=<L>` s'il est d'arité nulle, ou soit une application de `Omega->Omega` s'il est unaire, ou soit une application de `Omega^2->Omega` s'il est binaire, etc., ou soit une application de `Omega^n->Omega` s'il est d'arité `n">"0`. Et il appartient à la présentation du langage `L`. LEs opérateurs sont : `a, f"(.)", g"(.,.)"`.

Un terme est un emboitement clos d'opérateurs, ou dit autrement une composition close d'opérateurs non évalués, de telle sorte que deux termes distincts peuvent désigner le même élément. Les termes peuvent ainsi êtres distincts en tant que terme du langage `L`, et égaux en tant qu'élément de `Omega`. Par exemple si nous avons la propriété `g(f(a),a) = f(a)`, alors ces deux termes `g(f(a),a)` et ` f(a)` sont distincts en tant que terme, et sont égaux en tant qu'élément, ou dit autrement, ils désignent le même élément.

L'ensemble des termes se note `L^•` et constitue l'univers de Herbrand, du nom de son concepteur, Jacques Herbrand (1908 Paris - 1931 La Bérarde), mathématicien et logicien français. Le symbole de Kleene généralisé, `•`, placé en exposant, désigne ainsi l'ensemble des termes engendrés par compositions closes finies d'un ensemble d'opérateurs libres. Cet univers de Herbrand `L^•` est aussi appelé le langage `L`, ou encore la structure libre associée au langage `L`.

`L^•={a,f(a),g(a,a),g(a,f(a)),g(f(a),a), g(f(a),f(a)), g(a,g(a,a)),...}`

Les éléments sont désignés par les termes. Mais plusieurs termes distincts peuvent désigner le même éléments. Exemple d'élément : `g(f(a),a)`.

L'ensemble des éléments est `Omega = "<"L">"`. Les crochets `"<>"` désignent ainsi l'ensemble des éléments engendrés par compositions closes d'un ensemble d'opérateurs.

A ce stade le langage permet de désigner tous les éléments de la structure, et constitue ce que l'on appel un langage de donnée. On va lui ajouter le prédicat d'égalité et les connecteurs logiques ce qui va enrichire le langage et le tranformer en un langage de propriété.

5) Langage de propriété

Le prédicat d'égalité `"=(.,.)"` est une application de `(L^•)^2->{0,1}` qui s'applique à deux termes du langage et retourne `0` si les termes désignent deux éléments distincts, et retourne `1` si les deux termes désignent le même élément.

Ainsi, le concept de prédicat incorpore déjà le principe du tiers exclus puisque un prédicat produit un résultat booléen.

Un littéral est une égalité du langage appliquée à deux termes du langage, et qui peut être négativée par le connecteur de négation. Comme le résultat est un booléen, la double négation est identique à l'absence de négation. Et on note la négation en utilisant le symbole `≠` à la place de `=`. Exemples de littéraux : `a"="g(a,a)`, `a"≠"f(a)`.

Une clause est une disjonction de littéraux. Exemple : `f(a)"="a vv g(a,a)"≠"a vv g(a,a)"="f(a)`.

Notez que le prédicat d'égalité est définie à l'ordre près de ses deux arguments, qu'une clause est définie à l'ordre près de ses littéraux, et qu'une conjonction de clause est défiinie à l'ordre près de ses clauses. Cela donne la définition d'un niveau d'expression des théories sans variables n'utilisant que les trois connecteurs `¬, ^^, vv`.

Une théorie est une combinaison logique finie de littéraux faite en utilisant les connecteurs logiques habituels : `{¬, ^^, vv, =>, <=>, ∈}`. Notez que le et logique correspond à l'intersection `nn` et au connecteur `^^`, tandis que le ou logique correspond à l'union `uu` et au connecteur `vv`. Notez qu'il n'y a pas de différence entre une théorie et une propriété, et elles sont par principe de taille finie. On représente souvent une théorie `T` par un ensemble de plus petites théorie, et qui en constitue la conjonction.

La théorie vide correspond à la conjonction vide et est notée `{}`, ou notée `"⊤"`, ou notée true, ou notée `1`.

La théorie pleine est la négation de la théorie vide, notée `"⊥"` ou notée false, ou notée `0`.

L'ensemble des théories exprimable dans le langage `L` avec comme seul prédicat l'égalité et sans variable, se note avec la même lettre mais en lettre ronde `ccL_0` et indicée par zéro pour spécifier qu'il n'y a pas de variable et donc pas de quantificateur.

Déjà, en utilisant que la seul égalité, et sans utiliser de quantificateurs, on établit une logique `ccL_0` loin d'être triviale comme on le verra. Mais pour parachever sa construction, il faut lui donner une sémantique, le sens du vrai et du faux, et il faut définir les règles de déduction qui y sont autorisées. Elles sont basée sur le calcul booléen et sur l'axiome d'égalité que nous allons décrire.

 

 

 

 

 

 

6) Résolution booléenne

Toutes théories se met sous forme d'une conjonction de clause. On considère donc une telle conjonction de clauses et on s'autorise, les règles de transformation suivantes :

  1. Si la théorie est une conjonction vide, alors sa valeur logique est `1`. La théorie constitue une tautologie.
     
  2. S'il y a une clause vide, alors sa valeur logique est `0`, et la valeur logique de la théorie est `0`. La théorie constitue une antilogie.
     
  3. Si un littéral apparait plusieurs fois dans une clause, on retire les occurences de celle-ci en ne gardant à chaque fois qu'un original.
     
  4. S'il apparait dans une clause un littéral et sa négation, alors la clause vaut `1`, elle est tautologique, on retire la clause de la théorie.
     
  5. Etant donnée deux clauses ayant un littéral commun, affirmatif dans l'un et négatif dans l'autre, on ajoute une nouvelle clause, union des deux premières, dans laquelle on a enlevé les deux littéraux.

7) Axiome de l'égalité

L'égalité entre termes est une relation symétrique et transitive, mais cela ne dévoile pas le fondement des règles d'égalités.

`AA (x,y,z)"∈"(L^•)^3,  (x"="y" et "y"="z)   =>   x"="z`

L'axiome de l'égalité se résume en la seule assertion suivante :

Si `x"="y` alors toute propriété est équivalente à la même propriété dans laquel on a remplacé les occurences de `x` par `y`.

Notez que rien n'empêche que les termes évoqués `x` et `y` soient des sous-termes de termes présent dans la propriété.

8) Conjonction d'égalités

Il est possible de construire des théories d'un type encore plus simple, constituée simplement d'une conjonction d'égalités de termes dans un langage tel que `L = {a,f"(.)",g"(.,.)"}`. Par exemple :

`T= {f(a)"="a, g(a,a)"="a}`

Vous remarquerez alors que cette théorie démontre l'égalité `g(g(a,f(a)),f(g(f(a),a)))"="a`, et cela se note comme suit :

`T |-- g(g(a,f(a)),f(g(f(a),a)))"="a`

La démonstration se fait par récurrence, ou plus exactement par un procédé que l'on répète recurrentiellement. Cela est possible sans variable uniquement avec la constante `a`. Car il n'y a pas vraiment de différence entre une variable élémentaire et un élément, et que dans cette logique d'égalité, l'élément `a` va jouer le rôle de variable sans même que le lecteur ne s'en aperçoive. Cela provient de la définition des termes et des éléments. Le terme `a` désigne un élément, mais on ne sait pas lequel, et c'est bien cela la définition d'une variable.

La récurrence est consubstantielle à la notion de structure.

---- 8 décembre 2017 ----

 

 

 

 

 

 

 

 

 

Structure et théorie d'égalité sans quantificateur

4) Théorie sans quantificateur

La présentation d'un langage logique `L` est un ensemble énumérable d'opérateurs notés en minuscule et de prédicats notés en majuscule. Exemple :

`L = {a,f"(.)",g"(.,.)", A, B"(.)", R"(.,.)"}`

Les arités sont précisées à l'aide des suffixes `"(.)"` pour l'arité `1`, `"(.,.)"` pour l'arité `2` , etc.., et par absence de suffixe pour l'arité `0`.

On adopte la terminologie suivante :

Un opérateur satisfait deux conditions : Il est soit un élément appartenant à `Omega` s'il est d'arité nulle, ou soit une application de `Omega->Omega` s'il est unaire, ou soit une application de `Omega^2->Omega` s'il est binaire, etc., ou soit une application de `Omega^n->Omega` s'il est d'arité `n">"0`. Et il appartient à la présentation du langage `L`. Exemples d'opérateurs : `a, f"(.)", g"(.,.)"`.

Un prédicat satisfait deux conditions : Il est soit une valeur booléenne appartenant à `{0,1}` s'il est d'arité nulle, ou soit une application de `Omega->{0,1}` s'il est unaire, ou soit une application de `Omega^2->{0,1}` s'il est binaire, etc., ou soit une application de `Omega^n->{0,1}` s'il est d'arité `n">"0`. Et il appartient à la présentation du langage `L`. Exemples de prédicats : `A, B"(.)", R"(.,.)"`. Et on ajoute un prédicat binaire supplémentaire qui est l'égalité `"=(.,.)"`, qui est symétrique, entendez par là que `u=v` et `v=u` désigne le même littéral, et qui jouera un rôle particulier dans les règles de déduction.

Ainsi, le concept de prédicat incorpore déjà le principe du tiers exclus puisque un prédicat produit comme résultat un booléen.

Un terme est un une composition close finie d'opérateurs non évaluée, de telle sorte que deux termes distincts peuvent désigner le même élément. Les termes peuvent ainsi êtres distincts en tant que terme du langage `L`, et égaux en tant qu'élément de `Omega`. Par exemple si nous avons la propriété `g(f(a),a) = f(a)`, alors ces deux termes `g(f(a),a)` et ` f(a)`, sont distincts en tant que terme, et sont égaux en tant qu'élément.

L'ensemble des termes se note `L^•` et constitue l'univers de Herbrand, du nom de son concepteur, Jacques Herbrand (1908 Paris - 1931 La Bérarde), mathématicien et logicien français. Le symbole de Kleene généralisé, `•`, placé en exposant, désigne ainsi l'ensemble des termes engendrés par compositions closes finies d'un ensemble d'opérateurs libres. Notez que les prédicats n'interviennent pas dans ces compositions. Cet univers de Herbrand `L^•` est aussi appelé la structure libre associée au langage `L`. Par construction, l'ensemble des termes est un ensemble énumérable.

`L^•={a,f(a),g(a,a),g(a,f(a)),g(f(a),a), g(f(a),f(a)), g(a,g(a,a)),...}`

Les éléments sont désignés par les termes. Mais à priori et sans preuve du contraire, ils n'épuisent pas `Omega`. Les autres éléments de `Omega` non désignés par les termes s'appelleront nouveaux éléments. Exemple d'élément : `g(f(a),a)`.

L'ensemble des éléments se note `"<"L">"`. Les crochets `"<>"` désignent ainsi l'ensemble des éléments engendrés par compositions closes finies d'un ensemble d'opérateurs. Notez que comme précédement les prédicats n'interviennent pas dans ces compositions, et que ces compositions sont évalués pour produire des éléments. Par construction, cet ensemble des éléments est un ensemble énumérable.

Le langage logique sans quantificateur est constitué de toutes les combinaisons logiques finie sans quantificateur, appelées théories sans quantificateur, qu'il est possibles de construire à l'aide des seuls prédicats du langage appliqués aux seuls éléments du langage et en utilisant les connecteurs logiques habituels : `{¬, ^^, vv, =>, <=>}`. Un moyen mémotechnique pour savoir qu'elle symbole représente le et logique et le ou logique : le et logique correspond à l'intersection `nn` et au symbole `^^`, tandis que le ou logique corerespond à l'union `uu` et au symbole `vv`. Notez que les théories comme les termes sont par principe de taille finie.

Un littéral est un prédicat du langage appliqué à des éléments du langage, et qui peut être négativé par le symbole de négation. Comme le résultat est un booléen, la double négation est identique à l'absence de négation. Exemples de littéraux : `"¬"A`, `B(a)`, `a"="g(a,a)`, `a"≠"f(a)`, `"¬"R(a,a)`.

Une clause est une disjonction de littéraux. Exemple `f(a)"="a vv "¬"B(a) vv R(a,a)`, que l'on note aussi par `f(a)"="a|"¬"B(a)|R(a,a)`.

Notez qu'une clause est définie à l'ordre près de ses littéraux. De même une conjonction de clause est défiinie à l'ordre près de ses clauses.

Une théorie sans quantificateur est une combinaison logique finie de littéraux. On représente souvent une théorie `T` par un ensemble de plus petites théories, et qui en constitue la conjonction.

La théorie vide correspond à la conjonction vide et est notée `{}`, ou notée `"⊤"`, ou notée true, ou notée `1`.

La théorie pleine est la négation de la théorie vide, notée `"⊥"` ou notée false, ou notée `0`.

L'ensemble de toutes les théories sans quantificateur exprimable dans le langage `L` se note avec la même lettre mais en lettre ronde `ccL_0` et indicée par zéro pour spécifier qu'il n'y a dans ce langage logique aucun quantificateur. Par construction, cet ensemble des théories sans quantificateur noté `ccL_0` est un ensemble énumérable.

Déjà, sans utiliser de quantificateurs, on établit une logique `ccL_0` loin d'être triviale comme on le verra. Mais pour parachever sa construction, il faut lui donner une sémantique, le sens du vrai et du faux, et il faut définir les règles de déduction qui sont autorisées dans cette logique `ccL_0`. Cela est-il possible ?. Le raisonnement dans cette logique ne nécessite-t-il pas d'utiliser des quantificateurs ?, ainsi que de nouveaux opérateurs et prédicats ?

5)

5) Le langage propositionnelle

L'étude des connecteurs logiques et du calcul booléen nous permet de définir une relation d'équivalence sur l'ensemble des théories sans quantificateur `ccL_0` que l'on note par le symbole `=_0` et qui n'associe que des théories logiquement équivalentes entre-elles. Et par cette seul relation d'équivalence, toute théorie sans quantificateur se décompose de façon unique en une conjonction de clauses.

----- 15 octobre 2017 -----

 

 

 

 

 

 

 

 

`"<"L">"` représente l'ensemble des éléments engendrés par `L`
`"<"T">"` représente l'ensemble des théories engendrées par `T`

Pour toutes théories `A`, `B` écrites dans le langage `L`, on note `A|--B` pour signifier que la théorie `B` se déduit de la théorie `A` à l'aide des règles de déduction que nous allons décrire, et cela signifie que `B` est engendrée par `A`, c'est à dire que `B in "<"A">"`, ou encore que `"<"B">" sube "<"A">"`.

 

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

Comme nous l'avons déjà précisé, nous allons construire la sémanique à partir de la seul syntaxe. Nous allons construire un modèle devant satisfaire la théorie à partir de la théorie elle-même et de son langage.

Il nous faut définir les valeurs de vérité vrai et faux, et la négation doit être une symétrie permettant de passer de l'une à l'autre. Autrement dit, la négation doit être 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, c'est à dire si et seulement si `"<"T">"=ccL_0`, l'ensemble de toutes les théories sans quantificateur exprimables dans le langage `L`. Et, par négation de cette caractéristique, une théorie `T` est dite cohérente si et seulement si il existe au moins une théorie `A` dans le langage `L` que `T` ne peut pas démontrer.

Ainsi on définie le faux comme une théorie incohérente.

Il existe un moyen intérieur au langage pour définir de façon absolue, le vrai, grâce au sens de l'implication. Une théorie `T` est dite incohérente si et seulement si `T` démontre tout, c'est à dire si et seulement si `"<"T">"=ccL_0`, l'ensemble de toutes les théories sans quantificateur exprimables dans le langage `L`. Et, par négation de cette caractéristique, une théorie `T` est dite cohérente si et seulement si il existe au moins une théorie `A` dans le langage `L` que `T` ne peut pas démontrer.

et on définie le vrai comme une théorie nécessaire.

`T⊬A`

----- 15 octobre 2017 -----

 

Antilogie : Une proposition sera dite fausse si et seulement si elle démontre tout.
Totologie : 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"⊢⊤"`

`AA A,  "⊥⊢"A` `AA A,  A"⊢⊤"`
`"<⊥>"` est l'ensemble des propositions. `"<⊤>"` 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`.

5) Structure

Puisque on ne veut pas s'investire de toute la mathématique mais de la seul logique. On construit la structure sur laquelle reposera le raisonnement, à partir du seul langage logique et de ses constructions syntaxiques appelées règles de déduction. Ou autrement dit, on construit la sémantique à partir de la seul syntaxe. On construit le modèle censé satisfaire la théorie à partir de la théorie elle-même.

Une théorie sans quantificateur telle que décrite précédement comprend implicitement un langage, le langage dont la présentation est constituée des opérateurs et prédicats qui sont mentionnés au moins une fois dans la théorie. En cela, il y a bien dans la théorie, une partie déclarative qui déclare les opérateurs et prédicats utilisés, et donc qui déclare un langage.

Une structure est l'association d'un langage `L` et d'une théorie `T` écrite dans ce langage, et on la représente sous forme d'un quotient

`L"/"T`   

Il est toujours possible d'ajouter au langage placé au numérateur de nouveaux opérateurs et de nouveaux prédicats. Et il est toujours possible d'ajouter à la théorie placée au dénominateur des propositions supplémentaires écrites dans le langage placé au numérateur.

La structure `L"/"T` est l'ensemble des éléments engendrés par `L`, muni des opérateurs et prédicats de la présentation du langage `L`, et satisfaisant la théorie `T`.

`"<"L">"` représente l'ensemble des éléments engendrés par `L`
`"<"T">"` représente l'ensemble des théories engendrées par `T`

Pour toutes théories `A`, `B` écrites dans le langage `L`, on note `A|--B` pour signifier que la théorie `B` se déduit de la théorie `A` à l'aide des règles de déduction que nous allons décrire, et cela signifie que `B` est engendrée par `A`, c'est à dire que `B in "<"A">"`, ou encore que `"<"B">" sube "<"A">"`.

L'engendrement se fait par un procédé calculatoire, et donc n'engendre par principe que des ensembles énumérables. Il existe un procédé de calcul qui énumère tous les éléments de `"<"L">"` et toutes les théories de `"<"T">"`. Les règles de déduction forment un énumérateur qui appliqué à une théorie `A` va énumérer toutes les déductions possibles exprimables dans le langage `L`. Ainsi, si une théorie se déduit de `A` alors l'énumérateur produira en un temps fini cette théorie. Par contre si la théorie n'est pas déduisible de `A` nous n'avons aucun procédé qui nous assure de pouvoir le découvrir en un temps fini. Autrement dit, le complément de `"<"T">"` dans l'ensemble de toutes les théories exprimables dans le langage `L` peut ne pas être énumérable.

La théorie vide qui correspond à la conjonction vide, notée `"⊤"` (ou notée `{}`, ou notée true, ou notée `1`) est toujours vrai. Elle engendre l'ensemble `"<⊤>"` qui est l'ensemble de toutes les totologies écrivables dans le langage `L`.

La théorie incohérente, notée `"⊥"` (ou notée false, ou notée `0`) est toujours fausse. Elle engendre l'ensemble `"<⊥>"` qui est l'ensemble de toutes les théories écrivables dans le langage `L`.

5) Structure déterminée

Une telle structure `L"/"T` peut être floue, et ainsi en quelque sorte, être dans plusieurs états à la fois.... Par analogie à la mécanique quantique, la structure se comporte comme un système physique pouvant se trouvant dans plusieurs états quantiques à la fois. On considère que son état est déterminé si et seulement si la théorie `T` est complète pour l'égalité c'est à dire que pour tout couple de termes `u` et `v` appartenant à `L^•`, la théorie doit toujours trancher la question en temps fini, si `u` est égal ou non à `v` en tant qu'élément. Autrement dit, la théorie `T` doit satisfaire la propriété suivante :

`AAu"∈"L^•, AAv"∈"L^•,  (T|--u"="v) vv (T|--u"≠"v)`

La relation d'égalité définie dans `T` forme une relation d'équivalence sur la structure libre `L^•`, et les classes d'équivalences de termes forment les éléments. La notation `L"/"T` pour désigner la structure, prend alors tout sont sens comme étant la division de l'ensemble `L^•` par la relation d'équivalence qu'est l'égalité `"=(.,.)"` définie par `T`, une division en des parties de taille non nécessairement égale que sont les classes d'équivalences de termes. Les éléments de la structure `L"/"T` sont exactement les classes d'équivalences de termes de `L^•`.

La complétude de `T` pour l'égalité entraine que chaque élément de la structure est un sous-ensemble énumérable de `L^•` dont le complément dans `L^•` est également énumérable.

Mais la plus part du temps la théorie `T` n'est pas complète pour l'égalité. Dans ce cas, selon l'adage des intuitionnistes comme quoi il n'y a rien au delà de l'infini, l'incomplétude de la théorie sur l'égalité entres deux termes `u` et `v`, ne s'interprète alors que de trois façons possibles qui sont les trois sens que l'on peut donner à l'assertion suivante :

 `(T"⊬"u"="v) ^^ (T"⊬"u"≠"v")`

Cela signifie que `T` ne tranche pas la théorie `{u=v}`, ou dit autrement que `T` est indépendant de la théorie `{u=v}`. Et donc que :

T ^^u=v est cohérent

 

 

Soit on considère que les éléments `u` et `v` sont distincts mais d'une distinction non déclarée. Soit on considère qu'il sont égaux mais d'une égalité non déclarée. Soit on considère un troisième état logique ni distinct ni égaux, qui entre alors dans le cadre d'une logique ternaire.

On dira que `u` et `v` sont indiscernable si et seulement si `T"⊬"u"≠"v"`

Les deux premier cas définissent deux relations d'équivalences, la relation dite d'indiscernablité noté `~_T`, et une relation plus étroite dite d'égalité déclaré notée `=_T`.

`u~_Tv <=> (T"⊬"u"≠"v)`

`=_T`<=> (T"⊢"u"≠"v)`

-----------

 

 

 

On note u=v si et seulement si T|-u=v. L'égalité ainsi définie forment une relation d'équivalence sur `L^•` :

Reflexive : `Ax,  x"="x`
Symétrique : `AxAy,  x"="y => y"="x`
Transitive : `AxAyAz,  (x"="y ^^ y="z) =>x"="z`

 

 

 

6) Extension

Une variable est désignée par toute nouvelle lettre minuscule ne figurant pas dans la présentation du langage. La variable est un nouvel opérateur et possède une arité. La variable enrichie le langage. On parlera de l'univers de Herbrand étendu, du langage étendu. Le procédé consistant à ajouter ces nouveaux opérateurs s'appelle une extension.

L'extension est dite élémentaire si le nouvel opérateur `x` ajouté est d'arité nulle. L'opérateur est ajouté dans le langage `L`, c'est à dire dans sa présentation, et on obtient un nouveau langage que l'on note `L[x]` :

`L = {a,f"(.)",g"(.,.)"}`
`L[x] = {a,x,f"(.)",g"(.,.)"}`

Et on obtient une nouvelle structure que l'on note `S[x]` :

`S = L"/"T`
`S[x] = L[x]"/"T`

L'extension est dite intérieure si on ajoute à la théorie la condition `x"∈"L`. Et l'extension est dite extérieure si on ajoute à la théorie la condition inverse `x"∉"L`.

Il est possible de procéder à plusieurs extensions élémentaires à la suite. Par exemple on note `S[x][y][z]` simplement `S[x,y,z]`, une extension de la structure `S` par trois nouveaux opérateurs d'arité nulle `x,y,z`.

L'extension est dite unaire si le nouvel opérateur `h` ajouté est d'arité un. L'opérateur est ajouté dans le langage `L`, c'est à dire dans sa présentation, et on obtient un nouveau langage que l'on note `L[h"(.)"]` :

`L = {a,f"(.)",g"(.,.)"}`
`L[h"(.)"] = {a,f"(.)",h"(.)",g"(.,.)"}`

Et on obtient une nouvelle structure que l'on note `S[h"(.)"]` :

`S = L"/"T`
`S[h"(.)"] = L[h"(.)"]"/"T`

L'extension est dite intérieure si on ajoute à la théorie la condition `AAx,  h(x)"∈"L`. L'extension est dite extérieure si on ajoute à la théorie la condition inverse `EEx,  h(x)"∉"L`.

Il est possible de procéder à plusieurs extensions à la suite, et par exemple on note `S[x][h"(.)"]` simplement `S[x,h"(.)"]`.

5) Morphisme

(à simplifier)

Un morphisme est une application entre deux structures de même patronage qui respecte la forme. Mais pour comprendre cette phrase, il faut définir ce qu'est un patronage. Comme reconnait-on deux structures de même patronage ?. Il faut pouvoir définir un langage commun aux deux structures. Il faut pouvoir associer de façon biunivoque, en respectant les arités, les opérateurs générateurs d'une structure avec les opérateurs générateurs de l'autre structures. La signature de leur langage doit donc être identique.

La signature d'un langage d'opérateurs est la liste des nombres d'opérateurs pour chaque arité. Par exemple la signature de `L` est `(1,1,1)` car la présentation de `L` contient exactement `1` opérateur d'arité nulle, `1` opérateur unaire et `1` opérateur binaire.

Mais une même signature de langage ne suffit pas, il convient en plus de disposer les opérateurs de même arités selon un ordre précis. Le patronage de la structure ou de son langage, c'est la signature du langage, mais dans lequel on ajoute en plus, un ordre total dans chaque groupe d'opérateurs ayants la même arité.

Un patronage est donc quelque chose d'un peu plus riche que la présentation anonymisée d'un langage. Il incorpore ces ordres. Par convention, le patronage se présente sous forme d'une liste sachant que l'ordre n'a d'importance que dans les groupes d'opérateurs de même arité. Par exemple considérons les deux patronages de signature `(1,2)` suivants :

`L_1 = (a,f"(.)",h"(.)")`
`L_2 = (a,h"(.)",f"(.)")`

L'ordre d'apparition de `f"(.)"` par rapport à `h"(.)"` joue un rôle. Les patronages `L_1` et `L_2`, sont distincts. Le patronage `L_1` admet comme premier opérateurs unaire, l'opérateur `f"(.)"`, et comme second opérater unaire, l'opérateur `h"(.)`. Parcontre, en terme de langage d'opérateurs, ce sont deux mêmes langages, mais celui-ci ne sera pas le langage commun.

Etant donné un patronage utilisant des opérateurs non prédéfinie, l'arité d'un opérateur et sa position au sein du groupe de même arité suffit à détermine l'opérateur. C'est pourquoi deux structures de même patronage possède un langage commun, le langage obtenu en renomant les opérateurs par leur caractéristiques comprenant leur arité et l'ordre s'il y en a plusieurs de même arité.

Le patronage permet d'anonymiser tout langage d'opérateurs.

Un morphisme est relatif à un patronage. Le morphisme doit respecter chaque opérateur du patronage qui constitue un langage commun à plusieurs structures. Par exemple considérons deux structures de même patronage :

`S_1 = (a_1, f_1"(.)", g_1"(.,.)") "/" T_1`
`S_2 = (a_2, f_2"(.)", g_2"(.,.)") "/" T_2`

Il y a une correspondance biunivoque des opérateurs entre les deux structures comme suit :

`((a_1|->a_2), (f_1|->f_2), (g_1|->g_2))`

Cette correspondance fait qu'il est possible de parler d'un unique langage qui peut être interprété dans l'une ou l'autre structure.

Une application `varphi` de `S_1 -> S_2` est un morphisme si et seulement si quelques soient `x` et `y` appartenant à `S_1` nous avons :

`varphi(a_1)=a_2`
`varphi(f_1(x))=f_2(varphi(x))`
`varphi(g_1(x,y))=g_2(varphi(x),varphi(y))`

Si de plus le morphisme est injectif alors c'est un plongement et la structure `S_1` est abstraitement inclus dans `S_2`, ce qui se note `S_1"↪"S_2` ou plus précisement `S_1"↪"_varphi S_2`

Si de plus le morphisme est bijectif alors c'est un isomorphisme, et les deux structures sont dite isomorphes, ce qui se note `S_1 ~= S_2` ou plus précisement `S_1 ~=_varphi S_2`

 

--- 14 octobre 2017 ---

 

 

 

 

5) Quantification

Considérons une variable `x` appartenant à `L`. Cela constitue une extension interieur de la structure `L`. Puis considérons la proposition `AAx  B(x)`. Le quantificateur `AA` appliqué à la variable `x` correspond à un `"et"` logique intégré sur l'ensemble des valeurs possibles de `x` c'est à dire sur l'ensemble des éléments de la structure `L`

L'opérateur `"et"` est représenté par le symbole `^^` similaire à l'intersection. Nous avons :

`(AAx  B(x))   <=>   ^^^_(x in L) B(x)`

L'ensemble des valeurs possible de `x`, qui est l'ensemble sous-jacent de la structure `L`, est par principe énumérable. Cela entraine que la proposition `AA x, P(x)` est réfutable en un temps fini dans le cas où celle-ci serait fausse. Et il s'agit là d'une périssologie car on définie justement la valeur logique fausse de cette proposition par le fait qu'elle doit être réfutée en un temps fini. Parcontre dans le cas où elle ne serait pas fausse, on remarquera qu'elle n'est pas assurement affirmable en un temps fini. Et en effet, on verra que l'affirmation d'une telle proposition peut dans certain cas constituer un oracle.

En tant qu'idée mathématique sans contrainte matériel ni temporelle d'aucune sorte, on peut se placer à l'infini des temps et ainsi connaître l'oracle. Mais il faut en quelque sorte, être immortel dans un monde immortel et de surcroit régit par une mécanique classique, somme-toute, des présupposés assurement faux, mais qui à notre échelle sont approximativement vrai. Si on adopte ce principe qui correspond au présuposé des mathématiques, à savoir que le monde dans le quel est développé cette mathématique perdure éternellement et est régis par une mécanique abstraite mais classique, et que nous pouvons nous placer abstraitement à l'infini des temps et ainsi connaitre la valeur logique de la proposition, alors toutes les propositions exprimables dans notre langage ont une valeur logique bien définie.

La négation de cette propostion s'obtient simplement en inversant les quantificateurs et en négativant les combinaisons selon une loi de Morgane étendu aux suites énumérables.

`¬(AAx  B(x))   <=>   (EEx  ¬B(x))`
`¬(EEx  B(x))   <=>   (AAx  ¬B(x))`

Le quantificateur `EE` appliqué à la variable `x` correspond à un `"ou"` intégré sur l'ensemble des valeurs possible de `x`. L'opérateur `"ou"` est représenté par le symbole `vv` similaire à l'union. Nous avons :

`(EEx  B(x))   <=>   vvv_(x in L) B(x)`

Même remarque que précédement, cette proposition, dans le cas où elle ne serait pas vrai, n'est pas assurement réfutable en un temps fini. La réfutation d'une telle proposition peut dans certain cas constituer un oracle.

Le `AA x` constituant un `"et"` logique intégré sur `L`, et le `EE y` constituant un `"ou"` logique intégré sur `L`, nous pouvons conclure un certain nombre de règles sur les quantificateurs.

--- 25 septembre 2017 ---

 

On considère considère la variables booléennes `A`, les prédicats `B(.), C(.)` et le prédicat `R(.,.)`, qui peuvent être définis librement dans la théorie de la structure. Nous avons :

Associativité du `"et"` :
`(AAx  B(x)) "et" A`
`<=>`
`AAx  B(x) "et" A`
`(AAx  B(x)) "et" (AAy  C(y)) `
`<=>`
`AAx  B(x) "et" C(x)`
`AAx  B(x) "et" AAy  R(x,y)`
`<=>`
`AA(x,y)  B(x) "et" R(x,y)`

 

Distributivité du `"ou"` par rapport au `"et"` :

`(AAx  B(x)) "ou" (AAy  C(y)) `

`(^^^_(x in L) B(x)) "ou" (^^^_(y in L) C(y))`

`(B(1) "et" B(2) "et" B(3) "et" ...) "ou" (C(1) "et" C(2) "et" C(3) "et" ...)`

`^^^_((x,y) in L^2) B(x) "ou" C(y))`

`AA(x,y)  B(x) "ou" C(y)`

 

Distributivité du `"ou"` par rapport au `"et"` :

`(AAx  B(x)) "ou" (AAy  C(y)) `
`<=>`
`AA(x,y)  B(x) "ou" C(y)`
       
 
`AAx  B(x) "ou" AAy  R(x,y)`
`<=>`
`AA(x,y)  B(x) "ou" R(x,y)`

 

`(AAx  B(x)) "ou" (EEy  C(y)) `

`(^^^_(x in L) B(x)) "ou" (vvv_(y in L) C(y))`

`(B(1) "et" B(2) "et" B(3) "et" ...) "ou" (C(1) "ou" C(2) "ou" C(3) "ou" ...)`

 

`^^^_((x,y) in L^2) B(x) "ou" C(y))`

`AA(x,y)  B(x) "ou" C(y)`

 

 

 

 
`(AAx  B(x)) "ou" (AAy  C(y)) `
`<=>`
`AA(x,y)  B(x) "ou" C(y)`
 
`AAx  B(x) "ou" AAy  R(x,y)`
`<=>`
`AA(x,y)  B(x) "ou" R(x,y)`
`(AAx  B(x)) "ou" A`
`<=>`
`AAx  B(x) "ou" A`
`(AAx  B(x)) "ou" (AAy  C(y)) `
`=>`
`AAx  B(x) "ou" C(x)`

 

 

6) L'indépendance

 

 

Associativité du `"et"` :
`AAxAAy  R(x,y)`
`<=>`
`AA(x,y)  R(x,y)`
Associativité du `"ou"` :
`EExEEy  R(x,y)`
`<=>`
`EE(x,y)  R(x,y)`
Indépendance de `y` par rapport à `x`
`EEyAAx R(x,y)`
`=>`
`AAxEEy R(x,y)`

 

 

 


   <=>   
   =>    

<=>
<=>

 

 

 

 

 

 


Dominique Mabboux-Stromberg

 

 

 

 

 

 

 

 

 

 

 

Et pour les élémentariens, cet ensemble est un ensemble d'éléments énumérable quelconque. Et cela revient à dire que l'on se place dans l'ensemble des entiers naturels `bbbN`. Et ce n'est pas un infini immanent puisqu'il se construit par un processus récurcif. Le seul postulat est notre capacité d'abstraction à nous projeter aussi loin que l'on veut dans le temps, et à concevoir l'oracle, c'est à dire à se placer à la fin des temps pour le vérifier.

essai structure-principe

 

 

Par construction, l'ensemble des termes `L^•` étant énumérable et désignant les éléments (par évaluation calculable), l'ensemble des éléments est énumérable.

Par construction, l'ensemble des théories `ccL_0` est énumérable.

3) Proto-ensemble des éléments

On évacue la question de la nature des éléments, en considérant un proto-ensemble `Omega` de tous les éléments et comprenant les nouveaux éléments, les éléments qui n'ont pas été prévus initialement. Et ce n'est pas vraiment un ensemble car nous ne posons aucune hypothèse sur ce proto-ensemble. Mais son rôle de support sur lequel vont être construites les règles de déduction logique, va lui donner un sens mathématique que l'on pourra alors décrire.

Et on étudie les théories d'égalités sans prédicats et sans variable. La théorie est écrite dans un langage. Le langage est décrit par une présentation qui est un ensemble d'opérateurs.

Les éléments sont désignés par les termes. Mais à priori et sans preuve du contraire, ils n'épuisent pas `Omega`. Les autres éléments de `Omega` non désignés par les termes s'appelleront nouveaux éléments. Exemple d'élément : `g(f(a),a)`. Mais rappelez-vous que plusieurs termes distincts peuvent désigner le même éléments.