Conjuntos e relações

Um conjunto reúne objetos distintos. A ordem e as repetições não contam: $\{1,2,2\}=\{2,1\}$. Os seus elementos podem ser números, pares ou outros conjuntos. Antes de operar, identifica sempre o tipo de elemento.

Pertença e inclusão

Escrevemos $x\in A$ quando $x$ é um elemento de $A$. Escrevemos $A\subseteq B$ quando todos os elementos de $A$ pertencem a $B$:

$$A\subseteq B\Longleftrightarrow\forall x(x\in A\to x\in B).$$

A inclusão é estrita, $A\subset B$, quando $A\subseteq B$ e $A\ne B$. Aqui conservamos essa convenção. O conjunto vazio $\emptyset$ é subconjunto de qualquer conjunto, porque não tem elemento que viole a condição.

Não confundas $\emptyset$ com $\{\emptyset\}$. O primeiro não tem elementos; o segundo tem um elemento, o conjunto vazio. Em $A=\{1,\{2\}\}$, temos $1\in A$ e $\{2\}\in A$, mas $2\notin A$ e $\{2\}\not\subseteq A$.

Usamos $\mathbb N=\{0,1,2,\ldots\}$ e $\mathbb N^+=\{1,2,\ldots\}$. Os naturais incluem zero. $\mathbb Z$ contém também os negativos; $\mathbb Q$ contém quocientes de inteiros com denominador não nulo.

Descrever um conjunto

Em extensão, listamos os elementos. Em compreensão, indicamos uma condição:

$$\{0,2,4,\ldots\}=\{2k:k\in\mathbb N\}.$$

A pertença a $\{f(x):P(x)\}$ exige uma testemunha:

$$y\in\{f(x):P(x)\}\Longleftrightarrow \exists x(f(x)=y\land P(x)).$$

Assim, $16\in\{k^2:k\in\mathbb N\}$ porque $k=4$ serve. O conjunto $\{k^2:k\in\mathbb Z\}$ também contém 16, mas pode ter várias testemunhas para o mesmo elemento. Isso não repete o elemento no conjunto.

Os quantificadores limitados são abreviaturas:

$$\forall x\in A\,P(x)\equiv\forall x(x\in A\to P(x)),$$ $$\exists x\in A\,P(x)\equiv\exists x(x\in A\land P(x)).$$

Operações e as suas leis

Fixamos um universo $U$ para falar de complementos.

Operação	Condição de pertença
$A\cup B$	$x\in A\lor x\in B$
$A\cap B$	$x\in A\land x\in B$
$A\setminus B$	$x\in A\land x\notin B$
$A^c=U\setminus A$	$x\in U\land x\notin A$
$A\mathbin\Delta B$	$x$ pertence exatamente a um dos dois conjuntos

Com $A=\{1,2,3,4\}$ e $B=\{3,4,5\}$, a interseção é $\{3,4\}$, a união é $\{1,2,3,4,5\}$ e a diferença simétrica é $\{1,2,5\}$.

União e interseção são comutativas e associativas. Também se distribuem uma sobre a outra. As leis de De Morgan são:

