Sejam
e
relações em
. 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
e
são reflexivas, então
é reflexiva.
Se
Passo 1
Então o enunciado diz o seguinte: “Sejam
e
relações em
. Se
e
são reflexivas, então
é reflexiva.”
Matéria: teoria de relações – especificamente reflexividade e composição de relações.
O que precisamos usar:
Matéria: teoria de relações – especificamente reflexividade e composição de relações.
O que precisamos usar:
- Definição de relação reflexiva.
- Definição de composição de relações.
- Montar uma prova direta que mostra que, para todo
, .
Passo 2
Definição de reflexiva (explicando devagar):
Uma relação em
é dita reflexiva se, para todo elemento
, o par
pertence a
.
Em notação:
Uma relação
Em notação:
Como
e
são reflexivas, sabemos:
Passo 3
Definição de composição de relações:
Se e
são relações em
, a composição
é o conjunto de pares
tais que existe
com
Se
Em fórmulas:
Passo 4
Agora a prova direta, passo a passo:
- Pegue um elemento qualquer
. Queremos mostrar que . - Como .
- Como
é reflexiva, sabemos que . - Para a definição de composição, basta encontrar um “pontinho” intermediário
tal que
e . - A escolha natural é
. Aí fica:
e .
Logo, por definição,. - Como o
foi um elemento genérico de , concluímos que todos os elementos de têm em .
Resposta
A proposição é verdadeira. Por reflexividade de
e
e pela definição de composição, sempre temos para todo
.