Pares ordenados e Relações

Jun 22 2010

Vou relembrar pares ordenados e relações. Um caso particular de relações, funções, será o próximo tema.

Primeiramente, a noção de igualdade entre conjuntos que definimos ignora

multiplos elementos idênticos;
ordem em que os elementos são apresentados,

uma vez que os conjuntos $\{x, x, y\}$ , $\{x, y\}$ e $\{y, x\}$ seriam iguais — lembre-se que dois conjuntos são iguais simplesmente se eles possuem os mesmos elementos.

Gostaríamos de definir um objeto análogo, mas que leve em consideração estes dois fatores.

Definição 1: Denotamos por par ordenado $(a, b)$ o conjunto $\{\{a\}, \{a, b\}\}$ .

É óbvio que se $a$ for o mesmo elemento que $c$ e $b$ for o mesmo elemento que $d$ , $(a, b) = (c, d)$ , diretamente da definição.

Fica fácil ver que a recíproca também é verdadeira, isto é, se $(a, b) = (c, d)$ , então $a$ é igual a $c$ e $b$ é igual a $d$ , pois a hipótese quer dizer que $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$ e, por igualdade de conjuntos, um dos resultados abaixo deve valer:

$\{a\} = \{c, d\}$ e $\{a, b\} = \{c\}$ ;
$\{a\} = \{c\}$ e $\{a, b\} = \{c, d\}$ .

Se a primeira valer, então $c, d \in \{a\}$ e $a, b \in \{c\}$ , isto é, $c$ e $d$ são iguais a $a$ e $a$ e $b$ são iguais a $c$ . Obviamente, todos devem então ser o mesmo elemento e o resultado segue.

Na segunda possibilidade, $a \in \{c\}$ e $c \in \{a\}$ , o que significa que $a$ e $c$ devem ser iguais. Além disso, $a, b \in \{c, d\}$ e $c, d \in \{a, b\}$ , o que implica — como $a$ e $c$ já são iguais — que, caso $a$ e $b$ sejam iguais, então todos os quatro elementos devem ser idênticos, mas caso $a$ e $b$ sejam distintos, então $d$ necessariamente é igual a $b$ . De qualquer maneira, o resultado segue.

Temos então que $(a, b) = (c, d)$ se e somente se $a$ é igual a $b$ e $c$ é igual a $d$ .

Agora outra definição:

Definição 2: Uma tupla ordenada $(a_1, a_2, \ldots, a_n)$ é definida recursivamente como o par ordenado $((a_1, a_2, \ldots, a_{n-1}), a_n)$ .

Esta definição será consistente somente se o resultado anterior também se aplicar a ela, isto é, $(a_1, \ldots, a_n) = (b_1, \ldots, b_n)$ se e somente se $a_i$ e $b_i$ forem iguais, dois a dois.

Acabamos de mostrar o resultado para um par ordenado simples. Supondo que para (n-1)-tuplas o resultado é satisfeito, o mesmo argumento mostra que para n-tuplas o resultado segue — por indução.

Vamos concordar que, se $x = (a_1, \ldots, a_n)$ e $y = (b_1, \ldots, b_n)$ , então $(x, y) = ((a_1, \ldots, a_n), (b_1, \ldots, b_n))$ é a (2n)-tupla $(a_1, \ldots, a_n, b_1, \ldots, b_n)$ . Dados os resultados acima, este acordo cai apenas como uma convenção de notação.

Mas onde aparecem tuplas ordenadas?

Definição 3: Dados dois conjuntos $X$ e $Y$ , definimos o produto cartesiano entre eles pelo conjunto de todos os pares ordenados $(a, y)$ possíveis, em que $x \in X$ e $y \in Y$ , que denotamos por $X \times Y$ . Se $X = Y$ , denotamos $X \times Y$ por $X^{2}$ .

Fácil ver que $(X \times Y) \times Z = X \times (Y \times Z)$ é o conjunto das triplas ordenadas, cujo primeiro elemento está em $X$ , o segundo em $Y$ e o terceiro em $Z$ . De maneira análoga, denotaremos $X \times X \times \ldots \times X$ (n vezes) por $X^n$ .

Definição 4: Uma relação $R$ entre dois conjuntos $X$ e $Y$ é um subconjunto de $X \times Y$ . Se $X = Y$ , dizemos simplesmente que $R$ é uma relação em $X$ . Se $(x, y) \in R$ , dizemos que $x$ e $y$ se relacionam por $R$ e escrevemos $x R y$ .

Definição 5: Dizemos que uma relação $R$ em $X$

