Saltar para o conteúdo

Álgebra universal

Origem: Wikipédia, a enciclopédia livre.

A álgebra universal (às vezes chamada de álgebra geral) é o campo da matemática que estuda as estruturas algébricas em si, não os exemplos ("modelos") de estruturas algébricas. Por exemplo, em vez de considerar grupos específicos como objeto de estudo, na álgebra universal é considerada a classe dos grupos como objeto de estudo.

Ideia básica

[editar | editar código-fonte]

Em álgebra universal, uma álgebra (ou estrutura algébrica) é um conjunto A, juntamente com uma coleção de operações em A. Uma operação n-ária em A é uma função que pega n elementos de A e retorna um único elemento de A. Assim, uma operação 0-ária (ou operação nula) pode ser representada simplesmente como um elemento de A, ou uma constante, frequentemente denotada por uma letra como a. Uma operação de 1-ária (ou operação unária) é simplesmente uma função de A a A, geralmente denotada por um símbolo colocado na frente de seu argumento, como ~x. Uma operação de 2-ária (ou operação binária) é frequentemente indicada por um símbolo colocado entre seus argumentos, como xy. Operações de aridade superior ou não especificada são geralmente indicadas por símbolos de função, com os argumentos colocados entre parênteses e separados por vírgulas, como em f( x, y, z) ou f(x1, ..., xn). Alguns pesquisadores permitem operações infinitárias, como em que J é um conjunto infinito de índices, levando assim à teoria algébrica de reticulados completos . Então, uma maneira de falar sobre uma álgebra é se referindo a ela como uma álgebra de um certo tipo , em que é uma sequência ordenada de números naturais que representa a aridade das operações da álgebra.

Uma vez que as operações são especificadas, a natureza da álgebra é especificada mais detalhadamente por axiomas, que em álgebra universal geralmente assumem a forma de identidades ou leis equacionais. Um exemplo é o axioma da associatividade para uma operação binária, que é dado pela equação x ∗ (yz ) = (xy) ∗ z. O axioma deve ser válido para todos os elementos x, y e z do conjunto A.

Uma coleção de estruturas algébricas definidas por identidades é chamada de variedade ou classe equacional. Alguns autores consideram as variedades o principal foco da álgebra universal. [carece de fontes?]

A restrição do estudo às variedades exclui:

O estudo de classes equacionais pode ser visto como um ramo especial da teoria dos modelos, tipicamente lidando com estruturas que possuem apenas operações (ou seja, o tipo pode ter símbolos para funções, mas não para relações que não sejam a igualdade), e nas quais a linguagem usada para falar sobre essas estruturas usa apenas equações.

Nem todas as estruturas algébricas em um sentido mais amplo se enquadram nesse escopo. Por exemplo, grupos ordenados envolvem uma relação de ordem, portanto, não se enquadram nesse escopo.

A classe de corpos não é uma classe equacional porque não existe um tipo (ou "assinatura") em que todos os axiomas de corpo possam ser escritos como equações (inversos de elementos são definidos para todos os elementos diferentes de zero em um corpo, portanto, a inversão não pode ser adicionada ao tipo).

Uma vantagem dessa restrição é que as estruturas estudadas em álgebra universal podem ser definidas em qualquer categoria que possua produtos finitos. Por exemplo, um grupo topológico é apenas um grupo na categoria de espaços topológicos.

A maioria dos sistemas algébricos usuais da matemática são exemplos de variedades, mas nem sempre de uma maneira óbvia, uma vez que as definições usuais geralmente envolvem quantificação ou desigualdades.

Como exemplo, considere a definição de grupo. Geralmente, um grupo é definido em termos de uma única operação binária ∗, sujeita aos axiomas:

  • Associatividade (como na seção anterior): x ∗ (yz)    = (xy) ∗ z; formalmente: ∀x,y,z. x∗(yz)=(xy)∗z.
  • Elemento identidade: existe um elemento e tal que, para cada elemento x, tem-se ex = x = xe; formalmente: ∃ex. ex=x=xe.
  • Elemento inverso: demonstra-se que o elemento identidade é único, e geralmente é indicado por e. Então, para cada x, existe um elemento i tal que x ∗ i  =  e  =  i ∗ x; formalmente: ∀xi. xi=e=ix.

(Alguns autores também usam o axioma de "fechamento" segundo o qual xy pertence a A sempre que x e y pertencem, mas aqui isso já está implícito ao chamar ∗ de operação binária.)

