Précédent
 
Suivant

III) Langage logique du premier ordre

Un langage logique du premier ordre se définit en présentant une liste d'opérateurs et de prédicats non instanciés. 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..

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`. Les termes du langage d'opérateurs sont les compositions closes d'opérateurs. Ils forment le domaine de Herbrand qui désigne tous les éléments calculablesL On le note entre crochet :

`"<"a, f"(.)", g"(.,.)">" `

La récurrence est consubstentielle à la notion de structure. C'est pourquoi on commence par définir ce qu'est la récurrence générale :

On dit qu'un élément `x` respecte une proposition `P`, si et seulement si `P(x)` est vrai. On dit qu'un opérateur respecte une proposition `P` si et seulement si, appliqué qu'à des éléments respectant `P`, il produit un élément respectant `P`.

Etant donné un ensemble `L` d'opérateurs et d'éléments respectants `P`, la clôture par composition close notée `"<"L">"` ou `L"°"` est un ensemble d'éléments respectant `P`.

 

 

 

---- 14 décembre 2019 ----

 

On définit une opération

 

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.

---- 8 novembre 2014 ----

 

 

Dans notre conception des structures, on considère un ensemble suffisament grand pour contenir tous les éléments et qui est appelé l'ensemble sous-jacent, et un langage limité à cet ensemble comprenant des opérateurs et prédicats de types dérivé de l'ensemble sous-jacent. Puis on utilise un patron de structure qui complète la structure avec une théorie écrite dans le langage de la structure. Quand la théorie et vide, le patron s'appelle `"Structure"` et définit simplement un langage.

`"Structure"(G,h"(.)",R"(.,.)")`

Cette expression définie dans le contexte, la structure `G`, composée d'un ensemble sous-jacent `G` et d'un opérateur unaire inconnu `h` et d'un préficat binaire inconnu `R`. En d'autres termes, on pose comme hypothèse l'existence de `h` et de `R` indépendanment de tout paramètre autre que `G`. Une hypothèse qui est assurement vrai. Et cela s'écrit comme suit :

`EE h"∈"G"→"G, EER"∈"G"×"G"→"{0,1}`

Cettte assertion déclare un langage appliqué à `G`, et qui peut être rendu indépendant de `G` en extirpant cette dépendance :

`(EE h"(.)", EER"(.,.)" )^G`

Considérons maintenant le patron `"Bidule"` de langage `("E", bbh, bbR)` et de théorie :

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

C'est à dire explicitement

`EE h"∈"G"→" G, EER"∈"G"×"G"→"{0,1}, AAx"∈"G, x"="h(x) "ou" R(x,x)`

`(EE h"(.)", EER"(.,.)", AAx, x"="h(x) "ou" R(x,x))^G`

`(AAx, x"="h(x) "ou" R(x,x))^("("G, h"(.)",R"(.,.))")`

Le patron `"Bidule"` désigne sa théorie sous forme d'une fonction propositionnelle :

`"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`, que la restriction `R"|"_G` est un prédicat binaire dans `G`, et que cela forme un bidule c'est à dire telle que la théorie en question soit 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, tout en nommant de façon classique la structure par `G`.

É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` qui constitue la structure `(f(G),h,R)` ou notée simplement `f(G)`. Et on peut appliquer `f` aux éléments de `G`, et appliqué `f` de façon parallèle 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` qui constitue la structure `(f(G),f_"∥"(h),f_"∥"(R))` ou notée simplement `f_"∥"(G)`.

On peut aussi considérer une structure `K` que l'on déclare comme suit : `"Structure"(K,f(h),f(R))` et pour la quelle l'ensemble sous-jacent `K=f(G)`, alors la struture `K` devient l'image parallèle de la structure `G` par `f`, ce qui se note `K"="f_"∥"(G)`.

 

 

 

 

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.

 

et le prédicat d'égalité `"="` qui joue un rôle particulier exposé plus loin.

 

 

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 ----

