Suivant

I) Structures finies, langage et théorie

 

1) Introduction

La théorie des ensembles à pour principal objet d'explorer l'infini, et donc peut parraître à bien des égards comme une question byzantine. En effet, certaines opinions estiment qu'il n'existe pas d'infini même conceptuellement parlant puisque physiquement impossible. D'autres estiment qu'il n'existe qu'une sorte d'infini, dit potentiel, et dont un exemple est l'ensemble `NN`, d'autres encore estiment qu'il existe une multitude d'infinis non équipotants...

Cette controverse découle du fait que tout ce qui peut être dit est nécessairement énumérable, c'est à dire ne constitue au plus qu'un ensemble énumérable d'énoncés.

Le théorème de Löwenheim-Skolem affirme que, si une théorie du premier ordre écrite dans un langage mathématique dénombrable est réalisable dans un modèle infini, alors elle est réalisable dans un modèle dénombrable. C'est pourquoi, en logique du premier ordre, on choisira la solution la plus simple qui consiste à récuser les infinis autres que ceux équipotant à `NN`.

Le théorème de Godel démontre que toute théorie `T` cohérente, suffisamment complexe pour contenir l'arithmétique, est incomplète. C'est à dire qu'il existe au moins une proposition `P` écrite dans le langage de `T` qui ne pourra pas être tranchée par `T`, autrement dit, telle que `T"⊬"P"` et `T"⊬¬"P`. Et ce théorème est valable non seulement pour les théories du premier ordre, mais aussi pour les théories du second ordre.

À partir d'une théorie, on peut construire un programme qui énumère toutes ses déductions. Car un langage d'opérateurs de présentation énumérable est encore énumérable. Et en passant en revue tout ce qui peut être dit, en ne retenant que ce qui constitue syntaxiquement une démonstration, et pour chaque telle démonstration en n'en retenant que la conclusion, on énumère ainsi toutes les déductions possibles.

Nous allons décritre le langage logique du `n`-ième ordre, dont la définition ne pose pas de difficulté dans les cas finis, car elle fait partie de l'analyse combinatoire. Elle constitue un des piliers de la théorie des ensembles sans pourtant vraiment en faire partie puisqu'elle ne s'interesse pas à l'infini. Les théories mathématiques dans le cas fini, sont toujours complétables ne fussent qu'en énumérant tous les cas, et le langage logique du n-ième ordre se définit combinatoirement. Puis nous décrirons la sémantique de façons formelle. Car dans le cas fini, la sémantique d'une théorie est parfaitement déterminée, c'est l'ensemble des mondes complets finis satisfaisant la théorie.

Nous ne souhaitons pas utiliser le terme de modèle tel qu'il est utilisé dans la théorie des modèles, car sa signification en français est ambigüe, désignant tantôt un patron, tantôt un shéma, tantôt un prototype, tantôt un type d'article, tantôt un article achevé qu'on exhibe à titre d'exemple. On utilisera à la place le terme de monde, mais pris, non pas comme un élément extérieur à la théorie, mais plutôt comme une instantiation de la théorie, de tous ses littéraux. Ainsi on propose un paradigme quelque peu différent dans lequel la sémantique se définie formellement, et on l'appellera la théorie des mondes.

--------------

Qu'est-ce qui est plus général ; une application de `A` vers `B`, ou bien une application de `E` vers `E` ? S'il fallait répondre vite, on répondrait la première, et on ferait une erreur. Car chacune contient potentiellement l'autre. En effet les applications de `A` vers `B` couvrent toutes les applications de `E` vers `E` lorsque `A"="B"="E`, et réciproquement lorsque `E"="A"∪"B`, les applications de `E` vers `E` restreintes à `A` couvrent toutes les applications de `A` vers `B`. Et donc la plus générale des deux est la plus simple des deux, c'est à dire l'application de `E` vers `E`. Rappelez-vous cet adage, car il s'appliquera à d'autres situations : « Etant donné deux formes, si chacune est incluse dans l'autre alors la plus générale des deux est la plus simple des deux. »

2) Groupe

Un groupe `G` est un ensemble muni d'une loi de composition interne partout définie notée par simple juxtaposition, d'un élément neutre noté `1`, d'un opérateur d'inversion partout défini noté par l'exposant `"-"1`, satisfaisant les règles suivantes :

`AA (x,y,z) "∈" G^3`

`(xy)z= x(yz)`
`x1=1x=x`
`x x^("-"1)=x^("-"1)x=1`

C'est ainsi que l'on décrit la théorie du groupe en notation multiplicative.

Mais pour rendre cette définition incontestable et afin qu'elle soit perçue de la même façon par tous, il convient de formaliser davantage, en procédant à une construction rigoureuse du langage logique utilisé et en y décrivant sa sémantique sous forme d'ensemble de mondes possibles.

Afin de pouvoir désigner facilement la loi de composition qui est un opérateur binaire, et l'opérateur d'inversion qui est un opérateur unaire, on leur donne un nom. Le symbole `"∗"` désignera la loi de composition, et le symbole `frI` désignera l'opérateur d'inversion, faisant que `x"∗"y"="xy` et `frI(x)"="x^("-"1)`, de même pour l'élément neutre, on lui a donné un nom, `1`.

3) Structure et langage.

Une structure `G` possède un ensemble sous-jacent de même nom `G` et des opérateurs et prédicats définis dans l'ensemble sous-jacent `G`. Cela signifie que les opérateurs zéro-aires ou éléments appartiennent à `G`, que les opérateurs unaires appartiennent à `G"→"G`, que les prédicats unaires appartiennent à `G"→"{0,1}`, que les opérateurs binaires appatiennent à `(G"×"G)"→"G`, etc...

Ces opérateurs et prédicats sont regroupés dans la présentation de la structure et, lorsqu'il ne sont pas instantiés, ils forment le langage de la structure. Puis la structure possède une théorie écrite dans ce langage.

L'interprétation du langage de la structure est posé comme étant interne à la structure, c'est à dire que les quantifications universelles et existentielles sont interprétées comme ayant une portée limitée dans l'ensemble sous-jacent `G`. Ce qui se définit pour les exemples suivants de façon exacte comme suit :

`AAx"∈"G, P(x)`
  `<=>`   `underset(x in G)("et")P(x)`      
`AAf"∈"(E"→"E), P(f(a))`
  `<=>`   `underset(f in E"→"E)("et")P(f(a))`
`AA A"∈"(E"→"{0,1}), A(a)`
  `<=>`   `underset(A in E"→"{0,1})("et")A(a)`
`AAg"∈"(E"×"E"→"E), P(g(a,b))`
  `<=>`   `underset(g in E"×"E"→"{0,1})("et")P(g(a,b))`
 
etc..
 

`EEx"∈"G, P(x)`
  `<=>`   `underset(x in G)("ou")P(x)`      
`EEf"∈"(E"→"E), P(f(a))`
  `<=>`   `underset(f in E"→"E)("ou")P(f(a))`
`EE A"∈"(E"→"{0,1}), A(a)`
  `<=>`   `underset(A in E"→"{0,1})("ou")A(a)`
`EE g"∈"(E"×"E"→"E), P(g(a,b))`
  `<=>`   `underset(g in E"×"E"→"{0,1})("ou")P(g(a,b))`
 
etc..
 

Dans ces exemples, `a,b` sont des éléments, et `P` est une fonction propositionnelle.

On se place donc dans la structure `G`. Délors, par défaut une application ou un opérateur est dans `G` c'est à dire défini partout dans `G` et d'image dans `G`, par défaut un ensemble est inclus dans `G`, par défaut un élément appartient à `G`, par défaut un couple appartient à `G^2`, et par défaut une relation qui est un ensemble de couples est incluse dans `G^2`. Ces prédispositions par défauts sont importantes. Elle donne au contexte un rôle majeur permettant de ne pas noyer l'important dans les détails, incarne une intuition, façonne le concept de structure, et permet de définir un langage logique restreint à l'ensemble sous-jacent. Dans ce contexte, nous décrivons maintenant ce qu'est une quantification, ce qu'est un ensemble, une relation et une application.

Dans la structure `G` :

L'expression `AAx` signifiera `AAx "∈" G`,
l'expression `EE x` signifiera `EE x "∈" G`,
l'expression `AA A"(.)"` signifiera `AA A "∈" (G"→"{0,1})`,
l'expression `EE A"(.)"` signifiera `EE A "∈" (G"→"{0,1})`,
l'expresssion `AA h"(.)"` signifiera `AAh "∈" (G"→"G)`,
l'expresssion `EE h"(.)"` signifiera `EEh "∈" (G"→"G)`,
l'expression `AA R"(.,.)"` signifiera `AA R "∈" (G"×"G"→"{0,1})`,
l'expression `EE R"(.,.)"` signifiera `EE R "∈" (G"×"G"→"{0,1})`,
etc..

Ainsi on définit un langage logique de la structure restreint à son ensemble sous-jacent, utilisant les opérateurs et prédicats de la présentation de la structure définis dans l'ensemble sous-jacent, et utilisant de nouveaux opérateurs et prédicats définis dans l'ensemble sous-jacent et devant alors être quantifiés universellement ou existentiellement de portée définie dans l'ensemble sous-jacent.

Toute proposition écrite dans ce langage aura une signification spécifique dans chaque structure possédant ce même langage.

Et d'une manière plus générale sous le patronage d'un traducteur qui est une relation associant les opérateurs et prédicats d'un langage vers un ceux de même type d'un autre langage, toute proposition écrite dans le premier langage aura une signification spécifique dans le second langage.

Le langage d'une structure se note en présentant une liste d'opérateurs et de prédicats non instanciés c'est à dire libre de toute contrainte, c'est à dire ici `("∗",1,frI)`. Conventionnellement les opérateurs sont notés en minuscule et les prédicats en majuscule, et on précise parfois leur type de deux façons courantes, soit par un suffixe indiquant l'arité ; absence de suffixe pour l'arité nulle, suffixe `"(.)"` pour unaires, suffixe `"(.,.)"` pour binaires, suffixe `"(.,.,.)"` pour ternaire, etc.. , ou soit par un exposant indiquant leur type explicite. Puis on ajoute parfois comme premier symbole, `"E"`, qui désigne l'ensemble sous-jacent qui peut être lui-aussi non instancié. C'est ce sur quoi porte les quantifications `AA` et `EE` du langage.

