Completude (teoria da ordem) - Completeness (order theory)

Na área matemática da teoria da ordem , as propriedades de completude afirmam a existência de certos infima ou suprema de um determinado conjunto parcialmente ordenado (poset). O exemplo mais familiar é a integridade dos números reais . Um uso especial do termo refere-se a ordens parciais completas ou redes completas . No entanto, existem muitas outras noções interessantes de completude.

A motivação para considerar as propriedades de completude deriva da grande importância de suprema (mínimos limites superiores, junções , " ") e infima (maiores limites inferiores, encontra " ") para a teoria das ordens parciais. Encontrar um supremo significa destacar um elemento menos distinto do conjunto de limites superiores. Por um lado, esses elementos especiais muitas vezes incorporam certas propriedades concretas que são interessantes para a aplicação dada (como ser o mínimo múltiplo comum de um conjunto de números ou a união de uma coleção de conjuntos). Por outro lado, o conhecimento de que certos tipos de subconjuntostêm a garantia de suprema ou infima nos permite considerar o cálculo desses elementos como operações totais em um conjunto parcialmente ordenado. Por esse motivo, os posets com certas propriedades de completude podem frequentemente ser descritos como estruturas algébricas de um certo tipo. Além disso, estudar as propriedades das operações recém-obtidas produz outros assuntos interessantes.

Tipos de propriedades de completude

Todas as propriedades de completude são descritas ao longo de um esquema semelhante: uma descreve uma certa classe de subconjuntos de um conjunto parcialmente ordenado que são obrigados a ter um supremo ou um mínimo. Portanto, toda propriedade de completude tem seu dual , obtido pela inversão das definições dependentes da ordem na instrução dada. Algumas das noções geralmente não são dualizadas, enquanto outras podem ser autoduais (ou seja, equivalentes às suas afirmações duais).

Menores e maiores elementos

O exemplo mais fácil de um supremo é o vazio, ou seja, o supremo do conjunto vazio . Por definição, este é o menor elemento entre todos os elementos maiores do que cada membro do conjunto vazio. Mas este é apenas o menor elemento de todo o poset, se houver um, uma vez que o subconjunto vazio de um poset P é convencionalmente considerado como limitado por cima e por baixo, com cada elemento de P sendo um limite superior e inferior do subconjunto vazio. Outros nomes comuns para o elemento mínimo são bottom e zero (0). A noção dual, o limite inferior vazio, é o maior elemento , topo ou unidade (1).

Posets que têm um fundo são às vezes chamados de pontiagudos, enquanto os posets com topo são chamados de unitais ou com topo. Uma ordem que tem o menor e o maior elemento é limitada. No entanto, isso não deve ser confundido com a noção de completude limitada fornecida abaixo.

Completude finita

Outras condições simples de completude surgem da consideração de todos os conjuntos finitos não vazios . Uma ordem na qual todos os conjuntos finitos não vazios têm um supremo e um mínimo é chamada de rede . É suficiente exigir que todos os suprema e infima de dois elementos existam para obter todos os elementos finitos não vazios; um argumento de indução direto mostra que todo supremo / ínfimo não vazio finito pode ser decomposto em um número finito de suprema / infima binário. Assim, as operações centrais dos reticulados são suprema e infima binários . É nesse contexto que os termos atender para e ingressar para são mais comuns.

Um poset em que apenas supremas finitos não vazios são conhecidos por existir é, portanto, chamado de semilática de junção . A noção dupla é encontro-semilattice .

Outras condições de completude

A forma mais forte de completude é a existência de todo suprema e de todo infima. Os posets com esta propriedade são as redes completas . No entanto, usando a ordem dada, pode-se restringir a outras classes de subconjuntos (possivelmente infinitos), que não produzem essa completude forte de uma vez.

