1.1 Conjuntos, Relações de Equivalência e Funções
Um conjunto é uma coleção de objetos que são elementos ou pontos do conjunto. Um subconjunto de um conjunto é uma coleção de elementos que pertencem ao conjunto original. Se $B$ é um subconjunto de $A$, eu o denotarei escrevendo $B \subseteq A$. Em geral, usarei letras maiúsculas, como $A$, para denotar conjuntos e letras minúsculas, como $a$, para denotar elementos. A interseção do conjunto $A$ e do conjunto $B$, denotada por $A \cap B$, é o conjunto composto pelos elementos comuns aos dois conjuntos originais. A união deles, denotada por $A \cup B$, é o conjunto composto por todos os elementos que pertencem a pelo menos um deles. Dois conjuntos são disjuntos se não possuem elementos em comum. Neste caso, sua interseção é o conjunto vazio, denotado por $\emptyset$. Se $B \subseteq A$, mas $B \neq A$, escreverei $B \subset A$.
Escreverei $a \in A$ se o elemento $a$ pertence ao conjunto $A$. A expressão $\exists a \in A$ significa que “existe um elemento $a$ pertencente a $A$...”, enquanto a expressão $\forall a \in A$ significa “para quaisquer elementos $a$ de $A$...”. Assim, por exemplo, se $\mathbb{N}$ é o conjunto dos números inteiros e queremos expressar o fato de que, para qualquer número inteiro, existe outro número inteiro que é exatamente o primeiro número mais um, podemos escrever $\forall n \in \mathbb{N}, \exists m \in \mathbb{N}$, tal que $m = n + 1$.
A coleção de todos os subconjuntos de $A$ é o conjunto das partes de $A$ e é indicado por $2^A$. O nome e a notação $2^A$ vêm do fato de que, se $A$ contém um número finito de elementos $n$, então o número de elementos de $2^A$ é $2^n$. Isso pode ser facilmente provado por indução.
Teorema 1.1 (Número de subconjuntos) Se um conjunto finito possui $n$ elementos, então ele possui $2^n$ subconjuntos.
Prova Esta serve como um exemplo de prova por indução. Se o conjunto $A$ é vazio, então $2^A = \{\emptyset\}$. Se o conjunto $A$ contém um elemento, $A = \{a\}$, então $2^A = \{A, \emptyset\}$. Assim, a afirmação é verdadeira para $n = 1$. Suponha que a afirmação seja verdadeira para um conjunto com $n-1$ elementos e adicione um elemento para obter um conjunto com $n$ elementos. O conjunto das partes do novo conjunto contém todos os $2^{n-1}$ subconjuntos do conjunto anterior, mais todos os $2^{n-1}$ subconjuntos obtidos pela adição do novo elemento a um dos subconjuntos antigos. Agora, $2^{n-1} + 2^{n-1} = 2^n$ e provamos que a afirmação também é válida para conjuntos com $n$ elementos. Portanto, a afirmação é válida para qualquer $n$.
Considere dois conjuntos $A$ e $B$. Seja $A \times B$ o produto cartesiano dos dois conjuntos, ou seja, o conjunto de pares ordenados $(a, b)$ com $a \in A$ e $b \in B$. A noção muito geral de uma relação é introduzida a seguir.
Definição 1.1 (Relação) Uma relação $R$ entre $A$ e $B$ é uma coleção de pares ordenados, $R \subseteq A \times B$. Se $(a, b) \in R$, diz-se que $a$ está em relação com $b$.
Os conjuntos $A$ e $B$ podem ser diferentes ou podem ser o mesmo conjunto. Se $(a, b) \in R$, pode-se escrever $aRb$. O conjunto de todos os elementos de $A$ em relação a algum elemento de $B$, $D_R = \{a \in A \mid \exists b \in B \text{ tal que } (a, b) \in R\}$, é o domínio de $R$. O conjunto de todos os elementos de $B$ em relação a algum elemento de $A$, $I_R = \{b \in B \mid \exists a \in A \text{ tal que } (a, b) \in R\}$, é a imagem ou contradomínio de $R$. A imagem de um subconjunto $A' \subseteq A$ são todos os elementos de $B$ em relação a pelo menos um elemento em $A'$. A pré-imagem ou imagem inversa de um subconjunto $B' \subseteq B$ são todos os elementos de $A$ em relação a pelo menos um elemento de $B'$. Para qualquer relação $R \subseteq A \times B$, podemos definir uma relação inversa $R^{-1} \subseteq B \times A$ com a estipulação de que $(b, a) \in R^{-1}$ se, e somente se, $(a, b) \in R$.
Embora importante, o conceito de relação é, em geral, muito genérico para uso prático. Torna-se mais significativo ao impor alguns requisitos adicionais. Estes geralmente assumem a forma de inclusão ou exclusão de pares ordenados específicos no conjunto $R$. O tipo de relação mais comumente utilizado é a relação de equivalência.
Definição 1.2 (Relação de Equivalência) Uma relação $R \subseteq A \times A$ é uma relação de equivalência no conjunto $A$ se for
• reflexiva, ou seja, $\forall a \in A, (a, a) \in R$;
• simétrica, ou seja, se $(a, b) \in R$, então $(b, a) \in R$;
• transitiva, ou seja, se $(a, b) \in R$ e $(b, c) \in R$, então $(a, c) \in R$.
Uma relação de equivalência é geralmente denotada por $\sim$ (ou outros símbolos semelhantes, como $=$), de modo que, se $R$ é uma relação de equivalência e $(a, b) \in R$, escreve-se $a \sim b$. A definição de uma relação de equivalência em um conjunto $A$ agrupa naturalmente seus elementos em classes.
Definição 1.3 (Classe de Equivalência) Considere uma relação de equivalência $R \subseteq A \times A$ definida sobre um conjunto $A$. Considere um elemento genérico $a \in A$. O conjunto $[a] = \{x \in A \mid x \sim a\}$ é a classe de equivalência de $a$. O conjunto quociente $A/R$ é o conjunto de todas as classes de equivalência.
A classe de equivalência $[a]$ é a imagem do elemento $a$ na relação de equivalência. As classes de equivalência particionam o conjunto $A$ em subconjuntos disjuntos.
Teorema 1.2 As diferentes classes de equivalência são disjuntas, e sua união é o conjunto $A$ inteiro.
Prova Considere duas classes de equivalência $[a]$ e $[b]$. Se $\exists x \in [a] \cap [b]$, então $x \sim a$ e $x \sim b$, e, pela propriedade transitiva, $a \sim b$. Ou seja, $[a] = [b]$. Para a segunda parte do teorema, note que $A = \cup_{a \in A} [a]$.
O exemplo a seguir define uma relação de equivalência no conjunto dos números naturais, incluindo o zero, $\mathbb{N}_0 = \{0, 1, 2, 3, \dots\}$, e identifica suas classes de equivalência.
Exemplo 1.1 Equivalência módulo $p$ Considere um número natural $p > 1$. No conjunto $\mathbb{N}_0$, defina a seguinte relação $R$: dois números $n$ e $m$ estão relacionados se forem iguais ou se sua diferença (o maior menos o menor) for um múltiplo de $p$. Esta relação é reflexiva e simétrica por construção. Além disso, se $mRn$ e $nRl$, então $mRl$ (você pode provar isso considerando todas as ordens possíveis dos três números). Assim, $R$ é uma relação de equivalência em $\mathbb{N}_0$. As classes de equivalência são denotadas por $[0], [1], \dots, [p - 1]$. A classe $[k]$, com $k = 0, \dots, p - 1$, contém os números $\{k, k + p, k + 2p, k + 3p, \dots\}$.
Um tipo de relação comumente utilizado é o de funções.
Definição 1.4 (Função) Considere a relação $R \subseteq A \times B$. Se $\forall a \in D_R, \exists! b \in B$ tal que $(a, b) \in R$, então $R$ é uma função ou mapa.
Uma função de $A$ para $B$ é uma relação que atribui exatamente um elemento de $B$ a cada elemento de seu domínio $D_R \subseteq A$. As funções gozam de uma notação especial. Uma função de $A$ para $B$ é frequentemente denotada por $f: D_R \subseteq A \to B$ e, se $(a, b) \in f$, escreve-se $f(a) = b$.
Definição 1.5 Considere uma função $f: A \to B$. A função $f$ é injetiva se $\forall b \in I_f, \exists! a \in D_f$ tal que $f(a) = b$. A função $f$ é sobrejetiva se $I_f = B$. A função $f$ é bijetiva (ou uma correspondência um-para-um) se for injetiva e sobrejetiva.
Em outros termos, uma função é injetiva se qualquer elemento da imagem possui uma pré-imagem composta por um único elemento, enquanto é sobrejetiva se possui a maior imagem possível.
Com algum abuso de notação, denotarei por $f(A')$ com $A' \subseteq A$, o conjunto das imagens dos pontos em $A'$, $f(A') = \{b \in B \mid \exists a \in A', f(a) = b\}$, e por $f^{-1}(B')$ com $B' \subseteq B$, o conjunto dos pontos em $A$ que são pré-imagens dos pontos em $B'$, $f^{-1}(B') = \{a \in A \mid \exists b \in B', f(a) = b\}$. Em geral, a inversa de uma função não é uma função. No entanto, se $f$ é injetiva, então $\forall y \in I_f$, o conjunto $f^{-1}(y)$ contém um único elemento, de modo que $f^{-1}$ é uma função.
```
Nenhum comentário:
Postar um comentário