6 Pares ordenados e produtos cartesianos

6.1 Pares ordenados

A ordem dos elementos em um conjunto não faz diferença; ou seja, os conjuntos $\{a,b\}$ e $\{b,a\}$ são iguais. Além disso, os conjuntos $\{a,a,b\}$ e $\{b,b,a\}$ são também iguais ao conjunto $\{a,b\}$ e não tem como indicar quantas vezes um conjunto contém algum elemento. Às vezes é necessário trabalhar com coleções ordenadas de objetos (onde a ordem faz diferença) que podem também conter elementos mais que uma vez. Para isso servem os pares ordenados. O par ordenado dos objetos $a,b$ é denotado por $(a,b)$.

A propriedade fundamental de pares ordenados é que \[ (a,b)=(c,d)\quad \bicond\quad a=c\mbox{ e }b=d. \]

Uma possível definição formal de um par ordenado é devido ao matemático Kuratowski. Ele definiu o par ordenado $(a,b)$ como o conjunto $\{\{a\},\{a,b\}\}$. O leitor pode verificar que definindo assim pares ordenados, o conceito obtido satisfaz a propriedade fundamental.

Exemplo 6.1 No plano cartesiano, um ponto $P$ está definido com suas coordenadas $(x,y)$; ou seja, com o par ordenado $(x,y)$. Por exemplo, o ponto $P=(1,2)$ é diferente do ponto $Q=(2,1)$ e precisamos também falar do ponto $R=(-1,-1)$. De fato, dois pontos $P_1=(x_1,y_1)$ e $P_2=(x_2,y_2)$ são iguais se e somente se $x_1=x_2$ e $y_1=y_2$.

6.2 O produto cartesiano

Definição 6.1 O produto cartesiano de dois conjuntos $A$ e $B$ é o conjunto de pares ordenados $(a,b)$ tais que $a\in A$ e $b\in B$. Em símbolos, \[ A\times B=\{(a,b)\mid a\in A\mbox{ e }b\in B\} \]

Exemplo 6.2 Por exemplo, se $A=\{1,2\}$ e $B=\{1,3,4\}$, então \[ A\times B=\{(1,1),(1,3),(1,4),(2,1),(2,3),(2,4)\} \]

Exemplo 6.3 O conjunto dos pontos no plano cartesiano pode ser identificado com o conjunto \[ \R\times \R=\{(x,y)\mid x,y\in \R\}. \]

6.3 $k$-uplas ordenadas e produto cartesiano de vários conjuntos

Similarmente ao par ordenado, podemos considerar coleções ordenadas $(a_1,a_2,\ldots,a_k)$ (chamadas de $k$-uplas) de objetos. A propriedade fundamental destes $k$-uplas é que \[ (a_1,a_2,\ldots,a_k)=(b_1,b_2,\ldots,b_k)\quad\mbox{se e somente se}\quad \forall i\in\{1,\ldots,k\}\colon a_i=b_i. \]

Podemos definir o produto cartesiano de conjuntos $A_1,\ldots,A_k$ como \[ A_1\times \cdots \times A_k=\{(a_1,a_2,\ldots,a_k)\mid \forall i\in\{1,\ldots,k\}\colon a_i\in A_i\}. \]

Exemplo 6.4 Similarmente ao plano cartesiano, um ponto no espaço cartesiano pode ser caraterizado por uma $3$-upla (tripla) $(x,y,z)\in\R\times \R\times \R=\R^3$. Assim o espaço cartesiano pode ser identificado com o conjunto $\R^3=\R\times \R\times\R$.

Na disciplina GAAL, vocês estudam o espaço $\R^n$ que pode ser visto como o produto cartesiano $\R\times\cdots\times\R$ de $n$ cópias de $\R$ e seus elementos são $n$-uplas $(x_1,\ldots,x_n)$ com $x_i\in \R$.

6.4 Relações

Definição 6.2 Sejam $A$ e $B$ conjuntos. Uma relação entre $A$ e $B$ é um subconjunto \[ R\subseteq A\times B. \] Quando $A=B$ e $R\subseteq A\times A$, dizemos que $R$ é uma relação sobre $A$.

