Malha (ordem)

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Uma rede é uma estrutura abstrata estudada nas subdisciplinas matemáticas da teoria da ordem e da álgebra abstrata . Consiste em um conjunto parcialmente ordenado em que cada par de elementos tem um único supremo (também chamado de limite superior mínimo ou junção ) e um único ínfimo (também chamado de limite inferior máximo ou encontro ). Um exemplo é dado pelo conjunto potência de um conjunto, parcialmente ordenado por inclusão , para o qual o supremo é a união e o ínfimo é a interseção . Outro exemplo é dado pelonúmeros naturais , parcialmente ordenados por divisibilidade , para os quais o supremo é o mínimo múltiplo comum e o ínfimo é o máximo divisor comum .

As redes também podem ser caracterizadas como estruturas algébricas que satisfazem certas identidades axiomáticas . Como as duas definições são equivalentes, a teoria da rede baseia-se tanto na teoria da ordem quanto na álgebra universal . Semilattices incluem reticulados, que por sua vez incluem Heyting e álgebras booleanas . Todas essas estruturas tipo treliça admitem descrições teóricas de ordem e também descrições algébricas.

Definição

Uma rede pode ser definida teoricamente como um conjunto parcialmente ordenado ou como uma estrutura algébrica.

Como conjunto parcialmente ordenado

Um conjunto parcialmente ordenado (poset)é chamado de reticulado se for ao mesmo tempo um join- e um meet - semi -lattice , ou seja, cada subconjunto de dois elementostem uma junção (ou seja, o menor limite superior, denotado por) e duplamente um encontro (ou seja, o maior limite inferior, denotado por). Essa definição faze operações binárias . Ambas as operações são monótonas em relação à ordem dada:eimplica quee

Segue-se por um argumento de indução que todo subconjunto finito não vazio de uma rede tem um limite superior mínimo e um limite inferior máximo. Com suposições adicionais, outras conclusões podem ser possíveis; veja Completude (teoria da ordem) para mais discussão sobre este assunto. Esse artigo também discute como se pode reformular a definição acima em termos da existência de conexões de Galois adequadas entre conjuntos parcialmente ordenados relacionados – uma abordagem de interesse especial para a abordagem teórica de categorias para reticulados e para a análise formal de conceitos .

Dado um subconjunto de uma rede,atender e unir restrito a funções parciais – elas são indefinidas se seu valor não estiver no subconjuntoA estrutura resultante emé chamado derede parcial . Além dessa definição extrínseca como um subconjunto de alguma outra estrutura algébrica (uma rede), uma rede parcial também pode ser definida intrinsecamente como um conjunto com duas operações binárias parciais que satisfazem certos axiomas. [1]

Como estrutura algébrica

Uma rede é uma estrutura algébrica , composto por um conjuntoe duas operações binárias, comutativas e associativas eemsatisfazendo as seguintes identidades axiomáticas para todos os elementos(às vezes chamado de leis de absorção ):

As duas identidades a seguir também são geralmente consideradas como axiomas, embora decorram das duas leis de absorção tomadas em conjunto. [2] Estas são chamadas de leis idempotentes .

Esses axiomas afirmam que ambosesão semi- reticulados . As leis de absorção, os únicos axiomas acima em que ambos se encontram e se unem, distinguem uma rede de um par arbitrário de estruturas semi-reticuladas e asseguram que as duas semi-redes interagem adequadamente. Em particular, cada semi-reticulado é o dual do outro. As leis de absorção podem ser vistas como um requisito para que as semi-redes de encontro e junção definam a mesma ordem parcial .

Conexão entre as duas definições

Uma rede teórica de ordem dá origem às duas operações bináriaseComo as leis comutativa, associativa e de absorção podem ser facilmente verificadas para essas operações, elas tornamem uma rede no sentido algébrico.

A recíproca também é verdadeira. Dada uma rede definida algebricamentepode-se definir uma ordem parcialemdefinindo

