Retículo (matemáticas)

estructura algebraica
(Redirigido desde «Reticulado (orden)»)

En matemáticas, específicamente en álgebra y teoría del orden, un retículo es una estructura algebraica en un conjunto: con una relación binaria: que es conjunto parcialmente ordenado y dos operaciones binarias, con la propiedad fundamental de que toda pareja de elementos tiene un único supremo (o extremo superior) en y un único ínfimo (o extremo inferior) en .[1][2][3]

Diagrama de Hasse del retículo de particiones del conjunto {1,2,3,4}.

El término «retículo» viene de la forma de los diagramas de Hasse de tales órdenes.[4][5][6]

Un ejemplo de retículo es el conjunto de particiones de un conjunto finito, ordenado por la relación de inclusión.

Definición como conjunto ordenado

editar

En teoría de conjuntos, un retículo es un conjunto parcialmente ordenado en el cual, para cada par de elementos, existen un supremo y un ínfimo, esto es:

Un conjunto parcialmente ordenado (L, ≤) se denomina retículo si satisface las siguientes propiedades:

Existencia del supremo por pares
Para cualesquiera dos elementos a y b de L, el conjunto {a, b} tiene un supremo:   (también conocido como mínima cota superior, o join en idioma inglés).
Existencia del ínfimo por pares
Para cualesquiera dos elementos a y b de L, el conjunto {a, b} tiene un ínfimo:   (también conocido como máxima cota inferior, o meet en idioma inglés).

El supremo y el ínfimo de a y b se denotan por   y  , respectivamente, lo que define a   y   como operaciones binarias. El primer axioma dice que L es un semirretículo superior; el segundo que L es un semirretículo inferior. Ambas operaciones son monótonas con respecto al orden: a1 ≤ a2 y b1 ≤ b2 implica que a1  b1 ≤ a2   b2 y a1 b1 ≤ a2 b2.

Se sigue por inducción matemática que para todo subconjunto finito no vacío de un retículo existen un supremo y un ínfimo.

Nótese que aún en un conjunto parcialmente ordenado (L, ≤) arbitrario, la existencia de algún supremo (o ínfimo) z para un subconjunto finito no vacío S de L implica que este supremo (o ínfimo) z es único, puesto que de existir dos o más cotas superiores (o inferiores) de S que sean incomparables entre sí, el supremo (o ínfimo) por definición no existe.

Definición algebraica

editar

En álgebra, en sentido inverso, un retículo es un conjunto L, provisto de dos operaciones binarias   y  , tales que para cualesquiera a, b, c en L se cumplen

    las leyes de conmutatividad
    las leyes de asociatividad
    las leyes de absorción
condiciones de las que se derivan
    las leyes de idempotencia

Si las dos operaciones satisfacen estas reglas algebraicas, entonces a su vez definen un orden parcial ≤ en L por la regla siguiente: ab si y solo si a   b = b, o, equivalentemente, a   b = a.

L, junto con el orden parcial ≤ así definido, sería entonces un retículo en el sentido antedicho de la teoría del orden.

Inversamente, si se da un retículo (L, ≤) en términos de la teoría del orden, y escribimos a   b para el supremo de {a, b} y a   b para el ínfimo de {a, b}, entonces (L,  ) satisface todos los axiomas de un retículo definido algebraicamente.

Por tanto L es un semirretículo con respecto a cada operación por separado, es decir, un semigrupo conmutativo, con idempotencia de cada uno de sus elementos. Las operaciones interactúan a través de las leyes de absorción.

Al permutar las operaciones se obtiene el retículo dual de L.

Homomorfismos

editar

La clase de todos los retículos forma una categoría si definimos un homomorfismo entre dos retículos (L,  ) y (N,  ) como una función f: L   N tal que:

  ;
  ;

para todo a y b en L. Si es un homomorfismo biyectivo, entonces su inverso es también un homomorfismo, y se llama un isomorfismo de retículos. Los dos retículos implicados son entonces isomorfos; para todos los propósitos prácticos, son iguales y se diferencian solamente en la notación de sus elementos.

Cada homomorfismo es una función monótona entre los dos retículos, pero no cada función monótona da un homomorfismo de retículo: además necesitamos la compatibilidad con supremos e ínfimos finitos.

Retículos particulares

editar

En lo que sigue, por "retículo L" siempre nos referiremos a (L,  ,  ).


  • Retículo distributivo

Un retículo L se denomina distributivo, si sus operaciones son doblemente distributivas:

  •   y
  •  .

Como estos dos juicios son equivalentes entre sí, basta exigir el cumplimiento de una de las dos leyes distributivas.


  • Retículo modular

