celosía libre

Concepto matemático

En matemáticas , en el área de la teoría del orden , una red libre es el objeto libre correspondiente a una red . Como objetos libres, tienen la propiedad universal .

Definicion formal

Debido a que el concepto de red puede axiomatizarse en términos de dos operaciones y que satisfacen ciertas identidades, la categoría de todas las redes constituye una variedad (álgebra universal) y, por lo tanto, existen (según principios generales del álgebra universal ) objetos libres dentro de esta categoría: retículos donde sólo se mantienen aquellas relaciones que se derivan de los axiomas generales. ${\displaystyle \wedge }$ ${\displaystyle \vee }$

Estas redes libres pueden caracterizarse utilizando la propiedad universal relevante . Concretamente, el retículo libre es un functor de conjuntos a retículos, asignando a cada conjunto el retículo libre provisto de un mapa de conjuntos asignando a cada uno el elemento correspondiente . La propiedad universal de estos es que para cualquier aplicación desde hasta alguna red arbitraria existe un homomorfismo de red único que satisface , o como un diagrama conmutativo : ${\displaystyle F}$ ${\displaystyle X}$ ${\displaystyle F(X)}$ ${\displaystyle \eta \colon X\longrightarrow F(X)}$ ${\displaystyle x\in X}$ ${\displaystyle \eta (x)\in F(X)}$ ${\displaystyle f\colon X\longrightarrow L}$ ${\displaystyle X}$ ${\displaystyle L}$ ${\displaystyle {\tilde {f}}\colon F(X)\longrightarrow L}$ ${\displaystyle f={\tilde {f}}\circ \eta }$

$${\displaystyle {\begin{array}{cccc}X&{\stackrel {\eta }{\longrightarrow }}&F(X)\\&\!\forall f\searrow &{\Bigg \downarrow }\exists _{1}{\tilde {f}}\!\!\!\!\!\!\!\!\!\!&\quad \\&&L\end{array}}}$$

deja adjuntofuntor olvidadizo ${\displaystyle F}$

Con frecuencia es posible demostrar cosas sobre la red libre utilizando directamente la propiedad universal, pero tales argumentos tienden a ser bastante abstractos, por lo que una construcción concreta proporciona una presentación alternativa valiosa.

Semiredes

En el caso de semiredes , es sencillo dar una construcción explícita de la semired libre ; esto ayuda a ilustrar varias características de la definición a modo de propiedad universal. Concretamente, la semired libre puede realizarse como el conjunto de todos los subconjuntos finitos no vacíos de , con la unión de conjuntos ordinarios como operación de unión . El mapa asigna elementos de a conjuntos singleton , es decir, para todos . Para cualquier semired y cualquier mapa conjunto , el morfismo universal correspondiente viene dado por ${\displaystyle F_{\vee }(X)}$ ${\displaystyle F_{\vee }(X)}$ ${\displaystyle X}$ ${\displaystyle \vee }$ ${\displaystyle \eta \colon X\longrightarrow F_{\vee }(X)}$ ${\displaystyle X}$ ${\displaystyle \eta (x)=\{x\}}$ ${\displaystyle x\in X}$ ${\displaystyle L}$ ${\displaystyle f\colon X\longrightarrow L}$ ${\displaystyle {\tilde {f}}\colon F_{\vee }(X)\longrightarrow L}$

$${\displaystyle {\tilde {f}}(S)=\bigvee _{x\in S}f(x)\qquad {\text{for all }}S\in F_{\vee }(X)}$$

${\displaystyle \bigvee }$ ${\displaystyle L}$

Esta forma de es forzada por la propiedad universal: cualquiera 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 . Sin embargo, cualquier extensión de a infinitos subconjuntos de (si es que hay uno) no necesita estar determinada únicamente por estas condiciones, por lo que no puede haber ningún elemento correspondiente a infinitos subconjuntos de . ${\displaystyle {\tilde {f}}}$ ${\displaystyle S\in F_{\vee }(X)}$ ${\displaystyle \eta (x)}$ ${\displaystyle x\in X}$ ${\displaystyle {\tilde {f}}{\bigl (}\eta (x){\bigr )}=f(x)}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle {\tilde {f}}(S_{1}\cup S_{2})={\tilde {f}}(S_{1})\vee {\tilde {f}}(S_{2})}$ ${\displaystyle S_{1},S_{2}\in F_{\vee }(X)}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle X}$ ${\displaystyle F_{\vee }(X)}$ ${\displaystyle X}$

Semirretículas inferiores

