Elementos Notáveis

UNIVERSIDADE FEDERAL DO CEARÁ - CAMPUS DE CRATEÚS CURSOS: CIÊNCIA DA COMPUTAÇÃO e SISTEMAS DE INFORMAÇÃO DISCIPLINA: MATEMÁTICA DISCRETA Elementos Notáveis Seja (S,⪯) um conjunto parcialmente ordenado. Dizemos que: • a é maximal de S se, e somente, se ∀b ∈ S ou b ⪯ a ou b e a não são comparáveis. Ou seja, não e existe nenhum elemento diferente de a que seja posterior a a. Neste caso a não precisa se relacionar com todos os elementos do conjunto. • a é minimal de S se, e somente, se ∀b ∈ S ou a ⪯ b ou b e a não são comparáveis. Ou seja, não e existe nenhum elemento diferente de a que seja anterior a a. Neste caso a não precisa se relacionar com todos os elementos do conjunto. • a é máximo de S se, e somente, se ∀b ∈ S,b ⪯ a. Ou seja, todos os elementos do conjunto S são anteriores a a ou equivalentemente a é posterior a todos os elementos de S. Neste caso a deve se relacionar com todos os elementos do conjunto. a é maior que todos os outros elementos. • a é mínimo de S se, e somente, se ∀b ∈ S,a ⪯ b. Ou seja, a é anterior a todos os elementos de S ou equivalentemente todos os elementos do conjunto S são posteriores a a. Neste caso a deve se relacionar com todos os elementos do conjunto. a é menor que todos os outros elementos. No diagrama de Hasse da relação, o elemento mınimo existe se há um único ponto no diagrama a partir do qual é possível alcançar qualquer outro ponto por uma sequência de linhas, todas elas percorridas no sentido de baixo para cima. O elemento máximo, se existe, pode ser identificado de maneira análoga, isto é, se a partir dele podemos alcançar qualquer outro ponto percorrendo uma sequência de linhas no sentido descendente. Se R é uma relação de ordem total, e o conjunto S é finito, sempre existe um elemento mínimo. Se R não é uma ordem total, ou se S é infinito, o mínimo pode existir ou não. Em qualquer caso, se existe um elemento mínimo, ele é único. As mesmas observações são válidas para o máximo. Figura 1: O diagrama de Hasse desta relação mostra que os elementos minimais são 3 e 5, e o único maximal é 4. O elemento 4 é máximo, e não há elemento mınimo. Considere a relação em A = {1,2,3,4,5} cujo diagrama de Hasse está representado na Figura 1. Note que não há um único ponto no diagrama a partir do qual é possível alcançar qualquer outro ponto por uma sequência de linhas, todas elas percorridas no sentido de baixo para cima. Por exemplo, não dá para alcançar o elemento 3 a partir do 5 no sentido ascendente. Portanto, não há um elemento mínimo. Por outro lado, há um único ponto no diagrama (4) a partir do qual é possível alcançar qualquer outro ponto por uma sequência de linhas, todas elas percorridas no sentido de cima para baixo. Portanto, elemento 4 é máximo. Exercício resolvido. Seja S = {a,b,c} um conjunto e seja P(S) o conjunto das partes de S. Considere a relação de ordem parcial R em P(S) definida por R = {(A,B)|A ⊆ B}. Determine se existe um elemento máximo e um elemento mínimo em P(S). Figura 2: O diagrama de Hasse de (P(S),⊆). O diagrama de Hasse do conjunto parcialmente ordenado (P(S),⊆) está representado na Figura 2. Note que o elemento mínimo ou menor elemento é o conjunto vazio, ∅, pois ∅ ⊆ C para qualquer subconjunto C de S. O conjunto S = {a,b,c} é o elemento máximo ou maior elemento, pois todos os elementos de P(S) são subconjuntos de S. Note que não há nenhum conjunto maior que S que se relacione com os demais elementos de P(S). Observação: R não é uma relação de ordem total, pois {a,b} e {a,c} não são comparáveis, ou seja, nem {a,b} ⊈ {a,c} nem {a,c} ⊈ {a,b}.