Conjuntos, relações e funções

Conjuntos são coleções sem ordem e sem repetição, como o set do Python. As operações básicas têm tradução direta para código:

A ∪ B   união          a | b
A ∩ B   interseção     a & b
A \ B   diferença      a - b
A △ B   dif. simétrica a ^ b
|A|     cardinalidade  len(a)

Relações

Uma relação entre A e B é um subconjunto de A × B. Uma tabela de junção no banco de dados (usuario_id, grupo_id) é literalmente uma relação. Relações de equivalência (reflexiva, simétrica, transitiva) dividem o conjunto em classes: é o que a estrutura Union-Find mantém.

Funções

Uma função f: A → B associa cada elemento de A a exatamente um de B. Ela é injetora se não repete saídas, sobrejetora se atinge todo B e bijetora se é as duas coisas. Toda função de hash de um domínio grande para um pequeno deixa de ser injetora: colisões são inevitáveis.

def e_equivalencia(rel, universo):
    reflexiva = all((a, a) in rel for a in universo)
    simetrica = all((b, a) in rel for (a, b) in rel)
    transitiva = all((a, d) in rel
                     for (a, b) in rel for (c, d) in rel if b == c)
    return reflexiva and simetrica and transitiva