Précédent
 
De l'algèbre
et du dénombrement
(5ème partie)

1) Relation ternaire

Une relation ternaire `R` est un ensemble de triplets d'éléments. Une relation `R` de `A` vers `B` puis `C` est un sous-ensemble de `A×B×C`. L'ensemble des relations ternaires de `A` vers `B` puis `C` se note en trisymboles par `A_×B_×C_×` Le nombre de relations distinctes de `A` vers `B` puis `C`, est donc égal à :

`|A_×B_×C_×`|=|ccP(A×B×C)|=2^(|A| |B| |C|)`

Le nombre de relations ternaires opérant sur un ensemble de `n` éléments est égal à `2^(n^3)`

L'appellation des attributs change quelque peu lorsque la relation possède une arité superieure à `2`. On ne parle plus d'ensembles de départ et d'arrivé de `R` mais d'ensembles arguments numérotés de `R` :

Projections des supports :

`Arg_1(R)=A`
`Arg_2(R)=B`
`Arg_3(R)=C`
`Arg_(1,2)(R)=A×B`
`Arg_(1,3)(R)=A×C`
`Arg_(2,3)(R)=B×C`
`Arg_(1,2,3)(R)=A×B×C`

Projections des bases :

`Base_1(R) = {x "/" EEyEEz, (x,y,z) "∈" R}`
`Base_2(R) = {y "/" EExEEz, (x,y,z) "∈" R}`
`Base_3(R) = {z "/" EExEEy, (x,y,z) "∈" R}`
`Base_(1,2)(R) = {(x,y) "/" EEz, (x,y,z) "∈" R}`
`Base_(1,3)(R) = {(x,z) "/" EEy, (x,y,z) "∈" R}`
`Base_(2,3)(R) = {(y,z) "/" EEx, (x,y,z) "∈" R}`
`Base_(1,2,3)(R) = R`

Projections des relations d'arité 2 :

`(x,y) "∈" R_(1,2) <=> EEz, (x,y,z) "∈" R`
`(x,z) "∈" R_(1,3) <=> EEy, (x,y,z) "∈" R`
`(y,z) "∈" R_(2,3) <=> EEx, (x,y,z) "∈" R`

Projections signées des bases :

`Base"0--"(R) = {x "/" EEyEEz, (x,y,z) "∈" R}`
`Base"0+-"(R) = {x "/" AAyEEz, (x,y,z) "∈" R}`
`Base"0-+"(R) = {x "/" EEyAAz, (x,y,z) "∈" R}`
`Base"0++"(R) = {x "/" AAyAAz, (x,y,z) "∈" R}`

`Base"-0-"(R) = {y "/" EExEEz, (x,y,z) "∈" R}`
`Base"+0-"(R) = {y "/" AAxEEz, (x,y,z) "∈" R}`
`Base"-0+"(R) = {y "/" EExAAz, (x,y,z) "∈" R}`
`Base"+0+"(R) = {y "/" AAxAAz, (x,y,z) "∈" R}`

`Base"--0"(R) = {z "/" EExEEy, (x,y,z) "∈" R}`
`Base"+-0"(R) = {z "/" AAxEEy, (x,y,z) "∈" R}`
`Base"-+0"(R) = {z "/" EExAAy, (x,y,z) "∈" R}`
`Base"++0"(R) = {z "/" AAxAAy, (x,y,z) "∈" R}`

Projections signées des relations d'arité 2 :

`(x,y) "∈" R"00-" <=> EEz, (x,y,z) "∈" R`
`(x,y) "∈" R"00+" <=> AAz, (x,y,z) "∈" R`
`(x,z) "∈" R"0-0" <=> EEy, (x,y,z) "∈" R`
`(x,z) "∈" R"0+0" <=> AAy, (x,y,z) "∈" R`
`(y,z) "∈" R"-00" <=> EEx, (x,y,z) "∈" R`
`(y,z) "∈" R"+00" <=> AAx, (x,y,z) "∈" R`

 

 

 

 

 

Symbole
Description
`"×"` Relation
Aucune contrainte
`"<"` Transformation Chaque élément de l'ensemble possède un ou plusieurs hyper-arcs.
`":"` Fonction Chaque élément de l'ensemble possède zero ou un seul hyper-arc.
`"="` Application Chaque élément de l'ensemble possède exactement un hyper-arc.

 

 

6) Magma

Un magma `G` est ensemble muni d'une opération binaire interne, c'est à dire une application de `G×G->G`, que l'on appelle produit, et qui se note, par défaut, par absence de symbole. Prenons trois éléments `x,y,z` de `G`, le produit n'étant pas apriori associatif, il est nécessaire de préciser dans tout produit d'au moins trois éléments, l'ordre d'évaluation des opérations de produit à l'aide de parenthèses. Ainsi il ne peut y avoir de produit de plus de 2 éléments sans que ceux-ci ne soient entourés de parenthèses, par exemples `(xy)z, x(yz)`.

Si on veut désigner explicitement l'opération de produit on pourra utiliser le symbole `**_G` indicé par le nom de la structure.

`xy = x**_Gy`

D'un point de vue élémentarien, le magma peut être monogène, bigène, trigène..., `n`-gène... ou `oo`-gène. Sont ainsi exclus les types infinis autre que `oo = card(NN)`. Par exemple, la définition programmative d'un magma bigène est :

`G = `Magma bigène `(**,a,b)`

Cette définition programmative précise le symbole de l'opération de produit ainsi que le premier et le second générateur dans cet ordre précis.

`G` est engendré par les deux éléments `a` et `b` ce qui se note par `G = "<"a,b,**">"`.

Cette approche constructive est plus parlante. Elle permet de définir les sous-magmas de façon constructive. Un sous-magma est un magma engendré par des éléments de `G` ou une suite calculable d'éléments de `G`. Par exemples voici trois sous-magmas : `"<"a,**">", "<"b,**">", "<"ab,b,**">"`.

Etant donnée deux magmas `G` et `H`. Une application `f` de `G->H` respecte le produit si et seulement si pour tout élément `x, y` nous avons `f(xy)=f(x)f(y)`. On dira alors que `f` est un morphisme, sous-entendu un morphisme de magma. Et `f` conservera ainsi la forme du magma, mais cette forme peut être quand même dégénérée comme dans le cas d'une projection. Pour que la forme intégrale soit conservée, il faut une propriété supplémentaire qu'est l'injection. Auquel cas `f` est un plongement de `G` dans `H`, sous entendu un plongement de magma, et l'image de `G` par `f` que l'on note `f(G)` est isomorphe à `G`, autrement dit `f` constitue un isomorphisme entre `G` et `f(G)`, sous-entendu un isomorphisme de magma.

magma `G`
magma `H`
`f in (G->H)`
`AA(x,y) in G^2`

`f` est un plongement
donc `G ~= f(G)`
`f` est un morphisme
`f(xy)=f(x)f(y)`
`f` est injectif
`f(x)=f(y)   =>   x=y`

On entend par image de `G`, à défaut d'autre indication, l'image d'un morphisme de `G`, c'est à dire l'image de `G` par une application qui respecte la forme du magma c'est à dire qui respecte le produit.

Le nombre de magmas qu'il est possible de définir sur un ensemble `G` est égal à :

`|G×G->G| = |G|^("("|G|^2")")`

C'est à dire que sur un ensemble de `n` éléments il est possibles de définir `n^("("n^2")")` magma différents.

 

---- 19 avril 2016 ----

 

1-4) Semigroupe

Un semigroupe `G` est un magma possédant la propriété d'associativité :

`AA (x,y,z) in G^3,  (xy)z = x(yz)`

Délors les parenthèses peuvent être enlevées dans tous les produits. Par exemple prenons quatre éléments `x,y,z,t` de `G`, le produit `xyzt` est définie sans ambiguité. Car le produit est associatif. Seul compte l'ordre `x,y,z,t` dans la liste du produit.

Il devient perspicace de définir les puissances entières. Quelque soit un entier `n` non nul, la puissance `n` de `x` se note `x^n` et est définie comme suit :

`x^1 = x`
`x^2 =xx`
`x^3 = xxx`

`x^n = xxx...(n fois)...`

Tout semigroupe est isomorphe à un sous-semigroupe d'applications. Cette propriété se démontre simplement en faisant opérer le semi-groupe sur lui-même par translation gauche. Étant donné un semigroupe G, on définie le morphisme f de `G->(G->G)` comme suit : `x|->(u|->xu)`. Délors il est facile de montrer que `f` respecte le produit

`f(xy) = (u|->xyu) = (u|->xu)°(u|->yu) = f(x)f(y)`

et que `f` est injectif : x!=y => (u|->xu) = (u|->yu)

=>

 

Tout groupe fini `G` est isomorphe à un sous-groupe de permutations.

On entend par image de `G`, à défaut d'autre indication, l'image d'un morphisme de `G`, c'est à dire qui respecte la forme du groupe (l'identité, l'inverse et le produit).

Pour tout ensemble `E` de cardinalité égale ou supérieur à celle de `G`, le groupe `G` est isomorphe à au moins un groupe d'applications de `E->E`, de la même façon qu'il peut agir sur lui-même par translation gauche ou droite.

On appelle l'isomorphisme construisant d'un tel groupe d'applications, une action fidèle de `G` sur `E`. Le groupe `G` opère ou agit sur `E` par son intermède. Tout élément `x` de `G` opère ou agit sur E comme une application E->E qui est l'image de `x` par le choix de l'action qui est ici un isomorphisme.

Si on ne choisie qu'un morphisme, c'est à dire non nécessairement injectif, pour construire un tel groupe d'applications de `E -> E`. Alors on appelle le choix de ce morphisme une action de `G` sur `E`.

On entend par groupe d'applications, un ensemble d'applications de `E->E` muni de la loi de composition d'applications. Or il existe deux lois de composition, une gauche et une droite. Il y a en effet deux façons de composer les applications unaires, soit avec l'opération de composition à l'anglaise, dite gauche, notée `@`, et qui s'écrit de droite à gauche, soit avec l'opération de composition à la française, dite droite, notée `*` ou notée par absence de symbole, et qui s'écrit de gauche à droite. L'ordre des arguments est inversé dans l'une des opérations de composition par rapport à l'autre.

Considérons deux applications quelconques `f` et `g` de `E->E` et un élément quelconque `x` de `E`. Nous avons par définition :

`(g@f)(x) = g(f(x))`
`(fg)(x) = g(f(x))`

Et donc nous avons :

`fg=g@f`

L'appel de `f` sur `x` se note également de deux façons, soit à l'anglaise, dite gauche, par `f(x)`, soit à la française, dite droite, par `x^f`. Ainsi nous avons `f(g(x))=(x^f)^g`.

À l'anglaise
(à gauche)
À la française
(à droite)
`(g@f)(x) = g(f(x))`
`x^(fg) = (x^f)^g`

Cela signifie qu'il existe une symétrie dans le monde des applications unaires qui détermine le sens de l'écriture de la composition d'applications, de gauche à droite ou de droite à gauche. On parlera de composition d'applications droite, à la française, qui s'écrit de gauche à droite. Et on parlera de composition d'applications gauche, à l'anglaise, qui s'écrit de droite à gauche.

2) Groupe `bbbsigma_3`

Considérons par exemple le plus petit groupe non commutatif qui est `bbbsigma_3`, le groupe des permutations de 3 éléments. C'est l'ensemble des bijections de `{1,2,3}->{1,2,3}`.

On note une permutation par sa décomposition en cycles et en choisissant toujours, à permutation circulaire près, les représentants les plus petits selon l'ordre lexicographique. Ainsi la permutation `(1,3,2)` est l'application `f` vérifiant `f(1)"="3`, `f(3)"="2`, `f(2)"="1`. La permutation notée `( )` correspond à l'application identité.

`bbbsigma_3 = {(), (1,2),(1,3),(2,3),(1,2,3),(1,3,2)}`

Cet ensemble `bbbsigma_3` est engendré par deux éléments `(1,2)`, `(1,3)` et par une opération de composition qui peut être `@` ou `*` et qui donne donc naissance à deux groupes. Remarquez que :

`(1,2)(1,3) = (1,2,3)`
`(1,2)@(1,3) = (1,3,2)`

En choississant comme générateurs les deux permutations `(1,2)`, `(1,3)` dans cet ordre précis, on munie le groupe d'une orientation qu'est la base génératrice `"("(1,2)`, `(1,3)")"`. Et selon que l'on munie de la composition `@` ou de la composition `*` cela crée deux groupes bigènes qui sont en notation programmative :

Groupe bigène `((1,2), (1,3), *)`
Groupe bigène `((1,2), (1,3), @)`

Le passage à l'inverse `x |-> x^(-1)` constitue l'isomorphisme canonique reliant ces deux groupes car :

`(xy)^(-1) = y^(-1)x^(-1)`
`(x@y)^(-1) = y^(-1)@x^(-1)`

Remarquez que pour cet exemple, l'isomorphisme de groupe est davantage que cela, c'est un isomorphisme de groupe bigène car les générateurs sont également images `(1,2)^(-1)=(1,2)` et `(1,3)^(-1)=(1,3)`.

`(1,2)|->(1,2)`
`(1,3)|->(1,3)`
`(1,2)(1,3) |-> (1,2)@(1,3)`
`(1,2,3)|->(1,3,2)`

3) Action

Etant donné un groupe fini `G`, et un ensemble fini `E`. L'opération interne du groupe `G` est notée par l'absence de symbole. L'opération mixte du groupe `G` sur l'ensemble `E` est également notées par l'absence de symbole. Et il n'y a pas d'ambiguité car c'est l'élément de `G` qui joue le rôle de l'application et qui s'applique à un élément de `E`. Aussi, étant donnée un élément `g in G` et un élément `e in E`, l'expression `g\e` ou `eg` signifie la même chose, l'appel de l'application `g` appliqué à `e`. Cette distinction est reservée pour spécifier laquelle des opérations de composition d'applications, gauche ou droite, est utilisée dans cette action.

L'appel d'une application `f` sur un élément `x` se note de deux façons, soit à l'anglaise, à gauche, par `f(x)`, soit à la française, à droite, par `x^f`. Et si elle est intégrée en une opération mixte sans symbole, elle se note alors `fx` si on utilise la composition gauche, et `xf` si on utilise la composition droite pour former le groupe d'application image de `G`. On entend par image de `G`, à défaut d'autre indication, l'image d'un morphisme de `G`, c'est à dire qui respecte la forme du groupe (l'identité, l'inverse et le produit).

On dit que `G` opère (ou agit) à gauche sur `E` s'il existe une opération de `G×E -> E` telle que :

`AA(x,y) in G^2, AAe in E,  x(ye) = (xy)e`

Un acte gauche de `G` sur `E` est une application de `E -> E` de la forme `e|->g\e``g` est un élément de `G`. Cet acte gauche est désigné par `g`. Les actes gauches se composent par défaut à l'anglaise. Le groupe des actes gauches de `G` sur `E` est munie de la composition d'applications gauche à l'anglaise notée par `@`. Cette propriété traduit simplement le morphisme entre `G` et le groupe des actes gauches. Grace à cette propriété, il n'est pas nécessaire de mettre des parenthèses dans l'expression `xye`.

On dit que `G` opère (ou agit) à doite sur `E` s'il existe une opération de `E×G -> E` telle que :

`AA(x,y) in G^2, AAe in E,  (ex)y = e(xy)`

Un acte droit de `G` sur `E` est une application de `E -> E` de la forme `e|->eg``g` est un élément de `G`. Cet acte droit est désigné par `g`. Les actes droits se composent par défaut à la française. Le groupe des actes doits de `G` sur `E` est munie de la composition d'applications droite à la française notée par `*` ou par l'absence de symbole. Cette propriété traduit simplement le morphisme entre `G` et le groupe des actes droits. Grace à cette propriété, il n'est pas nécessaire de mettre des parenthèses dans l'expression `exy`.

Cet opération `G×E -> E` ou `E×G -> E` est appellée une action du groupe `G` sur l'ensemble `E`, et plus précisement une action gauche ou une action droite. On dit que `G` opère (ou agit) sur l'ensemble `E`. On dit qu'il opère (ou agit) à gauche sur `E` ou à droite sur `E`.

L'action gauche est le morphisme créant (à partir de `G`) les actes gauches :

`x in G,  e in E`
`(x |-> (e|->xe))`

`1 |-> id`
`x |-> (e|->xe)`
`x^(-1) |-> (e|->xe)^(-1)`
`x^(-1) |-> (e|->x^(-1)e)`
`y |-> (e|->ye)`
`xy|->(e|->xe)@(e|->ye)`
`xy|->(e->xye)`

L'action droite est le morphisme créant (à partir de `G`) les actes droits :

`x in G,  e in E`
`(x |-> (e|->ex))`

`1 |-> id`
`x |-> (e|->ex)`
`x^(-1) |-> (e|->ex)^(-1)`
`x^(-1) |-> (e|->ex^(-1))`
`y |-> (e|->ex)`
`xy|->(e|->ex)(e|->ey)`
`xy|->(e->exy)`

4) Orbite, stabilisateur et points fixes

Etant donnée une action gauche de `G` sur `E` et un élément quelconque `e in E`.

L'orbite de `e` est l'ensemble de tous les éléments atteignable à partir de `e` en lui appliquant un acte. Autrement dit l'orbite de `e` est le produit `Ge`.

`Ge = {xe "/" x in G}`

Les orbites forment une partition de `E`.

Le stabilisateur de `e` noté `S(e)` est le sous-groupe de `G` qui regroupe tous les éléments laissant invariant `e`.

`S(e) = {x "/" x in G, xe=e}`

Les stabilisateurs de deux éléments d'une même orbite, `e` et `xe`, sont conjugués comme suit :

`S(xe) = xS(e)x^(-1)`

Il sont donc isomorphes et donc équipotents.

L'ensemble des points fixes d'une application `x in G` se note `F(x)`. La définition s'écrit :

`F(x) = {e "/" e in E, xe=e}`

La formule des classes : l'application `xS(e) |-> xe` établit une bijection `G"/"S(e)->Ge`. Et donc le cardinal de l'orbite de `x` et égal au cardinal de `G` divisé par le cardinal du stabilisateur de `x`.

`|Gx| = |G|/|S(x)|`

Si on désigne par `O` l'ensemble des orbites. Les orbites formant une partition de `E`, nous avons :

`|E| = sum_(o in O)|o|`

Et si on désigne par `S_o` le cardinal commun des stabilisateurs des éléments de l'orbite `o`, nous avons :

`|E| = |G|sum_(o in O)1/S_o`

La formule de Burnside affirme que :

`|O| = 1/(|G|) sum_(x in G) |F(x)|`

 

 

Dénombrement des arbres, des graphes (multi-ensemble)

Tout groupe est le groupe d'automorphisme d'un graphe

 

 

 

Langage régulier (succession, réunion, intercection)

 

 

1) Relation ternaire

Une relation ternaire `R` est un ensemble de triplets d'éléments.

Une relation ternaire `R`, quelque fois notée avec le suffixe `"(.,.,.)"` pour spécifier son arité `R"(.,.,.)"`, correspond à plusieurs fonctions multi-aire étendues aux ensembles comme suit :

Expression
Fonction étendue aux ensembles
Appel fonctionnelle
Appel fonctionnelle
`R(x,y,".")`
`A×B⇢C`
`R_(110)(x,y)`
`R_(001)^(-1)(x,y)`
`R(x,".",y)`
`A×C⇢B`
`R_(101)(x,y)`
`R_(010)^(-1)(x,y)`
`R(".",x,y)`
`B×C⇢A`
`R_(001)(x,y)`
`R_(100)^(-1)(x,y)`
`R(x,".",".")`
`A⇢B×C `
`R_(100)(x)`
`R_(011)^(-1)(x)`
`R(".",x,".")`
`B⇢A×C `
`R_(010)(x)`
`R_(101)^(-1)(x)`
`R(".",".",x)`
`C⇢A×B `
`R_(001)(x)`
`R_(110)^(-1)(x)`

Une relation ternaire `R` de `A` vers `B` vers `C` dans cet ordre, est un sous-ensemble de `A×B×C`. Le nombre de relations distinctes de `A` vers `B` vers `C`, est donc égal à :

`|ccP(A×B×C)|=2^(|A| |B| |C|)`

Le nombre de relations ternaires opérant sur un ensemble de `n` éléments est égal à `2^(n^3)`

Pour une relation binaire de `A` vers `B` nous avons :

Expression
Fonction étendue aux ensembles
Appel fonctionnelle
`R(x,".")`
`A⇢B`
`R(x)`
`R(".",x)`
`B⇢A`
`R^(-1)(x)`