lógica

Carlos Mario Sierra Duque

Relación de orden: definiciones, propiedades y teoremas.

RELACIÓN DE ORDEN
Toda relación binaria R definida en A, que sea reflexiva, antisimétrica y transitiva se dice relación de
orden, y se denota como , . Formalmente:
RO_1

∀

,

RO_2

∀ ∀ ∀

RO_3

∀ ∀

∈

reflexividad
,

,

∈
∈

∧
∧

,
,

∈
∈

→
→

,

∈

=transitividad
antisimentría

Cuando dos elementos ∈ y ∈ se vinculan mediante una relación de orden , o sea , ∈ ,
se dicen comparables. Notaciones frecuentemente empleadas para representar , ∈ , son: ≼ o
≤ 1; como consecuencia de estas notaciones, también puede simbolizarse a ,
mediante , ≼
o ,≤ 2
Una manera de traducir o leer la vinculación ≼ es: “ es un elemento que precede o a lo sumo seencuentra al mismo nivel que ”, o también puede afirmarse que “ es un elemento que sucede o por lo
menos se encuentra al mismo nivel que ”.
Una relación de orden definida en un conjunto en el cual no necesariamente todos sus elementos
son comparables, se le denomina relación de orden parcial; además, el conjunto será referido como
conjunto parcialmente ordenado (partially ordered set, o poset). Porotro lado, el caso de una relación
de orden definida en un conjunto en el que todos sus elementos son comparables, se denomina
relación de orden total. Formalmente, una relación de orden es total si, y sólo si, ∀ ∀
≠ ∧
3
, ∉ → , ∈ .
Ejemplos de conjuntos parcialmente ordenados:
, ⊆ : el conjunto potencia de , cuyos elementos (los subconjuntos de ) se ordenan
mediante la operación de“inclusión”.
ℤ , ≤ : el conjunto de los enteros positivos, cuyos elementos se ordenan mediante la operación
“menor o igual”.
ℤ , | : el conjunto de los enteros positivos, cuyos elementos se ordenan mediante la operación
“divisibilidad”.
Representación de relaciones de orden mediante un grafo
Ejemplo 1. Observe la Figura. Ella representa un grafo donde: = , , , , es un conjunto de
elementosdenominados vértices; y el conjunto ! de elementos llamados aristas o arcos, es:
!=
, , , , , , , , , , , , , , , , , , , , , , , , , .
Observe que ! representa una relación en , reflexiva, antisimétrica y transitiva. Por ende, una relación
de orden parcial.

cuando se garantiza que ≠ , entonces , ∈ es ≺
Es importante resaltar que, en este caso, el signo ≤ no hace referencia exclusiva a la relación“menor o igual”, y asume un
significado más general: “relación de orden”.
3
o∀ ∀
⊀ → ≼
1
2

1

Carlos Mario Sierra Duque

Relación de orden: definiciones, propiedades y teoremas.

e
a
b

d

c

Ilustración 1 Grafo para la relación de orden (V, E)
Representación de relaciones de orden mediante Diagramas de Hasse
En el caso de las relaciones de orden parcial, se ha planteado eluso, más conveniente, de los diagramas
de Hasse. Estos diagramas se construyen con base en las siguientes directrices:
No use las aristas que representan el enlace de un elemento consigo mismo (es decir, aquellas que
simbolizan la propiedad reflexiva)
No use las aristas que unan directamente aquellos vértices que se puedan conectar mediante un
camino que use dos o más aristas. (las aristas aeliminar son aquellas que son consecuencia de la
propiedad transitiva).
Coloque los vértices de manera que las aristas queden apuntando siempre hacia arriba. Lo anterior
implica que en la parte más inferior se ubican aquellos vértices de los cuales sólo salen aristas, y en
la parte superior aquellos a los cuales sólo llegan aristas.
Elimine las cabezas de flecha de las aristas, pues ya sehacen innecesarias.
Reemplace los círculos por puntos.
Ejemplo 2. El grafo mostrado en el Ejemplo 1, y que corresponde a la relación de orden
ser representado mediante el siguiente diagrama de Hasse.
b

, ! , puede

e
c
d
a
Elementos extremos en un conjunto parcialmente ordenado $
Se un conjunto parcialmente ordenado por medio de una relación de orden cualquiera ≤, es decir,
, ≤...