Reticulados

Tema II
Reticulados

Prof. Ismael Huerta

Cursos Intensivos 2015

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅ R6 = A × A

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅ R6 = A × A R7 = {(a, a)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅ R6 = A × A R7 = {(a, a)}
R8 = {(b, c)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅ R6 = A × A R7 = {(a, a)}
R8 = {(b, c)} R9 = {(a, b), (b, c)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Relación Binaria

Una relación binaria R sobre un conjunto A es un subconjunto del
producto cartesiano A × A.

Ejemplo 1
Si A = {a, b, c} entonces
A × A = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Son relaciones binarias sobre el conjunto A = {a, b, c}:

R1 = {(a, a), (a, c), (b, c), (c, b)} R2 = {(a, a), (b, b), (c, c)}
R3 = {(a, b), (a, c), (b, a)} R4 = {(a, a), (a, b), (b, a), (b, b)}

También son relaciones binarias sobre A:

R5 = ∅ R6 = A × A R7 = {(a, a)}
R8 = {(b, c)} R9 = {(a, b), (b, c)} R10 = {((a, b), (b, c), (a, c)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
Cuando el conjunto A finito, cualquier relación binaria puede ser
representada gráficamente, mediante un diagrama sagital o digrafo: los
elementos del conjunto son representados como vértices del digrafo y cada
pareja (x, y ) de la relación es representado por un arco dirigido desde x
hacia y .

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
Cuando el conjunto A finito, cualquier relación binaria puede ser
representada gráficamente, mediante un diagrama sagital o digrafo: los
elementos del conjunto son representados como vértices del digrafo y cada
pareja (x, y ) de la relación es representado por un arco dirigido desde x
hacia y .

Ejemplo 2
Representaciones gráficas de las relaciones R1 , R2 , R3 del Ejemplo 1.

a a a
b b b
R1
R2 R3
c
c c

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
Cuando el conjunto A es finito, las relaciones binarias sobre A también
admiten representación mediante matrices. Si A = {a1 , a2 , . . . , an },
entonces una relación binaria R sobre A es representada ( por una matriz
1 si ai Raj
binaria MR , de orden n × n, que tiene componente ij =
0 si ai R a j

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
Cuando el conjunto A es finito, las relaciones binarias sobre A también
admiten representación mediante matrices. Si A = {a1 , a2 , . . . , an },
entonces una relación binaria R sobre A es representada ( por una matriz
1 si ai Raj
binaria MR , de orden n × n, que tiene componente ij =
0 si ai R a j

Ejemplo
Para las relaciones R1 , R2 , R3 del Ejemplo 2, las relaciones matriciales
son:
     
1 0 1 1 0 0 0 1 1
MR1 = 0 0 1 MR2 = 0 1 0 MR3 = 1 0 0
0 1 0 0 0 1 0 0 0

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades Básicas de una Relación Binaria

Definición
Consideremos una relación binaria R sobre un conjunto no vacı́o A.
Diremos que la relación R es:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades Básicas de una Relación Binaria

Definición
Consideremos una relación binaria R sobre un conjunto no vacı́o A.
Diremos que la relación R es:
1 Reflexiva ⇐⇒ ∀a ∈ A, aRa.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades Básicas de una Relación Binaria

Definición
Consideremos una relación binaria R sobre un conjunto no vacı́o A.
Diremos que la relación R es:
1 Reflexiva ⇐⇒ ∀a ∈ A, aRa.

2 Antisimétrica ⇐⇒ ∀x, y ∈ A xRy ∧ y Rx =⇒ x = y

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades Básicas de una Relación Binaria

Definición
Consideremos una relación binaria R sobre un conjunto no vacı́o A.
Diremos que la relación R es:
1 Reflexiva ⇐⇒ ∀a ∈ A, aRa.

2 Antisimétrica ⇐⇒ ∀x, y ∈ A xRy ∧ y Rx =⇒ x = y

3 Transitiva ⇐⇒ ∀x, y , z ∈ A, xRy ∧ y Rz =⇒ xRz

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades Básicas de una Relación Binaria

Definición
Consideremos una relación binaria R sobre un conjunto no vacı́o A.
Diremos que la relación R es:
1 Reflexiva ⇐⇒ ∀a ∈ A, aRa.

2 Antisimétrica ⇐⇒ ∀x, y ∈ A xRy ∧ y Rx =⇒ x = y

3 Transitiva ⇐⇒ ∀x, y , z ∈ A, xRy ∧ y Rz =⇒ xRz

4 Conexa ⇐⇒ ∀x, y ∈ A con x 6= y : xRy o y Rx

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 La relación
R1 = {(a, a), (a, b), (a, c), (c, b)}
sobre el conjunto A = {a, b, c} no es reflexiva, puesto que faltan los
pares (b, b) y (c, c) en R1 , pero la relación

R2 = {(a, a), (b, b), (b, c), (c, c)}

si es reflexiva.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 La relación
R1 = {(a, a), (a, b), (a, c), (c, b)}
sobre el conjunto A = {a, b, c} no es reflexiva, puesto que faltan los
pares (b, b) y (c, c) en R1 , pero la relación

R2 = {(a, a), (b, b), (b, c), (c, c)}

si es reflexiva.
2 Sobre el conjunto A = {m, n, p, q} la relación

R3 = {(m, n), (n, p), (n, q), (p, q), (q, n), (q, m)}

no es antisimétrica porque aparecen los pares (n, q) y (q, n); eso

significa que nR3 q y qR3 n, pero q 6= n. Por el contrario,

R4 = {(m, m), (m, n), (n, q), (p, q), (p, p)}

si es antisimétrica.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
3 La relación

R3 = {(m, n), (n, p), (n, q), (p, q), (q, n), (q, m)}

no es transitiva pues allı́ aparecen (m, n) y (n, p) pero falta (m, p); o
sea, mR3 n y nR3 p pero mR 3 p. Si es transitiva

R4 = {(m, m), (m, n), (n, p), (p, q), (m, p), (m, q), (n, q)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
3 La relación

R3 = {(m, n), (n, p), (n, q), (p, q), (q, n), (q, m)}

no es transitiva pues allı́ aparecen (m, n) y (n, p) pero falta (m, p); o
sea, mR3 n y nR3 p pero mR 3 p. Si es transitiva

R4 = {(m, m), (m, n), (n, p), (p, q), (m, p), (m, q), (n, q)}

4 La relación

R5 = {(a, a), (a, b), (b, a), (b, b), (a, c), (c, c)}

sobre el conjunto A = {a, b, c} no es conexa porque no contiene el par

(b, c) ni el par (c, b): esto significa que bR
5 c y cR
5 b. Si es conexa

R6 = {(a, b), (a, c), (c, b), (c, c)}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Problema
Si la relación R es dada mediante una representación gráfica o
representación matricial

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Problema
Si la relación R es dada mediante una representación gráfica o
representación matricial
1 ¿Cómo determinar si R es o no es reflexiva?.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Problema
Si la relación R es dada mediante una representación gráfica o
representación matricial
1 ¿Cómo determinar si R es o no es reflexiva?.
2 ¿Cómo determinar si R es o no es antisimétrica?

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Problema
Si la relación R es dada mediante una representación gráfica o
representación matricial
1 ¿Cómo determinar si R es o no es reflexiva?.
2 ¿Cómo determinar si R es o no es antisimétrica?
3 ¿Cómo determinar si R es o no es transitiva?

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Problema
Si la relación R es dada mediante una representación gráfica o
representación matricial
1 ¿Cómo determinar si R es o no es reflexiva?.
2 ¿Cómo determinar si R es o no es antisimétrica?
3 ¿Cómo determinar si R es o no es transitiva?
4 ¿Cómo determinar si R es o no es conexa?

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Orden Parcial. Conjunto Parcialmente Ordenado

Definición: CPO, CTO

Dado un conjunto no vacı́o A, llamaremos Orden Parcial sobre A a
cualquier relación R sobre A que tenga las propiedades de reflexividad,
antisimétrica y transitividad. Cuando también es conexa, se le da el
nombre de orden total.
Un Conjunto Parcialmente Ordenado (CPO) es una estructura o sistema
algebraico [A, R ] formado por un conjunto no vacı́o A y un orden parcial
R sobre A. Cuando el orden es total, se denomina Conjunto Totalmente
Ordenado (CTO).

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
t
s
ec r
q
d
b
a p
CPO CTO CPO NO CPO

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
t
s
ec r
q
d
b
a p
CPO CTO CPO NO CPO

Teorema
Sea [A, R ] un CPO, B un subconjunto no vacı́o de A, R −1 la relación
inversa de R y RB la restricción de R al subconjunto B. Entonces,

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
t
s
ec r
q
d
b
a p
CPO CTO CPO NO CPO

Teorema
Sea [A, R ] un CPO, B un subconjunto no vacı́o de A, R −1 la relación
inversa de R y RB la restricción de R al subconjunto B. Entonces,
1 [A, R −1 ] es un CPO.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
t
s
ec r
q
d
b
a p
CPO CTO CPO NO CPO

Teorema
Sea [A, R ] un CPO, B un subconjunto no vacı́o de A, R −1 la relación
inversa de R y RB la restricción de R al subconjunto B. Entonces,
1 [A, R −1 ] es un CPO.
2 [B, RB ] es un CPO.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
t
s
ec r
q
d
b
a p
CPO CTO CPO NO CPO

Teorema
Sea [A, R ] un CPO, B un subconjunto no vacı́o de A, R −1 la relación
inversa de R y RB la restricción de R al subconjunto B. Entonces,
1 [A, R −1 ] es un CPO.
2 [B, RB ] es un CPO.
La conclusión es verdadera si ponemos CTO en lugar de CPO.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
1 Tomemos A = {a, b, c, d, e} y B = {a, b, d}. El teorema establece
que: al invertir o recortar (“restringir”) un orden parcial, ninguna de
las propiedades se pierde.

e d e d d
R R −1 RB
c c
b b b
a a a
  
reflexiva
 reflexiva
 reflexiva

R es antisimétrica R −1 es antisimétrica RB es antisimétrica
  
transitiva transitiva transitiva
  

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
2

e e
R d R −1 d RB d

c c
b b b

a a a
R es de orden total R −1 es de orden total RB es de orden total

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:
1 r ≤ s, r 6= s

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:
1 r ≤ s, r 6= s
2 no existe x ∈ A − {r , s} que haga verdadera la desigualdad r ≤ x ≤ s.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:
1 r ≤ s, r 6= s
2 no existe x ∈ A − {r , s} que haga verdadera la desigualdad r ≤ x ≤ s.

Nota
Sea [A, ≤] un CPO y r , s ∈ A. Nótese que, r ≺ s es equivalente a que se
satisfagan las siguientes dos condiciones:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:
1 r ≤ s, r 6= s
2 no existe x ∈ A − {r , s} que haga verdadera la desigualdad r ≤ x ≤ s.

Nota
Sea [A, ≤] un CPO y r , s ∈ A. Nótese que, r ≺ s es equivalente a que se
satisfagan las siguientes dos condiciones:
1 r ≤ s, r 6= s

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Comparabilidad. Predecesor Inmediato. Diagrama de Hasse

Definición
En un CPO [A, ≤], tomemos elementos p, q, r , s.
1 Diremos que p es comparable con q (denotado por p comp q) sii
p≤q oq≤p
2 Diremos que r es predecesor inmediato de s (se denota por r ≺ s) sii
se cumplen las siguientes dos condiciones:
1 r ≤ s, r 6= s
2 no existe x ∈ A − {r , s} que haga verdadera la desigualdad r ≤ x ≤ s.

Nota
Sea [A, ≤] un CPO y r , s ∈ A. Nótese que, r ≺ s es equivalente a que se
satisfagan las siguientes dos condiciones:
1 r ≤ s, r 6= s
2 ∃x ∈ A, r ≤ x ≤ s =⇒ x = r o x = s
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
1

e d a comp c, a comp e a ⊀ e porque a ≤ c ≤ e

a comp b, a comp d a ≺ c, a ≺ b
c c ≺ e, b ≺ d
b b comp a, b comp d
a b comp
 c, b comp
 e

  d comp
 a, d comp b
Ahora la
d comp
 c, d comp
 e, etc
relación es ≤

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
2

a comp b, a comp c a≺b

e
a comp d, a comp e a ⊀ c porque a ≤ b ≤ c
d a ⊀ d, a ⊀ e
b comp a, b comp c
c b comp d, b comp e
b
c comp a, c comp b c ≺d
c comp d, c comp e c ⊀ e porque c ≤ d ≤ e
a c ⊀ a porque c
a
d comp a, d comp b
d comp c, d comp d

e comp a, e comp b
e comp c, e comp d

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)
∀a, b, c ∈ A a ≺ b ∧ b ≺ c =⇒ a ⊀ c

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)
∀a, b, c ∈ A a ≺ b ∧ b ≺ c =⇒ a ⊀ c
3 Si A es finito, podemos obtener el diagrama sagital de ≺, a partir del
diagrama sagital de ≤,

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)
∀a, b, c ∈ A a ≺ b ∧ b ≺ c =⇒ a ⊀ c
3 Si A es finito, podemos obtener el diagrama sagital de ≺, a partir del
diagrama sagital de ≤,
Se eliminan todos los lazos del diagrama sagital de ≤

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)
∀a, b, c ∈ A a ≺ b ∧ b ≺ c =⇒ a ⊀ c
3 Si A es finito, podemos obtener el diagrama sagital de ≺, a partir del
diagrama sagital de ≤,
Se eliminan todos los lazos del diagrama sagital de ≤
Se eliminan todas aquellas flechas que dan origen a trángulos las
cuales unen a los extremos de dos flechas contiguas.
c
b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
1 El concepto de predecesor inmediato, da origen a una relación binaria
en A.
2 En la relación predecesor inmediato se tiene que:
a ≺ b =⇒ a ≤ b
∀a ∈ A, a ⊀ a (≺ es antireflexiva)
∀a, b, c ∈ A a ≺ b ∧ b ≺ c =⇒ a ⊀ c
3 Si A es finito, podemos obtener el diagrama sagital de ≺, a partir del
diagrama sagital de ≤,
Se eliminan todos los lazos del diagrama sagital de ≤
Se eliminan todas aquellas flechas que dan origen a trángulos las
cuales unen a los extremos de dos flechas contiguas.
c
b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d
≤

c b
a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación
e d e d
≤

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación Relación
e d e d
≤ ≺

c b c b
a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación Relación
e d e d
≤ ≺

c b c b
a a

Ir al Segundo Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1

Relación Relación
e d e d
≤ ≺

c b c b
a a

Retornar al Diagrama de Hasse

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e
d

c
b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación
≤ e e
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación Relación
≤ e e ≺
d d

c c
b b

a a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación Relación
≤ e e ≺
d d

c c
b b

a a

Continuar

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
2

Relación Relación
≤ e e ≺
d d

c c
b b

a a

Retornar al Diagrama de Hasse

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Convenimiento
Si A es un conjunto finito, de ahora en adelante convenimos para el
diagrama sagital de la relación predecesor inmediato, en omitir la dirección
del arco, por lo cual en lugar de tener un digrafo obtendriamos un grafo.
Para evitar confusiones, estableceremos el sentido de crecimiento
ordenando de abajo hacia arriba de acuerdo al ordenamiento de menor a
mayor que estable la relacion predecesor inmediato, eliminando de esta
manera, el direccionamiento de los arcos.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Convenimiento
Si A es un conjunto finito, de ahora en adelante convenimos para el
diagrama sagital de la relación predecesor inmediato, en omitir la dirección
del arco, por lo cual en lugar de tener un digrafo obtendriamos un grafo.
Para evitar confusiones, estableceremos el sentido de crecimiento
ordenando de abajo hacia arriba de acuerdo al ordenamiento de menor a
mayor que estable la relacion predecesor inmediato, eliminando de esta
manera, el direccionamiento de los arcos.

Definición: Diagrama de Hasse

Sea [A, ≤] un CPO finito, se define el Diagrama de Hasse del CPO [A, ≤],
como la representación sagital de la relación predecesor inmediato ≺.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Los diagramas de Hasse, de las dos CPO de los ejemplos previos serı́an:

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Los diagramas de Hasse, de las dos CPO de los ejemplos previos serı́an:

e d

c b
a
Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Los diagramas de Hasse, de las dos CPO de los ejemplos previos serı́an:

e d c

c b
b
a a
Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2
4 M≺ = Mα − (Mβ )

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2
4 M≺ = Mα − (Mβ )

Construcción del Diagrama de Hasse

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2
4 M≺ = Mα − (Mβ )

Construcción del Diagrama de Hasse

1er Paso Seleccionar elementos con filas nulas en M≺ . Estos elementos
ocuparan el nivel más alto en el Diagrama de Hasse.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2
4 M≺ = Mα − (Mβ )

Construcción del Diagrama de Hasse

1er Paso Seleccionar elementos con filas nulas en M≺ . Estos elementos
ocuparan el nivel más alto en el Diagrama de Hasse.
do
2 Paso Para cada elemento seleccionado en el paso anterior, ver en la
columna que el genera las entradas que sean unos, cada una de
estas entradas el elemento correspondiente a esa fila será un
predecesor inmediato del elemento que generó la columna que
hemos fijado.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Algoritmo para Obtener M≺

Sea [A, ≤] un CPO finito con n elementos.
1 Calcular M≤
2 Calcular Mα = M≤ − In
3 Calcular Mβ = bin(Mα )2
4 M≺ = Mα − (Mβ )

Construcción del Diagrama de Hasse

1er Paso Seleccionar elementos con filas nulas en M≺ . Estos elementos
ocuparan el nivel más alto en el Diagrama de Hasse.
do
2 Paso Para cada elemento seleccionado en el paso anterior, ver en la
columna que el genera las entradas que sean unos, cada una de
estas entradas el elemento correspondiente a esa fila será un
predecesor inmediato del elemento que generó la columna que
hemos fijado.
er
3 Paso A cada uno de los predecesores encontrados en el paso anterior,
aplicarle el 2do Paso.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En N = {1, 2, 3, . . .} el conjunto de los enteros positivos, definimos la
relación de divisibilidad la cual denotaremos por |, como

m | n ⇐⇒ ∃k ∈ N, n = km

Demostrar que la relación de divisibilidad es un orden parcial sobre N.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En N = {1, 2, 3, . . .} el conjunto de los enteros positivos, definimos la
relación de divisibilidad la cual denotaremos por |, como

m | n ⇐⇒ ∃k ∈ N, n = km

Demostrar que la relación de divisibilidad es un orden parcial sobre N.

2 Construya el Diagrama de Hasse del CPO [{4, 20, 5, 10, 25, 1, 2}, |].

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1

 
 
 
 
 
M| = 



 
 
 

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1
4 20 5 10 25 1 2
 
4



 20



 5
M| = 


 10



 25
  1
2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1
4 20 5 10 25 1 2
 
1 1 0 0 0 0 0 4

 0 1 0 0 0 0 0 
 20

 0 1 1 1 1 0 0 
 5
M| = 
 0 1 0 1 0 0 0 
 10

 0 0 0 0 1 0 0 
 25
 1 1 1 1 1 1 1  1
1 1 0 1 0 0 1 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4

 0 1 0 0 0 0 0 
 20 




 0 1 1 1 1 0 0 
 5 



M| = 
 0 1 0 1 0 0 0 
 10 Mα = 




 0 0 0 0 1 0 0 
 25 



 1 1 1 1 1 1 1  1  
1 1 0 1 0 0 1 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0
Paso 3
 
 
 
 
 
Mβ = 



 
 
 

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0
Paso 3
 
0 0 0 0 0 0 0
 0 0 0 0 0 0 0 
 
 0 1 0 0 0 0 0 
 
 0
Mβ =  0 0 0 0 0 0 

 0 0 0 0 0 0 0 
 
 1 1 0 1 1 0 0 
0 1 0 0 0 0 0
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0
Paso 3 Paso 4
   
0 0 0 0 0 0 0
 0 0 0 0 0 0 0   
   
 0 1 0 0 0 0 0   
   
 0
Mβ =  0 0 0 0 0 0 M≺ = 
 
  
 0 0 0 0 0 0 0   
   
 1 1 0 1 1 0 0   
0 1 0 0 0 0 0
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0
Paso 3 Paso 4
   
0 0 0 0 0 0 0 0 1 0 0 0 0 0
 0 0 0 0 0 0 0   0 0 0 0 0 0 0 
   
 0 1 0 0 0 0 0   0 0 0 1 1 0 0 
   
 0
Mβ =  0 0 0 0 0 0 M≺ =  0 1 0 0 0 0 0
 
  
 0 0 0 0 0 0 0   0 0 0 0 0 0 0 
   
 1 1 0 1 1 0 0   0 0 1 0 0 0 1 
0 1 0 0 0 0 0 1 0 0 1 0 0 0
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Paso 1 Paso 2
4 20 5 10 25 1 2
   
1 1 0 0 0 0 0 4 0 1 0 0 0 0 0

 0 1 0 0 0 0 0 
 20 
 0 0 0 0 0 0 0 


 0 1 1 1 1 0 0 
 5 
 0 1 0 1 1 0 0 

M| = 
 0 1 0 1 0 0 0 
 10 Mα = 
 0 1 0 0 0 0 0 


 0 0 0 0 1 0 0 
 25 
 0 0 0 0 0 0 0 

 1 1 1 1 1 1 1  1  1 1 1 1 1 0 1 
1 1 0 1 0 0 1 2 1 1 0 1 0 0 0
Paso 3 Paso 4
   
0 0 0 0 0 0 0 0 1 0 0 0 0 0 4
 0 0 0 0 0 0 0   0 0 0 0 0 0 0  20
   
 0 1 0 0 0 0 0   0 0 0 1 1 0 0  5
   
 0
Mβ =  0 0 0 0 0 0 M≺ =  0 1 0 0 0 0 0 10
 
  
 0 0 0 0 0 0 0   0 0 0 0 0 0 0  25
   
 1 1 0 1 1 0 0   0 0 1 0 0 0 1  1
0 1 0 0 0 0 0 1 0 0 1 0 0 0 2
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s
2 un elemento p ∈ B es elemento maximal de B sii todo x ∈ B cumple
x ≤ p o x comp
 p

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s
2 un elemento p ∈ B es elemento maximal de B sii todo x ∈ B cumple
x ≤ p o x comp
 p
3 un elemento m ∈ B es elemento máximo de B sii todo x ∈ B cumple
x ≤m

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s
2 un elemento p ∈ B es elemento maximal de B sii todo x ∈ B cumple
x ≤ p o x comp
 p
3 un elemento m ∈ B es elemento máximo de B sii todo x ∈ B cumple
x ≤m

Nota

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s
2 un elemento p ∈ B es elemento maximal de B sii todo x ∈ B cumple
x ≤ p o x comp
 p
3 un elemento m ∈ B es elemento máximo de B sii todo x ∈ B cumple
x ≤m

Nota
1 El conjunto formado por todas las cotas superiores de B es denotado
por cs(B), es decir, cs(B) = {s ∈ A/ s es cota superior de B}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Elementos Notables. Cotas Universales. Supremo e Infimo

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que:
1 un elemento s ∈ A es cota superior de B sii todo elemento x ∈ B
cumple x ≤ s
2 un elemento p ∈ B es elemento maximal de B sii todo x ∈ B cumple
x ≤ p o x comp
 p
3 un elemento m ∈ B es elemento máximo de B sii todo x ∈ B cumple
x ≤m

Nota
1 El conjunto formado por todas las cotas superiores de B es denotado
por cs(B), es decir, cs(B) = {s ∈ A/ s es cota superior de B}
2 Se definen cota inferior de B, elemento minimal de B y elemento
mı́nimo de B en forma similar, sólo hay que colocar s ≤ x en lugar de
x ≤ s (y p ≤ x en lugar de x ≤ p, m ≤ x en lugar de x ≤ m).
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
El diagrama muestra un CPO, en el cual seleccionamos B = {c, d, e, i, h},
al cual le vamos a buscar todas las cotas superiores, las cotas inferiores,
todos los elementos maximales, todos los elementos minimales, todos los
elementos máximos y todos los elementos mı́nimos.
p n

k l m

j i h g

d e f

c b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
El diagrama muestra un CPO, en el cual seleccionamos B = {c, d, e, i, h},
al cual le vamos a buscar todas las cotas superiores, las cotas inferiores,
todos los elementos maximales, todos los elementos minimales, todos los
elementos máximos y todos los elementos mı́nimos.
p n

k l m

j i h g

d e f

c b

Continuar

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
El diagrama muestra un CPO, en el cual seleccionamos B = {c, d, e, i, h},
al cual le vamos a buscar todas las cotas superiores, las cotas inferiores,
todos los elementos maximales, todos los elementos minimales, todos los
elementos máximos y todos los elementos mı́nimos.
p n

k l m

j i h g

d e f

c b

Retornar

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

2◦ Elementos maximales de B son: i, h.

Nótese que: c ≤ i, d ≤ i, e ≤ i, i ≤ i, h comp
 i (vea la definición de
elemento maximal), c ≤ h, e ≤ h, h ≤ h, d comp  h, i comp
 h.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

2◦ Elementos maximales de B son: i, h.

Nótese que: c ≤ i, d ≤ i, e ≤ i, i ≤ i, h comp
 i (vea la definición de
elemento maximal), c ≤ h, e ≤ h, h ≤ h, d comp  h, i comp
 h.

3◦ No hay un elemento z ∈ B que cumpla x ≤ z para todo x ∈ B; en

consecuencia, no hay elemento máximo de B

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

2◦ Elementos maximales de B son: i, h.

Nótese que: c ≤ i, d ≤ i, e ≤ i, i ≤ i, h comp
 i (vea la definición de
elemento maximal), c ≤ h, e ≤ h, h ≤ h, d comp  h, i comp
 h.

3◦ No hay un elemento z ∈ B que cumpla x ≤ z para todo x ∈ B; en

consecuencia, no hay elemento máximo de B

4◦ Cotas Inferiores de B son: c, a (ci(B) = {a, c})

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

2◦ Elementos maximales de B son: i, h.

Nótese que: c ≤ i, d ≤ i, e ≤ i, i ≤ i, h comp
 i (vea la definición de
elemento maximal), c ≤ h, e ≤ h, h ≤ h, d comp  h, i comp
 h.

3◦ No hay un elemento z ∈ B que cumpla x ≤ z para todo x ∈ B; en

consecuencia, no hay elemento máximo de B

4◦ Cotas Inferiores de B son: c, a (ci(B) = {a, c})

5◦ Elementos minimales de B son: c (único). Nótese que:

c ≤ c, c ≤ e, c ≤ d, c ≤ i, c ≤ h

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
1◦ En el diagrama vemos que c ≤ d, d ≤ j (por transitividad, c ≤ j),
pero j comp
 i, j comp
 h. Por lo tanto, j no es cota superior de B.
cs(B) = {l, n, p}

2◦ Elementos maximales de B son: i, h.

Nótese que: c ≤ i, d ≤ i, e ≤ i, i ≤ i, h comp
 i (vea la definición de
elemento maximal), c ≤ h, e ≤ h, h ≤ h, d comp  h, i comp
 h.

3◦ No hay un elemento z ∈ B que cumpla x ≤ z para todo x ∈ B; en

consecuencia, no hay elemento máximo de B

4◦ Cotas Inferiores de B son: c, a (ci(B) = {a, c})

5◦ Elementos minimales de B son: c (único). Nótese que:

c ≤ c, c ≤ e, c ≤ d, c ≤ i, c ≤ h

6◦ Elementos mı́nimos de B: c (único).

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.
3 B esta acotado cuando tiene los dos tipos de cotas.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.
3 B esta acotado cuando tiene los dos tipos de cotas.
Teorema
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.
3 B esta acotado cuando tiene los dos tipos de cotas.
Teorema
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A.
1 Si B tiene elemento máximo, este es único.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.
3 B esta acotado cuando tiene los dos tipos de cotas.
Teorema
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A.
1 Si B tiene elemento máximo, este es único.
2 Si B tiene elemento mı́nimo, este es único.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A. Diremos que
1 B esta acotado superiormente si B tiene cotas superiores, al menos
una.
2 B esta acotado inferiormente si B tiene cotas inferiores, al menos una.
3 B esta acotado cuando tiene los dos tipos de cotas.
Teorema
Sea [A, ≤] un CPO y B un subconjunto no vacı́o de A.
1 Si B tiene elemento máximo, este es único.
2 Si B tiene elemento mı́nimo, este es único.
Nota
Cuando el CPO tiene un elemento máximo (único por supuesto), se le da
el nombre de COTA SUPERIOR UNIVERSAL y se le denota por I ;
similarmente, cuando el CPO tiene un elemento mı́nimo, a este elemento
se le llama COTA INFERIOR UNIVERSAL y se le denota por . Nótese
que el CPO esta acotado cuando tiene las dos cotas universales: , I .
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
1 El CPO del ejemplo anterior no es acotado porque, aunque si tiene
cota inferior universal  = a, no tiene cota superior universal.
Ir al Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 El CPO del ejemplo anterior no es acotado porque, aunque si tiene
cota inferior universal  = a, no tiene cota superior universal.
Ir al Ejemplo

2 En los dos diagramas anexos encontramos un CPO acotado y otro

que sólo tiene cota superior universal.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 El CPO del ejemplo anterior no es acotado porque, aunque si tiene
cota inferior universal  = a, no tiene cota superior universal.
Ir al Ejemplo

2 En los dos diagramas anexos encontramos un CPO acotado y otro

que sólo tiene cota superior universal.

j k

h g j h

d e f d g

c b e f

a c b a
I = j,  = a I =k

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema: Principio de la Dualidad

Dado un CPO X = [A, ≤], consideremos su CPO dual Y = [A, (≤)−1 ]. Si B es un
subconjunto no vacı́o de A, entonces es verdad que:
 

 cota superior cota inferior

w ∈ A es elemento maximal de B en X ⇐⇒ w es elemento minimal de B en Y
 
elemento máximo elemento mı́nimo
 

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema: Principio de la Dualidad

Dado un CPO X = [A, ≤], consideremos su CPO dual Y = [A, (≤)−1 ]. Si B es un
subconjunto no vacı́o de A, entonces es verdad que:
 

 cota superior cota inferior

w ∈ A es elemento maximal de B en X ⇐⇒ w es elemento minimal de B en Y
 
elemento máximo elemento mı́nimo
 

Nota
Este teorema establece que invertir el orden parcial en el CPO produce, en los
elementos notables superiores, el efecto de convertirlos en elementos notables
inferiores (y viceversa). Esa inversión del orden se debe a que

a ≤ b en X =⇒ b (≤)−1 a en Y

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En los dos diagramas anexos vemos el efecto de invertir el orden.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En los dos diagramas anexos vemos el efecto de invertir el orden.

CPO [A, ≤] = X
l =I

j k

h g f

d e

c a b
no hay cota inferior universal
pero si cota superior universal

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En los dos diagramas anexos vemos el efecto de invertir el orden.

CPO [A, ≤] = X CPO dual [A, (≤)−1 ] = Y

l =I c a b

j k d e

h g f h g f

d e j k

c a b l =
no hay cota inferior universal no hay cota superior universal
pero si cota superior universal pero si cota inferior universal

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
En un CPO [A, ≤], tomemos un subconjunto no vacı́o B. Sea z un
elemento de A, diremos que z es una cota superior minimal de B sii z es
un elemento minimal entre las cotas superiores del subconjunto B.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
En un CPO [A, ≤], tomemos un subconjunto no vacı́o B. Sea z un
elemento de A, diremos que z es una cota superior minimal de B sii z es
un elemento minimal entre las cotas superiores del subconjunto B.

Definición
En un CPO [A, ≤], tomemos un subconjunto no vacı́o B. Sea z un
elemento de A, diremos que z es una cota inferior maximal de B sii z es
un elemento maximal entre las cotas inferiores del subconjunto B.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición
En un CPO [A, ≤], tomemos un subconjunto no vacı́o B. Sea z un
elemento de A, diremos que z es una cota superior minimal de B sii z es
un elemento minimal entre las cotas superiores del subconjunto B.

Definición
En un CPO [A, ≤], tomemos un subconjunto no vacı́o B. Sea z un
elemento de A, diremos que z es una cota inferior maximal de B sii z es
un elemento maximal entre las cotas inferiores del subconjunto B.

Nota
Denotaremos por csm(B) al conjunto formado por todas las cotas
superiores minimales de B y por cim(B) al conjunto formado por todas las
cotas inferiores maximales de B.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados
Ejemplo 1
En el CPO que se muestra en la figura anexa,
p n

k l m

j i h g

d e f

c b

a
Para el conjunto B = {c, d, e, h, i} tenemos que:
cs(B) = {l, n, p} y csm(B) = {l}
ci(B) = {a, c} y cim(B) = {c}
Para el conjunto B 0 = {e, h, i, l} resulta que
cs(B 0 ) = {l, n, p} y csm(B 0 ) = {l}
ci(B 0 ) = {a, b, c, e} y cim(B 0 ) = {e}
Prof. Ismael Huerta Tema IIReticulados
 Reticulados
Ejemplo 2
Respecto al CPO de la figura anexa,
l m

k h g

d e f

c b

a
Resulta que: Si C = {b, c, e, h, m, l}, entonces
cs(C ) = ∅ y csm(C ) = ∅
ci(C ) = {a} y cim(C ) = {a}
Si C 0 = {b, e, f }, entonces
cs(C 0 ) = {h, g , m, l} y csm(C 0 ) = {h, g }
ci(C 0 ) = {a, b} y cim(C 0 ) = {b}
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Nota
En los dos ejemplos anteriores encontramos casos variados. El conjunto
csm(B) puede resultar vacı́o (0 elementos), unitario (1 elemento) o con
más de un elemento. Con cim(B) se presentan los mismos casos.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En los dos ejemplos anteriores encontramos casos variados. El conjunto
csm(B) puede resultar vacı́o (0 elementos), unitario (1 elemento) o con
más de un elemento. Con cim(B) se presentan los mismos casos.

Definición
Cuando csm(B) es un conjunto unitario, al único elemento que lo forma lo
llamaremos SUPREMO de B y lo denotaremos por sup(B); similarmente,
cuando cim(B) es unitario, al único elemento que cim(B) contiene lo
llamaremos INFIMO de B y lo denotaremos por ı́nf(B).

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:
existe supremo de B = {c, d, e, h, i} y también el ı́nfimo de B. Dicho
valores son: sup(B) = l,ı́nf(B) = c.

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:
existe supremo de B = {c, d, e, h, i} y también el ı́nfimo de B. Dicho
valores son: sup(B) = l,ı́nf(B) = c.
También el conjunto B 0 = {e, h, i, l} tiene supremo e ı́nfimo, a saber:
sup(B 0 ) = l,ı́nf(B 0 ) = e.

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:
existe supremo de B = {c, d, e, h, i} y también el ı́nfimo de B. Dicho
valores son: sup(B) = l,ı́nf(B) = c.
También el conjunto B 0 = {e, h, i, l} tiene supremo e ı́nfimo, a saber:
sup(B 0 ) = l,ı́nf(B 0 ) = e.

2 En el Ejemplo 2, vemos que:

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:
existe supremo de B = {c, d, e, h, i} y también el ı́nfimo de B. Dicho
valores son: sup(B) = l,ı́nf(B) = c.
También el conjunto B 0 = {e, h, i, l} tiene supremo e ı́nfimo, a saber:
sup(B 0 ) = l,ı́nf(B 0 ) = e.

2 En el Ejemplo 2, vemos que:

el conjunto C = {b, c, e, h, l, m} no tiene supremo porque
csm(C ) = ∅, pero si tiene ı́nfimo: ı́nf(C ) = a.

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 En el Ejemplo 1, vimos que:
existe supremo de B = {c, d, e, h, i} y también el ı́nfimo de B. Dicho
valores son: sup(B) = l,ı́nf(B) = c.
También el conjunto B 0 = {e, h, i, l} tiene supremo e ı́nfimo, a saber:
sup(B 0 ) = l,ı́nf(B 0 ) = e.

2 En el Ejemplo 2, vemos que:

el conjunto C = {b, c, e, h, l, m} no tiene supremo porque
csm(C ) = ∅, pero si tiene ı́nfimo: ı́nf(C ) = a.
Tampoco C 0 tiene supremo porque el conjunto csm(C 0 ) tiene más de
un elemento, pero C 0 si tiene ı́nfimo, a saber ı́nf(C 0 ) = b.

Ir al Ejemplo 1 Ir al Ejemplo 2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B y (2◦ ) ∀w 0 ∈ ci(B) : w 0 ≤ w

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B y (2◦ ) ∀w 0 ∈ ci(B) : w 0 ≤ w
Resumen:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B y (2◦ ) ∀w 0 ∈ ci(B) : w 0 ≤ w
Resumen:
z = sup(B) ⇐⇒ [∀b ∈ B : b ≤ z] y [∀z 0 ∈ cs(B) : z ≤ z 0 ]

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B y (2◦ ) ∀w 0 ∈ ci(B) : w 0 ≤ w
Resumen:
z = sup(B) ⇐⇒ [∀b ∈ B : b ≤ z] y [∀z 0 ∈ cs(B) : z ≤ z 0 ]

w = ı́nf(B) ⇐⇒ [∀b ∈ B : w ≤ b] y [∀w 0 ∈ cs(B) : w 0 ≤ w ]

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Es importante notar que si un subconjunto B de un CPO [A, ≤] tiene

supremo, entonces ese elemento supremo es cota superior de B y es el
único elemento minimal de las cotas superiores. Es decir, si sup(B) = z
entonces z satisface
(1◦ ) b ≤ z, ∀b ∈ B y (2◦ ) ∀z 0 ∈ cs(B) : z ≤ z 0
Similarmente, si w es el ı́nfimo de B, entonces w cumple las condiciones
siguientes:
(1◦ ) w ≤ b, ∀b ∈ B y (2◦ ) ∀w 0 ∈ ci(B) : w 0 ≤ w
Resumen:
z = sup(B) ⇐⇒ [∀b ∈ B : b ≤ z] y [∀z 0 ∈ cs(B) : z ≤ z 0 ]

w = ı́nf(B) ⇐⇒ [∀b ∈ B : w ≤ b] y [∀w 0 ∈ cs(B) : w 0 ≤ w ]

Comentario: no nos interesamos en encontrar supremo e ı́nfimo de todos
los subconjuntos de los CPO, sólo nos ocuparemos de subconjuntos de la
forma {x, y } con x = y o con x 6= y . A tal efecto, el resultado siguiente
facilitará el trabajo.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Principio de Consistencia
En un CPO [A, ≤], tomemos elementos a, b. Entonces es verdad que:

a ≤ b ⇐⇒ sup({a, b}) = b ⇐⇒ ı́nf({a, b}) = a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Principio de Consistencia
En un CPO [A, ≤], tomemos elementos a, b. Entonces es verdad que:

a ≤ b ⇐⇒ sup({a, b}) = b ⇐⇒ ı́nf({a, b}) = a

Nota 1
Usualmente al trabajar con parejas {a, b}, escribiremos:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Principio de Consistencia
En un CPO [A, ≤], tomemos elementos a, b. Entonces es verdad que:

a ≤ b ⇐⇒ sup({a, b}) = b ⇐⇒ ı́nf({a, b}) = a

Nota 1
Usualmente al trabajar con parejas {a, b}, escribiremos:
a ∨ b en lugar de sup({a, b})

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Principio de Consistencia
En un CPO [A, ≤], tomemos elementos a, b. Entonces es verdad que:

a ≤ b ⇐⇒ sup({a, b}) = b ⇐⇒ ı́nf({a, b}) = a

Nota 1
Usualmente al trabajar con parejas {a, b}, escribiremos:
a ∨ b en lugar de sup({a, b})
a ∧ b en lugar de ı́nf({a, b})

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Principio de Consistencia
En un CPO [A, ≤], tomemos elementos a, b. Entonces es verdad que:

a ≤ b ⇐⇒ sup({a, b}) = b ⇐⇒ ı́nf({a, b}) = a

Nota 1
Usualmente al trabajar con parejas {a, b}, escribiremos:
a ∨ b en lugar de sup({a, b})
a ∧ b en lugar de ı́nf({a, b})

Nota 2
El principio de consistencia establece que al tomar una pareja de
elementos comparables, el menor de ellos es el ı́nfimo (entre los dos) y el
más grande es el supremo (entre los dos).

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f },

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f }, cs({g , f }) = ∅,

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f }, cs({g , f }) = ∅, csm({g , f }) = ∅,
por consiguiente no existe supremo de {g , f };

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f }, cs({g , f }) = ∅, csm({g , f }) = ∅,
por consiguiente no existe supremo de {g , f };
ci({g , f }) = {, a, b, d},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f }, cs({g , f }) = ∅, csm({g , f }) = ∅,
por consiguiente no existe supremo de {g , f };
ci({g , f }) = {, a, b, d}, cim({g , f }) = {d},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el CPO, cuyo diagrama de Hasse es
g f