Ainsi le langage des structures de groupe est :

`("E", "∗(.,.)",1,frI"(.)")`

ou encore :

`("E", "∗"^"E×E→E",1^E,frI^"E→E")`

Puis il convient de distinguer la structure `G` du patron. La structure `G` peut-être un monde qui concrétise le patron, c'est une instanciation du patron, Tandis que le patron, qui est le modèle commun, n'est pas instancié. De tel sorte qu'en dehors de tout autre condition, il est qualifié de libre.

Le patron de structure constitue sa théorie présentée sous forme de fonction propositionnelle. Et on utilisera deux formes, l'une classique que nous présentons ici, l'autre récursive que nous présenterons plus loin. Par exemple le patron de structure de groupe, noté `"Groupe"`, se définit comme suit :

`"Groupe"(G,"∗",1,frI) <=> ( ( AA(x,y,z)"∈"G^3"," (x"∗"y)"∗"z"="x"∗"(y"∗"z) ),( AAx"∈"G"," x"∗"1"="x ),( AAx"∈"G"," 1"∗"x"="x ),( AAx"∈"G"," x"∗"frI(x)"="1 ),( AAx"∈"G"," frI(x)"∗"x"="1 ) )`

Le patron `"Groupe"` a 4 arguments qui sont listés dans cet ordre :

  1. L'ensemble sous-jacent supposé fini
  2. l'opérateur de produit défini sur cet ensemble,
  3. l'élément neutre appartenant à cet ensemble,
  4. et l'opérateur d'inversion défini sur cet ensemble.

Cette définition du groupe sous forme de fonction propositionnelle, définit un langage logique, le langage de la structure, sans donner de nom à l'ensemble sous-jacent et aux opérateurs et prédicats puisque identifiés par leur place occupée dans la liste des arguments. Vous comprendrez que ce n'est pas trés pratique, aussi nous demanderons au contexte de les nommer, et cela se fait en mentionnant le langage de la structure de groupe qui servira de modèle `("E","∗",1,frI)` commun à toutes les groupes. Voyez ici que l'on utilise le terme de modèle pour autre chose que celui de monde. Le symbole `"E"` désigne l'ensemble sous-jacent non instancié, c'est ce sur quoi porte les quantificateurs `AA` et `EE` du langage. Une proposition écrite dans un langage signifit qu'il appartient à ce langage, c'est pourquoi on pourra préciser le langage en le mettant en exposant :

`"Groupe"("E","∗",1,frI) <=> ( ( AAxAAyAAz"," (x"∗"y)"∗"z"="x"∗"(y"∗"z) ),( AAx"," x"∗"1"="x ),( AAx"," 1"∗"x"="x ),( AAx"," x"∗"frI(x)"="1 ),( AAx"," frI(x)"∗"x"="1 ) )^("(""E","∗",1,frI")")`

Si nous définissons plusieurs structures de même langage, c'est à dire utilisant les mêmes symboles d'opérateur et de prédicat, telles que les groupes `(G,"∗",1,frI)` et `(H,"∗",1,frI)` où seul change le nom du groupe qui est identique au nom de son ensemble sous-jacent, alors on pourra spécifier les opérateurs à l'aide d'un indice pour savoir à quelle groupe ils font référence : `"∗"_G`, `1_G`, `frI_G`, `"∗"_H`, `1_H`, `frI_H`.

Dernière remarque, la variable `G` peut-être vu comme un ensemble, ou plus que cela, comme une structure que le contexte lui attribut, ici, une structure de groupe. Le groupe `G` détermine son ensemble sous-jacent, sa loi de composition interne `"∗"_G` son élément neutre `1_G` sa loi d'inversion `frI_G`, mais l'ensemble `G` ne détermine aucune loi ni élément, il ne détermine que l'ensemble sous-jacent. L'égalité `G"="H` peut désigner une égalité d'ensemble ou bien une égalité de groupe, et c'est au contexte de le préciser. Il se peut que `G"="H` en tant qu'ensemble, et que `G"≠"H` en tant que groupe.

4) Ensemble

Au sein de la structure `G`, il n'y a pas de différence entre un ensemble et un prédicat unaire. On les définit mécaniquement comme des processus qui appliqués à un élément, produisent `0` ou `1`. Considérons un prédicat `A"(.)"`, c'est aussi un ensemble et qui porte le même nom. De cette façon nous définissons un nouvel opérateur dit d'appartenance `"∈"`, et l'expression logique `A(x)` est équivalente à `x"∈"A`, et l'expression logique `"¬"A(x)` est équivalente à `x"∉"A`. Mais on n'ajoute pas cet opérateur au langage de la structure, on l'utilise uniquement par commodité comme seconde écriture (dans les cas où il est défini), car on ne s'intéresse pas à la théorie des ensembles pour l'instant.

L'ensemble des prédicats unaires se note donc `ccP(E)` lorsque `E` est fini, et son cardinal est :

`|ccP(G)| = |G"→"{0,1}| = 2^|G|`

5) Relation

De même, il n'y a pas de différence entre un ensemble de couples et un prédicat binaire. On les définit mécaniquement comme des processus qui appliqués à un couple, produisent `0` ou `1`. Considérons un prédicat `R"(.,.)"`, c'est aussi un ensemble de couples et qui porte le même nom, et nous avons `(x,y)"∈"R<=>R(x,y)`. L'ensemble des prédicats binaires se note donc `ccP(G^2)` lorsque `G` est fini, et son cardinal est :

`|ccP(G^2)| = |G"×"G"→"{0,1}| = 2^|G^2|`

Mais il existe une autre façon de percevoir ces prédicats binaires. On peut les voir comme des ensembles d'arêtes orientés, c'est à dire des ensembles de couples `(a,b)` que nous préférons parfois noter de façon intuitive par `a"↦"b` indiquant un sens de passage, une arête orientée. La relation va indiquer un flux, chaque arête indiquant un passage possible. La relation possède un domaine de définition qui est l'ensemble des points où partent des arêtes. Le domaine de définition de la relation `R` est :

`"Dom"(R) = {x "/"EEy,(x"↦"y) "∈" R}`

`"Dom"(R) = {x "/"EEy,R(x,y)}`

L'image d'un ensemble `A` transformé par la relation `R`, est l'ensemble atteignable à partir de `A` en un et un seul pas, en prenant une et seule arête de `R` et en l'empruntant dans son sens autorisé. On le note `R(A)`. Cela dénote l'ensemble des points nouvellement irrigués grâce au passage d'un fluide qui occupe tous les points de `A` et qui peut franchir une arête de `R`, mais juste une seule fois, et dans le sens autorisé :

`R(A) = {y "/"EEx, x"∈"A "et" (x"↦"y)"∈"R}`

`R(A) = {y "/"EEx, A(x) "et" R(x,y)}`

6) Composition de relations

Les relations sont emboitables grace à la composition de relation `"∘"` définie naturellement comme suit :

`R"∘"S = { x"↦"z "/"EEy,(x"↦"y) "∈" R "et" (y"↦"z) "∈" S}`

`R"∘"S = { (x,z) "/"EEy,R(x,y) "et" S(y,z)}`

Pour alléger l'écriture, lorsque l'ensemble est énuméré entre accolades tel que par exemple `{x,y,z}`, l'image par `R` de l'ensemble `{x,y,z}` est simplement noté `R{x,y,z,...}` au lieu de `R({x,y,z,...})` et est appelé aussi simplement l'image de `x,y,z` par `R`. Ainsi nous avons :

`R{x} = {y "/"(x"↦"y)"∈"R}`
`R{x,y} = {z "/"(x"↦"z)"∈"R "ou" (y"↦"z)"∈"R}`

Pour ne pas confondre une opération d'application avec une opération de produit, on note parfois sur quoi s'applique l'opération d'application en une couleur légèrement plus verte tel que que par exemple `R color(#079)("("A")")`, `Rcolor(#079)({x,y})`.

Puis nous définirons, le moment venu quand l'intuition mettra en évidence leur utilité, de nouvelles opérations sur ces relations.

7) Application

De même, au sein de la structure `G`, il n'y a pas de différence entre une application et un opérateur. On les définit mécaniquement comme un processus qui appliqué à un élément, produit un élément. On désigne l'ensemble des applications par l'expression `G"→"G`. Lorsque `G` est fini, son cardinal est :

`|G"→"G| =|G|^|G|`

Mais il existe une autre façon de percevoir ces opérateurs. On peut les voir également comme des relations applicatives partout définies, c'est à dire des ensembles de couples `(a,b)` que nous notons parfois `a"↦"b`, et qui satisfont les deux propriétés suivantes, où `R` désigne la relation en question :

`R` est une relation applicative : `AA(a,b,c) "∈" R^3, (a,b) "∈" R  "et" (a,c) "∈" R => b"="c`

`R` est une relation partout définie : `AAa"∈"G, EEb"∈"G, (a,b) "∈" R`

Et lorsque une relation `R` satisfait ces deux propriétés alors elle cumule le rôle d'application, et on lui donne un rôle syntaxique supplémentaire, celui d'une application, on lui autorise une syntaxe nouvelle, celle de désigné l'élément image de `x` par l'expression `R(x)` avec la définition suivante :

`R(x)"="y <=> y"∈"R{x}`.

Par défaut une applictaion `f` est définie sur `G`, Autrement dit, `"Dom"(f)"="G "et" f(G)"⊆"G`. Les éléments sont parfois appelés des points, faisant alors référence à une géométrie en construction. L'image d'un point `x` transformé par l'application `f`, est le point image atteint par la seul arête de `f` qui part de `x`. On le note `f(x)`.

`f(x)"="y <=> (x"↦"y)"∈"f`

L'ensemble `f` désigne le même objet que l'application `f` mais sous une forme syntaxique différente qu'est la forme prédicative binaire, ou sous forme d'ensemble de couples.

8) Composition d'applications

Les applications sont emboitables grace à la composition `"∘"` définie pour les relations au chapitre précédent, en les emboitant en tant que relations :