Pour interpréter correctement cette théorie, il convient d'étudier l'équivalence de Skolem que nous présentons en deux parties. La première partie s'appelle la spécialisation. Etant donné une fonction propositionnelle quelconque `P"(.,.)"`, nous avons :

Spécialisation
`EE frI"(.)"AAx, P(x,frI(x))`  
`=>`
  `AAx EEi, P(x,i)`

Cette propriété de spécialisation est toujours valide. Elle signifie que si nous avons la preuve qu'il existe une application `frI"(.)"`, même si nous ne sommes pas capable de la calculer, qui satisfait la proposition `AAx, P(x,frI(x))`, alors nous pouvons conclure que pour tout `x` nous avons la preuve qu'il existe un élément `i`, l'élément défini par `i"="frI(x)`, même si nous ne sommes pas capable de le calculer, qui satisfait la proposition `P(x,i)`.

On considère ainsi des éléments définissables mais non calculables. Définissable signifie que la théorie prouve leur existence, tandis que calculable signifie être désigné par au moins un terme clos du langage d'opérateurs.

La seconde partie s'appelle la définition d'application, c'est la réciproque :

Définition
d'application
   `AAx EEi, P(x,i)`  
`=>`
  `EEfrI"(.)"AAx, P(x,frI(x))`   

Cette propriété définissant une application est équivalente à l'axiome du choix. C'est l'affirmation qu'il est possible de procéder à une infinité de choix arbitraires et ainsi de définir une application `frI"(.)"` sur un domaine pouvant être de cardinalité infini.

Mais certaines opinions récusent cet axiome du choix et n'admète à la place qu'un axiome plus faible n'autorisant qu'un nombre fini de choix arbitraires, appelé définition fini d'application :

Définition
fini
d'application
   `((A "est fini"), (AAx"," A(x) => EEi"," P(x,i)),(AAx"," "¬"A(x) => EE!i"," P(x,i)) )`
`=>`
`EEfrI"(.)"AAx, P(x,frI(x))`   

Où l'expression `EE!x` signifie qu'il existe un et un seul élement `x`. Autrement dit :

    `((A" est fini") , (AAx"," A(x) => EEi"," P(x,i)) , (AAx"," "¬"A(x) => EEi"," P(x,i) "et" AAj"," P(x,j)"⇒"(i"="j)) ) => EEfrI"(.)"AAx, P(x,frI(x))`

Mais lorsque l'ensemble sous-jacent est fini, cette distinction n'a plus lieu d'être, puisqu'il n'y a forcement qu'un nombre fini de choix possibles à faire. L'équivalence de Skolem devient assurement valide, et donc cette deuxième définition du groupe devient exactement équivalente à la première.

 

 

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 ----

 

 

 

 

---- 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

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écrire le langage logique du `n`-ième ordre, dont la définition ne pose pas de difficulté dans les cas finis, car elle fait alors 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.

Et c'est donc à partir de ces fondations assurement calculables et donc incontestables que pourra être posé de façon non bancale la question de l'infini, si l'infini existe, qu'elle est-il ? quelle forme prend-t-il ?.

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 bien définie, 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 quelque chose d'extérieur à la théorie, mais plutôt comme une instantiation de la théorie, entendue comme une instantiation fini d'un ensemble sous-jacent et de tous les littéraux qui en découlent. Ainsi on propose un paradigme quelque peu différent dans lequel la sémantique se définit formellement, et on l'appellera la théorie des mondes.

2) Les types dérivés

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 à cette question, on répondrait une application de `A` vers `B`, 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. »

Dans un ensemble `G`, l'ensemble des applications, défini au sens le plus générale, sera donc `G"→"G`, et l'ensemble les prédicats, défini au sens le plus générale, sera `G"→"{0,1}`. C'est comme cela que l'on construit les types dérivés de `G`. Parcontre `G` et `G"→"G` ne peut être identifié, il découle de ce constat l'existence de nouveaux types dérivés `(G"→"G)"→"G`, `G"→"(G"→"G)` et `(G"→"G)"→"(G"→"G)`, et une infinité d'autres encore.

