Teoria das Categorias Ilustrada – Ordens

Quando se tem um conjunto de objetos, existem inúmeros critérios pelos quais eles podem ser ordenados (dependendo dos próprios objetos) — tamanho, peso, idade, ordem alfabética, entre tantos outros. No entanto, neste momento, não estamos interessados nos critérios que utilizamos para ordenar os objetos, mas sim na natureza das relações que definem essa ordem. E existem vários tipos dessas relações. Matematicamente, a ordem como construção é representada (assim como um monóide) por dois componentes: um conjunto de elementos e uma relação binária entre esses elementos, que obedece a determinadas leis. Essa relação binária é frequentemente denotada com uma seta, indicando a direção da ordem entre dois elementos. Por exemplo, se tivermos dois elementos, A e B, e A for “menor” ou “anterior” a B, representamos como A → B. As leis que regem essas relações variam conforme o tipo de ordem que estamos analisando. Vamos começar com um exemplo simples: o tipo mais direto de ordem que se pode imaginar é a ordem linear, na qual cada objeto tem seu lugar definido em relação a todos os outros. Nesse caso, o critério de ordenação é completamente determinístico e não deixa margem para ambiguidades sobre qual elemento vem antes de qual. Um exemplo clássico é a ordem das cores do arco-íris, que segue o comprimento de onda da luz visível, ou seja, do vermelho ao violeta.

A teoria dos conjuntos permite representar essa ordem — e qualquer outra ordem — como um conjunto de pares ordenados do conjunto subjacente ao próprio conjunto. Em programação, as ordens são definidas por meio de uma função que, dados dois objetos, indica qual deles é “maior” (vem antes) e qual é “menor”. Não é difícil perceber que essa função define um conjunto de pares: ao receber um par de elementos, ela determina se esse par pertence ou não ao conjunto ordenado. No entanto, nem todas as funções (nem todos os conjuntos de pares) definem uma ordem propriamente dita. Para que uma função realmente defina uma ordem, ou seja, produza sempre a mesma saída independentemente de como os objetos são organizados inicialmente, ela deve obedecer a várias regras. Essas regras são quase equivalentes às leis matemáticas que definem os critérios da relação de ordem, ou seja, as regras que determinam quais elementos podem apontar para quais outros.

Uma ordem linear é um conjunto de elementos associado a uma relação binária entre esses elementos, obedecendo às leis de reflexividade, transitividade, antissimetria e totalidade. Vamos examinar cada uma delas. Começando pela lei mais óbvia: cada objeto deve ser maior ou igual a si mesmo, ou seja, para todo elemento A, temos A ≤ A. Essa lei existe basicamente para cobrir o “caso base” da ordem. Alternativamente, poderíamos dizer que nenhum objeto tem relação consigo mesmo, o que resultaria em uma relação semelhante a “maior que” em vez de “maior ou igual”, definindo assim uma ordem estrita, um tipo ligeiramente diferente de ordem. A segunda lei, embora menos óbvia, é provavelmente a mais essencial: se um objeto A é maior que um objeto B, então A também é maior que qualquer objeto que seja menor que B. Em termos matemáticos, se A ≤ B e B ≤ C, então A ≤ C. Essa lei define em grande parte o que é uma ordem: se sou melhor em futebol que minha avó, também serei melhor que a amiga dela, a quem minha avó supera. Caso contrário, não seria realmente melhor que ela.

A terceira lei é a antissimetria, que estabelece que a função que define a ordem não pode produzir resultados contraditórios. Em outras palavras, só podemos ter A ≤ B e B ≤ A se A for igual a B. Isso também significa que não são permitidos empates: ou sou melhor que minha avó no futebol, ou ela é melhor que eu. A quarta e última lei é a totalidade (ou conexidade), que determina que todos os elementos pertencentes à ordem devem ser comparáveis. Para quaisquer dois elementos, um sempre será “maior” que o outro. Vale observar que a lei de totalidade torna a lei de reflexividade redundante, já que a reflexividade é apenas um caso especial da totalidade quando A e B são o mesmo objeto. No entanto, ainda apresentarei a reflexividade por motivos que ficarão claros adiante. Na verdade, a lei de totalidade pode ser removida. Ordens que não seguem essa lei são chamadas de ordens parciais (e as ordens lineares também são chamadas de ordens totais).