c d e

b a


Por el Principio de la Consistencia, se tiene que:
1) ≤ a =⇒  ∧a = ,  ∨ a = a 2) ≤ b =⇒  ∧b = ,  ∨ b = b
3)b ≤ d =⇒ b ∧ d = b, b ∨ d = d 4)b ≤ f =⇒ b ∧ f = b, b ∨ f = f
En cuanto a elementos no comparables, tenemos que:
para {g , f }, cs({g , f }) = ∅, csm({g , f }) = ∅,
por consiguiente no existe supremo de {g , f };
ci({g , f }) = {, a, b, d}, cim({g , f }) = {d},
ası́ que d = ı́nf {g , f } = g ∧ f
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación
para {c, d},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g },

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g }

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

∴ c ∨a =g y c ∧a =

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

∴ c ∨a =g y c ∧a =

para {b, e},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

∴ c ∨a =g y c ∧a =

para {b, e}, cs({c, e}) = {f }

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

∴ c ∨a =g y c ∧a =

para {b, e}, cs({c, e}) = {f } y ci({b, e}) = {},

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
para {c, d}, cs({c, d}) = {g }, csm({g , f }) = {g },
por tanto existe supremo de {c, d}, c ∨ d = g
ci({c, d}) = {, b}, cim({c, d}) = {b},
por tanto b = c ∧ d

