Participe e conheça - Join and meet

Relações binárias transitivas
Simétrico Anti-simétrico Conectado Bem fundado Tem junções Tem encontros Reflexivo Irreflexive Assimétrico Também conhecido como: Total, Semiconnex Anti-reflexivo Relação de equivalência Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Pré-encomenda (quase ordem) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Pré-encomenda total ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Ordem total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Quase ordenado ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Bem ordenado ✗ Y Y Y ✗ ✗ Y ✗ ✗ Malha ✗ Y ✗ ✗ Y Y Y ✗ ✗ Unir-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Ordem parcial estrita ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Ordem estrita fraca ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Pedido total estrito ✗ ✗ Y ✗ ✗ ✗ ✗ Y Y Simétrico Anti-simétrico Conectado Bem fundado Tem junções Tem encontros Reflexivo Irreflexive Assimétrico Definições: ${\ displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b \, {\ text {e}} \, S \ neq \ varnothing:}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$ ${\ displaystyle \ scriptstyle {aRb \, {\ text {e}} \, bRa \ Rightarrow a = b}}$ ${\ displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {ou}} \, bRa}}$ ${\ displaystyle \ scriptstyle {\ min S \, {\ text {existe}}}}$ ${\ displaystyle \ scriptstyle {a \ vee b \, {\ text {existe}}}}$ ${\ displaystyle \ scriptstyle {a \ wedge b \, {\ text {existe}}}}$ ${\ displaystyle \ scriptstyle {aRa}}$ ${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$ ${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$
Todas as definições exigem tacitamente que a relação homogênea seja transitiva : Um " " indica que a propriedade da coluna é exigida pela definição do termo da linha (à esquerda). Por exemplo, a definição de uma relação de equivalência requer que ela seja simétrica. Listadas aqui estão propriedades adicionais que uma relação homogênea pode satisfazer. ${\ displaystyle R}$${\ displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b, c, {\ text {if}} aRb {\ text {e}} bRc {\ text {then}} aRc}.}$ Y

Em matemática , especificamente na teoria da ordem , a junção de um subconjunto de um conjunto parcialmente ordenado é o supremo (menor limite superior) de denotado e, da mesma forma, o encontro de é o ínfimo (maior limite inferior), denotado. Em geral, a junção e encontro de um subconjunto de um conjunto parcialmente ordenado não precisa existir. Unir e conhecer são duais entre si no que diz respeito à inversão de ordem. ${\ displaystyle S}$ ${\ displaystyle P}$${\ displaystyle S,}$${\ displaystyle \ vee S,}$${\ displaystyle S}$${\ displaystyle \ wedge S.}$

Um conjunto parcialmente ordenado no qual todos os pares têm uma junção é uma semilattice de junção . Dualmente, um conjunto parcialmente ordenado em que todos os pares se encontram é um encontro-semilattice . Um conjunto parcialmente ordenado que é uma semilattice de junção e uma semilattice de encontro é uma rede . Uma rede na qual cada subconjunto, não apenas todos os pares, possui um encontro e uma junção é uma rede completa . Também é possível definir uma rede parcial , na qual nem todos os pares têm um encontro ou junção, mas as operações (quando definidas) satisfazem certos axiomas.

A junção / encontro de um subconjunto de um conjunto totalmente ordenado é simplesmente seu elemento máximo / mínimo, se tal elemento existir.

Se um subconjunto de um conjunto parcialmente ordenado também for um conjunto direcionado (para cima) , sua junção (se existir) será chamada de junção direcionada ou supremo direcionado . Dualmente, se é um conjunto direcionado para baixo, então seu encontro (se existir) é um encontro direcionado ou ínfimo direcionado . ${\ displaystyle S}$${\ displaystyle P}$${\ displaystyle S}$

Abordagem de pedido parcial

Let Ser um conjunto com uma ordem parcial e deixe Um elemento de é o${\ displaystyle A}$ ${\ displaystyle \, \ leq, \,}$${\ displaystyle x, y \ in A.}$${\ displaystyle z}$${\ displaystyle A}$ conhecer (oumaior limite inferior ouinfimum ) dese as duas condições a seguir forem satisfeitas: ${\ displaystyle x {\ text {e}} y}$

1. ${\ displaystyle z \ leq x {\ text {e}} z \ leq y}$(isto é, é um limite inferior de ).${\ displaystyle z}$${\ displaystyle x {\ text {e}} y}$
2. Para qualquer se então (isto é, é maior ou igual a qualquer outro limite inferior de ).${\ displaystyle w \ in A,}$${\ displaystyle w \ leq x {\ text {e}} w \ leq y,}$${\ displaystyle w \ leq z}$${\ displaystyle z}$${\ displaystyle x {\ text {e}} y}$

Se houver um encontro de, então ele é único, pois se ambos são os maiores limites inferiores de então e, portanto, se o encontro existe, é denotado Alguns pares de elementos em podem não ter um encontro, uma vez que eles não têm nenhum limite inferior , ou uma vez que nenhum de seus limites inferiores é maior do que todos os outros. Se todos os pares de elementos de ter um encontro, em seguida, o encontro é uma operação binária sobre e é fácil ver que esta operação cumpra os seguintes três condições: Para quaisquer elementos${\ displaystyle x {\ text {e}} y,}$${\ displaystyle z {\ text {e}} z ^ {\ prime}}$${\ displaystyle x {\ text {e}} y,}$${\ displaystyle z \ leq z ^ {\ prime} {\ text {e}} z ^ {\ prime} \ leq z,}$${\ displaystyle z = z ^ {\ prime}.}$${\ displaystyle x \ wedge y.}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A,}$${\ displaystyle x, y, z \ in A,}$

