En matemáticas , en el área de la teoría del orden , un retículo libre es el objeto libre correspondiente a un retículo . Como objetos libres, tienen la propiedad universal .
Puesto que el concepto de red puede axiomatizarse en términos de dos operaciones y satisfacer ciertas identidades, la categoría de todas las redes constituye una variedad (álgebra universal) , y por lo tanto existen (por principios generales del álgebra universal ) objetos libres dentro de esta categoría: redes en las que sólo se cumplen aquellas relaciones que se siguen de los axiomas generales.
Estas redes libres pueden caracterizarse utilizando la propiedad universal pertinente . Concretamente, la red libre es un funtor de conjuntos a redes, asignando a cada conjunto la red libre equipada con una función de conjunto que asigna a cada uno el elemento correspondiente . La propiedad universal de estos es que para cualquier función de a alguna red arbitraria existe un homomorfismo de red único que satisface , o como un diagrama conmutativo : El funtor es adjunto por izquierda al funtor olvidadizo de redes a sus conjuntos subyacentes.
Con frecuencia es posible demostrar cosas sobre la red libre directamente usando la propiedad universal, pero tales argumentos tienden a ser bastante abstractos, por lo que una construcción concreta proporciona una presentación alternativa valiosa.
En el caso de semirretículos , es fácil dar una construcción explícita del semirretículo libre ; esto ayuda a ilustrar varias características de la definición por medio de una propiedad universal. Concretamente, el semirretículo libre puede realizarse como el conjunto de todos los subconjuntos finitos no vacíos de , con la unión de conjuntos ordinaria como la operación de unión . La función mapea elementos de a conjuntos singleton , es decir, para todos los . Para cualquier semirretículo y cualquier función de conjunto , el morfismo universal correspondiente está dado por donde denota la operación de semirretículo en .
Esta forma de es forzada por la propiedad universal: cualquier puede escribirse como una unión finita de elementos en la forma para algunos , la igualdad en la propiedad universal dice , y finalmente el estado de homomorfismo de implica para todos . Cualquier extensión de a subconjuntos infinitos de (si es que hay uno) no necesita, sin embargo, estar determinada de manera única por estas condiciones, por lo que no puede haber en ningún elemento correspondiente a subconjuntos infinitos de .
De manera similar, es posible definir un funtor libre para semirretículos inferiores , pero la combinación no produce el retículo libre de varias maneras, porque se trata simplemente como un conjunto:
La estructura real de la red libre es considerablemente más compleja que la de la semired libre.
El problema verbal para redes libres tiene algunos aspectos interesantes. Consideremos el caso de redes acotadas , es decir, estructuras algebraicas con las dos operaciones binarias ∨ y ∧ y las dos constantes ( operaciones nularias ) 0 y 1. El conjunto de todas las expresiones bien formadas que se pueden formular usando estas operaciones sobre elementos de un conjunto dado de generadores X se llamará W ( X ). Este conjunto de palabras contiene muchas expresiones que resultan denotar valores iguales en cada red. Por ejemplo, si a es algún elemento de X , entonces a ∨ 1 = 1 y a ∧ 1 = a . El problema verbal para redes acotadas libres es el problema de determinar cuál de estos elementos de W ( X ) denota el mismo elemento en la red acotada libre FX , y por lo tanto en cada red acotada.
El problema de palabras puede resolverse de la siguiente manera. Una relación ≤ ~ en W ( X ) puede definirse inductivamente estableciendo w ≤ ~ v si y solo si se cumple una de las siguientes condiciones:
Esto define un preorden ≤ ~ en W ( X ), por lo que una relación de equivalencia puede definirse por w ~ v cuando w ≤ ~ v y v ≤ ~ w . Entonces se puede demostrar que el espacio cociente parcialmente ordenado W ( X )/~ es la red acotada libre FX . [1] [2] Las clases de equivalencia de W ( X )/~ son los conjuntos de todas las palabras w y v con w ≤ ~ v y v ≤ ~ w . Dos palabras bien formadas v y w en W ( X ) denotan el mismo valor en cada red acotada si y solo si w ≤ ~ v y v ≤ ~ w ; las últimas condiciones se pueden decidir efectivamente usando la definición inductiva anterior. La tabla muestra un ejemplo de cálculo para demostrar que las palabras x ∧ z y x ∧ z ∧( x ∨ y ) denotan el mismo valor en cada red acotada. El caso de redes que no están acotadas se trata de manera similar, omitiendo las reglas 2. y 3. en la construcción anterior.
La solución del problema verbal sobre redes libres tiene varios corolarios interesantes. Uno de ellos es que la red libre de un conjunto de generadores de tres elementos es infinita. De hecho, se puede incluso demostrar que cada red libre de tres generadores contiene una subred que es libre para un conjunto de cuatro generadores. Por inducción , esto finalmente produce una subred libre en una cantidad contable de generadores. [3] Esta propiedad recuerda a la universalidad SQ en grupos .
La prueba de que la red libre en tres generadores es infinita se realiza definiendo inductivamente
donde x , y y z son los tres generadores, y p 0 = x . Luego se muestra, usando las relaciones inductivas del problema de palabras, que p n +1 es estrictamente mayor [4] que p n , y por lo tanto todas las infinitas palabras p n evalúan valores diferentes en la red libre FX .
Otro corolario es que la red libre completa (en tres o más generadores) "no existe", en el sentido de que es una clase propia . La prueba de esto se desprende también del problema de palabras. Para definir una red completa en términos de relaciones, no basta con utilizar las relaciones finitarias de encuentro y unión ; también se deben tener relaciones infinitarias que definan el encuentro y la unión de subconjuntos infinitos. Por ejemplo, la relación infinitaria correspondiente a "unión" puede definirse como
Aquí, f es una función de los elementos de un cardinal N a FX ; el operador denota el supremo, ya que lleva la imagen de f a su unión. Esto es, por supuesto, idéntico a "unir" cuando N es un número finito; el objetivo de esta definición es definir la unión como una relación, incluso cuando N es un cardinal infinito.
Los axiomas de la preordenación del problema verbal pueden ser unidos por los dos operadores infinitarios correspondientes a encontrarse y unirse. Después de hacerlo, se extiende la definición de a un índice ordinal dado por
cuando es un ordinal límite . Entonces, como antes, se puede demostrar que es estrictamente mayor que . Por lo tanto, hay al menos tantos elementos en la red libre completa como ordinales y, por lo tanto, la red libre completa no puede existir como un conjunto y, por lo tanto, debe ser una clase propia.