Un retículo L se denomina modular, si se cumple que:

  •  .

Para un retículo L a su vez son equivalentes:

  • L es modular.
  •  .
  •  .
  •  .

Todo retículo distributivo es modular, pero el juicio inverso no se cumple. Un retículo no modular siempre contiene al retículo   como subretículo.


En caso de que la operación   tenga un elemento neutro 0,

  •  

a este se lo denomina el 'elemento cero' del retículo, es único y es el elemento menor con respecto al orden natural del retículo:

  •  

El retículo se denomina entonces retículo con cota inferior.


En caso de que la operación   tenga un elemento neutro 1,

  •  

a este se lo denomina el 'elemento uno' del retículo. Es único y es el elemento mayor con respecto al orden natural del retículo:

  •  
  •  

El retículo se denomina entonces retículo con cota superior.


El elemento neutral de una de las operaciones es entonces un elemento absorbente de la otra. Un retículo se denomina acotado si tiene cota superior e inferior, es decir, si ambas operaciones tienen elemento neutro.

Para un elemento dado a de un retículo acotado, al elemento b con la propiedad

  •  
  •  

se lo denomina complemento de a. Un retículo acotado, en el que cada uno sus elementos tiene complemento, se denomina complementado.


Un retículo distributivo complementado se denomina álgebra de Boole o retículo de Boole; cuando en lugar del complemento solamente existe un así llamado pseudocomplemento relativo, se habla de una álgebra de Heyting.


  • Retículo completo

Un retículo L se denomina completo si todo subconjunto (inclusive los subconjuntos vacío o posiblemente subconjuntos infinitos) tiene un supremo y un ínfimo.

Para cada subconjunto M basta exigir la existencia del supremo, ya que

  •  

Un elemento a de un retículo completo L se denomina compacto (según una propiedad similar en topología), si todo subconjunto M de L con

  •  

contiene un subconjunto finito E tal que

  •  .

Un retículo L se denomina algebraico, si es completo y si todo elemento de L es un supremo de elementos compactos.

Propiedades

editar

Todo retículo completo L es acotado, con

  •    y
  •  

Todo retículo finito, no vacío L es completo, por lo que también es acotado.

En un retículo distributivo y acotado, el complemento de un elemento a es único si existe, lo que suele denotarse como ac (particularmente en el caso de retículos de subconjuntos) o bien ¬a (particularmente en aplicaciones de lógica).

  • Demostración: Sean b y c complementos de a, queremos mostrar que b = c. Ahora se cumple que b = b   1 = b   (a  c) = (b   a )   (b   c) = b   c. Análogamente se muestra que c = b   c, por lo que b = c.

Sin embargo, si el retículo no es distributivo, pueden existir diversos complementos; va un ejemplo más adelante.

En un retículo distributivo acotado se verifica

  • ¬0 = 1, ¬1 = 0.

Si a tiene un complemento ¬a, entonces también ¬a tiene un complemento, que es:

  • ¬(¬a) = a.

Para otras propiedades de los retículos booleanos véase ese artículo.

Ejemplos de retículos

editar
 
  • Los subgrupos de un grupo, ordenado por la inclusión. El supremo viene dado por el subgrupo generado por la unión de los grupos y el ínfimo viene dado por la intersección.
  • Los submódulos de un módulo, ordenado por la inclusión. El supremo viene dado por de la suma de submódulos y el ínfimo por la intersección.
  • Los ideales de un anillo, ordenado por la inclusión. El supremo viene dado por la suma de ideales y el ínfimo por la intersección.
  • Las topologías en un conjunto, ordenadas por la inclusión. El ínfimo viene dado por la intersección de topologías, y el supremo por la topología generada por la unión de las topologías.
  • El retículo de todas las relaciones de equivalencia en un conjunto; la relación de equivalencia ~ se considera ser más pequeño (o "más fino") que ≈ si x~y implica siempre xy.

El teorema de Knaster-Tarski establece que el conjunto de puntos fijos de una función monótona en un retículo completo es asimismo un retículo completo.

El retículo de submódulos de un módulo y el retículo de los subgrupos normales de un grupo tienen la propiedad especial que x   (y   (x   z)) = (x   y)   (x   z) para todo x, y y z en el retículo. Un retículo con esta propiedad se llama un retículo modular. La condición de la modularidad puede también ser establecida como sigue: Si xz entonces para todo y tenemos la identidad x   (y   z) = (x   y)   z.

Distributividad

editar
Diagramas de Hasse de dos típicos retículos no-distributivos.
El retículo diamante, M3.
El retículo pentágono, N5.

