I) Structure
selon le point de vue élémentarien

Sommaire :

  1. Introduction
  2. Structure
  3. Langage d'opérateurs
  4. Sous-structure
  5. Langage d'une structure
  6. Constructeur

1) Introduction

"Les élémentariens ne font que calculer" (Les Chroniques de Riddick)

Les mathématiques élémentariennes sont jumelles de l'informatique, n'usant comme seul fondement, le langage et la programmation. Tout doit être calculable, tout doit être constructible.

La formalisation des démonstrations entraine une complexité qui nuit à la compréhension globale, noyant l'important dans le détail. Mais le choix d'un langage adapté résoud d'autant cette complexité. Ne dit-on pas que l'exposé d'un problème dans un langage adapté constitue la moitier de sa résolution ?

Au départ, toutes les structures sont finies. Puis, usant de la capacité énumérative des programmes, on construit des structures infinies, désignées par les programmes qui les énumèrent, et qui eux, sont de taille finie.

Tout n'est que construction. Un élément est une construction dans un langage d'opérateurs, qui sert de référence pour désigner toute chose que nous construisons. Selon ce principe, un élément ne peut contenir qu'une quantité finie d'information.

Un élément est perçue de multiple façons, par autant de représentations que sa construction peut l'exiger. L'ensemble de ces représentations forme une classe d'équivalence, qui résulte donc d'une relation d'équivalence. Et c'est cette relation d'équivalence qui fait le lien entre l'élément et la théorie.

2) Structure

Une structure est un ensemble muni d'une liste d'opérateurs générateurs qui l'engendre.

L'ensemble des éléments de la structure s'appelle l'ensemble sous-jacent. Et l'ensemble des opérateurs générateurs s'appelle la présentation. La structure et son ensemble sous-jacent sont désignés par la même lettre (car l'ensemble n'existe que parceque la structure le construit). La présentation d'une structure `S` se note `"℗"S`

Les première structures infinies construites sont les langages d'opérateurs.

3) Langage d'opérateurs

Un langage d'opérateurs est engendré par une liste de nouveaux opérateurs qui en constituent sa présentation. Les opérateurs sont présentés en minuscule entre crochet `"<>"`, et ils engendrent le langage par composition close, nommé l'univers de Herbrand, du nom de son concepteur, Jacques Herbrand (1908 Paris - 1931 La Bérarde), mathématicien et logicien français.

