Treliça (conjunto ordenado)

Em matemática , uma rede (em inglês : lattice ) é uma das estruturas algébricas usadas na álgebra geral . É um conjunto parcialmente ordenado em que cada par de elementos tem um limite superior e um limite inferior . Uma rede pode ser vista como a rede de Galois de uma relação binária .

Existem, na realidade, duas definições equivalentes da rede, uma concernente à relação de ordem mencionada anteriormente, a outra algébrica.

Exemplos preliminares e contra-exemplos

Qualquer conjunto fornecido com uma relação de ordem total é uma rede. Por exemplo, qualquer conjunto de números reais fornecido com a ordem usual.

Entre os conjuntos fornecidos com uma relação de ordem parcial, exemplos simples de reticulados resultam das relações de ordem “está incluído em” e “divide”.

O conjunto de partes de um conjunto fornecido com inclusão forma uma rede onde o limite superior é a união e o limite inferior a interseção.
Se uma parte de uma rede é estável por limite superior e limite inferior, ela forma uma rede (para a ordem restrita). É assim que o conjunto de aberturas de um espaço topológico (sempre com a inclusão) e um filtro em um conjunto formam reticulados.
Esta condição de estabilidade não é necessária:
- o conjunto de intervalos fechados de ℝ (incluindo o conjunto vazio) é uma rede cujo limite inferior é a interseção e cujo limite superior nem sempre é a união: portanto, o limite superior dos intervalos [1, 3] e [4, 5] é o intervalo [1, 5];
- o conjunto de relações de equivalência em um determinado conjunto é uma rede (ordenada pela suavidade das relações binárias ) cujo limite inferior é a interseção (nos gráficos), mas o limite superior é a relação de equivalência gerada por l 'união.
O conjunto de números naturais com a relação de "divisão" forma uma rede, onde o limite superior é o PPCM e o limite inferior é o GCD .
Para qualquer inteiro n ≥ 3, o conjunto de inteiros de 1 a n , dotado da relação de ordem “dividir”, não é uma rede porque o par { n , n - 1} não tem limite maior ou mesmo limite superior (porque qualquer múltiplo de n e n - 1 é um múltiplo de n ( n - 1), que é> n ).
Não é suficiente que cada par tenha limites superior e inferior para obter uma rede. Assim, na relação descrita pelo diagrama de Hasse ao lado, o par {b, c} admite três limites superiores d, e e f, mas nenhum limite superior porque {d, e, f} não possui um elemento menor.

Definição algébrica

Uma rede é um conjunto E fornecido com duas leis internas geralmente observadas ⋁ e ⋀ verificando:

as duas leis são comutativas e associativas ;
para todos $um$ e $b$ de E : ( lei de absorção ). $a \ wedge (a \ vee b) = a = a \ vee (a \ wedge b)$

A lei de absorção implica a idempotência de qualquer elemento a de E para as duas leis:

{\ displaystyle a \ vee a = a \ qquad {\ text {e}} \ qquad a \ wedge a = a}

A partir de tal estrutura, podemos definir em E uma relação de ordem , aqui observada ≤, como segue:

{\ displaystyle a \ leq b \ Leftrightarrow a \ vee b = b}

Podemos mostrar que essa relação é de fato uma relação de ordem (possivelmente parcial). A propriedade de associatividade garante transitividade . A propriedade de idempotência garante reflexividade . A comutatividade garante a anti-simetria . Graças às duas propriedades de absorção, também podemos mostrar que

{\ displaystyle a \ leq b \ Leftrightarrow a \ wedge b = a}

Podemos então verificar se

{\ displaystyle \ sup (a, b) = a \ vee b \ qquad {\ text {et}} \ qquad \ inf (a, b) = a \ wedge b}

o que garante que seja de fato uma treliça no sentido das ordens. ${\ displaystyle (E, \ leq)}$

Definição por relação de pedido

Uma rede é um conjunto E fornecido com uma relação de ordem verificando:

para todos os elementos um e b de E , existe um limite superior e um limite inferior para o conjunto { um , b }.

Para fornecer a E uma estrutura de rede algébrica, notamos que o limite superior e o limite inferior definem duas leis internas:

