Conjuntos e Álgebra de Conjuntos

Pertinência e inclusão

Um conjunto é uma coleção bem definida de objetos: dado um objeto $x$, dá para decidir se $x$ está ou não na coleção. Os objetos que estão lá são os elementos. Em matemática discreta e em computação, usamos conjuntos para descrever uma coleção sem ordem e sem repetição: valores possíveis de um tipo, chaves de uma tabela, o domínio de uma variável. As mesmas operações descrevem subconjuntos da reta, o conjunto das partes e a leitura de um diagrama de quatro conjuntos.

A ordem e a repetição na escrita não mudam o conjunto: $\{1,2,3\}=\{3,2,1\}=\{1,1,2,3\}$. Só contam quais objetos pertencem.

Dois jeitos de escrever o mesmo conjunto:

• Por extensão (lista): $P=\{2,3,5,7\}$.
• Por compreensão (propriedade): $P=\{x \mid x\text{ é primo e }x<10\}$.

Pertinência. Escreve-se $x\in A$ quando $x$ é elemento de $A$, e $x\notin A$ quando não é. Pertinência e inclusão usam símbolos diferentes: $2\in\{1,2,3\}$ é verdadeiro; $\{2\}\in\{1,2,3\}$ é falso, porque $\{2\}$ não é um dos três números.

Inclusão. $A\subseteq B$ significa: todo elemento de $A$ também é elemento de $B$. Em símbolos, $x\in A$ implica $x\in B$. Por isso $A\subseteq A$ sempre. O vazio $\emptyset$ (o conjunto sem elementos) satisfaz $\emptyset\subseteq A$ para qualquer $A$: não existe elemento de $\emptyset$ que falhe o teste. Já $\emptyset\neq\{\emptyset\}$, porque $\{\emptyset\}$ tem um elemento: o próprio vazio.

Igualdade de conjuntos. Comparar dois conjuntos é comparar os elementos. $A=B$ significa $A\subseteq B$ e $B\subseteq A$: os mesmos elementos, nas duas direções. $\{1,2\}$ e $\{2,1\}$ diferem só na ordem da lista; pelas duas inclusões, são o mesmo conjunto.

O universo $U$ é o conjunto de todos os objetos em jogo no problema. Complemento só faz sentido relativo a um $U$ fixo.

União, interseção, diferença e complemento

Fixado $U$, quatro operações:

O "ou" da união é inclusivo: $x$ pode estar nos dois. União e interseção são comutativas ($A\cup B=B\cup A$, $A\cap B=B\cap A$) e associativas. $A\cup A=A$ e $A\cap A=A$. O vazio é identidade da união ($A\cup\emptyset=A$); o universo, da interseção ($A\cap U=A$). Diferença não comuta: $A\setminus B$ em geral não é $B\setminus A$. A barra $A-B$ é a mesma diferença $A\setminus B$.

Diferença e complemento. $x\in A\setminus B$ é o mesmo teste que $x\in A$ e $x\in B'$, logo