Par exemple :

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

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`. Les symboles `"<>"` entourant une séquence d'opérateurs, crée l'ensemble engendré par compostion close de ces opérateurs.

Les éléments du langage s'appellent des termes.

Le langage forme une structure libre : Deux termes distincts du langage d'opérateurs désignent forcement deux éléments distincts de la structure.

La présentation de la structure `L` est :

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

Et les opérateurs `a,f"(.)",g"(.,.)"` sont dit libres, c'est à dire qu'ils ne sont pas prédéfinis, leurs compositions, afin qu'elles ne perdent aucune information, correspondent excatement à leurs emboitements. Et ce comportement est implicite pour tout nouvel opérateur.

L'ensemble sous-jacent de la structure `L` est :

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

4) Sous-structure

Une structure est engendrée par une liste d'opérateurs qui en constituent sa présentation. Les opérateurs sont présentés en minuscule entre crochet `"<>"`, et ils engendrent la structure par composition close.

` S = "<"a,f"(.)",g"(.,.)>"`
`"℗"S= {a,f"(.)",g"(.,.)"}`

On ne peut pas énumérer les compositions closes entre crochet d'ensemble `{}` car certaines de ces compositions sont égales entre elles. Les opérateurs `a,f"(.)",g"(.,.)"` sont ici prédéfinis et ils appartiennent donc à un structure antérieure plus vaste `Omega`, et donc ils engendrent par composition close une sous-structure de `Omega`, ce qui se note :

`S"⊑"Omega`

Une sous-structure au sens de l'inclusion est un sous-ensemble munie d'une sous-présentation sachant que toute structure est engendrée par sa présentation. Autrement dit si `A` est `B` sont deux structures, nous avons :

`A"⊑"B    <=>    ((A sube B),("℗"A sube "℗"B))`

5) Langage d'une structure

A chaque structure `S` est associée une structure libre qui est son langage et que l'on nomme Lang`(S)`. On procède ainsi : On duplique chaque opérateur de la présentation de `S` en un opérateur de même arité, mais libre, qui est son nom et que l'on nomme pareillement mais en lettre droite, et qui appartient à la présentation du langage Lang`(S)`. On notera habituellement les variables désigant un terme du langage en lettre droite.

La bijection de `"℗"S->"℗"`Lang`(S)`, qui transforme chaque opérateur en son double libre, s'appelle l'application nom. Et l'application inverse qui transforme le nom d'un opérateur en l'opérateur en question, s'appelle val. L'une transforme l'opérateur en son nom qui constitue un opérateur libre de même arité dans la présentation du langage, `"℗"`Lang`(S)`. L'autre transforme le nom d'un opérateur en sa valeur qui est l'opérateur en question dans la présentation de la structure, `"℗"S` :

Présentation de la structure : `"℗"S= {a,f"(.)",g"(.,.)"}`
Présentation du langage de la structure : `"℗"`Lang`(S)={"a","f(.)","g(.,.)"}`

Opérateur libre
du langage de la structure
Opérateur
de la structure
`"a" = "nom"(a)`
`a = "val"("a")`
`"f(.)"= "nom"(f)"(.)"`
`f"(.)"= "val"("f")"(.)"`
`"g(.,.)" = "nom"(g)"(.,.)"`
`g"(.,.)" = "val"("g")"(.,.)"`

La présentation du langage Lang`(S)` est composée d'une copie libre des opérateurs de la présentation de la structure `S`. La structure Lang`(S)` est une structure libre. C'est un langage d'opérateurs :

`"℗"`Lang`(S)={"a","f(.)","g(.,.)"}`
Lang`(S) = "<""a","f(.)","g(.,.)>"`
Lang`(S) = {"a","f"("a"),"g"("a","a"),"g"("a","f"("a")),"g"("f"("a"),"f"("a")),"g"("a","g"("a","a")),...}`

Les éléments de ce langage Lang`(S)` sont appelés des termes.

6) Constructeur

L'application qui transforme chaque terme du langage Lang`(S)` en un élément de `S` se note `s` avec la même lettre que la structure mais en minuscule. C'est un morphisme surjectif. On l'appelle l'évaluateur dans `S` lorsque les éléments de `S` sont appelés des résultats, ou encore, on l'appelle le constructeur de `S` lorsque les éléments de `S` sont appelés des objets.

`AA("u","v")"∈"`Lang`(S)^2`

`s = (("Lang"(S)->>S),("a"|->a),("f"("u")|->f(s("u"))), ("g"("u","v")|->g(s("u"),s("v"))))`

`AA "o∈℗"`Lang`(S)  s("o") = `val`("o"),`
`AA "o(.)∈℗"`Lang`(S)  s("o"("u")) = `val`("o")(s("u")),`
`AA "o(.,.)∈℗"`Lang`(S)  s("o"("u","v")) = `val`("o")(s("u"),s("v"))` 

Le morphisme surjectif `s` de Lang`(S)->>S` induit une relation d'équivalence sur Lang`(S)`. Deux termes `"u"` et `"v"` sont équivalents, ce qui ce note par `"u""="_s"v"` si et seulement si leur évaluation ont même résultat c'est à dire si et seulement si `s("u")"="s("v")`. Cela signifie que pour le constructeur `s`, les termes `"u"` et `"v"` sont équivalents et donc désignent le même élément dans "`S`".

`AA("u","v")"∈"`Lang`(S)^2,   "u""="_s"v"  <=>  s("u")"="s("v")` 

Les classes d'équivalence regroupent tous les termes de même valeur. L'application `s` de Lang`(S)->>S` partitionne l'ensemble Lang`(S)` en classes d'équivalence. ce qui se note comme suit :

`("Lang"(S)"/="_s)  =  {E sube`Lang`(S) "/"`
                                        `AA("u","v")"∈"`Lang`(S)^2,`
                                               `("u∈"E "et" "v∈"E) =>"u""="_s"v",`
                                               `("u∈"E "et" "v∉"E)=> "u""≠"_s"v"`
                                 `}`

Et on note `s^-1` l'application inverse :

`s^-1 = ((S->>"Lang"(S)"/="_s), (x|-> {"u" "/" s("u")=x}))`

L'élément `x` admet de multiple représentations qui sont regroupées dans la classe d'équivalence `{"u" "/" s("u")=x}`. Il est donc possible de construire une structure ayant comme éléments ces classes d'équivalences. Elles se note sous forme d'un quotien d'une structure et d'une relation d'éuivalence :

`"Lang"(S)"/="_s`

On définie une application inverse de cette application `s^-1`, qui transforme chaque classe d'équivalence en un de ses éléments pris au hasard de la contingence, et on la note `"↓"`. A l'aide de cette application, on peut calculer les opérateurs générateurs de la structure `"Lang"(S)"/="_s`.

`"℗"("Lang"(S)"/="_s) = {s^-1(a), "↓"fs^-1"(.)", ("↓","↓")gs^-1"(.,.)"}`

ou en notation anglaise `= {s^-1(a), s^-1@f@"↓""(.)", s^-1@g@("↓","↓")"(.,.)"}`

Et `s^-1` constitue un isomorphisme de `S` vers `"Lang"(S)"/="_s`. Cette isomorphisme est une propriété de construction. Il est utile de trouver des notations pratiques pour mettre en forme ces calculs, car cela débouche sur la conception de nouveaux langages de programmation.

Puis on formalise un moyen de construire une structure à partir d'une autre en la quotientant par une relation d'équivalence définie par une théorie.

---- 1 octobre 2017 ----

3) Structure quotient

La structure quotient `Q` se présente sous forme d'un quotient, le quotient d'une structure `S` par une relation d'équivalence `"="_T`.

`Q = S"/="_T`

Et il s'agit bien d'une division de l'ensemble `S` par la relation d'équivalence `T`. La relation `T` sur `S` est une relation d'équivalence si et seulement si quelque soit `x` et `y` et `z` apartenant à `S`, nous avons :

`xTx`
`xTy => yTx`
`(xTy "et" yTz) => xTz`

Le résultat de la division `Q=S"/"T` est égale au partitionnement de `S` en classes d'équivalences :

`Q = {E"⊂"S "/"`
       `AA(x,y)"∈"S,`
              `(x"∈"E "et" y"∈"E)=>xTy,`
              `(x"∈"E "et" y"∉"E)=>¬xTy`
`}`

Chaque classe d'équivalence est un élément de la structure quotient `Q`. L'application qui transforme à chaque élément de `S` en la classe d'équivalence qui le contient se note `q` avec la même lettre que la structure mais en minuscule. C'est un morphisme surjectif. On l'appelle le constructeur de `Q` lorsque les éléments de `Q` sont appelés des objets ou encore l'évaluateur de `Q` lorsque les éléments de `Q` sont appelés des résultats.

`q = ((S->Q),("x"|->{y"∈"S "/" xTy}))`

Un opérateur d'arité zéro de S tel que `a` est transformé par q en un opérateur d'arité zéro de Q.

Un opérateur unaire de S tel que `f"(.)"` est

 

`(AAx"∈"S f(x)|->f(s(x))), (AA(x,y)"∈" "S"^2  "g"(x,y)|->"g"(s(x),s(y))))`

 

Chaque opérateur générateur de `S` désignera un opérateur générateur de `Q`.

 

 

 

 

 

4) Théorie complète pour le prédicat d'égalité

On définie une relation d'équivalence `T` sur `S` par une théorie, qui portera le même nom que la relation, et telle que quelque soit `x` et `y` apartenant à `S`, nous ayons :

`xTy`
`<=>`
T|--x"="y`
`¬xTy`
`<=>`
T|--x"≠"y`

Cette définition utilise le symbole de démontrabilité `|--` et elle exige que la théorie `T` soit complète pour le prédicat d'égalité appliqué aux éléments de `S`, c'est à dire que quelque soit `x` et `y` appartenant à `S`, la théorie `T` doit trancher en un temps fini si `x"="y` ou si `x"≠"y`, et cela peut être les deux à la fois si la théorie `T` et incohérente.

La condition de complétude vis à vis de l'égalité est nécessaire pour distinguer chaque élément de la structure quotient.

Dans certain cas, on peut forcer cette condition de complétude pour l'égalité en ajoutant à la théorie `T` l'axiome de séparabilité, noté `frs`, qui considére inégaux tout couple d'éléments dont on ne peut pas prouver qu'ils sont égaux, une propriété qui n'est pas exprimable en logique premier ordre et qui utilise l'opérateur de démontrabilité `"⊬"`.

Axiome de séparabilité : `AA(x,y)"∈"L^2  (T"⊬"x"="y)  =>  x"≠"y`

Mais attention, cet axiome très puissant entrainera dans de nombreux cas l'incohérence de la théorie.

4) Terminologie

On se place dans le cadre d'une structure quotient `Q= S "/"T``S` est une structure et `T` une théorie complète pour le prédicat d'égalité sur `S`. Et on suppose que la structure `S` est engendrée par les opérateurs `a,f"(.)",g"(.,.)` ce qui se note `S = "<"a,f"(.)",g"(.,.)>"`. Mais ses opérateurs ne sont pas forcement libre. Le langage d'opérateurs libres associé à `S` se note `"S" = "<a","f(.)","g(.,.)>"`. Et l'évaluateur ou le constructeur se note `s`. C'est un mophisme surjectif de `"S"->S` qui évalue tout terme appartenant au langage `"S"` en son résultat, un résultat qui appartient à `S`.