Se todos os subconjuntos direcionados de um poset tiverem um supremo, a ordem será uma ordem parcial completa direcionada (dcpo). Isso é especialmente importante na teoria do domínio . A noção dupla raramente considerada para um dcpo é o poset completo filtrado. Dcpos com um elemento mínimo ("dcpos pontiagudo") são um dos significados possíveis da frase ordem parcial completa (cpo).

Se cada subconjunto com algum limite superior também tiver um limite superior mínimo, o respectivo poset será chamado de limite completo . O termo é amplamente usado com esta definição que se concentra na suprema e não há um nome comum para a propriedade dual. No entanto, a integridade limitada pode ser expressa em termos de outras condições de integridade que são facilmente dualizadas (veja abaixo). Embora os conceitos com os nomes "completo" e "limitado" já tenham sido definidos, é improvável que ocorra confusão, uma vez que raramente se falaria de um "poset completo limitado" ao significar um "cpo limitado" (que é apenas um "cpo com o maior elemento "). Da mesma forma, "rede completa limitada" é quase inequívoca, uma vez que não se declararia a propriedade de limite para redes completas, onde está implícita de qualquer maneira. Observe também que o conjunto vazio geralmente tem limites superiores (se o poset não for vazio) e, portanto, um poset completo limitado tem um elemento mínimo.

Também se pode considerar os subconjuntos de um poset que são totalmente ordenados , ou seja, as cadeias . Se todas as cadeias tiverem um supremo, a ordem é chamada de cadeia completa . Novamente, esse conceito raramente é necessário na forma dual.

Relações entre propriedades de completude

Já foi observado que encontros / junções binários geram todos os encontros / junções finitos não vazios. Da mesma forma, muitas outras (combinações) das condições acima são equivalentes.

  • O exemplo mais conhecido é a existência de todo suprema, o que equivale, na verdade, à existência de todo infima, desde que exista um fundo. De fato, para qualquer subconjunto X de um poset, pode-se considerar seu conjunto de limites inferiores B , que não está vazio, pois contém pelo menos o fundo. O supremo de B é então igual ao ínfimo de X : uma vez que cada elemento de X é um limite superior de B , sup  B é menor do que todos os elementos de X , ou seja, sup  B é em B . É o maior elemento de B e, consequentemente, o ínfimo de X . De maneira dual, a existência de todos os infima implica a existência de todos os suprema.
  • A integridade limitada também pode ser caracterizada de maneira diferente. Por um argumento semelhante ao anterior, descobre-se que o supremo de um conjunto com limites superiores é o ínfimo do conjunto de limites superiores. Conseqüentemente, completude limitada é equivalente à existência de todos os infima não vazios.
  • Um poset é uma rede completa se e somente se for um cpo e uma junção-semilática. Na verdade, para qualquer subconjunto X , o conjunto de todos suprema finito (junta) de X é dirigido e o supremo deste conjunto (que existe por completude dirigida) é igual ao supremo de X . Assim, cada conjunto tem um supremo e, pela observação acima, temos uma rede completa. A outra direção da prova é trivial.
  • Assumindo o axioma de escolha , um poset é uma cadeia completa se e somente se for um dcpo.

Completude em termos de álgebra universal

Conforme explicado acima, a presença de certas condições de completude permite considerar a formação de certos suprema e infima como operações totais de um conjunto parcialmente ordenado. Acontece que em muitos casos é possível caracterizar a completude apenas considerando estruturas algébricas apropriadas no sentido de álgebra universal , que são equipadas com operações como ou . Ao impor condições adicionais (na forma de identidades adequadas ) a essas operações, pode-se então derivar a ordem parcial subjacente exclusivamente de tais estruturas algébricas. Detalhes sobre essa caracterização podem ser encontrados nos artigos sobre as estruturas "semelhantes a reticulados" para os quais isso é normalmente considerado: consulte semilattice , reticulado , álgebra de Heyting e álgebra booleana . Observe que as duas últimas estruturas estendem a aplicação desses princípios além de meros requisitos de completude, introduzindo uma operação adicional de negação .