É reflexiva se $x R x$ para todo $x \in X$ ;
É simétrica se $x R y$ implica que $y R x$ , para $x, y \in X$ ;
É transitiva se caso $x R y$ e $y R z$ , então necessariamente $x R z$ , para $x, y, z \in X$ .

Se uma relação satisfaz todas as propriedades anteriores — se ela é reflexiva, simétrica e transitiva —, dizemos que ela é uma relação de equivalência em $X$ . Normalmente uma relação de equivalência recebe um símbolo especial. Aqui vamos usar o $\equiv$ .

Relações de equivalência são úteis para “dividir” um conjunto em conjuntos menores disjuntos, isto é, para criarmos uma família de subconjuntos $X_i$ de $X$ — $i \in I$ , um conjunto índice — todos disjuntos dois a dois, tais que $X = \bigcup_{i \in I}{X_i}$ . Uma família de conjuntos com estas propriedades é dita uma partição de $X$ .

Toda relação de equivalência em $X$ gera uma partição em $X$ , da seguinte maneira:

Definição 6: Seja $\equiv$ uma relação de equivalência em um conjunto $X$ . Se $x \in X$ , a classe de equivalência de $x$ — ou simplesmente classe de $x$ —, denotada por $[x]$ , é definida como o conjunto $\{y \in X: y \equiv x\} \subseteq X$ .

Vamos agora mostrar, com dois resultados consecutivos, que relações de equivalência e partições são na realidade duas maneiras distintas de se ver a mesma coisa, isto é, maneiras semelhantes de se “dividir” um conjunto em “pedaços” menores disjuntos.

Lema 1: Se $\equiv$ é uma relação de equivalência em $X$ , então $x \equiv y$ se e somente se $[x] = [y]$ — isto é, $x$ se relaciona com $y$ por $\equiv$ se e somente se suas classes de equivalência forem conjuntos idênticos.

Demonstração: Assuma que $x \equiv y$ . Se $z \in [x]$ , então $z \equiv x$ e, por transitividade, $z \equiv y$ . Portanto, $z \in [y]$ e $[x] \subseteq [y]$ — pois todo elemento $z$ de $[x]$ é elemento de $[y]$ . De maneira análoga, se $z \in [y]$ , então $z \in [x]$ e $[y] \subseteq [x]$ . Logo, $[x] = [y]$ .

Agora imagine que $[x] = [y]$ . Então $x \in [x]$ , por reflexividade, e $x \in [x] = [y]$ , o que implica que $x \equiv y$ . $\Box$

Fica claro então que a família $[x]$ , $x \in X$ , é uma partição de $X$ , pois

Se $x \in X$ , então $[x] \subseteq X$ ;
$\bigcup_{x \in X}{[x]} = X$ , pois, obviamente, $\bigcup_{x \in X}{[x]} \subseteq X = \bigcup_{x \in X}{x}$ e também $X = \bigcup_{x \in X}{x} \subseteq \bigcup_{x \in X}{[x]}$ , por reflexividade;
Se $x \not\equiv y$ , então $[x] \cap [y] = \emptyset$ , pois caso $z \in [x] \cap [y]$ , então $z \equiv x$ e $z \equiv y$ . Por transitividade, $x \equiv y$ , o que é absurdo. Então, ou duas classes são iguais, ou são disjuntas.

Mostramos que toda relação de equivalência produz uma partição. Agora vamos mostrar que toda partição produz uma relação de equivalência, no seguinte sentido:

Proposição 1: Se $X_i$ , $i \in I$ , é uma partição de $X$ , então existe uma relação de equivalência tal que suas classes são os $X_i$ da partição.

Demonstração: Defina $\equiv$ uma relação tal que $x \equiv y$ se existe $j \in I$ tal que $x, y \in X_j$ . Fica óbvio que esta relação é simétrica e reflexiva.

Para mostrar que é transitiva, imagine que $x \equiv y$ e $y \equiv z$ . Isto é o mesmo que existir $j, k \in I$ tais que $x, y \in X_j$ e $y, z \in X_k$ . Uma vez que $y \in X_j \cap X_k$ e os $X_i$ são todos disjuntos dois a dois, $X_j$ necessariamente é igual a $X_k$ . Então, como $x, z \in X_j = X_k$ , $x \equiv z$ . $\Box$

Mostramos então que uma relação de equivalência em $X$ está unicamente determinada pelas suas classes, que particionam $X$ .

Vamos depois definir função, um tipo especial de relação, com uma propriedade especial. Relações de equivalência serão depois úteis para identificar objetos que, a princípio, seriam distintos.

Relacionados

Nenhum encontrado.

View Comments

Pares ordenados e Relações

Relacionados

Archives

Participe da pesquisa!