Qu'en est-il de l'ensemble des applications binaires `A"×"B"→"C``A,B,C` sont des types dérivés de `G` ? Quelle différence y-a-t-il entre une application binaire `f in A"×"B"→"C` et l'application unaire `g in A"→"(B"→"C)` telle que `g(x)(y)"="f(x,y)` ?. On peut identifier ces deux applications. Car `g` définit `f` par un procédé calculable de façon unique et réciproquement `f` définit `g` par un procédé calculable de façon unique. La transformation d'une fonction à plusieurs arguments en une fonction à un argument qui retourne une fonction sur le reste des arguments, s'appelle la curryfication. L'opération inverse s'appelle la décurryfication.

Ainsi on élimine l'opérateur `"×"` au profit de l'unique opérateur de création d'applications `"→"`. L'ensemble des types dérivés de `G` est l'ensemble des compositions closes de cet opérateur et de `G` et de `{0,1}`, ce qui se note `"<"G,{0,1},"→(.,.)>"`.

Remarquez que le type `{0,1}"→"A` `A` est un type dérivé de `G`, est identique au type `A"×"A`, chaque telle application correspondant à un couple d'éléments de `A`. Et remarquez que le type `A"→"{0,1}` est identique au type `ccP(A)`, chaque telle application correspondant à un sous-ensemble de `A`.

3) Groupe

Un groupe `G` est un ensemble muni d'une loi de composition notée par simple juxtaposition, d'un élément neutre noté `1`, d'un opérateur d'inversion 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`.

4) 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 appelés é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... Et les différents types possibles que peuvent prendrent les opérateurs et prédicats de la présentation de la structure sont les types dérivés de `G`.

Remarquez que les prédicats zéro-aires sont de type `{0,1}` et correspondent à des paramètres booléens.

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

L'interprétation de ce langage dans la structure est posée 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`.

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 à son ensemble sous-jacent.

On recourt à la prosopopée, on fait parler les structures, on se place dans la structure `G` ou plus exactement à la place de la structure `G`, et on adopte son point de vue sur elle-même, le point de vue qu'elle peut avoir d'elle-même.

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..

Le langage désigne ainsi des types dérivés de l'ensemble sous-jacent.

La quantification limitée à un ensemble fini `E` se définit de façon exacte comme suit :

`AAx"∈"E, P(x)   <=>  ^^^_(x in E) P(x)`

`EEx"∈"E, P(x)   <=>  vvv_(x in E) P(x)`

Le symbole `^^^` est un itérateur de conjonction, qui déclare une variable locale et qui effectue une conjonction de ce qui suit en faisant varier la variable locale sur tout son domaine de définition. Ainsi par exemple si `E"="{1,2,3}`, nous avons :

`^^^_(x in E) P(x)   <=>   P(1) "et" P(2) "et" P(3)`

Et de même avec le symbole `vvv` qui est un itérateur de disjonction :

`vvv_(x in E) P(x)   <=>   P(1) "ou" P(2) "ou" P(3)`