Antes de avançarmos, vamos recordar uma relação semelhante que já abordamos anteriormente. Você lembra qual era? Qual é a diferença entre elas? Ordens parciais são, na verdade, muito mais interessantes do que as ordens lineares ou totais. Mas antes de explorá-las em detalhes, vamos falar um pouco sobre números. Os números naturais formam uma ordem linear sob a operação “maior ou igual”. De muitas maneiras, os números naturais são a quintessência das ordens: qualquer ordem finita de objetos é isomorfa a um subconjunto da ordem dos números, pois podemos mapear o primeiro elemento de qualquer ordem para o número 1, o segundo para o número 2, e assim por diante. E a operação inversa também é válida. Na prática, esse isomorfismo está mais próximo da noção cotidiana de ordem linear do que a definição baseada em leis matemáticas. Quando as pessoas pensam em ordem, geralmente não estão pensando em uma relação transitiva, antissimétrica e total, mas sim em critérios pelos quais podem decidir qual objeto vem primeiro, qual vem segundo, etc. Portanto, é importante notar que essas duas noções são equivalentes.

O fato de qualquer ordem finita de objetos ser isomorfa aos números naturais também implica que todas as ordens lineares de mesma magnitude são isomorfas entre si. Portanto, a ordem linear é simples, mas também — e penso que esse isomorfismo prova isso — a mais monótona de todas, especialmente quando analisada do ponto de vista da teoria das categorias. Todas as ordens lineares finitas (e a maioria das infinitas) são simplesmente isomorfas aos números naturais, de modo que todos os seus diagramas se parecem da mesma forma. No entanto, isso não ocorre com as ordens parciais, que analisaremos a seguir. A lei de totalidade não parece tão “inquestionável” quanto as outras leis, ou seja, podemos pensar em situações em que ela não se aplica. Por exemplo, se tentarmos ordenar todas as pessoas com base em suas habilidades no futebol, haverá muitas maneiras de classificar uma pessoa em relação aos amigos dela e aos amigos dos amigos, mas não há como ordenar grupos de pessoas que nunca jogaram juntas. Se removermos a lei de totalidade das leis das ordens lineares, obteremos uma ordem parcial (também chamada de conjunto parcialmente ordenado ou poset).

Uma ordem parcial é um conjunto de elementos associado a uma relação binária entre esses elementos, obedecendo às leis de reflexividade, transitividade e antissimetria. Toda ordem linear também é uma ordem parcial (assim como um grupo ainda é um monóide), mas nem toda ordem parcial é uma ordem linear. Podemos até mesmo criar uma ordem entre as próprias ordens, com base em qual é mais geral. As ordens parciais também estão relacionadas ao conceito de relações de equivalência que abordamos no capítulo 1, exceto que a lei de simetria é substituída pela antissimetria. Ao revisitarmos o exemplo da classificação de jogadores de futebol, percebemos que a versão inicial, que incluía apenas a mim, minha avó e a amiga dela, é uma ordem linear. No entanto, ao adicionar outra pessoa com quem ninguém jogou ainda, a hierarquia se torna não linear, ou seja, uma ordem parcial. Essa é a principal diferença entre ordens parciais e totais: as ordens parciais nem sempre conseguem fornecer uma resposta definitiva sobre quem é melhor que quem. Mas às vezes é justamente isso que precisamos, tanto no esporte quanto em outros domínios, pois nem sempre há uma maneira adequada de classificar elementos de forma linear.

