Conjunto parcialmente ordenado

Em matemática , um conjunto parcialmente ordenado (às vezes chamado de poset do conjunto parcialmente ordenado inglês ) formaliza e generaliza a noção intuitiva de ordem ou arranjo entre os elementos de um conjunto . Um conjunto parcialmente ordenado é um conjunto fornecido com uma relação de ordem que indica que, para certos pares de elementos, um é menor que o outro. Todos os elementos não são necessariamente comparáveis, ao contrário de um conjunto fornecido com um pedido total .

Se o conjunto for finito, temos uma representação gráfica do conjunto parcialmente ordenado, o diagrama de Hasse , que pode facilitar o trabalho com ele. Se o conjunto for infinito, podemos desenhar parte de seu diagrama de Hasse.

Definição e exemplos

Definição

Uma ordem (ou ordem parcial) é uma relação binária em um conjunto P que é reflexiva , antissimétrica e transitiva . Nota-se ≤.

Os três axiomas anteriores são reescritos:

a ≤ a (reflexividade).
Se a ≤ b e b ≤ a , então a = b (anti-simetria).
Se um ≤ b e b ≤ c , em seguida, uma ≤ c (transitivity).

Portanto, não é necessariamente uma ordem total .

Exemplos

O conjunto de inteiros naturais, fornecido com divisibilidade, é um conjunto infinito parcialmente ordenado.
Um conjunto de pessoas com relação de descendência genealógica é um conjunto parcialmente ordenado. Por exemplo, duas irmãs são inferiores à mãe, mas não são comparáveis entre si.
O conjunto de partes de um determinado conjunto , fornecido com a inclusão, forma um conjunto parcialmente ordenado. Se o conjunto fornecido é finito, seu conjunto de partes é finito (mais precisamente para , temos ). A figura abaixo representa o diagrama de Hasse de um conjunto com 3 elementos. $\ # A = n$ $\ #P (A) = 2 ^ {n}$

