Le langage d'opérateurs met en avant deux notions clefs que sont la liberté des éléments et l'égalité des éléments, et permet de définir une troisième notion tout aussi importante que chacune des premières, qu'est l'indépendance des éléments.
De nombreuses structures du premier ordre peuvent se décrire d'une manière générale comme un ensemble d'éléments d'un seul type, où les éléments s'appliquent sur eux-mêmes. Un élément `a` aura alors deux notations, une notation en tant qu'élément `a`, et une notation en tant qu'application `a(".")`. Un élément s'applique sur un élément pour produire un élément. Il est considéré comme une application définie dans l'ensemble sous-jacent, ou plus exactement, on lui donne ce second rôle, d'application dans l'ensemble sous-jacent, car deux éléments distincts peuvent avoir un même second rôle et désigner la même application.
Une structure `E` comprend des éléments qui vont avoir comme second rôle, un rôle d'application de `E"→"E`. Autrement dit, il existe une application `varphi` de `E"→"(E"→"E)`, qui appliquée à un élément, produit son second rôle. Et par soucis de simplification d'écriture, on note directement :
`a(b)=varphi(a)(b)`
On constate que la connaissances de toutes ces applications se ramène à l'unique connaissance de l'application `varphi` qui, par décurryfication, correspond à la loi de composition binaire interne de la structure.
`varphi(a)(b) = varphi(a,b) = a"∗"b`
Un ensemble munie d'une loi de composition interne `"∗"` s'appelle un magma. Et pour tout couple d'élément `(a,b)`, l'application de l'élément `a` sur l'élément `b` noté `a(b)` est égale au produit `a"∗"b`.
`a(b) = a"∗"b`
En résumé, un magma est un ensemble d'éléments où chaque élément à un second rôle, le rôle d'une application dans le magma. Et les deux notations, loi interne `"∗"` ou composition entre élément, sont valables et désignent la même chose.
Considérons par exemple deux éléments `f,g` appartenant à un magma `E`. La clôture par composition de l'ensemble de ces deux éléments `{f,g}` se note en les plaçant entre crochets `"<"f,g">"` ou `"<"{f,g}">"`. C'est l'ensemble de tous les éléments engendrés par `{f,g}`. C'est à dire toutes les compositions finies possibles.
`"<"f,g">" = {f, g, f(f), f(g), g(f), g(g), ..., f(f(f)), f(f)(f), ....}`
`"<"f,g">" = {f, g, f"∗"f, f"∗"g, g"∗"f, g"∗"g, ...,f"∗"(f"∗"f), (f"∗"f)"∗"f, ....}`
Les crochets `"<"....">"` entourant des éléments ou ensembles d'éléments désignent la cloture par composition de ces éléments. Étant donné un ensemble `A` inclus dans `E`, la clôture par composition de `A` se note `"<"A">"` et regroupe tous les éléments engendrés par `A` tandis que son complémentaire `E"-""<"A">"` regroupe tous les éléments non engendrés par `A`.
`"<"A">"` constitue un sous-magma de `E`. Un magma `K` est un sous-magma de `E` si et seulement s'il est inclus dans `E` et que sa loi de composition est égale à celle de `E` restreinte à `K`, et cela se note `K"⊑"E`. Ainsi, l'ensemble des sous-magma de `E` se note `{K "/" K"⊑"E}`. Les sous-magma sont les clôtures par composition des sous-ensembles, ce qui se note par :
`{K "/" K"⊑"E} = {"<"A">" "/" A"⊆"E}`
`"<"A">"` est l'unique plus petit sous-magma de `E` contenant `A` :
`"<"A">" = "@min" {K "/" A"⊆"K"⊑"E}`
L'opérateur `"min"` appliqué à une famille d'ensembles, retourne la sous-famille des ensembles minimaux par inclusion. L'arobase est utilisé pour convertir un ensemble en son contenu.
---- 17 janvier 2021 ----
Dans un magma `E`, nous définissons une nouvelle notion d'indépendance. Mais cette notion d'indépendance n'est pas linéaire et ne correspond donc pas à celle d'un matroïde. C'est une notion d'indépendance magmatique.
On considère que des éléments sont indépendants entre eux, et donc forme un indépendant, si le sous-magma qu'ils engendrent ne peut pas être engendrée en en retirant un. Chaque élément doit apporter une contribution nécessaire. Autrement-dit, un ensemble `A` d'éléments est dit indépendant si et seulement si aucun de ses éléments n'est engendré par les autres. Car sinon on remarque que l'on pourrait enlever cet élément `x` qui est engendré par les autres, sans que cela ne change le sous-magma engendrée :
`x "∈<"A"-"{x}">" <=> "<"A">=<"A"-"{x}">"`
Etant donné un magma `E`. L'ensemble des parties de `E` se note `ccP(E)`. On appelle une famille ou famille d'ensembles, un ensemble d'ensembles. Et on appelle membre d'une famille, les ensembles qui appartiennent à la famille en question. Les ensembles considérés sont les parties de `E`. Les familles considérées sont les parties de `ccP(E)`. L'ensemble de toutes les familles est `ccP(ccP(E))`.
La notion d'indépendance magmatique définit 4 familles que sont les générateurs, les dépendants, les indépendants et les bases :
La famille des générateurs, `bbbG`, est définie comme suit : Un générateur est un ensemble qui engendre le magma `E` par clôture par composition :
`bbbG = {A"⊆"E "/" "<"A">=" E}`
La famille des dépendants, `bbb"D"`, est définie comme suit : Un dépendant est un ensemble qui possède un élément qui est engendré par les autres :
`bbb"D" = {A"⊆"E "/" EEx "∈" A, x "∈<"A"-"{x}">"}`
La famille des indépendants, `bbb"I"`, est définie comme suit : Un indépendant est un ensemble dont aucun élément n'est engendré par les autres :
`bbb"I" = {A"⊆"E "/" AAx "∈" A, x"∉<"A"-"{x}">"}`
La familles des bases se note `bbb"B"`, est définie comme suit : Une base est un ensemble qui est à la fois un générateur et un indépendant :
`bbbB = bbbI nn bbbG`
Récapitulatif :
Et on remarque que :
On dit qu'un élément `e` est dépendant d'un ensemble `A`, ce qui se note `e"←"A`, si et seulement si `e` appartient à `A` ou bien `A+{e}` constitue un ensemble dépendant. Autrement dit, `e"←"A` si et seulement si `e` est engendré par `A` ou s'il peut se substituer à un élément de `A` pour former un ensemble engendrant `A`, c'est à dire s'il existe un élément `a` de `A` qui est engendré par `A-{a}+{e}`. Ainsi, la relation de dépendance magmatique `x"←"A` se définit comme suit :
`x"←"A <=> x"∈<"A">" "ou" EEa "∈" A, a "∈<"A"-"{a}"+"{x}">"`
Et par négation, on dit qu'un élément `e` est indépendant d'un ensemble `A`, ce qui se note `e"↚"A`, si et seulement si `e` n'appartient pas à `A` et que `A+{e}` constitue un ensemble indépendant. Autrement dit, `e"↚"A` si et seulement si `e` n'est pas engendré par `A` et qu'aucun élément `a` de `A` n'est engendré par `A-{a}+{e}`. Ainsi, la relation d'indépendance magmatique `x"↚"A` se définit comme suit :
`x"↚"A <=> x"∉<"A">" "et" AAa"∈" A, a "∉<"A"-"{a}"+"{x}">"`
On rermarque que la relation de dépendance `x"←"A` est une relation plus large que la relation d'engendrement `x"∈<"A">"`, et que la relation d'indépendance `x"↚"A` est une relation plus fine que la relation de non engendrement `x"∉<"A">"` :
`x"∈<"A">" => x"←"A`
`x"↚"A => x"∉<"A">"`
Le matroïde est une structure, introduite par H. Whitney en 1935, qui généralise la relation de d'indépendance linéaire en ne retenant que ses propriétés ensemblistes, à savoir, les 3 propriétés suivantes définissant la famille des indépendants :
Le matroïde est défini par un couple `(E,sf"Indépendants" bbbI)`. Il comprend un ensemble sous-jacent `E`, et une famille d'ensembles `bbbI"∈"ccP(ccP(E))` qui regroupe tous les indépendants. La structure `(E,sf"Indépendants" bbbI)` est un matroïde si et seulement si elle vérifie :
| (1) L'ensemble vide est un indépendant : | `Ø "∈" bbbI` |
| (2) `bbbI` est clos par inclusion : | `AAX "∈" bbbI, AAY"/"Y"⊆"X, Y"∈" bbbI` |
| (3) `bbbI` permet l'agrandissement : | `AAX "∈" bbbI, AAY "∈" bbbI"/"|X|">"|Y|,EEe "∈" X"\"Y, Y"+"{e}"∈"bbbI` |
Dans ces expressions, les variables en majuscules désignent des sous-ensemble de `E`, tandis que les variables en minuscule désigne des éléments de `E`. Ainsi l'expression `AA X` signifie quelque soit un ensemble `X` appartenant à `ccP(E)`, et l'expression `EE e` signifie qu'il existe un élément `e` appartenant à `E`. Ainsi, les variables majuscules `X` et `Y` désignent des parties de `E` et la variable minuscule `e` désigne un élément de `E`.
Dans le matroïde `E`, la relation de d'indépendance entre un élément `x` et un ensemble `A`, notée `x"↚"A`, se définit comme suit : `x"↚"A` si et seulement si `x` n'appartient pas à `A` et `A"+"{x}` est un ensemble indépendant dans le matroïde `E` :
`x"↚"A <=> x"∉"A "et" (A"+"{x})"∈"bbbI`
Et par négation, la relation de dépendance entre un élément `x` et un ensemble `A`, notée `x"↚"A`, se définit comme suit :
`x"←"A <=> x"∈"A "ou" (A"+"{x})"∈"bbbD`
Considérons un matroïde `E`. On définie la famille des générateurs du matroïde, notée `bbbG`, comme suit : Un générateur est un ensemble ayant la dimension maximal.
`bbbG = {A "/" "dim"(A)"=dim"(E)}`
Et nous avons les propriétée suivantes :
Dans un magma quelconque `E`, la relation de dépendance induite par le magma, appelé dépendance magmatique, ne correspond pas en générale à une relation de dépendance linéaire c'est à dire définissable par un matroïde.
Formalisons la propriété que doit satisfaire un magma pour que sa relation de dépendance magmatique soit une relation de dépendance linéaire.
---- 16 janvier 2021 ----
Le magma `E` est dit d'engendrement linéaire si et seulement si la relation de dépendance magmatique coïncide avec la relation d'engendrement :
`AAx, AAA,`
`x"←"A <=> x"∈<"A">" "ou" EEa "∈" A, a "∈<"A"-"{a}"+"{x}">"`
`x"←"A <=> x"∈<"A">"`(relation de dépendance magmatique)
(relation d'engendrement)
C'est à dire si et seulement si :
`AAx, AAA,(EEa "∈" A, a "∈<"A"-"{a}"+"{x}">") =>x"∈<"A">"`
On en conclut que le magma `E` est d'engendrement linéaire si et seulement si dans tout ensemble dépendant c'est à dire où il existe un élément engendré par les autres, chaque élément est engendré par les autres :
`AA A, (EEx"∈"A, x"∈<"A"-"{x}">") => (AAx"∈"A, x"∈<"A"-"{x}">")`
Et dont voici la contraposée :
`AA A, (EEx"∈"A, x"∉<"A"-"{x}">") => (AAx"∈"A, x"∉<"A"-"{x}">")`
Dans un magma `E`, la relation de dépendance magmatique correspond à celle d'un matroïde `(E,sf"Indépendants" bbbI)` si et seulement si le magma est d'engendrement linéaire.
`(AAA, (EEx"∈"A, x"∈<"A"-"{x}">") => (AAx"∈"A, x"∈<"A"-"{x}">") <=> sf"Matroïde"(E, sf"Indépendants" {A"⊆"E "/" AAx "∈" A, x"∉<"A "-"{x}">"})`
L'implication se démontre en constatant que la famille `{A"⊆"E "/" AAx "∈" A, x"∉<"A "-"{x}">"}` satisfait les axiomes des indépendants d'un matroïde. Le premier axiome est vérifié, car la logique formelle nous dit que `AAx"∈"Ø,P` est une tautologie. Le second axiome est vérifié aussi. Le troisième axiome se démontre par l'absurde. S'il existe deux telles familles `A` et `B` avec `"card"(A)>"card"(B)` et tel que `AAa "∈" A"\"B, a "∈" "<"B">"`
---- 16 janvier 2021 ----
La réciproque se démontre en considérant la famille des dépendants qui regroupe toutes les ensembles qui ne sont pas des indépendants `{A"⊆"E "/" EEx "∈" A, x"∈<"A "-"{x}">"}`
Du point de vue élémentarien, tous les matroïdes peuvent se définir ainsi. Il existe un moyen de construire un magma d'engendrement linéaire à partir d'un matroïde `(E,sf"Indépendants" bbbI)`, c'est à dire de construire une loi de composition de `E"×"E"→"E` telle que `bbbD = {A"⊆"E "/" AAx "∈" A, x"∈<"A"-"{x}">"}`, faisant que les ensembles dépendants du matroïdes correspondent aux ensembles dépendants magmatiques.
---- 16 janvier 2021 ----
---- 17 mai 2017 ----