Buscar

1ª Lista

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1a Lista : Relac¸o˜es: Equivaleˆncia e Ordem. Disciplina: Aritme´tica e A´lgebra (04/fev./2011).
1. Sejam A e B conjuntos na˜o vazios, quaisquer. O produto cartesiano A×B e´ comutativo? Isto e´, A×B = B ×A?
2. Sejam R uma relac¸a˜o de equivaleˆncia sobre A e x, y ∈ A. Mostre que as seguintes afirmac¸o˜es sa˜o equivalentes:
(a) xRy;
(b) x ∈ y;
(c) y ∈ x;
(d) x = y
3. Se F e´ uma partic¸a˜o de um conjunto A, mostre que existe uma relac¸a˜o R de equivaleˆncia sobre A de modo que A∼R
= F .
4. Determinar todas as relac¸o˜es bina´rias sobre o conjunto A = {a, b}. Quais sa˜o Reflexivas? E Sime´tricas? E Transitivas? E
Anti-sime´tricas?
5. SejaA = {1, 2, 3}. Quais das seguintes relac¸o˜es em A sa˜o Reflexivas? E Sime´tricas? E Transitivas? E Anti-sime´tricas?Justifique.
(a) R1 = {(1, 2), (1, 1), (2, 2), (2, 1), (3, 3)};
(b) R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)};
(c) R3 = {(1, 1), (2, 2), (1, 2), (2, 3), (3, 1)};
(d) R4 = A×A;
(e) R5 = ∅.
6. Construir sobre A = {a, b, c, d} relac¸o˜esR1, R2, R3 eR4 tais queR1 so´ tem a propriedade reflexiva, R2 so´ tem a propriedade
sime´trica, R3 so´ tem a propriedade transitiva e R4 so´ tem a propriedade anti-sime´trica. Justifique.
7. Pode uma relac¸a˜o sobre um conjunto A 6= ∅ ser sime´trica e anti-sime´trica? Pode uma relac¸a˜o sobre A na˜o ser sime´trica e
nem anti-sime´trica? Justifique.
8. Quais das relac¸o˜es abaixo sa˜o relac¸o˜es de equivaleˆncia sobre A = {a, b, c}?
(a) R1 = {(a, a), (a, b), (b, a), (b, b), (c, c)};
(b) R2 = {(a, a), (a, b), (b, a), (b, b), (b, c)};
(c) R3 = {(a, a), (b, b), (b, c), (c, b), (a, c), (c, a)};
(d) R4 = A×A;
(e) R5 = ∅.
9. A relac¸a˜o R sobre N× N tal que
(x, y)R(z, t)⇔ x+ y = z + t,
e´ uma relac¸a˜o de equivaleˆncia?
10. A relac¸a˜o S sobre Z× {Z− {0}} tal que
(x, y)R(z, t)⇔ xt = yz,
e´ uma relac¸a˜o de equivaleˆncia?
11. Sejam A = {−3,−2,−1, 0, 1, 2, 3} e R = {(x, y) ∈ A2 : x + |x| = y + |y|}. Mostrar que R e´ uma relac¸a˜o de equivaleˆncia e
descrever
A
∼R
.
12. Seja R a relac¸a˜o sobre Q definida da seguinte forma
xRy ⇔ x− y ∈ Z.
Mostre que R e´ uma relac¸a˜o de equivaleˆncia e descreva as classes de equivaleˆncia 0 e 1.
13. Verifique se as seguintes relac¸o˜es sa˜o de Ordem Parcial. Em caso afirmativo, verifique se e´ uma Relac¸a˜o de Ordem Total.
(a) A = {a, b, c}, com R = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)};
(b) A = N, com R definida por ∀x, y ∈ N, xRy ⇔ x|y (x divide y).
1

Outros materiais