Essa definição de grupo não se encaixa diretamente no ponto de vista da álgebra universal, porque os axiomas do elemento identidade e da inversão não estão formulados puramente em termos de leis equacionais que valem universalmente "para todos ..." os elementos, mas também envolvem o quantificador existencial "existe...". Os axiomas de grupo podem ser reescritos como equações quantificadas universalmente, especificando, além da operação binária ∗, uma operação nula e e uma operação unária ~, geralmente denotando ~x como x−1. Os axiomas tornam-se:

  • Associatividade: x ∗ (yz)  =  (xy) ∗ z .
  • Elemento identidade: ex  =  x  =  xe ; formalmente: ∀x. ex=x=xe.
  • Elemento inverso: x ∗ (~x)  =  e  =  (~x) ∗ x   formalmente: ∀x. x∗~x=e=~xx.

Resumindo, a definição usual tem:

  • uma única operação binária (assinatura (2))
  • 1 lei equacional (associatividade)
  • 2 leis quantificadas (identidade e inverso)

enquanto que a definição em álgebra universal tem:

  • 3 operações: uma binária, uma unária e uma nula (assinatura (2,1,0))
  • 3 leis equacionais (associatividade, identidade e inversa)
  • nenhuma lei quantificada (exceto quantificadores universais extremos, permitidos em variedades)

Um ponto importante é que as operações extras não adicionam informações, mas seguem exclusivamente da definição usual de grupo. Embora a definição usual não especifique unicamente o elemento de identidade e, um simples exercício mostra que ele é único, bem como cada elemento inverso.

O ponto de vista da álgebra universal está bem adaptado à teoria das categorias. Por exemplo, ao definir um objeto grupo em teoria de categorias, em que o objeto em questão pode não ser um conjunto, é necessário usar leis equacionais (que fazem sentido em categorias gerais), em vez de leis quantificadas (que se referem a elementos individuais). Além disso, o inversão e a identidade são especificadas como morfismos na categoria. Por exemplo, em um grupo topológico, a inversão deve não apenas existir elemento a elemento, mas também deve consistir de uma aplicação contínua (um morfismo). Alguns autores também exigem que a aplicação identidade seja uma inclusão fechada (uma cofibração).

Outros exemplos

[editar | editar código-fonte]

A maioria das estruturas algébricas são exemplos de álgebras universais.

Exemplos de álgebras relacionais incluem semirreticulados, reticulados e álgebras booleanas.

Construções básicas

[editar | editar código-fonte]

Assumimos que o tipo, , foi fixado. Então existem três construções básicas na álgebra universal: imagem homomórfica, subálgebra e produto.

Um homomorfismo entre duas álgebras A e B é uma função h : A   →   B do conjunto A ao conjunto B, de modo que, para cada operação fA de A e correspondente fB de B (de aridade, por exemplo, n), h(fA(x1,...,xn)) = fB(h(x1),...,h(xn)). (Às vezes, omitem-se os subscritos de f quando fica claro no contexto de que álgebra a função é.) Por exemplo, se e é uma constante (operação nula), então h (eA) = eB. Se ~ é uma operação unária, então h (~x) = ~h(x). Se ∗ é uma operação binária, então h (xy) = h (x) ∗ h(y). E assim por diante. Algumas das coisas que podem ser feitas com homomorfismos, bem como definições de certos tipos especiais de homomorfismos, estão listadas no artigo sobre homomorfismo. Em particular, pode-se obter a imagem homomórfica de uma álgebra, h(A).

Uma subálgebra de A é um subconjunto de A que é fechado sob todas as operações de A. Um produto de algum conjunto de estruturas algébricas é o produto cartesiano dos conjuntos com as operações definidas coordenada a coordenada.

Alguns teoremas básicos

[editar | editar código-fonte]
  • Os teoremas do isomorfismo, que abrangem os teoremas do isomorfismo de grupos, anéis, módulos, etc.
  • O Teorema do HSP de Birkhoff, que afirma que uma classe de álgebras é uma variedade se, e somente se, for fechada sob imagens homomórficas, subálgebras e produtos diretos arbitrários.

Motivações e aplicações

[editar | editar código-fonte]