On adopte la terminologie suivante : Les éléments de la présentation d'une structure sont appelés opérateurs. Les éléments de `S` sont appelés résultats ou objets. L'évaluateur produit un résultat, le constructeur consruit un objet. Les éléments de `"S"` sont appelés termes, les termes du langages. Et les éléments de `Q` sont appelés éléments.

Un opérateur est un élément de la présentation de la structure `S`. Exemples : `a, f"(.)", g"(.,.)"`. Les élément de la présentation de la structure `Q` s'appellent aussi des opérateurs et on passera de l'un à l'autre par un autre morphisme surjectif.

L'ensemble des opérateurs de `S` engendrent la structure `S` par composition close. L'ensemble des opérateurs associés engendre le langage `"S"` par emboitement clos. L'ensemble des opérateurs de `Q` engendrent la structure `Q` par composition close.

Un opérateur d'arité zéro est un élément de `S`. Un opérateur d'arité `n">"0` est une fonction de `S^n->S`.

Un opérateur d'arité zéro est un représentant de sa classe d'équivalence c'est à dire de l'ensemble des résultats qui lui sont égaux selon la théorie `T` et qui constitue un élément de `Q`. Donc un opérateur d'arité zéro désigne un élément de `Q`, qui est la classe d'équivalence dont il fait partie.