${\ displaystyle a \ vee b = \ sup (a, b)}$ ;
$a \ wedge b = \ inf (a, b)$ .

As propriedades algébricas da rede para essas duas leis decorrem diretamente da definição.

As redes são, portanto, definidas algebricamente ou por uma relação de ordem.

Glossário Lattice

Um conjunto ordenado no qual cada par de elementos tem um limite superior (ou um limite inferior) é uma meia rede .

Um morfismo de meia rede de ( L , ∨ L ) para ( M , ∨ M ) é um mapa f : L → M tal que para todo a , b ∈ L , f ( a ∨ L b ) = f ( a ) ∨ M f ( b ). Dizemos que é uma incorporação (de meia rede) se f também for injetiva . As definições de morfismo e incorporação de uma rede são desnecessárias.Exemplo: a rede das partições de um conjunto $X$ - isomórfica à rede das relações de equivalência em $X$ - está imersa na rede dos subgrupos do grupo simétrico $S ( X )$ , associando a cada partição $π$ o subgrupo $\prod A \in π S ( A )$ .Qualquer morfismo (resp. Qualquer incorporação) de uma rede (ou mesmo de uma meia rede) é um morfismo (resp. Embedding) de conjuntos ordenados, mas os recíprocos são falsos e até mesmo: qualquer rede está imersa na rede das relações de equivalência em um determinado conjunto, que além disso pode ser escolhido finito se a rede for.

Uma rede é dita distributiva (en) se a lei ⋁ é distributiva com respeito à lei ⋀, ou novamente (o que em uma rede é equivalente) se a lei ⋀ é distributiva com respeito à lei ⋁.

Uma rede é considerada limitada se tiver um máximo e um mínimo. Assim, o conjunto de inteiros naturais dotados da relação de ordem ≤ não é limitado, mas o mesmo conjunto dotado da relação de ordem "divide" é uma rede limitada cujo mínimo é 1 e o máximo é 0.

Uma rede limitada é considerada complementada se cada um de seus elementos x tem um complemento y que satisfaz x ⋀ y = 0 e x ⋁ y = 1, onde 0 designa o elemento mínimo da rede e 1 o elemento máximo.

Uma rede distributiva limitada e complementada também é chamada de álgebra booleana .

Uma rede E é considerada completa se qualquer parte de E tiver um limite superior, ou novamente (o que é equivalente, veja abaixo ) se qualquer parte de E tiver um limite inferior.

Em uma rede E tendo um mínimo denotado por 0, os átomos são os elementos mínimos de E \ {0}. Por exemplo, na rede do conjunto de partes de um conjunto, os átomos são os singletons. Algumas redes com um mínimo podem não ter átomos. É o caso, por exemplo, de ℝ + , bem como do conjunto de aberturas regulares (aberturas iguais dentro de sua adesão ) de um espaço topológico provido com a inclusão.

Um ideal treliça E é um não vazio I que é estável sob o ⋁ operação e que é tal que, se x ∈ E e y ∈ I , então x ⋀ y ∈ eu .

Dado um subconjunto A de um conjunto X , o conjunto de partes de A é uma rede perfeita de todas as partes do X .

Treliça completa

Em uma rede, qualquer parte finita de E tem um limite superior e um limite inferior, mas nem sempre é o caso para as partes infinitas, mesmo que seja limitada: o conjunto de números racionais entre 0 e 2 é uma rede limitada, mas não está completo porque o conjunto de números racionais desse conjunto cujo quadrado é menor que 2 não tem limite superior.

Garrett Birkhoff introduziu o seguinte significado do epíteto “completo”: um conjunto ordenado é considerado completo se qualquer parte tiver um limite superior (incluindo o conjunto vazio, que exige que E tenha um mínimo). Isso é equivalente a qualquer parte com um limite inferior (incluindo o conjunto vazio, que impõe que E tenha um máximo).

