Artigos

6.5: Óperadas e suas álgebras - Matemática


No Teorema 6.77, descrevemos como decorar cospans constrói uma categoria de hipergrafo a partir de um functor monoidal simétrico. Em seguida, exploramos como isso funciona no caso de o functor de decoração ser de alguma forma “todos os grafos de circuito em um conjunto de nós”.

Neste livro, dedicamos muita atenção a diferentes tipos de teorias composicionais, desde pré-encomendas monoidais a categorias fechadas compactas e categorias de hipergrafo. No entanto, para uma aplicação que você algum dia tenha em mente, pode ser que nenhuma dessas teorias seja suficiente. Você precisa de uma estrutura diferente, personalizada para uma situação particular. Por exemplo, em [VSL15] os autores queriam compor sistemas dinâmicos contínuos com propriedades teóricas de controle e perceberam que, para que o feedback fizesse sentido, os diagramas de fiação não poderiam envolver o que eles chamam de 'fios de passagem'.

Então, para encerrar nossa discussão sobre estruturas composicionais, queremos esboçar rapidamente algo que podemos usar como uma espécie de estrutura meta-composicional, conhecida como operad. Vimos na Seção 6.4.3 que podemos construir circuitos elétricos a partir de um functor monoidal simétrico FinSet Definir. Da mesma forma, veremos que podemos construir exemplos de novas estruturas algébricas de functores operad O → Definir.

Diagramas de fiação do projeto Operads

Compreender que os circuitos são morfismos em uma categoria de hipergrafo é útil: significa que podemos usar a maquinaria da teoria das categorias para ajudar na compreensão dos circuitos elétricos. Por exemplo, podemos construir functores que expressam a composicionalidade da semântica do circuito, ou seja, como derivar a funcionalidade do todo a partir da funcionalidade e do padrão de interação das partes. Ou podemos usar a base teórica da categoria para relacionar circuitos a outros tipos de sistemas de rede, como gráficos de fluxo de sinal. Finalmente, os teoremas de coerência básicos para categorias monoidais e categorias fechadas compactas nos dizem que os diagramas de fiação fornecem um raciocínio sólido e completo nessas configurações.

No entanto, um resultado talvez insatisfatório é que a categoria hipergrafo introduz artefatos como o domínio e o codomínio de um circuito, que não são inerentes à estrutura dos circuitos ou à sua composição. Os circuitos têm apenas uma única interface de limite, não "domínios" e "codomínios". Isso não quer dizer que o modelo acima não seja útil: em muitas aplicações, um espaço vetorial não tem uma base preferencial, mas geralmente é útil escolher um para que possamos usar matrizes (ou gráficos de fluxo de sinal!). Mas valeria a pena ter um modelo teórico de categorias que representasse mais diretamente a estrutura composicional dos circuitos. Em geral, queremos que o modelo teórico da categoria se ajuste à nossa aplicação desejada como uma luva. Vamos esboçar rapidamente como isso pode ser feito.

Vamos voltar aos diagramas de fiação por um segundo. Vimos que os diagramas de fiação para categorias de hipergrafos são basicamente assim:

Observe que se você tivesse uma caixa com UMA e B à esquerda e D à direita, você pode conectar o diagrama acima dentro dele e obter um novo circuito aberto. Este é o movimento básico das óperas.

Mas antes de explicarmos isso, vamos chegar onde dissemos que queríamos ir: para um modelo onde não há portas à esquerda e portas à direita, há apenas portas. Queremos um modelo de composição mais sucinto para diagramas de circuitos; algo que se parece mais com isto:

Você vê como os diagramas Eq. (6.89) e Eq. (6,90) são exatamente iguais em

termos do padrão de interconexão? A única diferença é que este último não tem distinção esquerda / direita: perdemos exatamente o que queríamos perder.

O custo é que as 'caixas' f , g, h, k na Eq. (6,90) não tem mais uma distinção esquerda / direita; eles são apenas círculos agora. Isso não seria ruim, exceto que significa que eles não podem mais representar morfismos em uma categoria - como costumavam fazer acima, na Eq. (6.89) porque os morfismos em uma categoria, por definição, têm um domínio e um codomínio. Nossos novos círculos não têm essa distinção. Portanto, agora precisamos de uma maneira totalmente nova de pensar sobre "caixas" categoricamente: se elas não são mais morfismos em uma categoria, o que são? A resposta é encontrada na teoria das óperas.