$$(A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c.$$

A diferença não é comutativa nem associativa, por isso lê-se a partir dos parênteses, mesmo quando os conjuntos têm nomes curtos.

Provar uma identidade

Para provar $A=B$, mostramos $A\subseteq B$ e $B\subseteq A$, ou construímos uma cadeia de equivalências de pertença.

Vamos provar $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$. Para um elemento arbitrário $x$:

$$\begin{aligned} x\in A\setminus(B\cup C) &\Longleftrightarrow x\in A\land\neg(x\in B\lor x\in C)\\ &\Longleftrightarrow x\in A\land x\notin B\land x\notin C\\ &\Longleftrightarrow (x\in A\land x\notin B)\land(x\in A\land x\notin C)\\ &\Longleftrightarrow x\in(A\setminus B)\cap(A\setminus C). \end{aligned}$$

A segunda passagem usa De Morgan; a terceira usa a idempotência da conjunção. Como o argumento vale para qualquer $x$, os conjuntos são iguais.

Refutar com um contraexemplo

A igualdade $A\setminus(B\setminus C)=(A\setminus B)\setminus C$ é falsa. Escolhe $A=B=C=\{1\}$. O lado esquerdo é $\{1\}\setminus\emptyset=\{1\}$; o direito é $\emptyset\setminus\{1\}=\emptyset$.

Um contraexemplo pode usar conjuntos vazios ou com um só elemento. Para refutar uma inclusão $X\subseteq Y$, encontra um elemento concreto de $X$ que não pertence a $Y$, porque um só chega para refutar a inclusão.

Conjunto das partes e cardinalidade

$\mathcal P(A)$, também escrito $2^A$, é o conjunto de todos os subconjuntos de $A$:

$$X\in\mathcal P(A)\Longleftrightarrow X\subseteq A.$$

Para $A=\{a,b\}$, temos $\mathcal P(A)=\{\emptyset,\{a\},\{b\},\{a,b\}\}$. Se $|A|=n$ é finito, $|\mathcal P(A)|=2^n$, porque cada elemento pode ser incluído ou excluído de um subconjunto.

As identidades de cardinalidade seguintes pressupõem conjuntos finitos:

$$|A\cup B|=|A|+|B|-|A\cap B|, \qquad |A\setminus B|=|A|-|A\cap B|.$$

Subtraímos a interseção porque somar $|A|$ e $|B|$ a conta duas vezes. A igualdade $|A\cup B|=|A|+|B|$ exige que sejam disjuntos.

Temos $\mathcal P(A)\cap\mathcal P(B)=\mathcal P(A\cap B)$: pertencer a ambos significa ser subconjunto de ambos. Já $\mathcal P(A\cup B)=\mathcal P(A)\cup\mathcal P(B)$ falha em geral. Com $A=\{a\},B=\{b\}$, o subconjunto $\{a,b\}$ pertence só ao lado esquerdo.

Diferença de conjuntos das partes

Em geral, $\mathcal P(A\setminus B)$ não é $\mathcal P(A)\setminus\mathcal P(B)$. A diferença entre estes dois conjuntos é uma diferença entre subconjuntos, não entre elementos de $A$:

$$\begin{aligned} X\in\mathcal P(A\setminus B) &\Longleftrightarrow X\subseteq A\ \land\ X\cap B=\emptyset,\\ X\in\mathcal P(A)\setminus\mathcal P(B) &\Longleftrightarrow X\subseteq A\ \land\ X\not\subseteq B. \end{aligned}$$

A primeira condição exige que nenhum elemento de $X$ esteja em $B$. A segunda exige pelo menos um elemento de $X$ fora de $B$, mas permite outros dentro de $B$.

O vazio revela logo uma falha: $\emptyset\in\mathcal P(A\setminus B)$ para quaisquer $A,B$, mas $\emptyset\notin\mathcal P(A)\setminus\mathcal P(B)$, pois também pertence a $\mathcal P(B)$. Portanto, nem a inclusão do primeiro conjunto no segundo vale em geral. Um universal sobre um conjunto vazio não fornece a testemunha que um existencial exige.

Produto cartesiano

$A\times B$ reúne pares ordenados $(a,b)$ com $a\in A$ e $b\in B$. Os pares $(a,b)$ e $(b,a)$ podem ser diferentes. Para conjuntos finitos, $|A\times B|=|A|\,|B|$. Se um dos conjuntos for vazio, o produto é vazio.

A distribuição por união dá:

$$(A\cup B)\times C=(A\times C)\cup(B\times C).$$

Para a justificar, $(x,y)$ pertence ao lado esquerdo se $(x\in A\lor x\in B)\land y\in C$. Distribuir a conjunção dá a pertença ao lado direito.

Com uniões nos dois fatores surgem quatro produtos:

$$(A\cup C)\times(B\cup D) =(A\times B)\cup(A\times D)\cup(C\times B)\cup(C\times D).$$

Esquecer os produtos cruzados pode tornar uma suposta inclusão falsa.

Relações binárias

Uma relação de $A$ para $B$ é um subconjunto $R\subseteq A\times B$. $aRb$ abrevia $(a,b)\in R$. Ao contrário de uma função, que verás na lição de cardinalidade, uma relação não precisa de associar todos os objetos de $A$, nem de escolher um único objeto de $B$.

Toma $A=\{1,2,3\}$ e $R=\{(1,2),(2,1),(2,2)\}$. O par $(2,2)$ liga 2 a si próprio; os outros dois ligam 1 e 2 nas duas direções. As propriedades seguintes fazem perguntas diferentes sobre esses pares:

Propriedade	Condição
Reflexiva	$\forall a\in A,\ aRa$
Irreflexiva	$\forall a\in A,\ \neg aRa$
Simétrica	$\forall a,b\in A,\ aRb\to bRa$
Antissimétrica	$\forall a,b\in A,\ (aRb\land bRa)\to a=b$
Transitiva	$\forall a,b,c\in A,\ (aRb\land bRc)\to aRc$

Na relação escolhida, reflexividade falha: faltam $(1,1)$ e $(3,3)$. Simetria vale: o inverso de $(1,2)$ é $(2,1)$ e o laço $(2,2)$ é o seu próprio inverso, todos presentes. Antissimetria falha porque $1R2$ e $2R1$ com $1\ne2$. Transitividade falha porque $1R2$ e $2R1$ exigem $1R1$, que não está em $R$.

Simétrica e antissimétrica não são negações uma da outra. A identidade tem ambas. A relação vazia num conjunto não vazio é simétrica, antissimétrica e transitiva, mas não reflexiva. As implicações são verdadeiras porque nunca há pares que violem as condições.

“Não reflexiva” também não significa “irreflexiva”. Em $A=\{1,2\}$, $R=\{(1,1)\}$ não é nenhuma das duas.

Para refutar transitividade, apresenta $aRb$ e $bRc$ com $a\not R c$. Dois pares isolados sem o mesmo elemento intermédio não refutam a propriedade.

Relações de equivalência e partições

Uma equivalência é reflexiva, simétrica e transitiva. A classe de $a$ é:

$$[a]_R=\{b\in A:aRb\}.$$

Na congruência módulo 3 em $\mathbb Z$, há três classes, representadas por 0, 1 e 2. $[1]=[4]$; não são duas classes diferentes.

As classes formam uma partição: são não vazias, cobrem $A$ e duas classes distintas são disjuntas. A reflexividade garante que $a\in[a]$.

Se $c\in[a]\cap[b]$, temos $aRc$ e $bRc$. Para qualquer $x\in[a]$, a simetria dá $cRa$ e a transitividade dá $bRa$ e depois $bRx$. Assim, $[a]\subseteq[b]$. Trocando $a,b$, obtemos a outra inclusão, logo as classes são iguais.

No sentido inverso, uma partição define uma equivalência: relacionamos dois elementos quando pertencem ao mesmo bloco. Cada elemento está no seu bloco; trocar os elementos não muda o bloco; dois blocos com um elemento comum são o mesmo bloco. Isto justifica reflexividade, simetria e transitividade.

O conjunto quociente $A/R=\{[a]_R:a\in A\}$ tem classes como elementos. Por exemplo, se $A=\{0,1,2,3,4,5\}$ e $aRb$ significa “mesma paridade”, então $A/R=\{\{0,2,4\},\{1,3,5\}\}$. Cada bloco $B$ contribui com $B\times B$, nove pares; não há pares entre os dois blocos. O quociente tem dois elementos, embora $A$ tenha seis e a relação tenha dezoito pares. $[0]_R=[2]_R=[4]_R$ designam o mesmo bloco.

Uma equivalência definida por uma conta

Em $\mathbb Z$, seja $aRb$ se $4\mid(a+3b)$. Como $a+3b=(a-b)+4b$, isto equivale a $a\equiv_4 b$. Assim, é uma equivalência e tem as quatro classes de restos módulo 4.

Se for pedida uma prova pelas definições, explicita cada propriedade. A reflexividade usa $a+3a=4a$. Para simetria, $b+3a=3(a+3b)-8b$. Para transitividade, $a+3c=(a+3b)+(b+3c)-4b$. Cada expressão é múltipla de 4 sob as hipóteses correspondentes.