para {c, e}, cs({c, e}) = ∅ (no hay supremo) y

ci({c, e}) = {}, ∴  = c ∨ e

para {c, a}, cs({c, a}) = {g } y ci({c, a}) = {},

∴ c ∨a =g y c ∧a =

para {b, e}, cs({c, e}) = {f } y ci({b, e}) = {},

∴ b∨e =f y b∧e =

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Una manera de organizar el trabajo de buscar supremo e ı́nfimo a cada una
de las parejas de elementos del CPO, es la de construir una tabla para
supremo y otra para ı́nfimo, como vemos a continuación (respecto al CPO
del diagrama anexo).
I

j k

f g h

e d c

a b


Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación
sup  a b c d e f g h j k I
  a b c d e f g h j k I
a a a d ∗ d e f g h j k I
b b d b c d ∗ f g h j k I
c c ∗ c c ∗ g j g h j k I
d d d d ∗ d ∗ f g h j k I
e e e ∗ g ∗ e f g k j k I
f f f f j f f f j I j I I
g g g g g g g j g k j k I
h h h h h h k I k h I k I
j j j j j j j j j I j I I
k k k k k k k I k k I k I
I I I I I I I I I I I I I
[∗ significa que “que no hay” o no existe]

Observemos que algunas parejas no tienen supremo.

Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación
ı́nf  a b c d e f g h j k I
            