Para entender os operads, descobriremos que precisamos navegar por uma das mudanças de nível que discutimos primeiro na Seção 1.4.5. Observe que, para cospans decorados, definimos um hipergrafo categoria usando um monoidal simétrico functor. Isso é uma reminiscência de nossa breve discussão de teorias algébricas na Seção 5.4.2, onde definimos algo chamado de teoria dos monóides como um suporte M, e definimos monóides usando functores M → Definir; veja a observação 5.74.

Da mesma forma, podemos ver a categoria Cospan (_ {FinSet} ) como algum tipo de 'teoria das categorias do hipergrafo', e assim definir as categorias do hipergrafo como functores Cospan (_ {FinSet} ) → Definir.

Então essa é a ideia. Um operad O definirá uma teoria ou gramática de composição, e operad functores O → Definir, conhecido como O-álgebras, descreverá aplicativos específicos que obedecem a essa gramática.

Definição aproximada 6.91.

Para especificar um ópera O,

(i) um especifica uma coleção T, cujos elementos são chamados tipos;

(ii) para cada tupla (t(_{1}), ..., t (_ {n} ),t) de tipos, especifica-se um conjunto O (t(_{1}), ..., t (_ {n} );t), cujos elementos são chamados operações de aridade (t(_{1}), . , t (_ {n} ); t);

