Todo

2.4.3. Relaci´on de orden
Definici´on 29. Si 4 es una relaci´on binaria en A reflexiva, antisim´etrica y
transitiva, se dice que es una relaci´on de orden. Si a 4 b se dice que a es
anterior a b omenor o igual que16 b.
Una relaci´on de orden 4 en un conjunto A es de orden total si dados
dos elementos cualesquiera a, b de A, siempre se pueden comparar, es decir
a 4 b o b 4 a. Un ejemplo derelaci´on de orden total es la relaci´on ≤ en N, Z,
Q o R, mientras que las relaciones “ ⊆ ” y “divide a” definidas anteriormente
no son de orden total.
Definici´on 30. Un poset (A,4) es unconjunto A y una relaci´on de orden
4 definida en ´el.
Ejemplos 13. i) Son ejemplos de posets (P(A),⊆) y (N, |).
ii) Sea (L,≤) un alfabeto, es decir un conjunto finito totalmente ordenado
y sea L∗ elconjunto de palabras que se pueden formar con los elementos
de L. El orden de L se puede extender a L∗ siendo la relaci´on de orden
resultante de orden total y llamada orden lexicogr´afico por ser elorden
del diccionario. As´ı, las palabras l1l2 . . . lp y l′
1l′
2 . . . l′
q est´an relacionadas
y verifican que l1l2 . . . lp ≤ l′
1l′
2 . . . l′
q , si ocurre:
para alg´un k < p, se tieneque li = l′
i (con i = 1, . . . k), lk+1 ≤ l′
k+1
y lk+1 6= l′
k+1 (por ejemplo casa y caso)
p ≤ q y li = l′
i , para i = 1 . . . p (por ejemplo casa y casas).
Cuando (A,4) es un poset finito,se puede representar con un diagrama
de Hasse que consiste en un conjunto de v´ertices (denotando los elementos
de A) y una serie de aristas (sin flecha). Dibujaremos una arista ascendente
de x a ysi y cubre a x, es decir, x ≤ y y no hay “elementos intermedios”
entre ambos, es decir, si z ∈ A es tal que x ≤ z ≤ y, entonces z = x o z = y.
Definici´on 31. Dos posets (A,4) y (B,≤) son isomorfossi existe una
aplicaci´on biyectiva f : A → B, de modo que:
a 4 a′ ⇐⇒ f(a) ≤ f(a′).
Ejemplos 14. Los posets (P({a, b, c}),⊆), (D30 = {1, 2, 3, 5, 6, 10, 15, 30}, |)17
y ({0, 1}3,R) son isomorfos...