a  a   a a a a a a a a
b   b b b  b b b b b b
c   b c b  b c c c c c
d  a b b d a d d d d d d
e  a   a e e e a e e e
f  a b b d e f ∗ d f ∗ f
g  a b c d e ∗ g ∗ g g g
h  a b c d a d ∗ h ∗ h h
j  a b c d e f g ∗ j g j
k  a b c d e ∗ g h g k k
I  a b c d e f g h j k I

[∗ significa que “que no hay” o no existe]

Observemos que algunas parejas no tienen ı́nfimo. Encontramos casos en
los que cada pareja tiene tanto supremo como ı́nfimo.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Reticulados
Sea [A, ≤] un CPO. Diremos que [A, ≤] es un reticulado si cada pareja
{x, y } tiene tanto supremo como e ı́nfimo.
Ejemplo
1 Los últimos cuatro ejemplos son CPO que no son reticulados.
2 Los siguientes CPO si son reticulados

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Teorema: Propiedades de las Operaciones Binarias: ∨, ∧

Sea [A, ≤] un reticulado, entonces se cumple que:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Teorema: Propiedades de las Operaciones Binarias: ∨, ∧

Sea [A, ≤] un reticulado, entonces se cumple que:
1 ∀a ∈ A, a ∨ a = a, a ∧ a = a (Propiedad de Idempotencia)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Teorema: Propiedades de las Operaciones Binarias: ∨, ∧