`f"∘"g = { x"↦"z "/"EEy,(x"↦"y) "∈" f  "et" (y"↦"z) "∈" g}`

Cela signifie que la composition `"∘"` de deux relations préserve les propriétés « Relation applicative » et « Relation partout défini » afin que la composition de deux applications produise bien une relation qui soit encore une application. Par ailleurs une application `f` étant une relation, l'expression `f(A)` `A` est un ensemble, est parfaitement définie et s'appelle l'ensemble image de `A` par la relation `f`, ou par l'application `f`.

9) Application et transport de l'égalité et des ensembles

Le fait que `f` soit une application entraine la propriété évidente suivante :

`AAxAAy, x"="y => f(x)"="f(y)`

On dit que les applications respectent l'égalité, ou encore conservent l'égalité, ou encore transportent l'égalité. Cette dernière expression mettant l'accent sur une structure image `f(G)` dite parallèle dans laquelle les égalités connues dans la struture `G` sont transportées par l'application `f` en des égalités dans la structure image `f(G)`.

Si nous ajoutons au langage logique un prédicat unaire `A"(.)"`, alors ce prédicat désigne un sous-ensemble de `G`, que nous nommons avec la même lettre, et donc  : `A(x) <=> x"∈"A`. Le fait que `f` soit une application entraine la propriété suivante :

`AAx, A(x) => f(A)(f(x))`

`AAx, x"∈"A => f(x)"∈"f(A)`

`f(A)` est l'image de `A` par `f`. On dit que les applications transportent les ensembles, un transport d'une structure sur une autre, que l'on resume comme ceci :

`(G,A)underset(f)"→" (f(G),f(A))`

10) Application parallèle et transport des relations

Si nous ajoutons au langage logique un prédicat binaire `R"(.,.)"`, alors ce prédicat désigne un sous-ensemble de `G^2` et constitue une relation que nous nommons avec la même lettre, et donc : `R(x,y) <=> (x"↦"y)"∈"R`. Le fait que `f` soit une application entraine la propriété suivante :

`AAxAAy, R(x,y) => f(R)(f(x),f(y))`

`AAxAAy, (x"↦"y)"∈"R => (f(x)"↦"f(y))"∈"f(R)`

`f(R)` désigne l'application parallèle de `f` sur `R`. On introduit ici une nouvelle opération qui est l'application parallèle. Une application unaire `f` s'applique de façon parallèle à un couple comme suit : `f"("(x,y)")" "=" (f(x),f(y))`, ou si vous préférez `f(x"↦"y)"=" (f(x)"↦"f(y))`. On généralise cette définition aux relations. Une relation `R` s'applique de façon parallèle à un couple comme suit :

`R{x"↦"y}"=" { a"↦"b "/"a"∈"R{x} "et" b"∈"R{y} }`

Cela définit un bigraphe complet, que l'on note aussi par `R{x}"↦"R{y}`, envoyant tous les éléments de `R{x}` sur tous les éléments de `R{y}`.

Cette définition se généralise par union en appliquant parallèlement la relation à un ensemble de couples `S` :

`R(S) "=" { a"↦"b "/"EE(x"↦"y)"∈"S, a"∈"R{x} "et" b "∈"R{y} }`

`R(S) = uuu_((x"↦"y)in S) R{x"↦"y}`

Cela définit l'union des bigraphes complets `A"↦"B``A` et `B` sont les images par `R` de `x` et de `y` pour chaque arête `x"↦"y` de `S`.

On dit que les applications transportent les relations, un transport d'une structure sur une autre, que l'on resume comme ceci :

`(G,R)underset(f)"→" (f(G),f(R))`

11) Application parallèle et transport des applications

Si nous ajoutons au langage logique un opérateur unaire `h"(.)"`, alors cet opérateur constitue une application dans `G`, et aussi un ensemble inclus dans `G^2` constituant une relation applicative partout définie que nous nommons avec la même lettre, et donc  : `h(x)"="y<=> (x"↦"y)"∈"h`. Le fait que `f` soit une application entraine la propriété suivante :

`AAxAAy, h(x)"="y => f(h)(f(x))"="f(y)`

`AAxAAy, (x"↦"y) "∈" h => (f(x)"↦"f(y)) "∈" f(h)`

`f(h)` désigne l'application parallèle de `f` sur l'ensemble `h`, et que nous avons déjà définie dans le chapitre précédent pour les relations :

`f(h)"="{f(x)"↦"f(y) "/"(x"↦"y)"∈"h}`

L'ensemble de couples `h` est parfois appelé la forme prédicative binaire de l'opérateur unaire `h"(.)"`.

Comme vous l'aurez remarqué, la définition de l'application parallèle restreinte aux applications apparaît beaucoup plus simple, mais le résultat reste une relation qui n'est pas forcement une application. Parcontre elle l'est dans la structure image `f(G)`. On dit que les applications transportent les applications, un transport d'une structure sur une autre, que l'on resume comme ceci :

`(G,h)underset(f)"→" (f(G),f(h))`

12) Langage d'égalité

Faisons d'abord un constat sur le calcul booléen. Si nous avons `X"⇒"X'` et `Y"⇒"Y'` alors nous avons :

`(X "et" Y) => (X' "et" Y')`

`(X "ou" Y) => (X' "ou" Y')`

Par contre nous ne pouvons pas déduire `X'"⇒"Y'` ni que `"¬"X => "¬"X'`.

Et par récurrence, on généralise ce constat. On considére `n` inconnus booléens `X,Y,Z,...` tels que `X"⇒"X'` et `Y"⇒"Y'` et `Z"⇒"Z'` et etc.. Alors quelque soit la fonction booléenne propositionnelle `B` d'arité `n`, écrite dans le langage d'opérateurs booléens `"<et","ou",1,0">"`, nous avons toujours `B(X,Y,Z,...) => B(X',Y',Z',...)`.

À partir de cette remarque, on définit le langage dit langage d'égalité en n'utilisant comme connecteur booléens seulement la conjonction et la disjonction, et donc en utilisant aussi les quantificateurs `AA` et `EE`, et en n'utilisant que les prédicats affirmatifs dont l'égalité. Et on appelle proposition d'égalité, une proposition du langage d'égalité.

Toutes les égalités étant transportés par application, et de même tout les prédicats étant transportés par application parallèle, on en déduit que toutes les propositions qui combinent ces égalités et ces prédicats avec les seuls connecteurs booléens `"et"`, `"ou"`, et les quantificateurs `AA` et `EE`, sont également transportés par application. Autrement dit,  en prenant comme exemple le modèle `("E", bbh"(.)", bbR"(.,.)")` qui constitue un langage de structure, nous avons :

   Si `f` est une application dans `G`, alors toute proposition d'égalité qui se réalise dans la structure `(G,h,R)`, se réalise aussi dans la structure `(f(G), f(h), f(R))`.

Dans cet exemple on utilise le langage de structure `("E", bbh, bbR)` qui constitue un modèle. Chaque proposition écrite dans ce langage a une signification spécifique dans chaque structure possédant ce langage.

Puis on utilise un patron de structure qui complète le modèle de structure d'une théorie écrite dans le langage de la structure. Par exemple considérons le patron `"Bidule"` de modèle `("E", bbh, bbR)` et de théorie :

`AAx, x"="bbh(x) "ou" bbR(x,x)`

Le patron `"Bidule"` désigne sa théorie sous forme d'une fonction propositionnelle qui lorsqu'elle n'est pas instantiée désigne le Bidule libre:

`"Bidule"("E",bbh,bbR)   <=>   ( AAx, x"="bbh(x) "ou" bbR(x,x) )^( "(" "E", bbh, bbR ")" )`

`"Bidule"(G,h,R)   <=>   AAx"∈"G, x"="h(x) "ou" R(x,x)`

L'expression `"Bidule"(G,h,R)` signifie que l'ensemble `G` munie le l'opérateur `h` et du prédicat `R` forme une structure c'est à dire que la restriction `h"|"_G` est une application dans `G` et que la restriction `R"|"_G` est un prédicat binaire dans `G` et que la théorie en question est posée comme vrai.

Le bidule `(G,h,R)` est identique au bidule `(G,bbh,bbR)` avec `bbh_G"="h` et `bbR_G"="R`. Cette dernière expression ayant l'avantage de répéter le langage de la structure.

Étant donné une application `f` définie dans `G`. On peut appliquer `f` aux seuls éléments de la structure `G`, au quel cas on parlera de l'image de `G` par `f` notée `(f(G),h,R)`. Et on peut appliquer `f` aux éléments, aux opérateurs et aux prédicats de la structure `G` au quel cas on parlera de l'image parallèle de `G` par `f` notée `(f(G),f(h),f(R))` ou simplement `f_"∥"(G)`.

On peut aussi considérer un bidule `K` que l'on déclare comme suit : `"Bidule"(K,f(h),f(R))` et pour le quel l'ensemble sous-jacent `K=f(G)`, alors `K` devient l'image parallèle de `G` par `f`.

Soit `T` la théorie de Bidule :

`T = ( AAx,x"="bbh(x) "ou" bbR(x,x) )`

`T` est une théorie du premier ordre, car les opérateurs et prédicats ainsi que les quantificateurs `AA` et `EE` ne s'appliquent qu'à des éléments et il n'y a qu'un seul type d'élément.

`T` est une théorie d'égalité du premier ordre car de plus elle n'utilise que les connecteurs `"et"`, `"ou"`, et les quantificateurs `AA` et `EE`, et elle n'utilise que des prédicats affirmatifs dont l'égalité fait partie.

`T` est une théorie d'égalité universelle du premier ordre car de plus elle n'utilise pas de quantificateur `EE`.

La théorie`T` signifie littéralement que tout élément est soit invariant par `bbh` ou soit en `bbR`-relation avec lui-même. Comme `T` est la théorie du patron `"Bidule"`, on utilise parfois le nom de patron pour désigner la théorie :

`T"=Bidule"`

Soit une structure libre `(G,bbh,bbR)`. Cette structure possséde le langage de `"Bidule"` mais pas sa théorie. Après cette déclaration, les opérateurs et prédicats `bbh_G, bbR_G` sont posés définis dans `G`.

