Ordem vista por diagramas da teoria das categorias
(abuseofnotation.github.io)- Uma estrutura de ordem se estabelece quando uma relação binária sobre um conjunto de elementos satisfaz leis como reflexividade, transitividade e antissimetria
- Ordem linear é uma estrutura em que todo par de elementos é comparável; removendo a totalidade, obtém-se uma ordem parcial
- Em uma ordem parcial, é possível entender a estrutura por meio de cadeias, maior elemento e menor elemento, join·meet e diagramas de Hasse
- Mistura de cores, divisibilidade e relação de inclusão entre conjuntos são exemplos de ordens parciais; quando há join e meet para todos os pares, forma-se uma lattice
- Preorder é uma estrutura que tem apenas reflexividade e transitividade, e todo preorder pode ser interpretado como uma categoria com no máximo um morfismo entre dois objetos
Ordem
- Ordem é composta por um conjunto de elementos e uma relação binária sobre ele, formando uma estrutura matemática quando satisfaz certas leis
- Mais importante do que o critério de ordenação em si é quais propriedades a relação entre os elementos possui
- Uma relação binária é uma relação entre dois elementos de um conjunto e também pode ser representada por setas
- Em teoria dos conjuntos, uma ordem pode ser representada como um subconjunto do produto cartesiano de um conjunto consigo mesmo; em programação, como uma função que compara dois objetos
- Mas nem toda função de comparação ou conjunto de pares de elementos define uma ordem; para produzir resultados consistentes independentemente do arranjo inicial, certas regras são necessárias
Ordem linear
-
Ordem linear** é uma ordem em que todos os elementos ocupam uma posição entre si, uma estrutura em que não há**ambiguidade sobre qual elemento vem antes de outro
- Como exemplo, é apresentada a ordem das cores segundo o comprimento de onda da luz ou a disposição no arco-íris
- Ordem linear é definida como uma relação binária que satisfaz reflexividade, transitividade, antissimetria e totalidade
- Essas quatro leis são as condições que constituem a relação de ordem
-
Reflexividade
- Todo elemento deve ser maior ou igual a si mesmo, isto é, para todo $a$, vale $a \le a$
- Esta é a regra que trata o caso-base; em contraste, se definirmos que um elemento não se relaciona consigo mesmo, forma-se outro tipo semelhante a uma strict order
-
Transitividade
- Se $a \le b$ e $b \le c$, então deve valer $a \le c$
- Esta é uma das leis que mais definem a essência da ordem
-
Antissimetria
- É a regra que proíbe resultados de comparação contraditórios: se $x \le y$ e $y \le x$, isso só é permitido quando $x = y$
- Também é resumida como a proibição de empates entre elementos distintos
-
Totalidade
- Todo par de elementos deve ser necessariamente comparável, e para quaisquer dois elementos vale $a \le b \lor b \le a$
- Ou seja, para qualquer par, um deles deve ser maior ou igual ao outro
- Como a totalidade inclui o caso em que $a$ e $b$ são iguais, ela também abrange a reflexividade como caso especial
- Ao remover a totalidade, obtemos uma ordem parcial, e ordem linear também é chamada de total order
-
A ordem dos números naturais
- Os números naturais formam uma ordem linear sob a relação maior ou igual
- Toda ordem linear finita é isomorfa a um subconjunto dos números naturais ao associar o primeiro elemento a 1, o segundo a 2, e assim por diante
- Portanto, todas as ordens lineares finitas de mesmo tamanho são isomorfas entre si
- Também se menciona que, do ponto de vista da teoria das categorias, o diagrama de todas as ordens lineares finitas e da maioria das infinitas parece o mesmo
Ordem parcial
- Ordem parcial é a estrutura obtida ao remover a totalidade de uma ordem linear, mantendo apenas reflexividade, transitividade e antissimetria
- Também recebe o nome de partially-ordered set, ou poset
- Toda ordem linear é uma ordem parcial, mas nem toda ordem parcial é linear
- Ordem parcial também se conecta a relações de equivalência: é a estrutura que surge ao trocar a simetria da equivalência por antissimetria
- No exemplo de comparar habilidade no futebol, se há apenas algumas pessoas que podem ser comparadas direta ou indiretamente, uma ordem linear pode ser possível; mas, se entram pessoas que nunca jogaram entre si, a estrutura se torna não linear, formando uma ordem parcial
- Uma ordem parcial pode não dar sempre uma resposta definitiva à pergunta de quem é melhor
-
Cadeia
- Uma ordem parcial pode ser composta por vários subconjuntos lineares, e esses subconjuntos lineares são chamados de chain
- Como exemplo, são apresentadas as duas cadeias $m \to g \to f$ e $d \to o$
- As cadeias não precisam estar completamente separadas; desde que nem todas as conexões se encadeiem uma a uma até formar uma única cadeia, a ordem continua parcial
- No exemplo, é possível saber que $d \le g$ e $f \le g$, mas a relação entre $d$ e $f$ permanece indefinida
-
Maior elemento e menor elemento
- Se um elemento $a$ satisfaz $x \le a$ para todo outro elemento $x$, então ele é o greatest element
- Algumas ordens parciais possuem tal elemento; no diagrama de exemplo, $m$ é o greatest element
- Mesmo que vários elementos sejam maiores do que todos os outros, se eles não forem iguais entre si, então não existe greatest element
- De forma análoga, define-se o least element
-
Join
- O least upper bound de dois elementos conectados é chamado de join
- A definição tem duas condições
- Deve valer $A \le G$ e $B \le G$
- Para qualquer outro elemento $P$ maior do que $A$ e $B$, deve valer $G \le P$
- Se um elemento for maior que o outro, o join é o próprio elemento maior
- Em uma ordem linear, o join de quaisquer dois elementos é simplesmente o elemento maior
- Se houver vários limitantes superiores de mesmo nível, o join não existe; o join deve ser único
-
Meet
- Entre os elementos que são menores ou iguais a ambos, o maior deles é chamado de meet
- As mesmas regras do join se aplicam em sentido oposto
-
Diagramas de Hasse
- Os diagramas usados nesta seção são diagramas de Hasse
- Há a regra adicional de sempre posicionar os elementos maiores acima
- Se houver uma seta, o ponto para o qual ela aponta fica sempre mais acima
- Com essa disposição, é possível comparar elementos apenas observando sua posição relativa, e o join também pode ser identificado buscando o mais baixo entre os elementos ligados em comum
-
Ordem parcial de mistura de cores
- É apresentada uma color-mixing partial order definida de modo que cada cor aponte para as cores que a incluem
- O join de quaisquer duas cores é a cor produzida pela mistura das duas
-
Ordem parcial dos números pela divisibilidade
- Se os números forem ordenados não por tamanho, mas por divisibilidade, forma-se uma ordem parcial
- Define-se que $a$ vem antes de $b$ se $a$ divide $b$
- Por exemplo, como $2 \times 5 = 10$, 2 e 5 vêm antes de 10, mas 3 não vem antes de 10
- Nessa ordem, o join é o mínimo múltiplo comum, e o meet é o máximo divisor comum
-
Ordem parcial por inclusão
- Quando há vários conjuntos contendo alguns elementos em comum, pode-se definir uma inclusion order
- Se o conjunto $a$ inclui $b$, ou, dito de outra forma, se $b$ é subconjunto de $a$, então $a$ vem antes de $b$
- Nesse caso, o join é a união, e o meet é a interseção
- Se misturarmos as cores contidas em cada conjunto, obtemos a mesma estrutura da ordem parcial de mistura de cores vista antes
- A ordem por divisibilidade dos números é isomorfa à ordem de inclusão de conjuntos de primos ou prime powers com repetição permitida
- Isso pode ser verificado pelo teorema fundamental da aritmética, segundo o qual todo número é expresso como produto de primos de uma única maneira
Teorema da representação de Birkhoff
- Tanto a ordem parcial da mistura de cores quanto a da divisibilidade dos números podem ser representadas como uma ordem de inclusão sobre combinações possíveis de certos elementos básicos
- No primeiro caso, os elementos básicos são as cores primárias; no segundo, os números primos ou suas potências
- O Birkhoff’s representation theorem determina quais ordens parciais finitas podem ser representadas desse modo
- Há duas condições
- Deve existir join e meet para todo par de elementos
- Join e meet devem ser distributivos entre si. Usando a notação $∨$ e $∧$, temos $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
- Há duas condições
- Uma ordem parcial em que todo elemento possui join e meet é uma lattice
- Quando essas operações são distributivas entre si, temos uma distributive lattice
- Os elementos “primos” que compõem a ordem de inclusão são aqueles que não podem ser expressos como join de outros elementos, chamados de join-irreducible elements
- O teorema também pode ser formulado dizendo que toda distributive lattice é isomorfa à inclusion order de seus próprios join-irreducible elements
- Mesmo uma ordem parcial que não seja distributive lattice pode ser isomorfa a uma inclusion order; nesse caso, ela corresponde a uma ordem de inclusão que não contém todas as combinações possíveis
Reticulado
- Lattice é uma ordem parcial em que todo par de elementos possui join e meet
- Toda lattice é uma ordem parcial, mas nem toda ordem parcial é uma lattice
- Muitas ordens parciais geradas por certas regras são distributive lattices, e os exemplos da seção anterior também se tornam distributive lattices quando desenhados de forma completa
- No exemplo da mistura de cores, adiciona-se uma bola preta na parte superior e uma bola branca na inferior
- Caso contrário, os três elementos superiores não teriam join, e os três inferiores não teriam meet
-
Reticulado limitado
- Uma lattice que possui tanto greatest element quanto least element é chamada de bounded lattice
- Na lattice de mistura de cores, a bola preta é o greatest element e a branca é o least element
- Também se menciona que toda lattice finita é bounded
Isomorfismo de ordem
- Isomorfismo de ordem é uma função invertível entre os conjuntos subjacentes de duas ordens que preserva as setas da ordem
- No exemplo da ordem por divisibilidade dos números e da ordem por inclusão de primos, ele é composto por duas funções
- A função que vai da ordem de inclusão de primos para a ordem dos números é a multiplicação dos elementos do conjunto
- A função que vai da ordem dos números para a ordem de inclusão de primos é a prime factorization do número
- A condição essencial de um isomorfismo de ordem é que, para dois elementos $a$, $b$, $a \le b$ se e somente se $F(a) \le F(b)$
- Esse tipo de função é chamado de order-preserving
Preordem
- Preorder é a estrutura obtida ao remover a antissimetria de uma ordem linear, mantendo apenas reflexividade e transitividade
- Do ponto de vista da comparabilidade
- Em uma ordem linear, vale $a \le b$ ou $b \le a$
- Em uma ordem parcial, pode valer uma das duas ou nenhuma
- Em uma preordem, pode valer uma delas, nenhuma, ou ambas ao mesmo tempo
- Preordem difere do sentido cotidiano de ordem, pois pode haver setas partindo de qualquer ponto para outro
- É apresentado o exemplo do futebol, modelando “quem venceu quem”, incluindo vitórias indiretas
- Por causa da transitividade, vitórias indiretas são adicionadas como relações diretas; com isso, se houver relação circular, forma-se uma estrutura em que vários objetos ficam todos conectados entre si
-
Preordem e relação de equivalência
- Preordem é uma estrutura intermediária entre ordem parcial e relação de equivalência
- Isso porque falta apenas a (anti)simetria, o ponto em que elas diferem
- Em uma preordem, os elementos ligados nos dois sentidos satisfazem simetria e, portanto, formam uma relação de equivalência
- Ao agrupar tais elementos, formam-se as equivalence classes da preordem
- Se transferirmos apenas as conexões entre essas classes, elas passam a satisfazer antissimetria, formando uma ordem parcial
- Portanto, para toda preordem, é possível definir uma ordem parcial sobre as classes de equivalência dessa preordem
Preordem e categoria
- A transitividade de uma preordem é a regra segundo a qual, se existem $a \le b$ e $b \le c$, então surge $a \le c$; isso pode ser interpretado como composição de relações
- A definição de categoria inclui as duas condições a seguir
- Existe um morfismo identidade para cada objeto
- Dois morfismos adequados podem ser compostos, e essa composição deve ser associativa
- Em uma preordem, a transitividade cumpre o papel da composição, e a reflexividade faz o papel do morfismo identidade
- Portanto, toda preordem é uma categoria
- Em uma categoria geral, podem existir vários morfismos entre dois objetos, mas em uma preordem existe no máximo um morfismo entre quaisquer dois objetos
- Ou existe $a \le b$, ou não existe
- Assim como um monoide é uma categoria com um único objeto, uma ordem pode ser entendida como uma categoria com no máximo um morfismo entre dois objetos
- Por essa propriedade, em uma preordem todo diagrama comuta
-
Propriedades categóricas de ordens parciais e preordens
- Tanto ordens parciais quanto preordens são casos especiais de preordens, portanto também são categorias
- Na teoria das categorias, preordens são mencionadas como skeletal categories, categorias em que objetos isomorfos não coexistem como distintos
-
Produto e coproduto
- A definição de coproduct em uma categoria consiste em dois morfismos $A \to A + B$, $B \to A + B$ e uma propriedade universal
- Isso tem exatamente a mesma forma da definição de join em uma ordem
- Em uma ordem, como todo morfismo é único, “ser maior” corresponde à “existência de um morfismo único”
- Portanto, na categoria de uma preordem, o coproduct categórico é o join
- Pela dualidade, o product corresponde ao meet
-
Definição formal
- Na teoria das categorias, uma categoria que, como uma ordem, tem no máximo um morfismo entre dois objetos é chamada de thin category
- Toda preordem pode ser vista como uma thin category e, inversamente, toda categoria desse tipo pode ser interpretada como uma preordem
- Thin categories são usadas para explorar o conceito de categoria em um contexto mais fácil de entender do que o de categorias gerais
- Entender meet e join também ajuda a compreender os conceitos mais gerais de category theory, como product e coproduct
- Também é uma estrutura útil quando não importa distinguir múltiplos morfismos entre objetos e só se precisa de uma estrutura simples
1 comentários
Comentários do Hacker News
[1, 3, 2].sort((a, b) => { if (a > b) { return true } else { return false } })não é um comparator válido. A API espera um número negativo, 0 ou um número positivo, mas o código retorna boolean; no meu Chrome, o resultado continuou sendo[1, 3, 2]. Para mim, a precisão matemática do texto estava num nível parecido, e deixei observações mais detalhadas neste comentário<=vale ou não. Claro que leva bastante tempo para isso ficar natural, mas, por outro lado, quanto mais você traz isso para tarefas do dia a dia, mais familiar fica. Aí você começa a olhar para testes pensando algo como "essa condição daria para modelar com algum preorder"