De manera similar, es posible definir un funtor libre para semiredes inferiores , pero la combinación no logra producir la red libre de varias maneras, porque se trata solo como un conjunto: ${\displaystyle F_{\wedge }}$ ${\displaystyle F_{\wedge }(F_{\vee }(X))}$ ${\displaystyle F(X)}$ ${\displaystyle F_{\wedge }}$ ${\displaystyle F_{\vee }(X)}$

• la operación de unión no se extiende a los nuevos elementos de , ${\displaystyle \vee }$ ${\displaystyle F_{\wedge }(F_{\vee }(X))}$
• no se respeta el orden parcial existente ; puntos de vista y como no relacionados, no entenderlo debería hacer . ${\displaystyle F_{\vee }(X)}$ ${\displaystyle F_{\wedge }}$ ${\displaystyle a}$ ${\displaystyle a\vee b}$ ${\displaystyle a\wedge (a\vee b)=a}$

La estructura real de la red libre es considerablemente más compleja que la de la semired libre. ${\displaystyle F(X)}$

Problema de palabra

El problema verbal de celosías libres tiene algunos aspectos interesantes. Considere el caso de redes acotadas , es decir, estructuras algebraicas con las dos operaciones binarias ∨ y ∧ y las dos constantes ( operaciones nulas ) 0 y 1. El conjunto de todas las expresiones bien formadas que se pueden formular utilizando estas operaciones sobre elementos de un determinado El conjunto 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 tanto, en cada red acotada.

El problema verbal se puede resolver de la siguiente manera. Una relación ≤ _~ en W ( X ) se puede definir inductivamente estableciendo w ≤ _~ v si y sólo si se cumple una de las siguientes condiciones:

1.   w = v (esto puede restringirse al caso en el que w y v son elementos de X ),
2.   w = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ y ambos w ₁ ≤ _~ v y w ₂ ≤ _~ v se mantienen,
5.   w = w ₁ ∧ w ₂ y w ₁ ≤ _~ v o w ₂ ≤ _~ v se cumple,
6.   v = v ₁ ∨ v ₂ y w ≤ _~ v ₁ o w ≤ _~ v ₂ se cumple,
7.   v = v ₁ ∧ v ₂ y tanto w ≤ _~ v ₁ como w ≤ _~ v ₂ se mantienen.

Esto define un preorden ≤ _~ en W ( X ), por lo que se puede definir una relación de equivalencia mediante 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 sólo si w ≤ _~ v y v ≤ _~ w ; las últimas condiciones se pueden decidir efectivamente 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 red acotada. El caso de celosías 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. Una es que la red libre de un conjunto de generadores de tres elementos es infinita. De hecho, incluso se puede demostrar que cada red libre en tres generadores contiene una subred que está libre para un conjunto de cuatro generadores. Por inducción , esto eventualmente produce una subred libre en muchos generadores. ^[3] Esta propiedad recuerda a la universalidad SQ en grupos .

La prueba de que la red libre en tres generadores es infinita procede definiendo inductivamente

p _{norte +1} = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p _norte )))))

donde x , y y z son los tres generadores, y p ₀ = x . Luego se muestra, utilizando 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 con valores diferentes en la red libre FX .

La red libre completa

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 planteado. Para definir una red completa en términos de relaciones, no basta con utilizar las relaciones finitas 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 infinita correspondiente a "unir" se puede definir como

${\displaystyle \operatorname {sup} _{N}:(f:N\to FX)}$

Aquí, f es una aplicación de los elementos de un cardinal N a FX ; el operador denota el supremo, en el sentido de que toma la imagen de f para su unión. Por supuesto, esto es 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. ${\displaystyle \operatorname {sup} _{N}}$

Los axiomas del preordenamiento del problema verbal pueden estar unidos por los dos operadores infinitos correspondientes a encontrarse y unirse. Después de hacerlo, se extiende la definición de a un indexado ordinal dado por ${\displaystyle p_{n}}$ ${\displaystyle p_{\alpha }}$

${\displaystyle p_{\alpha }=\operatorname {sup} \{p_{\beta }\mid \beta <\alpha \}}$

cuando es un límite ordinal . 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 adecuada. ${\displaystyle \alpha }$ ${\displaystyle p_{\alpha +1}}$ ${\displaystyle p_{\alpha }}$

Referencias

1. Philip M. Whitman , "Celosías libres", Ann. Matemáticas. 42 (1941) págs. 325–329
2. Philip M. Whitman, "Free Lattices II", Ann. Matemáticas. 43 (1941) págs. 104-115
3. LA Skornjakov, Elementos de la teoría del entramado (1977) Adam Hilger Ltd. (véanse las páginas 77-78)
4. 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)