Un opérateur d'arité `n">"0` désigne une fonction de `Q^n->Q`.

L'ensemble des opérateurs désignés engendrent `Q` par composition close.

Un résultat est un élément de `S` obtenus par une composition close d'opérateurs. Le résultat possède une arité nulle. Un résultat est un représentant de sa classe d'équivalence c'est à dire de l'ensemble des éléments de `S` qui lui sont égaux selon la théorie `T` et qui constitue un élément de `Q`. Un terme désigne un élément de `Q`, qui est la classe d'équivalence dont il fait partie.

Un élément est un élément de `Q`. C'est une classe d'équivalence de termes. Il est désigné par n'importe quel de ses membres. Exemple `g(a,f(a))`.

5) Logique propositionnelle

Le langage logique de dimension zéro de la structure `L"/"T`, introduit le prédicat d'égalité `"=(.,.)"`. Ce langage logique est constitué de toutes les combinaisons logiques sans variable ni quantificateur, appelées propositons de dimension zéro, qu'il est possibles de construire avec ce prédicat en l'appliquant sur les éléments de `L` et en utilisant les connecteurs logiques habituels : `{¬,"et","ou", =>, <=>, "w"}`

Un littéral est soit une égalité ou une inégalité entre deux éléments. Exemples : `a"="g(a,a)`, `a"≠"f(a)`.

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

