En matemáticas , en el área de la teoría del orden , una celosía libre es el objeto libre correspondiente a una celosía . Como objetos libres, tienen la propiedad universal .
Definicion formal
Se puede usar cualquier conjunto X para generar el FX de semirretículo libre . La semirrejilla libre se define como formada por todos los subconjuntos finitos de X , con la operación de semirrejilla dada por la unión de conjuntos ordinarios . La semirrejilla libre tiene la propiedad universal . El morfismo universal es ( FX , η) , donde η es el mapa unitario η: X → FX que lleva x ∈ X al conjunto singleton { x }. La propiedad universal es entonces la siguiente: dado cualquier mapa f : X → L de X a alguna semirrejilla arbitraria L , existe un homomorfismo de semirrejilla único tal que . El mapapuede estar escrito explícitamente; es dado por
dónde denota la operación semilattice en L . Esta construcción puede ser promovida de semirretillas a celosías [ aclaración necesaria ] ; construyendo el mapa tendrá las mismas propiedades que la celosía.
La construcción X ↦ FX es entonces un funtor de la categoría de conjuntos a la categoría de celosías. El functor F se deja adjunto al functor olvidadizo desde las celosías hasta sus conjuntos subyacentes. La celosía libre es un objeto libre .
Problema de palabra
|
|
El problema verbal de las celosías libres tiene algunos aspectos interesantes. Considere el caso de retículas acotadas , es decir, estructuras algebraicas con las dos operaciones binarias ∨ y ∧ y las dos constantes ( operaciones nulares ) 0 y 1. El conjunto de todas las expresiones bien formadas que se pueden formular usando estas operaciones en elementos de una determinada El conjunto de generadores X se denominará W ( X ). Este conjunto de palabras contiene muchas expresiones que resultan denotar valores iguales en todas las celosías. Por ejemplo, si a es algún elemento de X , entonces a ∨ 1 = 1 y a ∧ 1 = a . El problema verbal de las celosías delimitadas libres es el problema de determinar cuál de estos elementos de W ( X ) denota el mismo elemento en la celosía libre delimitada FX y, por lo tanto, en cada celosía acotada.
El problema verbal se puede resolver 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:
- w = v (esto se puede restringir al caso donde w y v son elementos de X ),
- w = 0,
- v = 1,
- w = w 1 ∨ w 2 y tanto w 1 ≤ ~ v como w 2 ≤ ~ v se mantienen,
- w = w 1 ∧ w 2 y, o bien w 1 ≤ ~ v o w 2 ≤ ~ v sostiene,
- v = v 1 ∨ v 2 y w ≤ ~ v 1 o w ≤ ~ v 2 se cumple,
- v = v 1 ∧ v 2 y tanto w ≤ ~ v 1 como w ≤ ~ v 2 se mantienen.
Esto define un preorden ≤ ~ en W ( X ), por lo que una relación de equivalencia puede ser definida por w ~ v cuando w ≤ ~ v y v ≤ ~ w . Entonces se puede mostrar que el espacio cociente parcialmente ordenado W ( X ) / ~ es el retículo FX libre acotado . [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 retícula acotada si y solo si w ≤ ~ v y v ≤ ~ w ; las últimas condiciones pueden decidirse eficazmente utilizando la definición inductiva anterior. La tabla muestra un ejemplo de cálculo para mostrar que las palabras x ∧ z y x ∧ z ∧ ( x ∨ y ) denotan el mismo valor en cada retícula acotada. El caso de las celosías que no están delimitadas se trata de manera similar, omitiendo las reglas 2. y 3. en la construcción anterior.
La solución del problema verbal en celosías libres tiene varios corolarios interesantes. Una es que la red libre de un conjunto de generadores de tres elementos es infinita. De hecho, incluso se puede demostrar que cada celosía libre en tres generadores contiene una subred que es libre para un conjunto de cuatro generadores. Por inducción , lo que finalmente produce una subred libre en numerablemente muchos generadores. [3] Esta propiedad recuerda a la universalidad de SQ en grupos .
La prueba de que la red libre en tres generadores es infinita procede definiendo inductivamente
- p n 1 = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p n )))))
donde x , y y z son los tres generadores y p 0 = x . Entonces se muestra, usando las relaciones inductivas del problema verbal, que p n +1 es estrictamente mayor [4] que p n , y por lo tanto, todas las infinitas palabras p n se evalúan a diferentes valores en la red libre FX .
La celosía libre completa
Otro corolario es que la celosía libre completa (en tres o más generadores) "no existe", en el sentido de que es una clase propiamente dicha . La prueba de esto también se deriva del problema verbal. Para definir un entramado completo en términos de relaciones, no basta con utilizar las relaciones finitarias de encuentro y unión ; también se deben tener relaciones infinitas que definan el encuentro y la unión de subconjuntos infinitos. Por ejemplo, la relación infinitaria correspondiente a "join" puede definirse como
Aquí, f es un mapa de los elementos de un cardinal N a FX ; el operadordenota el supremo, en el sentido de que lleva la imagen de f a su unión. Esto es, por supuesto, idéntico a "unirse" cuando N es un número finito; el objetivo de esta definición es definir join como una relación, incluso cuando N es un cardinal infinito.
Los axiomas de la ordenación previa del problema verbal pueden ir acompañados de los dos operadores infinitarios correspondientes a meet y unir. Después de hacerlo, se amplía la definición dea un índice ordinalmente dada por
Cuándo es un ordinal límite . Entonces, como antes, uno puede mostrar que es estrictamente mayor que . Por lo tanto, hay al menos tantos elementos en la celosía libre completa como ordinales y, por lo tanto, la celosía libre completa no puede existir como un conjunto y, por lo tanto, debe ser una clase adecuada.
Referencias
- ^ Philip M. Whitman , "Celosías libres" , Ann. Matemáticas. 42 (1941) págs. 325–329
- ^ Philip M. Whitman, "Free Lattices II" , Ann. Matemáticas. 43 (1941) págs. 104-115
- ↑ LA Skornjakov, Elements of Lattice Theory (1977) Adam Hilger Ltd. (ver págs. 77-78)
- ^ es decir, p n ≤ ~ p n +1 , pero no p n +1 ≤ ~ p n
- Peter T. Johnstone, Stone Spaces , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ( ISBN 0-521-23893-5 ) (Ver capítulo 1)