Sea [A, ≤] un reticulado, entonces se cumple que:
1 ∀a ∈ A, a ∨ a = a, a ∧ a = a (Propiedad de Idempotencia)

2 ∀a, b ∈ A, a ∨ b = b ∨ a, a ∧ b = b ∧ a (Propiedad Conmutativa)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Teorema: Propiedades de las Operaciones Binarias: ∨, ∧

Sea [A, ≤] un reticulado, entonces se cumple que:
1 ∀a ∈ A, a ∨ a = a, a ∧ a = a (Propiedad de Idempotencia)

2 ∀a, b ∈ A, a ∨ b = b ∨ a, a ∧ b = b ∧ a (Propiedad Conmutativa)

3 ∀a, b, c ∈ A a ∨ (b ∨ c) = (a ∨ b) ∨ c, a ∧ (b ∧ c) = (a ∧ b) ∧ c
(Propiedad Asociativa)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
En un CPO [A, ≤] que sea un reticulado, cada pareja {x, y } tendrá tanto
un único supremo como un único ı́nfimo, lo cual significa que tanto el
supremo como el ı́nfimo son operaciones binarias.

Teorema: Propiedades de las Operaciones Binarias: ∨, ∧

Sea [A, ≤] un reticulado, entonces se cumple que:
1 ∀a ∈ A, a ∨ a = a, a ∧ a = a (Propiedad de Idempotencia)

