Relaciones

Conjuntos Parcialmente Ordenados

Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejes de Contenidos

1 Relaciones

2 Conjuntos Parcialmente Ordenados

3 Reticulados y Álgebras de Boole

4 Álgebras de Boole y Reticulados

5 Teoremas de representación

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Definición de Relación

Según la Real Academia Española, en su sentido

matemático, el término significa:
"Resultado de comparar dos cantidades expresadas en
números"
Por ejemplo:
Es correcto afirmar que 2 es menor que 5.
Es incorrecto afirmar que 2 es divisor de 5.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Definición de Relación

O sea:
La comparación de 2 con 5 arroja resultado positivo, si el
criterio de comparación es "ser menor que"
La comparación de 2 con 5 arroja resultado negativo, si el
criterio de comparación es "ser divisor de"

Podemos afirmar entonces que una relación queda

determinada por el conjunto de pares que arrojan
resultado positivo cuando son sometidos al "criterio de
comparación" que determina la relación.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Definición Formal

Sean A y B dos conjuntos, una relación R entre A y B será un

subconjunto del producto cartesiano A × B

O sea: R ⊆ A × B

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplo

A = {2, 4, 8, 10}

B = {1, 3, 9}

La relación R = "es menor que" se representa

matemáticamente mediante el siguiente subconjunto de A × B:

R = {(2, 3), (2, 9), (4, 9), (8, 9)}

Entonces la afirmación:
"2 es menor que 9" se formaliza expresando (2, 9) ∈ R
"4 no es menor que 1" se formaliza expresando (4, 1) ∈
/R

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Notación

Si R es una relación entre A y A, decimos que R es una

relación sobre A
Si R es una relación sobre A, y (a, b) ∈ R, entonces
escribimos

a ∼R b

o simplemente

a∼b

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Tipos fundamentales de relaciones

Funciones
No serán abordadas en este curso
Relaciones de equivalencia
Esta clase:
su vinculación con las particiones de un conjunto
Relaciones de orden
Casi la totalidad de la primera parte de la materia

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedades de las relaciones

Sea R una relación sobre un conjunto A. Decimos que R es:

reflexiva si y sólo si para todo a ∈ A: a ∼ a

simétrica si y sólo si para todo a, b ∈ A,

a ∼ b implica que b ∼ a

antisimétrica si y sólo si para todo a, b ∈ A

a ∼ b y b ∼ a implican que a = b

transitiva si y sólo si para todo a, b, c ∈ A,

a ∼ b y b ∼ c implican que a ∼ c

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplo 1: Relación "divide"

Es la relación sobre los naturales positivos definida mediante:

a ∼ b si y sólo si a es divisor de b

En cursos anteriores se utilizó la notación a|b

¿Cuáles de las 4 propiedades son satisfechas por la relación

divide?

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplo 2: Relación "congruente módulo k "

Dado un k fijo, es la relación sobre Z definida mediante:

a ∼k b si y sólo si k es divisor de b − a

En cursos anteriores se utilizó la notación a ≡ b mod(k )

¿Cuáles de las 4 propiedades son satisfechas por la relación

"congruente módulo k "?

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Relaciones de equivalencia

Son las relaciones que satisfacen las propiedades

reflexividad, simetría y transitividad

Por ejemplo, la relación "congruente módulo k " es una relación

de equivalencia, cualquiera sea k

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Clases de equivalencia

Sea ∼ una relación de equivalencia sobre un conjunto A y sea

x un elemento de A.
La clase de equivalencia de x se denota por [x] y es el conjunto
[x] = {y ∈ A | y ∼ x}
Por ejemplo, en la relación "congruente módulo 3",
[0] = {0, 3, −3, 6, −6, 9, −9, ...}
[1] = {1, 4, −2, 7, −5, 10, −8, ...}
[2] = {2, 5, −1, 8, −4, 11, −7, ...}
[3] = [0]
[4] = [1]
[5] = [2] ....
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Partición de un conjunto

Una partición de un conjunto A es una familia de subconjuntos

no vacíos de A, que son disjuntos entre sí, y cuya unión es
todo A.

Por ejemplo, las siguientes son distintas particiones de

A = {a, b, c}:
P1 : {a}, {b}, {c};
P2 : {a}, {b, c};
P3 : {a, b, c}.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Teorema