Completude em termos de complementos

Outra maneira interessante de caracterizar propriedades de completude é fornecida através do conceito de conexões de Galois (monótonas) , isto é, adjunções entre ordens parciais. Na verdade, essa abordagem oferece insights adicionais sobre a natureza de muitas propriedades de completude e sobre a importância das conexões de Galois para a teoria da ordem. A observação geral em que esta reformulação da completude se baseia é que a construção de certos suprema ou infima fornece partes adjacentes esquerda ou direita de conexões de Galois adequadas.

Considere um conjunto parcialmente ordenado ( X , ≤). Como um primeiro exemplo simples, seja 1 = {*} um conjunto de um elemento especificado com a única ordenação parcial possível. Há um mapeamento óbvio J : X → 1 com j ( x ) = * para todos os x em X . X tem um elemento menos se e apenas se a função j tem um adjunto inferior j * : 1 → X . De fato, a definição para conexões de Galois resulta em que, neste caso, j * (*) ≤ x se e somente se * ≤ j ( x ), onde o lado direito obviamente vale para qualquer x . Dualmente, a existência de um adjunto superior para j é equivalente a X tendo um elemento maior.

Outro mapeamento simples é a função q : X → X × X dada por q ( x ) = ( x , x ). Naturalmente, a relação de pedido pretendida para X × X é apenas o pedido de produto usual . q tem um q adjunto inferior * se e somente se todas as junções binárias em X existirem. Por outro lado, a operação de junção : X × X → X pode sempre fornecer o adjunto inferior (necessariamente único) para q . Dualmente, q permite um adjunto superior se, e somente se, X tiver todas as conexões binárias. Assim, a operação de encontro , se existir, é sempre um adjunto superior. Se ambos e existem e, além disso, também é um adjunto inferior, então o poset X é uma álgebra de Heyting - outra classe especial importante de ordens parciais.

Outras declarações de completude podem ser obtidas explorando procedimentos de completação adequados . Por exemplo, é bem conhecido que a coleção de todos os conjuntos inferiores de um poset X , ordenados por inclusão de subconjunto , produz uma rede completa D ( X ) (a rede de redução). Além disso, há uma incorporação óbvia e : X → D ( X ) que mapeia cada elemento x de X para seu ideal principal { y em X | y ≤ x }. Uma pequena reflexão agora mostra que e tem um adjunto inferior se e somente se X for uma rede completa. Na verdade, este adjunto inferior irá mapear todo o conjunto inferior de X ao seu supremo em X . Compor este com a função que mapeia qualquer subconjunto de X para o seu fecho inferior (mais uma vez uma adjunção a inclusão de conjuntos inferiores no powerset ), obtém-se o mapa supremum usual a partir do powerset 2 X a X . Como antes, outra situação importante ocorre sempre que este mapa supremo também é um adjunto superior: neste caso, a rede completa X é construtivamente completamente distributiva . Veja também os artigos sobre distributividade e distributividade completas (teoria da ordem) .

As considerações nesta seção sugerem uma reformulação da (partes da) teoria da ordem em termos da teoria das categorias , onde as propriedades são geralmente expressas por referência às relações ( morfismos , mais especificamente: adjunções) entre objetos, em vez de considerar sua estrutura interna. Para obter considerações mais detalhadas sobre essa relação, consulte o artigo sobre a formulação categórica da teoria da ordem .

Veja também

Notas


Referências

  • G. Markowsky e BK Rosen. Bases para posets completos em cadeia IBM Journal of Research and Development. Março de 1976.
  • Stephen Bloom. Variedades de álgebras ordenadas Journal of Computer and System Sciences. Outubro de 1976.
  • Michael Smyth. Domínios de poder Journal of Computer and System Sciences. 1978.
  • Daniel Lehmann. Na álgebra da ordem Journal of Computer and System Sciences. Agosto de 1980.