1. ${\ displaystyle x \ wedge y = y \ wedge x}$( comutatividade ),
2. ${\ displaystyle x \ wedge (y \ wedge z) = (x \ wedge y) \ wedge z}$( associatividade ), e
3. ${\ displaystyle x \ wedge x = x}$( idempotência ).

As junções são definidas duplamente com a junção de, se existir, denotado por Um elemento de é o ${\ displaystyle x {\ text {e}} y,}$${\ displaystyle x \ vee y.}$${\ displaystyle j}$${\ displaystyle A}$junte-se (oumínimo limite superior ousupremum ) deemse as seguintes duas condições forem satisfeitas: ${\ displaystyle x {\ text {e}} y}$${\ displaystyle A}$

1. ${\ displaystyle x \ leq j {\ text {e}} y \ leq j}$(isto é, é um limite superior de ).${\ displaystyle j}$${\ displaystyle x {\ text {e}} y}$
2. Para qualquer se então (isto é, é menor ou igual a qualquer outro limite superior de ).${\ displaystyle w \ in A,}$${\ displaystyle x \ leq w {\ text {e}} y \ leq w,}$${\ displaystyle j \ leq w}$${\ displaystyle j}$${\ displaystyle x {\ text {e}} y}$

Se nem todos os pares de elementos de tiverem um encontro (respectivamente, junção), então o encontro (respectivamente, junção) ainda pode ser visto como uma operação binária parcial em${\ displaystyle A}$${\ displaystyle A.}$

Abordagem de álgebra universal

Por definição, uma operação binária em um conjunto é um meet se satisfizer as três condições a , b e c . O par é então um encontro-semilattice . Além disso, podemos então definir uma relação binária em A , declarando que se e somente se De fato, essa relação é uma ordem parcial em De fato, para quaisquer elementos${\ displaystyle \, \ wedge \,}$${\ displaystyle A}$${\ displaystyle (A, \ wedge)}$ ${\ displaystyle \, \ leq \,}$${\ displaystyle x \ leq y}$${\ displaystyle x \ wedge y = x.}$${\ displaystyle A.}$${\ displaystyle x, y, z \ in A,}$

• ${\ displaystyle x \ leq x,}$já por c ;${\ displaystyle x \ wedge x = x}$
• se então por um ; e${\ displaystyle x \ leq y {\ text {e}} y \ leq x}$${\ displaystyle x = x \ wedge y = y \ wedge x = y}$
• se então, desde então por b .${\ displaystyle x \ leq y {\ text {e}} y \ leq z}$${\ displaystyle x \ leq z}$${\ displaystyle x \ wedge z = (x \ wedge y) = y \ wedge z = x \ wedge (y \ wedge z) = x \ wedge y = x}$

Ambas as reuniões e junções satisfazem igualmente esta definição: algumas operações associadas de reunião e junção geram ordens parciais que são inversas uma da outra. Ao escolher uma dessas ordens como principais, também se fixa qual operação é considerada reunião (aquela que dá a mesma ordem) e qual é considerada junção (a outra).

Equivalência de abordagens

Se for um conjunto parcialmente ordenado , de modo que cada par de elementos em tem um encontro, então, de fato, se e somente se, no último caso, de fato é um limite inferior de e já que é o maior limite inferior se e somente se for um limite inferior vinculado. Assim, a ordem parcial definida pelo encontro na abordagem da álgebra universal coincide com a ordem parcial original. ${\ displaystyle (A, \ leq)}$${\ displaystyle A}$${\ displaystyle x \ wedge y = x}$${\ displaystyle x \ leq y,}$${\ displaystyle x}$${\ displaystyle x {\ text {e}} y,}$${\ displaystyle x}$

Por outro lado, se é um encontro-semilattice , e a ordem parcial é definida como na abordagem de álgebra universal, e para alguns elementos, então, é o maior limite inferior de em relação a desde ${\ displaystyle (A, \ wedge)}$${\ displaystyle \, \ leq \,}$${\ displaystyle z = x \ wedge y}$${\ displaystyle x, y \ in A,}$${\ displaystyle z}$${\ displaystyle x {\ text {e}} y}$${\ displaystyle \, \ leq, \,}$

e, portanto , da mesma forma, e se é outro limite inferior de então de onde ${\ displaystyle z \ leq x.}$${\ displaystyle z \ leq y,}$${\ displaystyle w}$${\ displaystyle x {\ text {e}} y,}$${\ displaystyle w \ wedge x = w \ wedge y = w,}$ Assim, há uma reunião definida pela ordem parcial definida pela reunião original, e as duas reuniões coincidem.

Em outras palavras, as duas abordagens geram conceitos essencialmente equivalentes, um conjunto equipado tanto com uma relação binária quanto com uma operação binária, de modo que cada uma dessas estruturas determina a outra e preenche as condições para pedidos ou atendimentos parciais, respectivamente.

Reúne subconjuntos gerais

Se for um encontro-semilático, então o encontro pode ser estendido para um encontro bem definido de qualquer conjunto finito não vazio , pela técnica descrita em operações binárias iteradas . Alternativamente, se o encontro define ou é definido por uma ordem parcial, alguns subconjuntos de , de fato, têm infima com respeito a isso, e é razoável considerar um mínimo como o encontro do subconjunto. Para subconjuntos finitos não vazios, as duas abordagens geram o mesmo resultado e, portanto, qualquer uma delas pode ser considerada uma definição de encontro. No caso em que cada subconjunto de tem um encontro, na verdade é uma rede completa ; para obter detalhes, consulte completude (teoria da ordem) . ${\ displaystyle (A, \ wedge)}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle (A, \ leq)}$

Notas

Referências