Sea ∼ una relación de equivalencia en un conjunto A y sean x,

y elementos de A. Entonces

1 [x] = [y ] si y sólo si x ∼ y .
2 si x 6∼ y , entonces [x] e [y ] son disjuntas.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Relación de equivalencia y Partición

Son conceptos duales

Sea ∼ una relación de equivalencia en un conjunto A, entonces
las clases de equivalecia determinan una partición de A

Sea P1 , P2 , ... una partición de A, entonces la relación definida

mediante a ∼ b si y sólo si existe k tal que a, b ∈ Pk es una
relación de equivalecia sobre A

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Relación de Orden Parcial

Una relación de orden parcial R sobre un conjunto A es una

relación que satisface las propiedades de reflexividad,
antisimetría y transitividad

Notación: a ≤ b en lugar de (a, b) ∈ R

Ejemplos:
1 Si a y b son números, entonces a ≤ b denota la relación
de orden usual sobre R (o Z), salvo que se diga
explícitamente otra cosa.
2 a ≤ b si y sólo si a divide a b sobre N, (se puede usar a|b)
3 X ≤ Y si y sólo si X ⊆ Y sobre P(A)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Relación de Orden Parcial

Una relación de orden parcial R sobre un conjunto A es una

relación que satisface las propiedades de reflexividad,
antisimetría y transitividad

Notación: a ≤ b en lugar de (a, b) ∈ R

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Relación de Orden Parcial

Ejemplos:
1 Relación de orden usual sobre R (o Z): Si a y b son
números, entonces a ≤ b refleja la relación de orden dada
por la representación geométrica de la recta, salvo que se
diga explícitamente otra cosa.
2 La relación definida por a ≤ b si y sólo si a divide a b
(sobre N = {1, 2, 3, ...}) es una relación de orden. También
utilizamos a|b.
3 X ≤ Y si y sólo si X ⊆ Y (sobre P(A)) es una relación de
orden

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Diagramas de Hasse

Definición de la relación cubrimiento

Sea A un conjunto y ≤ un orden parcial sobre A. Sean a, b ∈ A
elementos distintos. Decimos que b cubre a a si a ≤ b y no
existe c distinto de a y b tal que a ≤ c y c ≤ b.

Definición de Diagrama de Hasse

Consiste de puntos llamados vértices que representan los
elementos del conjunto y de arcos o segmentos ascendentes
que unen pares de vértices de la siguiente manera:

a está conectado con b mediante un arco ascendente si y sólo

si b cubre a a.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Conjunto Parcialmente Ordenado (CPO o POSET)

Es un par (P, ≤) donde P es un conjunto y ≤ es un orden

parcial sobre P

Ejemplos:
1 (R, ≤) es un POSET
2 (N, |) es un POSET
3 ({1, 2, 3, 5, 6, 8}, |) es un POSET
4 (P(N), ⊆) es un POSET

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Máximos y Mínimos

(P, ≤) un POSET
a es mínimo de P si para todo x en P se tiene a ≤ x
a es máximo de P si para todo x en P se tiene x ≤ a

¿Cuáles de los siguientes tienen máximo y/o mínimo?

1 (N, ≤)
2 ([0, 1), ≤)
3 ({2, 4, 6, 12, 16}, |)
4 ({2, 4, 6, 12}, |)
5 ({{c}, {a, b}, {a, b, c}}, ⊆)
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Maximales y Minimales

(P, ≤) un POSET
a es minimal de P si para todo x en P,
x ≤ a implica que x = a
a es maximal de P si para todo x en P,
a ≤ x implica que a = x

¿Cuáles de los siguientes tienen maximales y/o minimales?

1 (N, ≤)
2 ([0, 1), ≤)
3 ({2, 4, 6, 12, 16}, |)
4 ({2, 4, 6, 12}, |)
5 ({{c}, {a, b}, {a, b, c}}, ⊆)
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Orden Total o Cadena

Un orden total sobre un conjunto P es un orden parcial ≤ sobre

P que satisface la ley de dicotomía:

para todo a, b ∈ P, a ≤ b o b ≤ a.

Algunos ejemplos de órdenes totales:

1 El orden ≤ en R
2 El orden lexicográfico en un diccionario.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Supremos e Ínfimos

Sea (P, ≤) un poset y sea S ⊆ P.

1 a ∈ P se dice cota superior de S si para todo b ∈ S ocurre