para todos os elementosAs leis da absorção garantem que ambas as definições sejam equivalentes:

e duplamente para a outra direção.

Pode-se agora verificar que a relação ≤ introduzida desta forma define uma ordenação parcial dentro da qual os encontros binários e as junções são dadas através das operações originaise

Uma vez que as duas definições de uma rede são equivalentes, pode-se invocar livremente os aspectos de qualquer definição de qualquer maneira que satisfaça o propósito em questão.

Rede limitada

Uma rede limitada é uma rede que possui adicionalmente um elemento máximo (também chamado de elemento máximo ou elemento superior e denotado por 1 ou por) e um elemento mínimo (também chamado de mínimo , ou fundo , denotado por 0 ou por), que satisfaz

Uma rede limitada também pode ser definida como uma estrutura algébrica da formade tal modo queé uma grade,(a parte inferior da treliça) é o elemento de identidade para a operação de junçãoe(o topo da treliça) é o elemento de identidade para a operação de encontro

Um conjunto parcialmente ordenado é uma rede limitada se e somente se todo conjunto finito de elementos (incluindo o conjunto vazio) tem uma junção e um encontro. Para cada elementode um poset é vagamente verdade que e e, portanto, cada elemento de um poset é tanto um limite superior quanto um limite inferior do conjunto vazio. Isso implica que a junção de um conjunto vazio é o menor elementoe o encontro do conjunto vazio é o maior elementoIsso é consistente com a associatividade e comutatividade de encontrar e unir: a união de uma união de conjuntos finitos é igual à união das uniões dos conjuntos e, dualmente, a união de uma união de conjuntos finitos é igual à união de conjuntos finitos. os encontros dos conjuntos, isto é, para subconjuntos finitosde um poset

e
espera. Tomando B como o conjunto vazio,
e

o que está de acordo com o fato de que

Cada rede pode ser incorporada em uma rede limitada adicionando um elemento maior e um menor. Além disso, toda rede finita não vazia é limitada, tomando a junção (respectivamente, encontro) de todos os elementos, denotada por(respectivamente) Ondeé o conjunto de todos os elementos.

Conexão com outras estruturas algébricas

As redes têm algumas conexões com a família de estruturas algébricas semelhantes a grupos . Como o encontro e a junção comutam e associam, uma rede pode ser vista como consistindo de dois semigrupos comutativos com o mesmo domínio. Para uma rede limitada, esses semigrupos são de fato monóides comutativos . A lei de absorção é a única identidade definidora que é peculiar à teoria da rede.

Por comutatividade, associatividade e idempotência pode-se pensar em juntar e encontrar como operações em conjuntos finitos não vazios, ao invés de pares de elementos. Em uma rede limitada, a junção e o encontro do conjunto vazio também podem ser definidos (comoerespectivamente). Isso torna os reticulados limitados um pouco mais naturais do que os reticulados gerais, e muitos autores exigem que todos os reticulados sejam delimitados.

A interpretação algébrica de reticulados desempenha um papel essencial na álgebra universal .

Exemplos

  • Para qualquer conjuntoa coleção de todos os subconjuntos de(chamado conjunto de potência de) pode ser ordenado via inclusão de subconjunto para obter uma rede limitada porpróprio e o conjunto vazio. Definir interseção e definir união interpretar conhecer e unir, respectivamente (veja a Figura 1).
  • Para qualquer conjuntoa coleção de todos os subconjuntos finitos deordenada por inclusão, também é uma rede, e será limitada se e somente seé finito.
  • Para qualquer conjuntoa coleta de todas as partições deordenada por refinamento , é uma rede (ver Fig. 3).
  • Os inteiros positivos em sua ordem usual formam uma rede, sob as operações de "min" e "max". 1 é inferior; não há topo (ver Fig. 4).
  • O quadrado cartesiano dos números naturais, ordenados de modo queE seO paré o elemento inferior; não há topo (ver Fig. 5).
  • Os números naturais também formam uma rede sob as operações de tomar o máximo divisor comum e o mínimo múltiplo comum , com divisibilidade como a relação de ordem:E sedivide é inferior;eu paro. Foto. 2 mostra uma sub-rede finita.
  • Cada rede completa (veja também abaixo ) é uma rede limitada (bastante específica). Esta aula dá origem a uma ampla gama de exemplos práticos .
  • O conjunto de elementos compactos de um reticulado aritmético completo é um reticulado com um elemento mínimo, onde as operações do reticulado são dadas restringindo-se as respectivas operações do reticulado aritmético. Esta é a propriedade específica que distingue reticulados aritméticos de reticulados algébricos , para os quais os compactos formam apenas uma junção-semilattice . Ambas as classes de reticulados completos são estudadas na teoria do domínio .

