Antichaine
Na matemática , mais precisamente na teoria da ordem , uma anticadeia é uma parte de um conjunto parcialmente ordenado cujos elementos são dois a dois incomparáveis.
Em outras palavras, seja E um conjunto dotado de uma relação de ordem ≤, um subconjunto A é uma anticadeia de E se para todo x , y de A ,
x≤y ou y≤x⟹x=y.{\ displaystyle x \ leq y {\ text {ou}} y \ leq x \ implica x = y.}
Uma anti-cadeia é considerada máxima se não estiver incluída em nenhuma outra anti-cadeia.
A largura de uma ordem é o máximo dos cardeais de suas antichains.
Exemplos
Ordem total
Os antichains de um conjunto totalmente ordenado são os singletons e o conjunto vazio. Portanto, a largura de um pedido total é 1.
Conjunto de partes de um conjunto e inclusão
Que o conjunto de partes de um determinado conjunto , dotado da relação de inclusão, seja denominado família de Sperner uma anticadeia de . Se é finito cardinal n , a largura da inclusão é então, de acordo com o teorema Sperner : .
P(E){\ displaystyle {\ mathcal {P}} (E)}E{\ displaystyle E}P(E){\ displaystyle {\ mathcal {P}} (E)}E{\ displaystyle E}(não⌊não/2⌋){\ displaystyle {n \ escolher \ lfloor {n / 2} \ rfloor}}
Tomemos o caso particular das partes de um conjunto com 3 elementos , dos quais a figura abaixo representa o diagrama de Hasse .
{x,y,z}{\ displaystyle \ {x, y, z \}}
Seus antichains máximos são:
-
{∅}{\ displaystyle {\ big \ {} \ varnothing {\ big \}}}, {{x,y,z}}{\ displaystyle {\ big \ {} \ {x, y, z \} {\ big \}}}
-
{{x},{y,z}}{\ displaystyle {\ big \ {} \ {x \}, \ {y, z \} {\ big \}}}, ,{{y},{x,z}}{\ displaystyle {\ big \ {} \ {y \}, \ {x, z \} {\ big \}}}{{z},{x,y}}{\ displaystyle {\ big \ {} \ {z \}, \ {x, y \} {\ big \}}}
-
{{x},{y},{z}}{\ displaystyle {\ big \ {} \ {x \}, \ {y \}, \ {z \} {\ big \}}}, .{{x,y},{x,z},{y,z}}{\ displaystyle {\ big \ {} \ {x, y \}, \ {x, z \}, \ {y, z \} {\ big \}}}
Sua largura é igual a 3, o cardeal das duas maiores antichains.
ℕ fornecido com divisibilidade
Considere o conjunto N de números naturais , ordenados por divisibilidade .
Para cada número natural n , a largura de {1, 2 ..., 2 n } (dotado com a ordem induzida) é n . Além disso, neste conjunto ordenado, um elemento da forma 2 k c com impar c pertence a um antichain máxima (ou seja, de cardinal n ) se e só se 2 n <3 k + 1 C .
Antichain infinito
Uma bela ordem é uma ordem parcial bem fundada sem uma anticadeia infinita.
Aplicativos de computador
Antichains são usados na ciência da computação como uma estrutura de dados eficiente na verificação de modelos .
Veja também
Artigos relacionados
Link externo
(pt) Eric W. Weisstein , “ Antichain ” , no MathWorld
Referências
-
Nathalie Caspard, Bruno Leclerc e Bernard Monjardet, Conjuntos ordenados finitos: conceitos, resultados e usos , Springer,2007( leia online ) , p. 19.
-
(in) De Wulf , L. Dean , N. Maquet e JF Raskin , " Antichains: Alternative Algorithms for LTL Satisfiability and Model-Checking " , Tools and Algorithms for the Construction and Analysis of Systems , Springer, Berlin, Heidelberg, lendo Notas em Ciência da Computação,29 de março de 2008, p. 63-77 ( ISBN 9783540787990 , DOI 10,1007 / 978-3-540-78800-3_6 , lido on-line , acessado 1 st março 2018 )
-
(em) " Antichains "
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">