(iii) para cada par de tuplas (s(_{1}), ..., s (_ {m} ), t(_{eu e (t(_{1}), ..., t (_ {n} ), t), especifica-se uma função

◦ (_ {i} ): O (s(_{1}), ..., s (_ {m} ); t (_ {i} )) × O (t(_{1}), ..., t (_ {n} ); t) → O (t(_{1}), ..., t (_ {i-1} ), s(_{1}), ..., s (_ {m} ), t (_ {i + 1} ), ..., t (_ {n} ); t);

chamado substituição; e

(iv) para cada tipo t, um especifica um id de operação (_ {t} ) ( in ) O(t ; t) Chamou o operação de identidade.

Estes devem obedecer a leis generalizadas de identidade e associatividade.

Vamos ignorar os tipos por um momento e pensar sobre o que essa estrutura modela. A intuição é que uma operad consiste, para cada n, um conjunto de operações de aridade n ou seja, todas as operações que aceitam n argumentos. Se fizermos uma operação f de aridade m, e conecte a saída no eu o argumento de uma operação g de aridade n, devemos obter uma operação de aridade m + n - 1: nós temos m argumentos para preencher m, e o restante n - 1 argumento para preencher m. Qual operação de aridadem + n - 1 nós entendemos? Isso é descrito pela função de substituição ◦ (_ {i} ), que diz que obtemos a operação f ◦ (_ {i} )g (eu não(m + n - 1). As condições de coerência dizem que essas funções ◦ (_ {i} ) capturam a seguinte imagem intuitiva:

Os tipos então nos permitem especificar os, bem, tipos de entradas de argumentos que cada função recebe. Portanto, fazer chá é uma operação 2 ária, uma operação com aridade 2, porque envolve duas coisas. Para fazer chá, você precisa de um pouco de água morna e de algumas folhas de chá.

Exemplo 6.92.

Gramáticas livres de contexto estão para as operads assim como os gráficos estão para as categorias. Vamos esboçar o que isso significa. Em primeiro lugar, uma gramática livre de contexto é uma maneira de descrever um determinado conjunto de "categorias sintáticas" que podem ser formadas a partir de um conjunto de símbolos. Por exemplo, em inglês, temos categorias sintáticas como substantivos, determinantes, adjetivos, verbos, sintagmas nominais, sintagmas preposicionais, sentenças, etc. Os símbolos são palavras, por ex. gato, cachorro, o, perseguições.

Para definir uma gramática livre de contexto em algum alfabeto, especifica-se alguns regras de produção, que dizem como formar uma entidade em alguma categoria sintática a partir de um grupo de entidades em outras categorias sintáticas. Por exemplo, podemos formar um sintagma nominal a partir de um determinante (o), um adjetivo (feliz) e um substantivo (menino). Gramáticas livres de contexto são importantes em linguística e ciência da computação. No primeiro caso, eles são uma maneira básica de falar sobre a estrutura das frases em linguagens naturais. No último, eles são cruciais ao projetar analisadores para linguagens de programação.

Assim, assim como os gráficos apresentam categorias livres, as gramáticas livres de contexto apresentam óperas livres. Essa ideia foi percebida pela primeira vez em [HMP98].

Óperadas de categorias monoidais simétricas

Veremos na Definição 6.97 que uma grande classe de operads vem de categorias monoidais simétricas. Antes de explicarmos isso, damos alguns exemplos. Talvez a ópera mais importante seja a de Definir.

Exemplo 6.93.

A ópera Definir de conjuntos tem

(i) Conjuntos X como tipos.

(ii) Funções X(_{1}) × ··· × X (_ {n} ) →Y como operações de aridade (X(_{1}), ..., X (_ {n} ); Y).

(iii) Substituição definida por

(g ◦ (_ {i} )f )(x(_{1}), ..., x (_ {i-1} ), C(_{1}), ..., C (_ {m} ), x (_ {i + 1} ), ..., x (_ {n} ))
= g (x(_{1}), ..., x (_ {i-1} ), f (C(_{1}), ..., C (_ {m} )), x (_ {i + 1} ), ..., x (_ {n} )

Onde f (em) Definir(C(_{1}), ..., C (_ {m} ); X(_{eu})), g (em) Definir(X(_{1}), ..., X (_ {n} ); Y), e, portanto g ◦ (_ {i} ) f é uma função

(g ◦ (_ {i} ) f ): X(_{1}) × ··· × X (_ {i-1} ) ×C(_{1}) × ··· × C (_ {m} ) × X (_ {i + 1} ) × ··· × X (_ {n} ) →Y

(iv) Identidades id (_ {X} ) ( in ) Definir(X ; X) são fornecidos pelo id da função de identidade (_ {X} ): X X.

A seguir, damos um exemplo que nos lembra para que servia todo esse material de operad: diagramas de fiação.

Exemplo 6.94.

A ópera Cospan de cospans de conjunto finito tem

(i) Números naturais uma ( in ) ( mathbb {N} ) como tipos.

(ii) Cospans uma ( underline {_ {1}} ) + ··· + uma ( underline {_ {n}} ) → p b de conjuntos finitos como operações de aridade (uma(_{1}), ..., uma (_ {n} ); b).

(iii) Substituição definida por pushout.

(iv) Identidades id (_ {a} ) ( in ) Definir(uma; uma) apenas dado pela identidade cospan ( underline {a} ) stackrel {id (_ { underline {a}} ) { rightarrow} ( underline {a} ) stackrel {id (_ { underline {a}} )} { leftarrow} ( underline {a} ) ).

Este é o análogo operádico da categoria monoidal (Cospan (_ {FinSet} ), 0, +).

Podemos descrever as operações neste operad usando diagramas como desenhamos acima. Por exemplo, aqui está a imagem de uma operação:

Esta é uma operação de aridade ( ( underline {3} ), ( underline {3} ), ( underline {4} ), ( underline {2} ); 3). Por quê? Os círculos marcados f e g tem 3 portas, h tem 4 portas, k tem 2 portas e o círculo externo tem 3 portas: 3, 3, 4, 2; 3

Então, como exatamente é a Eq. (6,95) um morfismo nesta ópera?

Bem, um morfismo deste ( underline {3} ) + ( underline {3} ) + ( underline {4} ) + ( underline {2} ) stackrel {a} { rightarrow} underline {p} stackrel {b} { leftarrow} underline {3} ).

No diagrama acima, o ápice ( underline {p} ) é o conjunto ( underline {7} ), porque existem 7 nós • no diagrama. A função uma envia cada porta em um dos pequenos círculos para o nó ao qual se conecta, e a função b envia cada porta do círculo externo para o nó ao qual se conecta.

Somos capazes de retratar cada operação do operad Cospan como um diagrama de fiação. Muitas vezes é útil pensar em operads como a descrição de uma gramática de diagrama de fiação. A operação de substituição do operad significa inserir um diagrama de fiação em um círculo ou caixa em outro diagrama de fiação.

Exercício 6.96.

1. Considere o seguinte cospan f (em) Cospan(2, 2; 2):

Desenhe-o como um diagrama de fiação com dois círculos internos, cada um com duas portas, e um círculo externo com duas portas.

2. Desenhe o diagrama de fiação correspondente ao seguinte cospan g (em) Cospan(2, 2, 2; 0):

3. Calcule o cospan g ◦(_{1}) f . Qual é a sua aridade?

4. Desenhe o cospan g ◦(_{1}) f . Você vê isso como uma substituição? ♦

Podemos transformar qualquer categoria monoidal simétrica em uma operad de uma forma que generalize os dois exemplos acima.

Definição 6.97.

Para qualquer categoria monoidal simétrica (C, eu, ⊗), há um operad O (_ {C} ), chamado de operad subjacente C, definido como tendo:

(i) Ob (C) como tipos.

(ii) morfismos C(_{1}) ⊗ ··· ⊗ C (_ {n} ) →D em C como as operações de aridade (C(_{1}), ..., C (_ {n} ); D).

(iii) substituição é definida por

(f ◦ (_ {i} ) g) := f ◦ (id, ..., id, g, Eu fiz)

(iv) identidades id (_ {a} ) ( in ) O (_ {C} ) (uma ; uma) definido por id (_ {a} ).

Também podemos transformar qualquer functor monoidal no que é chamado de functor operad.

O operad para hipergrafos adereços

Um operad functor leva os tipos de um operad aos tipos de outro, e então as operações do primeiro às operações do segundo de uma forma que respeite isso.

Definição de Rpugh 6.98.

Suponha que dados dois operads O e P com coleções de tipos T e você respectivamente. Para especificar um operad functor F : O → P,

(i) um especifica uma função f : T você.
(ii) Para todas as aridades (t(_{1}), . , t (_ {n} ); t) em O, especifica-se uma função

F : O (t(_{1}), ..., t (_ {n} ); t) → P (f (t(_{1})), ..., f (t (_ {n} )); f (t))

de modo que a composição e as identidades sejam preservadas.

Assim como os functores de valor definido C → Definir de qualquer categoria C são de particular interesse - nós os vimos como instâncias de banco de dados no Capítulo 3, para serem Definir-functores avaliados O → Definir de qualquer operad O.

Definição 6.99.

Um álgebra para um operad, O é um operad functor F : O → Definir.

Podemos pensar em functores O → Definir como definir um conjunto de maneiras possíveis de preencher as caixas em um diagrama de fiação. Na verdade, cada caixa em um diagrama de fiação representa um tipo t do dado operad O e uma álgebra F : O → Definir tomará um tipo t e devolver um conjunto F(t) de enchimentos para caixa t. Além disso, dada uma operação (ou seja, um diagrama de fiação) f (eu não(t1, . , tn; t), temos uma função F(f) que leva um elemento de cada conjunto F(teu) e retorna um elemento de F(t) Por exemplo, leva n circuitos com interface t1, . , tn respectivamente, e retorna um circuito com limite t.

Exemplo 6.100.

Para circuitos elétricos, os tipos são novamente conjuntos finitos, T = Ob (FinSet), onde cada conjunto finito t (em) T corresponde a uma célula com t portas. Assim como antes, temos um Circ (t) de enchimentos, ou seja, o conjunto de circuitos elétricos com aquele tterminais marcados. Como uma álgebra operada, Circ: Cospan Definir transforma diagramas de fiação como este

em fórmulas que constroem um novo circuito a partir de um monte de circuitos existentes.

No caso desenhado acima, obteríamos um morfismo Circ (φ) ( in ) Definir(Circ (2), Circ (2), Circ (2); Circ (0)), ou seja, uma função

Circ (φ): Circ (2) × Circ (2) × Circ (2) → Circ (0).

Poderíamos aplicar esta função aos três elementos de Circ (2) mostrados aqui

e o resultado seria o circuito fechado do início do capítulo:

Isso é uma reminiscência da história dos cospans decorados: colar enchimentos para formar categorias de hipergrafos. Uma vantagem da construção do cospan decorado é que se obtém uma categoria explícita (onde morfismos têm domínios e codomínios e podem, portanto, ser compostos associativamente), equipada com estruturas de Frobenius que nos permitem contornar as restrições de domínios e codomínios. A perspectiva operad tem outras vantagens. Primeiro, enquanto cospans decorados podem produzir apenas algumas categorias de hipergrafos, Cospan-álgebras podem produzir qualquer categoria de hipergrafo.

Proposição 6.101.

Existe uma equivalência entre Cospan-álgebras e adereços do hipergrafo.

Outra vantagem de usar operads é que se pode variar o operad em si, de Cospan a algo semelhante (como a ópera de "cobordismos") e obter regras de composição ligeiramente diferentes.

Na verdade, óperas com complexidade adicional em sua definição - podem ser personalizadas ainda mais do que todas as estruturas composicionais definidas até agora. Por exemplo, podemos definir operads de diagramas de fiação onde os diagramas de fiação devem obedecer a condições precisas muito mais específicas do que as restrições de uma categoria, como exigir que o diagrama em si não tenha fios que passem por ele. Na verdade, operads são fortes o suficiente para se definirem: grosso modo, existe uma operad para operads: a categoria de operads é equivalente à categoria de álgebras para um determinado operad [Lei04, Exemplo 2.2.23]. Embora as óperas possam, é claro, ser generalizadas novamente, elas concluem nossa marcha através de uma hierarquia informal de estruturas composicionais, de pré-ordens a categorias, de categorias monoidais a óperas.


Assista o vídeo: Obliczanie wartości wyrażeń algebraicznych - Matematyka Szkoła Podstawowa i Gimnazjum (Outubro 2021).