que b ≤ a.
2 a ∈ P se dice cota inferior de S si para todo b ∈ S ocurre
que a ≤ b.
3 a ∈ P se dice supremo de S si a es una cota superior de S
y para toda cota superior b de S se cumple que a ≤ b.
4 a ∈ P se dice ínfimo de S si a es una cota inferior de S y
para toda cota inferior b de S se cumple que b ≤ a.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Isomorfismo de POSETS

Sean (P, ≤), (Q, ≤0 ) dos posets, y sea f : P → Q una función.

Diremos que f es un isomorfismo si f es biyectiva y para todo
x, y ∈ P, se cumple que
x ≤ y si y sólo si f (x) ≤0 f (y )

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedad Fundamental de los Isomorfismos

Lema
Sean (P, ≤) y (Q, ≤0 ) posets. Sea f : P → Q un isomorfismo.

1 Para cada S ⊆ P, se tiene que existe sup(S) si y sólo si

existe sup(f (S)) y en el caso de que existan tales
elementos se tiene que f (sup(S)) = sup(f (S)).
2 Para cada S ⊆ P, se tiene que existe inf(S) si y sólo si
existe inf(f (S)) y en el caso de que existan tales
elementos se tiene que f (inf(S)) = inf(f (S)).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Supremos e Ínfimos

Sea (P, ≤) un poset y sea S ⊆ P.

1 a ∈ P se dice cota superior de S si para todo b ∈ S ocurre

que b ≤ a.
2 a ∈ P se dice cota inferior de S si para todo b ∈ S ocurre
que a ≤ b.
3 a ∈ P se dice supremo de S si a es una cota superior de S
y para toda cota superior b de S se cumple que a ≤ b.
4 a ∈ P se dice ínfimo de S si a es una cota inferior de S y
para toda cota inferior b de S se cumple que b ≤ a.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Isomorfismo de POSETS

Sean (P, ≤), (Q, ≤0 ) dos posets, y sea f : P → Q una función.

Diremos que f es un isomorfismo si f es biyectiva y para todo
x, y ∈ P, se cumple que
x ≤ y si y sólo si f (x) ≤0 f (y )

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedad Fundamental de los Isomorfismos

Lema
Sean (P, ≤) y (Q, ≤0 ) posets. Sea f : P → Q un isomorfismo.

1 Para cada S ⊆ P, se tiene que existe sup(S) si y sólo si

existe sup(f (S)) y en el caso de que existan tales
elementos se tiene que f (sup(S)) = sup(f (S)).
2 Para cada S ⊆ P, se tiene que existe inf(S) si y sólo si
existe inf(f (S)) y en el caso de que existan tales
elementos se tiene que f (inf(S)) = inf(f (S)).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Posets Rerticulados

Diremos que un poset (L, ≤) es un poset reticulado si para

todo a, b ∈ L, existen sup({a, b}) e inf({a, b}).

Notación: a ∨ b = sup{a, b} a ∧ b = inf{a, b}

¿Cuáles de los siguientes posets son reticulados?

