Le matroïde est une structure, introduite par Hassler Whitney en 1935, qui généralise la notion d'indépendance linéaire en ne retenant que ses propriétés ensemblistes.
Le matroïde est une structure qui se définie en logique du second ordre, utilisant des variables de deux types ; de type point et de type ensemble de points.
Le matroïde possède `10` facettes qui correspondent à `10` façons de le définir. Il possède 2 fonctions de rang et 8 familles d'ensembles que sont ; la famille des circuits, la famille des dépendants, la famille des indépendants, et la famille des bases, et une fonction dimension qui appliquée à un ensemble de points retourne un entier positif correspondant à la dimension de l' « espace » engendré par l'ensemble de points en question, et leurs duals que sont ; la famille des coupures, la famille des dépendants duals, la famille des indépendants duals, et la famille des base duales, et la fonction dimension duale qui appliquée à un ensemble de points retourne un entier positif correspondant à la dimension de l' « espace dual » engendré par cet ensemble de points.
Chacune de ces 8 familles satisfont une axiomatique spécifique et détermine le matroïde tout entier, et donc détermine les 7 autres familles et les 2 fonctions de rang. Et de même, chacune des deux fonctions de rang déterminent également le matroïde tout entier.
Cette structure est propice à la conception d'un langage logique du troisième ordre, utilisant trois types de variable que sont ; le point, l'ensemble de points, et la famille d'ensembles de points, et est propice à la conception d'un système original de démonstration automatique.
On pose un ensemble de points `E` comme ensemble sous-jacent de la structure. Cela peut être n'importe quel ensemble. Par commodité les éléments de `E` sont appelés des points. Et les sous-ensembles de `E` sont appelés simplement des ensembles.
Les variables désignant des points sont notées en minuscules `a,b,c...`.
Les variables désignant des ensembles sont notées en majuscules `A,B,C,...`.
Les variables désignant des familles d'ensembles sont notées en majuscules à double-barre `bbbA,bbbB,bbbC,...`.
Il y a ainsi `3` types de variables.
L'expression `AA a` signifie quelque soit un point `a` appartenant à `E`.
L'expression `AA A` signifie quelque soit un ensemble `A` appartenant à `ccP(E)`.
Et l'expression `AA bbbA` signifie quelque soit une famille `bbbA` appartenant à `ccP(ccP(E))`.
On désigne les différentes familles du matroïde comme suit :
`bbbC` : Famille des circuits `bbbD` : Famille des dépendants `bbbI` : Famille des indépendants `bbbB` : Famille des bases `bbbB^**` : Famille des bases duales `bbbI^**` : Famille des indépendants duals `bbbD^**` : Famille des dépendants duals `bbbC^**` : Famille des coupures
La famille des circuits est notée `bbbC`. Un circuit est ensembles de points liés par une relation de dépendance définie par le matroïde, et où chaque point est indispensable pour maintenir cette dépendance. Un circuit est un dépendant minimum. Si l'on retire un point quelconque d'un circuit celui-ci devient un indépendant. La famille des circuits obéït à trois axiomes :
Une famille quelconque `bbbC` correspondra à la famille des circuits d'un matroïde si et seulement si elle satisfait les trois axiomes suivants :
`bbbC` ne possède pas `Ø` `Ø "∉" bbbC` `bbbC` est une frontière `AAX "∈" bbbC, AAY"∈"bbbC, X"⊄"Y` `bbbC` permet l'élimination `AAX "∈" bbbC, AAY "∈" bbbC"/"(X"≠"Y "et" EEe "∈" X"∩"Y),EE Z"∈"bbbC, Z"⊆"(X"∪"Y)"-"{e}`
Et on note le matroïde définie par ses circuits comme suit :
`sf"Matroïde" (E,sf"Circuits" bbbC)`
Après cette déclaration, le symbole `E` en tant qu'ensemble désignera l'ensemble sous-jacent du matroïde, et en tant que structure désignera le matroïde en question.
La famille des dépendants est notée `bbbD`. Un dépendant contient un ensemble de points liés par une relation de dépendance définie par le matroïde. Autrement dit, un dépendant contient un circuit. La famille des dépendants obéït à trois axiomes :
Une famille quelconque `bbbD` correspondra à la famille des dépendants d'un matroïde si et seulement si elle satisfait les trois axiomes suivants :
`bbbD` ne possède pas `Ø` `Ø "∉" bbbD` `bbbD` est clos par agrandissement `AAX "∈" bbbD, AAY"/"X"⊆"Y, Y"∈" bbbD` `bbbD` permet l'élimination `AAX "∈" bbbD, AAY "∈" bbbD"/"(X"≠"Y "et" EEe "∈" X"∩"Y),EE Z "∈"bbbD, Z"⊆"(X"∪"Y)"-"{e}`
Et on note le matroïde définie par ses dépendants comme suit :
`sf"Matroïde" (E,sf"Dépendants" bbbD)`
La famille des indépendants est notée `bbbI`. Un indépendant est un ensemble qui n'est pas un dépendant. C'est un ensemble de points dans lequel aucune relation de dépendance n'existe. Un indépendant ne contient pas de circuit. La famille des indépendants obéït à trois axiomes :
Une famille quelconque `bbbI` correspondra à la famille des indépendants d'un matroïde si et seulement si elle satisfait les trois axiomes suivants :
`Ø "∈" bbbI` `Ø "∈" bbbI` `bbbI` est clos par inclusion `AAX "∈" bbbI, AAY"/"Y"⊆"X, Y"∈" bbbI` `bbbI` permet l'agrandissement `AAX "∈" bbbI, AAY "∈" bbbI"/"|X|">"|Y|,EEe "∈" X"\"Y, Y"+"{e}"∈"bbbI`
Et on note le matroïde définie par ses indépendants comme suit :
`sf"Matroïde" (E,sf"Indépendants" bbbI)`
Après cette déclaration, le symbole `E` en tant qu'ensemble désignera l'ensemble sous-jacent du matroïde, et en tant que structure désignera le matroïde en question.
La famille des bases est notée `bbbB`. Une base correspond à un indépendant maximal. C'est à dire que l'adjonction de tout point le transforme en un circuit. Autrement dit, une base ne contient pas de circuit et est maximale avec cette propriété. La famille des bases obéït à deux axiomes :
Une famille quelconque `bbbB` correspondra à la famille des bases d'un matroïde si et seulement si elle satisfait les deux axiomes suivants :
`bbbB` n'est pas vide `bbbB"≠"Ø` `bbbB` permet l'échange `AAX "∈" bbbB, AAY "∈" bbbB, AAe"∈"X"\"Y,EE f "∈" Y"\"X, (X"-"{e}"+"{f})"∈" bbbB`
Et on note le matroïde définie par ses bases comme suit :
`sf"Matroïde" (E,sf"Bases" bbbB)`
La fonction dimension, notée `"dim"`, s'applique à un ensemble de points et retourne un entier positif appelé la dimension de l'espace engendré par cet ensemble de points.
`"dim"∈ccP(E)"→"NN`
La dimension d'un ensemble est égale au plus grand cardinal rencontré parmis les sous-ensembles indépendants. La fonction dimension obéït à 3 axiomes :
Une application quelconque `rho` correspondra à une fonction dimension d'un matroïde si et seulement si elle satisfait les trois axiomes suivants :
`rho(Ø) "=" 0` `rho(Ø) "=" 0` `rho` respecte l'ordre `AA X, AA Y"/"Y"⊆"X, rho(Y)"≤"rho(X)` `AAX, AA Y"/"rho(X)">"rho(Y),EEe "∈" X, rho(Y"+"{e})">"rho(Y)`
Et on note le matroïde définie par sa fonction de dimension, `rho`, comme suit :
`sf"Matroïde" (E,sf"dimension" rho)`
Le matroïde dual noté `E^**` a le même ensemble sous-jacent `E`, et ses bases sont exactement les complémentaires des bases de `E`.
Les familles des circuits `bbbC`, des dépendants `bbbD`, des indépendants `bbbI` et des bases `bbbB`, ont les mêmes systèmes d'axiome que leurs duals respectifs qui sont notés avec l'exposant `""^**`.
La famille des coupures duales `bbbC^**` obéït donc aux axiomes suivants : L'ensemble vide n'est pas une coupure, `bbbC^**` est une frontière, et permet l'élimination.
La famille des dépendants duals `bbbD^**` obéït donc aux axiomes suivants : L'ensemble vide n'est pas dépendant, `bbbD^**` est clos par agrandissement, et permet l'élimination.
La famille des indépendants duals `bbbI^**` obéït donc aux axiomes suivants : L'ensemble vide est indépendant, `bbbI^**` est clos par inclusion, et permet l'agrandissement
La famille des bases duales `bbbB^**` obéït donc aux axiomes suivants : `bbbB^**` n'est pas vide et permet l'échange
La fonction de dimension duale `dim^**` obéït donc aux axiomes suivants : la dimension de l'ensemble vide est nulle, `"dim"^**` respecte l'ordre et permet l'agrandissement.
La théorie du matroïde `(E, bbbI)` stipule que l'ensemble vide est un indépendant, `Ø "∈" bbbI`, décrivant la définition intuitive initiale (davantage affine que vectorielle). Si cet axiome n'est pas respecté alors l'ensemble vide devient un ensemble dépendant, et comme les ensembles dépendants sont clos par agrandissement, tous les ensembles deviennent dépendant.
La containte apportée par cet axiome consiste a écarter un seul modèle triviale !. À l'inverse de la démarche du zéro dans l'histoire des mathématiques qui va ajouter un axiome pour introduire le zéro parmi les entiers naturels, on introduit ici un axiome pour enlever un cas particulier. C'est assurément une complexification inutile. Il est donc inutile de garder cet axiome. C'est pourquoi, dans de nombreux ouvrage, cette axiome n'y figure pas.
Les structures sont des objets mathématiques qui focalisent l'attention du démonstrateur. On formalise le langage en un langage d'opérateurs et prédicats, afin de pouvoir manipuler ces objets de façon formelle.
Conventionellement on utilise la famille des indépendants pour définir un matroïde. Ainsi un matroïde se présente par un couple `(E, bbbI)` comprenant un ensemble sous-jacent `E`, et une famille `bbbI` de sous-ensembles de `E`. On se limite aux seuls éléments de l'ensemble de la structure c'est à dire aux éléments de l'ensemble sous-jacent `E`. Un ensemble se traduit alors en langage d'opérateur par un prédicat appartenant à `E"→"{0,1}`, et une famille `bbbI` se traduit par un prédicat appartenant à `(E"→"{0,1})"→"{0,1}`.
On définie une structure anonyme de même signature comme suit :
`E = sf"Structure"(E,bbbI^((E"→"{0,1})"→"{0,1}))`
Notez que dans la présentation d'une structure anonyme, le type des opérateur est mis en exposant. Après cette déclaration, le symbole `E` en tant qu'ensemble désignera l'ensemble sous-jacent de la structure, et en tant que structure désignera la structure en question qui est l'ensemble `E` muni d'une famille `bbbI`. Le terme `sf"Structure"` se comporte comme un opérateur, mais il n'apporte ici aucune théorie si ce n'est sa signature qui est donnée par le type de ses arguments. Puis on lui donne encore un autre sens, celui de représenter l'ensemble des structures à isomorhisme près.
Le dénombrement nous indique le nombre distincts de telles structures, à isomorphisme près, basées sur un ensemble sous-jacent de `"card"(E)"="n` éléments. Le paramètre `n` est placé en indice du nom de la structure :
`"card"(sf"Structure"_n(E,bbbI^((E"→"{0,1})"→"{0,1}))) ⩽ 2^(2^n)/(n!)`
En effet il existe `2^(2^n)` familles distinctes et il existe `n!` isomorphismes triviaux. Un isomorphisme est à la fois une bijection et un morphisme c'est à dire qui respecte les opérateurs déclarées dans la présentation et que nous décrivons au chapitre suivant.
La structure peut se restreindre à une théorie telle que celle du matroïde, elle porte alors le nom de la théorie. Et on utilise le même nom de l'ensemble sous-jacent pour désigner la structure qui est cet ensemble sous-jacent muni d'une famille satisfaisant la théorie du matroïde :
`E = sf"Matroïde"(E,bbbI)`
Après cette déclaration, le symbole `E` en tant qu'ensemble désignera l'ensemble sous-jacent du matroïde, et en tant que structure désignera le matroïde en question. Puis on utilise aussi l'expression logique qui définit la strucure :
`sf"Matroïde"(E,bbbI) <=> (( Ø "∈" bbbI) , (AAX "∈" bbbI"," AAY"/"Y"⊆"X"," Y"∈" bbbI),(AAX "∈" bbbI"," AAY "∈" bbbI"/"|X|">"|Y|","EEe "∈" X"\"Y"," Y"+"{e}"∈"bbbI))`
Le terme `sf"Matroïde""(.,.)"` se comporte alors comme une fonction propositionnelle c'est à dire un prédicat. Ainsi, en tant qu'objet il désignera la structure, et en tant que proposition il désignera la théorie.
Notez que le symbole d'appartenance `"∈"` n'est ici qu'une rallonge syntaxique. L'expression `x"∈"A` où `x` est de type élément et `A` est de type ensemble (c'est à dire un prédicat de `E"→"{0,1}`), correspond à l'expression `A(x)`. Notez que La fonction propositionnelle `sf"Matroïde""(.,.)"` est du second ordre car elle introduit des variables quantifiés `AA` ou `EE`, de deux types ; de type élément désigné par `E`, et de type ensemble désigné par `E"→"{0,1}`.
---- 18 janvier 2021 ----
On considère deux sortes de structures ; les structure engendrées, et les structure innée. Par défaut une structure est innée.
Une structure innée possède un ensemble sous-jacent inconnu, et peut être paramétré en indice par le nombre d'éléments de son ensemble sous-jacent. Une structure engendrée possède un ensemble sous-jacent engendré, c'est à dire énumérable par un procédé de construction connue par la structure elle-même, et on le différencie de la structure innée en l'indiçant avec le symbole `""_"min"`.
Considérons d'abord la structure engendrée la plus simple qui énumère quelques éléments, c'est une liste telle que par exemple :
`sf"Structure"_"min" (E, a^E,b^E,c^E)`
Cette structure anonyme présente `3` opérateurs nullaires (d'arité nulle, c'est à dire un symbole désignant un élément), qui engendre l'ensemble sous-jacent `E`, qui contient donc les éléments `a,b,c`, et ne possède pas de contrainte théorique (théorie vide). Aussi on ne sait pas si ces éléments sont égaux entre eux ou pas.
Après cette déclaration, le symbole `E` en tant qu'ensemble désigne l'ensemble `E={a}"∪"{b}"∪"{c}`, et en tant que structure il désigne l'ensemble `E` muni des `3` opérateurs nullaires `a,b,c` qui désigne un triplet d'éléments.
La signature de la structure engendrée `E` est `(E,E,E)`. L'expression `sf"Structure"(a^E,b^E,c^E)` désigne également l'ensemble des structures engendrée de même signature `(E,E,E)` à isomorphisme près. Et il y en a `5` correspondant aux cas suivants :
`a"="b "et" b"="c`
`a"≠"b "et" a"≠"c "et" b"="c`
`b"≠"a "et" b"≠"c "et" a"="c`
`c"≠"a "et" c"≠"b "et" a"="b`
`a"≠"b "et" a"≠"c "et" b"≠"c`
Chacun de ces cas décrit un modèle, une forme concrète complétement définie que peut prendre la structure.
`"card"(sf"Structure"_"min"(a^E,b^E,c^E)) = 5`
Considérons ensuite la structure engendrée la plus simple qui énumére les entiers :
`N=sf"Structure"_"min"(1,s^(E"→"E))`
On notera souvent un opérateur de type `E"→"E` en le suffixant par `"(.)"`,
---- 18 janvier 2021 ----
Les isomorphismes sont des bijections f qui respecte les 3 opérateurs c'est à dire
Une précision importante, l'isomorphisme est défini relativement à la signature de la structure considérée et non à sa théorie. Le terme matroïde, en tant que signature, désigne la signature `(E, (E"→"{0,1})"→"{0,1}))`, et en tant que structure, il construit une structure comme vue au chapitre précédent.
comprenant qu'un ensemble sous-jacent `E`. C'est la structure d'un ensemble, notée `sf"Ensemble"(E)`. Et on note la structure d'un ensemble de `n` éléments `sf"Ensemble_n"(E)`. Et on note la structure d'un ensemble infini `sf"Ensemble_oo"(E)`.
Les isomorphismes d'ensembles sont simplement les bijections. Et il y a exactement `n!` bijections possibles entre deux ensembles de `n` éléments.
`"card"({1,2,3,...,n}↔{1,2,3,...,n}) = n!`
Dans le cas fini, le nombre de structure d'ensemble à `n` éléments, à bijection près, vaut exactement `1`. C'est ce constat qui permet de définir les entiers naturelles `NN` de manière ensembliste. Dans le cas infini, les élémentariens ne retiennent que les modèles dénombrables, et donc le nombre de structure d'ensembles infinis, à bijection près, vaut exactement `1`. C'est ce constat qui permet de définir les cardinaux `NN uu {oo}` de manière ensembliste. On résume cela par le dénombrement des structures d'ensemble à bijection près :
`"card"(sf"Ensemble"_n(E)) = 1`
`"card"(sf"Ensemble"_oo(E)) = 1`
`"card"(sf"Ensemble"(E)) = oo`
Considérons maintenat la structure comprenant qu'un ensemble sous-jacent `E` et un sous-ensemble `A` :
`E = sf"Structure"(E,A^(E"→"{0,1}))`
Notez que dans la présentation d'une structure anonyme, le type des opérateurs est mis en exposant. Une application `f` de `E"→"E` est un morphisme pour cette structure si et seulement si `AAx, x "∈" A <=> f(x) "∈" f(A)` où `f(A)` est la définition classique de l'image de `A` par `f`. Le morphisme `f` peut permuter les éléments de `A`, et il peut également permuter les éléments du complément que l'on note `¬A`. On en déduit le nombre d'isomorphismes pour `"card"(E)"="n` et `"card"(A)"="a`, qui est `a!(n-a)!`.
`"card"(sf"Structure"_n(E,A^(E"→"{0,1})) = 1,(n-1)`
Notez que dans la présentation d'une structure anonyme, le type des opérateurs est mis en exposant. Une application `f` de `E"→"E` est un morphisme pour cette structure si et seulement si `AAx, x "∈" A <=> f(x) "∈" f(A)` où `f(A)` est la définition classique de l'image de `A` par `f`. Le morphisme `f` peut permuter les éléments de `A`, et il peut également permuter les éléments du complément que l'on note `¬A`. On en déduit le nombre d'isomorphismes pour `"card"(E)"="n` et `"card"(A)"="a`, qui est `a!(n-a)!`.
(Les ensembles finis sont caractérisés par leur cardinal `n in NN`, et les ensembles infinis sont caractérisée par la limite lorsque `n` tend vers l'infini, une suite convergeant vers l'infini qui transporte toute l'information sur l'ordinalité de l'ensemble infini en question.)
---- 18 janvier 2021 ----