2 ∀a, b ∈ A, a ∨ b = b ∨ a, a ∧ b = b ∧ a (Propiedad Conmutativa)

3 ∀a, b, c ∈ A a ∨ (b ∨ c) = (a ∨ b) ∨ c, a ∧ (b ∧ c) = (a ∧ b) ∧ c
(Propiedad Asociativa)

4 ∀a, b ∈ A, a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a (Propiedad Absorción)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
1 Debido a la relación ≤ es reflexiva, tenemos que a ≤ a, ∀a ∈ A.
Ahora, el Principio de la Consistencia nos permite asegurar que

a = a ∧ a y a = a ∨ a, ∀a ∈ A

2 De la igualdad {a, b} = {b, a} resulta que cs({a, b}) = cs({b, a}) y

csm({a, b}) = csm({b, a}).
Pero csm({a, b}) = {a ∨ b} y csm({b, a}) = {b ∨ a} porque [A, ≤]
es un reticulado (esto es, que cada pareja tiene supremo, el cual es la
única cota superior minimal).
Ası́ concluimos que, {a ∨ b} = csm({a, b}) = csm({b, a}) = {b ∨ a},
en consecuencia,
a∨b =b∨a
Similarmente se demuestra que a ∧ b = b ∧ a).

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
3 Si x = a ∨ (b ∨ c) y z = (a ∨ b) ∨ c, entonces debemos comprobar que x = z.
Para lograrlo recurriremos a la antisimetrı́a de ≤, ası́ que comprobaremos que
x ≤ z y que z ≤ x. Ası́
x = a ∨ (b ∨ c) =⇒ x ∈ cs({a, b ∨ c})(porque supremo es cota superior mı́nima)
=⇒ a ≤ x, b ∨ c ≤ x (definición de cota superior)
=⇒ a ≤ x, b ≤ b ∨ c ≤ x, c ≤ b ∨ c ≤ x (b ∨ c ∈ cs({b, c}))
=⇒ a ≤ x, b ≤ x, c ≤ x (transitividad de ≤ )
=⇒ x ∈ cs({a, b}), c ≤ x (definición de cota superior)
=⇒ a ∨ b ≤ x, c ≤ x (porque a ∨ b es cota sup. mı́nima de {a, b})
=⇒ x ∈ cs({a ∨ b, c}) (por definición de cota superior)
=⇒ (a ∨ b) ∨ c ≤ x (supremo es mı́nima entre cotas superiores)
=⇒ z ≤ x (definición de z)
Similarmente se comprueba que x ≤ z.
4 Ejercicio: demostrar la propiedad de absorción (imitar la anterior)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Sea [X , ∗1 , ∗2 ] una estructura constituida por un conjunto no vacı́o X y
dos operaciones binarias sobre X : ∗1 , ∗2 .
Si estas dos operaciones tienen las 4−propiedades: idempotencia,
conmutatividad, asociatividad y absorción, entonces a partir de ∗1 , y ∗2 se
pueden construir un orden parcial ≤ sobre X , de manera que
1 [X , ≤] es un reticulado
2 ∀p, q ∈ X se cumple que p ∨ q = p ∗1 q
3 ∀p, q ∈ X se cumple que p ∧ q = p ∗2 q.
De este Teorema podemos “extraer” un COROLARIO que hace el papel
de una segunda definición de RETICULADO, como vemos a continuación.
Corolario
Si ∗1 y ∗2 son operaciones binarias sobre un conjunto no vacı́o X y cada
una de ellas dos tiene las cuatro propiedades idempotencia,
conmutatividad, asociatividad y absorción, entonces [X , ∗1 , ∗2 ] es un
reticulado.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
1 Si S es cualquier conjunto (puede ser vacı́o, o un conjunto finito, o un
conjunto infinito), entonces P(S) = {Y  Y es subconjunto de S}
es una colección no vacı́a; además de teorı́a de conjuntos sabemos
que ∪, ∩ son operaciones sobre P(S) (porque al tomar Y , Z ∈ P(S)
se “pueden calcular” Y ∪ Z , Y ∩ Z y ambos resultados permanecen
como elementos de P(S)). También se sabe que

∀ Y ∈ P(S) es verdad que Y ∪Y = Y, Y ∩Y = Y