(N, ≤)
([0, 1), ≤)
({2, 4, 6, 12, 24}, |)
({2, 4, 5, 6, 12}, |)
(P({a, b, c}, ⊆)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulado de divisores de n

Dn = {k ∈ N : k |n}

(Dn , |) es un reticulado

x ∨ y = mcm(x, y )

x ∧ y = mcd(x, y )

1 es mínimo de Dn

n es el máximo de Dn

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulado de partes de X

(P(X ), ⊆) es un reticulado

A∨B =A∪B

A∧B =A∩B

∅ es mínimo de P(X )

X es el máximo de P(X )

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedades básicas del supremo e ínfimo

Dado un reticulado (L, ≤), y elementos x, y , z, w ∈ L, se

cumplen las siguientes propiedades:

1 x ≤x ∨y
2 x ∧y ≤x
3 x ≤y ⇔ x ∨y =y ⇔ x ∧ y = x,
4 ley de compatibilidad

x ≤z e y ≤w implican x ∨ y ≤ z ∨ w, x ∧y ≤ z ∧w

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedades fundamentales del supremo e ínfimo

1 leyes de idempotencia:
x ∨x =x ∧x =x
2 leyes conmutativas:
x ∨ y = y ∨ x, x ∧y =y ∧x
3 leyes de absorción:
x ∨ (x ∧ y ) = x, x ∧ (x ∨ y ) = x
4 leyes asociativas:
(x ∨ y ) ∨ z = x ∨ (y ∨ z), (x ∧ y ) ∧ z = x ∧ (y ∧ z)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Desigualdades distributivas

x ∨ (y ∧ z) ≤ (x ∨ y ) ∧ (x ∨ z)

(x ∧ y ) ∨ (x ∧ z) ≤ x ∧ (y ∨ z)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Noción de Estructura Algebraica

Estructura Algebraica = conjunto con operaciones

Por ejemplo, los números enteros dotados de las operaciones
suma, producto y las constantes 0 y 1 tienen estructura de
Anillo.
Se denota: (Z, +.·, 0, 1)
Lo importante de la operación no es el nombre, sino el tipo.
Por ejemplo el tipo de + es Z × Z → Z
La estructura está dada no sólo por las operaciones, sino
también por las propiedades que las mismas satisfacen, en
este caso, la asociatividad, la distributividad del producto
respecto de la suma, etc.
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulado como Estructura Algebraica

Es una tupla (L, ∨, ∧) que satisface las propiedades:

1 Idempotencia: x ∨x =x ∧x =x
2 Conmutatividad: x ∨ y = y ∨ x x ∧y =y ∧x
3 Absorción: x ∨ (x ∧ y ) = x x ∧ (x ∨ y ) = x
4 Asociatividad:
(x ∨ y ) ∨ z = x ∨ (y ∨ z) (x ∧ y ) ∧ z = x ∧ (y ∧ z)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplos

1 No toda estructura del tipo (L, ∨, ∧) es un reticulado. Por

ejemplo la estructura (R, +, ·) donde + y · son las
operaciones de suma y producto usuales de R no es un
reticulado.
2 Por las propiedades fundamentales de supremo e ínfimo,
un poset reticulado (L, ≤) puede "mutar" para convertirse
en un reticulado (como estructura algebraica): tomamos la
estructura (L, ∨, ∧) donde ∨ y ∧ representan al supremo y
al ínfimo resp.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Existencia dual de un Reticulado

Sea (L, ∨, ∧) un reticulado (como estructura algebraica). La

relación binaria definida por:

x ≤ y ⇐⇒ x ∨ y = y

es un orden parcial sobre L para el cual se cumple:

x ∨ y = sup{x, y }, x ∧ y = inf {x, y }

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplos

1 Si X es un conjunto arbitrario, entonces (P(X ), ∪, ∩) es un

reticulado. La relación binaria inducida por ∪ y ∩ es
precisamente la inclusión, pues

A=A∪B ⇐⇒ B⊆A
2 Si n ∈ N entonces (Dn , mcm, mcd) es un reticulado. La
relación binaria inducida es la de divisibilidad, pues

mcm(x, y ) = y ⇐⇒ x|y

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Existencia dual de un Reticulado

Dado un CPO reticulado (L, ≤), entonces la estructura

algebraica (L, ∨, ∧) satisface las propiedades de
idempotencia, conmutatividad, absorción y asociatividad.
Sea (L, ∨, ∧) una estructura algebraica que satisface las
propiedades de idempotencia, conmutatividad, absorción y
asociatividad, entonces la relación binaria definida por:

x ≤ y ⇐⇒ x ∨ y = y

es un orden parcial sobre L.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Las construcciones son recíprocas

Lema
Sea (L, ∨, ∧) un reticulado (como estructura algebraica). La
relación binaria definida por:

x ≤ y ⇐⇒ x ∨ y = y

es un orden parcial sobre L para el cual se cumple:

x ∨ y = sup{x, y }, x ∧ y = inf {x, y }

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Las construcciones son recíprocas

o sea,

El CPO (L, ≤) que se obtiene de (L, ∨, ∧) definiendo:

x ≤ y ⇐⇒ x ∨ y = y

es un reticulado en el cual las operaciones supremo e ínfimo

coinciden con ∨ y ∧ resp.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplos

1 Si X es un conjunto arbitrario, entonces (P(X ), ∨, ∧) es un

reticulado. La relación binaria inducida por ∪ y ∩ es
precisamente la inclusión, y

A∨B =A∪B A∧B =A∩B

2 Si n ∈ N entonces (Dn , ∨, ∧) es un reticulado. La relación
binaria inducida es la de divisibilidad,

x ∨ y = mcm(x, y ) x ∧ y = mcd(x, y )

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Notación

Cuando escibimos

"sea L un reticulado"

consideramos L simultaneamente dotado de su estructura de

poset (L, ≤) y de estructura algebraica hL, ∨, ∧i.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulados acotados

Definición: L será acotado si tiene máximo y mínimo.

Notación: Usamos
1L para denotar al máximo
0L para denotar al mínimo

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulados complementados

Sea L un reticulado acotado y sea x ∈ L. Decimos que x es

complementado si existe y ∈ L tal que

x ∨ y = 1L x ∧ y = 0L

L será un reticulado complementado si todos sus elementos

tienen al menos 1 complemento.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Falla Estructural

El complemento no está determinado por la estructura de

orden, como lo están las operaciones supremo e ínfimo.

s1 s1
@ @
@ as @sb
a s s b @sc A
@ A sc
@
@s
A
As
0 0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Propiedad de distributividad

x ∨ (y ∧ z) = (x ∨ y ) ∧ (x ∨ z)

(x ∧ y ) ∨ (x ∧ z) = x ∧ (y ∨ z)

¿Valen en todo reticulado?

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Casos paradigmáticos de no distributividad

s1 s1
@ @
@ as @sb
a s s b @sc A
@ A sc
@
@s 0
A
As 0
M3 N5

c ∨ (b ∧ a) 6= (c ∨ b) ∧ (c ∨ a)

b ∧ (c ∨ a) 6= (b ∧ c) ∨ (b ∧ a)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Desigualdades distributivas

x ∨ (y ∧ z) ≤ (x ∨ y ) ∧ (x ∨ z)

(x ∧ y ) ∨ (x ∧ z) ≤ x ∧ (y ∨ z)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

La propiedad de Distributividad

Lema: Sea L un reticulado; entonces son equivalentes:

1 Para todo x, y , z ∈ L,

x ∧ (y ∨ z) = (x ∧ y ) ∨ (x ∧ z)

2 Para todo x, y , z ∈ L,

x ∨ (y ∧ z) = (x ∨ y ) ∧ (x ∨ z)

Notar que hay reticulados que no satisfacen ni 1 ni 2.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Distributividad implica compleménto único

Lema:
Si L es un reticulado acotado y distributivo, entonces todo
elemento tiene a lo sumo un complemento.
Notar que puede no haber complementos, por ejemplo

1s

sa

s
0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Noción de subreticulado

Sea L un reticulado. Un subconjunto M ⊆ L será llamado

subreticulado de L si

1 M 6= ∅,
2 para todo x, y ∈ M, se tiene que x ∨ y , x ∧ y ∈ M.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Por ejemplo:

Considere el reticulado
s1
@
u s sv @sw
@
x s @sy
@
@s 0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Por ejemplo:

Considere el reticulado
s1
@
u s sv @sw
@
x s @sy
@
@s 0

{0, x, y , 1} no es subreticulado

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Por ejemplo:

Considere el reticulado
s1
@
u s sv @sw
@
x s @sy
@
@s 0

{0, x, y , 1} no es subreticulado
{0, u, w, 1} es subreticulado

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Un subreticulado es un reticulado

Notar que M dotado de las operaciones (y/o el orden)

heredadas de L es en sí mismo un reticulado.

{0, u, w, 1} es el subreticulado
s1
@
u s @sw

@
@s 0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Noción de subreticulado II

Sean S y L dos reticulados.

Se suele decir que S es subreticulado de L cuando en realidad

S es isomorfo a un subreticulado de L

Por ejemplo,
P({a, b}) es subreticulado de D12
D12 es subreticulado de P({a, b, c})

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

La propiedad de Distributividad

Lema:
Sea L un reticulado; entonces son equivalentes:

1 Para todo x, y , z ∈ L,
x ∧ (y ∨ z) = (x ∧ y ) ∨ (x ∧ z)
2 Para todo x, y , z ∈ L,
x ∨ (y ∧ z) = (x ∨ y ) ∧ (x ∨ z)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulados Distributivos

Sea L un reticulado, entonces L se dice distributivo si

satisface alguna de las propiedades del Lema.

Ejemplos:
1 N con el orden usual es distributivo
2 [0, 1) con el orden usual es distributivo
3 P({a, b, c} es distributivo
4 Dn es distributivo

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Casos paradigmáticos de no distributividad

s1 s1
@ @
@ as @sb
a s s b @sc A
@ A sc
@
@s 0
A
As 0
M3 N5

c ∨ (b ∧ a) 6= (c ∨ b) ∧ (c ∨ a)

b ∧ (c ∨ a) 6= (b ∧ c) ∨ (b ∧ a)

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Distributividad implica compleménto único

Lema:
Si L es un reticulado acotado y distributivo, entonces todo
elemento tiene a lo sumo un complemento.
Notar que puede no haber complementos, por ejemplo

1s

sa

s
0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Criterio para analizar distributividad

Lema:

Un reticulado es distributivo si y sólo si no contiene

subreticulados isomorfos a M3 ni N5 .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Resumen de criterios para analizar distributividad

Para comprobar la distributividad de L:

1 Ver que L es subreticulado de algún reticulado de la forma
P(X ) o Dn .

Para refutar la distributividad de L:

1 Ver que existe un elemento con más de un complemento.
2 Ver que contiene como subreticulados a M3 o N5 .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Álgebras de Boole

Es una estructura del tipo hB, ∨, ∧,0 , 0, 1i, donde B es un

conjunto no vacío, y además satisface:
1 hB, ∨, ∧i es un reticulado distributivo
2 Para todo x ∈ B se tiene

0≤x x ≤1

3 para cada x ∈ L, se tiene que

x ∨ x 0 = 1, x ∧ x0 = 0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Álgebra de Boole de conjuntos

Sea X un conjunto.
Entonces hP(X ), ∪, ∩,c , ∅, X i es un álgebra de Boole,

{a,
s b}
@
@
s{a} {a} s @s{b}
@
@
s @s
∅ ∅
P({a}) P({a, b})

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Leyes de de Morgan

Sea hB, ∨, ∧,0 , 0, 1i un álgebra de Boole, entonces se cumple:

(x ∨ y )0 = x 0 ∧ y 0
(x ∧ y )0 = x 0 ∨ y 0

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Isomorfismo de Álgebras de Boole

Sean hB, ∨, ∧,0 , 0B , 1B i y hB1 , ∨1 , ∧1 ,∗ , 0B1 , 1B1 i Álgebras de

Boole. Una función F : B → B1 se dice un isomorfismo si F es
biyectiva y para todo x, y ∈ L se cumple que

F (x ∨ y ) = F (x) ∨1 F (y )
F (x ∧ y ) = F (x) ∧1 F (y )
F (x 0 ) = (F (x))∗
F (0B ) = 0B1
F (1B ) = 1B1

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Comparación de las nociones de Isomorfismo

Isomorfismo como posets:

x ≤y ⇐⇒ F (x) ≤0 F (y )

Isomorfismo como estructura algebraica:

F (x ∨ y ) = F (x) ∨1 F (y )
F (x ∧ y ) = F (x) ∧1 F (y )
F (x 0 ) = (F (x))∗
F (0B ) = 0B1
F (1B ) = 1B1
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Equivalencia de las nociones de Isomorfismo

Teorema:
Sean hB, ∨, ∧,0 , 0B , 1B i y hB1 , ∨1 , ∧1 ,∗ , 0B1 , 1B1 i Álgebras de
Boole y sean (B ≤) y (B1 , ≤1 ) los posets asociados.
Para toda F : B 7→ B1 , son equivalentes:
1 F es un isomorfismo entre las estructuras hB, ∨, ∧,0 ,B , 1B i
y hB1 , ∨1 , ∧1 ,∗ , 0B1 , 1B1 i.
2 F es un isomorfismo entre los posets (B, ≤) y (B1 , ≤1 ).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Cuestión a resolver

Todas las Álgebras de Boole vistas (aunque estén camufladas

como D6 o D30 ) son en definitiva (vía isomorfismo) de la forma
P(X ).

O sea, son álgebras de conjuntos.

¿Será cierto que todas las Álgebras de Boole son álgebras de

conjuntos?

(En tal caso estaríamos en presencia de una abstracción "poco

abstracta")

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Próximo objetivo: Teorema de Representación

Toda Álgebra de Boole finita B es un álgebra de conjuntos.

O sea, existe X tal que

B∼
= P(X )

Pregunta inicial:

¿Qué objetos juegan el rol de elementos de X ?

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Átomos

Sea B un álgebra de Boole (basta con que sea reticulado).

Un elemento a ∈ B será llamado átomo si a cubre a 0.

Notación: At(B) es el conjunto de todos los átomos de B.

Por ejemplo:
1 En P(X ), los átomos son los conjuntos unitarios.
2 Los átomos de D12 son 2 y 3.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Hay suficiente cantidad de átomos

Lema A
Sea B un álgebra de Boole finita. Para todo x ∈ B distinto de 0
existe a ∈ At(B) tal que a ≤ x.

Lema B Sea B un álgebra de Boole finita, y sean x, y ∈ B tales

que x  y . Entonces existe a ∈ At(B) tal que a ≤ x y a  y .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Hay suficiente cantidad de átomos

Lema
Sea B un álgebra de Boole finita. Entonces todo elemento de B
se escribe de manera única como supremo de átomos.
O sea: para todo x ∈ B se tiene:
1 x = sup{a ∈ At(B) : a ≤ x},
2 si A ⊆ At(B) y x = sup A, entonces

A = {a ∈ At(B) : a ≤ x}

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Teorema de Representación

Sea hB, ∨, ∧,0 , 0, 1i un álgebra de Boole finita, y sea

X = At(B). La función

F : B −→ P(X )
x −→ {a ∈ X : a ≤ x}

es un isomorfismo entre hB, ∨, ∧,0 , 0, 1i y hP(X ), ∪, ∩,c , ∅, X i.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Esquema de la Prueba del TR

Lema A
↓
Lema B
↓
Lema
↓
Teorema de Representación

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Problema de la representación de un reticulado

Las Álgebras de Boole finitas son álgebras de conjuntos.

¿Serán los reticulados finitos reticulados de conjuntos?

{a, b, c}
s
@
{a, b} s @s{b, c}
@
{a} s @s{b}
@
@s ∅

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Conjuntos decrecientes de un poset

Sea (P, ≤) un poset

Diremos que un subconjunto D ⊆ P es decreciente si para

todo x, z ∈ P se tiene que:

x ∈ D y z ≤ x =⇒ z ∈ D.
O sea, un conjunto decreciente satisface que si un elemento se
encuentra en el conjunto, entonces todos los elementos
menores también están.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Reticulado de conjuntos decrecientes de un poset

Denotaremos mediante D(P) a la familia de todos los

subconjuntos decrecientes de P:

D(P) = {D ⊆ P : D es decreciente}.

Entonces

hD(P), ∪, ∩, ∅, Pi.
es un reticulado es distributivo

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplo: sea P el poset

c s

a s b s

Los conj. decrecientes son: ∅, {a}, {b}, {a, b}, {b, c}, {a, b, c}
Forman el reticulado D(P):
{a, b, c}
s
@
{a, b} s @s{b, c}
@
{a} s @s{b}
@
@s ∅

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Problema de la representación de un reticulado

¿Será cierto que para todo reticulado distributivo L existe un

poset P tal que

L∼
= D(P)

Dado L un reticulado, ¿cómo obtengo el P tal que L ∼

= D(P)?

s
@
s @s
@
s @s
@
@s

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

¿Cómo se obtiene P desde L?

s
@
s @s
@
s @s
@
@s

↓
↓
s

s s

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Elementos Irreducibles

Sea L un reticulado acotado. Un elemento x ∈ L será llamado

irreducible si

1 x 6= 0,
2 si x = y ∨ z, entonces x = y o x = z, para todo y , z ∈ L.

La segunda condición es equivalente a decir que x no se

puede obtener como supremo de dos elementos distintos de x.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Ejemplos de Elementos Irreducibles

s1
@
ds @sc
@
a s @sb
@
@s 0

Elementos irreducibles: a, b, c
Forman el poset:
c s

a s b s

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Poset de Elementos Irreducibles

Definición: Irr (L) = {i ∈ L : i es irreducible}

Próximo objetivo: Demostrar que todo reticulado distributivo

finito L es isomorfo a D(P), donde el poset (P, ≤) asociado al
reticulado L es

(Irr (L), ≤)
,
donde ≤ es el orden heredado de L.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Hay suficiente cantidad de Irreducibles

Lema A
Sea L un reticulado finito, y sean x, y ∈ L tales que x  y .
Entonces existe i ∈ Irr (L) tal que i ≤ x e i  y .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Hay suficiente cantidad de Irreducibles

Lema
Sea L un reticulado distributivo finito. Entonces para todo x ∈ L
se tiene:

1 x = sup{i ∈ Irr (L) : i ≤ x},

2 si D ⊆ Irr (L) es decreciente, y x = sup D, entonces

D = {i ∈ Irr (L) : i ≤ x}

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Teorema de Birkhoff

Sea L un reticulado acotado distributivo finito, y sea P = Irr (L).

Entonces la función

F : L −→ D(P)
x −→ {y ∈ P : y ≤ x}

es un isomorfismo entre L y D(P).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

El ejemplo D12 completo

s1
@
ds @sc
@
a s @sb
@
@s 0
L

Irr (L) = {a, b, c}

Forman el poset:
c s

a s b s
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

D(P) = {∅, {a}, {b}, {a, b}, {b, c}, {a, b, c}}

{a, b, c}
s
@
{a, b} s @s{b, c}
@
{a} s @s{b}
@
@s ∅

La correspondencia F dada por el Teorema es:

0→∅ a → {a}
b → {b} d → {a, b}
c → {b, c} 1 → {a, b, d}
Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación
 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Nuevo criterio de análisis de distributividad

Se puede observar que la única intervención de la

distributividad en la prueba del Teorema de Birkhoff es para
probar que F es sobre.

Criterio de análisis de distributividad

Un reticulado finito es ditributivo si y sólo si |L| = |D(Irr (L))|

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Volviendo a las Álgebras de Boole

Vale:

At(B) = Irr (B)

Entonces, si L es un reticulado acotado distributivo finito, se

tiene:

L es álgebra de Boole si y sólo si Irr (L) = At(L).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

TR no vale para el caso infinito

Existe un álgebra de Boole infinita que no es isomorfa P(X ),

para ningún X .

Construiremos un Álgebra de Boole B, y usaremos un

argumento sobre su cardinalidad para probar que no es
isomorfa a ningún álgebra de la forma P(X ).

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Cardinal de un conjunto

1 X tiene cardinal finito si X = ∅, o existe n ∈ N tal que se

puede encontrar una biyección entre X y {1, 2, ..., n}.
2 Si X no es finito, decimos que X es infinito.
3 X tiene cardinal infinito numerable si se puede encontrar
una biyección entre X y N. En tal caso se dice que X tiene
cardinal ℵ0 .
4 Si X es infinito y no se puede encontrar tal biyección,
decimos que X es infinito no numerable.
5 Ejemplos de conjuntos infinitos no numerables: R, P(N) .
Ambos tienen cardinal ℵ1 .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Cardinal de P(X )

Los cardinales tiene un orden

0 < 1 < 2 < ... < ℵ0 < ℵ1 < ...

1 Si X es finito, entonces P(X ) es finito ¿Cuál es su

cardinal?
2 Si X es infinito, entonces P(X ) es infinito no numerable.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Cardinal de P(X )

Los cardinales tiene un orden

0 < 1 < 2 < ... < ℵ0 < ℵ1 < ...

1 Si X es finito, entonces P(X ) es finito ¿Cuál es su

cardinal?
2 Si X es infinito, entonces P(X ) es infinito no numerable.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Cardinal de P(X )

0 < 1 < 2 < ... < ℵ0 < ℵ1 < ℵ2 ....

P(X ) P(X )
(X finito) ↓ (X infinito)
No es el cardinal
de ningún P(X )

Conclusión: Si podemos construir un Álgebra de Boole B que

tenga cardinal infinito numerable (o sea ℵ0 ), entonces no
podrá existir una biyección (ni un isomorfismo) entre B y P(X ),
para ningún X .

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación

 Relaciones
Conjuntos Parcialmente Ordenados
Reticulados y Álgebras de Boole
Álgebras de Boole y Reticulados
Teoremas de representación

Construcción de B

Un subconjunto de números naturales se dice cofinito si su

complemento es finito.
Definimos:

B = {X ⊆ N : X es finito o cofinito}.
Entonces la estructura

hB, ∪, ∩,c , ∅, Ni
es un álgebra de Boole.

Parte I: Estructuras Ordenadas Introducción a la Lógica y la Computación