Outros exemplos de reticulados são dados para cada uma das propriedades adicionais discutidas abaixo.

Exemplos de não-reticulados

Foto. 8: poset sem treliça:etêm limites inferiores comunsemas nenhum deles é o maior limite inferior .
Foto. 7: poset sem treliça:etêm limites superiores comunsemas nenhum deles é o menor limite superior .
Foto. 6: poset sem treliça:enão possuem limite superior comum.

A maioria dos conjuntos parcialmente ordenados não são reticulados, incluindo os seguintes.

  • Um poset discreto, significando um poset tal queimplicaé uma rede se e somente se tem no máximo um elemento. Em particular, o poset discreto de dois elementos não é uma treliça.
  • Embora o conjuntoparcialmente ordenado por divisibilidade é uma rede, o conjuntoassim ordenado não é uma rede porque o par 2, 3 não possui uma junção; da mesma forma, 2, 3 não tem um encontro em
  • O conjuntoparcialmente ordenado por divisibilidade não é uma rede. Cada par de elementos tem um limite superior e um limite inferior, mas o par 2, 3 tem três limites superiores, ou seja, 12, 18 e 36, nenhum dos quais é o menor dos três sob divisibilidade (12 e 18 não dividem uns aos outros). Da mesma forma, o par 12, 18 tem três limites inferiores, a saber, 1, 2 e 3, nenhum dos quais é o maior daqueles três sob divisibilidade (2 e 3 não se dividem).

Morfismos de reticulados

Foto. 9: Mapa monotônicoentre reticulados que não preserva nem junções nem encontros, uma vez que e

A noção apropriada de um morfismo entre duas redes flui facilmente da definição algébrica acima . Dadas duas malhaseum homomorfismo de rede de L para M é uma funçãotal que para todos

portantoé um homomorfismo das duas semi- reticulados subjacentes . Quando reticulados com mais estrutura são considerados, os morfismos devem "respeitar" a estrutura extra também. Em particular, um homomorfismo de rede limitada (geralmente chamado apenas de "homomorfismo de rede")entre duas redes limitadasetambém deve ter a seguinte propriedade:

Na formulação teórica de ordem, essas condições apenas afirmam que um homomorfismo de reticulados é uma função que preserva encontros e junções binários. Para reticulados limitados, a preservação dos menores e maiores elementos é apenas a preservação da junção e encontro do conjunto vazio.

Qualquer homomorfismo de reticulados é necessariamente monótono em relação à relação de ordenação associada; veja Função de preservação de limite . A recíproca não é verdadeira: a monotonicidade de modo algum implica a preservação exigida de encontros e junções (veja a Figura 9), embora uma bijeção que preserva a ordem seja um homomorfismo se sua inversa também for preservadora da ordem.

Dada a definição padrão de isomorfismos como morfismos invertíveis, um isomorfismo de rede é apenas um homomorfismo de rede bijetivo . Da mesma forma, um endomorfismo de reticulado é um homomorfismo de reticulado de um reticulado para si mesmo, e um automorfismo de reticulado é um endomorfismo de reticulado bijetivo. As redes e seus homomorfismos formam uma categoria .