Além de sua abordagem unificadora, a álgebra universal também fornece teoremas profundos, e exemplos e contra-exemplos importantes. Ela fornece uma estrutura útil para aqueles que pretendem iniciar o estudo de novas classes de álgebras. Ela pode permitir o uso de métodos inventados para algumas classes específicas de álgebras em outras classes de álgebras, reformulando os métodos em termos da álgebra universal (se possível) e então interpretando-os como aplicados a outras classes. Ela também forneceu esclarecimentos conceituais; como J. D. H. Smith coloca: "O que parece confuso e complicado em uma estrutura específica pode se tornar simples e óbvio na estrutura geral apropriada".

Em particular, a álgebra universal pode ser aplicada ao estudo de monoides, anéis e reticulados. Antes do surgimento da álgebra universal, muitos teoremas (principalmente os teoremas do isomorfismo) eram provados separadamente em todas essas classes, mas com a álgebra universal, eles podem ser comprovados de uma vez por todas para todo tipo de sistema algébrico.

O artigo de 1956 de Higgins mencionado abaixo foi bem acompanhado por sua estrutura para uma variedade de sistemas algébricos particulares, enquanto seu artigo de 1963 é notável por sua discussão de álgebras com operações que são definidas apenas parcialmente, das quais são exemplos típicos as categorias e os grupoides. Isso leva ao assunto da álgebra de maior dimensão, que pode ser definida como o estudo de teorias algébricas com operações parciais cujos domínios são definidos sob condições geométricas. Exemplos notáveis disso são várias formas de grupoides e categorias de dimensões superiores.

Problema de satisfação de restrições mentira

[editar | editar código-fonte]

A álgebra universal fornece uma linguagem natural para o problema de satisfação de restrições (CSP) . CSP refere-se a uma classe importante de problemas computacionais em que, dada uma álgebra relacional A e uma sentença existencial sobre essa álgebra, a questão é descobrir se pode ser satisfeita em A. Geralmente a álgebra A é fixada, de modo que o CSPA se refere ao problema cuja instância é apenas a sentença existencial .

Está provado que todo problema computacional pode ser formulado como CSPA para alguma álgebra A.

Por exemplo, o problema da n-coloração pode ser formulado como CSP da álgebra , ou seja, uma álgebra com elementos e uma única relação, desigualdade.

A conjectura da dicotomia (demonstrada em abril de 2017) afirma que, se A é uma álgebra finita, então o CSPA é P ou NP completo.[1]

Generalizações

[editar | editar código-fonte]

A álgebra universal também foi estudada usando as técnicas da teoria das categorias. Nesta abordagem, em vez de escrever uma lista de operações e equações obedecidas por essas operações, pode-se descrever uma estrutura algébrica usando categorias de um tipo especial, conhecidas como teorias de Lawvere ou, mais geralmente, teorias algébricas. Alternativamente, pode-se descrever estruturas algébricas usando mônadas . As duas abordagens estão intimamente relacionadas, cada uma com suas próprias vantagens.[2] Em particular, toda teoria de Lawvere fornece uma mônada na categoria de conjuntos, enquanto qualquer mônada "finitária" na categoria de conjuntos surge de uma teoria de Lawvere. No entanto, uma mônada descreve estruturas algébricas dentro de uma categoria específica (por exemplo, a categoria de conjuntos), enquanto as teorias algébricas descrevem estruturas dentro de qualquer categoria dentro de uma grande classe de categorias (ou seja, aquelas com produtos finitos).

Um desenvolvimento mais recente na teoria das categorias é a teoria das operadas   - uma operada é um conjunto de operações, semelhante a uma álgebra universal, mas restrita no sentido de que só são permitidas equações entre expressões com as variáveis, sem duplicação ou omissão de variáveis permitidas. Assim, os anéis podem ser descritos como as chamadas "álgebras" de algumas operadas, mas os grupos não, uma vez que a lei duplica a variável g no lado esquerdo e a omite no lado direito. A princípio, isso pode parecer uma restrição problemática, mas a recompensa é que as operadas têm certas vantagens: por exemplo, é possível hibridar os conceitos de anel e espaço vetorial para obter o conceito de álgebra associativa, mas não é possível formar um híbrido semelhante dos conceitos de grupo e espaço vetorial.

Outro desenvolvimento é a álgebra parcial, em que os operadores podem ser funções parciais. Certas funções parciais também podem ser tratadas por uma generalização das teorias de Lawvere conhecidas como teorias essencialmente algébricas.

Outra generalização da álgebra universal é a teoria dos modelos, que às vezes é descrita como "álgebra universal + lógica".[3]

