Exercício 7.1 Sejam \(A=\{0,2,4\}\) e \(B=\{1,2,3,4\}\). Faça uma lista dos elementos de \(A\times A\), \(A\times B\), \(B\times A\) e \(B\times B\).
Exercício 7.2 Sejam \(A\), \(B\) e \(C\) conjuntos.
- O que pode dizer sobre \(\emptyset\times A\) e \(A\times \emptyset\)? Justifique.
- Demonstre que \(B=C\) se e somente se \(\forall A:A\times B=A\times C\).
- Assumindo que \(A\times B=B\times A\), o que pode dizer sobre \(A\) e \(B\)?
Exercício 7.3 Demonstre as seguintes igualdades para conjuntos \(A\), \(B\), \(C\), \(D\):
- \((A\cup B)\times C=(A\times C)\cup (B\times C)\);
- \((A\cap B)\times C=(A\times C)\cap (B\times C)\);
- \(A\times (B\cup C)=(A\times B)\cup (A\times C)\);
- \(A\times (B\cap C)=(A\times B)\cap (A\times C)\);
- \((A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)\).
Exercício 7.4 Sejam \(A\), \(B\), \(C\) e \(D\) conjuntos. Será que a igualdade \[
(A\times B)\cup (C\times D)=(A\cup C)\times (B\cup D)
\] é sempre verdadeira. Se sim, dê prova; se não, dê contraexemplo.
Exercício 7.5 Seja \(A=\{1,2,3,4,5,6\}\). Faça uma lista dos pares ordenados que pertencem às seguintes relações:
- igualdade (\(=\))
- menor (\(<\))
- menor ou igual (\(\leq\))
- divisor (\(\mid\))
Exercício 7.6 Seja \(A=\{1,2,3,4,5,6\}\). Dê exemplo de relação \(R\) no conjunto \(A\) para cada item que satisfaz as propriedades indicadas no item.
- \(R\) é reflexiva, mas não é simétrica.
- \(R\) é simétrica, mas não é reflexiva.
- \(R\) é simétrica e antisimétrica.
Exercício 7.7 Determine quais das seguintes relações são reflexivas, simétricas, antisimétricas, ou transitivas no conjunto \(\mathbb R\):
- \(aRb\) se e somente se \(a-b\leq 1\);
- \(aRb\) se e somente se \(|a-b|\leq 1\);
- \(aRb\) se e somente se \(a-b\) é inteiro;
- \(aRb\) se e somente se \(a^2+b^2=0\);
- \(aRb\) se e somente se \(a^2+b^2=1\);
- \(aRb\) se e somente se \(a-b\) é irracional.
Exercício 7.8 Sejam \(R\) e \(Q\) duas relações em um conjunto \(A\). Considere \(R\cup Q\) e \(R\cap Q\) como relações em \(A\) e demonstre as seguintes afirmações.
- Se \(R\) e \(Q\) são reflexivas, então \(R\cup Q\) e \(R\cap Q\) são reflexivas.
- Se \(R\) e \(Q\) são simétricas, então \(R\cup Q\) e \(R\cap Q\) são simétricas.
- Se \(R\) e \(Q\) são transitivas, então \(R\cap Q\) é transitiva, mas \(R\cup Q\) pode não ser transitiva.
Exercício 7.9 Um aluno gostaria de provar que se \(R\) é uma relação transitiva e simétrica sobre um conjunto \(A\), então \(R\) é reflexiva. O aluno fez o seguinte argumento:
Seja \(R\) uma relação transitiva e simétrica sobre um conjunto \(A\). Assuma que \(a\in A\) é um elemento qualquer. Seja \(b\in A\) tal que \(aRb\). Como \(R\) é simétrica, temos que \(bRa\). Como \(R\) é transitiva, \(aRb\) e \(bRa\) implicam que \(aRa\). Portanto, provamos para um elemento \(a\in A\) qualquer que \(aRa\) e assim \(R\) é reflexiva.
- Será que a prova do aluno está certa? Critique a resposta.
- Se você não concorda com o argumento do aluno, dê exemplo explícito de uma relação \(R\) que seja transitiva e simétrica, mas não é reflexiva.
Exercício 7.10 Revisar a relação \(\equiv_n\) em \(\mathbb Z\) no Exercício 6.1. Escolha um valor pequeno para \(n\) (por exemplo, \(n=3,4,5\)) e responda às seguintes perguntas:
- Mostre que temos apenas um número finito de classes de equivalência.
- Mostre que cada classe contem infinitos elementos.
- Descreve a classe de equivalência dos números \(-3,-2,-1,0,1,2,3\).
- Faça uma lista de todas as classes de equivalência para o \(n\) escolhido.
Exercício 7.11 Seja \(A=\mathbb N\times \mathbb N\) e seja \(R\) a relação em \(A\) definida com a seguinte regra: \[
(a,b)R(c,d)\quad\mbox{se e somente se}\quad a+d=b+c.
\]
- Demonstre que \(R\) é uma relação de equivalência.
- Ache as classes de equivalência dos elementos \((1,1)\), \((1,2)\), \((2,1)\), \((6,4)\).
- Mostre que há infinitas classes de equivalência e cada classe contem infinitos elementos.
- Faça uma lista das classes de equivalência listando cada classe exatamente uma vez.
Exercício 7.12 Seja \(A=\mathbb Z\times \mathbb Z\smallsetminus\{0\}\) e seja \(R\) a relação em \(A\) definida com a seguinte regra: \[
(a,b)R(c,d)\quad\mbox{se e somente se}\quad ad=bc.
\]
- Demonstre que \(R\) é uma relação de equivalência.
- Ache as classes de equivalência dos elementos \((1,1)\), \((1,2)\), \((2,1)\), \((6,3)\).
- Mostre que há infinitas classes de equivalência e cada classe contem infinitos elementos.
- Faça uma lista das classes de equivalência listando cada classe exatamente uma vez.
- Explique porque a mesma relação não é equivalência sobre o conjunto \(\mathbb Z\times\mathbb Z\).
Exercício 7.13 Considere \(A=\mathbb R^2\) e defina a seguinte relação \(R\) em \(A\): \[
(x_1,y_1)R(x_2,y_2)\quad\mbox{se e somente se}\quad x_1<x_2 \mbox{ ou }x_1=x_2 \mbox{ e } y_1\leq y_2.
\]
- Mostre que \(R\) é uma relação de ordem.
- Decida se \(R\) é ordem total ou não.
- Considere o ponto \((1,2)\in \mathbb R^2\). Faça um esboço dos seguintes conjuntos no plano: \[
\{(x,y)\in\mathbb R\mid (1,2)R(x,y)\}\quad\mbox{e}\quad \{(x,y)\in\mathbb R\mid (x,y)R(1,2)\}.
\]
Exercício 7.14 Sejam \(A\) e \(B\) conjuntos com relações de ordem \(R_A\) e \(R_B\), respetivamente. Defina uma relação \(R_C\) em \(C=A\times B\) na seguinte maneira: \[
(a_1,b_1)R_C(a_2,b_2)\quad\mbox{se e somente se}\quad [a_1R_Aa_2 \mbox{ e } a_1\neq a_2] \mbox{ ou }[a_1=a_2 \mbox{ e } y_1R_By_2].
\] Mostre que \(R_C\) é uma relação de ordem.
Exercício 7.15 Seja \(R\subseteq A\times A\) uma relação reflexiva e transitiva. Define \(Q\subseteq A\times A\), com a regra que \(aQb\) se e somente se \(aRb\) e \(bRa\). Moste que \(Q\) é uma relação de equivalência.
Exercício 7.16 Considere a relação \(\mid\) para números inteiros; ou seja, para \(a,b\in\mathbb Z\), \(a\mid b\) se existir \(q\in \mathbb Z\) tal que \(b=qa\).
- Mostre que \(\mid\) é uma relação reflexiva, transitiva, mas não é simétrica.
- Aplique a construção do Exercício 7.15 para a relação \(\mid\) e descreva a relação que obteve. Verifique que a relação obtida desta forma é uma equivalência.
Exercício 7.17 Seja \(A\) um conjunto e sejam \(R,\ Q\subseteq A\times A\) relações. Demostre as seguintes afirmações.
- Se \(R\) e \(Q\) são relações de equivalência, então \(R\cap Q\) também é.
- Se \(R\) e \(Q\) são relações de equivaléncia, então pode ser que \(R\cup Q\) não é.
- Se \(R\) e \(Q\) são relações de ordem, então \(R\cap Q\) também é.
- Se \(R\) e \(Q\) são relações de ordem, então pode ser que \(R\cup Q\) não é.
- Se \(R\) e \(Q\) são ordens totais, então pode ser que \(R\cup Q\) não é.
- Se \(R\) e \(Q\) são ordens totais, então pode ser que \(R\cap Q\) não é.