Antes, dissemos que todas as ordens lineares podem ser representadas pelo mesmo diagrama em cadeia. Podemos inverter essa afirmação e dizer que todos os diagramas que não se parecem com esse diagrama representam ordens parciais. Um exemplo disso é uma ordem parcial que contém vários subconjuntos linearmente ordenados. No exemplo do futebol, podemos ter grupos separados de amigos que jogam juntos e são classificados entre si, mas não com ninguém de outros grupos. Esses diferentes subconjuntos linearmente ordenados que compõem a ordem parcial são chamados de cadeias. No diagrama acima, temos duas cadeias: M → G → F e D → O. Nas ordens parciais, as cadeias não precisam estar completamente desconectadas umas das outras para que a ordem seja parcial. Elas podem se conectar desde que as conexões não sejam todas um-para-um, ou seja, quando o último elemento de uma cadeia se conecta ao primeiro elemento de outra (isso uniria efetivamente as duas cadeias em uma só).

No conjunto acima, não temos uma ordem linear: embora saibamos que D ≤ G e que F ≤ G, a relação entre D e F não é conhecida — qualquer um dos elementos pode ser maior que o outro. Embora as ordens parciais não nos deem uma resposta definitiva para “Quem é melhor que quem?”, algumas delas ainda conseguem responder a uma pergunta mais importante (tanto no esporte quanto em outros domínios): “Quem é o número um?”, ou seja, quem é o campeão, o jogador que é melhor que todos os outros. Ou, de forma mais geral, o elemento que é maior que todos os demais. O maior elemento de uma ordem é aquele elemento A para o qual temos X ≤ A para qualquer outro elemento X da ordem. Nem todas as ordens parciais possuem tal elemento — no último diagrama, M é o maior elemento, enquanto no diagrama a seguir, o elemento verde é o maior.

Às vezes, há mais de um elemento que é maior que todos os outros, caso em que nenhum deles é o maior elemento. Além do maior elemento, uma ordem parcial também pode ter um menor elemento (o menor de todos), definido da mesma forma. A menor cota superior de dois elementos conectados em uma ordem é chamada de união desses elementos. Por exemplo, o elemento verde é a união dos outros dois. A união de A e B é o menor elemento C que é maior que ambos, formalmente: Dados quaisquer dois elementos em que um é maior que o outro (por exemplo, A ≤ B), a união é esse elemento maior (nesse caso, B). Por exemplo, nas ordens lineares, a união de quaisquer dois elementos é simplesmente o elemento maior. Assim como ocorre com o maior elemento, se dois elementos tiverem várias cotas superiores igualmente grandes, nenhuma delas será a união (a união deve ser única). No entanto, se um desses elementos for estabelecido como menor que os demais, ele imediatamente se qualifica como a união.

Dada uma ordem, o maior elemento que é menor que ambos é chamado de intersecção desses elementos. As mesmas regras aplicadas às uniões se aplicam aqui, mas de forma invertida. Os diagramas que utilizamos nesta seção são chamados de “diagramas de Hasse” e funcionam de maneira semelhante aos nossos diagramas habituais, com uma regra adicional: os elementos “maiores” sempre são posicionados acima dos menores. Em termos de setas, isso significa que, se adicionarmos uma seta de um ponto a outro, o ponto de destino deve sempre estar acima do ponto de origem. Essa disposição nos permite comparar quaisquer dois pontos simplesmente observando qual está acima do outro. Por exemplo, podemos determinar a união de dois elementos identificando os elementos aos quais eles se conectam e vendo qual está mais baixo. Todos nós conhecemos muitos exemplos de ordens totais (qualquer tipo de classificação ou ranking é uma ordem total), mas provavelmente não há tantos exemplos óbvios de ordens parciais que possamos citar de imediato. Por isso, vamos explorar alguns para contextualizar e ajudar a entender o que são uniões e intersecções.

Para manter a coerência com nosso estilo, vamos revisitar nosso monóide de mistura de cores e criar uma ordem parcial de mistura de cores na qual todas as cores apontem para as cores que as contêm. Ao percorrer essa ordem, você notará que a união de quaisquer duas cores é a cor resultante de sua mistura. Legal, não é? Vimos que, ao ordenar números pela relação “maior ou igual”, eles formam uma ordem linear. Mas os números também podem formar uma ordem parcial, por exemplo, quando os ordenamos pela relação de divisibilidade. Nesse caso, se A divide B, então A vem antes de B. Por exemplo, como 2 × 5 = 10, tanto 2 quanto 5 vêm antes de 10 (mas 3, por exemplo, não vem antes de 10). Acontece que, por um motivo muito bom, a operação de união nessa ordem parcial corresponde a uma operação relevante no contexto dos objetos — a união de dois números nessa ordem parcial é o mínimo múltiplo comum deles. E a intersecção (o oposto da união) de dois números é o máximo divisor comum.