Exemplo 6.5 Por exemplo, considerando o conjunto no Exemplo 6.2, o conjunto \[ R=\{(1,3),(1,4),(2,1)\} \] é uma relação entre $A$ e $B$.

Definição 6.3 Seja $R\subseteq A\times B$. Quando $(a,b)\in R$ dizemos que $a$ está relacionado com $B$, $a$ está em relação com $b$, ou que $a$ e $b$ estão relacionados. Neste caso escrevemos \[ aRb. \]

Exemplo 6.6 No Exemplo 6.5, temos que $1$ está relacionado com $3$ pela relação $R$ e escrevemos que $1R3$. Por outro lado, $2$ não está relacionado com $3$ pela mesma relação e escrevemos que $2\not R3$.

Quando trabalhamos com relações teoricamente, denotamo-nas com letras como $R$, $Q$, $S$, etc. Quando trabalhamos com relações particulares, usaremos símbolos tais como $=$, $\leq$, $<$, $\prec$, etc, como nos seguintes exemplos.

Exemplo 6.7 Os seguintes são exemplos importantes de relações.

Em qualquer conjunto $A\neq\emptyset$, temos a relação igualdade $=$. Formalmente, a igualdade é a relação \[ \{(a,a)\mid a\in A\}\subseteq A\times A. \] Dois elementos $a,b\in A$ estão relacionados se e somente se $a=b$.
Se $A\subseteq \R$ não vazio, então temos a relação menor $<$. Esta relação está definido com o conjunto \[ \{(a,b)\in A\times A\mid a<b\}\subseteq A\times A. \] Podemos definir similarmente a relação menor ou igual $\leq$ como o conjunto \[ \{(a,b)\in A\times A\mid a\leq b\}\subseteq A\times A. \] Além disso, o leitor pode também definir as relações maior e maior ou igual.
No conjunto $\Z$ podemos definir a relação divisor $\mid$. Esta relação está definida formalmente como \[ \{(a,b)\in\Z\times\Z\mid b=qa\textrm{ com algum }q\in \Z\}. \]

6.5 Propriedades de relações

Definição 6.4 Seja $R$ uma relação sobre $A$.

Dizemos que $R$ é reflexiva se $aRa$ para todo $a\in A$ (ou seja $(a,a)\in R$ para todo $a\in A$).
Dizemos que $R$ é simétrica se $aRb$ implica que $bRa$ para todo $a,b\in A$.
Dizemos que $R$ é antisimétrica se $aRb$ e $bRa$ implicam que $a=b$ para todo $a,b\in A$.
Dizemos que $R$ é transitiva se $aRb$ e $bRc$ implicam que $aRc$ para todo $a,b,c\in A$.

Exemplo 6.8 Considerando as relações no Exemplo 6.7, temos que as relações de igualdade, maior ou igual, menor ou igual, e divisor são reflexivas. A igualdade é simétrica. As relações maior ou igual, menor ou igual, maior e menor são antisimétricas, e todas as relações neste exemplo são transitivas.

6.6 Relações de equivalência

Definição 6.5 Seja $A$ um conjunto. Uma relação $R\subseteq A\times A$ é dita relação de equivalência se

$R$ é reflexiva (ou seja, $aRa$ para todo $a\in A$);
$R$ é simétrica (ou seja $aRb$ implica $bRa$ para todo $a,b\in A$); e
$R$ é transitiva (ou seja $aRb$ e $bRc$ implica $aRc$ para todo $a,b,c\in A$).

As relações de equivalência são normalmente denotados com os símbolos $\equiv$, $\cong$, etc, e escrevemos $a\equiv b$ ou $a\cong b$ em vez de $aRb$.

Exemplo 6.9 O protôtipo das relações de equivalência é a relação de igualdade. A relação de igualdade \[ \{(a,a)\mid a\in A\} \] é uma relação de equivalência para todo conjunto $A$.

Exemplo 6.10 Seja $A=\{1,2,3,4,5\}$ e seja \[ \equiv=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4)\} \] Então $\equiv$ é uma relação de equivalência.