Lorsque la proposition `T` est vrai dans la structure `G`, nous dirons que `T` se réalise dans `G` ou que `G` satisfait `T`, et nous noterons :

`G⊨T`

Et comme `T` est la théorie de Bidule, nous avons :

`G⊨"Bidule" <=> "Bidule"(G,bbh,bbR)`

-----------------------------------------------------------------------------------

Condidérons le bidule `(G,h,R)`, donc `bbh_G"="h`, et `bbR_G"="R`.

Considérons une application `f` dans `G`.

Considérons la structure `(K,bbh,bbR)` obtenue par image parallèle de `G` de `f`, c'est à dire telle que `K"="f(G)` et `bbh_K"="f(h)` et `bbR_K"="f(R)`.

Nous déduisons :

`"Bidule"(G,h,R)`
`=>       G⊨T`
`=>       G⊨( AAx, x"="bbh(x) "ou" bbR(x,x) )`
`=>       G⊨( AAx_G, x"="bbh_G(x) "ou" bbR_G(x,x) )`
`=>       AAx"∈"G ,x"="h(x) "ou" R(x,x)`
`=>       AAx"∈"G ,f(x)"="f(h)(f(x)) "ou" f(R)(f(x),f(x))`
`=>      AAz"∈"f(G), z"="f(h)(z) "ou" f(R)(z,z)`
`=>      AAz"∈"K, z"="bbh_K(z) "ou" bbR_K(z,z)`
`=>       K⊨( AAz_K, z"="bbh_K(z) "ou" bbR_K(z,z) )`
`=>       K⊨( AAz, z"="bbh(z) "ou" bbR(z,z) )`
`=>       K⊨( AAx, x "="bbh(x) "ou" bbR(x,x) )`
`=>       K⊨T`
`=>       "Bidule"(f(G),f(h),f(R))`

Ainsi la propriété `T`, qui est une propriété d'égalité du premier ordre, est transportées par l'application `f`, un transport d'une structure sur une autre :

`(G"⊨"T) => (K"⊨"T)`

`"Bidule"(G,h,R) => "Bidule"(f(G),f(h),f(R))`

---- 7 décembre 2019 ----

 

 

 

 

Afin de pouvoir instancier les opérateurs et prédicats de la structure, on sépare le langage proprement dit, de la présentation de la structure. Ainsi une structure `(G, h, R)` aura comme langage `"<"bbh">"{bbR}``h` sera une instantiation de `bbh`, et `R` sera une instantiation de `bbR`. Dans le langage, l'opérateur `bbh` désigne le premier opérateur unaire rencontré dans la présentation. L'opérateur `bbR` désigne le premier prédicat binaire rencontré dans la présentation. La proposition `P` se réécrit alors comme suit :

`P = ( AAx,x"="bbh(x) "ou" bbR(x,x) )`

En explicitant les structures, on obtient une vérité de La Palice :

`( (G, h, R)"⊨"P ) => ( (f(G), f(h), f(R))"⊨"P )`

Ainsi, si la structure `G` satisfait une théorie d'égalité, alors la structure `f(G)` ainsi définie satisfera la même théorie d'égalité.

L'application constitue un traducteur transportant les propriétés d'égalités vrais sur `G` en des propriétés d'égalité vrais sur `f(G)`. Et cela s'applique aussi pour les propriétés d'égalité du second ordre.

Considérons par exemple la structure `(G,h"(.,.)")` de langage `"<"bbh"(.,.)>"`. Remarquez alors que `h` est une instantiation de `bbh`. Considérons la proposition suivante :

`P = ( EEg"(.)"AAxAAy, g(bbh(x,y)) "=" bbh(y,x) )`

La proposition `P` signifie littéralement qu'il existe une application qui appliquée à `bbh(x,y)` donne comme résultat `bbh(y,x)`. La propriété `P`, qui est une propriété d'égalité du second ordre, est transportées par l'application `f`, ce qui se note :

`(G"⊨"P) => (f(G)"⊨"P)`

En effet, nous pouvons constater :

`(G"⊨"P) <=> EEg^(G->G),AAx^G,AAy^G, g(bbh(x,y)) "=" bbh(y,x)`

`(f(G)"⊨"P) <=> EEg^(f(G)->f(G)),AAx^(f(G)),AAy^(f(G)), g(bbh_f(G)(x,y)) "=" bbk_f(G)(y,x)`

On note le type des opérateurs en exposant, ainsi par exemples, `x^G` désigne un élement de la structure `G`, l'expression `h^(G"→"G)` désigne un opérateur unaire de la structure `G`, et l'expression `R^(G×G"→"{0,1})` désigne un prédicat binaire de la structure `G`.

l'expression `bbh_(f(G))` désigne l'opérateur `bbh` de la structure `f(G)` qui est égal à `f(bbh_G)` et donc à `f(h)`.

Plaçons nous dans le groupe `(G, "∗")` et considérons une application `f`. La théorie du groupe est une proposition d'égalité, donc la structure image `(f(G), f("∗"))` est également un groupe. Et cela est une évidence parceque `f` est une application.

En démontrant cette évidence, on décrit notre langage logique.

 

---- 3 novembre 2014 ----

 

 

 

 

 

 

 

3) Langage logique du premier ordre

Un langage logique du premier ordre se définit en présentant une liste d'opérateurs entre braquettes `"<"...">"` suivie d'un ensemble de prédicats, qui sont des opérateurs et prédicats déclarés libres par le langage. Conventionnellement les opérateurs sont notés en minuscule et les prédicats en majuscule et on ajoute parfois pour les types simples, un suffixe indiquant l'arité ; absence de suffixe pour l'arité nulle, suffixe `"(.)"` pour unaires, suffixe `"(.,.)"` pour binaires, suffixe `"(.,.,.)"` pour ternaire, etc..

Par exemple considérons le langage suivant :

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

Il comprend un élément `a`, un opérateur unaire `f`, un opérateur binaire `g`, un prédicat unaire `A` et le prédicat d'égalité `"="` qui joue un rôle particulier exposé plus loin.

Les braquettes forment un opérateur appelé opérateur de clôture. Appliqué à une liste d'opérateurs ou d'ensembles d'opérateurs, il produit l'ensemble de tous les compositions closes possibles parmis les opérateurs évoqués et répétés autant de fois que l'on veut. Cet opérateur, généralise l'opérateur de Kleene et se note par un symbole similaire `°`, faisant que `"<"a,f"(.)",g"(.,.)>"` `=` `{a,f"(.)",g"(.,.)"}°`.

Ce langage se présente donc comme suit :

`ccL° ccM`

`ccL= {a,f,g}`
`ccM = {A,"="}`

L'expression `"<"ccL">"` ou `ccL°` désigne la clôture par composition close des éléments et opérateurs de `ccL`. C'est le domaine de Herbrand généralisé à des opérateurs de types plus complexes que nous verrons plus loin, et qui est appelé le langage d'opérateurs. C'est aussi la structure libre du langage qui en constitue son monde canonique nu et infini.

Puis, au premier ordre, on en extrait qu'un seul type d'opérateurs, généralement les éléments, ce qui se note en appliquant la restriction `"|"_E` et qui est prise par défaut sauf si le contexte le précise autrement. Ainsi nous avons

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

Le produit `"<"ccL">" ccM`, en notation française, désigne les compositions closes des prédicats appartenant à `ccM` composés avec des éléments appartenant à `"<"ccL">"`. C'est l'ensemble des littéraux affirmatifs.

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

On appelle cet ensemble, la matrice du langage. Ce sont des cases mémoires qui permettent de construire un monde concret à partir de la structure libre. Chaque monde est une instantiation de bas niveau de la structure. Chaque littéral affirmatif doit posséder une valeur booléenne `0` ou `1`, ou l'infini de Turing `oo` lorsque le monde n'est pas complet, qu'elle mémorise pour construire un monde qui se définie donc comme une instance de cette structure. Mais le prédicat d'égalité impose une contrainte spécifique, à savoir :

Si deux termes sont égaux selon le prédicat d'égalité alors il peuvent être permutés dans tout littéral affirmatif où ils apparaisent comme sous-terme ou terme, sans que cela ne change la valeur booléenne du littéral en question.

Comme nous nous intéressons aux seuls cas des mondes finis, cette contrainte et assurement suffisante pour assurer leur cohérence.

Le prédicat `A` désigne un ensemble que nous nommons avec le même nom. De cette façon nous définissons un nouvel opérateur dit d'appartenance `"∈"`, et l'expression logique `A(x)` est équivalente à `x"∈"A`, et l'expression logique `"¬"A(x)` est équivalente à `x"∉"A`. Mais on n'ajoute pas cet opérateur au langage de la structure, on l'utilise uniquement par commodité comme seconde écriture (dans les cas où il est défini), car on ne s'intéresse pas à la théorie des ensembles pour l'instant.

Remarquer qu'un monde peut être volontairement incomplet. Il aura alors le statut de disjonction de mondes. Dans le cas infini on est contraint à cette situation d'après les théorèmes de Godel et de Turing. Par contre dans le cas fini, on peut toujours compléter les mondes, les définitions sémantiques sont exactes, complètes et parfaitement déterminées, ce qui est loin d'être le cas lorsque les mondes deviennent infinis.

 

 

---- 1 novembre 2014 ----

 

 

 

4) Groupe (suite)

Reprenons notre structure de groupe `G` défini au chapitre `2`. La structure de groupe ainsi exposée possède le langage `"<"1,frI,"∗>"{"="}`, et possède la théorie suivante :

`AAxAAyAAz, (x"∗"y"∗")z"="x"∗"(y"∗"z)`
`AAx, x"∗"1"="x`
`AAx, 1"∗"x"="x`
`AAx, xfrI(x)"="1`
`AAx, frI(x)x"="1`

Puis on s'intérresse au langage `"<"1,frI,"∗>"{"="}` et à un ensemble sous-jacent de `n` éléments `G=⟅ e_1,e_2,e_2,...,e_n ⟆` servant à construire les mondes d'au plus `n` éléments. Ce sont `n` éléments qui peuvent être rendus égaux, et qui constituent la base de construction des mondes d'au plus `n` éléments.

