Teoria dos Conjuntos, Relações e Funções: Álgebra Relacional e Hashing

Teoria dos conjuntos, relações e funções

Pense em um carrinho de compras de supermercado. Dentro dele, pouco importa se a caixa de leite entrou antes ou depois do pacote de café, e se você tentar colocar exatamente o mesmo item duplicado, ele continua sendo a mesma entidade no sistema. Um conjunto é exatamente isso: uma coleção de elementos distintos onde a ordem não faz a menor diferença e duplicatas simplesmente não existem.

Se a lógica proposicional é o cérebro que decide e a indução matemática é o motor que caminha para frente, a teoria dos conjuntos é o solo onde todos os dados repousam. Toda vez que você roda um SELECT com INNER JOIN, modela uma tabela no PostgreSQL, declara um map em Go ou cria uma hierarquia de permissões no seu backend, você está manipulando conjuntos, relações e funções.

Esta aula percorre a matemática fundamental das estruturas de dados. Começaremos com as operações de conjuntos e sua tradução direta para SQL e código em Go (seções 1 a 3), avançaremos para as relações binárias e suas quatro propriedades essenciais (seções 4 e 5), estudaremos funções injetoras, sobrejetoras e o dilema das funções hash (seções 6 e 7), e fecharemos com a cardinalidade infinita de Cantor, erros comuns, exercícios resolvidos e glossário.

1. Conjuntos e álgebra booleana de dados

Formalmente, um conjunto é uma coleção bem definida de objetos, chamados de elementos ou membros. Escrevemos x ∈ A para indicar que x pertence ao conjunto A, e x ∉ A para indicar que ele não pertence.

Três propriedades distinguem conjuntos de arrays e slices tradicionais:

• Não há duplicatas: o conjunto {1, 2, 2, 3} é idêntico ao conjunto {1, 2, 3}.
• Não há ordem: {1, 2, 3} é rigorosamente o mesmo conjunto que {3, 1, 2}.
• A cardinalidade, denotada por |A|, representa a quantidade de elementos únicos dentro dele. Se A = {a, b, c}, então |A| = 3.

As operações fundamentais entre conjuntos operam exatamente como os conectivos lógicos da aula 1:

• União (A ∪ B): elementos que estão em A OU em B (equivale à disjunção ∨).
• Interseção (A ∩ B): elementos que estão em A E em B (equivale à conjunção ∧).
• Diferença (A \ B): elementos que estão em A e NÃO estão em B.
• Produto Cartesiano (A × B): o conjunto de todos os pares ordenados (a, b) onde a ∈ A e b ∈ B. A cardinalidade do produto é |A| · |B|.

Veja como essas operações regem o mecanismo de junções em bancos de dados relacionais:

O diagrama ilustra a manipulação de dados entre duas tabelas: o conjunto A (usuários ativos) e o conjunto B (assinantes pagantes). O olhar percorre da esquerda para o centro. Quando calculamos a interseção (A ∩ B), encontramos Bob e Carlos, que estão em ambos os grupos; isso equivale exatamente a um INNER JOIN. Quando executamos a união (A ∪ B), agrupamos todos os quatro usuários sem duplicatas, como um FULL OUTER JOIN. E quando calculamos a diferença (A \ B), isolamos Alice, que é ativa mas não é assinante, reproduzindo a clássica consulta SQL LEFT JOIN WHERE b.id IS NULL.

2. Implementando conjuntos eficientes em Go

Muitas linguagens possuem tipos primitivos de conjunto (como Set em Python e JavaScript). Em Go, a biblioteca padrão não traz um tipo set nativo por decisão de design, mas a comunidade adota um padrão idiomático de alto desempenho usando mapas com struct vazia (map[T]struct{}):

package main

import "fmt"

// Set representa uma colecao de elementos unicos usando memoria zero para os valores.
type Set[T comparable] map[T]struct{}