∀ Y , Z ∈ P(S) es verdad que Y ∪Z = Z ∪Y, Y ∩Z = Z ∩Y
∀ Y , Z , W ∈ P(S) es verdad que (Y ∪ Z ) ∪ W = Y ∪ (Z ∪ W ), (Y ∩ Z
∀ Y , Z ∈ P(S) es verdad que Y ∪ (Y ∩ Z ) = Y , Y ∩ (Y ∪ Z ) = Y

El Corolario anterior nos permite concluir que [P(S), ∪, ∩ ] es un

reticulado.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
2 El conjunto N = {1, 2, 3, . . . , } es no vacı́o, y mcm (mı́nimo común
múltiplo), mcd (máximo común divisor) son operaciones sobre N. Con
un trabajo muy laborioso, aunque muy sencillo, se comprueba que
mcm y mcd poseen las 4-propiedades requeridas en el Corolario
anterior, ası́ que podemos concluir que [N, mcm, mcd ] es un
reticulado.
3 Aunque el conjunto R es no vacı́o, resulta que mcm y mcd NO SON
operaciones sobre R, de manera que [R, mcm, mcd ] no es un
reticulado. Pero [R, mı́n, máx] si es un reticulado.
(máx(a, b) es el mayor de los números a, b; similarmente, mı́n(a, b) es
el menor de los números. Ası́: máx(3, 5) = 5, mı́n(3, 5) = 3)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Isomorfismos. Subreticulados. Reticulados Distributivos.

Complementos

Definición
Supongamos que L1 = [A1 , ∨1 , ∧1 ] y L2 = [A2 , ∨2 , ∧2 ] son reticulados y
que h : A1 −→ A2 es una aplicación. Diremos que:
1 la aplicación h preserva las operaciones si se cumple que

h(x1 ∨1 x2 ) = h(x1 ) ∨2 h(x2 ) y h(x1 ∧1 ) = h(x1 ) ∧2 h(x2 )

2 h es un isomorfismo entre reticulados ⇐⇒ h es biyectiva y preserva

las operaciones.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Subreticulado
Supongamos qu L1 = [A1 , ∨, ∧] es un reticulado. Si L2 = [B, ∨0 , ∧0 ]
también es un reticulado, diremos que L2 es un subreticulado deL1 si y
sólo si se cumple que:
1 B ⊆A
2 x ∨0 x 0 = x ∨ x 0 ∀x, x 0 ∈ B
3 x ∧0 x 0 = x ∧ x 0 ∀x, x 0 ∈ B

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
A continuación encontramos 4 diagramas. El primero, el segundo y el
tercero representan 3-reticulados, el cuarto no.

g g g g
L L1 L2 D
e f e f e f f
c c c

d b d b b

a a a
Conjunto Conjunto Conjunto Conjunto
A = {a, b, c, d, e, f ,Bg1}= {a, b, d, e, f , gB}2 = {a, c, e, f , gB}3 = {b, c, f , g }

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación
L1 es reticulado y B1 ⊆ A pero en L1 es e ∧1 f = a y en L es
e ∧ f = c 6= e ∧1 f (no cumple (2))
∴ L1 NO ES SUBRETICULADO de L L2 es reticulado, B2 ⊆ A:

e ∧2 f = c = e ∧ f , e ∨2 f = g = e ∨ f , para toda pareja x, x 0 ∈ B2 se

comprueba que x ∨2 x 0 = x ∨ x 0 , x ∧2 x 0 = x ∧ x 0 . Ası́ que L2 si es
subreticulado de L. La figura D representa un CPO que no es un

reticulado, por eso no puede ser subreticulado de L

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Supongamos que L = [A, ∨, ∧] es un reticulado, que B 6= ∅ es un
subconjunto de A y que ∨B , ∧B son las restricciones de ∨, ∧ al
subconjunto B. Entonces se cumple que:

[B, ∨B , ∧B ] es un subreticulado de L ⇐⇒ las operaciones ∨, ∧ son cerradas en e

(esto es, que x ∨ x 0 , x ∧ x 0 ∈ B, ∀x, x 0 ∈ B)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En la figura anexa vemos un reticulado L, cuyo conjunto es
A = {m, n, p, q, r , s, t}.
s

r t

p
q n

m
Si tomamos el subconjunto B1 = {n, q, r , t} vemos que
r ∨t =s ∈
/ B1 r ∧t =m ∈
/ B1
n∨q =p ∈ / B1 n∧q =m ∈/ B1

Ası́ que las operaciones ∨, ∧ no son cerradas en B1 .

Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación
Debido a eso, B1 no sirve para construir un subreticulado de L. Por el
contrario, al tomar el subconjunto B2 = {m, n, p, q} y el subconjunto
B3 = {q, p, r , s} se puede comprobar que las operaciones ∨, ∧ de L son
cerradas en ambos subconjuntos. En consecuencia, con B2 y B3 si se
obtienen subreticulados de L

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Distributividad
Un reticulado L = [A, ∨, ∧] es distributivo ⇐⇒ las igualdades
x ∨ (y ∧ z) = (x ∨ y ) ∧ (x ∨ z), x ∧ (y ∨ z) = (x ∧ y ) ∨ (x ∧ z) para todos
los valores que puedan tomar las variables x, y , z sobre el conjunto A.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Ya vimos que si S es cualquier conjunto, entonces [P(S), ∪, ∩] es un
reticulado. De teorı́a de conjuntos sabemos que las igualdades
Z ∪ (W ∩ T ) = (Z ∪ W ) ∩ (Z ∪ T ) y Z ∩ (W ∪ T ) = (Z ∩ W ) ∪ (Z ∩ T )
son verdaderas para cualquier Z , W , T ∈ P(S)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados
Ejemplo
El diagrama anexo muestra un reticulado con 5-elementos.
e

d c b

¿Cuántas asignaciones de valores podemos hacer, para las 3-variables

x, y , z, con estos 5 elementos?
x y z
a a
b
b c
d
a c e
d
e
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Continuación
Asignar valores a x (5-valores posibles). Con x fijo (un único valor),
asignarle a y (5 alternativas). Con x, y fijos, asignarle valor a z (5
alternativas). Total: 53 = 125.
En cada una de las 125 asignaciones posibles, debemos calcular
J = x ∨ (y ∧ z), K = (x ∨ y ) ∧ (x ∨ z), H = x ∧ (y ∨ z), L = (x ∧ y ) ∨ (x ∧ Z )
y chequear si coinciden J = K , H = L.
Ambas coincidencias deben darse, en las 125 asignaciones posibles, para
poder concluir que el reticulado si es distributivo (al fallar una de las
igualdades, se concluye que el reticulado no es distributivo). En nuestro
ejemplo vemos que:
(
J = x ∨ (y ∧ z) = b ∨ (c ∧ d) = b ∨ a = b
x = b, y = c, z = d =⇒
K = (x ∨ y ) ∧ (x ∨ z) = (b ∨ c) ∧ (b ∨ d) = e ∧ e =

de manera que J 6= K y el reticulado no es distributivo

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema: Criterio para distributividad

Un reticulado L es distributivo ⇐⇒ ningún subreticulado de L es
isomorfo a alguno de los dos reticulados siguientes:

F1 F2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En el diagrama anexo no es difı́cil ver que el subconjunto
B = {a, d, e, g , b} “parece” proporcionarnos la figura F2 . Al hacer la
comprobación, se podrá concluir que las operaciones ∨, ∧ del reticulado
son cerradas sobre el conjunto B. Esto significa que L1 si tiene un
subreticulado isomorfo a F2 : en consecuencia, L1 no es distributivo.
g
L1 L2 L3
e f
c
d b
a

Por el contrario L2 y L3 si son distributivos (¿por qué?)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Complemento
En un reticulado L = [A, ∨, ∧] que sea acotado, tomemos elementos p, q

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Complemento
En un reticulado L = [A, ∨, ∧] que sea acotado, tomemos elementos p, q
1 Diremos que q es un complemento de p si cumple:

p ∧ q = , p ∨ q = I

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Complemento
En un reticulado L = [A, ∨, ∧] que sea acotado, tomemos elementos p, q
1 Diremos que q es un complemento de p si cumple:

p ∧ q = , p ∨ q = I

2 Diremos que el reticulado es complementado ⇐⇒ todo elemento p

de L posee, al menos, un complemento

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el diagrama anexo,

I
L1
b a

En el reticulado L1 podemos ver que

 ∧I =  ∨I =I
a∧b = a∨b =I

en consecuencia I es un complemento de , b es un complemento de a.

(Nótese que I ∧  = , I ∨  = I , b ∧ a = , b ∨ a = I , de manera que 
es un complemento de I , a es un complemento de b).

∴ L1 es un reticulado complementado
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
Dado el diagrama

I
L2
m n t

En L2 vemos que m ∧ n = , m ∨ n = I , m ∧ t = , m ∨ t = I ; esto

significa que tanto n como t son complementos de m.
Nótese que, en L2 , la cota universal I es un complemento de  y  es un
complemento de I .

∴ L2 es un reticulado complementado

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
Dado el diagrama,

I
L3 w
r s
u


En L3 , también es verdad que  ∧ I = ,  ∨ I = I (o sea, I es un

complemento de ) y que I ∧  = , I ∨  = I (ası́ que  es un
complemento de I ); pero ninguno de los elementos r , s, u, w tiene
complemento.

En consecuencia, el reticulado L3 no es complementado.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Demostración.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Demostración.

q es un complemento de p

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Demostración.

q es un complemento de p =⇒ p ∧ q = , p ∨ q = I (ver † )

† por la definición de complemento.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Demostración.

q es un complemento de p =⇒ p ∧ q = , p ∨ q = I (ver † )
=⇒ q ∧ p = , q ∨ p = I (ver ‡ )

† por la definición de complemento.

‡ por la conmutatividad de ∨, ∧.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Propiedades del Complemento

Teorema
Si p, q son elementos de un reticulado acotado L = [A, ∨, ∧] y q es un
complemento de p, entonces p es un complemento de q.

Demostración.

q es un complemento de p =⇒ p ∧ q = , p ∨ q = I (ver † )
=⇒ q ∧ p = , q ∨ p = I (ver ‡ )
=⇒ p es un complemento de q (ver  )

† por la definición de complemento.

‡ por la conmutatividad de ∨, ∧.
 por la definición de complemento.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Supongamos que L = [A, ∨, ∧] es un reticulado acotado y distributivo.
Entonces se cumple que ningún elemento de L puede tener más de un
complemento.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)
=  ∨ (r ∧ s) (porque  ≤ (r ∧ s))

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)
=  ∨ (r ∧ s) (porque  ≤ (r ∧ s))
= (p ∧ s) ∨ (r ∧ s)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)
=  ∨ (r ∧ s) (porque  ≤ (r ∧ s))
= (p ∧ s) ∨ (r ∧ s)
= (p ∨ r ) ∧ s (por distributividad)

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)
=  ∨ (r ∧ s) (porque  ≤ (r ∧ s))
= (p ∧ s) ∨ (r ∧ s)
= (p ∨ r ) ∧ s (por distributividad)
= I ∧ s (porque p ∨ r = I )

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Sean r , s complementos de p. Luego,
r es complemento de p =⇒ p ∧ r = , p ∨ r = I
s es complemento de p =⇒ p ∧ s = , p ∨ s = I
Ası́,
r = I ∧ r (porque r ≤ I )
= (p ∨ s) ∧ r (porque p ∨ s = I )
= (p ∧ r ) ∨ (s ∧ r ) (por distributividad)
=  ∨ (s ∧ r ) (porque p ∧ r = )
= s ∧ r (porque  ≤ (s ∧ r ))
= r ∧ s (por conmutatividad)
=  ∨ (r ∧ s) (porque  ≤ (r ∧ s))
= (p ∧ s) ∨ (r ∧ s)
= (p ∨ r ) ∧ s (por distributividad)
= I ∧ s (porque p ∨ r = I )
= s (porque s ≤ I )
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Nota
El Teorema anterior establece que en un reticulado distributivo y acotado
un elemento x puede tener a lo más un único complemento, no puede
tener más. En ese caso, al único complemento de x se le denota por x
(porque en ese caso no hay riesgo de ambigüedad).

Ejemplo
En el reticulado L1 de los ejemplos anteriores vimos que cada elemento
tiene un único complemento, ası́ que podemos escribir

 = I , a = b, b = a, I = 

En el reticulado L2 de los ejemplos anteriores, vemos que m tiene dos

complementos: n y t. ¿Cuál de ellos dos serı́a representado por el sı́mbolo
m?. La ambigüedad presente en este caso es razón suficiente para no
utilizar m.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Nota
El último teorema también nos proporciona un criterio (indirecto) para
determinar si un reticulado es no distributivo: al encontrar un elemento
que tenga más de un complemento, podemos asegurar que el reticulado es
no distributivo.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En el reticulado L del diagrama anexo,
I

L j h g

d e f

c b a


vemos que
j ∨ h = I , j ∧ h = . Luego h es un complemento de j.
j ∨ g = I , j ∧ g = . Luego g es un complemento de j.
j ∨ f = I , j ∧ f = . Luego f es un complemento de j.
j ∨ a = I , j ∧ a = . Luego a es un complemento de j.
Ası́ hemos encontrado 4-complementos del elemento j, en consecuencia el
reticulado L no es distributivo.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Teorema
Sea L = [A, ∨, ∧] un reticulado acotado y distributivo. Si a, b son
elementos de L, y poseen complementos a, b respectivamente, entonces:
1 a tiene complemento y es a, es decir, a = a
2 a ∨ b tiene complemento, el cual es a ∧ b, es decir, a ∨ b = a ∧ b
3 a ∧ b tiene complemento, el cual es a ∨ b, es decir, a ∧ b = a ∨ b

La primera propiedad, recibe el nombre de Propiedad de Involución;

mientras que la segunda y tercera propiedad, reciben el nombre de
Propiedad de Dualización.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
1 De acuerdo con los teoremas anteriores, como a es complemento de
a, entonces se tiene que a es complemento de a. Pero el complemento
es único porque L es distributivo, en consecuencia a = a.
2 Ahora comprobaremos que a ∧ b es complemento (único) de a ∨ b;
para eso, debemos ver que (a ∨ b) ∧ (a ∧ b) =  y
(a ∨ b) ∨ (a ∧ b) = I
Primero:

(a ∨ b) ∧ (a ∧ b) = (a ∧ b) ∧ (a ∨ b)
= [(a ∧ b) ∧ a] ∨ [(a ∧ b) ∧ b]
= [(a ∧ a) ∧ b] ∨ [a ∧ (b ∧ b)]
= [ ∧ b] ∨ [a ∧ ]
=∨
=

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Demostración.
Segundo:

