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|`
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 une 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 franchit exactement une arête de `R` dans le sens autorisé :
`R(A) = {y "/"EEx, x"∈"A "et" (x"↦"y)"∈"R}`
`R(A) = {y "/"EEx, A(x) "et" R(x,y)}`
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é 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.
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 fonctionnelle : `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.
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 fonctionnelle » 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)` où `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`.
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)` dans laquelle les égalités connues dans la struture `G` sont transportées par l'application `f` en des égalités dans la structure `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)`
Où `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))`
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)`
Où `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` où `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))`
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 fonctionnelle 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)`
Où `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))`
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) => (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'` 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.
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 propriété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` dans sa forme prénexe.
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.