On procéde alors à une extension élémentaire en ajoutant au langage les éléments `e_1,e_2,e_3,...,e_n` et en ajoutant au cadre théorique la restriction que tous les opérateurs et prédicats évoqués soient définis dans l'ensemble sous-jacent `G` ou dans ses dérivés `G"→"G`, `G"→"(G"→"G)`, `(G"→"G)"→"G`, ..., que nous verrons plus loin.

Cela constitue un univers où chaque instantiation cohérente de bas niveau constitue un monde d'au plus `n` éléments qui est possible pour cet univers.

Ainsi nous définissons deux niveaux de langage emboités. Un premier niveau dit langage de l'univers `"<"1,frI,"∗>"{"="}` et un second niveau, le bas niveau, dit langage des mondes possédant au plus `n` éléments, `"<"1,e_1,e_2,e_3,...,e_n, frI,"∗>"{"="}`, et en ajoutant au cadre théorique la restriction que l'ensemble sous-jacent est `⟅e_1,e_2,e_3,...,e_n⟆`.

Chaque proposition `P` écrite dans le langage de haut niveau `"<"1,frI,"∗>"{"="}` aura une signification spécifique dans chaque monde `G` décrit dans le langage de bas niveau `"<"1,e_1,e_2,e_3,...,e_n, frI,"∗>"{"="}`. Si la proposition `P` est vrai dans le monde `G`, nous dirons que `P` se réalise dans `G`, ou que `G` réalise `P`, ou que `G` satisfait `P`, et nous noterons `G"⊨"P`.

Chaque proposition `P` écrite dans ce langage `"<"1,frI,"∗>"{"="}` constitue un paramètre macroscopique. Tandis que chaque littéral de `"<"1,e_1,e_2,e_3,...,e_n,frI,"∗>"{"="}` constitue un paramètre microscopique. Le nombre de mondes complets satisfaisant la proposition `P` représente le nombre d'états microscopiques possibles de `G` possédant le même état macroscopique défini par `P` et `|G|`. L'entropie qui est exprimée en bits, en est le logarithme en base `2`.

---- 30 novembre 2019 ----

5) Différentes théories de groupe

Nous devons revenir sur la définition d'un groupe car il y a plusieurs façons de définir la théorie du groupe, soit par une théorie du premier ordre, soit par une théorie du second ordre, ou soit par une théorie du premier ordre dans un langage augmenté...

5.1) Définition du premier ordre

On définit une structure de groupe, en notation multiplicative, comme suit. On présente un ensemble-sous jacent prédéterminé `G`. On le muni d'une loi de composition interne `"∗"`, qui admet un élément neutre et qui admet pour chaque élément un inverse. Autrement dit on le munie d'une application de `G"×"G"→"G`, que l'on nomme `"∗"`, et qui doit satisfaire la théorie du groupe suivante :

`AAxAAyAAz, (x"∗"y"∗")z"="x"∗"(y"∗"z)`
`EE1AAx, x"∗"1"="x" et "1"∗"x"="x" et "EEy, yx"="1" et "xy"="1`

Tout cela se fait implicitement en énonçant simplement :

`(G,"∗")` est un groupe

Puis une distinction doit s'opérer entre le modèle et le groupe. Le modèle est la structure comprenant le langage `"<∗>"{"="}` et comprenant la théorie précédente. Tandis qu'un groupe est une réalisation du modèle. Un groupe d'au plus `n` élément est une théorie complète de langage `"<∗",e_1,e_2,e_2,...,e_n">"{"="}` et d'ensemble sous-jacent `⟅ e_1,e_2,e_2,...,e_n ⟆`

Si nous considérons plusieurs groupes `(G,"∗")` et `(H,"∗")` en utilisant le même symbole de produit, alors on pourra spécifie la loi de composition à l'aide d'un indice pour savoir à quelle groupe elle fait référence : `"∗"_G`, `"∗"_H`.

5.2) Définition du second ordre

Cette définition se distingue de la précédente en ce qu'elle affirme l'existence d'un opérateur d'inversion `frI"(.)"`

`AAxAAyAAz, (x"∗"y"∗")z"="x"∗"(y"∗"z)`
`EE1EE frI"(.)"AAx, x"∗"1"="x" et "1"∗"x"="x" et "xfrI(x)"="1" et "frI(x)x"="1`

Comme nous ne considérons que des groupes finis, l'équivalence de Skolem que nous verrons plus loin est valide. Et donc cette deuxième définition est exactement équivalente à la première.

5.3) Définition du premier ordre dans un langage augmenté :

Dans le langage augmenté des opérateurs `1,frI"(.)"`, la définition du second ordre précédente s'exprime au premier ordre et de façon universelle (sans quantificateur existenciel) :

`AAxAAyAAz, (x"∗"y"∗")z"="x"∗"(y"∗"z)`
`AAx, x"∗"1"="x`
`AAx, 1"∗"x"="x`
`AAx, xfrI(x)"="1`
`AAx, frI(x)x"="1`

On désigne ainsi l'élément neutre de la loi par `1` et l'opérateur d'inversion de la loi par `frI"(.)"`. Le langage du groupe est ainsi augmenté en `"<∗", 1, frI">"{"="}`. Tout cela se fait implicitement en énonçant simplement :

`(G,"∗",1,frI)` est un groupe

Puis une distinction doit s'opérer entre le modèle et le groupe. Le modèle est la structure comprenant le langage `"<∗", 1, frI">"{"="}` et comprenant la théorie précédente, et il s'applique à tous les groupes. Tandis qu'un groupe est une réalisation du modèle. Un groupe d'au plus `n` élément est une théorie complète de langage `"<"e_1,e_2,e_2,...,e_n,1,frI,"∗>"{"="}` et d'ensemble sous-jacent `⟅ e_1,e_2,e_2,...,e_n ⟆`

Puis, si nous définissons plusieurs structures de groupe en utilisant les même symboles d'opérateurs, tel que `(G,"∗",1,frI)` et `(H,"∗",1,frI)`, alors on pourra spécifier les opérateurs à l'aide d'un indice pour savoir à quelle groupe ils font référence : `"∗"_G`, `1_G`, `frI_G`, `"∗"_H`, `1_H`, `frI_H`.

5.4) Groupe de fonctions

Tout monoïde agit sur lui même par translation, et donc peut être considéré comme un ensemble d'applications. Ainsi peut-on définir un groupe comme étant un ensemble d'applications réversibles

Groupe d'applications `(E, @)` avec `AA(f,g) in (E->E)^2, f@g = (AAx in E, x|->f(g(x)) )`

 

 

 

 

 

 

Un patron de structure comprend un nom, un langage et un théorie. Par exemple la structure de groupe a comme nom "groupe" comme langage

---- 29 novembre 2019 ----

 

Ainsi expose-t-on une théorie des mondes finis.

On utilise le terme de monde et non celui de modèle qui sera utilisé pour désigner autre chose. Les mondes sont des structures instantiées par le plus bas niveau, celui des littéraux. Tandis que les modèles qui nous servent de patron et que nous choisissons à notre convenance sont des structures non instantiées.

 

un ensemble sous-jacent de même nom `G` et des opérateurs et prédicats définis dans l'ensemble sous-jacent `G` ou dans ses types dérivées `G"→"G`, `G"×"G"→"G`, `(G"→"G)"→"G`, ... , que nous verrons plus loin.

Ces opérateurs et prédicats sont dit appartenir à la présentation de `G`. Ils forment un langage logique dont on ne retient que la clef qui est constituée du type de chaque opérateur et prédicat ainsi qu'un ordre des opérateurs ayant le même type et d'un ordre des prédicats ayant le même type.

Et la structure `G` constitue un monde où chaque littéral affirmatif du langage en question possède une valeur `0,1` ou `oo`, un monde dans le quel la théorie se réalise.

Ainsi la théorie constitue un paramètre macroscopique, tandis que chaque littéral affirmatif constitue un paramètre microscopique.

L'interprétation du langage de la structure est posé comme étant interne à la structure, c'est à dire que les quantifications universelles et existentielles sont interprétées comme ayant une portée limitée à l'ensemble sous-jacent `G` ou à ses types dérivées.

 

 

 

5.5) Théories d'engendrement

 

, ou bien encore d'une façon totalement différente dite récursive.

Définition récursive :

On définit une structure de groupe en présentant des opérateurs générateurs qui vont construire tous les éléments de la structure libre, et une théorie d'égalité qui va quotienter la structure libre pour produire tous les éléments du groupe. Par exemple voici le groupe bigène libre :

`G="Groupe"("∗",1,frI,a,b)`

Le premier argument du patron `"Groupe"` est sa loi de composition interne `"∗"`, le second argument est l'élément neutre `1`, le troisième argument est l'opérateur d'inversion `frI`, et les arguments suivants sont des éléments générateurs `a,b`. Dans cet exemple il y a que deux éléments générateurs. Les éléments de la structure sont construits à partir des opérateurs de la présentation. Puis, à charge de ces affectations, le patron `"Groupe"` transporte la théorie du groupe suivante :

`AAxAAyAAz, (x"∗"y"∗")z"="x"∗"(y"∗"z)`
`AAx, x"∗"1"="x`
`AAx, 1"∗"x"="x`
`AAx, xfrI(x)"="1`
`AAx, frI(x)x"="1`

Les éléments du groupe sont les classes d'équivalences de la relation d'équivalence définie comme suit : `x` et `y` étant deux termes quelconques appartenant à la structure libre `"<∗",1,frI,a,,b">"`, ils sont équivalents si et seulement si la théorie du groupe le démontre, ce qui se note, `G|--x"="y`.

De même que précédement, il existe un langage du groupe, commun à tous les groupes. Une distinction doit donc s'opérer entre le langage du groupe `"<∗", 1, frI">"{"="}` qui est le même pour tous les groupes, et qui est celui du modèle, et la définition du groupe qui instancie d'une certaine façon les opérateurs et prédicats du modèle.

Puis, si nous définissons plusieurs groupes, en utilisant les même symboles d'opérateurs que ceux du modèle, `G"=Groupe"("∗",1,frI,a,b)` et `H"=Groupe"("∗",1,frI,a,b)`, alors on pourra spécifie ces opérateurs à l'aide d'un indice pour savoir à quelle groupe ils font référence : `"∗"_G`, `1_G`, `frI_G`, `a_G`, `b_G`, `"∗"_H`, `1_H`, `frI_H`, `a_H`, `b_H`.