Para tomar um caso concreto (na verdade, isomórfico ) do exemplo anterior, um conjunto de pessoas dotadas da relação pode doar sangue para formar um conjunto parcialmente ordenado de acordo com os sistemas ABO e Rhesus . Os elementos x , y e z no exemplo anterior mais geral sendo instanciados pelos antígenos A, B e D (Rh +) do indivíduo. Por exemplo, um indivíduo do grupo O + pode dar a um destinatário do grupo B +, mas nenhum pode dar ou receber de um indivíduo do grupo A-.
O conjunto de números complexos fornecidos na seguinte relação de ordem está parcialmente ordenado: . $a + ib <a '+ ib' \ Leftrightarrow \ left \ {{\ begin {matrix} a <a '\\ b <b' \ end {matrix}} \ right.$

Por exemplo, não podemos comparar 1 e i . Esta ordem não é compatível com a estrutura corporal de . $\ mathbb {C}$

O conjunto de funções de in , fornecido com a relação de ordem si , é um conjunto infinito parcialmente ordenado. Intuitivamente, uma função é menor do que outra se sua curva estiver sempre abaixo da outra. Podemos generalizar este exemplo para as funções de um conjunto X em um conjunto parcialmente ordenado P. $\ mathbb {R}$ $\ mathbb {R}$ $f <g$ $\ forall x, f (x) <g (x)$
O conjunto de partições de um determinado conjunto é parcialmente ordenado, com a ordem dada pelo refinamento das partições: por definição, uma partição é mais fina que outra se divide as partes da outra em partes menores.
Podemos fornecer o conjunto de polinômios com n variáveis com uma relação de ordem parcial. Começamos comparando os monômios com n variáveis por meio da ordem lexicográfica induzida por (essa ordem lexicográfica é total). Comparamos dois polinômios e dizemos que é estritamente menor do que se qualquer monômio diferente de zero de for estritamente menor do que qualquer monômio diferente de zero de . Essa relação de ordem nos polinômios é parcial. $R [X_ {1}, ..., X_ {n}]$ $1 <X_ {1} <X_ {2} <... <X_ {n}$ $P$ $Q$ $P$ $Q$ $P$ $Q$

Especificidades de conjuntos parcialmente ordenados

Maior Elemento , Elemento Máximo e Limite Superior

Seja P um conjunto parcialmente ordenado:

Um elemento a de P é um elemento maior se para qualquer elemento b de P, b ≤ a. Um conjunto parcialmente pedido pode ter apenas um elemento maior.

Um elemento a de P é um elemento máximo se não houver nenhum elemento b de P tal que b> a. Se P tem um elemento maior, é o elemento máximo único de P.

Para um subconjunto A de P, o elemento x de P é um limite superior de A se a ≤ x para qualquer elemento a de A. x não pertence necessariamente a A. O maior elemento de P, s 'que existe, é um limite superior de P.

Exemplo : considere o conjunto de inteiros positivos, ordenados por divisão. 1 é o menor elemento. Por outro lado, este conjunto não possui um elemento maior. Se agora excluíssemos o elemento 1, o conjunto parcialmente ordenado não teria mais um elemento menor, mas uma infinidade de elementos mínimos: os números primos .

Se E é um conjunto parcialmente ordenado, não existe necessariamente um elemento maior. Se E for um conjunto finito parcialmente ordenado, ele conterá pelo menos um elemento máximo. Se E é um conjunto indutivo infinito, podemos usar o lema de Zorn para ter a existência de um elemento máximo.

Certas condições nos elementos maiores e nos menores elementos de um conjunto parcialmente ordenado levam à definição de uma rede .

Pelo mesmo raciocínio, obtemos o menor elemento, os elementos mínimos e o limite inferior.

Comparabilidade

Se a ≤ b ou a b, então a e b são comparáveis. No diagrama de Hasse acima, {x} e {x, y, z} são comparáveis, enquanto {x} e {y} não são. Uma ordem parcial em que qualquer par de elementos é comparável é chamada de ordem total e o conjunto é chamado de string . Um conjunto em que nenhum par comparável pode ser encontrado é chamado de anticadeia (por exemplo, o conjunto {{x}, {y }, {z}} na figura acima) $\ geq$

Recuperação

Dizemos que um elemento a é coberto por um elemento b, que é escrito a <: b, se a for estritamente menor que be não houver nenhum elemento c interposto entre os dois. Por exemplo, {x} é coberto por {x, z} na figura acima, mas não por {x, y, z}.

Links com complexos simpliciais

Uma classe importante de complexos simpliciais vem de conjuntos finitos parcialmente ordenados. Definimos o complexo de ordem D (P) de um conjunto finito parcialmente ordenado P como sendo o conjunto de cadeias de P. O complexo de ordem é trivialmente um complexo simplicial.

O estudo do conjunto parcialmente ordenado fornece informações sobre seu complexo de ordem e, portanto, é interessante estudar um complexo simplicial como o complexo de ordem de um conjunto parcialmente ordenado.

Operação em conjuntos parcialmente encomendados

Conjunto de produtos cartesianos parcialmente encomendado

Para eliminar a multiplicidade de relações de ordem possíveis durante um conjunto parcialmente ordenado, podemos definir três regras diferentes:

A ordem lexicográfica : ( a , b ) ≤ ( c , d ) se a < c ou ( a = c e b ≤ d );
A ordem multiplicativa : ( a , b ) ≤ ( c , d ) se a ≤ c e b ≤ d ;
O fechamento reflexivo do produto direto : ( a , b ) ≤ ( c , d ) se ( a < c e b < d ) ou ( a = c e b = d ).

Todas essas regras também se aplicam a produtos de mais de dois conjuntos parcialmente pedidos.

Finitude local

Um conjunto parcialmente ordenado E é considerado localmente finito se, para todos , o intervalo for finito. Esta suposição torna possível generalizar a fórmula de inversão de Möbius . $x, y \ em E$ $[x, y]$

Referências

(pt) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ detalhe das edições ] ( apresentação online )

Veja também