Voir Les matroïdes
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)`. On utilise couramment 6 opérateurs sur `ccP(ccP(E))` nommés `"sup(.)"`, `"sub(.)"`, `"max(.)"`, `"min(.)"`, `¬"(.)"`, `bar¬"(.)"` et qui vont nous permettre de construire des familles du matroïde à partir d'autre famille du matroïde.
Étant donné une famille quelconque `bbbF` :
Récapitulatif :
Clôture par agrandissement. `"sup"bbbF = {X "/" EEA"∈"bbbF, A"⊆"X}` Clôture par inclusion. `"sub"bbbF = {X "/" EEA"∈"bbbF, X"⊆"A}` Maximalisation `"max"bbbF = {X "/" X"∈"bbbF "et" AAA"∈"bbbF, X"⊄"A}` Minimalisation `"min"bbbF = {X "/" X "∈"bbbF "et" AAA "∈"bbbF, A "⊄"X}` Négation `¬bbbF = {X "/" X "∉"bbbF}` Complément `bar¬ bbbF = {E"-"X "/" X "∈"bbbF}`
Clos par agrandissement `AAX "∈" bbbF, AAY"/"X"⊆"Y, Y"∈" bbbF` Clos par minimalisation `AAX "∈" bbbF, AAY"/"Y"⊆"X, Y"∈" bbbF` Frontière `AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y` Frontière `AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y`
Notez que `AA Y` signifie `AA Y"⊆"E`.
Notez que le symbole `"⊂"` dénote l'inclusion stricte et donc que nous avons `AA Y, Y "⊄"Y`.
Un ensemble est un dépendant si et seulement s'il n'est pas un indépendant :
`X"∈"bbbI <=> X "∉"bbbD`
On utilise l'opérateur de négation `¬"(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille complémentaire :
`¬bbbF = {A "/" A"∉"bbbF}`
La famille des dépendants s'obtient par négation de la famille des indépendants, et réciproquement :
`¬bbbD = bbbI` `¬bbbI = bbbD`
Ce procédé de construction s'appelle la négation
Un ensemble est dépendant si et seulement s'il contient un circuit.
`X"∈"bbbD <=> EEC"∈"bbbC, C "⊆"X`
On utilise l'opérateur de clôture par agrandissement `"sup(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille des ensembles contenant au moins un membre de `bbbF`.
`"sup"bbbF = {A "/" EEX"∈"bbbF, X"⊆"A}`
La construction des dépendants à partir des circuits consiste à faire une copie de la famille des circuits, puis à ajouter dans la famille tous les ensembles contenant un membre de cette famille.
`"sup"bbbC = bbbD`
Ce procédé de construction s'appelle la clôture par agrandissement. La famille des dépendants s'obtient en prenant la cloture par agrandissement de la famille des circuits.
Un ensemble est un circuit si et seulement si c'est un ensemble dépendant qui ne contient aucun autre ensemble dépendant.
`X"∈"bbbC <=> X"∈"bbbD "et" AAD"∈"bbbD, D"⊄"X`
On utilise l'opérateur de minimalisation `"min(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille des membres minimaux c'est à dire qui ne contiennent aucun autre membre.
`"min"bbbF = {A"∈"bbbF "/" AAX"∈"bbbF, X"⊄"A}`
`"min"bbbF = {A "/" EE!X"∈"bbbF, X"⊆"A}`
La construction des circuits à partir des dépendants consiste à faire une copie de la famille des dépendants, puis à ne garder que les membres minimaux c'est à dire ne contenant aucun autre membre de la famille.
`"min"bbbD = bbbC`
Ce procédé de construction s'appelle la minimalisation. La famille des circuits s'obtient en prenant la minimalisation de la famille des dépendants.
Un ensemble est une base si et seulement si c'est un ensemble indépendant qui n'est contenu dans aucun autre indépendant.
`X"∈"bbbB <=> X"∈"bbbI "et" AAI"∈"bbbI, X "⊄"I`
On utilise l'opérateur de maximalisation `"max(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille des membres maximaux c'est à dire qui ne sont contenus dans aucun autre membre.
`"max"bbbF = {A"∈"bbbF "/" AAX"∈"bbbF, A"⊄"X}`
`"max"bbbF = {A "/" EE!X"∈"bbbF, A"⊆"X}`
La construction des bases à partir des indépendants consiste à faire une copie de la famille des indépendants, puis à ne garder que les membres maximaux c'est à dire ceux qui ne sont contenu dans aucun autre membre de la famille.
`"max"(bbbI) = bbbB`
Ce procédé de construction s'appelle la maximalisation. La famille des base s'obtient en prenant la maximalisation de la famille des indépendants.
Un ensemble est un indépendant si et seulement s'il est inclus dans une base.
`X"∈"bbbI <=> EE B "∈"bbbB, X "⊆"B`
On utilise l'opérateur de clôture par inclusion `"sub(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille des ensembles contenue dans au moins un membre de `bbbF`.
`"sub"bbbF = {A "/" EEX"∈"bbbF, A"⊆"X}`
La construction des dépendants à partir des bases consiste à faire une copie de la famille des bases, puis à ajouter dans la famille tous les ensembles contenus par un membre de cette famille.
`"sub"bbbB = bbbI`
Ce procédé de construction s'appelle la clôture par inclusion. La famille des dépendants s'obtient en prenant la cloture par inclusion de la famille des bases.
Un ensemble est une bases duales si et seulement si c'est le complément d'une base :
`X"∈"bbbB^** <=> EE B "∈"bbbB, X "="¬B`
On utilise l'opérateur de complément des membres ` bar¬"(.)"` qui, appliqué à une famille `bbbF` appartenant à `ccP(ccP(E))`, produit la famille des néggation des membres :
`bar¬bbbF = {¬A "/" A"∉"bbbF}`
La famille des bases duales s'obtient par compléments des membres de la famille des base, et réciproquement :
`bar¬bbbB^** = bbbB` `bar¬bbbB^** = bbbB`
Ce procédé de construction s'appelle le complément des membres. La famille des bases duales s'obtient en prenant le complément des membres de la famille des bases.
Nous allons démontrer de façon formelle les affirmations du chapitre III, et nous allons développer un langage spécifique de démonstration qui sera utilisé pour concevoir un démonstrateur automatique de théorèmes.
...
L'axiomatique des indépendants est :
| `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` |
L'axiomatique des dépendants est :
| `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}` |
Étant donné une famille `bbbI` satisfaisant l'axiomatique des indépendants, et le moyen de construction de la famille `bbbD = ¬bbbI`, on veut démontrer que la famille `bbbD` satisfait l'axiomatique des dépendants.
| Hypothèse | `AAB"∈" bbbI, AAC"/"C"⊆"B, C "∈" bbbI` | 1 |
| Hypothèse | `AA A , A "∈" bbbI <=> A "∉" bbbD` | 2 |
| Hypothèse (raisonnement ad absurdo) | `¬ AAX "∈" bbbD, AAY"/"X"⊆"Y, Y"∈" bbbD` | 3 |
| Simplification de (3), développement de la négation |
`EEX"∈" bbbD, EEY"/"X"⊆"Y, Y"∉" bbbD` | 4 |
| Application de (2) sur (4), sur l'expression `X"∉" bbbI | (X"="A)` puis sur l'expression `Y"∉" bbbD | (X"="Y)` |
`EEX"∉" bbbI, EEY"/"X"⊆"Y, Y"∈" bbbI` | 5 |
| Application de (1) sur (5), sur l'expression `Y"∈" bbbI | (Y"="B)` |
`AAC"/"C"⊆"Y, C "∈" bbbI` | 6 |
| Application de (6) sur (5), sur l'expression `EEY"/"X"⊆"Y | (Y"="C)` |
`Y"∈" bbbI` | 7 |
| Application de (7) sur (4), sur l'expression `Y"∉" bbbD` |
`EEX"∈" bbbD, EEY"/"X"⊆"Y, "Faux"` | 8 |
| Simplification de (8) | `"Faux"` | 9 |
---- 17 janvier 2021 ----
La famille des bases duales est nommée `bbbB^**`. Les bases duales sont les complémentaires des bases. Une base duales intersecte tous les circuits et est minimal avec cette propriété. Une base duales intersecte tous les circuits, et tout point de la base peut se regrouper avec des points en dehors de la base pour former un circuit.
`bbbB^** = {¬X "/" X "∈"bbbB}` `bbbB^** = "∁"(bbbB)` `bbbB^** = "∁"("max"(bbbI))` `bbbB^** = "∁"("max"({X "/" X"∉"D}))` `bbbB^** = "∁"("max"({X "/" AAC"∈"bbbC, C "⊈"X}))` `bbbB^** = "min"({X "/" AAC"∈"bbbC, X"∩"C"≠"Ø})` `bbbB^** = {X "/" (AAC"∈"bbbC, X"∩"C"≠"Ø) "et" (AAe"∈"X, EEC"∈"bbbC, (X"-"{e})"∩"C"="Ø)}`
La famille des bases duales d'un matroïde possède les mêmes axiomes que ceux de la famille des bases d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des bases duales d'un martroïde si elle satisfait l'axiome du non vide `P_7(bbbF)` et l'axiome d'échange `P_8(bbbF)`.
Etant donné la famille des bases `bbbF` d'un matroïde. C'est à dire une famille `bbbF` satisfaisant les deux axiomes `P_7(bbbF)` et `P_8(bbbF)`. Nous allons vérifier que la famille des compléments `"∁"(bbbB)` satisfait également ces deux propriétés.
D'après l'axiome de non vide, il existe au moins une base. Le complément de cette base constitue une base duale. On en déduit qu'il existe au moins une base duale.
`bbbF"≠"Ø` donc `"∁"bbbF"≠"Ø`
Etant donné deux bases `A`, `B` et un élément `e` appartenant à `A"\"B`, d'après l'axiome d'échange, il exite un élément `f` appartenant à `B"\"A` tel que `(A"-"{e}"+"{f})` est une base.
Les formules suivantes sont équivalentes :
`AAX "∈" bbbF, AAY "∈" bbbF, AAe"∈"X"\"Y, EE f "∈" Y"\"X, (X"-"{e}"+"{f})"∈" bbbF`
`AAX "∈" bbbF, AAY "∈" bbbF, AAe"∈"¬Y"\"¬X, EE f "∈" ¬X "\"¬Y, ¬(¬X"+"{e}"-"{f})"∈" bbbF`
`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"Y"\"X, EE f "∈" X "\"Y, (X"+"{e}"-"{f})"∈""∁" bbbF`
`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (Y"+"{e}"-"{f})"∈""∁" bbbF`
`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (Y"+"{e}"-"{f})"∈""∁" bbbF`
et à cause d'une symétrie (qui reste à formaliser...)
`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (X"+"{f}"-"{e})"∈""∁" bbbF`
`AAX "∈" "∁"bbbF, AAY "∈" "∁"bbbF, AAe"∈"X"\"Y, EE f "∈" Y "\"X, (X"-"{e}"+"{f})"∈""∁" bbbF`
La famille des indépendants duals est nommée `bbbI^**`. Les indépendants duals s'obtiennent à partir des bases duales de la même façon que les indépendants s'obtiennent des bases, par cloture par inclusion.
`bbbI^** = "inf"(bbbB^**)` `bbbI^** = {X "/" EEB"∈"bbbB^**, X"⊆"B}`
Tout point appartenant à un indépendant dual admet un circuit composé du point en question et d'autres points tous à l'exterieur de l'indépendant dual.
`X"∈"bbbD^** <=> AAe"∈"X, EE C"∈"bbbC, C"∩"X"="{e}`
La famille des indépendants duals d'un matroïde possède les mêmes axiomes que ceux de la famille des indépendants d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des indépendants duals d'un martroïde si et seulement si elle satisfait l'axiome du vide inclus `¬P_1(bbbF)`, l'axiome de clôture par inclusion `P_5(bbbF)` et l'axiome d'agrandissement `P_6(bbbF)`.
La famille des dépendants duals est nommée `bbbD'`. Les dépendants duals s'obtiennent à partir des indépendants duals de la même façon que les dépendants s'obtiennent des indépendants, par la négation.
`bbbD^** = ¬(bbbI^**)` `bbbD^** = {X "/" X "∉"bbbI^**}`
La famille des dépendants duals d'un matroïde possède les mêmes axiomes que ceux de la famille des dépendants d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des dépendants duals d'un martroïde si et seulement si elle satisfait l'axiome du vide exclus `P_1(bbbF)`, l'axiome clôture par agrandissement.`P_4(bbbF)` et l'axiome d'élimination `P_3(bbbF)`
La famille des coupures est nommée `bbbC'`. Les coupures s'obtiennent à partir des dépendants duals de la même façon que les circuits s'obtiennent des dépendants, par frontière minimum.
`bbbC^** = "min"(bbbD^**)` `bbbC^** = {X "/" X"∈"bbbD^** "et" AAY"∈"bbbD^**, Y "⊄"X}`
La famille des coupure d'un matroïde possède les mêmes axiomes que ceux de la famille des circuits d'un matroïde. Autrement dit une famille `bbbF` correspondra à la famille des coupures d'un martroïde si et seulement si elle satisfait l'axiome du vide exclus `P_1(bbbF)`, l'axiome de frontière `P_2(bbbF)` et l'axiome d'élimination `P_3(bbbF)`
---- 14 mai 2017 ----
Etant donné une famille quelconque `bbbF`.
La famille `"inf"(bbbF)` regroupe tous les ensembles contenus dans au moins un membre de `bbbF`. C'est la clôture par inclusion.
`"inf"(bbbF) = {X "/" EEA"∈"bbbF, X"⊆"A}`
La propriété pour une famille d'être invariante par l'opérateur `"inf"` est équivalente à celle d'être close par inclusion. Autrement dit, la famille satisfait la propriété `P_5(bbbF)` dite "Inf".
`bbbF "=inf"(bbbF) <=> P_5(bbbF)` `bbbF "=inf"(bbbF) <=> AAX "∈" bbbF, AAY"/"Y"⊆"X, Y"∈" bbbF`
La famille `"max"(bbbF)` regroupe tous les membres de `bbbF` qui sont maximaux (sous entendu selon l'ordre d'inclusion). C'est la frontière des maximums.
`"max"(bbbF) = {X "/" X"∈"bbbF "et" AAA"∈"bbbF, X"⊄"A}`
La propriété pour une famille d'être invariante par l'opérateur `"max"` est équivalente à celle d'être composée de membres qui ne sont jamais inclus strictement l'un dans l'autre. Autrement dit, la famille satisfait la propriété `P_2(bbbF)` dite "Frontière".
`bbbF "=max"(bbbF) <=> P_2(bbbF)` `bbbF "=max"(bbbF) <=> AAX"∈"bbbF,AAY"∈"bbbF,X"⊄"Y`
Les opérérations `"min"` et `"sup"` sont l'inverse l'une de l'autre pour les familles `bbbF` possèdant la caractéristique `P_2(bbbF)` dite "Frontière" ou bien la caracteristique `P_4(bbbF)` dite "Sup", et font passer les familles d'une caractéristique à l'autre.