5.5)

 

 

 

 

 

 

 

 

 

 

 

 

Si la proposition `P` est vrai dans la structure `G`, nous dirons que `P` se réalise dans `G`, ou que `G` réalise `P`, ou que `G` satisfait `P`, et on notera `G"⊨"P`.

 

 

Une structure du premier ordre servant de patron comprend un nom de patron, tel que par exemple Groupe, et est désigné par une variable, par exemple `G`, qui représente une sorte d'intanciation canonique d'apport informationnelle nulle. C'est une façon de dire deux fois la même chose mais l'une est abstraite et sert de patron tandis que l'autre est concrète et constitue une déclinaison du patron, une instanciation de variables libres par d'autres variables libres, mais qui ne constitue pas encore un monde dans lequel chaque littéral doit avoir une détermination parmis `0,1, oo`.

Le groupe `G` comprend un ensemble sous-jacent désigné par la même lette `G`, et il comprend des opérateurs `ccL"="{"∗", 1, frI}` et des prédicats `ccM"="{"="}` constituant le langage du Groupe.

La structure `G` comprend une théorie `T` écrite dans ce langage `"<"ccL">"{ccM}`. La structure s'obtient en quotientant la structure libre du langage `"<"ccL">"` par la théorie `T` :

`E = ("<"ccL">"{ccM})"/"T`

Les éléments de la structure sont les classes d'équivalences de la relation d'équivalence définie comme suit : `x` et `y` étant deux termes quelconques appartenant à la structure libre `"<"ccL">"`, ils sont équivalents si et seulement si la théorie de la structure le démontre, ce qui se note, `T|--x"="y`.

Et la structure de groupe, étant définie en toute généralité, elle constitue un patron de structure, c'est à dire qu'elle va, en instanciant ses opérateurs et prédicats, construire des mondes qui seront autant de groupes particuliers conforme au patron Groupe.

 

 

Ainsi, étant donné une proposition `P` écrite dans ce langage, et étant donné une structure `G` possédant ce langage.

lorsque `P` est vrai dans `G`, on dira que `P` se réalise dans `G`, ou que `G` réalise `P`, ou que `P` satisfait `X`, et on notera `G"⊨"P`.

---- 23 novembre 2019 ----

 

4) langage du n-ième ordre

Au premier ordre, seuls les éléments peuvent être quantifiés `EE` ou `AA`. Au second ordre, les opérateurs et prédicats s'appliquant à des éléments peuvent à leur tour être quantifiés. Au troisième ordre, les opérateurs et prédicats s'appliquant à des opérateurs et prédicats s'appliquant à des éléments, peuvent à leur tour être quantifiés, etc.. Les opérateurs et prédicats sont donc typés, conventionnellement on ajoute parfois en exposant leur type explicite comme suit :

`x` ou `x^E` pour désigner un élément (opérateur zéro-aire) `x`.
`f"(.)"` ou `f^(E"→"E)` pour un opérateur unaire `f`.
`A"(.)"` ou `A^(E"→"{0,1})` pour un prédicat unaire `A`.
`g"(.,.)"` ou `g^(E"×"E"→"E)` pour un opérateur binaire `g`.
`R"(.,.)"` ou `R^(E"×"E"→"{0,1})` pour un prédicat binaire `R`.
`h"(.,.,.)"` ou `h^(E"×"E"×"E"→"E)` pour un opérateur ternaire `h`.
`K"(.,.,.)"` ou `K^(E"×"E"×"E"→"{0,1})` pour un prédicat ternaire `K`.
`varphi"(.→.)"` ou `varphi^((E"→"E)"→"E)` pour un opérateur `varphi` de `(E"→"E)"→"E`.
`Gamma"(.→.)"` ou `Gamma^((E"→"E)"→"{0,1})` pour un prédicats `Gamma` de `(E"→"E)"→"{0,1}`.
`beta"((.→.)→.,.)"` ou `beta^(((E"→"E)"→"E)"→"(E"→"E))` pour un opérateur `beta` de `((E"→"E)"→"E)->(E"→"E)`.
etc..

Dans une proposition, tous les opérateurs et prédicats y apparaissant doivent être quantifiés, soit préalablement en faisant parti d'un langage, soit implicitement selon le contexte, ou soit explicitement dans la proposition. Sinon nous obtenons une fonction propositionnelle, et qui doit alors être déclarée comme telle par un prototype.

Conventionnellement, l'introduction de nouveaux opérateurs ou prédicats dans une proposition, sans qu'ils n'aient été préalablement déclarés, sont par défaut quantifiés universellement sur l'ensemble auquel se restreint le langage logique, et possède un type déterminé par la forme syntaxique utilisée, selon un mécanisme d'inférence de type. Et en cas d'ambiguité sur le type, c'est au contexte que reviendra la charge de départager les différents types possibles. Cela s'applique aussi aux propositions décrites littéralement. Ainsi par exemples, après avoir défini l'opérateur d'inversion `x"↦"x^("-"1)`, si nous disons :

« Étant donné la fonction `f`, nous avons `f(f(x))"="x^("-"1)` »

Cela signifie : `AAx,f(f(x))"="x^("-"1)`. Et de même, si nous disons :

« Étant donné un élément `a` nous avons `f(A)"⊆"A => (a"∈"A "ou" a^("-"1)"∈"A)` »

Cela signifie : `AA A "(.)", f(A)"⊆"A => (a"∈"A "ou" a^("-"1)"∈"A)`. Et par ailleurs, si nous disons :

« On définit la proposition `P(f)"="( AAxEEy,x"="f(f(y)) )` »

Le type de `f` est déterminé comme s'appliquant à un élément et retournant un élément. L'inférence de type dans cette expression assigne donc à `f` le type `E"→"E`. La proposition `P(f)` définie alors un prototype de fonction propositionnelle de type `(E"→"E)"→"{0,1}` autrement dit `P` est une application qui prend en entrée une application dans `E` et retourne un booléen.

Dans le cas infini, la sémantique des opérateurs et prédicats s'avèrent incomplète. Mais dans le cas fini qui nous intéresse ici, la sémantique est bien définie. Elle est fini et fait partie de la combinatoire, le nombre d'applications de `A"→"B` étant égale à :

`|A"→"B|=|B|^|A|`

Nous pouvons calculer le cardinal de tous ces types d'opérateurs et prédicats. Par exemple, le nombre d'opérateurs de type `((G"→"G)"→"G)->(G"→"G)` est :

`|((G"→"G)"→"G)->(G"→"G)| = (|G|^|G|)^(|G|^(|G|^|G|))`

5) La négation

Le langage logique permet facilement d'exprimer la négation d'une proposition, par un procédé récurcif : En inversant les quantificateurs `AA` `EE` dans l'entête puis en négativant la fonction propositionnelle sur laquelle ils portent, ou bien en inversant le `"et"` `"ou"` et en négativant leurs arguments, ou bien en inversant le `"⇔"` `"⊕"` et en laissant inchangés leurs arguments, ou bien en remplaçant l'expressions de la forme `A"⇒"B` directement par `A "et" "¬"B`. Par exemple, considérons la proposition suivante :

`P(R) = EEh"(.)"AAx, R(x,h(x)) => x"≠"h(x)`

Cette proposition signifie littéralement qu'il existe une application `h` telle qu'à chaque fois que `x` et en `R`-relation avec son image `h(x)`, il est alors différent de son image `x"≠"h(x)`. La négation s'obtient ainsi :

`"¬"P(R) = "¬"( EEh"(.)" AAx, R(x,h(x)) => x"≠"h(x) )`
`"¬"P(R) =       AAh"(.)" EEx, R(x,h(x)) "et" x"="h(x)`

Dans le cas fini, c'est à dire où l'ensembles sous-jacent `E` est fini, toutes théories est complètable puisqu'il suffit d'énumérer tous les cas qui sont en nombre fini. Et donc, étant donné une propostion `P`, nous avons toujours :

`E"⊨"P "ou" E"⊨¬"P`

C'est à dire que la négation de l'expression `E"⊨"P` que l'on note `E"⊭"P` se traduit par :

`E"⊭"P<=> E "⊨¬"P`

Et il existe toujours une démonstration (en énumérant tous les cas), ce que l'on note par :

`E"⊨"P<=> E "⊢"P`  

 

---- 20 novembre 2019 ----

 

L'opérateur `f(h)` est aussi noté `h_f(G)`, et le prédicat `f(R)` est aussi noté `R_f(G)`, faisant référence à la structure `f(G)`. On a donc une structure `(G,h,R)` désigné par `G` qui est transporté par l'application `f` en une structure `(f(G),f(h),f(R))` pouvant être noté comme le modèle `(G,h,R)` mais désigné par `f(G)`, c'est à dire `(f(G),h,R)` avec `h_f(G)=f(h)`, et `R_f(G)=f(R)`.

 

 

 

 

 

 

 

 

5) Langage de type

Il n'est pas pertinant de démultiplier les types pour la même raison que la forme la plus simple parmis deux formes se contenant potentiellement mutuellement est la plus simple des deux. Ainsi une application de `A"→"B``A` et `B` sont des sous-ensemblee de `E` se ramène à une application de `E"→"E` en la complétant n'importe comment.

Puis, le procédé de currification fait qu'une application de `A"→"(B"→"C)` est équivalente à une application de `A"×"B"→"C`.

La liste des types considérés commence alors comme suit. Dans l'avant dernière colonne se trouve l'ordre de la logique qui quantifie ces types. Dans la dernière colonne se trouve la quantité d'information que représente la détermination d'un élément du type en question, c'est le logarithme en base 2 du cardinale du type :

