Sejam R e S relações em A. Determine o valor-verdade das seguintes proposições. Se a proposição for verdadeira, faça a demonstração respectiva; caso contrário, dê um contra-exemplo.
Se R e S são antissimétricas, então R circ S é antissimétrica.

Passo 1

Beleza, o enunciado diz o seguinte: temos duas relações em um conjunto , chamadas e . Ambas são antissimétricas (ou seja, sempre que um par e o par inverso estiverem na relação, isso só pode acontecer se ). A pergunta é: será que a composição também é antissimétrica?
Conteúdo: teoria de relações (antissimetria e composição de relações).
O que precisamos:
  • Entender bem o que é “antissimétrica”.
  • Lembrar como se define a composição .
  • Mostrar que a afirmação é falsa, dando um contra-exemplo simples.

Passo 2

Teoria usada:
  1. Uma relação (x,z)in Rcirc S Long<=ftrightarrow exists,yin A:;(x,y)inS wed>= (y,z)inR em é antissimétrica se, sempre que e , então .
  2. A composição é definida por
Pra refutar, a ideia é escolher e antissimétricas mas fazer com que tenha um par e o seu inverso com .

Passo 3

Vamos montar o contra-exemplo. Seja
A=1,2,3
Definimos
S=(1,2),(1,3),(2,3), R=(2,1),(3,1),(3,2)
  • é antissimétrica porque não temos nenhum par invertido.
  • também é antissimétrica pelo mesmo motivo.

Passo 4

Agora calculamos Rcirc S =(1,1),,(1,2),,(2,1),,(2,2) .
Para ver se está em , achamos um tal que e .
  1. x=1:
    • 1→2 em e 2→1 em ⇒ (1,1)
    • 1→3 em e 3→2 em ⇒ (1,2)
    • 1→3 em e 3→1 em ⇒ (1,1) (já tínhamos)
  2. x=2:
    • 2→3 em e 3→2 em ⇒ (2,2)
    • 2→3 em e 3→1 em ⇒ (2,1)
  3. x=3: não sai nada porque não tem pares com 3 à esquerda.
Logo

Passo 5

Repare que em temos e também , mas . Isso viola a antissimetria (pois apareceu um par e seu inverso para valores distintos).

Resposta

A proposição é falsa. Contra-exemplo:
,
e
.
Ambas são antissimétricas, mas não é, pois contém e com .

Exercícios relacionados