Comutativa Não-Associativa e Associativa Não-Comutativa

#computerscience #learning

Em uma das vezes que decidi estudar Teoria das Categorias, parcialmente por causa de Programação Funcional, Provadores Automáticos e parcialmente por nenhum motivo em especial. Essa foi provavelmente a vez que levei o assunto mais a sério e tentei criar intuição sobre vários tópicos que encontrei no caminho.

Até hoje não posso dizer que entendo bem Teoria das Categorias, mas consegui alguns exemplos e intuições úteis no caminho. Nesse texto vou falar sobre quando precisei entender Comutatividade e Associatividade como propriedades separadas, afinal é muito fácil pensar nas duas juntas já que os conjuntos de números que usamos no dia-a-dia tem ambas as propriedades. A seguir vou mostrar os exemplos e explica-los em algum nível. Podem botar dúvidas nos comentários ou outros exemplos, a discussão é bem-vinda.

Operação comutativa, mas não-associativa

Vou usar uma notação levemente diferente, mas gosto de usar operadores infixos para esse assunto, então prefiro descrever a operação abaixo da mesma forma. Vou usar a média de dois números racionais ( $\mathbb{Q}$ ).

p \star q \triangleq \frac{p + q}{2}

Média é uma operação comutativa

p \star q = \frac{p + q}{2} = \frac{q + p}{2} = q \star p

Mas média não é associativa

(p \star q) \star r = \frac{\frac{p + q}{2} + r}{2} = \frac{\frac{p}{2} + \frac{q}{2} + r}{2} = \frac{p}{4} + \frac{q}{4} + \frac{r}{2} \\~\\ p \star (q \star r) = \frac{p + \frac{q + r}{2}}{2} = \frac{p + \frac{q}{2} + \frac{r}{2}}{2} = \frac{p}{2} + \frac{q}{4} + \frac{r}{4} \\~\\ \frac{p}{4} + \frac{q}{4} + \frac{r}{2} \neq \frac{p}{2} + \frac{q}{4} + \frac{r}{4} \to (p \star q) \star r \neq p \star (q \star r) \\~\\

Dando um exemplo com números.

p = 1; \qquad q = 2; \qquad r = 3 \\~\\ (p \star q) \star r = (1 \star 2) \star 3 = \frac{\frac{1 + 2}{2} + 3}{2} = \frac{\frac{3}{2} + 3}{2} = \frac{3}{4} + \frac{3}{2} = \frac{3}{4} + \frac{6}{4} = \frac{9}{4} \\~\\ p \star (q \star r) = 1 \star (2 \star 3) = \frac{1 + \frac{2 + 3}{2}}{2} = \frac{1 + \frac{5}{2}}{2} = \frac{1}{2} + \frac{5}{4} = \frac{2}{4} + \frac{5}{4} = \frac{7}{4} \\~\\ \frac{9}{4} \neq \frac{7}{4}

Operação associativa, mas não comutativa

O concatenação de strings (encadeamento de sequências de símbolos) é um exemplo de operação que é associativa, mas não é comutativa. Para diferenciar um símbolo que seja uma variável de um que seja o valor de uma vou usar aspas duplas para os valores.

x \text{ é uma variável} \\~\\ "x" \text{ é um valor}

Primeiro um símbolo infixo para concatenação, vou usar o mesmo da linguagem de programação Julia.

"\text{a}" * "\text{b}" \triangleq "\text{ab}"

Concatenação de strings não é comutativa

Parece óbvio, mas vou dar só um contraexemplo.

"\text{a}" * "\text{b}" = "\text{ab}" \\~\\ "\text{b}" * "\text{a}" = "\text{ba}" \\~\\ "\text{ab}" \neq "\text{ba}" \to "\text{a}" * "\text{b}" \neq "\text{b}" * "\text{a}"

Concatenação de strings é associativa

Dadas 3 strings $x, y \text{ e } z$ quaisquer, vale o abaixo.

x * y * z = x * (y * z) = (x * y) * z

Para um exemplo com valores:

x = "\text{obrigado}" \\~\\ y = "\text{ por ler}" \qquad \text{(observe o espaço no início)} \\~\\ z = "\text{ até aqui}" \qquad \text{(observe o espaço no início)} \\~\\ x * (y * z) = "\text{obrigado}" * ("\text{ por ler}" * "\text{ até aqui}") = "\text{obrigado}" * "\text{ por ler até aqui}" = "\text{obrigado por ler até aqui}" \\~\\ (x * y) * z = ("\text{obrigado}" * "\text{ por ler}") * "\text{ até aqui}") = "\text{obrigado por ler}" * "\text{ até aqui}" = "\text{obrigado por ler até aqui}" \\~\\ x * (y * z) = (x * y) * z = x * y * z = "\text{obrigado por ler até aqui}"

Muito obrigado por ler até aqui. Esses exemplos junto com o produto de matrizes (que também é associativo, mas não comutativo) me ajudaram muito numa das vezes que tentei estudar Teoria das Categorias. Espero que seja útil para mais alguém.