Type d'opérateur
forme série
Type d'opérateur
forme liste
Ordre logique
Quantité
d'information
d'un opérateur
1
`E`
`E`
1
`Q"="ln(n)"/"ln(2)`
1
`E"→"E`
`E"→"E`
2
`nQ`
2
`(E"→"E)"→"E`
`(E"→"E)"→"E`
3
`n^nQ`
`E"→"(E"→"E)`
`E"×"E"→"E`
2
`n^2Q`
5
`((E"→"E)"→"E)"→"E`
`((E"→"E)"→"E)"→"E`
4
`n^(n^n)Q`
`(E"→"(E"→"E))"→"E`
`(E"×"E"→"E)"→"E`
3
`n^(n^2)Q`
`(E"→"E)"→"(E"→"E)`
`(E"→"E)"×"E"→"E`
3
`n^(n"+"1)Q`
`E"→"((E"→"E)"→"E)`
`E"×"(E"→"E)"→"E`
3
`n^(n"+"1)Q`
`E"→"(E"→"(E"→"E))`
`E"×"E"×"E"→"E`
2
`n^3Q`
14
`(((E"→"E)"→"E)"→"E)"→"E`
`(((E"→"E)"→"E)"→"E)"→"E`
5
`n^(n^(n^n))Q`
`((E"→"(E"→"E))"→"E)"→"E`
`(E"×"E"→"E)"×"E"→"E`
3
`n^(n^2+1)Q`
`((E"→"E)"→"(E"→"E))"→"E`
`((E"→"E)"×"E"→"E)"→"E`
4
`n^(n^n n)Q`
`(E"→"((E"→"E)"→"E))"→"E`
`E"×"((E"→"E)"→"E)"→"E`
4
`n^(n^n)nQ`
`(E"→"(E"→"(E"→"E)))"→"E`
`(E"×"E"×"E"→"E)"→"E`
3
`n^(n^3)Q`
`((E"→"E)"→"E)"→"(E"→"E)`
`((E"→"E)"→"E)"×"E"→"E`
4
`n^(n^n)nQ`
`(E"→"(E"→"E))"→"(E"→"E)`
`(E"×"E"→"E)"×"E"→"E`
3
`n^(n^2)nQ`
`(E"→"E)"→"((E"→"E)"→"E)`
`(E"→"E)"×"(E"→"E)"→"E`
3
`(n^n)^2Q`
`(E"→"E)"→"(E"→"(E"→"E))`
`(E"→"E)"×"E"×"E"→"E`
3
`(n^n)n^2Q`
`E"→"(((E"→"E)"→"E)"→"E)`
`E"×"((E"→"E)"→"E)"→"E`
4
`n^(n^n)nQ`
`E"→"((E"→"(E"→"E))"→"E)`
`E"×"(E"×"E"→"E)"→"E`
3
`n^(n^2)nQ`
`E"→"((E"→"E)"→"(E"→"E))`
`E"×"(E"→"E)"×"E"→"E`
3
`(n^n)n^2Q`
`E"→"(E"→"((E"→"E)"→"E))`
`E"×"E"×"(E"→"E)"→"E`
3
`(n^n)n^2Q`
`E"→"(E"→"(E"→"(E"→"E)))`
`E"×"E"×"E"×"E"→"E`
2
`n^4Q`
...
...
...
...

 

 

Type d'opérateur
forme liste
Type de prédicat
Forme liste
Ordre logique
Quantité
d'information
d'un prédicat
1
`E`
`{0,1}`
0
1
1
`E"→"E`
`E"→"{0,1}`
1
`n`
2
`(E"→"E)"→"E`
`(E"→"E)"→"{0,1}`
3
`n^n`
`E"×"E"→"E`
`E"×"E"→"{0,1}`
2
`n^2`
5
`((E"→"E)"→"E)"→"E`
`((E"→"E)"→"E)"→"{0,1}`
4
`n^(n^n)`
`(E"×"E"→"E)"→"E`
`(E"×"E"→"E)"→"{0,1}`
3
`n^(n^2)`
`(E"→"E)"×"E"→"E`
`(E"→"E)"×"E"→"{0,1}`
3
`n^(n"+"1)`
`E"×"(E"→"E)"→"E`
`E"×"(E"→"E)"→"{0,1}`
3
`n^(n"+"1)`
`E"×"E"×"E"→"E`
`E"×"E"×"E"→"{0,1}`
2
`n^3`
14
`(((E"→"E)"→"E)"→"E)"→"E`
`(((E"→"E)"→"E)"→"E)"→"{0,1}`
5
`n^(n^(n^n))`
`(E"×"E"→"E)"×"E"→"E`
`(E"×"E"→"E)"×"E"→"{0,1}`
3
`n^(n^2+1)`
`((E"→"E)"×"E"→"E)"→"E`
`((E"→"E)"×"E"→"E)"→"{0,1}`
4
`n^(n^n n)`
`E"×"((E"→"E)"→"E)"→"E`
`E"×"((E"→"E)"→"E)"→"{0,1}`
4
`n^(n^n)n`
`(E"×"E"×"E"→"E)"→"E`
`(E"×"E"×"E"→"E)"→"{0,1}`
3
`n^(n^3)`
`((E"→"E)"→"E)"×"E"→"E`
`((E"→"E)"→"E)"×"E"→"{0,1}`
4
`n^(n^n)n`
`(E"×"E"→"E)"×"E"→"E`
`(E"×"E"→"E)"×"E"→"{0,1}`
3
`n^(n^2)n`
`(E"→"E)"×"(E"→"E)"→"E`
`(E"→"E)"×"(E"→"E)"→"{0,1}`
3
`(n^n)^2`
`(E"→"E)"×"E"×"E"→"E`
`(E"→"E)"×"E"×"E"→"{0,1}`
3
`(n^n)n^2`
`E"×"((E"→"E)"→"E)"→"E`
`E"×"((E"→"E)"→"E)"→"{0,1}`
4
`n^(n^n)n`
`E"×"(E"×"E"→"E)"→"E`
`E"×"(E"×"E"→"E)"→"{0,1}`
3
`n^(n^2)n`
`E"×"(E"→"E)"×"E"→"E`
`E"×"(E"→"E)"×"E"→"{0,1}`
3
`(n^n)n^2`
`E"×"E"×"(E"→"E)"→"E`
`E"×"E"×"(E"→"E)"→"{0,1}`
3
`(n^n)n^2`
`E"×"E"×"E"×"E"→"E`
`E"×"E"×"E"×"E"→"{0,1}`
2
`n^4`
...
...
...
...

 

 

 

 

 

 

 

 

15) L'équivalence de Skolem et de Herbrand

Dans le cas fini, toute théorie est nécessairement complètes puisqu'il suffit d'énumérer tous les cas. Et donc l'équivalence de Skolem est exacte. Par exemple :

`AAxEEy, P(x,y) <=> EEy"(.)"AAx, P(x,y(x))`

Et la contraposée correspond à l'équivalence de Herbrand :

`EExAAy, P(x,y) <=> AAy"(.)"EEx, P(x,y(x))`

Et si on réitère le processus, on obtient:

`EExAAy, P(x,y) <=> EEx"(.→.)"AAy"(.)", P(x(y),y(x(y)))`

Cela se démontre par restriction aux seules applications constantes, en remarquant que les seuls applications constantes `y"(.)"` et `x"(.→.)"` sont suffisantes pour explorer toutes les possibilitées, ce qui permet de remplaçer le quantificateur `AAy"(.)"` par `AAy` et la valeur `y"(a,b,c,...)"` par `y` à condition que les quantificateurs de `a,b,c,...` soit déclarés avant celui de `y`. Et de même, cela permet de remplacer le quantificateur `EEx"(.→.)"` par `EEx` et la valeur `x"(a,b,c,...)"` par `x` à condition que les quantificateurs de `a,b,c,...` soit déclarés avant celui de `x`, et cela signifie aussi qu'une fonction de `a,b,c,...` qui est fonction de `a,b,c,...` n'est pas davantage fonction de `a,b,c,...`.

Ainsi à chaque alternative de blocs `EE...EEAA...AA` ou `AA...AAEE...EE`, se crée un lien de dépendance. Les variables du second bloque dépendent des variables du premier bloque. Et cela s'exprime au second ordre en remplaçant les variables ainsi dépendantes par des opérateurs s'appliquant sur les variables dont ils dépendent. Par exemple :

        `AAxEEyAAzEEt, P(x,y,z,t)`
`<=>`
        `AAxEEy"(.)"AAz"(.)"EEt"(.,.)", P( x, y(x), z(y(x))), t(x,z(y(x))) )`

Toutes les dépendances étant explicitées, les quantificateurs peuvent être intervertis librement grâce à l'équivalence que l'on obtient par restriction aux seules applications constantes vue précédement. La forme skolémisée est :

`EEy"(.)"EEt"(.,.)"AAxAAz"(.)", A(x,y(x),z(y(x))),t(x,z(y(x))))`

Cela se simplifie encore pour la même raison, en constatant que les applications `z"(.)"` constantes engendrent un ensemble d'images égale à `G`, et donc que l'on peut remplacer la quantification `AAz"(.)"` par `AAz` et les expressions `z(...)` par `z` à condition que les arguments de `z` soit déclarés avant `z` :

`EEy"(.)"EEt"(.,.)"AAxAAz, A(x,y(x),z,t(x,z))`

Et la forme herbrandisée est :

`AAxAAz"(.)"EEy"(.)"EEt"(.,.)", A(x,y(x),z(y(x))),t(x,z(y(x))))`

Cela se simplifie encore pour la même raison, par restriction aux seuls applications constantes vue plus haut :

`AAxAAz"(.)"EEyEEt, A(x,y,z(y),t)`

Une écriture plus judicieuse utilisera des variables d'état dont les dépendances sont explicites, comme suit :

        `AAxEEyAAzEEt, A(x,y,z,t)`
`<=>`
        `AAxEEy(x)AAz(y)EEt(x,y), A(x,y,z,t)`

Toutes les dépendances étant explicitées, les quantificateurs peuvent être intervertis librement. La forme skolémisée est :

`EEy(x)EEt(x,y)AAxAAz(y), A(x,y,z,t)`

Cela se simplifie en constatant que les argument de `z"(.)"` sont toujours déclarés avant la déclaration de `z` :

`EEy(x)EEt(x,y)AAxAAz, A(x,y,z,t)`

`EEy"(.)"EEt"(.,.)"AAxAAz, A(x,y(x),z,t(x,y))`

Et la forme herbrandisée est :

`AAxAAz(y)EEy(x)EEt(x,y), A(x,y,z,t)`