Une proposition est une combinaison logique de littéraux. L'étude des connecteurs logiques nous montre que toute proposition se décompose de façon unique en une conjonction de clauses. On représente souvent une théorie `T` par un ensemble de propositions qui correspond à la conjonction de ces propositions.

La théorie vide, notée `{}`, ou notée, true, correspond à la conjonction vide. Elle est toujours vrai et ne démontre aucune égalité entre éléments distincts appartenant à `L`. Mais elle n'est pas complète pour l'égalité. Si on lui ajoute l'axiome de séparabilité noté `frs`, alors elle démontre l'inégalité entre tous les termes distincts.

`L = L"/"{frs}`

La théorie incohérente, notée `"⊥"` ou notée false, est toujours fausse et donc démontre tout. Elle démontre l'égalité entre tous les termes distincts. La structure résultante est la structure triviale réduite à un seul élément.

`{1} = L"/"`fase

3) Extension élémentaire

Une variable est désignée habituellement par `x,y,z....` et par toute nouvelle lettre minuscule ne figurant pas dans la présentation de la structure. La variable est un nouvel opérateur d'arité zéro. La variable enrichie le langage et donc la structure. On parlera de l'univers de Herbrand étendu, de langage étendu, ou de structure étendue aux nouvelles variables `x,y,z,...`. Le procédé consistant à ajouter ces nouveaux opérateurs dans le langage d'opérateurs et ainsi à agrandire la structure quotient, s'appelle une extension élémentaire.

L'extension élémentaire consiste à ajouter un nouvel opérateur `x` d'arité nulle dans le langage de la structure quotient `S` c'est à dire dans la présentation de la structure `S`, c'est à dire dans la présentation de la structure `L` . On obtient une nouvelle structure que l'on note `S[x]` :

`S = L"/"T`   avec   `L = "<"a,f"(.)",g"(.,.)>"`
`S[x] = "<"a,x,f"(.)",g"(.,.)>"/"T`
`S[x] = L[x] "/"T`

L'extension est dite intérieure si on ajoute à la théorie la condition `x"∈"L`. 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 à 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`.

La structure `S` peut être définie à extension près. Délors son univers de Herbrand ne représente qu'une partie de son ensemble sous-jacent.

Par défaut une structure `L` n'est pas définie à extension près, et son ensemble sous-jacent correspond à son univers de Herbrand.

Une structure `S` à extension près est une structure `S` potentiellement étendue par l'ajout d'une infinité énumérable de nouveaux opérateurs d'arité nulle `S[x_1,x_2,x_3,...]`.

Il y a alors deux niveaux de langage. Un premier niveau comprenant les opérateurs de la présentation de la structure auquel on ajoute le prédicat égal, et un second niveau comprenant en plus une infinité énumérable d'opérateurs d'arité nulle `x_1,x_2,x_3,...`.

Remarquez que du point de vue élémentarien, toute structure est énumérable, même à extension près.