Ainsi on définit un langage logique propre à la structure, restreint à son ensemble sous-jacent, utilisant les opérateurs et prédicats de sa présentation, et utilisant de nouveaux opérateurs et prédicats quantifiés universellement ou existentiellement. Mais la portée de chaque quantificateur se limite à l'ensemble sous-jacent ou à un de ses types dérivés. Et chacun de ces opérateurs et prédicats n'est définis que sur l'ensemble sous-jacent ou sur un de ses types dérivés.

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 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. Par exemple le langage de la structure de groupe est posé `("∗",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, soit par un suffixe indiquant l'arité pour les types simples ; absence de suffixe pour l'arité nulle, suffixe `"(.)"` pour unaires, suffixe `"(.,.)"` pour binaires, suffixe `"(.,.,.)"` pour ternaire, etc.., ou soit par un exposant indiquant explicitement le type.

Puis on ajoute parfois comme premier argument le nom de l'ensemble sous-jacent.

Souvent on utilisera le symbole `E` pour désigner l'ensemble sous-jacent non instancié. Ainsi le langage de la structures de groupe est posé :

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

ou encore :

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

`E` désigne ici l'ensemble sous-jacent non instancié de la structure. C'est ce sur quoi porte par défaut les quantifications `AA` et `EE` du langage de la structure.

La structure stricto sensu ne nomme pas les opérateurs et prédicats du langage ni son ensemble sous-jacent. La structure est avant tout une théorie, définie à l'aide d'un patron sous forme d'une fonction propositionnelle.

Par exemple le patron de structure de groupe, noté `"Groupe"`, est une fonction propositionnelle définie 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
  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.

L'expression « Etant donné un groupe `(G,"∗",1,frI)` » aura la même signification que la proposition formelle `"Groupe"(G,"∗",1,frI)`. Lorsque les opérateurs et prédicats ou ensemble sous-jacent sont instanciés, la théorie évoquée s'enrichit alors des définitions des pièces rapportées.

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 appliquant le patron sur des symboles non instanciés une première fois mais à titre de modèle. Cela mentionne explicitement 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é, un ensemble d'éléments, c'est ce sur quoi porte les quantificateurs `AA` et `EE` du langage de la structure.

Une proposition écrite dans un langage signifie qu'il appartient à ce langage, et donc on pourra préciser le langage en le mettant en exposant, tel un type :

`( ( 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")") <=>     "Groupe"(E,"∗",1,frI)`

Ainsi nous avons défini un langage logique spécifique `(E, "∗(.,.)",1,frI"(.)")` propre à tous les groupes. On remarque que le langage peut être plus grand que celui utilisé par la proposition mais pas l'inverse. L'expression d'une proposition logique avec son type qui est un langage constitue une structure qui nomme son langage.

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`.

Notez que la variable `G` peut-être vu comme un ensemble, ou plus que cela, comme une structure que le contexte lui attribue, 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` et sa loi d'inversion `frI_G`, mais l'ensemble `G` ne détermine aucune loi ni élément, il ne détermine que lui-même c'est à dire 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.

5) Calculabilité et définissabilité

Le langage d'une structure désigne tout ce que peut dire une structure, et limite donc tout ce qu'elle peut démontrer par elle-même, c'est à dire ce qu'elle peut savoir par elle-même, ou dit autrement, ce qu'elle peut calculer ou définir par elle-même. Cela introduit les notions de calculabilité et de définissabilité, deux notions relatives au langage de la structure et à sa théorie. Un élément est dit calculable par la structure si et seulement si il est désigné par un terme du langage de la structure c'est à dire une composition close d'opérateurs appartenant à la présentation de la structure. Un élément est dit définissable par la structure si et seulement si il existe une démonstration, faite à partir de la théorie de la structure et avec le langage de la structure, de l'existence de cet élément, et il est dit définissable de façon unique, si de plus, la théorie peut démontrer son unicité.

Dans l'exemple d'un groupe `G`, ne possèdant que la théorie du groupe et aucune autre information, on remarquera qu'aucun élément autre que l'élément neutre n'est calculable ni définissable par le groupe `G` lui-même. Cela est facile à comprendre puisque le groupe trivial `{1}` est un exemple de groupe constituant un monde et qui ne contient que cet élément.

6) Monde

Un monde fini est une structure dont l'ensemble sous-jacent est de cardinalité fini, où tous les éléments sont calculables et où la théorie est complète.

Un monde `G` est un groupe s'il possède le langage `(E, "∗(.,.)",1,frI"(.)")` et qu'il vérifie la théorie du groupe. Et toutes les propositions écrites dans le langage `(E, "∗(.,.)",1,frI"(.)")` commun à tous les groupes auront donc une signification spécifique dans `G`. Par exemple considérons la proposition `P` suivante :

`P = (AAxEEy, x"="y"∗"y)^("("E, "∗(.,.)",1,frI"(.))")`

Cette proposition signifie que tous les éléments de la structure de groupe sont des carrés.

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

`G"⊨"P`

Ce symbole `"⊨"` désigne une implication sémantique. Et on l'étend aux propositions écrites dans un même langage logique. Il signifie que tous les mondes qui satisfont `G` satisfont `P`. Et on l'étend également aux ensembles de mondes. Il correspond alors simplement à une inclusion entre ensembles de mondes.

L'implication syntaxique, quant-à elle, est plus compliqué à définir. C'est le lien de démontrabilité par les règles du système de déduction choisie et qui se note :

`G"⊢"P`

Les symboles `"⊨"` et `"⊢"` ne font pas partie du langage logique. C'est en cela qu'ils diffèrent du symbole d'implication `"⇒"` qui, lui, fait partie du langage logique.

7) 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..

Chaque opérateur et prédicat possède un type dérivé de l'ensemble sous-jacent. 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 d'une structure, 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érivé déterminé par la forme syntaxique utilisée, selon un mécanisme d'inférence de type. 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 `((E"→"E)"→"E)->(E"→"E)` est :

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

8) 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 les deux symboles `"et"`, `"ou"` et en négativant leurs arguments, ou bien en inversant les deux symboles `"⇔"`, `"⊕"` et en laissant inchangés leurs arguments, ou bien en remplaçant l'expressions de la forme `A"⇒"B` directement par `A "et" "¬"B`. Cela se définit formellement dans le langage logique utilisant les connecteurs booléens `¬`, `"et"`, `"ou"`, `"⇒"`, `"⇔"`, `"⊕"`. à l'aide de ces 8 règles de substitutions :

`"¬"(AA alpha, beta(alpha))`
=
`EE alpha, "¬"beta(alpha)`
`"¬"(EE alpha, beta(alpha))`
=
`AA alpha, "¬"beta(alpha)`
`"¬"(A "et" B)`
=
`"¬"A "ou" "¬"B`
`"¬"(A "ou" B)`
=
`"¬"A "et" "¬"B`
`"¬"(A"⇔"B)`
=
`A"⊕"B`
`"¬"(A"⊕"B)`
=
`A"⇔"B`
`"¬"(A"⇒"B)`
=
`A "et" "¬"B`
`"¬¬"A`
=
`A`

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` est en `R`-relation avec son image `h(x)`, alors il est 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) )`

Un monde fini est une structure d'ensemble sous-jacent fini où tous les éléments sont calculables et dont la théorie est complète.

Donc pour toute proposition `P` écrite dans le langage d'un monde fini `M`, nous avons toujours `(M"⊨"P)` ou bien `(M"⊨¬"P)`. C'est à dire que la négation de l'expression `M"⊨"P` que l'on note `M"⊭"P` signifie exactement `(M"⊨¬"P)`.

9) Différentes théories de groupe

Nous devons revenir sur la définition du 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é, et nous verrons plus tard encore d'autre façons de définir un groupe.

9.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 `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 munit `G` 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