No livro de Alfred North Whitehead, A Treatise on Universal Algebra, publicado em 1898, o termo álgebra universal tinha essencialmente o mesmo significado que tem hoje. Whitehead credita William Rowan Hamilton e Augustus De Morgan como criadores do assunto, e James Joseph Sylvester por cunhar o termo propriamente dito.[4]:v

Na época, estruturas como álgebras de Lie e quatérnios hiperbólicos chamavam a atenção para a necessidade de se expandir estruturas algébricas além da classe associativamente multiplicativa. Em uma revisão, Alexander Macfarlane escreveu: "A ideia principal do trabalho não é a unificação dos vários métodos, nem a generalização da álgebra comum a fim de incluí-los, mas o estudo comparativo de suas diversas estruturas".[5] Na época, a álgebra da lógica de George Boole fazia um forte contraponto à álgebra de números ordinária, de modo que o termo "universal" serviu para acalmar as sensibilidades tensas.

Os primeiros trabalhos de Whitehead procuraram unificar os quatérnios (devido a Hamilton), o Ausdehnungslehre de Grassmann e a álgebra da lógica de Boole. Whitehead escreveu em seu livro:

"Tais álgebras têm um valor intrínseco para estudos detalhados separados; também são dignas de estudo comparativo, pelo bem da luz lançada sobre a teoria geral do raciocínio simbólico e, em particular, sobre o simbolismo algébrico. O estudo comparativo pressupõe necessariamente algum estudo separado anterior, sendo impossível a comparação sem conhecimento."[4]

Whitehead, no entanto, não teve resultados de natureza geral. O trabalho sobre o assunto foi mínimo até o início dos anos 30, quando Garrett Birkhoff e Øystein Ore começaram a publicar sobre álgebras universais. Os desenvolvimentos em metamatemática e teoria das categorias nas décadas de 1940 e 1950 aprofundaram a área, particularmente o trabalho de Abraham Robinson, Alfred Tarski, Andrzej Mostowski e seus alunos.[6]

No período entre 1935 e 1950, a maioria dos artigos foi escrita de acordo com o que foi sugerido pelos artigos de Birkhoff, tratando de álgebras livres, congruência e reticulados de subálgebra e teoremas do homomorfismo. Embora o desenvolvimento da lógica matemática tornasse possíveis as aplicações à álgebra, elas surgiram lentamente; os resultados publicados por Anatoly Maltsev na década de 1940 passaram despercebidos por causa da guerra. A palestra de Tarski no Congresso Internacional de Matemáticos de 1950, em Cambridge, deu início a um novo período no qual os aspectos de teoria de modelos foram desenvolvidos, principalmente pelo próprio Tarski, bem como por CC Chang, Leon Henkin, Bjarni Jónsson, Roger Lyndon e outros.

No final dos anos 1950, Edward Marczewski[7] enfatizou a importância das álgebras livres, levando à publicação de mais de 50 artigos sobre a teoria algébrica das álgebras livres pelo próprio Marczewski, juntamente com Jan Mycielski, Władysław Narkiewicz, Witold Nitka, J. Płonka, S. Świerczkowski, K. Urbanik e outros.

Começando com a tese de William Lawvere em 1963, as técnicas da teoria das categorias tornaram-se importantes na álgebra universal.[8]

  1. Zhuk, Dmitriy (2017). «The Proof of CSP Dichotomy Conjecture». arXiv:1704.01914Acessível livremente [cs.cc] 
  2. Hyland, Martin; Power, John (2007), The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and Monads (PDF) 
  3. C.C. Chang and H. Jerome Keisler (1990). Model Theory. North Holland. Col: Studies in Logic and the Foundation of Mathematics. 73 3rd ed. [S.l.: s.n.] ISBN 0444880542 
  4. a b George Grätzer (1968). M.H. Stone and L. Nirenberg and S.S. Chern, ed. Universal Algebra. Van Nostrand Co., Inc 1st ed. [S.l.: s.n.] 
  5. Alexander Macfarlane (1899) Review:A Treatise on Universal Algebra (pdf), Science 9: 324–8 via Internet Archive
  6. Brainerd, Barron (Aug–Sep 1967) "Review of Universal Algebra by P. M. Cohn", American Mathematical Monthly 74(7): 878–880.
  7. Marczewski, E. "A general scheme of the notions of independence in mathematics." Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 6 (1958), 731–736.
  8. Lawvere, William F. (1964), Functorial Semantics of Algebraic Theories (PhD Thesis) 

Ligações externas

[editar | editar código-fonte]