Dada uma coleção de conjuntos que contêm uma combinação de elementos de um conjunto dado, podemos definir o que é chamado de ordem de inclusão desses conjuntos. A ordem de inclusão de conjuntos é uma relação binária que permite ordenar uma coleção de conjuntos (geralmente conjuntos que compartilham alguns elementos em comum) na qual A vem antes de B se A incluir B, ou seja, se B for um subconjunto de A. Nesse caso, a operação de união de dois conjuntos é a união deles, e a operação de intersecção é a intersecção dos conjuntos. Você pode reconhecer esse diagrama — se pegarmos as cores contidas em cada conjunto e as misturarmos em uma única cor, obteremos a ordem parcial de mistura de cores que vimos anteriormente. O exemplo de ordem com divisores de números também é isomorfo a uma ordem de inclusão, especificamente a ordem de inclusão de todos os conjuntos possíveis de números primos, incluindo repetições (ou, alternativamente, o conjunto de todas as potências de primos). Isso é confirmado pelo Teorema Fundamental da Aritmética, que estabelece que todo número pode ser escrito como um produto de primos de maneira única.

Até agora, vimos dois exemplos diferentes de ordens parciais — uma baseada na mistura de cores e outra na divisão de números — que podem ser representadas pelas ordens de inclusão de todas as combinações possíveis de conjuntos de elementos básicos (as cores primárias no primeiro caso e os números primos ou potências de primos no segundo). Muitas outras ordens parciais podem ser definidas dessa maneira. Quais exatamente são essas ordens é uma questão respondida por um resultado incrível chamado Teorema da Representação de Birkhoff. São as ordens parciais finitas que atendem aos seguintes dois critérios: as ordens parciais que atendem ao primeiro critério são chamadas de reticulados. As que atendem ao segundo são chamadas de reticulados distributivos. Vamos registrar isso: ordens parciais em que todos os elementos têm uniões e intersecções são chamados de reticulados. Um reticulado cujas operações de intersecção e união são distributivas entre si é chamado de reticulado distributivo. E os elementos “primos”, que utilizamos para construir a ordem de inclusão, são aqueles que não são a união de quaisquer outros elementos. Eles também são chamados de elementos irredutíveis por união.

Portanto, podemos enunciar o teorema da seguinte forma: cada reticulado distributivo é isomorfo a uma ordem de inclusão de seus elementos irredutíveis por união. Aliás, as ordens parciais que não são reticulados distributivos também são isomorfas a ordens de inclusão, só que são isomorfas a ordens de inclusão que não contêm todas as combinações possíveis de elementos. Agora, vamos falar mais sobre reticulados (as ordens para as quais o Teorema de Birkhoff se aplica). Reticulados são ordens parciais em que todo par de elementos tem uma união e uma intersecção. Portanto, todo reticulado também é uma ordem parcial, mas nem toda ordem parcial é um reticulado (veremos ainda mais membros dessa hierarquia). A maioria das ordens parciais criadas com base em alguma regra são reticulados distributivos, como os exemplos da seção anterior quando desenhados em sua totalidade. Por exemplo, a ordem de mistura de cores também é um reticulado distributivo quando desenhada completamente.