ou encore :

`"Groupe"(G,"∗")`

Puis une distinction doit s'opérer entre le modèle et le groupe en tant que monde fini. Le modèle est la structure comprenant le langage `(E,"∗")` 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éments est une théorie complète dont le langage est `(e_1,e_2,e_2,...,e_n,"∗")`, et l'ensemble sous-jacent n'est pas mentionné puisqu'il est énuméré en un sac `⟅ e_1,e_2,e_2,...,e_n ⟆`. Le monde ainsi défini a donc une connaissance complète de lui-même, ce qui n'est pas le cas du modèle. Le monde peut calculer tous ses éléments.

La théorie `"Groupe"(G,"∗")` enrichie le langage de la structure `G` avec l'opérateur `1` rendu ainsi définissable par la structure. Mais celui-ci ne fait pas partie du langage de la structure. Il est définissable, et s'avère même définissable de façon unique par la structure, mais il n'est pas calculable par la structure. D'une certaine façon la structure ne le connait pas.

9.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"(.)"`. La théorie précedente est remplacée par :

`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`

Pour interpréter correctement cette théorie, il convient d'étudier l'équivalence de Skolem que nous présentons en deux parties. La première partie s'appelle la spécialisation. Etant donné une fonction propositionnelle quelconque `P"(.,.)"`, nous avons :

Spécialisation
`EE frI"(.)"AAx, P(x,frI(x))`  
`=>`
  `AAx EEi, P(x,i)`

Cette propriété de spécialisation est toujours valide. Elle signifie que si nous avons la preuve qu'il existe une application `frI"(.)"`, même si nous ne sommes pas capable de la calculer, qui satisfait la proposition `AAx, P(x,frI(x))`, alors nous pouvons conclure que pour tout `x` nous avons la preuve qu'il existe un élément `i`, l'élément défini par `i"="frI(x)`, même si nous ne sommes pas capable de le calculer, qui satisfait la proposition `P(x,i)`.

On considère ainsi des éléments définissables mais non calculables. Définissable signifie que la théorie prouve leur existence, tandis que calculable signifie être désigné par au moins un terme clos du langage d'opérateurs.

La seconde partie s'appelle la définition d'application, c'est la réciproque :

Définition
d'application
   `AAx EEi, P(x,i)`  
`=>`
  `EEfrI"(.)"AAx, P(x,frI(x))`   

Cette propriété définissant une application est équivalente à l'axiome du choix. C'est l'affirmation qu'il est possible de procéder à une infinité de choix arbitraires et ainsi de définir une application `frI"(.)"` sur un domaine pouvant être de cardinalité infini.

Mais certaines opinions récusent cet axiome du choix et n'admète à la place qu'un axiome plus faible n'autorisant qu'un nombre fini de choix arbitraires, appelé définition fini d'application :

Définition
fini
d'application
   `((A "est fini"), (AAx"," A(x) => EEi"," P(x,i)),(AAx"," "¬"A(x) => EE!i"," P(x,i)) )`
`=>`
`EEfrI"(.)"AAx, P(x,frI(x))`   

Où l'expression `EE!x` signifie qu'il existe un et un seul élement `x`. Autrement dit :

    `((A" est fini") , (AAx"," A(x) => EEi"," P(x,i)) , (AAx"," "¬"A(x) => EEi"," P(x,i) "et" AAj"," P(x,j)"⇒"(i"="j)) ) => EEfrI"(.)"AAx, P(x,frI(x))`

Mais lorsque l'ensemble sous-jacent est fini, cette distinction n'a plus lieu d'être, puisqu'il n'y a forcement qu'un nombre fini de choix possibles à faire. L'équivalence de Skolem devient assurement valide, et donc cette deuxième définition du groupe devient exactement équivalente à la première. Aussi dans le cas fini, elle est noté pareillement :

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

ou encore :

`"Groupe"(G,"∗")`

La théorie `"Groupe"(G,"∗")` enrichie le langage de la structure `G` avec des opérateurs `1` et `frI"(.)"` rendus ainsi définissables par la structure. Mais ceux-ci ne sont pas dans le langage de la structure et s'avèrent non calculables par la structure. D'une certaine façon la structure ne les connait pas, bien qu'il s'avère qu'il soient définissables de façon unique.

9.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 :

`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 par `frI"(.)"`. Le langage du groupe est ainsi augmenté en `(G, "∗", 1, frI)`. Tout cela se fait implicitement en énonçant simplement :

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

