Prove que a relação S sobre N × N tal que (a, b)S(c, d) se, e somente se, a | c e b | d é uma relação de ordem. A relação S ordena totalmente N × N ?

Passo 1

Fala minha galera, bora fazer mais um exercício maravilhoso da matemática discreta!

Vamos provar a reflexividade, simetria e transitividade para atestar que é uma relação de ordem.

Provando a reflexividade:

Como a │ a e b │ b então a , b S ( a , b ) e a relação é simétrica.

Passo 2

Para provar a simetria temos que considerar ( a ,   b ) S ( c ,   d ) e ( c ,   d ) S ( a ,   b ) , então:

a │ c   e   b │ d e também c │ a   e   d │ b ⇒ a = c , da mesma forma pode-se concluir que b = d . Portanto, a , b = ( c , d ) provando que é antissimétrica.

Passo 3

Para provar a transitividade temos que considerar ( a ,   b ) S ( c ,   d ) e ( c ,   d ) S ( e ,   f ) , então:

a │ c   e   b │ d e também c │ e   e   d │ f , que implica em a │ e e b │ f , ou seja, a , b S ( e , f ) e está provada a transitividade.

Portanto, S ordena o conjunto parcialmente.

Resposta

Não, apenas parcialmente.