Deixareser duas redes com 0 e 1 . Um homomorfismo deparaé chamado 0,1 - separando se e somente se (separa 0 ) e(separa 1).

Sub -redes

Uma sub -rede de uma redeé um subconjunto deque é uma treliça com as mesmas operações de encontro e junção que Ou seja, seé uma grade eé um subconjunto detal que para cada par de elementosAmbaseestão dentroentãoé uma sub-rede de[3]

Uma sub-redede uma treliçaé uma sub- rede convexa deE seeimplica quepertence apara todos os elementos

Propriedades das redes

Apresentamos agora uma série de propriedades importantes que levam a classes especiais interessantes de reticulados. Uma, a limitação, já foi discutida.

Completude

Um poset é chamado de rede completa se todos os seus subconjuntos tiverem uma junção e uma reunião. Em particular, toda rede completa é uma rede limitada. Enquanto homomorfismos de reticulados limitados em geral preservam apenas junções e encontros finitos, homomorfismos de reticulados completos são necessários para preservar junções e encontros arbitrários.

Todo poset que é uma semi-rede completa também é uma rede completa. Relacionado a este resultado está o fenômeno interessante de que existem várias noções concorrentes de homomorfismo para essa classe de posets, dependendo se eles são vistos como reticulados completos, semi-reticulados completos, semi-semilattices completos, ou como join-complete ou meet- treliças completas.

Observe que "rede parcial" não é o oposto de "rede completa" - em vez disso, "rede parcial", "rede" e "rede completa" são definições cada vez mais restritivas.

Completude condicional

Uma rede condicionalmente completa é uma rede na qual todo subconjunto não vazio que tem um limite superior tem uma junção (ou seja, um limite superior mínimo). Tais reticulados fornecem a generalização mais direta do axioma da completude dos números reais . Um reticulado condicionalmente completo é um reticulado completo ou um reticulado completo sem seu elemento máximoseu elemento mínimoou ambos.

Distributividade

Foto. 11: Menor rede não modular (e, portanto, não distributiva) N 5 .
Os elementos rotulados violam a equação de distributividademas satisfaça sua dupla
Foto. 10: Menor rede não distributiva (mas modular) M 3 .

Como os reticulados vêm com duas operações binárias, é natural perguntar se uma delas se distribui sobre a outra, ou seja, se uma ou outra das seguintes leis duais vale para cada três elementos:

Distributividade desobre

Distributividade desobre

Uma rede que satisfaz o primeiro ou, equivalentemente (como se vê), o segundo axioma, é chamada de rede distributiva . As únicas redes não distributivas com menos de 6 elementos são chamadas de M 3 e N 5 ; [4] elas são mostradas nas Figuras 10 e 11, respectivamente. Uma rede é distributiva se e somente se ela não tem uma sub -rede isomórfica a M 3 ou N 5 . [5] Cada rede distributiva é isomórfica a uma rede de conjuntos (com união e interseção como junção e encontro, respectivamente). [6]

Para uma visão geral das noções mais fortes de distributividade que são apropriadas para reticulados completos e que são usadas para definir classes mais especiais de reticulados, como quadros e reticulados completamente distributivos , veja distributividade na teoria da ordem .

Modularidade

Para algumas aplicações, a condição de distributividade é muito forte e a propriedade mais fraca a seguir é frequentemente útil. Uma treliçaé modular se, para todos os elementosvale a seguinte identidade: ( Identidade modular )
Esta condição é equivalente ao seguinte axioma: implica( Lei modular )
Uma rede é modular se e somente se ela não tem uma sub -rede isomórfica a N 5 (mostrada na Figura 11). [5] Além de reticulados distributivos, exemplos de reticulados modulares são o reticulado de ideais bilaterais de um anel , o reticulado de submódulos de um módulo , e o reticulado de subgrupos normais de um grupo . O conjunto de termos de primeira ordem com a ordenação "é mais específico que" é uma rede não modular usada no raciocínio automatizado .

Semimodularidade