func NovoSet[T comparable](itens ...T) Set[T] {
	s := make(Set[T])
	for _, item := range itens {
		s.Adicionar(item)
	}
	return s
}

func (s Set[T]) Adicionar(item T) {
	// struct{} ocupa 0 bytes de memoria RAM no compilador de Go
	s[item] = struct{}{}
}

func (s Set[T]) Contem(item T) bool {
	_, existe := s[item]
	return existe
}

// Intersecao calcula A ∩ B em tempo O(min(|A|, |B|))
func (s Set[T]) Intersecao(outro Set[T]) Set[T] {
	resultado := make(Set[T])
	// Otimizacao: iteramos sobre o menor conjunto para poupar ciclos
	menor, maior := s, outro
	if len(s) > len(outro) {
		menor, maior = outro, s
	}
	for item := range menor {
		if maior.Contem(item) {
			resultado.Adicionar(item)
		}
	}
	return resultado
}

func main() {
	ativos := NovoSet("alice", "bob", "carlos")
	premium := NovoSet("bob", "carlos", "diana")

	comuns := ativos.Intersecao(premium)
	fmt.Printf("Usuarios ativos e premium (|A ∩ B| = %d): ", len(comuns))
	for user := range comuns {
		fmt.Printf("%s ", user) // Saida: bob carlos
	}
	fmt.Println()
}

O uso de struct{} em vez de bool no mapa é uma técnica famosa em Go: enquanto map[string]bool aloca 1 byte para cada valor booleano no heap, struct{} possui tamanho zero (unsafe.Sizeof(struct{}{}) == 0), transformando a tabela hash em um conjunto puro sem desperdício de memória.

3. O conjunto das partes e a explosão exponencial

Dado um conjunto A, o conjunto das partes (power set), denotado por P(A), é o conjunto de todos os subconjuntos possíveis de A, incluindo o conjunto vazio (∅) e o próprio A.

Se A = {1, 2}, os subconjuntos possíveis são: P(A) = { ∅, {1}, {2}, {1, 2} }

Existe um teorema matemático fundamental sobre a cardinalidade do conjunto das partes: Se |A| = n, então |P(A)| = 2ⁿ.

A intuição é simples: para montar qualquer subconjunto, você olha para cada um dos n elementos e toma uma decisão binária: “este item entra ou não entra?”. Como há 2 escolhas para cada elemento, temos 2 · 2 · … · 2 = 2ⁿ combinações.

Na computação, essa fórmula explica por que problemas que exigem testar “todas as combinações de configurações” (como o problema da mochila ou quebra de senhas por força bruta) têm complexidade exponencial O(2ⁿ) e travam rapidamente qualquer computador se n passar de 40 ou 50 itens.

4. Relações binárias e suas propriedades

Um conjunto agrupa elementos soltos. Uma relação binária R conecta elementos entre dois conjuntos (ou dentro do mesmo conjunto).

Formalmente, uma relação binária de A para B é simplesmente um subconjunto do produto cartesiano: R ⊆ A × B. Se o par (a, b) pertence a R, escrevemos a R b.

Quando uma relação opera sobre o mesmo conjunto (R ⊆ A × A), ela pode exibir quatro propriedades essenciais que os engenheiros de software utilizam todos os dias:

O diagrama desmembra essas quatro propriedades em modelos práticos:

1. Reflexiva

Para todo elemento a, a R a é verdadeiro. Todo objeto se relaciona consigo mesmo. Exemplos: A igualdade matemática (x = x) e o operador “menor ou igual” (x ≤ x). No software, a checagem de permissão onde “toda organização tem acesso a si própria”.

2. Simétrica

Se a R b, então obrigatoriamente b R a. A relação é uma via de mão dupla sem sentido único. Exemplos: A amizade no Facebook (se Alice é amiga de Bob, Bob é amigo de Alice) e o enlace físico em redes locais não-direcionadas.

3. Antissimétrica