ou encore :

`"Groupe"(G,"∗",1,frI)`

La distinction avec la définition précédente tient dans la calculabilité de `1` et de l'opérateur `frI"(.)"`. L'élément `1` est calculable, alors que dans la définition précédente l'élément `1` n'était que définissable et non calculable. De même, l'opérateur `frI"(.)"` est calculable, alors que dans la définition précédente l'opérateur `frI"(.)"` n'était que définissable et non calculable.

Puis une distinction doit s'opérer entre le modèle et le groupe en tant que monde. Le modèle est la structure comprenant le langage `(G, "∗", 1, frI)` et comprenant la théorie précédente, et il s'applique à tous les groupes. Tandis qu'un monde 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 l'ensemble sous-jacent n'est pas mentionné puisqu'il est énuméré en un sac `⟅ e_1,e_2,e_2,...,e_n ⟆`. Pour le monde fini, tout les objets finis sont calculables, parcontre pour le modèle, sa théorie et son langage sont insuffisant pour tout définir et tout calculer.

II) Structures d'égalité

1) Ensemble

Au sein d'une 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(G)` lorsque `G` est fini, et son cardinal est :

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

2) Relation

De même, au sein d'une structure `G`, 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)}`

3) 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.

4) 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.

5) 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`.

6) 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))`

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