(a ∨ b) ∨ (a ∧ b) = [(a ∨ b) ∨ a] ∧ [(a ∨ b) ∨ b]
= [(b ∨ a) ∨ a] ∧ [(a ∨ b) ∨ b]
= [b ∨ (a ∨ a)] ∧ [a ∨ (b ∨ b)]
= [b ∨ I ] ∧ [a ∨ I ]
=I ∨I
=I

3 Ejercicio

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Representación en Reticulados
Consideremos un reticulado L = [A, ∨, ∧] y elementos a, b, c, d ∈ A. Al
escribir una expresión como [(a ∨ b) ∧ c] ∨ [(a ∨ c ∨ d) ∧ b] se esta
describiendo una cierta forma de combinar los elementos a, b, c, d
mediante las operaciones ∨, ∧. En esa expresión aparecen indicadas las
operaciones que se deben realizar: al efectuar esas operaciones, se van
obteniendo otros elementos de A. Ası́: a ∨ b = p, (a ∨ b) ∧ c = p ∧ c =
q, a ∨ c = r , a ∨ c ∨ d = r ∨ d = s, (a ∨ c ∨ d) ∧ b = s ∧ b = t y
[(a ∨ b) ∧ c] ∨ [(a ∨ c ∨ d) ∧ b] = q ∨ t = w .
Al finalizar los cálculos, encontramos que la expresión dada también
representa un elemento w del reticulado L. Esto abre la posibilidad de
representar cualquier elemento de L mediante expresiones que contienen
ciertos “elementos básico” de L.
Un procedimiento que permite producir representaciones, utilizando
sólo una operación, es el que se describe a continuación:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Dado x ∈ A, se escoge dos predecesores inmediatos de x, digamos w1 y w2

(w1 6= w2 ). De ahı́ resulta que
x = w1 ∨ w2
Ahora, a w1 y w2 se les aplica el mismo procedimiento y se obtienen
elementos w11 , w12 , w21 , w22 que satisfacen w1 = w11 ∨ w12 y
w2 = w21 ∨ w22 con w11 6= w12 , w21 6= w22 , ası́ que:
x = w11 ∨ w12 ∨ w21 ∨ w22
Ahora se le aplica el procedimiento a w11 , w12 , w13 , w14 y se continuará
repitiendo con los elementos que se obtengan. Bajo unas condiciones
“buenas”, este proceso terminará (finito) cuando los elementos que se
obtengan ya no tengan dos o más predecesores inmediatos (cada uno). En
ese momento, para el elemento x se ha encontrado una representación de
la forma
x = p1 ∨ p2 ∨ . . . ∨ pk
en la cual cada uno de los elementos p1 , p2 , . . . , pk tiene menos de dos
predecesores inmediatos.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Definición: ∨-irreducible
Sea L = [A, ∨, ∧] un reticulado y p un elemento de L. Diremos que p es
∨-irreducible sii no existen elementos w1 , w2 en L tales que:
1 w1 6= w2
2 w1 6= p, w2 6= p
3 p = w1 ∨ w2

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En el reticulado L mostrado en la figura,

j h g

d e f

c b a


son elementos ∨-irreducibles

, a, b, c, d, f , h

(debido a que tienen menos de dos predecesores inmediatos).

Los elementos a, b, c que tienen a  como predecesor inmediato, son
llamados los ÁTOMOS del reticulado L.
Prof. Ismael Huerta Tema IIReticulados
 Reticulados

Ejemplo
1 En cualquier reticulado acotado, son ∨-irreducibles los átomos y la
cota inferior universal  (porque tienen menos de dos predecesores
inmediatos).
2 En el reticulado del ejemplo anterior, desarrollemos el procedimiento
descrito antes de la definición de elementos ∨-irreducibles.

I = j ∨ h = (d ∨ e) ∨ h = d ∨ e ∨ h = d ∨ c ∨ b ∨ h

obsérvese que en la expresión a extrema derecha, cada elemento es

∨-irreducible. Otra expresión para I :

I =j ∨g =d ∨e ∨e ∨f =d ∨e ∨f =d ∨c ∨a∨f

de nuevo, obsérvese que en la expresión a extrema derecha, cada

elemento es ∨-irreducible.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Con la definición y el teorema siguiente se establecen las condiciones

“buenas” para que el procedimiento ya mencionado tenga final (siempre).
Definición
Un reticulado L tiene longitud finita sii cualquier subconjunto totalmente
ordenado (cadena) de L es finito.

Teorema
Si L = [A, ∨, ∧] es un reticulado que tiene longitud finita, entonces cada
elemento x de L admite al menos una representación de la forma

x = p1 ∨ p2 ∨ · · · ∨ pk

en la cual cada pi (i = 1, 2, . . . , k) es ∨-irreducible.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
El reticulado L del ejemplo anterior, tiene longitud finita. En ese ejemplo,
ya encontramos dos representaciones del tipo mencionado en el teorema
anterior, ambas representaciones correspondiente al elemento I . Para los
demás elementos también hay representaciones de dicho tipo, como las
siguientes:
j =d ∨e =d ∨c ∨b j =d ∨e =d ∨c ∨a j =d ∨e =d ∨b∨a
g =e ∨f =c ∨b∨f g =e ∨f =c ∨a∨f g =e ∨f =b∨a∨f
e = c ∨ b, e = c ∨ a e = b ∨ a, d = d ∨  a = a ∨ a, a = a ∨ 
Nótese que en g = c ∨ a ∨ f resulta que a es comparable con f (a ≤ f ),
en consecuencia el Principio de Consistencia establece que a ∨ f = f y la
expresión c ∨ a ∨ f se simplifica y nos queda g = c ∨ f . Esta situación se
presenta en muchas otras representaciones, como vemos a continuación:

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Continuación

I = d ∨ c ∨ b ∨ h = (d ∨ c) ∨ (b ∨ h) = d ∨ h
I = d ∨ c ∨ a ∨ f = (d ∨ c) ∨ (a ∨ f ) = d ∨ f
g = b ∨ a ∨ f = b ∨ (a ∨ f ) = b ∨ f
d =d ∨c =d
d =d ∨=d
a =a∨a =a
a =a∨=a

Las expresiones que no se pueden “simplificar” o “reducir de tamaño” son

más importantes y reciben denominación especial.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Definición: Expresiones ∨-irredundantes

En un reticulado L = [A, ∨, ∧] tomemos elementos p1 , p2 , . . . , pk y
q1 , q2 , . . . , qr . Diremos que:
1 la expresión p1 ∨ p2 ∨ · · · ∨ pk es una subexpresión propia de
q1 ∨ q2 ∨ · · · ∨ qr sii {p1 , p2 , . . . , pk } ( {q1 , q2 , . . . , qr }

2 la expresión q1 ∨ q2 ∨ · · · ∨ qr es ∨-irreduntante sii

Cada qj (j = 1, 2, . . . , r ) es ∨-irreducible.
Ninguna subexpresión propia p1 ∨ p2 ∨ · · · ∨ pk de q1 ∨ q2 ∨ · · · ∨ qr
hace verdadera la igualdad q1 ∨ q2 ∨ · · · ∨ qr = p1 ∨ p2 ∨ · · · ∨ pk

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Ejemplo
En el ejemplo anterior vimos que I = d ∨ c ∨ b ∨ h y también I = d ∨ h. La
segunda expresión, d ∨ h, es una subexpresión de la primera d ∨ c ∨ b ∨ h.
Debido a la igualdad d ∨ c ∨ b ∨ h, podemos asegurar que d ∨ c ∨ b ∨ h no
es ∨-irredundante, pero d ∨ h si es ∨-irredundante (nótese que I = d ∨ h;
si quitamos d nos queda I = h, igualdad que es falsa; si quitamos h, queda
I = d y también es falsa, ası́ que d ∨ h es una representación del elemento
I la cual deja de ser representación de I al quitarle cualquier elemento). En
resumen, d ∨ h es una representación ∨-irredundante del elemento I .

Pero d ∨ f también es otra representación ∨-irredundante de I , ası́ que en

este caso no es única la representación ∨-irredundadnte de I .

En la igualdad d = d ∨ c vemos que se puede quitar el elemento c y la

igualdad sigue siendo verdadera; d ∨ c es una representación del elemento
d, pero no es ∨-irredundante porque se puede reducir a una subexpresión
que sigue representando a d.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Sea L un reticulado que tiene longitud finita. Si L es distributivo,
entonces cada elemento de L posee una única representación del tipo
∨-irredundante.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Sea L un reticulado que tiene longitud finita. Si L es distributivo,
entonces cada elemento de L posee una única representación del tipo
∨-irredundante.

Nota
Este resultado viene a ser otro criterio para estudiar la distributividad de
un reticulado.

Prof. Ismael Huerta Tema IIReticulados

 Reticulados

Teorema
Sea L un reticulado que tiene longitud finita. Si L es distributivo,
entonces cada elemento de L posee una única representación del tipo
∨-irredundante.

Nota
Este resultado viene a ser otro criterio para estudiar la distributividad de
un reticulado.

Ejemplo
En el caso del reticulado del ejemplo anterior acabamos de encontrar dos
representaciones ∨-irredundantes del elemento I . Esto nos permite
asegurar que dicho reticulado no es distributivo.

Prof. Ismael Huerta Tema IIReticulados