Observe que adicionamos a bola preta no topo e a branca na parte inferior. Fizemos isso porque, caso contrário, os três elementos superiores não teriam um elemento de união, e os três inferiores não teriam um elemento de intersecção. Nosso reticulado de mistura de cores tem um maior elemento (a bola preta) e um menor elemento (a bola branca). Reticulados que têm um menor e um maior elemento são chamados de reticulados delimitados. Não é difícil perceber que todos os reticulados finitos também são delimitados. Antes, mencionamos isomorfismos de ordens várias vezes, então é hora de detalhar o que eles são. Dados dois conjuntos (usaremos a ordem parcial de números por divisão e a ordem de inclusão de primos como exemplo), um isomorfismo entre eles é composto pelas seguintes duas funções: uma que mapeia os elementos do primeiro conjunto nos elementos do segundo conjunto, e outra que faz o inverso. Um isomorfismo de ordens é essencialmente um isomorfismo entre os conjuntos subjacentes das ordens (função invertível). No entanto, além de seus conjuntos subjacentes, as ordens também têm as setas que as conectam, então há mais uma condição: para que uma função invertível constitua um isomorfismo de ordens, ela deve respeitar essas setas.

Um isomorfismo entre duas ordens é uma função invertível entre seus conjuntos subjacentes, de modo que, ao aplicar essa função (vamos chamá-la de F) a quaisquer dois elementos que tenham uma certa ordem em um conjunto (vamos chamá-los de A e B), o resultado deve ser dois elementos que tenham uma ordem correspondente no outro conjunto (ou seja, A ≤ B se e somente se F(A) ≤ F(B)). Tais funções são chamadas de funções que preservam a ordem. Na seção anterior, vimos como a remoção da lei de totalidade das leis da ordem (linear) produz uma estrutura diferente (e um pouco mais interessante), chamada ordem parcial. Agora, vamos ver o que acontece se removermos outra lei, a antissimetria. A lei de antissimetria determinava que não podemos ter um objeto que seja ao mesmo tempo menor e maior que outro (ou seja, A ≤ B se e somente se B não ≤ A). O resultado é uma estrutura chamada pré-ordem: um conjunto de elementos associado a uma relação binária entre eles que obedece às leis de reflexividade e transitividade.

A pré-ordem não é exatamente uma ordem no sentido cotidiano, pois pode ter setas indo de qualquer ponto para qualquer outro: enquanto uma ordem parcial pode modelar quem é melhor que quem no futebol, uma pré-ordem pode modelar quem venceu quem, seja diretamente (por ter jogado contra) ou indiretamente. As pré-ordens têm apenas uma lei — a transitividade (A ≤ B e B ≤ C implica A ≤ C) — além da reflexividade. A parte sobre as vitórias indiretas é um resultado dessa lei. Devido a ela, todas as vitórias indiretas (aquelas não contra o jogador diretamente, mas contra alguém que o venceu) são adicionadas como consequência direta de sua aplicação. Como resultado, todas as relações circulares (por exemplo, quando um jogador mais fraco vence um mais forte) resultam em um conjunto de objetos todos conectados entre si. Essa estrutura surge naturalmente a partir da simples lei da transitividade. As pré-ordens podem ser vistas como um meio-termo entre ordens parciais e relações de equivalência, pois lhes falta exatamente a propriedade que diferencia essas duas estruturas — (anti)simetria. Por causa disso, se tivermos um conjunto de objetos em uma pré-ordem que obedecem à lei da simetria, esses objetos formam uma relação de equivalência. E se obedecerem à lei inversa da antissimetria, formam uma ordem parcial.

Em particular, qualquer subconjunto de objetos que estejam conectados mutuamente em ambas as direções (como no exemplo acima) obedece ao requisito de simetria. Portanto, se agruparmos todos os elementos que têm tal conexão, obteremos um conjunto de classes de equivalência da pré-ordem, cada uma definindo diferentes relações de equivalência baseadas na pré-ordem. E, ainda mais interessante, se transferirmos as conexões da pré-ordem entre os elementos desses conjuntos para conexões entre os próprios conjuntos, essas conexões obedeceriam ao requisito de antissimetria, o que significa que formariam uma ordem parcial. Em resumo, para cada pré-ordem, podemos definir a ordem parcial das classes de equivalência dessa pré-ordem. Vimos que as pré-ordens são um conceito poderoso, então vamos analisar mais a fundo a lei que as rege — a lei da transitividade. O que essa lei nos diz é que, se t