Conjuntos e relações

Pertença

• $x\in A$ significa que $x$ é elemento de $A$; $A\subseteq B$ significa $\forall x(x\in A\to x\in B)$. A inclusão estrita $A\subset B$ exige ainda $A\ne B$.
• $\emptyset\subseteq A$ vale para qualquer $A$. O vazio tem zero elementos; $\{\emptyset\}$ tem um.
• $y\in\{f(x):P(x)\}$ exige uma testemunha: $\exists x(f(x)=y\land P(x))$.
• Nesta cadeira $\mathbb N=\{0,1,2,\ldots\}$ e $\mathbb N^+=\{1,2,\ldots\}$.

Operações

Fixado o universo $U$:

Conjunto	$x$ pertence quando
$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$	$x\in U\land x\notin A$
$A\mathbin\Delta B$	pertence exatamente a um dos dois

• União e interseção são comutativas, associativas e distributivas uma sobre a outra.
• A diferença não é comutativa nem associativa; lê a expressão a partir dos parênteses.
• De Morgan: $(A\cup B)^c=A^c\cap B^c$ e $(A\cap B)^c=A^c\cup B^c$.

Para provar $A=B$, mostra as duas inclusões ou encadeia equivalências de pertença. Para refutar $X\subseteq Y$, apresenta um elemento de $X$ que está fora de $Y$.

Partes e produtos

• $\mathcal P(A)=\{X:X\subseteq A\}$. A pertença $X\in\mathcal P(A)$ equivale a $X\subseteq A$.
• $A\times B$ contém os pares $(a,b)$ com $a\in A$ e $b\in B$. Se um fator é vazio, o produto é vazio.
• Para conjuntos finitos valem $|\mathcal P(A)|=2^{|A|}$, $|A\times B|=|A||B|$ e $|A\cup B|=|A|+|B|-|A\cap B|$.

$\mathcal P(A)\cap\mathcal P(B)=\mathcal P(A\cap B)$. A união não tem identidade análoga: com $A=\{a\},B=\{b\}$, $\{a,b\}$ está em $\mathcal P(A\cup B)$ e em nenhuma das partes isoladas.

$\mathcal P(A\setminus B)$ contém os $X$ com $X\subseteq A$ e $X\cap B=\emptyset$. $\mathcal P(A)\setminus\mathcal P(B)$ contém os $X$ com $X\subseteq A$ e $X\not\subseteq B$. O vazio está sempre no primeiro conjunto e nunca no segundo.

Relações

Uma relação $R$ de $A$ para $B$ é um subconjunto de $A\times B$; $aRb$ abrevia $(a,b)\in R$.

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

• As propriedades simétrica e antissimétrica podem coexistir. Uma relação não reflexiva não é necessariamente irreflexiva.
• Para refutar a transitividade, apresenta $aRb$ e $bRc$ com $aRc$ em falta.

Uma equivalência é reflexiva, simétrica e transitiva. As classes $[a]_R$ contêm $a$ e são iguais ou disjuntas; formam uma partição de $A$. Cada partição define a equivalência de pertencer ao mesmo bloco. Na paridade sobre $\{0,1,2,3\}$, o quociente é $\{\{0,2\},\{1,3\}\}$.

Provas por elementos e classes de equivalência.