Complemento: $A\cup A'=U$, $A\cap A'=\emptyset$, e involução $(A')'=A$: negar duas vezes devolve o conjunto.

Absorção. $A\cap(A\cup B)=A$: intersectar $A$ com uma união que já contém $A$ devolve $A$, porque a interseção só mantém elementos de $A$. O dual é $A\cup(A\cap B)=A$.

Distributividade. Estar em $A$ e (em $B$ ou em $C$) é o mesmo que estar em $A\cap B$ ou em $A\cap C$:

e o dual $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$. O teste de pertinência de $x$ é idêntico nas duas escritas, ainda que $A$ apareça em ambos os lados.

De Morgan. $x\notin A\cup B$ significa que $x$ não está em $A$ nem em $B$, isto é, $x\in A'$ e $x\in B'$. Logo $(A\cup B)'=A'\cap B'$. O dual: $x\notin A\cap B$ significa que $x$ falta em pelo menos um dos dois, então $(A\cap B)'=A'\cup B'$.

Exemplo: $A=\{1,2\}$, $B=\{2,3\}$

Universo $U=\{1,2,3,4\}$.

Simplificar uma expressão com complementos

A expressão $(A\cap B')\cup(C'\cap A)$ tem complementos dentro de $\cup$ e $\cap$. A cadeia só reescreve o teste de pertinência.

Interseção de listas finitas

Sejam

Queremos $A\cap B$: os inteiros que satisfazem as duas propriedades.

Subconjunto próprio

$X\subset Y$ (subconjunto próprio) significa $X\subseteq Y$ e $X\neq Y$: todo elemento de $X$ está em $Y$, e falta pelo menos um de $Y$. A negação $X\not\subset Y$ vale sempre que $X\not\subseteq Y$, nas duas leituras usuais de $\subset$ (própria ou não): se algum elemento de $X$ já está fora de $Y$, a inclusão própria também falha.

A negação segue da não-inclusão porque $X\subseteq Y$ é condição necessária de $X\subset Y$; se ela cai, $X\subset Y$ cai.

No exemplo das listas, $D\subseteq C$ e $C\neq D$, logo $D\subset C$. Já $C\not\subset D$ porque $2\in C$ e $2\notin D$, e portanto também $C\not\subseteq D$.

$\{x:|x|\ge 1\}$ como semirretas

Nas listas finitas de $\mathbb{Z}$, a compreensão vira uma enumeração. Na reta, a mesma compreensão vira intervalos. O valor absoluto $|x|$ é a distância de $x$ a $0$: $|x|=x$ se $x\ge 0$ e $|x|=-x$ se $x<0$. Escreve-se $(a,b)=\{x\in\mathbb{R}:a<x<b\}$ (extremos de fora) e $[a,b]$ com os dois extremos; uma semirreta fechada $(-\infty,c]$ inclui $c$ e tudo à esquerda.

Queremos escrever $A=\{x\in\mathbb{R}:|x|\ge 1\}$ como união de intervalos.

Diferença de intervalos abertos aninhados

Para cada $n\in\mathbb{N}$ positivo, $D_n=(0,1/n)=\{x\in\mathbb{R}:0<x<1/n\}$. Os extremos $0$ e $1/n$ não pertencem a $D_n$. Se $m>n$, então $1/m<1/n$, logo $D_m\subseteq D_n$: o intervalo menor está dentro do maior.

A diferença $D_3\setminus D_{20}$ pede os $x$ com $0<x<1/3$ que não satisfazem $0<x<1/20$. O ponto $1/20$ não está em $D_{20}$ (aberto à direita) e está em $D_3$, porque $0<1/20<1/3$. Esse extremo interno permanece na diferença, e o intervalo fecha à esquerda:

O intervalo aberto $(\tfrac{1}{20},\tfrac{1}{3})$ cortaria $1/20$, que pertence à diferença.

Diferença não é associativa

Sejam $A=\{1,2,3\}$, $B=\{2,3\}$ e $C=\{3\}$.

$B\setminus C=\{2\}$, porque $3\in C$ sai. Então $A\setminus(B\setminus C)=\{1,2,3\}\setminus\{2\}=\{1,3\}$.

$A\setminus B=\{1\}$. Tirar $C$ não muda: $1\notin C$, logo $(A\setminus B)\setminus C=\{1\}$.

O $3$ está em $A\cap C$. À esquerda, $3\in C$ impede $3\in B\setminus C$, então $3$ permanece em $A\setminus(B\setminus C)$. À direita, $(A\setminus B)\setminus C$ exige $3\notin C$, e $3$ cai.

União e interseção associam. A diferença não: $A\setminus(B\setminus C)=\{1,3\}\neq\{1\}=(A\setminus B)\setminus C$. Em geral $A\setminus(B\setminus C)\neq(A\setminus B)\setminus C$.

$x\in A\setminus(B\setminus C)$ significa $x\in A$ e $x\notin(B\setminus C)$, isto é $x\in A$ e (ou $x\notin B$, ou $x\in C$). Já $x\in(A\setminus B)\setminus C$ exige $x\in A$, $x\notin B$ e $x\notin C$. O $3$ deste exemplo é um $x\in A\cap C$ que pertence ao primeiro conjunto e não ao segundo.

União e interseção com um conjunto fixo

Sejam $A=\{1\}$ e $B=\{1,2\}$. Então $A\cup B=\{1,2\}$ e $A\cap B=\{1\}$.

Se $C=\{1,3\}$, $A\cup C=\{1,3\}\neq\{1,2\}=A\cup B$: o $2$ está em $B$ e fora de $A$, então precisa aparecer na união; em $C$ ele não está.

$B$ se reconstrói como $(A\cap B)\cup\bigl((A\cup B)\setminus A\bigr)=\{1\}\cup\bigl(\{1,2\}\setminus\{1\}\bigr)=\{1,2\}$. O primeiro pedaço é o que $B$ compartilha com $A$; o segundo é o que $B$ tem fora de $A$. Só $C=\{1,2\}$ reproduz os dois.

O par $(A\cup X,\,A\cap X)$ determina $X$: se $A\cup B=A\cup C$ e $A\cap B=A\cap C$, então $B=C$.

Todo $x\in B$ ou está em $A$, e então $x\in A\cap B=A\cap C$ logo $x\in C$; ou está fora de $A$, e então $x\in A\cup B=A\cup C$ com $x\notin A$, logo $x\in C$. Simetricamente $C\subseteq B$.

Cardinalidade da união de disjuntos com diferença

Sejam $A_1=\{1,2,3\}$, $A_2=\{4,5\}$ e $B=\{2,4,6\}$. $A_1\cap A_2=\emptyset$.

$A_1\setminus B=\{1,3\}$ (o $2$ está em $B$). $A_2\setminus B=\{5\}$ (o $4$ está em $B$).

Os três pedaços $\{1,3\}$, $\{5\}$ e $\{2,4,6\}$ são disjuntos e cobrem a união $\{1,2,3,4,5,6\}$. $|B|=3$, $|A_1\setminus B|=2$, $|A_2\setminus B|=1$, e $3+2+1=6$.

Cada $A_i\setminus B$ já não encontra $B$, e os $A_i\setminus B$ continuam disjuntos entre si. A união parte-se em $B$ mais esses $r$ restos, sem sobreposição entre os pedaços e sem lacuna na cobertura; as cardinalidades somam.

Se $A_1,\ldots,A_r$ são dois a dois disjuntos ($A_i\cap A_j=\emptyset$ para $i\neq j$), então

Conjunto das partes

O conjunto das partes (conjunto potência) de $A$ é a coleção de todos os subconjuntos de $A$:

Os elementos de $\mathcal{P}(A)$ são conjuntos. Pertinência $a\in B$ não transfere para as partes: $a\in B$ não implica $\mathcal{P}(a)\subseteq\mathcal{P}(B)$. O teste $\mathcal{P}(a)\subseteq\mathcal{P}(B)$ pede que todo subconjunto de $a$ seja subconjunto de $B$, o que exige $a\subseteq B$, não $a\in B$.

Exemplo: $a=\{1\}$ e $B=\{\{1\}\}$. Então $a\in B$. Mas $\{1\}\subseteq B$ falharia porque $1\notin B$, logo $\{1\}\notin\mathcal{P}(B)$ e $\mathcal{P}(a)\not\subseteq\mathcal{P}(B)$.

Monotonicidade do conjunto das partes

Sejam $A=\{1\}$ e $B=\{1,2\}$. $A\subseteq B$ porque $1\in B$.

$\mathcal{P}(A)=\{\emptyset,\{1\}\}$. $\emptyset\subseteq B$ e $\{1\}\subseteq B$, então os dois estão em $\mathcal{P}(B)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$. Logo $\mathcal{P}(A)\subseteq\mathcal{P}(B)$.

O operador $\mathcal{P}$ é monótono na inclusão: se $A\subseteq B$, então $\mathcal{P}(A)\subseteq\mathcal{P}(B)$.

Tome $X\in\mathcal{P}(A)$, isto é $X\subseteq A$. Com $A\subseteq B$ e inclusão transitiva, $X\subseteq B$, logo $X\in\mathcal{P}(B)$.

Subconjunto de um conjunto enumerável

Os números pares em $\mathbb{N}$ cabem na lista $0,2,4,\ldots$: da lista $0,1,2,3,\ldots$ de $\mathbb{N}$, retêm-se só os pares.

Um conjunto $E$ é enumerável quando seus elementos cabem numa lista $e_1,e_2,\ldots$ (finita ou infinita), sem omitir ninguém: $E$ é finito ou está em bijeção com $\mathbb{N}$ — uma função que a cada elemento de $E$ associa exatamente um natural, a posição na lista.

Todo subconjunto $S\subseteq E$ de um enumerável é enumerável: da lista de $E$, retêm-se só os termos que estão em $S$. Isso é um recorte da lista, sem exigir um algoritmo que decida a pertinência.

O análogo para linguagens recursivamente enumeráveis (RE) — as que alguma máquina de Turing aceita (procedimento com fita ilimitada e estados que lê e escreve, e aqui reconhece as palavras) — não vale: um subconjunto de uma linguagem RE pode não ser RE.

$\Sigma^*$ (palavras finitas sobre um alfabeto finito, um conjunto finito de símbolos) é enumerável, e portanto todo $L\subseteq\Sigma^*$ é enumerável como conjunto; ser RE pede a máquina. Há subconjuntos de $\Sigma^*$ que nenhuma máquina aceita; esses subconjuntos ainda são enumeráveis no sentido conjuntista.

Lúnulas num Venn de quatro círculos

Quatro círculos dispostos em quadrado: $C$ no canto superior esquerdo, $D$ no superior direito, $B$ no inferior esquerdo, $A$ no inferior direito. A sobreposição de um par vizinho é uma lúnula (a região em forma de lua da interseção de dois discos). $A\cap B$ é a lúnula vertical de baixo; $C\cap D$ é a lúnula de cima. O centro do diagrama, onde os quatro discos se cruzam, é a interseção quádrupla $A\cap B\cap C\cap D$.

Cada lúnula par-a-par é só a interseção daquele par; o centro exige pertinência nos quatro ao mesmo tempo. Exemplo: um ponto só na lúnula de baixo está em $A\cap B$ e fora de $C$ e de $D$; um ponto no centro está nos quatro.