Anticadeia

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. Anticadeias também são chamadas de sistemas de Sperner na literatura mais antiga.

Operações de junção e encontro

Uma anticadeia A corresponde a um segmento inicial

$L_{A}=\{x\mid \exists y\in A{\mbox{ s.t. }}x\leq y\}.$

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:

$A\vee B=\{x\in A\cup B\mid \nexists y\in A\cup B{\mbox{ s.t. }}x<y\}.$

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

$A\wedge B=\{x\in L_{A}\cap L_{B}\mid \nexists y\in L_{A}\cap L_{B}{\mbox{ s.t. }}x<y\}.$

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, a rede distributiva livre gerada por X. O teorema de representação de Birkhoff 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.