Exemplo 6.11 Considere a relação $R$ em $\Z$ definido como \[ a\equiv b\quad\mbox{se e somente se $a-b$ é par}. \] Note que $\equiv$ é uma relação de equivalência. Também note que $a\equiv b$ se e somente se $a$ e $b$ tem a mesma paridade. Ou seja, $0\equiv 2$, $0\equiv -2$, $0\equiv 4$, $0\equiv -4$, $1\equiv -1$, $1\equiv 3$, $1\equiv -3$, etc, mas $2\not\equiv -1$.

6.7 Classes de equivalência

Definição 6.6 Seja $A$ um conjunto e $R$ uma relação de equivalência. Seja $a\in A$. O conjunto \[ [a]_\equiv=\{b\in A\mid a\equiv b\} \] é chamado de classe de equivalência de $a$ pela relação $\equiv$. Quando não tem perigo de ambiguidade, escrevemos $[a]$ em vez de $[a]_\equiv$. Note que $[a]\subseteq A$.

Exemplo 6.12 No Exemplo 6.9, a classe de equivalência de um elemento $a\in A$ é o conjunto $\{a\}$. No Exemplo 6.10, temos que \[ [1]=[2]=\{1,2\}\quad \mbox{e}\quad [3]=[4]=[5]=\{3,4,5\}. \] No Exemplo 6.10, temos que \[ [a]=\{0,\pm 2,\pm 4,\ldots\}=\{2k\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é par}, \] e \[ [a]=\{\pm 1,\pm 3,\ldots\}=\{2k+1\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é ímpar}. \] Ou seja, temos apenas duas classes de equivalência, uma formada pelos números pares, e a outra formada pelos números ímpares.

Lema 6.1 Seja $A$ um conjunto e assuma que $\equiv$ é uma relação de equivalência. Temos as seguintes propriedades para todo $a,b\in A$.

$a\in [a]$;
se $[a]\cap [b]\neq \emptyset$ então $[a]=[b]$.

Comprovação.

Note que $a\in[a]$ é equivalente a dizer que $a\equiv a$ e isso vale pois a relação $\equiv$ é reflexiva.
Assuma que $c\in [a]\cap [b]$. Isso quer dizer que $a\equiv c$ e $b\equiv c$. Por simetria temos também que $c\equiv a$. Afirmamos que $[a]=[b]$. Provaremos isso verificando que $[a]\subseteq [b]$ e $[b]\subseteq [a]$. Assuma primeiro que $x\in[a]$; ou seja $a\equiv x$. Então \[ b\equiv c\equiv a\equiv x. \] Aplicando a transitividade, obtemos que $b\equiv x$ e $x\in [b]$. Portanto obtemos que $[a]\subseteq [b]$. A inclusão que $[b]\subseteq [c]$ pode ser verificado por argumento similar.

6.8 Partições

Definição 6.7 Seja $A$ um conjunto. Um conjunto $\mathcal P$ de subconjuntos de $A$ é dito partição de $A$ se

todo elemento $a\in A$ pertence a um subconjunto $X\in \mathcal P$; e
se $X,Y\in \mathcal P$ são distintos, então $X\cap Y=\emptyset$.

Os conjuntos $X\in\mathcal P$ são chamados de partes ou blocos da partição $\mathcal P$.

Exemplo 6.13 Todo conjunto $A$ tem duas partições triviais: \[ \{A\}\quad\mbox{e}\quad \{\{a\}\mid a\in A\}. \] O conjunto $\{\{1,2\},\{3,4,5\}\}$ é uma partição do conjunto $\{1,2,3,4,5\}$. O conjunto dos números inteioros pode ser particionado como \[ \{\{2k\mid k\in \Z\},\{2k+1\mid k\in\Z\}\}. \] Ou seja, o conjunto dos inteiros pode ser particionado para o conjunto de pares e o conjunto de ímpares.

Teorema 6.1 Seja $A$ um conjunto. Se $\equiv$ é uma relação de equivalência sobre $A$, então o conjunto das classes de equivalência é uma partição de $A$.

