7  Lista de Exercícios

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.

  1. O que pode dizer sobre \(\emptyset\times A\) e \(A\times \emptyset\)? Justifique.
  2. Demonstre que \(B=C\) se e somente se \(\forall A:A\times B=A\times C\).
  3. 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\):

  1. \((A\cup B)\times C=(A\times C)\cup (B\times C)\);
  2. \((A\cap B)\times C=(A\times C)\cap (B\times C)\);
  3. \(A\times (B\cup C)=(A\times B)\cup (A\times C)\);
  4. \(A\times (B\cap C)=(A\times B)\cap (A\times C)\);
  5. \((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:

  1. igualdade (\(=\))
  2. menor (\(<\))
  3. menor ou igual (\(\leq\))
  4. 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.

  1. \(R\) é reflexiva, mas não é simétrica.
  2. \(R\) é simétrica, mas não é reflexiva.
  3. \(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\):

  1. \(aRb\) se e somente se \(a-b\leq 1\);
  2. \(aRb\) se e somente se \(|a-b|\leq 1\);
  3. \(aRb\) se e somente se \(a-b\) é inteiro;
  4. \(aRb\) se e somente se \(a^2+b^2=0\);
  5. \(aRb\) se e somente se \(a^2+b^2=1\);
  6. \(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.

  1. Se \(R\) e \(Q\) são reflexivas, então \(R\cup Q\) e \(R\cap Q\) são reflexivas.
  2. Se \(R\) e \(Q\) são simétricas, então \(R\cup Q\) e \(R\cap Q\) são simétricas.
  3. 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.

  1. Será que a prova do aluno está certa? Critique a resposta.
  2. 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:

  1. Mostre que temos apenas um número finito de classes de equivalência.
  2. Mostre que cada classe contem infinitos elementos.
  3. Descreve a classe de equivalência dos números \(-3,-2,-1,0,1,2,3\).
  4. 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. \]

  1. Demonstre que \(R\) é uma relação de equivalência.
  2. Ache as classes de equivalência dos elementos \((1,1)\), \((1,2)\), \((2,1)\), \((6,4)\).
  3. Mostre que há infinitas classes de equivalência e cada classe contem infinitos elementos.
  4. 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. \]

  1. Demonstre que \(R\) é uma relação de equivalência.
  2. Ache as classes de equivalência dos elementos \((1,1)\), \((1,2)\), \((2,1)\), \((6,3)\).
  3. Mostre que há infinitas classes de equivalência e cada classe contem infinitos elementos.
  4. Faça uma lista das classes de equivalência listando cada classe exatamente uma vez.
  5. 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. \]

  1. Mostre que \(R\) é uma relação de ordem.
  2. Decida se \(R\) é ordem total ou não.
  3. 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\).

  1. Mostre que \(\mid\) é uma relação reflexiva, transitiva, mas não é simétrica.
  2. 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.

  1. Se \(R\) e \(Q\) são relações de equivalência, então \(R\cap Q\) também é.
  2. Se \(R\) e \(Q\) são relações de equivaléncia, então pode ser que \(R\cup Q\) não é.
  3. Se \(R\) e \(Q\) são relações de ordem, então \(R\cap Q\) também é.
  4. Se \(R\) e \(Q\) são relações de ordem, então pode ser que \(R\cup Q\) não é.
  5. Se \(R\) e \(Q\) são ordens totais, então pode ser que \(R\cup Q\) não é.
  6. Se \(R\) e \(Q\) são ordens totais, então pode ser que \(R\cap Q\) não é.