5) Morphisme

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érateur 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 pour déterminer cette association biunivoque, car si les structures possèdent plusieurs opérateurs de même arité, il y a alors plusieurs façon possible de créer cette association biunivoque. Pour déterminer complètement le patronage, il convient à chaque fois, 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"(.)>"`

Dans chaque patronage, 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 `g"(.)`. Parcontre, en terme de langage d'opérateurs, ce sont les deux mêmes langages.

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 à extension près qui sont de même patronage :

`L_1 = "<"a_1, f_1"(.)", g_1"(.,.)>" "/" T_1`
`L_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 `L_1 -> L_2` est un morphisme si et seulement si quelques soient `x` et `y` appartenant à `L_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 `L_1` est abstraitement inclus dans `L_2`, ce qui se note `L_1"↪"L_2` ou plus précisement `L_1"↪"_varphi L_2`

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

 

--- 28 septembre 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)`

 

 

 


   <=>   
   =>    

<=>
<=>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Une proposition de dimension `2` se construit pareillement. Elle quantifie une variable. Elle possède une tête et un corps. La tête quantifie la variable à l'aide d'un opérateur `AA` ou `EE` et le corps est une combinaison de littéraux et d'une proposition de dimension `2-1` dans le langage augmenté de cette variable mais ne possédant pas d'autre variable. Voici un exemple de telle proposition :

`AA xEE y  R(x,y)`

Une proposition de dimension `n` se construit pareillement. Elle quantifie une variable. Elle possède une tête et un corps. La tête quantifie la variable à l'aide d'un opérateur `AA` ou `EE` et le corps est une combinaison de littéraux et d'une proposition de dimension `n-1` dans le langage augmenté de cette variable mais ne possédant pas d'autre variable.

Définie ainsi

--- 21 septembre 2017 ---

 

 

`EE x  x"≠"a`

Cette proposition affirme qu'il existe dans la structure un élément différent de `a`. Veuillez noter que la structure `L = "<"a">/"{EE x  x"≠"a}` est incohérente, tandis que la structure `L = "<"a,b">/"{EE x  x"≠"a}` est identique à la structure `L = "<"a,b">/"{a"≠"b}`.

 


Dominique Mabboux-Stromberg

 

Le langage de la structure est définie par deux listes ; une liste d'opérateurs générateurs et une liste de prédicats générateurs. Chaque opérateur et prédicat y est placé dans un ordre précis, tels qu'ils apparaissent dans la présentation de la structure. Le langage possède un type et une signature :

 

 

 

Les opérateurs engendrent le langage d'éléments par clôture par emboitement. Et les prédicats appliqués à ce langage d'éléments engendre toutes les propositions logiques simples, c'est à dire sans quantificateur ni variable. On le note pareillement à l'aide de crochets `"<>"` eutourant la liste des opérateurs et prédicats générateurs.

`M = "<"a, f"(.)", g"(.,.),A, B"(.)", R"(.,.)">"`

M comprend deux types d'éléments, les éléments et les propositions simples. Voici quelques exemples d'éléments de `M` :

`a`
`f(a)`
`g(a,f(a))`
`A`
`B(a)`
`B(f(a)) => A`
`(R(a,g(a,a)) "ou" B(f(a))) <=> A`

 

 

 

 

La même lettre `L` est utilisé pour désigné le langage d'élément et le langage logique. On laisse le soin au contexte de lever l'ambiguité.

 

 

Une structure est présentée sous forme d'un quotient, le quotient d'un langage par une théorie du premier ordre écrite dans ce langage. On part d'un langage d'opérateurs d'arité fixe et de prédicats d'arité fixe tel que par exemple :

 

Les opérateurs sont présentés en une liste entre crochet `"<>"` en minuscule. Et ils engendrent l'ensemble sous-jacent de la structure par clôture par emboitement, nommé l'univers de Herbrand, du nom de son concepteur, Jacques Herbrand (1908 Paris - 1931 La Bérarde), mathématicien et logicien français.

 

L'ensemble des opérateurs et prédicats constitue la présentation du langage.

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

 

Lorsqu'il est quotienté par une théorie, on dira que il constitue la présentation d'une structure.

 

Le langage comprend un prédicat supplémentaire non mentionné dans la présentation qu'est l'égalité `"=(.,.)"`

 

La théorie de la structure se place au dénominateur entre accolade `{}` sous forme d'un ensemble représentant une conjonction.

Le langage de la structure est définie par deux listes ; une liste d'opérateurs générateurs et une liste de prédicats générateurs. Chaque opérateur et prédicat y est placé dans un ordre précis, tels qu'ils apparaissent dans la présentation de la structure. Le langage possède un type et une signature :

 

La théorie `T` doit satisfaire une condition de détermination. On lui ajoute une propriété qui n'est pas du premier ordre et qui utilise l'opérateur de démontrabilité :

Axiome de détermination : `AA(x,y) T|-/-x=y => x=/=y`

Un prédicat est un élément de la présentation de la structure ou bien l'égalité que l'on rajoute comme prédicat. Exemples : `A,B"(.)", R"(.,.)", "=(.,.)"`. On appel prédicat ce qui est habituellement désigné comme prédicat générateur. Le prédicat d'arité nulle est un attribut booléen `0` ou `1` de la structure. Le prédicat d'arité `n">"0` est une fonction de `L^n -> {0,1}`.

De même, le résultat du prédicat appliqué à ses opérandes est l'emboitement de celui-ci avec ses opérandes, c'est à dire l'expression composée telle quelle, le littéral, et constitue une variable booléenne inconnue. Et toutes les égalités entre éléments sont engendrées par la seul théorie de la structure, ainsi que toutes les équivalences entre littéraux.

Voici un exemple de combinaison logique de dimension zéro ou de théorie de dimension zéro :

`f(a)"≠"a <=> (f(f(a))"="a "et" g(a,a)"≠"a)`

 

Mais ce qu'il faut comprendre de la construction élémentarienne, c'est que ces opérateurs, s'il ne sont pas préalablement définie, sont libres. Le résultat d'un opérateur appliqué à ses opérandes est l'emboitement de celui-ci avec ses opérandes, c'est à dire le terme composé tel quel, et qui constitue un élément inconnu. Cet inconnu, s'il n'est pas rendu égale à un autre élément par la théorie, constitue un élément différent des autres, identifié par l'expression même de sa construction. C'est la complétude de la théorie vis-à-vis de l'égalité qui assure cela.

Un littéral avec variable est une fonction de `L^n -> {0,1}` d'arité `n` égale au nombre de variables que le littéral contient.

Un terme de l'univers de Herbrand est plus générale qu'un élément, car il peut contenir des variables. Exemple `g(a,f(x))`. Un terme sans variable désigne un élément inconnue de la structure. Un terme avec variables est une fonction de `L^n->L``n` est égale au nombre de variables qu'il contient.

Une combinaison de littéraux se fait à l'aide d'opérations logiques. Une combinaison de littéraux sans variable constitue un paramètre booléen inconnue de la structure. Une combinaison de littéraux avec variable est une fonction de `L^n -> {0,1}` d'arité `n` égale au nombre de variables qu'elle contient. Exemple : `(f(a)"="a "ou" x"≠"y) => f(x)"="y`.

Une application `varphi` de `L_1 -> L_2` est un morphisme si et seulement si quelques soient `x` et `y` appartenant à `L_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))`
`A_1<=>A_2`
`B_1(x)<=>B_2(varphi(x))`
`R_1(x,y)<=>R_2(varphi(x),varphi(y))`

On dira que le langage est implémenté par l'interface qui comprend la définition de ces opérateurs.

 

On propose une déscription de la logique respecteuse de l'indépendance du point de vue élémentarien (voir structure).