Reciprocamente, se $\mathcal P$ é uma partição de $A$, então pode-se definir uma relação de equivalência $\equiv_{\mathcal P}$ pondo \[ a\equiv_{\mathcal P} b\quad \bicond\quad \mbox{$a$ e $b$ estão no mesma parte de $\mathcal P$} \] As classes de equivalência de $\equiv_{\mathcal P}$ são as partes de $\mathcal P$.

Comprovação. Assuma primeiro que $\equiv$ é uma relação de equivalência. Seja $\mathcal C$ o conjunto de classes de equivalência. Por item 1. do Lema 6.1, obtemos que $a\in [a]\in \mathcal C$ para todo $a\in A$. Então o item 1. da Definição 89.1 está verificada. O item 2. da Definição 89.1 está verdadeira para $\mathcal C$ por causa do item 2. do Lema 6.1.

Assuma agora que $\mathcal P$ é uma partição de $A$ e defina $\equiv_{\mathcal P}$ como no enunciado do teorema. Vamos verificar as três propriedades na definição Definição 6.5.

Reflexividade: se $a\in A$, então $a$ claramente pertence à mesma parte de $\mathcal P$ que $a$ e $a\equiv_{\mathcal P} a$. Logo $\equiv_{\mathcal P}$ é reflexiva.
Simetria: se $a\equiv_{\mathcal P}b$, então $a,b$ pertencem à mesma parte de $\mathcal P$. Logo $b,a$ também pertencem à mesma parte e assim $b\equiv_{\mathcal P}a$. Portanto $\equiv_{\mathcal P}$ é simétrica.
Transitividade: se $a\equiv_{\mathcal P}b$ e $b\equiv_{\mathcal P}c$, então $a$ e $b$ pertencem à mesma parte de $\mathcal P$ e $b$ e $c$ também pertencem à mesma parte de $\mathcal P$. Isso implica que $a$ e $c$ pertencem à mesma parte de $\mathcal P$. Portanto $a\equiv_{\mathcal P}c$ e a relação $\equiv_{\mathcal P}$ é transitiva.

6.9 Exemplo: Classes residuais

Como nós já discutimos, dizemos que $a$ divide $b$ ($a$ e $b$ são números inteiros) se $b=qa$ com algum $q$ inteiro. Neste caso pode-se dizer também que $a$ é um divisor de $b$ ou que $b$ é múltiplo de $a$. Se $a$ divide $b$, então escrevemos $a\mid b$.

Defina a seguinte relação sobre $\Z$: \[ a\equiv_3 b\quad\bicond\quad b-a=3k\mbox{ com algum }k\in\Z. \] Pode também dizer que $a\equiv_3 b$ se e somente se $3\mid b-a$.

Lema 6.2 A relação $\equiv_3$ é uma relação de equivalência sobre $\Z$.

Comprovação. Por definição, Definição 6.5, precisamos verificar que a relação é reflexiva, simétrica, e transitiva.

Reflexividade: Se $a\in\Z$, então $a-a=0=3\cdot 0$. Logo $a\equiv_3 a$.

Simetria: Sejam $a,b\in\Z$ tal que $a\equiv_3 b$. Então $b-a=3k$ e assim $a-b=-(b-a)=-3k=3(-k)$.

Transitividade: Sejam $a,b,c\in\Z$ tais que $a\equiv_3 b$ e $b\equiv_3 c$; ou seja $b-a=3k_1$ e $c-b=3k_2$. Neste caso \[ c-a=(b-a)+(c-b)=3k_1+3k_2=3(k_1+k_2). \] Pronto.

Exemplo 6.14 Por exemplo $2\equiv_3 5$, pois $5-2=3=3\cdot 1$. Temos também que $1\equiv_3 -2$, pois $-2-1=-3=3\cdot (-1)$. Por outro lado, $1\not\equiv_3 -1$, pois $-1-1=-2\neq 3k$.