Também dizemos que E é um espaço totalmente reticulado. Na ciência da computação teórica, a sigla em inglês CPO , embora sua tradução literal seja "ordem parcial completa", tem um significado diferente. Para evitar qualquer confusão com outra noção de espaço completo , aquela no sentido de espaços métricos ou mais geralmente de espaços uniformes , Bourbaki propôs o termo completado , que não foi imposto. Assim, ℝ (que é completo para a distância usual) não é completado, mas ℝ = ℝ ⋃ ${-\infty, + \infty}$ é, daí seu nome de linha real completada . ℝ é de fato o completo (in) (no sentido de Dedekind - MacNeille (in) ) de ℝ, ou seja, a menor rede completa contendo ℝ.

Outros exemplos.

Cada segmento é uma rede completa.
O conjunto de partes de um conjunto é uma estrutura completa para inclusão.
Para qualquer parte G de uma rede completa, a sub-rede dos limites superiores de G é completa (e o mesmo para o limite inferior).
Em teoria da integração, se f e g são duas funções Borelian em ℝ, integráveis no sentido de Lebesgue e verificando f <g , o conjunto de funções Borelian h incluído entre f e g é uma estrutura não-completa que se torna completa se identificar duas funções iguais em quase toda parte ! (nota do limite superior de uma família de funções Borelian pode ser imensurável, quando quociente modulo igualdade em quase toda parte, olhamos para o que é chamado de superior essencial obrigado , que, retornando às funções, em quase toda parte aumenta cada elemento da família).

Teorema de Knaster-Tarski : todo mapa crescente de uma rede completa em si tem um ponto fixo.

Dualidade

Se for uma rede, então sua rede dupla é . ${\ displaystyle (E, \ vee, \ wedge, \ leq)}$ ${\ displaystyle (E, \ wedge, \ vee, \ geq)}$

Teorema da dualidade : Se um teorema T é verdadeiro para todas as treliças, então o teorema dual de T, obtido pela substituição de todas as ocorrências de por (e vice-versa) e todas as ocorrências de por (e vice-versa), é um teorema verdadeiro para todas as treliças. $\ vee$ $\ wedge$ $\ leq$ $\ geq$

Notas e referências

N. Bourbaki , Elementos da matemática : teoria dos conjuntos [ detalhe das edições ], p. ER.28 , visto no Google Books , fala de " todo reticulado ou rede ordenada (ou rede )" .
De fato, e da mesma forma, invertendo as duas leis. $a \ lor a = a \ lor (a \ land (a \ lor a)) = a$
(em) Philip Whitman (em) , " Grades, relações de equivalência e subgrupos " , Bull. Amargo. Matemática. Soc. , vol. 52,1946, p. 507-522 ( ler online ).
(em) Pavel Pudlak Jiří Tůma, " Cada rede finita pode ser embutida em uma partição de rede finita " , Algebra Universalis , vol. 10,1980, p. 74-95 ( ler online ).
De fato, se por exemplo ⋁ é distributivo em comparação com ⋀ então ${\ displaystyle (a \ land c) \ lor (b \ land c) = [a \ lor (b \ land c)] \ land [c \ lor (b \ land c)] = (a \ lor b) \ land (a \ lor c) \ land c = (a \ lor b) \ land c}$ portanto, ⋀ é distributivo em relação a ⋁.
Veja, por exemplo, este exercício corrigido na Wikiversidade .
Veja também as páginas de desambiguação Complétude e Complet .

Veja também

Bibliografia

Recursos disponíveis online:
- Garrett Birkhoff , " Theory and Applications of Lattices " , Annals of the IHP , vol. 11, n o 5,1949, p. 227-240 ( ler online )
- (en) Stanley N. Burris e HP Sankappanavar, A Course in Universal Algebra , Springer Verlag , 1981 ( ISBN 978-3-540-90578-3 )
- (en) Peter Jipsen e Henry Rose, Varieties of Lattices , Springer Lecture Notes in Mathematics 1533 , 1992 ( ISBN 978-0-387-56314-5 )
Livros de referência:
- (pt) Thomas Donnellan, Lattice Theory , Pergamon Press , 1968
- (pt) G. Grätzer, Teoria da Malha: Primeiros conceitos e redes distributivas , WH Freeman, 1971
- (en) BA Davey e HA Priestley, Introdução a Lattices and Order , Cambridge University Press , 2002
- (pt) Garrett Birkhoff, Lattice Theory , AMS Colloquium Publications, vol. 25, 3 e ed., 1967