Se a R b e b R a, então a = b. Em outras palavras: dois elementos diferentes nunca podem ter relação mútua nos dois sentidos. Exemplos: A relação de ordem menor ou igual (≤). Se x ≤ y e y ≤ x, obrigatoriamente x e y são o mesmo número. No backend, hierarquias estritas de cargos ou herança de classes onde um pai não pode ser filho do seu próprio filho.

4. Transitiva

Se a R b e b R c, então obrigatoriamente a R c. A relação permite atalhos e propaga propriedades ao longo de cadeias. Exemplos: Se Alice é mais velha que Bob, e Bob é mais velho que Carlos, Alice é mais velha que Carlos. No controle de acesso baseado em papéis (RBAC), se o papel Admin herda Editor, e Editor herda Viewer, o fechamento transitivo garante que o Admin possui acesso imediato ao Viewer.

5. Relações de equivalência e ordens parciais

Quando combinamos essas propriedades, surgem duas estruturas com aplicações gigantescas na arquitetura de sistemas:

Relação de equivalência (Reflexiva + Simétrica + Transitiva)

Uma relação de equivalência quebra um conjunto gigante em grupos menores disjuntos, chamados de classes de equivalência. Cada elemento pertence a uma, e apenas uma, classe. Exemplo: A congruência modular na matemática (dois números são equivalentes se deixam o mesmo resto na divisão por n). Em sistemas distribuídos, o particionamento de banco de dados (sharding): a função hash(user_id) % shards particiona milhões de usuários em classes isoladas que vão para servidores distintos sem colisão de partição.

Ordem parcial ou Poset (Reflexiva + Antissimétrica + Transitiva)

Uma relação de ordem parcial permite dizer quem vem antes de quem, mas não exige que todos os elementos sejam comparáveis entre si. Exemplo: Dependências de pacotes em Go ou tarefas de build em um pipeline de CI/CD. Algumas tarefas podem rodar em paralelo porque são independentes, mas outras precisam esperar pré-requisitos. A ordenação topológica de um grafo acíclico direcionado (DAG) nada mais é do que transformar uma ordem parcial em uma sequência linear de execução.

6. Funções: domínio, contradomínio e imagem

Uma função f: X → Y é um caso especial de relação binária onde cada elemento do conjunto de partida X (o domínio) é associado a exatamente um elemento do conjunto de chegada Y (o contradomínio). O conjunto dos valores reais atingidos em Y chama-se imagem da função.

As funções são classificadas de acordo com a forma como cobrem o contradomínio:

1. Injetora (um para um)

Elementos diferentes do domínio sempre produzem resultados diferentes na imagem: Se x₁ ≠ x₂, então f(x₁) ≠ f(x₂). Nenhuma saída recebe mais de uma seta vinda do domínio. No software, gerar IDs com UUID v4 busca ser uma função injetora prática para que nunca existam dois registros com a mesma chave primária.

2. Sobrejetora (cobre tudo)

Todo elemento do contradomínio Y é atingido por pelo menos um elemento do domínio X. A imagem é idêntica ao contradomínio. No software, mapear um conjunto de status internos de erro em códigos padrão HTTP (200, 400, 404, 500) é uma função sobrejetora quando todos os códigos HTTP suportados são emitidos por alguma falha do sistema.

3. Bijetora (injetora e sobrejetora ao mesmo tempo)

Existe um casamento perfeito de um para um entre X e Y. Cada entrada tem uma saída única, e nenhuma saída sobra vazia. A consequência mais importante de uma bijeção é que ela é perfeitamente invertível: existe uma função inversa f⁻¹ que desfaz o caminho com segurança matemática. Criptografia simétrica moderna (como AES) exige bijeções estritas: cada bloco de texto claro gera um bloco cifrado único, permitindo a descriptografia sem ambiguidade.

7. O dilema matemático das funções hash