8) 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))`

9) 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 tous les prédicats et opérateurs étant transportés par application parallèle, on en déduit que toutes les propositions qui combinent ces égalités ces prédicats et ces opérateurs 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 langage de structure `(E, bbh^(E"→"E), bbR^(E"×"E"→"{0,1}))`, 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, chaque proposition écrite dans le langage `(E, bbh, bbR)` a une signification spécifique dans chaque structure possédant ce langage.

10) Structure d'égalité

Considérons la structure bidule suivante :

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

Le langage `(E,h,R)` est ainsi choisi pour exprimer les proprités propres au bidule. La théorie `T` de Bidule esprimé dans le langage `(E,h,R)` est :

`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'à un seul type d'éléments.

`T` est une théorie d'égalité car 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 universelle car 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"`

La théorie admet un langage minimum, c'est le plus petit ensemble d'opérateurs et de prédicats qu'elle utilise dans une de ses formes équivalentes. Remarquez alors, que la structure peut posséder un langage plus grand que sa théorie. C'est le cas lorsque la structure est construite à partir d'une autre structure par extension de son langage.

Soit une structure `(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 donc posés définis dans `G`.

Lorsque la proposition `T` est vrai dans la structure `G`, autrement dit lorsque `G⊨T`, cela signifie que `G` est un bidule. Autrement dit :

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

Considérons maintenant le bidule `(G,h,R)`, donc `E_G"="G`, et `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 `K"="f_"∥"(G)`, 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⊨"Bidule"`
`=>       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⊨"Bidule"`
`=>       f_"∥"(G)⊨"Bidule"`
`=>       "Bidule"(f(G),f_"∥"(h),f_"∥"(R))`

Ainsi la propriété `"Bidule"`, 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"⊨""Bidule") => (K"⊨""Bidule")`

`(G"⊨""Bidule") => (f_"∥"(G)"⊨Bidule")`

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

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

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

Ainsi, si la structure `G` satisfait une théorie d'égalité, alors la structure `f_"∥"(G)` satisfera la même théorie d'égalité.

L'application constitue un traducteur transportant les propriétés d'égalités vrais sur la structure `G` en des propriétés d'égalité vrais sur la structure `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 `(E,bbh"(.,.)")`. Remarquez alors que `h` est une instantiation de `bbh`, et que `G` est une intantiation de `E`. Considérons la proposition suivante :

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

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` est une propriété d'égalité du second ordre, car elle quantifie un opérateur `g` opérant sur des éléments. Remarquez que si le langage de la structure comprenait l'opérateur `g` alors la proposition allégée `AAxAAy, g(bbh(x,y)) "=" bbh(y,x)` serait quant-à-elle bien du premier ordre.

La propriété `P`, qui est une propriété d'égalité du second ordre, est transportées par l'application parallèle `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))"=" bbh_(f_"∥"(G))(y,x)`

On note le type des opérateurs en exposant, ainsi par exemples, `x^G` désigne un élément 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)`.

Autre exemple du premier ordre. Plaçons nous dans le groupe `(G,"∗",1,frI)` et considérons une application `f`. La théorie du groupe est une proposition d'égalité, donc la structure image `(f(G), f_"∥"("∗"),f(1),f_"∥"(frI))` 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.

