Anticadeia

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Em matemática, na área da teoria da ordem, uma anticadeia é um subconjunto de um conjunto parcialmente ordenado de modo que quaisquer dois elementos distintos no subconjunto são incomparáveis.[1] Anticadeias também são chamadas de sistemas de Sperner na literatura mais antiga.[2]

Operações de junção e encontro[editar | editar código-fonte]

Uma anticadeia A corresponde a um segmento inicial[3]

Em uma ordem parcial finita (ou mais geralmente em uma ordem parcial que satisfaça a condição de cadeia ascendente), todos os segmentos iniciais têm essa forma. Da mesma forma, podemos definir uma operação de encontro em antichains, correspondendo à interseção de segmentos iniciais:

Da mesma forma, podemos definir uma operação de encontro em anticadeias, correspondendo à interseção de segmentos iniciais:

As operações de junção e encontro em todas as anticadeias finitas de subconjuntos finitos de um conjunto X definem uma rede ou reticulado distributivo[4], a rede distributiva livre gerada por X.[5] O teorema de representação de Birkhoff[6] para redes distributivas afirma que toda rede distributiva finita pode ser representada por meio de operações de junção e encontro em anticadeias de uma ordem parcial finita, ou equivalentemente como operações de união e intersecção nos conjuntos inferiores da ordem parcial.[7]

Referências

  1. Viennot, G. (1984). «Chain and antichain families, grids and Young tableaux» (PDF) 
  2. Comtet, L (1974). «"Sperner Systems."». www.amazon.com. p. 271-273. Consultado em 19 de novembro de 2020 
  3. Bazerman, Gershom; Puzio, Raymond (12 de abril de 2020). «The Topological and Logical Structure of Concurrency and Dependency via Distributive Lattices» (em inglês). Consultado em 19 de novembro de 2020 
  4. Birkhoff, Garrett (1967). Lattice theory. [S.l.]: Providence, American Mathematical Society 
  5. Bazerman, Gershom; Puzio, Raymond (12 de abril de 2020). «The Topological and Logical Structure of Concurrency and Dependency via Distributive Lattices». arXiv:2004.05688 [cs, math]. Consultado em 19 de novembro de 2020 
  6. Birkhoff, Garrett (setembro de 1937). «Rings of sets». Duke Mathematical Journal (3): 443–454. ISSN 0012-7094. doi:10.1215/s0012-7094-37-00334-x. Consultado em 19 de novembro de 2020 
  7. Priestley, H. A. (julho de 1970). «Representation of Distributive Lattices by means of ordered Stone Spaces». Bulletin of the London Mathematical Society (em inglês) (2): 186–190. doi:10.1112/blms/2.2.186. Consultado em 19 de novembro de 2020 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.