Funções hash criptográficas (como SHA-256) ou tabelas hash de linguagens de programação são funções matemáticas especiais: elas recebem um domínio de tamanho infinito (qualquer sequência de bytes, arquivos de 10 gigabytes ou palavras soltas) e produzem um digest de tamanho estritamente fixo (como 256 bits).

O diagrama ilustra o mecanismo. Três entradas do domínio passam pelo motor de hash. As duas primeiras produzem valores hexadecimais únicos no contradomínio. Mas veja o que acontece com a terceira entrada e o bloco vermelho:

Como o contradomínio de uma função hash é finito (há “apenas” 2²⁵⁶ valores possíveis em SHA-256) e o domínio de dados possíveis que a humanidade pode criar é infinito, o Princípio da Casa dos Pombos (que estudaremos na aula de combinatória) dita que é matematicamente impossível que uma função hash seja perfeitamente injetora. Duas entradas diferentes em algum lugar do universo fatalmente produzirão exatamente o mesmo hash (uma colisão).

O trabalho da criptografia não é impedir colisões, mas torná-las computacionalmente inviáveis de serem encontradas antes do fim da vida útil do Sol.

8. Cardinalidade infinita e a diagonal de Cantor

Em 1874, Georg Cantor chocou os matemáticos ao provar que nem todos os infinitos têm o mesmo tamanho.

Dois conjuntos têm o mesmo tamanho (mesma cardinalidade) se, e somente se, existir uma bijeção perfeita entre eles.

Cantor dividiu os infinitos em duas classes:

1. Conjuntos contáveis: conjuntos que podem ser colocados em correspondência biunívoca com os números naturais {1, 2, 3, …}. Os inteiros (ℤ) e os números racionais (frações ℚ) são contáveis, mesmo que pareçam maiores que os naturais.
2. Conjuntos incontáveis: conjuntos densos demais para serem listados em fila, como os números reais (ℝ). Cantor provou isso com o famoso argumento da diagonal: mesmo que você tente listar todos os números reais entre 0 e 1, sempre é possível construir um novo número real alterando os dígitos da diagonal principal da tabela que não pertence à lista.

O impacto disso na ciência da computação é monumental:

• Qualquer programa de computador válido em Go, Rust ou C nada mais é do que uma cadeia finita de caracteres (código-fonte), que pode ser traduzida para um único número inteiro binário. Logo, o conjunto de todos os programas de computador possíveis é contável.
• Porém, o conjunto de todos os problemas e funções matemáticas imagináveis é incontável.

Como há infinitamente mais problemas no universo do que programas de computador que jamais poderemos escrever, a matemática prova que a maioria dos problemas computacionais é indecidível: não existe nem nunca existirá um algoritmo capaz de resolvê-los (o que Alan Turing provou formalmente com o Problema da Parada).

9. Erros comuns e boas práticas

1. Confundir relação com função. Toda função é uma relação matemática, mas nem toda relação é uma função. Se um usuário pode ter múltiplos endereços cadastrados, o mapeamento Usuario → Endereco é uma relação de um-para-muitos, e não uma função matemática determinística.
2. Supor que tabelas hash têm ordem. Em Go, o runtime introduz intencionalmente uma semente aleatória na iteração de mapas (for k := range m). Fazer código que depende da ordem de iteração de conjuntos baseados em hash gera bugs intermitentes que só aparecem em produção.
3. Não tratar a transitividade em tabelas relacionais de herança. Em bancos SQL, modelar permissões com tabelas de fechamento (closure tables) evita consultas recursivas lentas com múltiplos joins para resolver se um usuário herda permissões de grupos aninhados.
4. Tentar inverter funções que não são bijetoras. Se uma função comprime dados ou perde resolução (como extrair apenas o ano de uma data), ela não é injetora e jamais poderá ser invertida de forma determinística sem dados auxiliares.

10. Exercícios de fixação

Exercício 1: Classificação de relações

