Sejam (
) e (
) ordens parciais isomorfas, e associe a elas seus respectivos grafos
e
, como na Definição 2.5. Prove que
e
são grafos isomorfos.
Passo 1
O enunciado afirma que temos dois posets isomorfos
e
. Por definição, existe uma bijeção
tal que, para todos
,
A cada poset associamos um grafo
(Definição 2.5), cujo conjunto de vértices é
e cujas arestas representam a relação (ou a cobertura, dependendo da definição). Queremos provar que
e
são isomorfos, ou seja, existe uma bijeção entre vértices que preserva as arestas.
Passo 2
Definimos
Como
é bijetora,
também é bijeção entre os conjuntos de vértices de
e
.
Passo 3
Agora verificamos que
preserva adjacência. Seja
uma aresta de
. Dois casos comuns de definição de
são:
- Grafos de comparabilidade:
é aresta se e somente se ou . - Grafos de Hasse (grafo de cobertura):
é aresta se e somente se um cobre o outro em , i.e., e não existe tal que , ou vice-versa.
Em ambos os casos, a condição de isomorfismo de posets garante:
– Se
então
.
– Se não existe intermediário em
entre
e
, então, por sobrejetividade de
, também não existe intermediário entre
e
em
.
– Se não existe intermediário
Portanto,
O mesmo raciocínio na direção inversa (usando
) mostra que nenhuma outra aresta é criada ou destruída. Logo,
é um isomorfismo de grafos.
Resposta
Os grafos
e
são isomorfos via a bijeção
, que preserva exatamente as arestas.