Uma rede finita é modular se, e somente se, é semimodular superior e inferior . Para uma rede graduada, a semimodularidade (superior) é equivalente à seguinte condição na função de classificação

Outra condição equivalente (para grades graduadas) é a condição de Birkhoff :

para cadaedentroE seeambos cobrementãoabrange tantoe

Uma rede é chamada de semimodular inferior se a sua dual for semimodular. Para redes finitas, isso significa que as condições anteriores são válidas cometrocado, "cobre" trocado por "está coberto por", e as desigualdades revertidas. [7]

Continuidade e algebraicidade

Na teoria do domínio , é natural procurar aproximar os elementos em uma ordem parcial por elementos "muito mais simples". Isso leva à classe de posets contínuos , consistindo em posets onde cada elemento pode ser obtido como o supremo de um conjunto direcionado de elementos que estão muito abaixo do elemento. Se pudermos restringi-los adicionalmente aos elementos compactos de um poset para obter esses conjuntos direcionados, então o poset é mesmo algébrico . Ambos os conceitos podem ser aplicados a reticulados da seguinte forma:

  • Uma rede contínua é uma rede completa que é contínua como um poset.
  • Uma rede algébrica é uma rede completa que é algébrica como um poset.

Ambas as classes têm propriedades interessantes. Por exemplo, reticulados contínuos podem ser caracterizados como estruturas algébricas (com operações infinitárias) que satisfazem certas identidades. Embora tal caracterização não seja conhecida para redes algébricas, elas podem ser descritas "sintaticamente" por meio de sistemas de informação de Scott .

Complementos e pseudo-complementos

Deixarser uma rede limitada com maior elemento 1 e menor elemento 0. Dois elementosedosão complementares se e somente se:

Em geral, alguns elementos de uma rede limitada podem não ter um complemento e outros podem ter mais de um complemento. Por exemplo, o conjuntocom sua ordenação usual é uma rede limitada, enão tem complemento. Na rede limitada N 5 , o elementotem dois complementos, viz.e(ver Fig. 11). Uma rede limitada para a qual cada elemento tem um complemento é chamada de rede complementada .

Uma rede complementada que também é distributiva é uma álgebra booleana . Para uma rede distributiva, o complemento dequando existe, é único.

No caso do complemento ser único, escrevemos ¬ x = y e equivalentemente, ¬ y = x . A operação unária correspondente sobrechamada complementação, introduz um análogo da negação lógica na teoria da rede.

As álgebras de Heyting são um exemplo de redes distributivas onde alguns membros podem não ter complementos. Cada elementode uma álgebra de Heyting tem, por outro lado, um pseudo-complemento , também denotado ¬ x . O pseudo-complemento é o maior elementode tal modo queSe o pseudo-complemento de cada elemento de uma álgebra de Heyting é de fato um complemento, então a álgebra de Heyting é de fato uma álgebra booleana.

Condição da cadeia Jordan–Dedekind

Uma cadeia deparaé um conjuntoOnde O comprimento desta cadeia é n , ou um a menos que seu número de elementos. Uma cadeia é máxima secobrepara todos

Se para qualquer par,eOndetodas as cadeias máximas deparatêm o mesmo comprimento, diz-se que a rede satisfaz a condição da cadeia de Jordan-Dedekind .

Classificada/classificada

Uma treliçaé chamado graded , às vezes rankeado (mas veja poset ranqueado para um significado alternativo), se puder ser equipado com uma função rank às vezes até ℤ, compatível com o pedido (assimsempre que) tal que sempre que cobre então O valor da função de posto para um elemento de rede é chamado de posto .

Um elemento de redediz-se que cobre outro elementoE semas não existe umde tal modo que Aqui,meiose

Grades livres

Qualquer conjuntopode ser usado para gerar a semi-rede livre A semi-rede livre é definida para consistir em todos os subconjuntos finitos decom a operação semi-reticulada dada pela união comum de conjuntos . A semi-rede livre tem a propriedade universal . Para a rede livre sobre um conjunto Whitman deu uma construção baseada em polinômios sobremembros . [8] [9]