Quais são as classes de equivalência (Definição 6.6)? Por exemplo, qual conjunto é a classe $[0]$ de $0$? Temos pela definição da classe $[0]$ que \[ [0]=\{a\in\Z\mid 0\equiv_3 a\}=\{a\in\Z\mid a-0=3k\}=\{a\in\Z\mid a=3k\}=\{3k\mid k\in \Z\}. \] Ou seja, \[ [0]=\{0,3,-3,6,-6,\ldots\}=\{3k\mid k\in\Z\}. \] Similarmente \[ [1]=\{a\in\Z\mid 1\equiv_3 a\}=\{a\in\Z\mid a-1=3k\}=\{a\in\Z\mid a=3k+1\}=\{1,-2,4,-5,7,-8,10,\ldots\} \] e \[ [2]=\{a\in\Z\mid 2\equiv_3 a\}=\{a\in\Z\mid a-2=3k\}=\{a\in\Z\mid a=3k+2\}=\{2,-1,5,-4,8,-7,\ldots\} \]

Obtemos que todo número inteiro pertençe a uma das classes de equivalência $[0],[1],[2]$. De fato se $a\in\Z$, então o resto de $a$ quando dividido por $3$ é $0$, $1$ ou $2$ e $a\in[r]$ onde $r$ é o seu resto. Assim temos apenas estas três classes.

Exercício 6.1 Seja $n\geq 2$ um inteiro e defina a relação $\equiv_n$ sobre $\Z$ na seguinte forma: \[ a\equiv_n b\quad\mbox{se e somente se $b-a=kn$ com algum $k\in \Z$}. \] Descreve as classes de equivalência para a relação $\equiv_n$.

6.10 Mais duas relações

Os seguintes dois exemplos importantes serão tratados como exercícios.

Exercício 6.2 Seja $A=\N\times \N$ e defina a seguinte relação sobre $A$: \[ (a,b)\equiv (c,d)\quad\bicond \quad a+d=b+c. \]

Mostre que $\equiv$ é uma relação de equivalência.
Ache as classes de equivalência dos elementos $(1,2)$, $(2,4)$, e $(3,5)$.
Dê uma descrição de todas as classes de equivalência.

Exercício 6.3 Seja $A=\Z\times \Z$ e defina a seguinte relação sobre $A$: \[ (a,b)\equiv (c,d)\quad\bicond \quad ad=bc. \]

Mostre que $\equiv$ é uma relação de equivalência.
Ache as classes de equivalência dos elementos $(1,2)$, $(2,4)$, e $(3,6)$.
Dê uma descrição de todas as classes de equivalência.

6.11 Relação de ordem

Definição 6.8 Seja $A$ um conjunto e $R$ uma relação em $A$. Dizemos que $R$ é uma relação de ordem (ou ordem parcial) em $A$ se

$R$ é reflexiva ($aRa$ para todo $a\in A$);
$R$ é antisimétrica (se $aRb$ e $bRa$ então $a=b$ para todo $a,b\in A$);
$R$ é transitiva (se $aRb$ e $bRc$ então $aRc$ para todo $a,b,c\in A$).

Exemplo 6.15

Se $A$ é um conjunto de números, então as relações $\leq$ e $\geq$ são relações de ordem, mas as relações $<$ e $>$ não são relações de ordem pela Definição 6.8 (pois elas não são reflexivas).
Assuma que $X$ é um conjunto e seja \[ A=\{Y\mid Y\subseteq X\}. \] As relações $\subseteq$ e $\supseteq$ são relações de ordem sobre $A$.
Seja $A=\N$ e considere a relação $\mid$ de divisibilidade. Em outras palávras, $a\mid b$ se e somente se $b=qa$ com algum $q\in\N$. Então $\mid$ é uma relação de ordem sobre $A$. Note que a mesma relação não é relação de ordem sobre $\Z$, pois $2\mid -2$ e $-2\mid 2$, mas $-2\neq 2$. Ou seja, $\mid$ não é antisimétrica em $\Z$.

6.12 Ordem total ou linear

Definição 6.9 Seja $R$ uma relação de ordem sobre o conjunto $A$, Dizemos que $R$ é uma ordem total ou ordem linear se \[ aRb\quad \mbox{ou}\quad bRa \] vale para todo $a,b\in R$.

Exercício 6.4 Entre os exemplos no Exemplo 6.15, 1. é ordem total, mas 2. e 3. não são ordens totais.