III) Langage logique du premier ordre

Un langage logique du premier ordre se définit en présentant une liste d'opérateurs et de prédicats non instanciés. 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..

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`. Les termes du langage d'opérateurs sont les compositions closes d'opérateurs. Ils forment le domaine de Herbrand qui désigne tous les éléments calculablesL On le note entre crochet :

`"<"a, f"(.)", g"(.,.)">" `

La récurrence est consubstentielle à la notion de structure. C'est pourquoi on commence par définir ce qu'est la récurrence générale :

On dit qu'un élément `x` respecte une proposition `P`, si et seulement si `P(x)` est vrai. On dit qu'un opérateur respecte une proposition `P` si et seulement si, appliqué qu'à des éléments respectant `P`, il produit un élément respectant `P`.

Etant donné un ensemble `L` d'opérateurs et d'éléments respectants `P`, la clôture par composition close notée `"<"L">"` ou `L"°"` est un ensemble d'éléments respectant `P`.

 

 

 

---- 14 décembre 2019 ----

 

On définit une opération

 

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.

---- 8 novembre 2014 ----

 

 

Dans notre conception des structures, on considère un ensemble suffisament grand pour contenir tous les éléments et qui est appelé l'ensemble sous-jacent, et un langage limité à cet ensemble comprenant des opérateurs et prédicats de types dérivé de l'ensemble sous-jacent. Puis on utilise un patron de structure qui complète la structure avec une théorie écrite dans le langage de la structure. Quand la théorie et vide, le patron s'appelle `"Structure"` et définit simplement un langage.

`"Structure"(G,h"(.)",R"(.,.)")`

Cette expression définie dans le contexte, la structure `G`, composée d'un ensemble sous-jacent `G` et d'un opérateur unaire inconnu `h` et d'un préficat binaire inconnu `R`. En d'autres termes, on pose comme hypothèse l'existence de `h` et de `R` indépendanment de tout paramètre autre que `G`. Une hypothèse qui est assurement vrai. Et cela s'écrit comme suit :

`EE h"∈"G"→"G, EER"∈"G"×"G"→"{0,1}`

Cettte assertion déclare un langage appliqué à `G`, et qui peut être rendu indépendant de `G` en extirpant cette dépendance :

`(EE h"(.)", EER"(.,.)" )^G`

Considérons maintenant le patron `"Bidule"` de langage `("E", bbh, bbR)` et de théorie :

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

C'est à dire explicitement

`EE h"∈"G"→" G, EER"∈"G"×"G"→"{0,1}, AAx"∈"G, x"="h(x) "ou" R(x,x)`

`(EE h"(.)", EER"(.,.)", AAx, x"="h(x) "ou" R(x,x))^G`

`(AAx, x"="h(x) "ou" R(x,x))^("("G, h"(.)",R"(.,.))")`

Le patron `"Bidule"` désigne sa théorie sous forme d'une fonction propositionnelle :

`"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`, que la restriction `R"|"_G` est un prédicat binaire dans `G`, et que cela forme un bidule c'est à dire telle que la théorie en question soit 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, tout en nommant de façon classique la structure par `G`.

É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` qui constitue la structure `(f(G),h,R)` ou notée simplement `f(G)`. Et on peut appliquer `f` aux éléments de `G`, et appliqué `f` de façon parallèle 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` qui constitue la structure `(f(G),f_"∥"(h),f_"∥"(R))` ou notée simplement `f_"∥"(G)`.

On peut aussi considérer une structure `K` que l'on déclare comme suit : `"Structure"(K,f(h),f(R))` et pour la quelle l'ensemble sous-jacent `K=f(G)`, alors la struture `K` devient l'image parallèle de la structure `G` par `f`, ce qui se note `K"="f_"∥"(G)`.

 

 

 

 

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.

 

et le prédicat d'égalité `"="` qui joue un rôle particulier exposé plus loin.

 

 

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 ----

 

 

 

 

---- 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 3

 


Dominique Mabboux-Stromberg