Um estudo sobre reticulados distributivos

Um estudo sobre reticulados distributivos João Manuel Guerra Fontes Gonçalves UMinho | 2021 João Manuel Guerra Fontes Gonçalves Um estudo sobre reticulados distributivos Dezembro, 2021 Universidade do Minho Escola de Ciências João Manuel Guerra Fontes Gonçalves Um estudo sobre reticulados distributivos Dissertação de Mestrado Mestrado em Matemática Trabalho realizado sob a orientação da Doutora Carla Albertina Carvalhinho da Silva Mendes Dezembro, 2021 DIREITOS DE AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional CC BY-NC-SA 4.0 https://creativecommons.org/licenses/by-nc-sa/4.0/deed.pt Agradecimentos Gostaria de manifestar a minha sincera gratidão à Doutora Carla Albertina Carvalhinho da Silva Mendes por todo o seu trabalho em orientar-me ao longo de toda a elaboração desta dissertação de mestrado. Todos os seus conselhos e sugestões, todo o conhecimento que me transmitiu, toda a ajuda que me prestou foram verdadeiramente indispensáveis para a conclusão e aperfeiçoamento deste trabalho. ii DECLARAÇÃO DE INTEGRIDADE Declaro ter atuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. Resumo Nesta dissertação de mestrado, intitulada ”Um estudo sobre reticulados distributivos”, é desenvolvido um estudo sobre um dos ramos mais antigos da teoria de reticulados: os reticulados distributivos. Um reticulado distributivo é um reticulado cujas operações binárias são distributivas uma face à outra. Assim sendo, quando a teoria dos reticulados é restringida apenas ao estudo destes reticulados, torna-se necessário saber caraterizar e representar os reticulados distributivos de modo a simplificar a sua identificação em relação aos restantes reticulados. Como será constatado ao longo da dissertação, existem, de facto, várias formas de os caraterizar e representar; para tal, tem-se por auxílio alguns conceitos da teoria de reticulados como os ideais/filtros, as relações de congruência, os homomorfismos e os elementos ∧-irredutíveis/∨-irredutíveis/primos/complementados. Inicialmente, são recordados conceitos básicos sobre conjuntos parcialmente ordenados, álgebra universal e teoria geral de reticulados; destaque-se que é equivalente um reticulado ser considerado como um conjunto parcialmente ordenado ou como uma estrutura algébrica. O capítulo final desta dissertação é reservado ao estudo das álgebras de Boole. O interesse em abordar estas álgebras deve-se ao facto de as mesmas terem um reticulado distributivo como reduto, para além de serem as estruturas algébricas que estão envolvidas na génese da teoria de reticulados e, em particular, da de reticulados distributivos. São apresentadas várias propriedades destas estruturas algébricas, com o objetivo de encontrar caraterizações e representações das mesmas. Palavras-chave: Álgebra; Álgebra de Boole; Conjunto parcialmente ordenado; Reticulado; Reticulado distributivo. iv Abstract In this master’s dissertation, entitled ”A study on distributive lattices”, a study is developed on one of the oldest branches of lattice theory: the distributive lattices. A distributive lattice is a lattice whose binary operations are distributive towards each other. Therefore, when the lattice theory is restricted to the study of these lattices, it becomes necessary to know how to characterize and represent the distributive lattices in order to simplify their identification in relation to the other lattices. As will be seen throughout the dissertation, there are, in fact, several ways to characterize and represent them; for that, some concepts of the lattice theory, such as ideals/filters, congruence relations, homomorphisms and ∧-irreducible/∨-irreducible/prime/complemented elements, are used as help. Initially, basic concepts about partially ordered sets, universal algebra and general lattice theory are recalled; it shall be highlighted that it is equivalent for a lattice to be considered as a partially ordered set or as an algebraic structure. The final chapter of this dissertation is reserved for the study of Boolean algebras. The interest in approaching these algebras is due to the fact that they have a distributive lattice as a reduct, in addition to being the algebraic structures that are involved in the genesis of the lattice theory and, in particular, of the distributive lattice theory. Several properties of these algebraic structures are presented, with the aim of finding characterizations and representations of them. Keywords: Algebra; Boolean algebra; Distributive lattice; Lattice; Partially ordered set. v Índice Introdução 1 0 Conceitos introdutórios 3 0.1 Relações de ordem e relações de equivalência . . . . . . . . . . . . . . . . . . . . 3 0.2 Álgebrauniversal.................................. 9 0.3 Reticulados..................................... 13 1 Reticulados distributivos 39 1.1 Definições e propriedades principais . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.2 Teoremas de caraterização e de representação . . . . . . . . . . . . . . . . . . . 42 2 Álgebras de Boole 76 2.1 Noções e propriedades principais . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.2 Teoremas de caraterização e de representação . . . . . . . . . . . . . . . . . . . 83 Bibliografia 90 vi CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Definição 0.1.20. Seja (𝑃;≤) um c.p.o.. • Diz-se que 𝑃satisfaz a condição da cadeia ascendente (abreviadamente, c.c.a.) se, para qualquer cadeia ascendente 𝑥1≤𝑥2≤𝑥3≤ · · · em 𝑃, existir algum 𝑛∈ℕtal que, para qualquer 𝑘∈ℕ,𝑥𝑛+𝑘=𝑥𝑛. • Diz-se que 𝑃satisfaz a condição da cadeia descendente (abreviadamente, c.c.d.) se, para qualquer cadeia descendente 𝑥1≥𝑥2≥𝑥3≥ · · · em 𝑃, existir algum 𝑛∈ℕtal que, para qualquer 𝑘∈ℕ,𝑥𝑛+𝑘=𝑥𝑛. Teorema 0.1.21 (cf. [9], Theorem 1.13, p. 17).Seja 𝑃um c.p.o.. Então, (i) 𝑃satisfaz a c.c.d. se e só se 𝑃satisfaz a condição minimal; (ii) 𝑃satisfaz a c.c.a. se e só se 𝑃satisfaz a condição maximal. Demonstração. Como as condições (i) e(ii) são duais uma da outra, basta provar uma delas; demonstrese (i). Suponha-se, primeiramente, que 𝑃satisfaz a c.c.d.. Seja 𝑄um subconjunto não vazio de 𝑃. Então, tome-se arbitrariamente algum elemento de 𝑄,𝑞1. Caso 𝑞1seja um elemento minimal de 𝑄, dá-se por concluída a prova. Caso 𝑞1não seja um elemento minimal de 𝑄, então existe 𝑞2∈𝑄tal que 𝑞1>𝑞2. De igual modo, se 𝑞2for um elemento minimal de 𝑄, a prova termina; caso contrário, existe 𝑞3∈𝑄tal que 𝑞1>𝑞2>𝑞3. Usando sucessivamente o mesmo raciocínio, ou se obtém, a dado momento, algum 𝑞𝑛∈𝑄(𝑛∈ℕ) tal que 𝑞𝑛seja um elemento minimal de 𝑄ou se obtém uma cadeia ascendente infinita 𝑞1>𝑞2>𝑞3>· · · >𝑞𝑛>· · · , o que, devido à hipótese, não pode acontecer. Logo, 𝑃satisfaz a condição minimal. Admita-se, agora, que 𝑃satisfaz a condição minimal. Então, em particular, qualquer cadeia descendente 𝑥1≥𝑥2≥𝑥3≥ · · · em 𝑃possui algum elemento minimal 𝑥𝑛, para certo 𝑛∈ℕ. Logo, para qualquer 𝑘∈ℕ, tem-se 𝑥𝑛+𝑘=𝑥𝑛. Portanto, 𝑃satisfaz a c.c.d.. □ 7 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS De entre as aplicações entre c.p.o., destacam-se aquelas que preservam as ordens parciais dos c.p.o. envolvidos: os homomorfismos de c.p.o.. Definição 0.1.22. Sejam (𝑃;≤𝑃)e(𝑄;≤𝑄)c.p.o.. Uma aplicação 𝜑de 𝑃em 𝑄diz-se: •isótona ou um homomorfismo de c.p.o. se, para quaisquer 𝑥,𝑦 ∈𝑃, 𝑥≤𝑃𝑦=⇒𝜑(𝑥) ≤𝑄𝜑(𝑦); • um mergulho de ordem se, para quaisquer 𝑥,𝑦 ∈𝑃, 𝑥≤𝑃𝑦⇐⇒ 𝜑(𝑥) ≤𝑄𝜑(𝑦); • um isomorfismo de c.p.o. se 𝜑for, simultaneamente, sobrejetiva e um mergulho de ordem. Definição 0.1.23. Sejam 𝑃e𝑄c.p.o.. Diz-se que 𝑃é isomorfo a 𝑄se existir algum isomorfismo de c.p.o. de 𝑃em 𝑄. Observe-se também que um mergulho de ordem é uma aplicação injetiva e que, por consequência, um isomorfismo de c.p.o. é uma bijeção. Proposição 0.1.24. Sejam (𝑃;≤𝑃)e(𝑄;≤𝑄)c.p.o.. Uma aplicação 𝜑de 𝑃em 𝑄é um isomorfismo de c.p.o. se e só se 𝜑é invertível e 𝜑e𝜑−1são isótonas. Repare-se que, dados dois c.p.o. 𝑃e𝑄, se 𝑃for isomorfo a 𝑄, também 𝑄será isomorfo a 𝑃, pelo que poderá dizer-se simplesmente que os c.p.o. 𝑃e𝑄são isomorfos, podendo, como alternativa, escrever-se 𝑃𝑄para indicar essa informação. Um dos exemplos mais comuns de construções de c.p.o. são os produtos diretos de c.p.o.. Primeiramente, recorde-se que, sendo 𝐼um conjunto, o produto cartesiano da família de conjuntos (𝑋𝑖)𝑖∈𝐼é o conjunto de funções {𝑓:𝐼→Ð𝑖∈𝐼𝑋𝑖|𝑓(𝑖) ∈ 𝑋𝑖}. Proposição 0.1.25. Sejam 𝐼um conjunto, ((𝑃𝑖;≤𝑖))𝑖∈𝐼uma família de c.p.o. e ⊑a relação binária em Î𝑖∈𝐼𝑃𝑖definida de tal modo que, para quaisquer 𝑥,𝑦 ∈Î𝑖∈𝐼𝑃𝑖, 𝑥⊑𝑦se ∀𝑖∈𝐼, 𝑥 (𝑖) ≤𝑖𝑦(𝑖). Então, o par (Î𝑖∈𝐼𝑃𝑖;⊑) é um c.p.o.. Definição 0.1.26. Sejam 𝐼um conjunto e ((𝑃𝑖;≤𝑖))𝑖∈𝐼uma família de c.p.o.. Designa-se o c.p.o. (Î𝑖∈𝐼𝑃𝑖;⊑) por produto direto de ((𝑃𝑖;≤𝑖))𝑖∈𝐼. Para o estudo desenvolvido nesta dissertação, é também útil recordar o conceito de relação de equivalência. 8 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Definição 0.1.27. Seja 𝑋um conjunto. Chama-se relação de equivalência em 𝑋ou, simplesmente, equivalência em 𝑋a qualquer relação binária em 𝑋que seja, simultaneamente, reflexiva, simétrica e transitiva. Sendo 𝑋um conjunto, representa-se por Equ(𝑋)o conjunto de todas as equivalências em 𝑋. Definição 0.1.28. Sejam 𝑋um conjunto e 𝜃∈Equ(𝑋). Para qualquer 𝑥∈𝑋, o conjunto [𝑥]𝜃={𝑦∈𝑋|𝑥𝜃𝑦} diz-se uma classe de equivalência de 𝜃em 𝑋; em particular, [𝑥]𝜃diz-se a classe de equivalência de 𝑥 módulo 𝜃, ou simplesmente a classe de equivalência de 𝑥, caso não haja ambiguidade. Dados um conjunto 𝑋,𝜃∈Equ(𝑋)e𝑥∈𝑋, poderá representar-se a classe de equivalência [𝑥]𝜃 apenas por [𝑥], quando for óbvia a relação tratada. Definição 0.1.29. Sejam 𝑋um conjunto e 𝜃∈Equ(𝑋). Chama-se conjunto quociente de 𝑋por 𝜃ao conjunto de todas as classes de equivalência de 𝜃em 𝑋, representado usualmente por 𝑋/𝜃, isto é, 𝑋/𝜃={[𝑥]𝜃|𝑥∈𝑋}. 0.2 Álgebra universal Nesta secção, recordam-se algumas noções básicas de álgebra universal, área matemática que generaliza o estudo que é feito em estruturas algébricas mais concretas, tais como grupos, anéis, reticulados, procurando investigar as propriedades que estas têm em comum. A noção de álgebra é nuclear para o estudo em álgebra universal. No sentido de a formalizar, recordam-se, de seguida, alguns conceitos necessários para tal. Definição 0.2.1. Sejam 𝐴um conjunto não vazio e 𝑛∈ℕ0. Uma aplicação 𝑓de 𝐴𝑛em 𝐴diz-se uma operação 𝑛-ária em 𝐴ou uma operação de aridade 𝑛em 𝐴;𝑛diz-se a aridade de 𝑓. Dados um conjunto não vazio 𝐴,𝑛∈ℕ0e𝑓uma operação 𝑛-ária em 𝐴, em situações em que não seja necessário indicar a aridade de 𝑓, pode simplesmente dizer-se que 𝑓é uma operação em 𝐴. Além disso, a operação 𝑓diz-se nulária,unária,binária se a aridade de 𝑓for, respetivamente, 0,1,2. Definição 0.2.2. Sejam 𝐴um conjunto não vazio, 𝑛∈ℕ0,𝑓uma operação 𝑛-ária em 𝐴e𝑋⊆𝐴. O conjunto 𝑋diz-se fechado para a operação 𝑓se, para qualquer (𝑥1, . . . , 𝑥𝑛) ∈ 𝑋𝑛, 𝑓(𝑥1, . . . , 𝑥𝑛) ∈ 𝑋. 9 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Habitualmente, as operações são representadas por símbolos, tais como 𝑓,𝑔,+,·,×, designados por símbolos de operação. Definição 0.2.3. Um tipo algébrico ou, simplesmente, tipo consiste num par (𝑂, (𝑛𝑓)𝑓∈𝑂)onde 𝑂 é um conjunto formado por símbolos de operação e (𝑛𝑓)𝑓∈𝑂é uma família de números inteiros não negativos; para cada 𝑓∈𝑂,𝑛𝑓diz-se a aridade de 𝑓. Definição 0.2.4. Define-se álgebra de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂)ou, somente, álgebra como sendo um par A=(𝐴;𝐹)onde 𝐴é um conjunto não vazio e 𝐹é uma família (𝑓A)𝑓∈𝑂de operações em 𝐴indexada pelo conjunto 𝑂, de tal modo que, para cada símbolo de operação 𝑓∈𝑂de aridade 𝑛𝑓,𝑓Aé uma operação 𝑛𝑓-ária em 𝐴. Designa-se o conjunto 𝐴por universo de Ae cada operação 𝑓A∈𝐹por operação fundamental de A. Diz-se que o conjunto 𝑂éo conjunto dos símbolos de operação de A. Para cada operação fundamental 𝑓Ade uma álgebra A, também pode escrever-se 𝑓em vez de 𝑓A, caso não haja ambiguidade. Note-se que, dada uma álgebra A=(𝐴;𝐹)de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂), o conjunto de símbolos de operação de Apode ser finito ou infinito. Caso seja finito e não vazio, isto é, 𝑂={𝑓1, . . ., 𝑓𝑘}para algum 𝑘∈ℕ, e supondo, sem perda de generalidade, que 𝑛𝑓1≥ · · · ≥ 𝑛𝑓𝑘, é usual representar a álgebra (𝐴;𝐹)por (𝐴;𝑓A 1, . . . , 𝑓 A 𝑘)ou, se não houver ambiguidade, por (𝐴;𝑓1, . . . , 𝑓𝑘); neste caso, também é frequente denotar o tipo de Apor (𝑂,𝑛𝑓1, . . . , 𝑛𝑓𝑘)ou somente por (𝑛𝑓1, . . . , 𝑛𝑓𝑘). Definição 0.2.5. Seja A=(𝐴;𝐹)uma álgebra de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂). Chama-se reduto de Aa qualquer álgebra B=(𝐵;𝐺)de tipo (𝑈, (𝑚𝑔)𝑔∈𝑈)tal que 𝐵=𝐴,𝑈⊆𝑂e, para cada 𝑔∈𝑈, 𝑚𝑔=𝑛𝑔e𝑔B=𝑔A. Definição 0.2.6. Seja A=(𝐴;𝐹)uma álgebra. Um subconjunto 𝐵de 𝐴diz-se um subuniverso de A se 𝐵for fechado para toda a operação fundamental de A. Definição 0.2.7. Sejam A=(𝐴;𝐹)eB=(𝐵;𝐺)duas álgebras, ambas de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂). Diz-se que Bé uma subálgebra de A, e escreve-se B ≤ A, se 𝐵for um subuniverso de Ae, para quaisquer 𝑓∈𝑂e(𝑏1, . . . ,𝑏𝑛𝑓) ∈ 𝐵𝑛𝑓, 𝑓B(𝑏1, . . . ,𝑏𝑛𝑓)=𝑓A(𝑏1, . . . ,𝑏𝑛𝑓). O conceito de homomorfismo de álgebras consiste numa aplicação entre universos de álgebras que é compatível com as operações das álgebras envolvidas. Esta noção, que será formalizada de seguida, tem, de facto, um papel muito importante no estudo da álgebra universal. Definição 0.2.8. Sejam A=(𝐴;𝐹)eB=(𝐵;𝐺)duas álgebras do mesmo tipo (𝑂, (𝑛𝑓)𝑓∈𝑂). Uma aplicação 𝜑de 𝐴em 𝐵diz-se: 10 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS • um homomorfismo de Aem B, e escreve-se 𝜑:A → B, se, para quaisquer 𝑓∈𝑂e (𝑎1, . . . , 𝑎𝑛𝑓) ∈ 𝐴𝑛𝑓, 𝜑(𝑓A(𝑎1, . . . , 𝑎𝑛𝑓)) =𝑓B(𝜑(𝑎1), . . . , 𝜑 (𝑎𝑛𝑓)); • um epimorfismo se 𝜑for sobrejetiva e 𝜑:A → B; • um monomorfismo se 𝜑for injetiva e 𝜑:A → B; • um isomorfismo se 𝜑for bijetiva e 𝜑:A → B. Definição 0.2.9. Seja Auma álgebra. Dá-se a designação de endomorfismo em Aa qualquer homomorfismo de Aem A. Definição 0.2.10. Sejam AeBálgebras do mesmo tipo. Diz-se que Aéisomorfa a Bse existir algum isomorfismo de Aem B. É simples verificar que, dadas duas álgebras AeBdo mesmo tipo, se Afor isomorfa a B, então também Bé isomorfa a A. Por isso, poderá apenas dizer-se que AeBsão isomorfas e usa-se a notação ABpara indicar essa informação; neste caso, também se diz frequentemente que ”AeB são iguais, a menos de um isomorfismo”. Definição 0.2.11. Seja Auma álgebra. Dá-se a designação de imagem homomorfa de Aa qualquer álgebra Btal que exista algum epimorfismo de Aem B. A composição de homomorfismos de álgebras continua a ser um homomorfismo de álgebras, tal como é estabelecido no teorema seguinte. Proposição 0.2.12 (cf. [3], Theorem 6.5, p. 48).Sejam A,BeCálgebras do mesmo tipo. Para quaisquer 𝜑:A → B e𝜙:B → C, a composição 𝜙◦𝜑é um homomorfismo de Aem C. Apresentam-se, de seguida, os conceitos de congruência numa álgebra e de álgebra quociente, e ver-se-á como estes se relacionam com a noção de homomorfismo de álgebras. Definição 0.2.13. Sejam A=(𝐴;𝐹)uma álgebra de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂)e𝜃∈Equ(𝐴). Diz-se que 𝜃é uma relação de congruência em Aou, somente, congruência em Ase, para quaisquer 𝑓∈𝑂e (𝑎1, . . . , 𝑎𝑛𝑓),(𝑏1, . . . ,𝑏𝑛𝑓) ∈ 𝐴𝑛𝑓, (∀𝑖∈ {1, . . . , 𝑛𝑓}, 𝑎𝑖𝜃𝑏𝑖)=⇒𝑓A(𝑎1, . . . , 𝑎𝑛𝑓)𝜃 𝑓 A(𝑏1, . . . ,𝑏𝑛𝑓). O conjunto de todas as congruências em Aé denotado por Con(A). Observe-se que (Con(A);⊆) é um c.p.o. limitado, sendo a relação identidade △𝐴={(𝑎, 𝑎) ∈ 𝐴2|𝑎∈𝐴}e a relação universal ▽𝐴=𝐴2os seus elementos mínimo e máximo, respetivamente. 11 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Definição 0.2.14. Sejam A=(𝐴;𝐹)uma álgebra de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂)e𝜃∈Con(A). Chama-se álgebra quociente de Apor 𝜃à álgebra A/𝜃=(𝐴/𝜃;(𝑓A/𝜃)𝑓∈𝑂), também de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂), onde, para quaisquer 𝑓∈𝑂e𝑎1, . . . , 𝑎𝑛𝑓∈𝐴, 𝑓A/𝜃([𝑎1]𝜃, . . . , [𝑎𝑛𝑓]𝜃)=[𝑓A(𝑎1, . . . , 𝑎𝑛𝑓)]𝜃. Segue-se a definição de núcleo de um homomorfismo de álgebras, o qual se prova tratar-se de uma congruência definida no domínio do homomorfismo. Definição 0.2.15. Sejam A=(𝐴;𝐹)eB=(𝐵;𝐺)álgebras do mesmo tipo e 𝜑:A → B. Designa-se por núcleo de 𝜑a relação binária em 𝐴definida por Nuc(𝜑)={(𝑎,𝑏) ∈ 𝐴2:𝜑(𝑎)=𝜑(𝑏)}. Proposição 0.2.16 (cf. [3], Theorem 6.8, p. 49).Sejam AeBálgebras do mesmo tipo e 𝜑:A → B. Então, Nuc(𝜑)é uma congruência em A. Proposição 0.2.17 (cf. [3], Theorem 6.10, p. 50).Sejam A=(𝐴;𝐹)uma álgebra e 𝜃∈Con(A). A correspondência 𝜋𝜃de 𝐴em 𝐴/𝜃, definida por 𝜋𝜃(𝑎)=[𝑎]𝜃,∀𝑎∈𝐴, é um epimorfismo de Aem A/𝜃. Definição 0.2.18. Sejam A=(𝐴;𝐹)uma álgebra e 𝜃∈Con(A). Chama-se homomorfismo natural de Aem A/𝜃ao epimorfismo 𝜋𝜃definido tal como na proposição anterior. Teorema 0.2.19 (Teorema do Homomorfismo; cf. [3], Theorem 6.12, pp. 50–51).Seja A=(𝐴;𝐹) uma álgebra de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂). Qualquer imagem homomorfa a Aé isomorfa a alguma álgebra quociente de A: sendo B=(𝐵;𝐺)uma álgebra tal que existe um epimorfismo 𝜑de Aem Be definindo 𝜃=Nuc(𝜑)e𝜓como sendo a correspondência de 𝐴/𝜃em 𝐵tal que 𝜓([𝑎]𝜃)=𝜑(𝑎),∀ [𝑎]𝜃∈𝐴/𝜃, tem-se que 𝜓é um isomorfismo de A/𝜃em Btal que 𝜓◦𝜋𝜃=𝜑, ou seja, tal que o diagrama AB A/𝜃 𝜑 𝜋𝜃𝜓 é comutativo. 12 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Anteriormente, foram apresentados conceitos, como o de subálgebra e o de álgebra quociente, que são exemplos de processos de construção de novas álgebras a partir de outras dadas. Contudo, nos que até agora foram tratados, as álgebras obtidas têm complexidade inferior ou igual às álgebras originais. De seguida, descreve-se um processo de construção de álgebras em que, a partir da combinação de várias álgebras, se obtém uma álgebra com complexidade superior a qualquer uma das álgebras iniciais. Trata-se do produto direto de álgebras. Definição 0.2.20. Sejam 𝐼um conjunto e (A𝑖)𝑖∈𝐼=((𝐴𝑖;𝐹𝑖))𝑖∈𝐼uma família de álgebras de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂). Chama-se produto direto de (A𝑖)𝑖∈𝐼à álgebra (Î𝑖∈𝐼𝐴𝑖;(𝑓Î𝑖∈𝐼A𝑖)𝑓∈𝑂), também de tipo (𝑂, (𝑛𝑓)𝑓∈𝑂), representada habitualmente por Î𝑖∈𝐼A𝑖, onde, para quaisquer 𝑓∈𝑂e 𝑥1, . . . , 𝑥𝑛𝑓∈Î𝑖∈𝐼𝐴𝑖, 𝑓Î𝑖∈𝐼A𝑖(𝑥1, . . . , 𝑥𝑛𝑓)(𝑖)=𝑓A𝑖(𝑥1(𝑖), . . . , 𝑥𝑛𝑓(𝑖)), para cada 𝑖∈𝐼. Sendo 𝐼={𝑖1, . . . ,𝑖𝑘}, para certo 𝑘∈ℕ, escreve-se A𝑖1× · · · × A𝑖𝑘para representar o produto direto Î𝑖∈𝐼A𝑖. Sendo Auma álgebra, denota-se por A𝐼o produto direto Î𝑖∈𝐼A𝑖onde, para qualquer 𝑖∈𝐼,A𝑖=A; além disso, se 𝐼={𝑖1, . . . ,𝑖𝑘}, para certo 𝑘∈ℕ, escreve-se A𝑘para representar o produto direto A𝑖1× · · · × A𝑖𝑘quando A𝑖1=· · · =A𝑖𝑘=A. 0.3 Reticulados Nesta secção, estudam-se alguns tópicos da teoria geral de reticulados. 0.3.1 Duas definições de reticulado A noção de reticulado pode ser definida sob dois pontos de vista: um reticulado pode ser tratado como um conjunto parcialmente ordenado ou como uma álgebra. Definição 0.3.1. Um c.p.o. (𝑅;≤) diz-se um reticulado se, em 𝑅, existirem inf{𝑥,𝑦}esup{𝑥,𝑦}, para quaisquer 𝑥,𝑦∈𝑅. Equivalentemente, um c.p.o. (𝑅;≤) é um reticulado se, para qualquer subconjunto não vazio finito 𝑆 de 𝑅, os elementos inf (𝑆)esup(𝑆)existirem em 𝑅. Definição 0.3.2. Um reticulado (𝑅;≤) diz-se completo se, para qualquer subconjunto 𝑆de 𝑅, os elementos inf (𝑆)esup(𝑆)existirem em 𝑅. 13 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Um reticulado pode também ser visto como uma estrutura algébrica. De facto, uma vez que, num reticulado (𝑅;≤), existem sempre inf{𝑥,𝑦}esup{𝑥,𝑦}, para quaisquer 𝑥,𝑦 ∈𝑅, e ambos são univocamente determinados, então é possível definir, em 𝑅, operações binárias, habitualmente denotadas por ∧e∨, conforme as igualdades 𝑥∧𝑦=inf{𝑥,𝑦}e𝑥∨𝑦=sup{𝑥,𝑦}. Assim, (𝑅;∧,∨) é uma álgebra (de tipo (2,2)). Além disso, as operações ∧e∨satisfazem (ver demonstração do Teorema 0.3.4) • a propriedade de idempotência, isto é, para qualquer 𝑥∈𝑅, 𝑥∧𝑥=𝑥e𝑥∨𝑥=𝑥; • a propriedade comutativa, isto é, para quaisquer 𝑥,𝑦 ∈𝑅, 𝑥∧𝑦=𝑦∧𝑥e𝑥∨𝑦=𝑦∨𝑥; • a propriedade associativa, isto é, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, 𝑥∧ (𝑦∧𝑧)=(𝑥∧𝑦) ∧ 𝑧e𝑥∨ (𝑦∨𝑧)=(𝑥∨𝑦) ∨ 𝑧; • a propriedade de absorção, isto é, para quaisquer 𝑥,𝑦 ∈𝑅, 𝑥∧ (𝑥∨𝑦)=𝑥e𝑥∨ (𝑥∧𝑦)=𝑥. Considerando a propriedade associativa satisfeita pelas operações de um reticulado 𝑅, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, poderá escrever-se 𝑥∧𝑦∧𝑧em vez de 𝑥∧ (𝑦∧𝑧)ou (𝑥∧𝑦) ∧ 𝑧, bem como 𝑥∨𝑦∨𝑧 em vez de 𝑥∨ (𝑦∨𝑧)ou (𝑥∨𝑦) ∨ 𝑧. Faz sentido, portanto, definir reticulado tratando-o como uma estrutura algébrica. Definição 0.3.3. Seja 𝑅um conjunto não vazio. Uma álgebra (𝑅;∧,∨) de tipo (2,2)designa-se reticulado se as operações binárias ∧e∨satisfizerem as propriedades de idempotência, comutativa, associativa e de absorção. Apesar de as duas definições de reticulado aqui expostas serem de naturezas diferentes, elas relacionam-se e até podem dizer-se equivalentes no sentido em que, se um reticulado, definido sobre um conjunto 𝑅, satisfizer uma das definições, então é possível construir-se, de modo único, um reticulado, sobre o mesmo conjunto 𝑅, conforme a outra definição. Esta relação entre as duas definições de reticulado é estabelecida no resultado seguinte. 14 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Teorema 0.3.4 (cf. [7], Theorem 3, pp. 12–14).Seja 𝑅um conjunto não vazio. (i) Se (𝑅;∧,∨) for um reticulado, então (𝑅;≤), onde ≤é a relação definida por 𝑥≤𝑦se 𝑥=𝑥∧𝑦, é um reticulado, onde, para quaisquer 𝑥,𝑦 ∈𝑅, inf{𝑥,𝑦}=𝑥∧𝑦esup{𝑥,𝑦}=𝑥∨𝑦. (ii) Se (𝑅;≤) é um reticulado, então (𝑅;∧,∨), onde, para quaisquer 𝑥,𝑦 ∈𝑅, 𝑥∧𝑦=inf{𝑥,𝑦}e𝑥∨𝑦=sup{𝑥,𝑦}, é um reticulado. Além disso, para quaisquer 𝑥,𝑦 ∈𝑅, 𝑥≤𝑦⇐⇒ 𝑥=𝑥∧𝑦⇐⇒ 𝑥∨𝑦=𝑦. Demonstração. (i) Suponha-se que (𝑅;∧,∨) é um reticulado. A relação ≤é uma ordem parcial em 𝑅: primeiramente, sendo 𝑥∈𝑅, como, pela idempotência, 𝑥=𝑥∧𝑥, então 𝑥≤𝑥e, portanto, ≤é reflexiva; além disso, dados 𝑥,𝑦 ∈𝑅e admitindo que 𝑥≤𝑦e𝑦≤𝑥, isto é, 𝑥=𝑥∧𝑦 e𝑦=𝑦∧𝑥, segue, pela comutatividade, que 𝑥=𝑦, logo ≤é antissimétrica; por fim, dados 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑥≤𝑦e𝑦≤𝑧, ou seja, 𝑥=𝑥∧𝑦e𝑦=𝑦∧𝑧, tem-se 𝑥∧𝑧=(𝑥∧𝑦) ∧ 𝑧[hipótese] =𝑥∧ (𝑦∧𝑧)[associatividade] =𝑥∧𝑦[hipótese] =𝑥, [hipótese] pelo que 𝑥≤𝑧e, portanto, ≤é transitiva. Conclui-se assim que (𝑅;≤) é um c.p.o.. Sejam, agora, 𝑥,𝑦 ∈𝑅. Ora, por um lado, tem-se (𝑥∧𝑦) ∧ 𝑥=(𝑦∧𝑥) ∧ 𝑥[comutatividade] =𝑦∧ (𝑥∧𝑥)[associatividade] =𝑥∧𝑦[idempotência e comutatividade] e, por outro lado, (𝑥∧𝑦) ∧ 𝑦=𝑥∧ (𝑦∧𝑦)[associatividade] =𝑥∧𝑦, [idempotência] 15 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS o que implica que 𝑥∧𝑦é um minorante de {𝑥,𝑦}. Seja 𝑧um minorante qualquer de {𝑥,𝑦}. Assim, 𝑧=𝑧∧𝑥e𝑧=𝑧∧𝑦e, consequentemente, 𝑧∧ (𝑥∧𝑦)=(𝑧∧𝑥) ∧ 𝑦[associatividade] =𝑧∧𝑦[hipótese] =𝑧, [hipótese] ou seja, 𝑧≤𝑥∧𝑦, donde se conclui que inf{𝑥,𝑦}existe e é dado por 𝑥∧𝑦. Analogamente, sup{𝑥,𝑦}também existe e coincide com 𝑥∨𝑦. Portanto, (𝑅;≤) é um reticulado. (ii) Suponha-se que (𝑅;≤) é um reticulado. Já foi observado anteriormente que ambas as operações binárias ∧e∨estão, de facto, bem definidas, pelo que (𝑅;∧,∨) é uma álgebra. É simples verificar que as operações ∧e∨satisfazem a idempotência, a comutatividade e a associatividade. A absorção também é verificada. De facto, dados 𝑥,𝑦 ∈𝑅, é claro que 𝑥≤𝑥e𝑥≤sup{𝑥,𝑦}, ou seja, 𝑥é um minorante de {𝑥, sup{𝑥,𝑦}}. É imediato que, tomando um qualquer minorante 𝑧de {𝑥, sup{𝑥,𝑦}}, se tem 𝑧≤𝑥. Logo, inf{𝑥, sup{𝑥,𝑦}} =𝑥, ou seja, 𝑥∧ (𝑥∨𝑦)=𝑥. Analogamente se prova que 𝑥∨ (𝑥∧𝑦)=𝑥. Portanto, a álgebra (𝑅;∧,∨) é um reticulado. Finalmente, pela Proposição 0.1.13, é imediato que 𝑥≤𝑦⇐⇒ 𝑥=𝑥∧𝑦⇐⇒ 𝑥∨𝑦=𝑦, para quaisquer 𝑥,𝑦 ∈𝑅.□ Atendendo ao resultado estabelecido no teorema anterior, ao longo deste trabalho, não se fará distinção entre tratar um reticulado como uma álgebra, usando a notação (𝑅;∧,∨), e tratá-lo como um c.p.o., usando a notação (𝑅;≤), a não ser que tal seja necessário. Assim, escrever-se-á simplesmente 𝑅 significando (𝑅;∧,∨) e(𝑅;≤), simultaneamente. Todos os conceitos e resultados estudados na secção 0.2 podem ser especificados para o caso dos reticulados definidos como álgebras e adaptados, segundo o Teorema 0.3.4, para o caso dos reticulados tratados como c.p.o.. Apresentam-se, de seguida, alguns deles, no sentido de introduzir a notação estabelecida no caso dos reticulados. 16 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS ou seja, 𝜙(𝑥) ∧ 𝜙(𝑦)=𝜙(𝑥∧𝑦). Seja, agora, 𝑧∈id(𝑥) ∨ id(𝑦). Assim, pelo Teorema 0.3.17, 𝑧≤𝑎∨𝑏, para certos 𝑎∈id(𝑥)e𝑏∈id(𝑦). Como 𝑎≤𝑥e𝑏≤𝑦, tem-se 𝑎∨𝑏≤𝑥∨𝑦, logo 𝑧≤𝑥∨𝑦, ou seja, 𝑧∈id(𝑥∨𝑦). Reciprocamente, se 𝑧∈id(𝑥∨𝑦), então 𝑧≤𝑥∨𝑦, com 𝑥∈id(𝑥)e𝑦∈id(𝑦). Assim, 𝑧∈id(𝑥) ∨ id(𝑦). Logo, id(𝑥) ∨ id(𝑦)=id(𝑥∨𝑦), ou seja, 𝜙(𝑥) ∨ 𝜙(𝑦)=𝜙(𝑥∨𝑦). Portanto, 𝜙é, de facto, um monomorfismo de reticulados. □ Dado um reticulado 𝑅, definem-se, por dualidade, os conceitos de filtro de 𝑅gerado por 𝑆, sendo 𝑆um subconjunto não vazio de 𝑅, e filtro principal de 𝑅gerado por 𝑥, onde 𝑥∈𝑅, os quais são representados, respetivamente, por fil(𝑆)efil(𝑥), bem como se estabelecem os resultados duais dos anteriores, envolvendo estes conceitos. 0.3.4 Relações de congruência Também as relações de congruência têm um papel relevante no estudo de reticulados. Definição 0.3.27. Sejam (𝑅;∧,∨) um reticulado e 𝜃∈Equ(𝑅). Diz-se que 𝜃é uma relação de congruência em 𝑅ou, simplesmente, congruência em 𝑅se, para quaisquer 𝑥, 𝑦, 𝑧, 𝑤 ∈𝑅, (𝑥𝜃𝑧 e𝑦𝜃𝑤)=⇒ ((𝑥∧𝑦)𝜃(𝑧∧𝑤)e(𝑥∨𝑦)𝜃(𝑧∨𝑤)). Os resultados seguintes são úteis no estudo de congruências. 23 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Lema 0.3.28 (cf. [9], Theorem 9.2, p. 181).Sejam (𝑅;∧,∨) um reticulado e 𝜃∈Equ(𝑅). A relação 𝜃é uma congruência em 𝑅se e só se, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, 𝑥𝜃𝑦 =⇒ ((𝑥∧𝑧)𝜃(𝑦∧𝑧)e(𝑥∨𝑧)𝜃(𝑦∨𝑧)). Lema 0.3.29 (cf. [7], Lemma 11, pp. 37–38).Seja (𝑅;∧,∨) um reticulado. Uma relação binária 𝜃em 𝑅é uma congruência se e só se cada uma das condições seguintes é verificada: (i) 𝜃é reflexiva; (ii) para quaisquer 𝑥,𝑦 ∈𝑅, 𝑥𝜃𝑦 ⇐⇒ (𝑥∧𝑦)𝜃(𝑥∨𝑦); (iii) para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑥≤𝑦≤𝑧, (𝑥𝜃𝑦 e𝑦𝜃𝑧)=⇒𝑥𝜃𝑧; (iv) para quaisquer 𝑥,𝑦 ∈𝑅tais que 𝑥≤𝑦, 𝑥𝜃𝑦 =⇒ (∀𝑤∈𝑅, (𝑥∧𝑤)𝜃(𝑦∧𝑤)e(𝑥∨𝑤)𝜃(𝑦∨𝑤)). Demonstração. Seja 𝜃uma relação binária em 𝑅. Suponha-se, primeiramente, que 𝜃é uma congruência. É óbvio que (i) e(iii) são satisfeitas, além de que (iv) é uma consequência imediata do Lema 0.3.28. Mostre-se que (ii) também se verifica. Sejam 𝑥,𝑦 ∈𝑅. Supondo que 𝑥𝜃𝑦, segue, pelo Lema 0.3.28, que (𝑥∧𝑥)𝜃(𝑦∧𝑥), pelo que 𝑥𝜃 (𝑥∧𝑦). Dualmente, 𝑥𝜃 (𝑥∨𝑦). Logo, pela simetria e transitividade de 𝜃,(𝑥∧𝑦)𝜃(𝑥∨𝑦). Reciprocamente, suponha-se que (𝑥∧𝑦)𝜃(𝑥∨𝑦). Assim, usando novamente o Lema 0.3.28, tem-se que ((𝑥∧𝑦) ∧ 𝑥)𝜃((𝑥∨𝑦) ∧ 𝑥), donde (𝑥∧𝑦)𝜃𝑥. Analogamente, (𝑥∧𝑦)𝜃𝑦. Logo, pela simetria e transitividade de 𝜃,𝑥𝜃𝑦. Admita-se, agora, que a relação 𝜃satisfaz (i)–(iv). A reflexividade de 𝜃é garantida por (i). Quanto à simetria de 𝜃, é facilmente retirada de (ii): dados 𝑥,𝑦 ∈𝑅tais que 𝑥𝜃𝑦, então (𝑥∧𝑦)𝜃(𝑥∨𝑦), donde, pela comutatividade de ∧e de ∨, segue que (𝑦∧𝑥)𝜃(𝑦∨𝑥), pelo que 𝑦𝜃𝑥. Prove-se, agora, que 𝜃é transitiva. Nesse sentido, repare-se, primeiramente, que, para quaisquer 𝑥,𝑦, 𝑎, 𝑏 ∈𝑅tais que 𝑥≤𝑎≤𝑦,𝑥≤𝑏≤𝑦e𝑥𝜃𝑦, tem-se que 𝑎𝜃𝑏. De facto, como 𝑥𝜃𝑦 e𝑥≤𝑦, então, por (iv), (𝑥∧ (𝑎∨𝑏))𝜃(𝑦∧ (𝑎∨𝑏)). Claramente, 𝑥∧ (𝑎∨𝑏)=𝑥e𝑦∧ (𝑎∨𝑏)=𝑎∨𝑏. Logo, 𝑥𝜃 (𝑎∨𝑏). 24 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Seguidamente, como 𝑥≤𝑎∨𝑏, então, por (iv), (𝑥∨ (𝑎∧𝑏))𝜃((𝑎∨𝑏) ∨ (𝑎∧𝑏)). É claro que (𝑎∨𝑏) ∨ (𝑎∧𝑏)=𝑎∨𝑏. Além disso, tem-se 𝑥≤𝑎∧𝑏, pelo que 𝑥∨ (𝑎∧𝑏)=𝑎∧𝑏. Por conseguinte, (𝑎∧𝑏)𝜃(𝑎∨𝑏). Portanto, por (ii),𝑎𝜃𝑏. Sejam, agora, 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑥𝜃𝑦 e𝑦𝜃𝑧. Assim, por (ii), (𝑥∧𝑦)𝜃(𝑥∨𝑦)e(𝑦∧𝑧)𝜃(𝑦∨𝑧). Uma vez que 𝑥∧𝑦≤𝑥∨𝑦, segue, por (iv), que ((𝑥∧𝑦) ∧ (𝑦∧𝑧))𝜃((𝑥∨𝑦) ∧ (𝑦∧𝑧)) e, consequentemente, como 𝑦∧𝑧≤𝑥∨𝑦, tem-se (𝑥∧𝑦∧𝑧)𝜃(𝑦∧𝑧). De forma semelhante, obtém-se que (𝑦∨𝑧)𝜃(𝑥∨𝑦∨𝑧). Ora, como 𝑥∧𝑦∧𝑧≤𝑦∧𝑧≤𝑦∨𝑧≤𝑥∨𝑦∨𝑧 e (𝑥∧𝑦∧𝑧)𝜃(𝑦∧𝑧),(𝑦∧𝑧)𝜃(𝑦∨𝑧)e(𝑦∨𝑧)𝜃(𝑥∨𝑦∨𝑧), então, aplicando (iii) duas vezes, tem-se que (𝑥∧𝑦∧𝑧)𝜃(𝑥∨𝑦∨𝑧). Agora, como 𝑢=𝑥∧𝑦∧𝑧,𝑣=𝑥∨𝑦∨𝑧,𝑥e𝑧são elementos de 𝑅tais que 𝑢≤𝑥≤𝑣,𝑢≤𝑧≤𝑣 e𝑢𝜃𝑣, então, tendo em conta o que foi provado anteriormente, tem-se que 𝑥𝜃𝑧, concluindo, assim, a prova da transitividade de 𝜃. Portanto, 𝜃∈Equ(𝑅). Sejam, agora, 𝑥,𝑦, 𝑧 ∈𝑅com 𝑥𝜃𝑦. Então, por (ii), (𝑥∧𝑦)𝜃(𝑥∨𝑦), donde, por (iv), segue que (𝑥∧𝑦∧𝑧)𝜃((𝑥∨𝑦) ∧ 𝑧) e ((𝑥∧𝑦) ∨ 𝑧)𝜃(𝑥∨𝑦∨𝑧). Assim, uma vez que 𝑢=𝑥∧𝑦∧𝑧,𝑣=(𝑥∨𝑦) ∧ 𝑧,𝑎=𝑥∧𝑧,𝑏=𝑦∧𝑧são elementos de 𝑅tais que 𝑢≤𝑎≤𝑣,𝑢≤𝑏≤𝑣e𝑢𝜃𝑣, tem-se que 𝑎𝜃𝑏, ou seja, (𝑥∧𝑧)𝜃(𝑦∧𝑧). Mais, visto que 𝑟=(𝑥∧𝑦) ∨𝑧, 𝑠=𝑥∨𝑦∨𝑧,𝑐=𝑥∨𝑧e𝑑=𝑦∨𝑧são elementos de 𝑅tais que 𝑟≤𝑐≤𝑠,𝑟≤𝑑≤𝑠e𝑟𝜃𝑠, tem-se que 𝑐𝜃𝑑, ou seja, (𝑥∨𝑧)𝜃(𝑦∨𝑧). Portanto, pelo Lema 0.3.28, 𝜃é uma congruência. □ 25 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS O conjunto de todas as congruências num reticulado 𝑅é denotado por Con(𝑅). Observe-se que o par (Con(𝑅),⊆) é um c.p.o.. O resultado seguinte é muito simples de provar, mas facilita a demonstração do teorema que se lhe segue. Lema 0.3.30 (cf. [7], Theorem 12, p. 38).Seja 𝑅um reticulado. Então, para qualquer 𝑋⊆Con(𝑅), Ñ𝑋∈Con(𝑅). Teorema 0.3.31 (cf. [7], Theorem 12, pp. 38–39).Seja (𝑅;∧,∨) um reticulado. O c.p.o. (Con(𝑅);⊆) é um reticulado, onde, para quaisquer 𝜃, 𝜗 ∈Con(𝑅), •𝜃∧𝜗=𝜃∩𝜗; •𝜃∨𝜗=          (𝑥,𝑦) ∈ 𝑅2 ∃𝑛∈ℕ,∃𝑟1,𝑟2, . . . , 𝑟𝑛∈𝑅: 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦, ∀𝑖∈ {1,2, . . . , 𝑛 −1}, 𝑟𝑖𝜃𝑟𝑖+1ou 𝑟𝑖𝜗𝑟𝑖+1           . Demonstração. Sejam 𝜃, 𝜗 ∈Con(𝑅). Tendo em conta o lema anterior e as propriedades da interseção de conjuntos, é muito simples verificar que 𝜃∩𝜗é o ínfimo de {𝜃, 𝜗}, pelo que 𝜃∧𝜗=𝜃∩𝜗. Represente-se por 𝜉a relação binária dada por           (𝑥,𝑦) ∈ 𝑅2 ∃𝑛∈ℕ,∃𝑟1,𝑟2, . . . , 𝑟𝑛∈𝑅: 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦, ∀𝑖∈ {1,2, . . . , 𝑛 −1}, 𝑟𝑖𝜃𝑟𝑖+1ou 𝑟𝑖𝜗𝑟𝑖+1           . Prove-se, primeiramente, que 𝜉∈Con(𝑅). Para tal, basta mostrar que 𝜉observa cada uma das condições (i)–(iv) do Lema 0.3.29. Ora, é óbvio que 𝜉é reflexiva, ou seja, satisfaz (i) do Lema 0.3.29. Também não é difícil verificar que 𝜉satisfaz a condição (ii) do mesmo lema. Prove-se, agora, (iii). Sejam 𝑥,𝑦, 𝑧 ∈𝑅 tais que 𝑥≤𝑦≤𝑧,𝑥𝜉𝑦 e𝑦𝜉𝑧. Por um lado, existem 𝑟1,𝑟2, . . . ,𝑟𝑛∈𝑅, para algum 𝑛∈ℕ, tais que 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦 e, para cada 𝑖∈ {1,2, . . . , 𝑛 −1},𝑟𝑖𝜃𝑟𝑖+1ou 𝑟𝑖𝜗𝑟𝑖+1. Por outro lado, existem 𝑠1,𝑠2, . . . , 𝑠𝑚∈𝑅, para algum 𝑚∈ℕ, tais que 𝑦∧𝑧=𝑠1≤𝑠2≤ · · · ≤ 𝑠𝑚=𝑦∨𝑧 e, para cada 𝑗∈ {1,2, . . . ,𝑚 −1},𝑠𝑗𝜃𝑠𝑗+1ou 𝑠𝑗𝜗𝑠𝑗+1. Ora, 𝑥∧𝑧=𝑥=𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛−1 ≤𝑟𝑛=𝑥∨𝑦=𝑦=𝑦∧𝑧=𝑠1≤𝑠2≤ · · · ≤ 𝑠𝑚−1 ≤𝑠𝑚=𝑦∨𝑧=𝑧=𝑥∨𝑧, 26 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS ou seja, 𝑥∧𝑧=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑠1≤𝑠2≤ · · · ≤ 𝑠𝑚=𝑥∨𝑧. Defina-se 𝑝=𝑛+𝑚−1∈ℕe𝑡1, 𝑡2, . . . , 𝑡𝑝como sendo os elementos de 𝑅tais que, para cada 𝑘∈ {1,2, . . . , 𝑝}, (a) 𝑡𝑘=𝑟𝑘se 𝑘∈ {1,2, . . . , 𝑛}; (b) 𝑡𝑘=𝑠𝑘−𝑛+1se 𝑘∈ {𝑛+1,𝑛 +2, . . . , 𝑝}. Assim, tem-se que 𝑥∧𝑧=𝑡1≤𝑡2≤ · · · ≤ 𝑡𝑝=𝑥∨𝑧, onde, para cada 𝑙∈ {1,2, . . . , 𝑝 −1}, se tem, claramente, que 𝑡𝑙𝜃𝑡𝑙+1ou 𝑡𝑙𝜗𝑡𝑙+1. Logo, 𝑥𝜉𝑧. Portanto, a condição (iii) do Lema 0.3.29 é observada por 𝜉. Para mostrar que a propriedade (iv) do Lema 0.3.29 também se verifica, tomem-se arbitrariamente 𝑥,𝑦 ∈𝑅tais que 𝑥≤𝑦e𝑥𝜉𝑦. Então, existem 𝑟1,𝑟2, . . . , 𝑟𝑛∈𝑅, para algum 𝑛∈ℕ, tais que 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦 e, para cada 𝑖∈ {1,2, . . . ,𝑛 −1},𝑟𝑖𝜃𝑟𝑖+1ou 𝑟𝑖𝜗𝑟𝑖+1. Seja 𝑤∈𝑅. Ora, pela Proposição 0.1.14, (𝑥∧𝑦) ∧ 𝑤=𝑟1∧𝑤≤𝑟2∧𝑤≤ · · · ≤ 𝑟𝑛∧𝑤=(𝑥∨𝑦) ∧ 𝑤; além disso, tem-se, claramente, que (𝑥∧𝑤) ∧ (𝑦∧𝑤)=(𝑥∧𝑦) ∧ 𝑤; também não é difícil ver que (𝑥∧𝑤) ∨ (𝑦∧𝑤)=𝑦∧𝑤=(𝑥∨𝑦) ∧ 𝑤. Assim, definindo 𝑠1,𝑠2, . . . , 𝑠𝑛como sendo os elementos de 𝑅tais que, para cada 𝑘∈ {1,2, . . . , 𝑛}, 𝑠𝑘=𝑟𝑘∧𝑤, tem-se que (𝑥∧𝑤) ∧ (𝑦∧𝑤)=𝑠1≤𝑠2≤ · · · ≤ 𝑠𝑛=(𝑥∧𝑤) ∨ (𝑦∧𝑤), onde, para cada 𝑗∈ {1,2, . . . , 𝑛 −1},𝑠𝑗𝜃𝑠𝑗+1ou 𝑠𝑗𝜗𝑠𝑗+1, uma vez que 𝜃e𝜗são congruências em 𝑅. Logo, (𝑥∧𝑤)𝜉(𝑦∧𝑤). Por analogia, também se prova que (𝑥∨𝑤)𝜉(𝑦∨𝑤). Conclui-se, assim, que 𝜉∈Con(𝑅). Mostre-se, agora, que 𝜉é o supremo de {𝜃, 𝜎}. Sejam 𝑥,𝑦 ∈𝑅tais que 𝑥𝜃𝑦. Então, por (ii) do Lema 0.3.29, tem-se (𝑥∧𝑦)𝜃(𝑥∨𝑦). Como, além disso, 𝑥∧𝑦≤𝑥∨𝑦, segue que 𝑥𝜉𝑦. Logo, 𝜃⊆𝜉. Por argumentos semelhantes, também se mostra que 𝜗⊆𝜉. Falta verificar que 𝜉é a menor congruência 27 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS nestas condições. Seja 𝜁∈Con(𝑅)tal que 𝜃⊆𝜁e𝜗⊆𝜁. O objetivo é mostrar que 𝜉⊆𝜁. Sejam, então, 𝑥,𝑦 ∈𝑅tais que 𝑥𝜉𝑦. Assim, existem 𝑟1,𝑟2, . . . ,𝑟𝑛∈𝑅, para algum 𝑛∈ℕ, tais que 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦 e, para cada 𝑖∈ {1,2, . . . , 𝑛 −1},𝑟𝑖𝜃𝑟𝑖+1ou 𝑟𝑖𝜗𝑟𝑖+1. Por conseguinte, para cada 𝑖∈ {1,2, . . . , 𝑛 −1}, 𝑟𝑖𝜁𝑟𝑖+1. Pela transitividade de 𝜁, tem-se que 𝑟1𝜁𝑟𝑛, ou seja, (𝑥∧𝑦)𝜁(𝑥∨𝑦), donde segue, por (ii) do Lema 0.3.29, que 𝑥𝜁𝑦. Efetivamente, 𝜉⊆𝜁. Portanto, 𝜉é o supremo de {𝜃, 𝜗}, pelo que 𝜃∨𝜗=𝜉. Fica, assim, concluída a prova de que (Con(𝑅);⊆) é um reticulado. □ Definição 0.3.32. Seja 𝑅um reticulado. Chama-se reticulado das congruências em 𝑅ao reticulado (Con(𝑅);⊆). Observe-se que, de acordo com o que foi estudado na Secção 0.2, o reticulado das congruências de um reticulado é limitado. Tendo em conta o Teorema 0.3.31, é simples deduzir o seguinte resultado. Teorema 0.3.33 (cf. [7], Theorem 37, p. 51).Sejam (𝑅;∧,∨) um reticulado e 𝐼um conjunto. Então, Con(𝑅)é um reticulado completo e, dada uma qualquer família (𝜃𝑖)𝑖∈𝐼de congruências em 𝑅, tem-se •Ó𝑖∈𝐼𝜃𝑖=Ñ𝑖∈𝐼𝜃𝑖; •Ô𝑖∈𝐼𝜃𝑖=          (𝑥,𝑦) ∈ 𝑅2 ∃𝑛∈ℕ,∃𝑟1,𝑟2, . . . , 𝑟𝑛∈𝑅: 𝑥∧𝑦=𝑟1≤𝑟2≤ · · · ≤ 𝑟𝑛=𝑥∨𝑦, ∀𝑗∈ {1,2, . . . , 𝑛 −1},∃𝑖∈𝐼:𝑟𝑗𝜃𝑖𝑟𝑗+1           . Define-se, de seguida, o conceito de congruência gerada por uma relação binária não vazia. Para tal, veja-se, primeiramente, o seguinte resultado. Proposição 0.3.34 (cf. [7], Lemma 13, p. 39).Sejam 𝑅um reticulado e 𝜌uma relação binária não vazia em 𝑅. O conjunto dado por Ù{𝜃∈Con(𝑅) | 𝜌⊆𝜃} é uma congruência em 𝑅, sendo, aliás, a menor congruência em 𝑅que contém 𝜌. Demonstração. Seja 𝜗=Ù{𝜃∈Con(𝑅) | 𝜌⊆𝜃}. Pelo Lema 0.3.30, é imediato que 𝜗∈Con(𝑅). Sendo também óbvio que 𝜌⊆𝜗, resta demonstrar que 𝜗é a menor congruência em 𝑅nestas condições. Seja 𝜉∈Con(𝑅)tal que 𝜌⊆𝜉. Por conseguinte, 𝜉∈ {𝜃∈Con(𝑅) | 𝜌⊆𝜃}. Logo, é claro que 𝜗⊆𝜉. Portanto, 𝜗é a menor congruência em 𝑅que contém 𝜌.□ 28 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Definição 0.3.35. Sejam 𝑅um reticulado e 𝜌uma relação binária não vazia em 𝑅. Chama-se congruência em 𝑅gerada por 𝜌, e representa-se por con(𝜌), à menor congruência em 𝑅que contém 𝜌. Se 𝜌={(𝑥,𝑦)}, para alguns 𝑥,𝑦 ∈𝑅, a relação con(𝜌)designa-se por congruência principal em 𝑅 gerada por {(𝑥,𝑦)}. Sendo 𝑅um reticulado e 𝑥,𝑦 ∈𝑅, é usual representar-se a relação con({(𝑥,𝑦)}) por con(𝑥,𝑦). Além disso, dado um ideal 𝐼de 𝑅, é usual denotar-se a congruência con(𝐼2)por con(𝐼). O seguinte resultado é uma consequência trivial da condição (ii) do Lema 0.3.29. Proposição 0.3.36. Seja (𝑅;∧,∨) um reticulado. Então, para quaisquer 𝑥,𝑦 ∈𝑅, con(𝑥,𝑦)=con(𝑥∧𝑦, 𝑥 ∨𝑦). A proposição anterior é importante, pois dela se conclui que, para o estudo das congruências principais num reticulado, basta que sejam consideradas aquelas que são geradas por pares de elementos comparáveis. Com o conceito de congruência principal, é possível estabelecer a seguinte forma de descrever uma congruência gerada por alguma relação binária não vazia. Proposição 0.3.37 (cf. [7], Lemma 14, p. 39).Sejam 𝑅um reticulado e 𝜌uma relação binária não vazia em 𝑅. Então, con(𝜌)=Ü{con(𝑥,𝑦) | 𝑥𝜌𝑦}. Demonstração. Seja 𝜃=Ü{con(𝑥,𝑦) | 𝑥𝜌𝑦}. Pelo Teorema 0.3.33, é imediato que 𝜃∈Con(𝑅). Também não é difícil verificar que 𝜌⊆𝜃. De facto, para quaisquer 𝑥,𝑦 ∈𝑅tais que 𝑥𝜌𝑦, tem-se con(𝑥,𝑦) ⊆ 𝜃, logo 𝑥𝜃𝑦. Seja, agora, 𝜗∈Con(𝑅)tal que 𝜌⊆𝜗. Então, para todo (𝑥,𝑦) ∈ 𝜌, tem-se (𝑥,𝑦) ∈ 𝜗, pelo que con(𝑥,𝑦) ⊆ 𝜗. Logo 𝜃⊆𝜗. Portanto, con(𝜌)=𝜃.□ Proposição 0.3.38 (cf. [9], Theorem 9.10, pp. 189–190).Sejam (𝑅;∧,∨) um reticulado e 𝜃uma congruência em 𝑅. O conjunto quociente de 𝑅por 𝜃,𝑅/𝜃, quando munido das operações ∧𝜃e∨𝜃tais que, para quaisquer 𝑥,𝑦 ∈𝑅, [𝑥]𝜃∧𝜃[𝑦]𝜃=[𝑥∧𝑦]𝜃e[𝑥]𝜃∨𝜃[𝑦]𝜃=[𝑥∨𝑦]𝜃, é um reticulado. Definição 0.3.39. Sejam (𝑅;∧,∨) um reticulado e 𝜃∈Con(𝑅). Chama-se reticulado quociente de 𝑅por 𝜃ao reticulado (𝑅/𝜃;∧𝜃,∨𝜃)definido tal como na proposição anterior. Definição 0.3.40. Sejam 𝑅um reticulado, 𝜃∈Con(𝑅)e𝑅/𝜃o reticulado quociente de 𝑅por 𝜃. Chama-se classe de congruência a qualquer [𝑥]𝜃∈𝑅/𝜃. 29 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS 0.3.5 Elementos especiais Existem classes de elementos que desempenham um papel importante no estudo de reticulados. Definem-se seguidamente alguns desses elementos. Definição 0.3.41. Seja (𝑅;∧,∨) um reticulado com elemento mínimo 0. Um elemento 𝑥de 𝑅diz-se um átomo de 𝑅se 0≺𝑥. Seja (𝑅;∧,∨) um reticulado com elemento mínimo. Representa-se por At(𝑅)o conjunto de todos os átomos do reticulado 𝑅. Além disso, dado 𝑥∈𝑅, representa-se por at(𝑥)o conjunto de todos os átomos 𝑎de 𝑅tais que 𝑎≤𝑥, ou seja, at(𝑥)={𝑦∈At(𝑅) | 𝑦≤𝑥}. Definição 0.3.42. Seja (𝑅;∧,∨) um reticulado com elemento mínimo 0. O reticulado 𝑅diz-se atómico se, para qualquer 𝑥∈𝑅\ {0}, existe 𝑎∈At(𝑅)tal que 𝑎≤𝑥. Exemplo 0.3.43. Sendo 𝑋um conjunto, o reticulado (℘(𝑋);∩,∪) é atómico, onde At(℘(𝑋)) ={{𝑥} | 𝑥∈𝑋}. Faz-se, agora, um estudo acerca dos elementos irredutíveis de um reticulado. Definição 0.3.44. Seja (𝑅;∧,∨) um reticulado. • Um elemento 𝑥de 𝑅diz-se ∧-irredutível se 𝑥≠1(no caso de 𝑅ter elemento máximo) e, para quaisquer 𝑟, 𝑠 ∈𝑅, 𝑥=𝑟∧𝑠=⇒ (𝑥=𝑟ou 𝑥=𝑠). • Um elemento 𝑦de 𝑅diz-se ∨-irredutível se 𝑦≠0(no caso de 𝑅ter elemento mínimo) e, para quaisquer 𝑟, 𝑠 ∈𝑅, 𝑦=𝑟∨𝑠=⇒ (𝑦=𝑟ou 𝑦=𝑠). Seja 𝑅um reticulado. Representa-se por I(𝑅)o conjunto de todos os elementos ∧-irredutíveis de 𝑅 e por S(𝑅)o conjunto de todos os elementos ∨-irredutíveis de 𝑅. Para cada 𝑥∈𝑅, denota-se por S(𝑥) o conjunto de todos os elementos ∨-irredutíveis de 𝑅menores ou iguais a 𝑥, isto é, S(𝑥)={𝑦∈ S(𝑅) | 𝑦≤𝑥}. Exemplo 0.3.45. Seguem-se alguns exemplos de elementos ∧-irredutíveis e ∨-irredutíveis de reticulados. • Em qualquer cadeia, apenas o elemento 1, caso exista, não é ∧-irredutível. 30 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS • Em qualquer reticulado (℘(𝑋);∩,∪), onde 𝑋é um conjunto não vazio qualquer e ℘(𝑋)representa o conjunto das partes de 𝑋, tem-se S(℘(𝑋)) ={{𝑥} | 𝑥∈𝑋}. • Nos reticulados 𝑀3e𝑁5dados, respetivamente, por 𝑎𝑏𝑐 0 1 e𝑡 𝑠 𝑟 0′ 1′ , tem-se I(𝑀3)={𝑎,𝑏, 𝑐}=S(𝑀3)eI(𝑁5)={𝑟, 𝑠, 𝑡}=S(𝑁5). Proposição 0.3.46. Sejam (𝑅;∧𝑅,∨𝑅)e(𝑆;∧𝑆,∨𝑆)reticulados e seja 𝜑um isomorfismo de 𝑅em 𝑆. Então, para qualquer 𝑥∈𝑅, (i) 𝑥∈ I(𝑅)se e só se 𝜑(𝑥) ∈ I(𝑆); (ii) 𝑥∈ S(𝑅)se e só se 𝜑(𝑥) ∈ S(𝑆). Demonstração. Observe-se, primeiramente, que, sendo 𝑅e𝑆reticulados isomorfos, 𝑅tem elemento máximo (mínimo) se e só se 𝑆tem elemento máximo (mínimo). Ora, caso 𝑅tenha máximo, para qualquer 𝑥∈𝑅, tem-se 𝑥=1𝑅se e só se 𝜑(𝑥)=1𝑆. De facto, se 𝑥=1𝑅e uma vez que, para qualquer 𝑦∈𝑆, 𝑦=𝜑(𝑧), para certo 𝑧∈𝑅, 𝑦∨𝑆𝜑(𝑥)=𝑦∨𝑆𝜑(1𝑅) =𝜑(𝑧) ∨𝑆𝜑(1𝑅) =𝜑(𝑧∨𝑅1𝑅) =𝜑(1𝑅) =𝜑(𝑥), donde se obtém 𝜑(𝑥)=1𝑆. Reciprocamente, se 𝜑(𝑥)=1𝑆, então, para qualquer 𝑤∈𝑅, 𝜑(𝑥)=𝜑(𝑥) ∨𝑆𝜑(𝑤) =𝜑(𝑥∨𝑅𝑤), donde, pela injetividade de 𝜑, se obtém 𝑥=𝑥∨𝑅𝑤. Logo, 𝑥=1𝑅. De modo análogo, caso 𝑅tenha mínimo, tem-se 𝑥=0𝑅se e só se 𝜑(𝑥)=0𝑆. 31 CAPÍTULO 0. CONCEITOS INTRODUTÓRIOS Seja 𝑥∈𝑅. Mostre-se que (i) é verificada. Suponha-se que 𝑥∈ I(𝑅). Sejam 𝑎,𝑏 ∈𝑆tais que 𝜑(𝑥)=𝑎∧𝑆𝑏. Como 𝜑é um isomorfismo de reticulados, existem 𝑢, 𝑣 ∈𝑅tais que 𝑎=𝜑(𝑢)e𝑏=𝜑(𝑣). Assim, 𝜑(𝑥)=𝑎∧𝑆𝑏=𝜑(𝑢) ∧𝑆𝜑(𝑣)=𝜑(𝑢∧𝑅𝑣). Pela injetividade de 𝜑,𝑥=𝑢∧𝑅𝑣. Por hipótese, 𝑥=𝑢ou 𝑥=𝑣, pelo que 𝜑(𝑥)=𝜑(𝑢)=𝑎ou 𝜑(𝑥)=𝜑(𝑣)=𝑏. Além disso, como 𝑥≠1𝑅, então, pelo que se provou antes, 𝜑(𝑥)≠1𝑆. Logo, 𝜑(𝑥) ∈ I(𝑆). Reciprocamente, admitindo-se que 𝜑(𝑥) ∈ I(𝑆)e tomando-se quaisquer 𝑦, 𝑧 ∈𝑅tais que 𝑥= 𝑦∧𝑅𝑧, tem-se 𝜑(𝑥)=𝜑(𝑦∧𝑅𝑧)=𝜑(𝑦) ∧𝑆𝜑(𝑧), donde, por hipótese, se retira que 𝜑(𝑥)=𝜑(𝑦)ou 𝜑(𝑥)=𝜑(𝑧) e, pela injetividade de 𝜑, segue 𝑥=𝑦ou 𝑥=𝑧. Além disso, como 𝜑(𝑥)≠1𝑆, então, pelo que foi visto inicialmente, 𝑥≠1𝑅. Portanto, 𝑥∈ I(𝑅). Conclui-se que (i) é válida e, por raciocínios análogos, também se verifica (ii).□ Teorema 0.3.47 (cf. [2], Theorem 4.8, p. 59).Seja (𝑅;∧,∨) um reticulado que satisfaz a c.c.d.. Então, 𝑅tem elemento mínimo e qualquer 𝑥∈𝑅\ {0}pode ser representado como o supremo de um número finito de elementos ∨-irredutíveis de 𝑅. Demonstração. Por (ii) do Teorema 0.1.21, tem-se que 𝑅satisfaz a condição minimal, pelo que, em particular, 𝑅tem, pelo menos, um elemento minimal, 𝑥1. Se 𝑅contivesse algum outro elemento minimal, 𝑥2, então não existiria 𝑥1∧𝑥2, o que não acontece pois 𝑅é um reticulado. Logo, 𝑥1é o único elemento minimal de 𝑅. Portanto, 𝑥1=0. Seja, agora, 𝑥∈𝑅\ {0}. Se 𝑥∈ S(𝑅), a prova termina. Se 𝑥∉S(𝑅), então existem 𝑦, 𝑧 ∈𝑅tais que 𝑥=𝑦∨𝑧,𝑥>𝑦e𝑥>𝑧. Se 𝑦, 𝑧 ∈ S(𝑅), conclui-se o pretendido. Caso 𝑦∉S(𝑅)ou 𝑧∉S(𝑅), então 𝑦=𝑢∨𝑣, para certos 𝑢, 𝑣 ∈𝑅tais que 𝑦>𝑢e𝑦>𝑣, ou 𝑧=𝑟∨𝑠, para certos 𝑟, 𝑠 ∈𝑅tais que 𝑧>𝑟e𝑧>𝑠. Repetindo este procedimento, ou se obtém que 𝑥é o supremo de um número finito de elementos ∨-irredutíveis ou se obtém alguma cadeia descendente infinita. No entanto, o segundo caso é falso, pois contraria a c.c.d.. Dá-se, assim, por concluída a prova. □ 32 1Reticulados distributivos Ao longo deste capítulo, estudam-se os assuntos relativos ao tema central desta dissertação: os reticulados distributivos. Numa primeira secção, apresentam-se conceitos básicos relacionados com esta classe de reticulados, bem como algumas das suas principais propriedades. Na secção seguinte e suas subsecções, estudam-se propriedades dos reticulados distributivos, recorrendo, para tal, a noções como as de ideal/filtro, relação de congruência, elemento ∧-irredutível/∨-irredutível, complemento (relativo) com o objetivo de estabelecer resultados que auxiliem na caraterização e na representação de reticulados distributivos. 1.1 Definições e propriedades principais Existem reticulados (𝑅;∧,∨) em que as operações ∧e∨satisfazem propriedades adicionais àquelas que constam na definição 0.3.3, dos quais se destacam os reticulados distributivos e os reticulados modulares. Definição 1.1.1. Seja (𝑅;∧,∨) um reticulado. Diz-se que 𝑅é um reticulado distributivo se as operações ∧e∨satisfizerem as propriedades distributivas, isto é, para quaisquer 𝑥, 𝑦, 𝑧 ∈𝑅, 𝑥∧ (𝑦∨𝑧)=(𝑥∧𝑦) ∨ (𝑥∧𝑧)e𝑥∨ (𝑦∧𝑧)=(𝑥∨𝑦) ∧ (𝑥∨𝑧). Exemplo 1.1.2. Alguns exemplos de reticulados distributivos são •(ℤ; inf,sup), onde inf esup representam, respetivamente, as operações ínfimo e supremo quando em ℤse considera a relação de ordem ≤usual; •(℘(𝑋);∩,∪), onde 𝑋é um conjunto qualquer, ℘(𝑋)representa o conjunto das partes de 𝑋e∩ e∪são, respetivamente, as operações de interseção e de união; •(ℕ; m.d.c., m.m.c.), onde m.d.c.em.m.c.denotam, respetivamente, as operações máximo divisor comum e mínimo múltiplo comum. 39 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Para um reticulado ser distributivo, basta que uma das propriedades da Definição 1.1.1 seja satisfeita, uma vez que estas são equivalentes. Proposição 1.1.3 (cf. [4], Secção 4.3, pp. 85–86).Seja (𝑅;∧,∨) um reticulado. Então, são equivalentes as seguintes condições: (i) para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅,𝑥∧ (𝑦∨𝑧)=(𝑥∧𝑦) ∨ (𝑥∧𝑧); (ii) para quaisquer 𝑢, 𝑣,𝑤 ∈𝑅,𝑢∨ (𝑣∧𝑤)=(𝑢∨𝑣) ∧ (𝑢∨𝑤). Demonstração. Suponha-se que a condição (i) é satisfeita. Sejam 𝑢, 𝑣,𝑤 ∈𝑅. Então, (𝑢∨𝑣) ∧ (𝑢∨𝑤)=((𝑢∨𝑣) ∧ 𝑢) ∨ ((𝑢∨𝑣) ∧ 𝑤)[hipótese] =𝑢∨ (𝑤∧ (𝑢∨𝑣)) [comutatividade e absorção] =𝑢∨ (𝑤∧𝑢) ∨ (𝑤∧𝑣)[hipótese] =𝑢∨ (𝑣∧𝑤). [comutatividade e absorção] Logo, 𝑢∨ (𝑣∧𝑤)=(𝑢∨𝑣) ∧ (𝑢∨𝑤), ou seja, a condição (ii) é verificada. Por raciocínios análogos, prova-se que o recíproco também é válido. □ Repare-se que, em qualquer reticulado, verificam-se as desigualdades (𝑥∧𝑦) ∨ (𝑥∧𝑧) ≤ 𝑥∧ (𝑦∨𝑧)e𝑥∨ (𝑦∧𝑧) ≤ (𝑥∨𝑦) ∧ (𝑥∨𝑧). Portanto, para averiguar se um reticulado é distributivo, basta verificar se 𝑥∧ (𝑦∨𝑧) ≤ (𝑥∧𝑦) ∨ (𝑥∧𝑧)ou (𝑥∨𝑦) ∧ (𝑥∨𝑧) ≤ 𝑥∨ (𝑦∧𝑧). Os reticulados distributivos são casos particulares de uma classe de reticulados mais abrangente: os reticulados modulares. Definição 1.1.4. Seja (𝑅;∧,∨) um reticulado. Diz-se que 𝑅é um reticulado modular se for verificada apropriedade modular, isto é, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, 𝑥≤𝑦=⇒𝑥∨ (𝑦∧𝑧)=𝑦∧ (𝑥∨𝑧). Equivalentemente, um reticulado (𝑅;∧,∨) é modular se, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, (𝑥∧𝑦) ∨ (𝑦∧𝑧)=𝑦∧ ((𝑥∧𝑦) ∨ 𝑧)ou 𝑥∨ ((𝑥∨𝑦) ∧ 𝑧)=(𝑥∨𝑦) ∧ (𝑥∨𝑧), 40 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS já que 𝑥≤𝑦se e só se 𝑥=𝑥∧𝑦se e só se 𝑦=𝑥∨𝑦. Além disso, facilmente se verifica que em todo o reticulado são válidas as desigualdades (𝑥∧𝑦) ∨ (𝑦∧𝑧) ≤ 𝑦∧ ((𝑥∧𝑦) ∨ 𝑧)e𝑥∨ ((𝑥∨𝑦) ∧ 𝑧) ≤ (𝑥∨𝑦) ∧ (𝑥∨𝑧); pelo que, para provar que um reticulado é modular, é suficiente justificar que 𝑦∧ ((𝑥∧𝑦) ∨ 𝑧) ≤ (𝑥∧𝑦) ∨ (𝑦∧𝑧)ou (𝑥∨𝑦) ∧ (𝑥∨𝑧) ≤ 𝑥∨ ((𝑥∨𝑦) ∧ 𝑧). Proposição 1.1.5 (cf. [3], Theorem 3.4, p. 13).Qualquer reticulado distributivo é um reticulado modular. Demonstração. Sejam (𝑅;∧,∨) um reticulado distributivo e 𝑥,𝑦, 𝑧 ∈𝑅. Então, (𝑥∧𝑦) ∨ (𝑦∧𝑧)=((𝑥∧𝑦) ∨ 𝑦) ∧ ((𝑥∧𝑦) ∨ 𝑧)[hipótese] =𝑦∧ ((𝑥∧𝑦) ∨ 𝑧), [comutatividade e absorção] donde segue que o reticulado 𝑅é modular. □ Como já foi estudado, é possível formar novos reticulados a partir de outros já dados, como é o caso dos sub-reticulados, produtos diretos de reticulados e imagens homomorfas de reticulados. A questão que pode ser levantada é se estes processos de construção de reticulados respeitam as propriedades de distributividade e modularidade. Ora, segundo o que afirma o resultado que se segue, a distributividade e a modularidade são preservadas por estas construções. Proposição 1.1.6 (cf. [4], Secção 4.7, p. 88).(i) Se 𝑅é um reticulado distributivo (modular), então qualquer sub-reticulado de 𝑅é distributivo (modular). (ii) Se 𝑅e𝑆são reticulados distributivos (modulares), então o produto direto 𝑅×𝑆é distributivo (modular). (iii) Se 𝑅é um reticulado distributivo (modular), então qualquer imagem homomorfa de 𝑅é distributiva (modular). Demonstração. Faz-se a prova apenas para a distributividade, visto que são semelhantes os argumentos usados para provar ambos os casos. (i) É imediato. 41 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS (ii) Sejam (𝑅;∧𝑅,∨𝑅)e(𝑆;∧𝑆,∨𝑆)reticulados distributivos e (𝑥,𝑢),(𝑦, 𝑣),(𝑧,𝑤) ∈ 𝑅×𝑆. Então, pela Proposição 0.3.10, (𝑅×𝑆;⊓,⊔) é um reticulado; além disso, (𝑥,𝑢) ⊓ ((𝑦, 𝑣) ⊔ (𝑧,𝑤)) =(𝑥,𝑢) ⊓ (𝑦∨𝑅𝑧, 𝑣 ∨𝑆𝑤)[Definição 0.3.11] =(𝑥∧𝑅(𝑦∨𝑅𝑧),𝑢 ∧𝑆(𝑣∨𝑆𝑤)) [Definição 0.3.11] =((𝑥∧𝑅𝑦) ∨𝑅(𝑥∧𝑅𝑧),(𝑢∧𝑆𝑣) ∨𝑆(𝑢∧𝑆𝑤)) [distributividade de 𝑅e de 𝑆] =(𝑥∧𝑅𝑦,𝑢 ∧𝑆𝑣) ⊔ (𝑥∧𝑅𝑧,𝑢 ∧𝑆𝑤)[Definição 0.3.11] =((𝑥,𝑢) ⊓ (𝑦, 𝑣)) ⊔ ((𝑥,𝑢) ⊓ (𝑧,𝑤)). [Definição 0.3.11] Logo, o produto direto (𝑅×𝑆;⊓,⊔) é distributivo. (iii) Seja (𝑅;∧𝑅,∨𝑅)um reticulado distributivo. Sejam (𝑆;∧𝑆,∨𝑆)um reticulado e 𝜑um homomorfismo de reticulados de 𝑅em 𝑆. Ora, pela Proposição 0.3.8, sabe-se que a imagem homomorfa (𝜑(𝑅);∧𝑆,∨𝑆)de 𝑅é um sub-reticulado de 𝑆. Prove-se que o reticulado (𝜑(𝑅);∧𝑆,∨𝑆)é distributivo. Sejam 𝑝,𝑞, 𝑟 ∈𝜑(𝑅). Então, existem 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑝=𝜑(𝑥),𝑞=𝜑(𝑦)e𝑟=𝜑(𝑧). Ora, 𝑝∧𝑆(𝑞∨𝑆𝑟)=𝜑(𝑥) ∧𝑆(𝜑(𝑦) ∨𝑆𝜑(𝑧)) =𝜑(𝑥∧𝑅(𝑦∨𝑅𝑧)) [𝜑é um homomorfismo] =𝜑((𝑥∧𝑅𝑦) ∨𝑅(𝑥∧𝑅𝑧)) [distributividade de 𝑅] =(𝜑(𝑥) ∧𝑆𝜑(𝑦)) ∨𝑆(𝜑(𝑥) ∧𝑆𝜑(𝑧)) [𝜑é um homomorfismo] =(𝑝∧𝑆𝑞) ∨𝑆(𝑝∧𝑆𝑟). Portanto, o reticulado (𝜑(𝑅);∧𝑆,∨𝑆)é, de facto, distributivo. □ 1.2 Teoremas de caraterização e de representação O objetivo desta secção é estabelecer teoremas e resultados que auxiliem na caraterização e representação de reticulados distributivos, recorrendo, para tal, a conceitos e propriedades fundamentais da teoria de reticulados. 42 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS 1.2.1 Critério de distributividade de Birkhoff e outras caraterizações Considerem-se os reticulados representados pelos diagramas de Hasse 𝑎𝑏𝑐 0 1 e𝑥 𝑦 𝑧 0 1 e habitualmente designados por 𝑀3e𝑁5, respetivamente. Observe-se que nenhum destes reticulados é distributivo. De facto, não é difícil ver que, em 𝑀3, 𝑎∧ (𝑏∨𝑐)≠(𝑎∧𝑏) ∨ (𝑎∧𝑐) e, em 𝑁5, 𝑥∧ (𝑦∨𝑧)≠(𝑥∧𝑦) ∨ (𝑥∧𝑧). Quanto à modularidade, esta não é respeitada no reticulado 𝑁5, uma vez que (𝑦∧𝑥) ∨ (𝑥∧𝑧)≠𝑥∧ ((𝑦∧𝑥) ∨ 𝑧). Contudo, com uma verificação simples, prova-se que o reticulado 𝑀3é modular. Estes reticulados permitem estabelecer dois critérios que caraterizam a modularidade e a distributividade de um reticulado, os quais se apresentam no teorema seguinte. Teorema 1.2.1 (Critério de modularidade de Dedekind e Critério de distributividade de Birkhoff; cf. [3], Theorem 3.5 + Theorem 3.6, pp. 14–16).Seja (𝑅;∧,∨) um reticulado. Então, (i) 𝑅é modular se e só se 𝑅não possui qualquer sub-reticulado isomorfo a 𝑁5; (ii) 𝑅é distributivo se e só se 𝑅não possui qualquer sub-reticulado isomorfo a 𝑀3ou a 𝑁5. Demonstração. (i) Como o reticulado 𝑁5não é modular, então, por (i) e(iii) da Proposição 1.1.6, se 𝑁5for isomorfo a algum sub-reticulado 𝑆de 𝑅, o reticulado 𝑅não será modular. Reciprocamente, admita-se que 𝑅não é modular. Assim, existem 𝑥,𝑦, 𝑧 ∈𝑅tais que (𝑥∧𝑦) ∨ (𝑦∧𝑧)<𝑦∧ ((𝑥∧𝑦) ∨ 𝑧). Então, considerando 𝑎=(𝑥∧𝑦) ∨ (𝑦∧𝑧)e𝑏=𝑦∧ ((𝑥∧𝑦) ∨ 𝑧), tem-se que 𝑧∧𝑏=𝑧∧𝑦∧ ((𝑥∧𝑦) ∨ 𝑧) =𝑧∧𝑦[comutatividade e absorção] 43 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS e 𝑧∨𝑎=𝑧∨ (𝑥∧𝑦) ∨ (𝑦∧𝑧) =𝑧∨ (𝑥∧𝑦). [comutatividade e absorção] Além disso, como 𝑧∧𝑦≤𝑎<𝑏, segue que 𝑧∧𝑦≤𝑧∧𝑎≤𝑧∧𝑏=𝑧∧𝑦, pelo que 𝑧∧𝑎=𝑧∧𝑏=𝑧∧𝑦. Analogamente, também se tem 𝑧∨𝑎=𝑧∨𝑏=𝑧∨ (𝑥∧𝑦). Ora, fazendo 𝑐=𝑧∧𝑦e𝑑=𝑧∨ (𝑥∧𝑦), não é difícil verificar que os elementos 𝑐, 𝑧, 𝑎, 𝑏, 𝑑 são distintos dois a dois. Conclui-se assim que o reticulado 𝑧 𝑎 𝑏 𝑐 𝑑 é um sub-reticulado de 𝑅isomorfo a 𝑁5. (ii) Como os reticulados 𝑀3e𝑁5não são distributivos, então, se existir algum sub-reticulado 𝑆de 𝑅 isomorfo a 𝑀3ou a 𝑁5, é imediato, por (i) e(iii) da Proposição 1.1.6, que 𝑅não será distributivo. Reciprocamente, suponha-se que 𝑅não é distributivo e que 𝑅não contém qualquer sub-reticulado isomorfo a 𝑁5. Então, existem 𝑥,𝑦, 𝑧 ∈𝑅tais que (𝑥∧𝑦) ∨ (𝑥∧𝑧)<𝑥∧ (𝑦∨𝑧) e, por (i),𝑅é modular. Sendo 𝑑,𝑒,𝑎,𝑏e𝑐os elementos de 𝑅dados por 𝑑=(𝑥∧𝑦) ∨ (𝑥∧𝑧) ∨ (𝑦∧𝑧) 𝑒=(𝑥∨𝑦) ∧ (𝑥∨𝑧) ∧ (𝑦∨𝑧) 𝑎=(𝑥∧𝑒) ∨ 𝑑 𝑏=(𝑦∧𝑒) ∨ 𝑑 𝑐=(𝑧∧𝑒) ∨ 𝑑, não é difícil de verificar que, para qualquer 𝑢∈ {𝑎,𝑏,𝑐},𝑑≤𝑢≤𝑒. De facto, é óbvio que 𝑑≤𝑎. Além disso, como 𝑥∧𝑦≤𝑥∨𝑦,𝑥∧𝑦≤𝑥∨𝑧e𝑥∧𝑦≤𝑦∨𝑧, então 𝑥∧𝑦≤ (𝑥∨𝑦) ∧ (𝑥∨𝑧) ∧ (𝑦∨𝑧)=𝑒. Analogamente, prova-se que 𝑥∧𝑧≤𝑒e𝑦∧𝑧≤𝑒. 44 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Logo, 𝑑=(𝑥∧𝑦) ∨ (𝑥∧𝑧) ∨ (𝑦∧𝑧) ≤ 𝑒. Adicionalmente, uma vez que 𝑒∨𝑎=𝑒∨ (𝑥∧𝑒) ∨ 𝑑 =𝑒∨𝑑[comutatividade e absorção] =𝑒, [𝑑≤𝑒] tem-se que 𝑎≤𝑒. Portanto, 𝑑≤𝑎≤𝑒. Por raciocínios análogos, prova-se que 𝑑≤𝑏≤𝑒e 𝑑≤𝑐≤𝑒. Observe-se, agora, que 𝑥∧𝑒=𝑥∧ (𝑥∨𝑦) ∧ (𝑥∨𝑧) ∧ (𝑦∨𝑧) =𝑥∧ (𝑦∨𝑧)[absorção] e 𝑥∧𝑑=𝑥∧ ((𝑥∧𝑦) ∨ (𝑥∧𝑧) ∨ (𝑦∧𝑧)) =(𝑥∧𝑦) ∨ (𝑥∧ ((𝑥∧𝑧) ∨ (𝑦∧𝑧))) [modularidade] =(𝑥∧𝑦) ∨ (𝑥∧𝑧) ∨ (𝑥∧𝑦∧𝑧)[modularidade] =(𝑥∧𝑦) ∨ (𝑥∧𝑧), [𝑥∧𝑦∧𝑧≤𝑥∧𝑧] pelo que 𝑥∧𝑑<𝑥∧𝑒. Como 𝑑=𝑒conduz a uma contradição, conclui-se que 𝑑<𝑒. Demonstra-se, de seguida, que 𝑏∧𝑐=𝑑. Ora, 𝑏∧𝑐=((𝑦∧𝑒) ∨ 𝑑) ∧ ((𝑧∧𝑒) ∨ 𝑑) =𝑑∨ ((𝑑∨ (𝑦∧𝑒)) ∧ 𝑧∧𝑒)[comutatividade e modularidade] =𝑑∨ (𝑒∧ (𝑑∨𝑦) ∧ 𝑧∧𝑒)[comutatividade e modularidade (𝑑≤𝑒)] =𝑑∨ ((𝑑∨𝑦) ∧ 𝑧∧𝑒)[comutatividade e idempotência] =𝑑∨ (𝑧∧ ((𝑥∧𝑧) ∨ 𝑦) ∧ (𝑥∨𝑦)) [absorção e comutatividade] =𝑑∨ (((𝑥∧𝑧) ∨ (𝑧∧𝑦)) ∧ (𝑥∨𝑦)) [modularidade] =𝑑∨ (𝑥∧𝑧) ∨ (𝑧∧𝑦)[(𝑥∧𝑧) ∨ (𝑧∧𝑦) ≤ 𝑥∨𝑦] =𝑑. [idempotência] Por demonstrações análogas, conclui-se que 𝑎∧𝑏=𝑑e𝑎∧𝑐=𝑑. Argumentos semelhantes mostram que 𝑎∨𝑏=𝑒,𝑎∨𝑐=𝑒e𝑏∨𝑐=𝑒. Por fim, resta verificar que os elementos 𝑑,𝑒,𝑎,𝑏e𝑐são distintos dois a dois. Suponha-se que 𝑎=𝑏. Então, 𝑑=𝑎∧𝑏=𝑎∧𝑎=𝑎=𝑎∨𝑎=𝑎∨𝑏=𝑒, 45 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS o que é uma contradição. Logo, 𝑎≠𝑏. Analogamente, mostra-se que 𝑎≠𝑐e𝑏≠𝑐. Admita-se, agora, que 𝑒=𝑏. Assim, por um lado, 𝑑=𝑎∧𝑏=𝑎∧𝑒=𝑎∧ (𝑎∨𝑏)=𝑎 e, por outro lado, 𝑑=𝑏∧𝑐=𝑒∧𝑐=(𝑏∨𝑐) ∧ 𝑐=𝑐, pelo que 𝑑=𝑎∨𝑐=𝑒, o que é impossível. Logo, 𝑒≠𝑏. Os restantes casos provam-se de forma análoga. Portanto, o reticulado 𝑎𝑏𝑐 𝑑 𝑒 é um sub-reticulado de 𝑅isomorfo a 𝑀3.□ Seguem-se mais alguns resultados que estabelecem formas de caraterizar a distributividade de um reticulado. Teorema 1.2.2 (cf. [2], Exercise 5.3, p. 67).Seja (𝑅;∧,∨) um reticulado. Então, 𝑅é distributivo se e só se, para quaisquer 𝑥, 𝑦, 𝑧 ∈𝑅, (𝑥∧𝑦) ∨ (𝑦∧𝑧) ∨ (𝑧∧𝑥)=(𝑥∨𝑦) ∧ (𝑦∨𝑧) ∧ (𝑧∨𝑥). Demonstração. Suponha-se, primeiramente, que o reticulado 𝑅é distributivo. Sejam 𝑥,𝑦, 𝑧 ∈𝑅. Então, (𝑥∧𝑦) ∨ (𝑦∧𝑧) ∨ (𝑧∧𝑥)=(𝑦∧ (𝑥∨𝑧)) ∨ (𝑧∧𝑥)[comutatividade e hipótese] =(𝑦∨ (𝑧∧𝑥)) ∧ ((𝑥∨𝑧) ∨ (𝑧∧𝑥)) [hipótese] =(𝑦∨ (𝑧∧𝑥)) ∧ (𝑥∨𝑧)[𝑧∧𝑥≤𝑥∨𝑧] =(𝑥∨𝑦) ∧ (𝑦∨𝑧) ∧ (𝑧∨𝑥). [hipótese e comutatividade] Reciprocamente, admita-se que, para quaisquer 𝑥, 𝑦, 𝑧 ∈𝑅, (𝑥∧𝑦) ∨ (𝑦∧𝑧) ∨ (𝑧∧𝑥)=(𝑥∨𝑦) ∧ (𝑦∨𝑧) ∧ (𝑧∨𝑥). Então, para quaisquer 𝑢, 𝑣,𝑤 ∈𝑅, ((𝑢∧𝑣) ∧ 𝑣) ∨ (𝑣∧𝑤) ∨ (𝑤∧ (𝑢∧𝑣)) =((𝑢∧𝑣) ∨ 𝑣) ∧ (𝑣∨𝑤) ∧ (𝑤∨ (𝑢∧𝑣)), 46 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS donde, pelas propriedades das operações ∧e∨, segue (𝑢∧𝑣) ∨ (𝑣∧𝑤) ∨ (𝑤∧𝑢∧𝑣)=𝑣∧ (𝑣∨𝑤) ∧ (𝑤∨ (𝑢∧𝑣)) e, consequentemente, (𝑢∧𝑣) ∨ (𝑣∧𝑤)=𝑣∧ ((𝑢∧𝑣) ∨ 𝑤).(I) Da hipótese, também resulta que, para quaisquer 𝑢, 𝑣,𝑤 ∈𝑅, 𝑢∧ ((𝑢∧𝑣) ∨ (𝑣∧𝑤) ∨ (𝑤∧𝑢)) =𝑢∧ ((𝑢∨𝑣) ∧ (𝑣∨𝑤) ∧ (𝑤∨𝑢)), e, por absorção, obtém-se 𝑢∧ ((𝑢∧𝑣) ∨ (𝑣∧𝑤) ∨ (𝑤∧𝑢)) =𝑢∧ (𝑣∨𝑤).(II) Assim, dados 𝑢, 𝑣, 𝑤 ∈𝑅, 𝑢∧ (𝑣∨𝑤)=𝑢∧ ((𝑢∧𝑣) ∨ (𝑣∧𝑤) ∨ (𝑤∧𝑢)) [(II)] =(𝑢∧𝑣) ∨ (𝑢∧ ((𝑤∧𝑢) ∨ (𝑣∧𝑤))) [(I) e comutatividade] =(𝑢∧𝑣) ∨ (𝑤∧𝑢) ∨ (𝑢∧𝑣∧𝑤)[(I)] =(𝑢∧𝑣) ∨ (𝑢∧𝑤). [comutatividade e 𝑢∧𝑣∧𝑤≤𝑢∧𝑤] Logo, o reticulado 𝑅é distributivo. □ Teorema 1.2.3 (cf. [2], Theorem 5.1, p. 67).Seja (𝑅;∧,∨) um reticulado. Então, 𝑅é distributivo se e só se, para quaisquer 𝑥, 𝑦, 𝑧 ∈𝑅, (𝑥∧𝑧=𝑦∧𝑧e𝑥∨𝑧=𝑦∨𝑧)=⇒𝑥=𝑦. Demonstração. Suponha-se, primeiramente, que 𝑅é distributivo. Sejam 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑥∧𝑧=𝑦∧𝑧 e𝑥∨𝑧=𝑦∨𝑧. Então, 𝑥=𝑥∧ (𝑥∨𝑧)[absorção] =𝑥∧ (𝑦∨𝑧)[hipótese] =(𝑥∧𝑦) ∨ (𝑥∧𝑧)[distributividade] =(𝑥∧𝑦) ∨ (𝑦∧𝑧)[hipótese] =𝑦∧ (𝑥∨𝑧)[distributividade e comutatividade] =𝑦∧ (𝑦∨𝑧)[hipótese] =𝑦. [absorção] Logo, 𝑥=𝑦. 47 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Reciprocamente, admita-se que 𝑅não é distributivo. Então, por (ii) do Teorema 1.2.1, 𝑅possui algum sub-reticulado 𝑆isomorfo a 𝑀3ou a 𝑁5. Assim, o diagrama de Hasse de 𝑆tem uma das seguintes formas: 𝑥𝑦𝑧 0 1 ou 𝑥 𝑦 𝑧 0 1 . Em ambos os casos, observa-se que 𝑥∧𝑧=𝑦∧𝑧e𝑥∨𝑧=𝑦∨𝑧, mas 𝑥≠𝑦. Dá-se, assim, por concluída a prova. □ Existem também aplicações especiais que ajudam na caraterização de reticulados distributivos. Sejam (𝑅;∧,∨) um reticulado e 𝑎∈𝑅. Representa-se por ∧𝑎a aplicação de 𝑅em 𝑅tal que, para cada 𝑥∈𝑅,∧𝑎(𝑥)=𝑥∧𝑎; e por ∨𝑎a aplicação de 𝑅em 𝑅tal que, para cada 𝑥∈𝑅,∨𝑎(𝑥)=𝑥∨𝑎. Mais, dados 𝑎,𝑏 ∈𝑅, usar-se-ão as notações 𝜑𝑎e𝜓𝑏para denotar, respetivamente, as aplicações [𝑏, 𝑎 ∨𝑏]→[𝑎∧𝑏, 𝑎] 𝑥↦→ ∧𝑎(𝑥)e[𝑎∧𝑏, 𝑎]→[𝑏, 𝑎 ∨𝑏] 𝑥↦→ ∨𝑏(𝑥). Além disso, para qualquer subconjunto 𝑆de 𝑅, denota-se a aplicação identidade em 𝑆por 𝜄𝑆. Teorema 1.2.4 (cf. [9], Theorem 4.9, p. 103).Seja (𝑅;∧,∨) um reticulado. Então, (i) 𝑅é distributivo se e só se, para qualquer 𝑎∈𝑅, a aplicação ∧𝑎é um homomorfismo de reticulados; (ii) 𝑅é distributivo se e só se, para qualquer 𝑎∈𝑅, a aplicação ∨𝑎é um homomorfismo de reticulados. Demonstração. Como as condições (i) e(ii) são duais uma da outra, basta provar uma delas; neste caso, demonstrar-se-á (i). Suponha-se, primeiramente, que 𝑅é distributivo. Seja 𝑎∈𝑅. Ora, para quaisquer 𝑥,𝑦 ∈𝑅, ∧𝑎(𝑥∧𝑦)=𝑥∧𝑦∧𝑎=(𝑥∧𝑎) ∧ (𝑦∧𝑎)=∧𝑎(𝑥) ∧ ∧𝑎(𝑦) e, por hipótese, ∧𝑎(𝑥∨𝑦)=(𝑥∨𝑦) ∧ 𝑎=(𝑥∧𝑎) ∨ (𝑦∧𝑎)=∧𝑎(𝑥) ∨ ∧𝑎(𝑦). Logo, ∧𝑎é um homomorfismo de reticulados. Reciprocamente, admitindo-se que, para qualquer 𝑎∈𝑅,∧𝑎é um homomorfismo de reticulados, então, para quaisquer 𝑥,𝑦, 𝑧 ∈𝑅, tem-se ∧𝑥(𝑦∨𝑧)=∧𝑥(𝑦) ∨ ∧𝑥(𝑧), 48 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Demonstração. Seja 𝐹=fil(𝑥). Tem-se que 𝐼∩𝐹=∅. De facto, se existisse 𝑦∈𝐼∩𝐹, então 𝑦∈𝐼 e𝑥≤𝑦, donde seguiria, por (ii) do Lema 0.3.16, que 𝑥∈𝐼, o que seria uma contradição. Assim, aplicando o Teorema 1.2.8, sabe-se que existe 𝑃∈Esp(𝑅)tal que 𝐼⊆𝑃e𝑃∩𝐹=∅. Logo, como 𝑥∈𝐹, conclui-se que 𝑥∉𝑃.□ Corolário 1.2.10 (cf. [7], Corollary 117, p. 118).Sejam 𝑅um reticulado distributivo e 𝑥,𝑦 ∈𝑅tais que 𝑥≠𝑦. Então existe um ideal primo de 𝑅que contém exatamente um dos elementos 𝑥e𝑦. Demonstração. Defina-se 𝐼=id(𝑥),𝐽=id(𝑦),𝐹=fil(𝑥)e𝐺=fil(𝑦). Suponha-se, por absurdo, que 𝐼∩𝐺≠∅e𝐽∩𝐹≠∅. Então, por um lado, existe 𝑧∈𝐼∩𝐺, pelo que 𝑧≤𝑥e𝑦≤𝑧, donde, pela transitividade, segue que 𝑦≤𝑥; por outro lado, existe 𝑤∈𝐽∩𝐹e, analogamente, conclui-se que 𝑥≤𝑦. Assim, 𝑥=𝑦, o que é um absurdo. Logo, 𝐼∩𝐺=∅ou 𝐽∩𝐹=∅. Ora, se 𝐼∩𝐺=∅, então 𝑦∉𝐼. Por conseguinte, aplicando o Corolário 1.2.9, sabe-se que existe 𝑃∈Esp(𝑅)tal que 𝐼⊆𝑃e𝑦∉𝑃. Logo, 𝑥∈𝑃e𝑦∉𝑃. Argumentos análogos mostram que, se 𝐽∩𝐹=∅, então existe 𝑄∈Esp(𝑅)tal que 𝑦∈𝑄e𝑥∉𝑄. Portanto, em qualquer um dos casos, existe um ideal primo de 𝑅que contém exatamente um dos elementos 𝑥e𝑦.□ Como consequência do Teorema 1.2.8, também é possível obter uma importante representação dos reticulados distributivos, provando-se que todo o reticulado distributivo é isomorfo a um sub-reticulado de (℘(𝑋),∩,∪), para algum conjunto 𝑋. A um sub-reticulado de (℘(𝑋),∩,∪) dá-se a designação de anel de conjuntos. Teorema 1.2.11 (cf. [7], Theorem 119, p. 118).Um reticulado 𝑅é distributivo se e só se 𝑅é isomorfo a algum anel de conjuntos. Demonstração. Seja (𝑅;∧,∨) um reticulado. Assuma-se, primeiramente, que 𝑅é isomorfo a algum anel de conjuntos. Então, para algum conjunto 𝑋,𝑅é isomorfo a algum sub-reticulado de (℘(𝑋);∩,∪). Assim, como (℘(𝑋);∩,∪) é um reticulado distributivo, por (i) e(iii) do Teorema 1.1.6, segue que 𝑅é distributivo. Reciprocamente, admita-se que 𝑅é distributivo. Para cada 𝑥∈𝑅, defina-se I(𝑥)={𝑃∈Esp(𝑅) | 𝑥∉𝑃}. Considere-se o conjunto I={I(𝑥) | 𝑥∈𝑅}. Pretende-se demonstrar que (I,∩,∪) é um anel de conjuntos. Primeiramente, note-se que I≠∅(visto que 𝑅≠∅) e que I ⊆ ℘(Esp(𝑅)). Sejam 𝑋,𝑌 ∈ I. Então, 𝑋=I(𝑥)e𝑌=I(𝑦), para alguns 𝑥,𝑦 ∈𝑅. 55 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Mostre-se que 𝑋∩𝑌∈ I, ou seja, que existe 𝑧∈𝑅tal que 𝑋∩𝑌=I(𝑧). Seja 𝑃∈𝑋∩𝑌. Então, 𝑃é um ideal primo tal que 𝑥∉𝑃e𝑦∉𝑃. Assim, pela definição de ideal primo (Definição 0.3.14), tem-se que 𝑥∧𝑦∉𝑃. Logo, 𝑃∈ I(𝑥∧𝑦). Portanto, 𝑋∩𝑌⊆ I(𝑥∧𝑦). Reciprocamente, dado 𝑃∈ I(𝑥∧𝑦), tem-se que 𝑃é um ideal primo tal que 𝑥∧𝑦∉𝑃. Então, pela definição de ideal (Definição 0.3.14), tem-se que 𝑥∉𝑃e𝑦∉𝑃; de facto, é simples ver que, se 𝑥∈𝑃ou 𝑦∈𝑃, então, pelo facto de 𝑃ser ideal, ter-se-ia 𝑥∧𝑦∈𝑃, o que contradiria a hipótese. Logo, 𝑃∈𝑋∩𝑌. Portanto, I(𝑥∧𝑦) ⊆ 𝑋∩𝑌. Conclui-se, assim, o que era pretendido. Verifique-se, agora, que 𝑋∪𝑌∈ I, ou seja, que existe 𝑤∈𝑅tal que 𝑋∪𝑌=I(𝑤). Seja 𝑃∈𝑋∪𝑌. Caso 𝑃∈𝑋, tem-se que 𝑃é um ideal primo tal que 𝑥∉𝑃. Então, 𝑥∨𝑦∉𝑃; caso contrário, como 𝑥≤𝑥∨𝑦, ter-se-ia, por (ii) do Lema 0.3.16, que 𝑥∈𝑃, o que não acontece. Logo, 𝑃∈ I(𝑥∨𝑦). Analogamente se prova que, se 𝑃∈𝑌, então 𝑃∈ I(𝑥∨𝑦). Portanto, 𝑋∪𝑌⊆ I(𝑥∨𝑦). Reciprocamente, seja 𝑃∈ I(𝑥∨𝑦). Então, 𝑃é um ideal primo tal que 𝑥∨𝑦∉𝑃. Por conseguinte, 𝑥∉𝑃ou 𝑦∉𝑃; caso contrário, por (i) do Lema 0.3.16, ter-se-ia um absurdo. Portanto, 𝑃∈𝑋ou 𝑃∈𝑌, ou seja, 𝑃∈𝑋∪𝑌. Fica, assim, provado que 𝑋∪𝑌=I(𝑥∨𝑦), ou seja, 𝑋∪𝑌∈ I. Mostre-se, agora, que é possível definir um isomorfismo de (𝑅;∧,∨) em (𝐼, ∩,∪). Para tal, considerese a aplicação 𝜑de 𝑅em Ital que, para qualquer 𝑥∈𝑅, 𝜑(𝑥)=I(𝑥). Esta aplicação está bem definida: para qualquer 𝑥∈𝑅,I(𝑥) ∈ I; além disso, é fácil ver que, dados 𝑥,𝑦 ∈𝑅tais que 𝑥=𝑦, se tem I(𝑥)=I(𝑦), ou seja, 𝜑(𝑥)=𝜑(𝑦). A aplicação 𝜑é injetiva. De facto, se 𝑥,𝑦 ∈𝑅são tais que 𝑥≠𝑦, então, pelo Corolário 1.2.10, existe um ideal primo 𝑃de 𝑅que contém exatamente um dos elementos 𝑥e𝑦. Por conseguinte, 𝑃pertence a exatamente um dos conjuntos I(𝑥)ou I(𝑦). Logo, I(𝑥)≠I(𝑦), ou seja, 𝜑(𝑥)≠𝜑(𝑦). Seja, agora, 𝑋∈ I. Então, 𝑋=I(𝑥), para algum 𝑥∈𝑅. Logo, 𝑋=𝜑(𝑥). Portanto, além de ser injetiva, a aplicação 𝜑é sobrejetiva, ou seja, 𝜑é uma bijeção. Foi visto anteriormente que, para quaisquer 𝑥,𝑦 ∈𝑅, se tem I(𝑥∧𝑦)=I(𝑥) ∩ I(𝑦)eI(𝑥∨𝑦)=I(𝑥) ∪ I(𝑦), ou seja, 𝜑(𝑥∧𝑦)=𝜑(𝑥) ∩ 𝜑(𝑦)e𝜑(𝑥∨𝑦)=𝜑(𝑥) ∪ 𝜑(𝑦). Portanto, 𝜑é um homomorfismo de reticulados. Conclui-se, assim, o que era pretendido, donde resulta que 𝑅I.□ 56 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS 1.2.3 Caraterização e representação de reticulados distributivos recorrendo a relações de congruência Nesta subsecção, dá-se continuidade ao estudo sobre relações de congruência em reticulados, abordando, agora, as suas propriedades quando os reticulados aos quais estão associadas forem distributivos. Teorema 1.2.12 (cf. [2], Theorem 8.10, p. 126).Seja 𝑅um reticulado distributivo. Então, para quaisquer 𝑥,𝑦 ∈𝑅, con(𝑥,𝑦)={(𝑧, 𝑤) ∈ 𝑅2|𝑧∧𝑥∧𝑦=𝑤∧𝑥∧𝑦e𝑧∨𝑥∨𝑦=𝑤∨𝑥∨𝑦}. Demonstração. Defina-se 𝜃={(𝑧,𝑤) ∈ 𝑅2|𝑧∧𝑥∧𝑦=𝑤∧𝑥∧𝑦e𝑧∨𝑥∨𝑦=𝑤∨𝑥∨𝑦}. Mostre-se que 𝜃é a menor congruência em 𝑅que contém o par (𝑥,𝑦). É óbvio que 𝜃é reflexiva e simétrica. Sejam 𝑧, 𝑤, 𝑣 ∈𝑅tais que 𝑧𝜃𝑤 e𝑤𝜃𝑣. Assim, (I) 𝑧∧𝑥∧𝑦=𝑤∧𝑥∧𝑦; (II) 𝑧∨𝑥∨𝑦=𝑤∨𝑥∨𝑦; (III) 𝑤∧𝑥∧𝑦=𝑣∧𝑥∧𝑦; (IV) 𝑤∨𝑥∨𝑦=𝑣∨𝑥∨𝑦. Logo, por (I) e(III),𝑧∧𝑥∧𝑦=𝑣∧𝑥∧𝑦e, por (II) e(IV),𝑧∨𝑥∨𝑦=𝑣∨𝑥∨𝑦, pelo que 𝑧𝜃𝑣, o que prova a transitividade de 𝜃. Sejam, agora, 𝑧,𝑤,𝑟 ∈𝑅tais que 𝑧𝜃𝑤. Então, são válidas as condições (I) e(II), donde resulta (𝑧∧𝑟) ∧ 𝑥∧𝑦=(𝑧∧𝑥∧𝑦) ∧ 𝑟=(𝑤∧𝑥∧𝑦) ∧ 𝑟=(𝑤∧𝑟) ∧ 𝑥∧𝑦 e (𝑧∧𝑟) ∨ 𝑥∨𝑦=(𝑧∨𝑥∨𝑦) ∧ (𝑟∨𝑥∨𝑦)=(𝑤∨𝑥∨𝑦) ∧ (𝑟∨𝑥∨𝑦)=(𝑤∧𝑟) ∨ 𝑥∨𝑦. Logo, (𝑧∧𝑟)𝜃(𝑤∧𝑟). Procedendo de forma semelhante, também se conclui que (𝑧∨𝑟)𝜃(𝑤∨𝑟). Portanto, 𝜃é uma congruência em 𝑅. Também não é difícil verificar que 𝑥𝜃𝑦. De facto, 𝑥∧𝑥∧𝑦=𝑥∧𝑦=𝑦∧𝑥∧𝑦e𝑥∨𝑥∨𝑦=𝑥∨𝑦=𝑦∨𝑥∨𝑦. Por fim, considere-se uma qualquer congruência 𝜗em 𝑅tal que 𝑥𝜗𝑦. Sejam 𝑧,𝑤 ∈𝑅tais que 𝑧𝜃𝑤. Por um lado, por definição de 𝜃, tem-se 57 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS (V) 𝑧∧𝑥∧𝑦=𝑤∧𝑥∧𝑦; (VI) 𝑧∨𝑥∨𝑦=𝑤∨𝑥∨𝑦. Por outro lado, como 𝜗é uma congruência, tem-se, por (ii) do Lema 0.3.29, (𝑥∧𝑦)𝜗(𝑥∨𝑦)e, consequentemente, (VII) (𝑧∧𝑥∧𝑦)𝜗(𝑧∧ (𝑥∨𝑦)); (VIII) (𝑧∨ (𝑥∧𝑦))𝜗(𝑧∨𝑥∨𝑦). Ora, por (VI) e(VIII), tem-se (𝑧∨ (𝑥∧𝑦))𝜗(𝑤∨𝑥∨𝑦), pelo que (𝑧∧ (𝑧∨ (𝑥∧𝑦)))𝜗(𝑧∧ (𝑤∨𝑥∨𝑦)), ou seja, 𝑧𝜗 ((𝑧∧𝑤) ∨ (𝑧∧𝑥) ∨ (𝑧∧𝑦)). Além disso, por (V) e(VII), segue que (𝑤∧𝑥∧𝑦)𝜗(𝑧∧ (𝑥∨𝑦)). Assim, ((𝑧∧𝑤) ∨ (𝑤∧𝑥∧𝑦))𝜗((𝑧∧𝑤) ∨ (𝑧∧ (𝑥∨𝑦))), ou seja, ((𝑧∧𝑤) ∨ (𝑤∧𝑥∧𝑦))𝜗((𝑧∧𝑤) ∨ (𝑧∧𝑥) ∨ (𝑧∧𝑦)). Logo, pela simetria e transitividade, 𝑧𝜗 ((𝑤∧𝑧) ∨ (𝑤∧𝑥∧𝑦)), isto é, 𝑧𝜗 (𝑤∧ (𝑧∨ (𝑥∧𝑦))). Além disso, por (VIII), tem-se (𝑤∧ (𝑧∨ (𝑥∧𝑦)))𝜗(𝑤∧ (𝑧∨𝑥∨𝑦)), onde, por (VI), 𝑤∧ (𝑧∨𝑥∨𝑦)=𝑤∧ (𝑤∨𝑥∨𝑦)=𝑤. Logo, por transitividade, 𝑧𝜗𝑤, pelo que 𝜃⊆𝜗. Portanto, con(𝑥,𝑦)=𝜃.□ 58 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Apresentam-se, de seguida, alguns corolários do teorema anterior. Corolário 1.2.13 (cf. [7], Theorem 141, pp. 138–139).Seja 𝑅um reticulado distributivo. Então, para quaisquer 𝑥,𝑦 ∈𝑅tais que 𝑥≤𝑦, con(𝑥,𝑦)={(𝑧, 𝑤) ∈ 𝑅2|𝑧∧𝑥=𝑤∧𝑥e𝑧∨𝑦=𝑤∨𝑦}. Corolário 1.2.14 (cf. [8], Theorem 1, pp. 141–142).Seja (𝑅;∧,∨) um reticulado distributivo e tomem- -se 𝑥,𝑦 ∈𝑅tais que 𝑥≤𝑦. Então, para quaisquer 𝑧,𝑤 ∈𝑅tais que 𝑧≤𝑤, são equivalentes as condições seguintes: (i) (𝑧,𝑤) ∈ con(𝑥,𝑦); (ii) (𝑥∨𝑧) ∧ 𝑤=𝑧e(𝑦∨𝑧) ∧ 𝑤=𝑤. Demonstração. Sejam 𝑧,𝑤 ∈𝑅tais que 𝑧≤𝑤. Suponha-se, primeiramente, que (𝑧,𝑤) ∈ con(𝑥,𝑦). Então, pelo Corolário 1.2.13, 𝑧∧𝑥=𝑤∧𝑥e𝑧∨𝑦=𝑤∨𝑦. Assim, (𝑥∨𝑧) ∧ 𝑤=(𝑥∧𝑤) ∨ (𝑧∧𝑤)[distributividade] =(𝑥∧𝑧) ∨ 𝑧[𝑥∧𝑤=𝑥∧𝑧;𝑧≤𝑤] =𝑧[absorção] e (𝑦∨𝑧) ∧ 𝑤=(𝑦∨𝑤) ∧ 𝑤[𝑦∨𝑧=𝑦∨𝑤] =𝑤. [absorção] Reciprocamente, assuma-se que a condição (ii) é válida. Segundo o Corolário 1.2.13, para provar que (𝑧,𝑤) ∈ con(𝑥,𝑦), basta verificar que 𝑧∧𝑥=𝑤∧𝑥e𝑧∨𝑦=𝑤∨𝑦. Ora, 𝑧∧𝑥=(𝑥∨𝑧) ∧ 𝑤∧𝑥[hipótese] =𝑤∧𝑥. [absorção] 59 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Além disso, como, pela Proposição 1.1.5, 𝑅é também modular, segue 𝑤=(𝑦∨𝑧) ∧ 𝑤[hipótese] =(𝑦∧𝑤) ∨ 𝑧. [𝑧≤𝑤e modularidade] Logo, 𝑤∨𝑦=(𝑦∧𝑤) ∨ 𝑧∨𝑦 =𝑧∨𝑦, [absorção] tal como se pretendia provar. Fica assim concluída a demonstração. □ Corolário 1.2.15 (cf. [7], Corollary 143, p. 141).Sejam 𝑅um reticulado distributivo e 𝑥,𝑦, 𝑧, 𝑤 ∈𝑅 tais que 𝑥≤𝑦≤𝑧≤𝑤ou 𝑧≤𝑤≤𝑥≤𝑦. Então, (𝑧,𝑤) ∈ con(𝑥,𝑦)=⇒𝑧=𝑤. Teorema 1.2.16 (cf. [2], Theorem 8.11, pp. 126–127).Seja 𝑅um reticulado distributivo. Então, a interseção de duas congruências principais em 𝑅é também uma congruência principal. Mais precisamente, dados 𝑥,𝑦, 𝑧, 𝑤 ∈𝑅tais que 𝑥≤𝑦e𝑧≤𝑤, tem-se con(𝑥,𝑦) ∩ con(𝑧, 𝑤)=con(𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤). Demonstração. Sejam 𝑥,𝑦, 𝑧, 𝑤 ∈𝑅tais que 𝑥≤𝑦e𝑧≤𝑤. Considerando o Lema 0.3.30, para mostrar que con(𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤) ⊆ con(𝑥,𝑦) ∩ con(𝑧,𝑤), é suficiente verificar que (𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤) ∈ con(𝑥,𝑦) ∩ con(𝑧,𝑤). Ora, é facil ver que (𝑦∧𝑤∧ (𝑥∨𝑧)) ∧ 𝑥=(𝑦∧𝑤) ∧ 𝑥 e que (𝑦∧𝑤∧ (𝑥∨𝑧)) ∨ 𝑦=𝑦=(𝑦∧𝑤) ∨ 𝑦. Logo, pelo Corolário 1.2.13, (𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤) ∈ con(𝑥,𝑦). 60 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS De forma semelhante se prova que (𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤) ∈ con(𝑧, 𝑤). Reciprocamente, seja (𝑟, 𝑠) ∈ con(𝑥,𝑦) ∩ con(𝑧,𝑤). Então, sabendo que 𝑥≤𝑦e𝑧≤𝑤e recorrendo ao Corolário 1.2.13, tem-se (I) 𝑟∧𝑥=𝑠∧𝑥; (II) 𝑟∨𝑦=𝑠∨𝑦; (III) 𝑟∧𝑧=𝑠∧𝑧; (IV) 𝑟∨𝑤=𝑠∨𝑤. Além disso, como 𝑦∧𝑤∧ (𝑥∨𝑧) ≤ 𝑦∧𝑤, sabe-se, pelo Corolário 1.2.13, que con(𝑦∧𝑤∧(𝑥∨𝑧),𝑦∧𝑤)=((𝑎,𝑏) ∈ 𝑅2 𝑎∧ (𝑦∧𝑤∧ (𝑥∨𝑧)) =𝑏∧ (𝑦∧𝑤∧ (𝑥∨𝑧)), 𝑎∨ (𝑦∧𝑤)=𝑏∨ (𝑦∧𝑤)). Ora, 𝑟∧ (𝑦∧𝑤∧ (𝑥∨𝑧)) =(𝑟∧𝑦∧𝑤∧𝑥) ∨ (𝑟∧𝑦∧𝑤∧𝑧)[distributividade] =(𝑟∧𝑥∧𝑤) ∨ (𝑟∧𝑧∧𝑦)[𝑥≤𝑦;𝑧≤𝑤] =(𝑠∧𝑥∧𝑤) ∨ (𝑠∧𝑧∧𝑦)[(I) e(III)] =(𝑠∧𝑦∧𝑤∧𝑥) ∨ (𝑠∧𝑦∧𝑤∧𝑧)[𝑥≤𝑦;𝑧≤𝑤] =𝑠∧ (𝑦∧𝑤∧ (𝑥∨𝑧)) [distributividade] e 𝑟∨ (𝑦∧𝑤)=(𝑟∨𝑦) ∧ (𝑟∨𝑤)[distributividade] =(𝑠∨𝑦) ∧ (𝑠∨𝑤)[(II) e(IV)] =𝑠∨ (𝑦∧𝑤). [distributividade] Portanto, (𝑟, 𝑠) ∈ con(𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤). Conclui-se assim que con(𝑥,𝑦) ∩ con(𝑧, 𝑤) ⊆ con(𝑦∧𝑤∧ (𝑥∨𝑧),𝑦 ∧𝑤), o que completa a prova. □ Teorema 1.2.17 (cf. [7], Corollary 142, pp. 140–141).Sejam 𝑅um reticulado distributivo e 𝐼∈Id(𝑅). Então, con(𝐼)={(𝑥,𝑦) ∈ 𝑅2|𝑥∨𝑦=(𝑥∧𝑦) ∨ 𝑎, para algum 𝑎∈𝐼}. Além disso, 𝐼é uma classe de congruência de con(𝐼)em 𝑅. 61 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Demonstração. Defina-se 𝜃={(𝑥,𝑦) ∈ 𝑅2|𝑥∨𝑦=(𝑥∧𝑦) ∨ 𝑎, para algum 𝑎∈𝐼}. Pretende-se provar que 𝜃∈Con(𝑅). Seja 𝑥∈𝑅. Como 𝐼≠∅, existe 𝑎∈𝐼. Por conseguinte, 𝑥∧𝑎∈𝐼. Então, 𝑥∨𝑥=𝑥=𝑥∨ (𝑥∧𝑎)=(𝑥∧𝑥) ∨ (𝑥∧𝑎). Logo, 𝑥𝜃𝑥. Portanto, 𝜃satisfaz (i) do Lema 0.3.29. É óbvio que 𝜃também observa (ii) do mesmo lema. Sejam 𝑥,𝑦, 𝑧 ∈𝑅tais que 𝑥≤𝑦≤𝑧e suponha-se que 𝑥𝜃𝑦 e𝑦𝜃𝑧. Então, existem 𝑎,𝑏 ∈𝐼tais que 𝑥∨𝑦=(𝑥∧𝑦) ∨ 𝑎e𝑦∨𝑧=(𝑦∧𝑧) ∨ 𝑏, ou seja, 𝑦=𝑥∨𝑎e𝑧=𝑦∨𝑏. Assim, 𝑥∨𝑧=𝑧=𝑦∨𝑏=(𝑥∨𝑎) ∨ 𝑏=(𝑥∧𝑧) ∨ (𝑎∨𝑏), com 𝑎∨𝑏∈𝐼. Logo, 𝑥𝜃𝑧, provando-se, assim, que (iii) do Lema 0.3.29 também é válida. Sejam 𝑥,𝑦 ∈𝑅tais que 𝑥≤𝑦e𝑥𝜃𝑦. Então, existe 𝑎∈𝐼tal que 𝑥∨𝑦=(𝑥∧𝑦) ∨ 𝑎, ou seja, 𝑦=𝑥∨𝑎. Assim, como, para qualquer 𝑤∈𝑅,𝑥∧𝑤≤𝑦∧𝑤, então (𝑥∧𝑤) ∨ (𝑦∧𝑤)=𝑦∧𝑤 =(𝑥∨𝑎) ∧ 𝑤 =(𝑥∧𝑤) ∨ (𝑎∧𝑤) =((𝑥∧𝑤) ∧ (𝑦∧𝑤)) ∨ (𝑎∧𝑤), com 𝑎∧𝑤∈𝐼; também se tem 𝑥∨𝑤≤𝑦∨𝑤e, por isso, (𝑥∨𝑤) ∨ (𝑦∨𝑤)=𝑦∨𝑤 =(𝑥∨𝑎) ∨ 𝑤 =(𝑥∨𝑤) ∨ 𝑎 =((𝑥∨𝑤) ∧ (𝑦∨𝑤)) ∨ 𝑎; logo, (𝑥∧𝑤)𝜃(𝑦∧𝑤)e(𝑥∨𝑤)𝜃(𝑦∨𝑤). Portanto, 𝜃respeita também a condição (iv) do Lema 0.3.29, pelo que se confirma que 𝜃∈Con(𝑅). Seja (𝑢, 𝑣) ∈ 𝐼2. Então, 𝑢∨𝑣=(𝑢∧𝑣) ∨ (𝑢∨𝑣), onde, claramente, 𝑢∨𝑣∈𝐼. Logo, 𝑢𝜃𝑣, donde se conclui que 𝐼2⊆𝜃. Seja 𝜗∈Con(𝑅)tal que 𝐼2⊆𝜗. Sejam, também, 𝑥,𝑦 ∈𝑅tais que 𝑥𝜃𝑦. Então, existe 𝑎∈𝐼 tal que 𝑥∨𝑦=(𝑥∧𝑦) ∨ 𝑎. Assim, como 𝑥∧𝑦∧𝑎∈𝐼, tem-se (𝑥∧𝑦∧𝑎, 𝑎) ∈ 𝐼2e, portanto, (𝑥∧𝑦∧𝑎)𝜗𝑎. Como 𝜗∈Con(𝑅), segue que ((𝑥∧𝑦) ∨ (𝑥∧𝑦∧𝑎))𝜗((𝑥∧𝑦) ∨ 𝑎), 62 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS ou seja, (𝑥∧𝑦)𝜗(𝑥∨𝑦), donde resulta que 𝑥𝜗𝑦. Portanto, 𝜃⊆𝜗. Conclui-se, assim, que con(𝐼)=𝜃. Por fim, sejam 𝑎∈𝐼e𝑏∈𝑅tais que (𝑎,𝑏) ∈ con(𝐼). Então, 𝑎∨𝑏=(𝑎∧𝑏) ∨ 𝑢, para algum 𝑢∈𝐼. Assim, como 𝑎∧𝑏,𝑢 ∈𝐼, tem-se que 𝑎∨𝑏=(𝑎∧𝑏) ∨𝑢∈𝐼. Portanto, uma vez que 𝑏≤𝑎∨𝑏, segue que 𝑏∈𝐼, ficando assim provado que 𝐼é uma classe de congruência de con(𝐼)em 𝑅.□ Estabelecem-se, de seguida, algumas caraterizações para reticulados distributivos, com base em propriedades de congruências. Teorema 1.2.18 (cf. [8], Theorem 2, pp. 143–145).Seja 𝑅um reticulado. Todas as condições seguintes são equivalentes: (i) 𝑅é um reticulado distributivo; (ii) para quaisquer 𝑥, 𝑦, 𝑧, 𝑤 ∈𝑅, se (𝑧, 𝑤) ∈ con(𝑥,𝑦), então é impossível que 𝑥≤𝑤(ou 𝑧≤𝑦) sempre que 𝑦≤𝑥e𝑤<𝑧; (iii) para quaisquer 𝑥,𝑦 ∈𝑅tais que 𝑦≤𝑥, o intervalo [𝑦, 𝑥]é uma classe de congruência de con(𝑥,𝑦)em 𝑅; (iv) para quaisquer 𝑥,𝑦, 𝑧, 𝑤 ∈𝑅tais que 𝑤≤𝑧≤𝑦≤𝑥,con(𝑥,𝑦) ∩ con(𝑧,𝑤)=△𝑅; (v) para quaisquer 𝐼∈Id(𝑅)e𝑥,𝑦 ∈𝑅tais que 𝑦≤𝑥,(𝑥,𝑦) ∈ con(𝐼)se e só se 𝑥=𝑦∨𝑎, para algum 𝑎∈𝐼. Demonstração. Suponha-se, primeiramente, que o reticulado 𝑅é distributivo. Pretende-se provar (ii). Para tal, sejam 𝑥,𝑦, 𝑧,𝑤 ∈𝑅. Admita-se que (𝑧,𝑤) ∈ con(𝑥,𝑦)=con(𝑦, 𝑥) e que 𝑦≤𝑥e𝑤<𝑧. Assim, (𝑤, 𝑧) ∈ con(𝑥,𝑦)e, pelo Corolário 1.2.14, tem-se (𝑦∨𝑤) ∧ 𝑧=𝑤(I) e(𝑥∨𝑤) ∧ 𝑧=𝑧(II). Ora, se 𝑥≤𝑤, então 𝑧=(𝑥∨𝑤) ∧ 𝑧[(II)] =𝑤∧𝑧[𝑥≤𝑤] =𝑤, [𝑤<𝑧] 63 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS o que contradiria a hipótese. De modo análogo se prova que, se 𝑧≤𝑦, então, por (I), também haveria uma contradição. De facto, (ii) verifica-se. Mostre-se, agora, que (iii) também é válida. Para tal, sejam 𝑥,𝑦 ∈𝑅tais que 𝑦≤𝑥. Para provar que [𝑦, 𝑥]é uma classe de congruência de con(𝑥,𝑦)em 𝑅, uma vez que 𝑦∈ [𝑦, 𝑥], basta mostrar que [𝑦, 𝑥]=[𝑦]con(𝑥,𝑦). Seja 𝑧∈ [𝑦, 𝑥]. Então, 𝑦≤𝑧≤𝑥. Assim, como (𝑥,𝑦) ∈ con(𝑥,𝑦), tem-se (𝑧,𝑦)=(𝑥∧𝑧,𝑦 ∧𝑧) ∈ con(𝑥,𝑦). Logo, 𝑧∈ [𝑦]con(𝑥,𝑦), donde segue que [𝑦, 𝑥] ⊆ [𝑦]con(𝑥,𝑦). Seja 𝑧∈ [𝑦]con(𝑥,𝑦). Então, (𝑧,𝑦) ∈ con(𝑥,𝑦). Suponha-se, por absurdo, que 𝑧∉[𝑦, 𝑥]. Assim, 𝑧∧𝑦<𝑦ou 𝑥<𝑧∨𝑥; de facto, se 𝑧∧𝑦=𝑦e𝑥=𝑧∨𝑥, ter-se-ia 𝑦≤𝑧≤𝑥, ou seja, 𝑧∈ [𝑦, 𝑥], o que não acontece. Mais ainda, uma vez que (𝑧,𝑦) ∈ con(𝑥,𝑦)e, consequentemente, (𝑧, 𝑥) ∈ con(𝑥,𝑦), segue que (𝑧∧𝑦,𝑦)=(𝑧∧𝑦,𝑦 ∧𝑦) ∈ con(𝑥,𝑦) e (𝑧∨𝑥, 𝑥)=(𝑧∨𝑥, 𝑥 ∨𝑥) ∈ con(𝑥,𝑦). Ora, caso 𝑧∧𝑦<𝑦, e juntando isso ao facto de (𝑦, 𝑧 ∧𝑦) ∈ con(𝑥,𝑦)e𝑦≤𝑥, segue, por (ii), que é impossível que 𝑦≤𝑦, o que é uma contradição. Analogamente se prova que 𝑥<𝑧∨𝑥também conduz a uma contradição. Logo, 𝑧∈ [𝑦, 𝑥], pelo que [𝑦]con(𝑥,𝑦)⊆ [𝑦, 𝑥]. Conclui-se, assim, que [𝑦, 𝑥]=[𝑦]con(𝑥,𝑦), tal como era pretendido. Portanto, (iii) também se verifica. Prove-se, agora, a condição (iv). Para tal, tomem-se 𝑥,𝑦, 𝑧, 𝑤 ∈𝑅tais que 𝑤≤𝑧≤𝑦≤𝑥. Então, con(𝑥,𝑦) ∩ con(𝑧, 𝑤)=con(𝑦, 𝑥) ∩ con(𝑤, 𝑧)[qualquer congruência é simétrica] =con(𝑥∧𝑧∧ (𝑦∨𝑤), 𝑥 ∧𝑧)[Teorema 1.2.16] =con(𝑧∧𝑦, 𝑧)[𝑧≤𝑥e𝑤≤𝑦] =con(𝑧, 𝑧). [𝑧≤𝑦] 64 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Assim, 𝑥𝑝=𝑥𝑝∧𝑥[absorção] =𝑥𝑝∧ (𝑦𝑞∨𝑟) =(𝑥𝑝∧𝑦𝑞) ∨ (𝑥𝑝∧𝑟), [distributividade] donde, pelo facto de 𝑥𝑝ser ∨-irredutível, 𝑥𝑝=𝑥𝑝∧𝑦𝑞ou 𝑥𝑝=𝑥𝑝∧𝑟, ou seja, 𝑥𝑝≤𝑦𝑞ou 𝑥𝑝≤𝑟. Só que não é possível que 𝑥𝑝≤𝑟: efetivamente, ter-se-ia 𝑟=𝑥𝑝∨𝑟=𝑥e, portanto, 𝑥𝑝seria redundante em Ô𝑚 𝑖=1𝑥𝑖, o que contradiria a hipótese. Logo, 𝑥𝑝≤𝑦𝑞. Aplicando, agora, novamente o Teorema 1.2.20, tem-se que, para algum 𝑘∈ {1, . . . ,𝑚},𝑥=𝑦𝑞∨𝑠=𝑥𝑘∨𝑠, onde 𝑠=𝑦1∨ · · · ∨ 𝑦𝑞−1∨𝑦𝑞+1∨ · · · ∨ 𝑦𝑛. Por argumentos análogos aos anteriores, obtém-se 𝑦𝑞≤𝑥𝑘. Por conseguinte, 𝑥𝑝≤𝑦𝑞≤𝑥𝑘. Então, 𝑥𝑘=𝑥𝑝∨𝑥𝑘, pelo que, se 𝑝≠𝑘,𝑥𝑝seria redundante em Ô𝑚 𝑖=1𝑥𝑖, o que, por hipótese, não acontece. Portanto, 𝑝=𝑘, donde resulta 𝑥𝑝=𝑦𝑞, tal como era pretendido. □ No resultado seguinte, estabelecem-se algumas caraterizações da distributividade de um reticulado finito com base nos conceitos de elemento ∨-irredutível e elemento primo. Teorema 1.2.24 (cf. [6], Theorem 3, p. 94).Num reticulado finito 𝑅, são equivalentes as seguintes condições: (i) 𝑅é distributivo; (ii) qualquer elemento ∨-irredutível de 𝑅é um elemento primo, ou seja, S(𝑅) ⊆ P(𝑅); (iii) para qualquer 𝑥∈𝑅,𝑥=ÔP(𝑥); (iv) para quaisquer 𝑥,𝑦 ∈𝑅tais que 𝑥≠𝑦,P(𝑥)≠P(𝑦). Demonstração. Seja 𝑅um reticulado finito. Suponha-se que 𝑅é distributivo. Pretende-se demonstrar que S(𝑅) ⊆ P(𝑅). Seja 𝑥∈ S(𝑅). Então, 𝑥≠0. Tomem-se quaisquer 𝑟,𝑠 ∈𝑅tais que 𝑥≤𝑟∨𝑠. Assim, 𝑥=𝑥∧ (𝑟∨𝑠)=(𝑥∧𝑟) ∨ (𝑥∧𝑠), graças à distributividade de 𝑅. Como 𝑥é∨-irredutível, então 𝑥=𝑥∧𝑟ou 𝑥=𝑥∧𝑠, ou seja, 𝑥≤𝑟ou 𝑥≤𝑠. Logo, 𝑥∈ P(𝑅). Suponha-se, agora, que S(𝑅) ⊆ P(𝑅). Pretende-se comprovar a veracidade da condição (iii). Seja 𝑥∈𝑅. Ora, pela hipótese, é muito simples perceber que S(𝑥) ⊆ P(𝑥). Além disso, pela Proposição 0.3.50, tem-se P(𝑥) ⊆ S(𝑥), donde S(𝑥)=P(𝑥). Logo, ÜS(𝑥)=ÜP(𝑥). 71 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Mais, pelo Corolário 0.3.48, obtém-se 𝑥=ÜS(𝑥)=ÜP(𝑥). Portanto, 𝑥=ÔP(𝑥). É muito simples verificar que (iii) =⇒(iv). De facto, para quaisquer 𝑥,𝑦 ∈𝑅, tem-se, por aplicação de (iii), que 𝑥≠𝑦=⇒ÜP(𝑥)≠ÜP(𝑦)=⇒ P(𝑥)≠P(𝑦). Suponha-se, agora, que (iv) é válida. Se 𝑅é um reticulado trivial, é óbvio que 𝑅é distributivo. Se 𝑅 não é trivial, então existem 𝑥,𝑦 ∈𝑅tais que P(𝑥)≠P(𝑦). Portanto, 𝑅tem elementos primos. Neste caso, seja 𝑛∈ℕo número máximo de elementos primos de 𝑅incomparáveis dois a dois. Pelo Teorema 0.3.51, existem 𝑛cadeias finitas 𝐶1,𝐶2, . . . ,𝐶𝑛em 𝑅e um homomorfismo de reticulados 𝜓de 𝑅no produto direto Î𝑛 𝑖=1𝐶𝑖tais que, para quaisquer 𝑥,𝑦 ∈𝑅, 𝜓(𝑥)=𝜓(𝑦) ⇐⇒ P(𝑥)=P(𝑦). Facilmente se conclui por (iv) que𝜓é um monomorfismo de 𝑅em Î𝑛 𝑖=1𝐶𝑖. Logo,𝜓é um isomorfismo de 𝑅em𝜓(𝑅), onde𝜓(𝑅)é um sub-reticulado de Î𝑛 𝑖=1𝐶𝑖, como estabelece a Proposição 0.3.8. Uma vez que toda a cadeia𝐶𝑖é um reticulado distributivo, o produto Î𝑛 𝑖=1𝐶𝑖é também um reticulado distributivo. Logo, 𝜓(𝑅)é um reticulado distributivo. Portanto, como 𝑅𝜓(𝑅),𝑅é um reticulado distributivo. Fica, assim, concluída a prova do Teorema 1.2.24. □ Com tudo o que já foi estudado, recorrendo, sobretudo, aos Teoremas 0.3.51, 0.3.52 e 1.2.24, é possível concluir que um reticulado distributivo finito pode ser mergulhado num produto direto de cadeias finitas, isto é, é isomorfo a um sub-reticulado de um produto direto de cadeias finitas. No caso de um reticulado trivial, é óbvio que esta afirmação se verifica. Na situação de um reticulado não trivial, a veracidade da referida afirmação segue do teorema seguinte. Teorema 1.2.25 (cf. [6], p. 94).Sejam 𝑅um reticulado distributivo finito e 𝑛∈ℕ0o número máximo de sucessores distintos de um qualquer elemento de 𝑅. Então, o número máximo de elementos ∨-irredutíveis de 𝑅incomparáveis dois a dois é dado também por 𝑛e, se 𝑛≥1,𝑅é isomorfo a algum sub-reticulado de algum produto direto de 𝑛cadeias finitas. Demonstração. Sabe-se, pelo Teorema 0.3.52, que𝑚≤𝑛≤𝑝, onde 𝑚, 𝑝 ∈ℕ0são, respetivamente, o número máximo de elementos primos de 𝑅incomparáveis dois a dois e o número máximo de elementos ∨-irredutíveis de 𝑅incomparáveis dois a dois. Além disso, como 𝑅é um reticulado distributivo finito, então, pela Proposição 0.3.50 e por (ii) do Teorema 1.2.24, tem-se que as noções de elemento primo e de elemento ∨-irredutível são equivalentes em 𝑅, pelo que 𝑚=𝑝. Logo, 𝑛=𝑚=𝑝, donde se conclui, 72 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS em particular, que, de facto, 𝑛também representa o número máximo de elementos ∨-irredutíveis de 𝑅 incomparáveis dois a dois. Suponha-se que 𝑛≥1. Então, pelo Teorema 0.3.51, existem 𝑛cadeias finitas 𝐶1,𝐶2, . . . ,𝐶𝑛em 𝑅 e um homomorfismo de reticulados 𝜓de 𝑅em Î𝑛 𝑖=1𝐶𝑖tais que, para quaisquer 𝑥,𝑦 ∈𝑅, 𝜓(𝑥)=𝜓(𝑦) ⇐⇒ P(𝑥)=P(𝑦). Ora, pela Proposição 0.3.8, tem-se que 𝜓(𝑅)é um sub-reticulado de Î𝑛 𝑖=1𝐶𝑖. Assim, considerando-se a aplicação 𝜑de 𝑅em 𝜓(𝑅)definida por 𝜑(𝑥)=𝜓(𝑥), para qualquer 𝑥∈𝑅, facilmente se verifica que 𝜑é um isomorfismo de reticulados: a sobrejetividade é óbvia; a injetividade também é imediata pela condição (iv) do Teorema 1.2.24. Portanto, 𝑅é isomorfo ao sub-reticulado 𝜓(𝑅)do produto direto Î𝑛 𝑖=1𝐶𝑖de 𝑛cadeias finitas em 𝑅.□ Segue-se, agora, um estudo sobre reticulados distributivos e algumas das suas propriedades envolvendo elementos complementados. Proposição 1.2.26 (cf. [2], Theorem 6.1, p. 78).Qualquer reticulado modular complementado é relativamente complementado. Demonstração. Sejam (𝑅;∧,∨) um reticulado modular complementado, 𝑟,𝑠 ∈𝑅tais que 𝑟≤𝑠e 𝑥∈ [𝑟,𝑠]. Como 𝑅é um reticulado complementado, 𝑥possui algum complemento, 𝑦∈𝑅. Seja 𝑧∈𝑅 o elemento de 𝑅tal que 𝑧=𝑟∨ (𝑠∧𝑦). Pela modularidade, também se tem 𝑧=𝑠∧ (𝑟∨𝑦). Claramente, 𝑟≤𝑧e𝑧≤𝑠, pelo que 𝑧∈ [𝑟,𝑠]. Então, 𝑥∧𝑧=𝑥∧𝑠∧ (𝑟∨𝑦)[𝑧=𝑠∧ (𝑟∨𝑦)] =𝑥∧ (𝑟∨𝑦)[𝑥≤𝑠] =𝑟∨ (𝑥∧𝑦)[𝑟≤𝑥e modularidade] =𝑟∨0[𝑦é um complemento de 𝑥] =𝑟 73 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS e 𝑥∨𝑧=𝑥∨𝑟∨ (𝑠∧𝑦)[𝑧=𝑟∨ (𝑠∧𝑦)] =𝑥∨ (𝑠∧𝑦)[𝑟≤𝑥] =𝑠∧ (𝑥∨𝑦)[𝑥≤𝑠e modularidade] =𝑠∧1[𝑦é um complemento de 𝑥] =𝑠. Logo, 𝑧é um complemento relativo de 𝑥em [𝑟,𝑠]. Portanto, o reticulado 𝑅é relativamente complementado. □ Corolário 1.2.27. Qualquer reticulado distributivo complementado é relativamente complementado. Demonstração. Imediato, tendo em conta as Proposições 1.1.5 e 1.2.26. □ Teorema 1.2.28 (cf. [2], Theorem 6.2, p. 78).Sejam 𝑅um reticulado distributivo (limitado) e 𝑥∈𝑅. Caso existam, os complementos relativos (e os complementos) de 𝑥são únicos. Demonstração. Sejam (𝑅;∧,∨) um reticulado distributivo e 𝑥∈𝑅. Admita-se que existem dois complementos relativos 𝑦, 𝑧 ∈𝑅de 𝑥num intervalo [𝑟,𝑠] ⊆ 𝑅. Então, 𝑦∧𝑥=𝑟=𝑧∧𝑥e𝑦∨𝑥=𝑠=𝑧∨𝑥. Logo, pelo Teorema 1.2.3, 𝑦=𝑧. De forma semelhante se prova que, se (𝑅;∧,∨) for um reticulado distributivo limitado e 𝑥∈𝑅, então os complementos de 𝑥, caso existam, são únicos. Conclui-se assim a prova. □ Teorema 1.2.29 (cf. [7], Corollary 103, p. 111).Um reticulado 𝑅é distributivo se e só se qualquer elemento 𝑥de 𝑅tem, quando muito, um complemento relativo em qualquer intervalo que contenha 𝑥. Demonstração. Seja (𝑅;∧,∨) um reticulado. Se 𝑅for distributivo, então, segundo o teorema anterior, cada 𝑥∈𝑅tem, quando muito, um complemento relativo em qualquer intervalo, em particular em qualquer intervalo que contenha 𝑥. Reciprocamente, se 𝑅não for distributivo, então 𝑅possui algum sub-reticulado isomorfo a 𝑀3ou a 𝑁5, ou seja, 𝑅possui algum sub-reticulado da forma 𝑎𝑏𝑐 𝑢0 𝑢1 ou 𝑡 𝑠 𝑟 𝑣0 𝑣1 . 74 CAPÍTULO 1. RETICULADOS DISTRIBUTIVOS Como facilmente se nota, em ambos os casos, existem elementos com mais do que um complemento relativo: no primeiro caso, os elementos 𝑏≠𝑐são complementos relativos de 𝑎no intervalo [𝑢0,𝑢1]; no caso restante, os elementos 𝑟≠𝑠são complementos relativos de 𝑡no intervalo [𝑣0, 𝑣1]. Fica concluída a prova. □ 75 2Álgebras de Boole Este último capítulo da dissertação é dedicado ao estudo de uma das mais conhecidas classes de álgebras que admitem como reduto algum reticulado distributivo: as álgebras de Boole. Estudam-se propriedades básicas deste tipo de álgebras e estabelecem-se teoremas de caracterização e de representação para álgebras de Boole. 2.1 Noções e propriedades principais Na secção 0.3 introduziu-se o conceito de elemento complementado em reticulados limitados. O complemento de um elemento, caso exista, não é, em geral, único. Num reticulado distributivo limitado, sabe-se, no entanto, pelo Teorema 1.2.28, que cada elemento complementado admite um único complemento. É o que motiva o estudo da classe de reticulados a seguir definidos. Definição 2.1.1. Chama-se reticulado de Boole a qualquer reticulado distributivo complementado. Pela definição anterior, sendo (𝑅;∧,∨) um reticulado de Boole, é simples concluir que •𝑅é um reticulado limitado; • cada elemento 𝑥de 𝑅admite um único complemento, que habitualmente se denota por 𝑥′. O elemento mínimo de um reticulado de Boole (𝑅;∧,∨) é representado por 0𝑅(ou apenas por 0, caso não haja ambiguidade) e o elemento máximo é representado por 1𝑅(ou apenas por 1). Considerando que, num reticulado de Boole 𝑅, cada elemento admite um único complemento, pode definir-se uma operação unária em 𝑅, denominada complementação, que, a cada elemento 𝑥∈𝑅, faz corresponder o seu único complemento 𝑥′. Esta operação é usualmente representada por ′. Definição 2.1.2. Chama-se álgebra de Boole a qualquer álgebra (𝐵;∧,∨,′)de tipo (2,2,1)onde •(𝐵;∧,∨) é um reticulado de Boole; • a operação unária ′é a operação de complementação em 𝐵. 76 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Portanto, dada uma álgebra de Boole (𝐵;∧,∨,′), a álgebra (𝐵;∧,∨) é um seu reduto que é um reticulado distributivo. Para simplificar a escrita, é usual representar uma álgebra de Boole (𝐵;∧,∨,′)apenas por 𝐵, caso não haja ambiguidade. Exemplo 2.1.3. Sendo 𝑋um conjunto qualquer, a álgebra (℘(𝑋);∩,∪,′), onde ′é a operação unária em ℘(𝑋)definida por 𝑌′=𝑋\𝑌, para qualquer 𝑌∈℘(𝑋), é uma álgebra de Boole. Eis algumas das principais propriedades da operação de complementação numa álgebra de Boole. Lema 2.1.4 (cf. [2], Theorem 6.7, p. 82; [3], Lemma 1.2, pp. 130–131; [4], Secção 4.15, pp. 93–94; [9], Theorem 5.1, pp. 129–130).Seja (𝐵;∧,∨,′)uma álgebra de Boole. Então, (i) 0′=1e1′=0; (ii) para qualquer 𝑥∈𝐵,𝑥′′=𝑥; (iii) para quaisquer 𝑥,𝑦 ∈𝐵, se 𝑥∧𝑦=0e𝑥∨𝑦=1, então 𝑥=𝑦′; (iv) para quaisquer 𝑥,𝑦 ∈𝐵, (𝑥∧𝑦)′=𝑥′∨𝑦′e(𝑥∨𝑦)′=𝑥′∧𝑦′; (v) para quaisquer 𝑥,𝑦 ∈𝐵, 𝑥∧𝑦=𝑥′∨𝑦′′e𝑥∨𝑦=𝑥′∧𝑦′′; (vi) para quaisquer 𝑥,𝑦 ∈𝐵, 𝑥≤𝑦⇐⇒ 𝑦′≤𝑥′⇐⇒ 𝑥∧𝑦′=0⇐⇒ 𝑥′∨𝑦=1; (vii) para quaisquer 𝑥,𝑦, 𝑧 ∈𝐵, 𝑥∧𝑦≤𝑧⇐⇒ 𝑥≤𝑧∨𝑦′e𝑧≤𝑥∨𝑦⇐⇒ 𝑧∧𝑦′≤𝑥. Demonstração. As condições (i) e(ii) são imediatas. 77 CAPÍTULO 2. ÁLGEBRAS DE BOOLE (iii) Sejam 𝑥,𝑦 ∈𝐵tais que 𝑥∧𝑦=0e𝑥∨𝑦=1. Então, 𝑥=𝑥∧1 =𝑥∧ (𝑦∨𝑦′) =(𝑥∧𝑦) ∨ (𝑥∧𝑦′) =0∨ (𝑥∧𝑦′) =𝑥∧𝑦′, pelo que 𝑥≤𝑦′. De forma semelhante se prova que 𝑦′≤𝑥. Logo, 𝑥=𝑦′. (iv) Sejam 𝑥,𝑦 ∈𝐵. Então, 𝑥′∨𝑦′∈𝐵. Para provar que (𝑥∧𝑦)′=𝑥′∨𝑦′, basta mostrar que (𝑥∧𝑦)∧𝑥′∨𝑦′=0e(𝑥∧𝑦) ∨ 𝑥′∨𝑦′=1. Ora, (𝑥∧𝑦) ∧ 𝑥′∨𝑦′=𝑥∧𝑦∧𝑥′∨𝑥∧𝑦∧𝑦′ =(𝑦∧0) ∨ (𝑥∧0) =0∨0 =0. Analogamente, se mostra que (𝑥∧𝑦) ∨ 𝑥′∨𝑦′=1. Logo, (𝑥∧𝑦)′=𝑥′∨𝑦′. Procedendo de forma semelhante, também se prova que (𝑥∨𝑦)′=𝑥′∧𝑦′. (v) Sejam 𝑥,𝑦 ∈𝐵. Por (ii) e(iv), obtém-se 𝑥∧𝑦=(𝑥∧𝑦)′′=𝑥′∨𝑦′′ e 𝑥∨𝑦=(𝑥∨𝑦)′′=𝑥′∧𝑦′′. (vi) Sejam 𝑥,𝑦 ∈𝐵. Suponha-se, primeiramente, que 𝑥≤𝑦. Então, 𝑥=𝑥∧𝑦. Assim, por (iv), 𝑥′=(𝑥∧𝑦)′=𝑥′∨𝑦′. Logo, 𝑦′≤𝑥′. 78 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Admita-se, agora, que 𝑦′≤𝑥′. Então, 𝑥∧𝑦′≤𝑥∧𝑥′=0. Logo, 𝑥∧𝑦′=0. Seguidamente, se 𝑥∧𝑦′=0, então 𝑥∧𝑦′′=0′, donde, por (iv),(i) e(ii), 𝑥′∨𝑦=1. Assuma-se, agora, que 𝑥′∨𝑦=1. Então, 𝑥∧𝑥′∨𝑦=𝑥∧1, pelo que 𝑥∧𝑥′∨ (𝑥∧𝑦)=𝑥, ou seja, 0∨ (𝑥∧𝑦)=𝑥, donde 𝑥∧𝑦=𝑥. Logo, 𝑥≤𝑦. (vii) Sejam 𝑥,𝑦, 𝑧 ∈𝐵. Ora, 𝑥∧𝑦≤𝑧=⇒ (𝑥∧𝑦) ∨ 𝑦′≤𝑧∨𝑦′ =⇒𝑥∨𝑦′∧𝑦∨𝑦′≤𝑧∨𝑦′ =⇒𝑥∨𝑦′∧1≤𝑧∨𝑦′ =⇒𝑥∨𝑦′≤𝑧∨𝑦′ =⇒𝑥≤𝑧∨𝑦′. [uma vez que 𝑥≤𝑥∨𝑦′] De forma semelhante se prova que 𝑥≤𝑧∨𝑦′=⇒𝑥∧𝑦≤𝑧. Logo, 𝑥∧𝑦≤𝑧⇐⇒ 𝑥≤𝑧∨𝑦′. Argumentos semelhantes provam que 𝑧≤𝑥∨𝑦⇐⇒ 𝑧∧𝑦′≤𝑥. 79 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Conclui-se assim a demonstração do Lema 2.1.4. □ As condições da alínea (iv) do Lema 2.1.4 são conhecidas como leis de De Morgan. Os conceitos que se seguem não são mais do que especificações dos que já foram estudados na Secção 0.2. Definição 2.1.5. Sejam (𝐵;∧,∨,′)uma álgebra de Boole e 𝐴⊆𝐵. Uma álgebra (𝐴;∧,∨,′), onde as operações ∧,∨,′são as mesmas que as respetivas operações de 𝐵restritas a 𝐴, diz-se uma subálgebra de (𝐵;∧,∨,′)se •(𝐴;∧,∨) é um sub-reticulado de (𝐵;∧,∨); • para qualquer 𝑥∈𝐴,𝑥′∈𝐴. Definição 2.1.6. Sejam (𝐵;∧𝐵,∨𝐵,′)e(𝐶;∧𝐶,∨𝐶,∗)álgebras de Boole e 𝑓uma aplicação de 𝐵 em 𝐶. Diz-se que 𝑓é um homomorfismo de álgebras de Boole se •𝑓preserva ínfimos e supremos: para quaisquer 𝑥,𝑦 ∈𝐵, 𝑓(𝑥∧𝐵𝑦)=𝑓(𝑥) ∧𝐶𝑓(𝑦) 𝑓(𝑥∨𝐵𝑦)=𝑓(𝑥) ∨𝐶𝑓(𝑦); •𝑓preserva complementos: para qualquer 𝑥∈𝐵, 𝑓(𝑥′)=(𝑓(𝑥))∗. Tendo em conta a definição anterior e o que já foi estudado na Secção 0.2, é simples entender como se definem os termos monomorfismo/epimorfismo/isomorfismo de álgebras de Boole. No lema seguinte, encontram-se algumas propriedades destes homomorfismos, que mostram que as condições da Definição 2.1.6 não são independentes entre si. Lema 2.1.7 (cf. [4], Secção 4.17).Sejam (𝐵;∧𝐵,∨𝐵,′)e(𝐶;∧𝐶,∨𝐶,∗)álgebras de Boole e 𝑓uma aplicação de 𝐵em 𝐶. (i) Se 𝑓preserva ínfimos e supremos, então as seguintes condições são equivalentes: (a) 𝑓preserva complementos; (b) 𝑓preserva mínimos e máximos: 𝑓(0𝐵)=0𝐶e𝑓(1𝐵)=1𝐶. 80 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Mostre-se, agora, que 𝜓é isótona. Sejam 𝑋, 𝑌 ∈℘(At(𝐵)) tais que 𝑋⊆𝑌. Se 𝑋=𝑌=∅, então 𝜓(𝑋)=0=𝜓(𝑌), pelo que 𝜓(𝑋) ≤ 𝜓(𝑌). Se 𝑋=∅e𝑌≠∅, então 𝜓(𝑋)=0≤Ü𝑌=𝜓(𝑌). Se 𝑋≠∅e𝑌≠∅, então, como Ô𝑋≤Ô𝑌, tem-se 𝜓(𝑋) ≤ 𝜓(𝑌). Confirma-se, assim, que 𝜓é isótona. Prove-se que 𝜑também é isótona. Sejam 𝑥,𝑦 ∈𝐵tais que 𝑥≤𝑦. Ora, se 𝑥=𝑦=0, então 𝜑(𝑥)=∅=𝜑(𝑦), pelo que 𝜑(𝑥) ⊆ 𝜑(𝑦). Se 𝑥=0e𝑦≠0, então 𝜑(𝑥)=∅ ⊆ at(𝑦)=𝜑(𝑦). Se 𝑥≠0e𝑦≠0, então 𝜑(𝑥)=at(𝑥) ⊆ at(𝑦)=𝜑(𝑦). Portanto, 𝜑é, de facto, isótona. Como 𝜓é isótona, invertível e a sua inversa, 𝜑, é também isótona, conclui-se, atendendo às Proposições 0.1.24 e 0.3.6, que 𝜓é um isomorfismo de reticulados de (𝐵;∧,∨) em (℘(At(𝐵));∩,∪). Verifique-se, agora, que 𝜓preserva complementos. Seja 𝑋∈℘(At(𝐵)). Para provar que 𝜓(𝑋′)=(𝜓(𝑋))∗, basta mostrar que 𝜓(𝑋′) ∈ 𝐵(o que é óbvio) e que 𝜓(𝑋) ∧ 𝜓(𝑋′)=0e𝜓(𝑋) ∨ 𝜓(𝑋′)=1. Ora, 𝜓(𝑋) ∧ 𝜓(𝑋′)=𝜓(𝑋∩ (At(𝐵) \ 𝑋)) =𝜓(∅) =0 e 𝜓(𝑋) ∨ 𝜓(𝑋′)=𝜓(𝑋∪ (At(𝐵) \ 𝑋)) =𝜓(At(𝐵)) =ÜAt(𝐵) =1. 87 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Verifique-se que, de facto, ÔAt(𝐵)=1. Para tal, suponha-se, por absurdo, que existe um majorante 𝑧de At(𝐵)tal que 𝑧<1. Como (𝐵;∧,∨) é um reticulado atómico, então existe 𝑎∈At(𝐵)tal que 𝑎≤𝑧∗. Assim, 0≺𝑎≤𝑧∧𝑧∗, o que é um absurdo. Portanto, 𝜓é um isomorfismo de álgebras de Boole, pelo que (𝐵;∧,∨,∗)(℘(At(𝐵));∩,∪,′). Fica, assim, concluída a demonstração. □ Corolário 2.2.4 (cf. [2], Corollary, pp. 87–88).Seja (𝐵;∧,∨,∗)uma álgebra de Boole finita. Então, 𝐵 tem 2𝑛elementos, onde 𝑛∈ℕé o número de átomos de 𝐵. Demonstração. É simples notar que (𝐵;∧,∨) é um reticulado completo e atómico. Logo, pelo teorema anterior, (𝐵;∧,∨,∗)(℘(𝑋);∩,∪,′), para algum conjunto 𝑋. Uma vez que 𝐵é finito, 𝑋é finito. Assuma-se, sem perda de generalidade, que 𝑋={𝑥1, . . . , 𝑥𝑛}, para certo 𝑛∈ℕ. Denote-se por 2a cadeia de dois elementos {0,1}e considere-se a aplicação 𝑓:℘(𝑋) → 2𝑛definida por 𝑓(𝑌)=(𝑦1, . . . ,𝑦𝑛), onde, para cada 𝑖∈ {1, . . . , 𝑛}, 𝑦𝑖=(1, se 𝑥𝑖∈𝑌; 0, caso contrário. É óbvio que 𝑓está bem definida. Suponha-se que a aplicação 𝑓é bijetiva. Então o conjunto ℘(𝑋)tem o mesmo número de elementos que o conjunto 2𝑛, tendo este último 2𝑛elementos. Sabe-se que 𝑋tem 𝑛elementos, o que significa que ℘(𝑋)possui exatamente 𝑛conjuntos singulares, os quais correspondem aos átomos de (℘(𝑋);∩,∪). Logo, como 𝐵℘(𝑋), conclui-se que 𝐵possui 2𝑛elementos, sendo 𝑛o número de átomos de 𝐵. Resta, portanto, provar que 𝑓é uma aplicação bijetiva. Inicialmente, mostre-se que 𝑓é injetiva. Para tal, verifique-se que, para quaisquer 𝑌, 𝑍 ∈℘(𝑋), 𝑌⊆𝑍⇐⇒ 𝑓(𝑌) ⊑ 𝑓(𝑍). Sejam 𝑌, 𝑍 ∈℘(𝑋). Então, 𝑓(𝑌)=(𝑦1, . . . ,𝑦𝑛)e𝑓(𝑍)=(𝑧1, . . . , 𝑧𝑛), para certos (𝑦1, . . . ,𝑦𝑛),(𝑧1, . . . , 𝑧𝑛) ∈ 2𝑛. Tem-se 𝑌⊆𝑍se e só se, para cada 𝑖∈ {1, . . . ,𝑛}, 𝑥𝑖∈𝑌implica 𝑥𝑖∈𝑍; ou seja, 𝑌⊆𝑍se e só se, para cada 𝑖∈ {1, . . . ,𝑛},𝑦𝑖=1implica 𝑧𝑖=1. Assim, 𝑌⊆𝑍se e só se 𝑓(𝑌)=(𝑦1, . . . ,𝑦𝑛) ⊑ (𝑧1, . . . , 𝑧𝑛)=𝑓(𝑍). 88 CAPÍTULO 2. ÁLGEBRAS DE BOOLE Logo, 𝑓é um mergulho de ordem de (℘(𝑋);⊆) em (2𝑛;⊑) e, portanto, 𝑓é injetiva. Mostre-se, agora, que 𝑓é sobrejetiva. Seja 𝑤=(𝑤1, . . . , 𝑤𝑛) ∈ 2𝑛. Considerando 𝑊={𝑥𝑖∈𝑋|𝑖∈ {1, . . . , 𝑛},𝑤𝑖=1}, tem-se claramente que 𝑓(𝑊)=𝑤. Portanto, 𝑓é sobrejetiva. Conclui-se assim o que era pretendido. □ 89 Bibliografia [1] Balbes, R. & Dwinger, P. (1974). Distributive lattices. University of Missouri Press. [2] Blyth, T. S. (2005). Lattices and ordered algebraic structures. Springer-Verlag London. [3] Burris, S. & Sankappanavar, H. P. (1981). A course in universal algebra. Springer-Verlag New York. [4] Davey, B. A. & Priestley, H. A. (2002). Introduction to lattices and order (2nd). Cambridge University Press. [5] Dilworth, R. P. (1950). A Decomposition Theorem for Partially Ordered Sets. Annals of Mathematics, 51, 161–166. [6] Fan, K. (1972). On Dilworth’s Coding Theorem. Mathematische Zeitschrift, 127, 92–94. [7] Grätzer, G. (2011). Lattice theory: Foundation. Birkhäuser Basel. [8] Grätzer, G. & Schmidt, E. T. (1958). Ideals and Congruence Relations in Lattices. Acta Mathematica Academiae Scientiarum Hungarica, 9, 137–175. [9] Roman, S. (2008). Lattices and ordered sets. Springer-Verlag New York. 90