Cela se simplifie en constatant que les argument de `t"(.,.)"` sont toujours déclarés avant la déclaration de `t` :

`AAxAAz(y)EEyEEt, A(x,y,z,t)`

`AAxAAz"(.)"EEyEEt, A(x,y,z(y),t)`

16) Logique respectueuse de l'indépendance

De même, les concepts d'indépendance, propre à la logique dite respectueuse de l'indépendance (Iogique IF), (independence-friendly logic), se définissent de façon exacte dans le cas fini. L'indépendance devient une propriété arithmétique parfaitement bien définie. Par exemple, en utilisant la notation antislash pour affirmer l'indépendance vis-à-vis d'une variable précédement déclarée ou d'un ensemble de variables précédément déclarées, si nous avons :

`P = AAxEEyAAzEEt"\"x, K(x,y,z,t)`

L'expression `EEt"\"x` signifie « il existe `t` indépendament de `x` ». On traduit cette proposition en utilisant la notation des dépendances explicites des variables d'état. Puis en skolémisant l'expression et en la remettant en notation normale, comme suit :

`P = AAxEEy(x)AAz(y)EEt(z), K(x,y,z,t)`

`P = EEy(x)EEt(z)AAxAAz(y), K(x,y,z,t)`

Et cela se simplifie en constatant que l'argument de `z"(.)"` est toujours déclaré avant la déclaration de `z` :

`P = EEy(x)EEt(z)AAxAAz, K(x,y,z,t)`

`P = EEy"(.)"EEt"(.)"AAxAAz, K(x,y(x),z,t(z))`

Ou bien en hérbrandisant l'expression et en la remettant en notation normale, comme suit :

`P = AAxEEy(x)AAz(y)EEt(z), K(x,y,z,t)`

`P = AAxAAz(y)EEy(x)EEt(z), K(x,y,z,t)`

Et cela se simplifie en constatant que l'argument de `t"(.)"` est toujours déclaré avant la déclaration de `t` :

`P = AAxAAz(y)EEyEEt, K(x,y,z,t)`

`P = AAxAAz"(.)"EEyEEt, K(x,y,z(y),t)`

 

---- 15 novembre 2019 ----

1) Structure libre

On définit récursivement une structure libre en présentant une liste d'opérateurs. Par exemple considérons la liste d'opérateurs (1,frI"(.)","∗(.,.)"). La structure libre se note `"<"1,frI"(.)","∗(.,.)>"`. Son ensemble sous-jacent est l'ensemble des compositions closes qu'il est possibles de faire avec un nombre quelconques d'occurence des opérateurs ainsi énumérés entre crochets `"<" ">"`.

Par convention, un groupe possède une loi de produit notée `"∗"`, un élément neutre noté `1`, et une loi d'inversion notée `frI`. La structure de groupe est notée `(G,"∗",1,frI)`. Le produit se note par simple juxtaposition. Et l'inverse d'un élément se note par l'élévation à la puissance `"-"1`. Par exemple : `x"∗"y "=" xy` et `frI(x)"="x^("-"1)`.

Par convention on note la théorie du groupe appliquée à l'ensemble sous-jacent `G` comme suit. `(G,"∗",1,frI)` est un groupe si et seulement si :

`AA (x,y,z) "∈" G^3, ((x(yz)"="(xy)z),(x1"="x),(1x"="x),(x x^("-"1)"="1),(x^("-"1)x"="1))`

 

 

1) Morphisme

On se place dans un groupe `G`. Un morphisme `f` est une application qui respecte les opérateurs du groupe, c'est à dire satisfaisant les trois règles suivantes :

`AAxAAy`

`f(1)=1`
`f(xy) =f(x)(y)`
`f(x^("-"1))=f(x)^("-"1)`

L'image `f(G)` constitue un groupe qui est un sous-groupe de `G`.

 

 

8.3) Langage d'égalité

Faisons d'abord un constat sur le calcul booléen, si nous avons `X"⇒"X'` et `Y"⇒"Y'` alors nous avons :

`(X "et" Y) => (X' "et" Y')`

`(X "ou" Y) => (X' "ou" Y')`

Par contre nous ne pouvons pas déduire `X'"⇒"Y'` ni que `"¬"X => "¬"X'`. On généralise ce constat. On considére `n` inconnus booléens `X,Y,Z,...` tels que `X"⇒"X'` et `Y"⇒"Y'` et `Z"⇒"Z'` et etc.. Alors quelque soit la fonction booléenne propositionnelle `P` d'arité `n`, écrite dans le langage booléen `"<et","ou>"`, nous avons `P(X,Y,Z,...) => P(X',Y'Z',...)`.

À partir de cette remarque, on définit le langage dit langage d'égalité en n'utilisant comme connecteur booléens seulement la conjonction et la disjonction, et en n'utilisant que les prédicats affirmatifs dont l'égalité. Et on appelle proposition d'égalité, une proposition du langage d'égalité.

Toutes les égalités étant transportés par morphisme, on en déduit que toutes les propositions qui combinent ces égalités avec les seuls connecteurs booléens `"et","ou"`, sont également transportés par morphisme. Autrement dit :

   Toute proposition d'égalité qui se réalise dans `G`, se réalise aussi dans `f(G)`.   

Considérons par exemple la proposition suivante :

`P = (AAxEEy,x"="yy "ou" x"="yyy)`

La proposition `P` signifie littéralement que tout élément est soit un carré ou une cube.

Lorsque la proposition `P` est vrai dans le groupe `G`, nous dirons que `P` se réalise dans `G` ou que `G` satisfait `P`, et nous noterons :

`G⊨P`

Nous déduisons :

`G⊨P`
`=>      G⊨(AAxEEy,x"="yy "ou" x"="yyy)`
`=>       G⊨(AAxEEy,f(x)"="f(yy) "ou" f(x)"="f(yyy))`
`=>       G⊨(AAxEEy,f(x)"="f(y)f(y) "ou" f(x)"="f(y)f(y)f(y))`
`=>       AAz "∈" f(G), EEt "∈" f(G),z"="t t "ou" z"="t t t`
`=>       AAx "∈" f(G),EEy "∈" f(G),x"="yy "ou" x"="yyy`
`=>       f(G)⊨(AAxEEy,x"="yy "ou" x"="yyy)`
`=>       f(G)⊨P`

Ainsi la propriété `P`, qui est une propriété d'égalité du premier ordre, est transportées par le morphisme `f`, ce qui se note :

`(G"⊨"P) => (f(G)"⊨"P)`

Le morphisme constitue un traducteur transportant les propriétés d'égalités vrais sur `G` en des propriétés d'égalité vrais sur `f(G)`. Et cela s'applique aussi pour les propriétés d'égalité du second ordre. Considérons par exemple la proposition suivante :

`P = (EEh"(.)",AAxAAy, h(xy) "=" yx)`

La proposition `P` signifie littéralement qu'il existe une application qui appliquée à un produit `xy` donne comme résultat le même produit mais dans l'ordre inversé. La propriété `P`, qui est une propriété d'égalité du second ordre, est transportées par le morphisme `f`, ce qui se note :

`(G"⊨"P) => (f(G)"⊨"P)`

`(f(G)"⊨"P) <=> EEh_(f(G)->f(G)),AAx_(f(G)),AAy_(f(G)), h(xy) "=" yx`

On note le type des opérateurs en un indice, ainsi par exemples, `x_G` désigne un élement de la structure `G`, l'expression `h_(G"→"G)` désigne un opérateur unaire de la structure `G`, et l'expression `R_(G×G"→"{0,1})` désigne un prédicat binaire de la structure `G`.

9) Bijection

 

9) Plongement

On se place dans un groupe `G`. Un plongement `f` est un morphisme injectif c'est à dire vérifiant :

`AAxAAy, x"≠"y => f(x)"≠"f(y)`.

L'ensemble des plongements se note G"𕨪"G. Lorsque `G` est fini, son cardinal est :

|G"𕨪"G| = |G|!

L'application nous apporte le transport de l'égalités. Et l'injectivité nous apporte la réciproque, c'est à dire le transport de l'inégalité, ce qui nous permet de remplace l'implication par l'équivalence. Ainsi, dans le langage augmenté de prédicats `A"(.)", H"(.,.)"` et de l'opérateur `h"(.)"`, nous avons :

`AAxAAy, x"="y <=> f(x)"="f(y)`
`AAx, A(x) <=> f(A)(f(x))`
`AAxAAy, H(x,y) <=> f(H)(f(x),f(y))`
`AAxAAy, h(x)"="y <=> f(h)(f(x))"="f(y)`

Toute proposition dans la structure `G`, qu'elle soit affirmative ou négative, qui se réalise dans `G`, se réalise aussi dans `f(G)`.

`(G"⊨"P) <=> (f(G)"⊨"P)`

L'application inverse `f^("-"1)` de `f(G)"→"G` est encore un plongement. On dit que `f` est un isomorphisme de `G"↦"f(G)`. Et si `f(G)"="G`, on dit que `f` est un automorphisme de `G`. Notez que si `G` est fini, un plongement qui par défaut est défini partout, est nécessairement un automorphisme.

 

Le groupe des automorphismes de `G` se note `"Aut"(G)`. Il agit naturellement sur `G`. S'il existe un automorphisme envoyant `a` sur `b`, cela signifie que `a` et `b` ont des rôles analogues. L'action de `"Aut"(G)` sur `G`, partitionne `G`. Chaque partie ainsi créée s'appelle une orbite et correspond à un rôle, c'est à dire à un élément à automorphisme près. On note l'ensemble des orbites `G"÷Aut"(G)`.

De même, s'il existe un automorphisme envoyant une configuration `(a,b,A,r)` sur `(a',b',A',r')``a,b` sont des éléments de `G`, et `A` un sous-ensembles de `G`, et `r` un sous-ensemble de `G^2`. C'est à dire si :

`EE f"∈Aut"(G), ((f(a)"="a'),(f(b)"="b'),(f(A)"="A'),(f(r)"="r'))`

Alors les configurations `(a,b,A,r)` et `(a',b',c', A',B')` ont des rôles analogues.

10) Catégorie des groupes

 

 

 

Voir la suite : Quaternions et rotations 2

 


Dominique Mabboux-Stromberg