Considere o conjunto de todos os arquivos de um sistema operacional e a relação R definida por: “O arquivo x possui exatamente o mesmo tamanho em bytes que o arquivo y.”

Essa relação é de equivalência? Justifique analisando as três propriedades.

Resolução:

1. Reflexiva: Todo arquivo x tem exatamente o mesmo tamanho que ele próprio (tamanho(x) = tamanho(x)). Válida.
2. Simétrica: Se o arquivo x tem o mesmo tamanho que y, então y tem o mesmo tamanho que x. Válida.
3. Transitiva: Se tamanho(x) = tamanho(y) e tamanho(y) = tamanho(z), então tamanho(x) = tamanho(z). Válida. Conclusão: Como a relação é reflexiva, simétrica e transitiva, ela é formalmente uma relação de equivalência. Cada classe de equivalência agrupa todos os arquivos que compartilham o mesmo tamanho exato de bytes no disco.

Exercício 2: Diferença simétrica de conjuntos em Go

A diferença simétrica entre dois conjuntos (A △ B) representa os elementos que estão em A ou em B, mas NÃO estão na interseção (equivale ao operador lógico XOR).

Implemente em Go a função que calcula a diferença simétrica entre dois sets:

package main

import "fmt"

type Set[T comparable] map[T]struct{}

func NovoSet[T comparable](itens ...T) Set[T] {
	s := make(Set[T])
	for _, item := range itens {
		s[item] = struct{}{}
	}
	return s
}

// DiferencaSimetrica calcula (A \ B) ∪ (B \ A)
func (s Set[T]) DiferencaSimetrica(outro Set[T]) Set[T] {
	resultado := make(Set[T])

	// Adiciona itens de s que nao estao no outro
	for item := range s {
		if _, existe := outro[item]; !existe {
			resultado[item] = struct{}{}
		}
	}

	// Adiciona itens do outro que nao estao em s
	for item := range outro {
		if _, existe := s[item]; !existe {
			resultado[item] = struct{}{}
		}
	}

	return resultado
}

func main() {
	grupo1 := NovoSet("go", "python", "rust")
	grupo2 := NovoSet("python", "javascript", "rust")

	exclusivos := grupo1.DiferencaSimetrica(grupo2)
	fmt.Print("Diferenca simetrica (XOR): ")
	for lang := range exclusivos {
		fmt.Printf("%s ", lang) // Saida: go javascript
	}
	fmt.Println()
}

11. Glossário

• Cardinalidade: A medida do número de elementos em um conjunto, finita ou infinita.
• Produto Cartesiano: O conjunto de todos os pares ordenados possíveis formados por elementos de dois conjuntos.
• Relação de equivalência: Relação reflexiva, simétrica e transitiva que particiona um domínio em classes isoladas.
• Ordem parcial (Poset): Relação reflexiva, antissimétrica e transitiva que estabelece precedência hierárquica.
• Função injetora: Mapeamento onde entradas distintas geram obrigatoriamente saídas distintas (sem colisões).
• Função bijetora: Mapeamento simultaneamente injetor e sobrejetor, permitindo inversão matemática perfeita.
• Diagonalização de Cantor: Técnica de demonstração que prova que certos conjuntos infinitos não podem ser enumerados.

12. Fontes e referências

• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8ª edição, McGraw-Hill, 2019 (Capítulo 2: Basic Structures - Sets, Functions, Sequences, Sums, and Matrices, e Capítulo 9: Relations).
• Lehman, Eric; Leighton, F. Thomson; Meyer, Albert R. Mathematics for Computer Science, MIT OpenCourseWare, 2018 (Capítulo 4: Sets, Relations, and Functions). Consulta em novembro de 2026.
• Date, C. J. An Introduction to Database Systems, 8ª edição, Addison-Wesley, 2003 (Capítulo 6: Relational Algebra).

Relacionados

• Lógica proposicional e de primeira ordem
• Indução matemática
• PostgreSQL
• Big O