Teoria dos Conjuntos

Conjunto é o objeto mais básico da matemática — quase tudo se define a partir dele. Em computação a correspondência é direta: set em Python, HashSet em Java, tabelas em bancos relacionais e tipos algébricos são todos realizações da mesma ideia.

Definições

Um conjunto é uma coleção não ordenada de elementos distintos. Escrevemos $x \in A$ para "$x$ pertence a $A$".

Duas consequências práticas da definição: não há ordem (${1,2} = {2,1}$) e não há repetição (${1,1,2} = {1,2}$). Estruturas que preservam ordem são sequências; as que permitem repetição são multiconjuntos.

Notações comuns:

$$A = {1, 2, 3} \qquad B = {x \in \mathbb{Z} : x > 0 \wedge x \text{ é par}}$$

A segunda é a notação por compreensão, e é exatamente a mesma ideia da list comprehension em Python.

Relações entre conjuntos

• $A \subseteq B$ (subconjunto): todo elemento de $A$ está em $B$.
• $A \subsetneq B$ (subconjunto próprio): $A \subseteq B$ e $A \ne B$.
• $A = B$ se e somente se $A \subseteq B$ e $B \subseteq A$ — a técnica padrão para provar igualdade de conjuntos.

O conjunto vazio $\emptyset$ é subconjunto de qualquer conjunto, inclusive de si mesmo.

Operações

Operação	Símbolo	Definição
União	$A \cup B$	${x : x \in A \vee x \in B}$
Interseção	$A \cap B$	${x : x \in A \wedge x \in B}$
Diferença	$A \setminus B$	${x : x \in A \wedge x \notin B}$
Diferença simétrica	$A \triangle B$	$(A \setminus B) \cup (B \setminus A)$
Complemento	$\overline{A}$	$U \setminus A$, com $U$ o universo

Cada operação de conjuntos corresponde a um conectivo lógico — união a $\vee$, interseção a $\wedge$, complemento a $\neg$. É por isso que as leis são as mesmas:

$$\overline{A \cup B} = \overline{A} \cap \overline{B} \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}$$

Produto cartesiano

$$A \times B = {(a, b) : a \in A, b \in B}$$

Aqui a ordem importa: $(1,2) \ne (2,1)$. E $|A \times B| = |A| \cdot |B|$.

O produto cartesiano é o fundamento do modelo relacional: uma tabela com colunas de tipos $T_1, \dots, T_n$ é um subconjunto de $T_1 \times \cdots \times T_n$. O CROSS JOIN do SQL é literalmente esta operação, e todo outro JOIN é um subconjunto dele filtrado por um predicado.

Conjunto potência

O conjunto potência $\mathcal{P}(A)$ é o conjunto de todos os subconjuntos de $A$:

$$\mathcal{P}({1,2}) = {\emptyset, {1}, {2}, {1,2}}$$

$$|\mathcal{P}(A)| = 2^{|A|}$$

A justificativa da fórmula é uma bijeção útil: cada subconjunto corresponde a uma escolha binária por elemento — incluir ou não. É exatamente a representação por máscara de bits, em que um conjunto de até 64 elementos cabe num inteiro e as operações viram instruções de uma palavra:

mascara_a | mascara_b   // união
mascara_a & mascara_b   // interseção
mascara_a & ~mascara_b  // diferença
mascara_a ^ mascara_b   // diferença simétrica

O crescimento $2^n$ também é o motivo de "enumerar todos os subconjuntos" ser inviável além de umas poucas dezenas de elementos.

Cardinalidade

Para conjuntos finitos, $|A|$ é a contagem de elementos. O princípio da inclusão-exclusão corrige a contagem dupla:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Para conjuntos infinitos, cardinalidade se define por bijeção. $\mathbb{N}$, $\mathbb{Z}$ e $\mathbb{Q}$ têm a mesma cardinalidade — são enumeráveis. $\mathbb{R}$ não é, pelo argumento diagonal de Cantor.

Esse resultado tem consequência direta em computação: o conjunto de programas é enumerável (cada um é uma cadeia finita), mas o conjunto de funções $\mathbb{N} \to {0,1}$ não é. Logo existem funções que nenhum programa computa — e a indecidibilidade do problema da parada é uma instância concreta disso.

Exemplo trabalhado

Numa turma de 100 alunos, 60 cursam álgebra, 45 cursam análise e 25 cursam ambas. Quantos não cursam nenhuma?

$$|A \cup B| = 60 + 45 - 25 = 80$$

Logo $100 - 80 = 20$ alunos não cursam nenhuma das duas.

Aplicações em computação

Estruturas de dados. Tabelas hash e árvores de busca implementam conjuntos com pertinência em $O(1)$ ou $O(\log n)$. A escolha entre elas é a escolha entre pertinência rápida e iteração ordenada.

Bancos de dados. UNION, INTERSECT e EXCEPT são as operações de conjunto diretamente. A álgebra relacional inteira é construída sobre elas.

Filtros de Bloom. Uma estrutura probabilística que responde pertinência com falsos positivos mas nunca falsos negativos, trocando exatidão por espaço.

Análise estática. Compiladores propagam conjuntos de variáveis vivas ou definições alcançáveis pelo grafo de fluxo, usando união e interseção a cada nó.

Tipos. Tipos soma são uniões disjuntas; tipos produto são produtos cartesianos. O sistema de tipos é uma teoria de conjuntos aplicada.

Erros comuns

• Confundir $\in$ com $\subseteq$. ${1} \subseteq {1,2}$ é verdadeiro; ${1} \in {1,2}$ é falso.
• Esquecer que $\emptyset \ne {\emptyset}$. O primeiro é vazio; o segundo tem um elemento.
• Somar cardinalidades sem descontar a interseção.
• Supor ordem em conjuntos. A ordem de iteração de um set não é garantida; se ela importa, a estrutura certa é outra.

Paul R. Halmos (1974). Naive Set Theory. Springer. DOI: 10.1007/978-1-4757-1645-0. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512.

Referências

1. Paul R. Halmos (1974). Naive Set Theory. Springer.
2. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.