Noções importantes da teoria da rede

Agora definimos algumas noções teóricas de ordem de importância para a teoria da rede. A seguir, deixeser um elemento de alguma redeSetem um elemento inferior às vezes é necessário.é chamado:

  • Junte-se irredutível seimplicapara todosQuando a primeira condição é generalizada para junções arbitrárias é chamado de junção completamente irredutível (ou-irredutível). A noção dual é encontrar irredutibilidade (-irredutível). Por exemplo, na foto. 2, os elementos 2, 3, 4 e 5 são irredutíveis de junção, enquanto 12, 15, 20 e 30 são irredutíveis de encontro. Na rede de números reais com a ordem usual, cada elemento é irredutível de junção, mas nenhum é completamente irredutível de junção.
  • Junte-se ao prime seimplicaIsso também pode ser generalizado para obter a noção de junção completa de primos . A noção dual é atender primo . Todo elemento join-prime também é irredutível, e todo elemento meet-prime também é irredutível. A recíproca vale seé distributiva.

Deixartem um elemento inferior 0. Um elementodoé um átomo see não existe nenhum elementode tal modo queEntãoé chamado:

  • Se atômico para todo elemento diferente de zerodoexiste um átomodode tal modo que
  • Atomística se cada elemento deé um supremo de átomos.

As noções de ideais e a noção dual de filtros referem-se a tipos particulares de subconjuntos de um conjunto parcialmente ordenado e, portanto, são importantes para a teoria da rede. Os detalhes podem ser encontrados nas respectivas entradas.

Veja também

Aplicações que usam a teoria da rede

Observe que em muitas aplicações os conjuntos são apenas redes parciais: nem todo par de elementos tem um encontro ou junção.

Notas

  1. ^ Grätzer 1996 , p. 52 .
  2. ^ Birkhoff 1948 , p. 18 . "desdee duplamente". Birkhoff atribui isso a Dedekind 1897 , p.  8
  3. ^ Burris, Stanley N., e Sankappanavar, HP, 1981. Um Curso em Álgebra Universal . Springer-Verlag. ISBN  3-540-90578-2 .
  4. ^ Davey & Priestley (2002) , Exercício 4.1, p. 104 .
  5. ^ a b Davey & Priestley (2002) , Teorema 4.10, p. 89 .
  6. Davey & Priestley (2002) , Teorema 10.21, pp. 238–239 .
  7. Stanley, Richard P , Enumerative Combinatorics (vol. 1) , Cambridge University Press, pp. 103–104, ISBN 0-521-66351-2
  8. ^ Philip Whitman (1941). "Reticulados Livres I". Anais de Matemática . 42 : 325-329. doi : 10.2307/1969001 .
  9. ^ Philip Whitman (1942). "Reticulados Livres II". Anais de Matemática . 43 : 104-115. doi : 10.2307/1968883 .

Referências

Monografias disponíveis gratuitamente online:

Textos elementares recomendados para aqueles com maturidade matemática limitada :

  • Donnellan, Thomas, 1968. Teoria da Malha . Pérgamo.
  • Grätzer, George , 1971. Teoria de Reticulados: Primeiros conceitos e reticulados distributivos . WH Freeman.

O texto introdutório contemporâneo padrão, um pouco mais difícil do que o acima:

Monografias avançadas:

Em treliças livres:

  • R. Freese, J. Jezek e JB Nation, 1985. "Free Lattices". Pesquisas e Monografias Matemáticas Vol. 42. Associação Matemática da América .
  • Johnstone, PT , 1982. Espaços de pedra . Estudos de Cambridge em Matemática Avançada 3. Cambridge University Press.

Sobre a história da teoria da rede:

Sobre aplicações da teoria da rede:

  • Garrett Birkhoff (1967). James C. Abbot (ed.). O que a Latices pode fazer por você? . Van Nostrand. Índice

Links externos