Un retículo se llama distributivo si   distribuye a  , es decir, x   (y   z) = (x   y)   (x   z). equivalentemente,   distribuye  . Todos los retículos distributivos son modulares. Dos tipos importantes de retículos distributivos son los conjuntos totalmente ordenados y las álgebras booleanas (como el retículo de todos los subconjuntos de un conjunto dado). El retículo de los números naturales, ordenados por divisibilidad, es también distributivo. Otras leyes comunes de distributividad (especialmente la ley de distributividad completa) se dan en el artículo sobre distributividad en teoría del orden.

Dos ejemplos fundamentales de retículos no distributivos son el pentágono,   y   que se obtiene de agregarle un elemento mínimo y un máximo a la anticadena de tres elementos. Obviamente si hacemos esto con una anticadena de n elementos, obtendremos el retículo   que tampoco es distributivo. Los anteriores ejemplos son fundamentales en la medida en que cualquier retículo no distributivo está caracterizado por contener como subretículo a una copia de   o de  .

Nociones importantes de la teoría de retículos

editar

En lo siguiente, sea L un retículo. Definimos algunas nociones de la teoría del orden que son de importancia particular en teoría de retículos.

Un elemento x de L se llama supremo-irreducible si y solo si

  • x = a   b implica x = a o x = b para cualquier a, b en L,
  • si L tiene un 0, de x se requiere a veces ser diferente de 0.

Cuando la primera condición se generaliza a supremos arbitrarios Vai, x se llama totalmente supremo-irreducible. la noción dual se llama ínfimo-irreducibilidad. A veces uno también utiliza los términos  -irreducibles y  -irreducibles, respectivamente.

Un elemento x de L se llama supremo-primo si y solo si

  • xa   b implica x a o xb,
  • Si L tiene 0, de x se requiere a veces ser diferente de 0.

Una vez más esto se puede generalizar para obtener la noción totalmente supremo-primo y dualizar para ínfimo-primo. Cualquier elemento supremo-primo es también supremo-irreducible, y cualquier elemento ínfimo-primo es también ínfimo-irreducible. Si el retículo es distributivo el inverso es también verdad.

Otras nociones importantes en teoría de retículos son ideal y su noción dual filtro. Ambos términos describen subconjuntos especiales de un retículo (o de cualquier conjunto parcialmente ordenado en general). Los detalles se pueden encontrar en los artículos respectivos.

Referencias

editar
  1. Ralph P. Grimaldi (1998). «7.20». Matemáticas discreta y combinatoria (3 edición). Pearson Educación. p. 379. ISBN 978-968-444-324-2. 
  2. Hortalá González, María Teresa; Leach Albert, Javier; Rodríguez Artalejo, Mario (2001). «3.3». Matemática discreta y lógica matemática (2 edición). Editorial Complutense. p. 185. ISBN 978-847-491-650-8. 
  3. García Rua, Joaquin (1977). «3». Matemática básica elemental (1 edición). Ministerio de Educación. p. 67. ISBN 978-843-690-216-7. 
  4. Bernard Kolman; Robert C. Busby; Sharon Ross (1997). «7». Estructuras de matemáticas discretas para la computación (Oscar Alfredo Palmas Velasco, trad.) (3 edición). Pearson Educación. p. 231. ISBN 978-968-880-799-6. 
  5. Ralph P. Grimaldi (1998). «7». Matemáticas discreta y combinatoria (3 edición). Pearson Educación. p. 373. ISBN 978-968-444-324-2. 
  6. Villalpando Becerra, José Francisco; García Sandoval, Andrés (2014). «3.8». Matemáticas Discretas. Grupo Editorial Patria. p. 76. ISBN 978-607-438-925-8. 

Bibliografía

editar
  1. Hortalá González, María Teresa; Leach Albert, Javier; Rodríguez Artalejo, Mario (2001). «3». Matemática discreta y lógica matemática (2 edición). Editorial Complutense. p. 161. ISBN 978-847-491-650-8. 
  2. García Rua, Joaquin (1977). «IV 3». Matemática básica elemental. Ministerio de Educación y Ciencia. p. 67. ISBN 978-843-690-216-7. 
  3. George Grätzer, 1978. General Lattice Theory. Birkhäuser. ISBN 9783764369965.
  4. Robert P. Dilworth y Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice-Hall. ISBN 9780130222695.
  5. Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society. ISBN 9780821810255
  6. Hans Hermes, 1963. La Teoría de Retículos y Su Aplicación a la Lógica Matemática. Consejo Superior de Investigaciones Científicas. ISBN 9788400031039