Hispanopedia Wiki
Articulo de referencia

Red (orden)

Un retículo es una estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría del orden y el álgebra abstracta . Consiste en un conjunto parcialmente ordenado...

Hispanopedia WikiContenido en espanolLectura gratuita

Un retículo es una estructura abstracta estudiada en las subdisciplinas matemáticas de la teoría del orden y el álgebra abstracta . Consiste en un conjunto parcialmente ordenado en el que cada par de elementos tiene un supremo único (también llamado cota superior mínima o unión ) y un ínfimo único (también llamado cota inferior máxima o intersección ). Un ejemplo lo da el conjunto potencia de un conjunto, parcialmente ordenado por inclusión , para el cual el supremo es la unión y el ínfimo es la intersección . Otro ejemplo lo dan los números naturales , parcialmente ordenados por divisibilidad , para los cuales el supremo es el mínimo común múltiplo y el ínfimo es el máximo común divisor .

Las retículas también pueden caracterizarse como estructuras algebraicas que satisfacen ciertas identidades axiomáticas . Dado que ambas definiciones son equivalentes, la teoría de retículas se basa tanto en la teoría del orden como en el álgebra universal . La clase de retículas puede generalizarse a semirretículas , y algunas subclases notables de retículas son las álgebras de Heyting , las álgebras booleanas , las retículas distributivas y las retículas geométricas ( matroides ). Todas estas estructuras reticulares admiten descripciones tanto algebraicas como basadas en la teoría del orden .

El subcampo que estudia las redes se llama teoría de redes .

Definición

Una red puede definirse bien desde el punto de vista de la teoría del orden, como un conjunto parcialmente ordenado, o bien como una estructura algebraica.

Como conjunto parcialmente ordenado

Un conjunto parcialmente ordenado (poset) se denomina retículo si es a la vez un semirretículo de unión y de intersección , es decir, cada subconjunto de dos elementos tiene una unión (es decir, el límite superior mínimo, denotado por ) y dualmente una intersección (es decir, el límite inferior máximo, denotado por ). Esta definición hace que y sean operaciones binarias . Ambas operaciones son monótonas con respecto al orden dado: y implica que y(L,≤){\displaystyle (L,\leq )}{a,b}⊆L{\displaystyle \{a,b\}\subseteq L}a∨b{\displaystyle a\vee b}a∧b{\displaystyle a\wedge b}∧{\displaystyle \,\wedge \,}∨{\displaystyle \,\vee \,}a1≤a2{\displaystyle a_{1}\leq a_{2}}b1≤b2{\displaystyle b_{1}\leq b_{2}}a1∨b1≤a2∨b2{\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}a1∧b1≤a2∧b2.{\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}

It follows by an induction argument that every non-empty finite subset of a lattice has a least upper bound and a greatest lower bound. With additional assumptions, further conclusions may be possible; see Completeness (order theory) for more discussion of this subject. That article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connections between related partially ordered sets—an approach of special interest for the category theoretic approach to lattices, and for formal concept analysis.

Given a subset of a lattice, H⊆L,{\displaystyle H\subseteq L,} meet and join restrict to partial functions – they are undefined if their value is not in the subset H.{\displaystyle H.} The resulting structure on H{\displaystyle H} is called a partial lattice. In addition to this extrinsic definition as a subset of some other algebraic structure (a lattice), a partial lattice can also be intrinsically defined as a set with two partial binary operations satisfying certain axioms.[1]

As algebraic structure

A lattice is an algebraic structure(L,∨,∧){\displaystyle (L,\vee ,\wedge )}, consisting of a set L{\displaystyle L} and two binary, commutative and associative operations∨{\displaystyle \vee } and ∧{\displaystyle \wedge } on L{\displaystyle L} satisfying the following axiomatic identities (sometimes called absorption laws) for all elements a,b∈L{\displaystyle a,b\in L} : a∨(a∧b)=a{\displaystyle a\vee (a\wedge b)=a}a∧(a∨b)=a{\displaystyle a\wedge (a\vee b)=a}

The following two identities are also usually regarded as axioms, even though they follow from the two absorption laws taken together.[2] These are called idempotent laws. a∨a=a{\displaystyle a\vee a=a}a∧a=a{\displaystyle a\wedge a=a}

These axioms assert that both (L,∨){\displaystyle (L,\vee )} and (L,∧){\displaystyle (L,\wedge )} are semilattices. The absorption laws, the only axioms above in which both meet and join appear, distinguish a lattice from an arbitrary pair of semilattice structures and assure that the two semilattices interact appropriately. In particular, each semilattice is the dual of the other. The absorption laws can be viewed as a requirement that the meet and join semilattices define the same partial order.

Connection between the two definitions

An order-theoretic lattice gives rise to the two binary operations ∨{\displaystyle \vee } and ∧.{\displaystyle \wedge .} Since the commutative, associative and absorption laws can easily be verified for these operations, they make (L,∨,∧){\displaystyle (L,\vee ,\wedge )} into a lattice in the algebraic sense.

Lo contrario también es cierto. Dada una red definida algebraicamente, se puede definir un orden parcial estableciendo para todos los elementos. Las leyes de absorción aseguran que ambas definiciones son equivalentes: y dualmente para la otra dirección.(L,∨,∧),{\displaystyle (L,\vee ,\wedge ),}≤{\displaystyle \leq }L{\displaystyle L}a≤b if a=a∧b, or {\displaystyle a\leq b{\text{ if }}a=a\wedge b,{\text{ or }}}a≤b if b=a∨b,{\displaystyle a\leq b{\text{ if }}b=a\vee b,}a,b∈L.{\displaystyle a,b\in L.}a=a∧b implies b=b∨(b∧a)=(a∧b)∨b=a∨b{\displaystyle a=a\wedge b{\text{ implies }}b=b\vee (b\wedge a)=(a\wedge b)\vee b=a\vee b}

Ahora se puede comprobar que la relación introducida de esta manera define un orden parcial dentro del cual se dan encuentros y uniones binarias a través de las operaciones originales y≤{\displaystyle \leq }∨{\displaystyle \vee }∧.{\displaystyle \wedge .}

Dado que las dos definiciones de retículo son equivalentes, se pueden invocar libremente aspectos de cualquiera de ellas de la manera que mejor se adapte al propósito en cuestión.

Retículo acotado

Un retículo acotado es un retículo que además tiene un elemento mayor (también llamado máximo o elemento superior , y denotado por o ) y un elemento menor (también llamado mínimo o inferior , denotado por o ), que satisfacen 1{\displaystyle 1}⊤{\displaystyle \top }0{\displaystyle 0}⊥{\displaystyle \bot }0≤x≤1 for every x∈L.{\displaystyle 0\leq x\leq 1\;{\text{ for every }}x\in L.}

Un retículo acotado también puede definirse como una estructura algebraica de la forma tal que es un retículo, (el fondo del retículo) es el elemento identidad para la operación de unión y (el borde superior del retículo) es el elemento identidad para la operación de intersección.(L,∨,∧,0,1){\displaystyle (L,\vee ,\wedge ,0,1)}(L,∨,∧){\displaystyle (L,\vee ,\wedge )}0{\displaystyle 0}∨,{\displaystyle \vee ,}1{\displaystyle 1}∧.{\displaystyle \wedge .}a∨0=a{\displaystyle a\vee 0=a}a∧1=a{\displaystyle a\wedge 1=a}

Se puede demostrar que un conjunto parcialmente ordenado es un retículo acotado si y solo si todo conjunto finito de elementos (incluido el conjunto vacío) tiene una unión y una intersección.

Cada retículo puede incrustarse en un retículo acotado añadiendo un elemento máximo y uno mínimo. Además, todo retículo finito no vacío es acotado, tomando la unión (respectivamente, la intersección) de todos los elementos, denotada por (respectivamente ), donde es el conjunto de todos los elementos.1=⋁L=a1∨⋯∨an{\textstyle 1=\bigvee L=a_{1}\lor \cdots \lor a_{n}}0=⋀L=a1∧⋯∧an{\textstyle 0=\bigwedge L=a_{1}\land \cdots \land a_{n}}L={a1,…,an}{\displaystyle L=\left\{a_{1},\ldots ,a_{n}\right\}}

Conexión con otras estructuras algebraicas

Los retículos guardan cierta relación con la familia de estructuras algebraicas de tipo grupo . Dado que las operaciones de intersección y unión conmutan y asocian, un retículo puede considerarse como la suma de dos semigrupos conmutativos con el mismo dominio. En el caso de un retículo acotado, estos semigrupos son, de hecho, monoides conmutativos . La ley de absorción es la única identidad definitoria propia de la teoría de retículos. Un retículo acotado también puede concebirse como una estructura conmutativa sin el axioma distributivo.

Por conmutatividad, asociatividad e idempotencia, se puede pensar en la unión y la intersección como operaciones sobre conjuntos finitos no vacíos, en lugar de sobre pares de elementos. En un retículo acotado, la unión y la intersección del conjunto vacío también se pueden definir (como y respectivamente). Esto hace que los retículos acotados sean algo más naturales que los retículos generales, y muchos autores exigen que todos los retículos sean acotados.0{\displaystyle 0}1,{\displaystyle 1,}

La interpretación algebraica de los retículos juega un papel esencial en el álgebra universal .

Ejemplos

  • Para cualquier conjunto, la colección de todos sus subconjuntos (denominada conjunto potencia de ) se puede ordenar mediante la inclusión de subconjuntos para obtener un retículo acotado por sí mismo y el conjunto vacío. En este retículo, el supremo viene dado por la unión de conjuntos y el ínfimo por la intersección de conjuntos (véase la figura 1).A,{\displaystyle A,}A{\displaystyle A}A{\displaystyle A}A{\displaystyle A} 
  • Para cualquier conjunto, la colección de todos los subconjuntos finitos ordenados por inclusión, también es un retículo, y estará acotada si y solo si es finito.A,{\displaystyle A,}A,{\displaystyle A,}A{\displaystyle A}
  • Para cualquier conjunto, la colección de todas las particiones ordenadas por refinamiento es una red (ver Fig. 3).A,{\displaystyle A,}A,{\displaystyle A,} 
  • Los enteros positivos, en su orden habitual, forman una red ilimitada bajo las operaciones de "mínimo" y "máximo". El 1 es el mínimo; no hay máximo (véase la figura  4).
  • El cuadrado cartesiano de los números naturales, ordenado de manera que si el par es el elemento inferior; no hay elemento superior (ver Fig. 5).(a,b)≤(c,d){\displaystyle (a,b)\leq (c,d)}a≤c and b≤d.{\displaystyle a\leq c{\text{ and }}b\leq d.}(0,0){\displaystyle (0,0)} 
  • Los números naturales también forman una red bajo las operaciones de máximo común divisor y mínimo común múltiplo , con la divisibilidad como relación de orden: si divide a , es el mínimo; es el máximo. La figura 2 muestra una subred finita.a≤b{\displaystyle a\leq b}a{\displaystyle a}b.{\displaystyle b.}1{\displaystyle 1}0{\displaystyle 0} 
  • Toda red completa (véase también más abajo ) es una red acotada (bastante específica). Esta clase da lugar a una amplia gama de ejemplos prácticos .
  • El conjunto de elementos compactos de un retículo aritmético completo es un retículo con un elemento mínimo, donde las operaciones del retículo se definen restringiendo las operaciones respectivas del retículo aritmético. Esta es la propiedad específica que distingue a los retículos aritméticos de los retículos algebraicos , para los cuales los compactos solo forman un semirretículo de unión . Ambas clases de retículos completos se estudian en la teoría de dominios .

A continuación se proporcionan ejemplos adicionales de redes para cada una de las propiedades adicionales que se analizan.

Ejemplos de estructuras no reticulares

La mayoría de los conjuntos parcialmente ordenados no son retículos, incluidos los siguientes.

  • Un conjunto parcialmente ordenado discreto, es decir, un conjunto parcialmente ordenado tal que implica que es un retículo si y solo si tiene como máximo un elemento. En particular, el conjunto parcialmente ordenado discreto de dos elementos no es un retículo.x≤y{\displaystyle x\leq y}x=y,{\displaystyle x=y,}
  • Aunque el conjunto parcialmente ordenado por divisibilidad es un retículo, el conjunto así ordenado no es un retículo porque el par 2, 3 carece de una unión; de manera similar, 2, 3 carece de una intersección en{1,2,3,6}{\displaystyle \{1,2,3,6\}}{1,2,3}{\displaystyle \{1,2,3\}}{2,3,6}.{\displaystyle \{2,3,6\}.}
  • El conjunto parcialmente ordenado por divisibilidad no es un retículo. Cada par de elementos tiene un límite superior y un límite inferior, pero el par 2, 3 tiene tres límites superiores: 12, 18 y 36, ninguno de los cuales es el menor de los tres bajo la propiedad de divisibilidad (12 y 18 no se dividen entre sí). De igual manera, el par 12, 18 tiene tres límites inferiores: 1, 2 y 3, ninguno de los cuales es el mayor de los tres bajo la propiedad de divisibilidad (2 y 3 no se dividen entre sí).{1,2,3,12,18,36}{\displaystyle \{1,2,3,12,18,36\}}

Morfismos de retículos

Imagen  9: Mapa monótono entre retículos que no conserva ni uniones ni encuentros, puesto que yf{\displaystyle f}f(u)∨f(v)=u′∨u′=u′{\displaystyle f(u)\vee f(v)=u^{\prime }\vee u^{\prime }=u^{\prime }}≠{\displaystyle \neq }1′=f(1)=f(u∨v){\displaystyle 1^{\prime }=f(1)=f(u\vee v)}f(u)∧f(v)=u′∧u′=u′{\displaystyle f(u)\wedge f(v)=u^{\prime }\wedge u^{\prime }=u^{\prime }}≠{\displaystyle \neq }0′=f(0)=f(u∧v).{\displaystyle 0^{\prime }=f(0)=f(u\wedge v).}

La noción apropiada de un morfismo entre dos retículos se deduce fácilmente de la definición algebraica anterior . Dados dos retículos y un homomorfismo de retículos de L a M, es una función tal que para todo(L,∨L,∧L){\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}(M,∨M,∧M),{\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}f:L→M{\displaystyle f:L\to M}a,b∈L:{\displaystyle a,b\in L:}f(a∨Lb)=f(a)∨Mf(b), and {\displaystyle f\left(a\vee _{L}b\right)=f(a)\vee _{M}f(b),{\text{ and }}}f(a∧Lb)=f(a)∧Mf(b).{\displaystyle f\left(a\wedge _{L}b\right)=f(a)\wedge _{M}f(b).}

Por lo tanto, se trata de un homomorfismo de las dos semirretículas subyacentes . Cuando se consideran retículas con más estructura, los morfismos también deben "respetar" la estructura adicional. En particular, un homomorfismo de retículas acotadas (generalmente llamado simplemente "homomorfismo de retículas") entre dos retículas acotadas y también debe tener la siguiente propiedad: f{\displaystyle f}f{\displaystyle f}L{\displaystyle L}M{\displaystyle M}f(0L)=0M, and {\displaystyle f\left(0_{L}\right)=0_{M},{\text{ and }}}f(1L)=1M.{\displaystyle f\left(1_{L}\right)=1_{M}.}

En la formulación basada en la teoría del orden, estas condiciones simplemente establecen que un homomorfismo de retículos es una función que preserva las intersecciones y uniones binarias. Para retículos acotados, la preservación de los elementos mínimo y máximo se reduce a la preservación de la unión y la intersección del conjunto vacío.

Todo homomorfismo de retículos es necesariamente monótono con respecto a la relación de orden asociada; véase Función que preserva el límite. Lo contrario no es cierto: la monotonicidad no implica en absoluto la preservación requerida de las intersecciones y uniones (véase la figura  9), aunque una biyección que preserva el orden es un homomorfismo si su inversa también lo preserva.

Dada la definición estándar de isomorfismos como morfismos invertibles, un isomorfismo de retículos es simplemente un homomorfismo de retículos biyectivo . De manera similar, un endomorfismo de retículos es un homomorfismo de retículos de un retículo a sí mismo, y un automorfismo de retículos es un endomorfismo de retículos biyectivo. Los retículos y sus homomorfismos forman una categoría .

Sean y dos retículos con 0 y 1. Un homomorfismo de a se llama 0 , 1 - separador si y solo si ( separa 0 ) y ( separa 1).L{\displaystyle \mathbb {L} }L′{\displaystyle \mathbb {L} '}L{\displaystyle \mathbb {L} }L′{\displaystyle \mathbb {L} '}f−1{f(0)}={0}{\displaystyle f^{-1}\{f(0)\}=\{0\}}f{\displaystyle f}f−1{f(1)}={1}{\displaystyle f^{-1}\{f(1)\}=\{1\}}f{\displaystyle f}

Subredes

Una subred de una red es un subconjunto de que es una red con las mismas operaciones de encuentro y unión que Es decir, si es una red y es un subconjunto de tal que para cada par de elementos tanto como están en entonces es una subred de [ 3 ]L{\displaystyle L}L{\displaystyle L}L.{\displaystyle L.}L{\displaystyle L}M{\displaystyle M}L{\displaystyle L}a,b∈M{\displaystyle a,b\in M}a∧b{\displaystyle a\wedge b}a∨b{\displaystyle a\vee b}M,{\displaystyle M,}M{\displaystyle M}L.{\displaystyle L.}

Una subred de una red es una subred convexa de si y implica que pertenece a para todos los elementos.M{\displaystyle M}L{\displaystyle L}L,{\displaystyle L,}x≤z≤y{\displaystyle x\leq z\leq y}x,y∈M{\displaystyle x,y\in M}z{\displaystyle z}M,{\displaystyle M,}x,y,z∈L.{\displaystyle x,y,z\in L.}

Propiedades de las redes

A continuación, presentamos una serie de propiedades importantes que dan lugar a interesantes clases especiales de retículos. Una de ellas, la acotación, ya se ha tratado.

Lo completo

Un conjunto parcialmente ordenado se denomina retículo completo si todos sus subconjuntos poseen tanto una unión como una intersección. En particular, todo retículo completo es un retículo acotado. Mientras que los homomorfismos de retículos acotados generalmente preservan solo uniones e intersecciones finitas, los homomorfismos de retículos completos deben preservar uniones e intersecciones arbitrarias.

Todo conjunto parcialmente ordenado que sea un semirretículo completo es también un retículo completo. Relacionado con este resultado está el interesante fenómeno de que existen diversas nociones de homomorfismo en competencia para esta clase de conjuntos parcialmente ordenados, dependiendo de si se consideran retículos completos, semirretículos de unión completos, semirretículos de intersección completos o retículos de unión o de intersección completos.

"Retícula parcial" no es lo opuesto a "retícula completa"; más bien, "retícula parcial", "retícula" y "retícula completa" son definiciones cada vez más restrictivas.

Completitud condicional

Un retículo condicionalmente completo es un retículo en el que cada subconjunto no vacío que tiene una cota superior tiene una unión (es decir, una cota superior mínima). Dichos retículos proporcionan la generalización más directa del axioma de completitud de los números reales . Un retículo condicionalmente completo es un retículo completo, o un retículo completo sin su elemento máximo, su elemento mínimo o ambos. [ 4 ] [ 5 ]1,{\displaystyle 1,}0,{\displaystyle 0,}

Distributividad

Dado que los retículos vienen con dos operaciones binarias, es natural preguntarse si una de ellas se distribuye sobre la otra, es decir, si se cumple alguna de las siguientes leyes duales para cada tres elementos :a,b,c∈L,{\displaystyle a,b,c\in L,}

Distributividad de sobre∨{\displaystyle \vee }∧{\displaystyle \wedge }

a∨(b∧c)=(a∨b)∧(a∨c).{\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c).}

Distributividad de sobre∧{\displaystyle \wedge }∨{\displaystyle \vee }

a∧(b∨c)=(a∧b)∨(a∧c).{\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c).}

Un retículo que satisface el primer axioma o, equivalentemente (como se verá), el segundo, se denomina retículo distributivo . [ 6 ] Los únicos retículos no distributivos con menos de 6 elementos se denominan M 3 y N 5 ; [ 7 ] se muestran en las Figuras 10 y 11, respectivamente. Un retículo es distributivo si y solo si no tiene un subretículo isomorfo a M 3 o N 5. [ 8 ] Cada retículo distributivo es isomorfo a un retículo de conjuntos (con unión e intersección como unión y encuentro, respectivamente) . [ 9 ]

Para obtener una visión general de las nociones más fuertes de distributividad que son apropiadas para retículos completos y que se utilizan para definir clases más especiales de retículos, como marcos y retículos completamente distributivos , consulte distributividad en la teoría del orden .

Modularidad

Para algunas aplicaciones la condición de distributividad es demasiado fuerte, y la siguiente propiedad más débil suele ser útil. Un retículo es modular si, para todos los elementos se cumple la siguiente identidad: ( Identidad modular ) Esta condición es equivalente al siguiente axioma: implica ( Ley modular ) De hecho, la desigualdad se cumple en cualquier retículo cuando . [ 10 ] Un retículo es modular si y solo si no tiene un subretículo isomorfo a N 5 (mostrado en la Fig. 11). [ 8 ] Además de los retículos distributivos, ejemplos de retículos modulares son el retículo de submódulos de un módulo (de ahí modular ), el retículo de ideales de dos lados de un anillo y el retículo de subgrupos normales de un grupo . El conjunto de términos de primer orden con el orden "es más específico que" es un retículo no modular utilizado en el razonamiento automatizado .(L,∨,∧){\displaystyle (L,\vee ,\wedge )}a,b,c∈L,{\displaystyle a,b,c\in L,}(a∧c)∨(b∧c)=((a∧c)∨b)∧c.{\displaystyle (a\wedge c)\vee (b\wedge c)=((a\wedge c)\vee b)\wedge c.}a≤c{\displaystyle a\leq c}a∨(b∧c)=(a∨b)∧c.{\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge c.}a∨(b∧c)≤(a∨b)∧c{\displaystyle a\vee (b\wedge c)\leq (a\vee b)\wedge c}a≤c{\displaystyle a\leq c} 

Semimodularidad

Un retículo finito es modular si y solo si es semimodular tanto superior como inferior . Para un retículo de longitud finita, la semimodularidad (superior) es equivalente a la condición de que el retículo sea graduado y su función de rango satisfaga la siguiente condición: [ 11 ]r{\displaystyle r}

r(x)+r(y)≥r(x∧y)+r(x∨y).{\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).}

Otra condición equivalente (para retículos graduados) es la condición de Birkhoff :

para cada uno y en si y ambos cubren entonces cubre ambos yx{\displaystyle x}y{\displaystyle y}L,{\displaystyle L,}x{\displaystyle x}y{\displaystyle y}x∧y,{\displaystyle x\wedge y,}x∨y{\displaystyle x\vee y}x{\displaystyle x}y.{\displaystyle y.}

Un retículo se denomina semimodular inferior si su dual es semimodular. Para retículos finitos, esto significa que las condiciones anteriores se cumplen con y intercambiadas, "cubre" intercambiada con "es cubierto por" e invertidas las desigualdades. [ 12 ]∨{\displaystyle \vee }∧{\displaystyle \wedge }

Continuidad y algebraicidad

En la teoría de dominios , es natural buscar aproximar los elementos en un orden parcial mediante elementos "mucho más simples". Esto conduce a la clase de conjuntos parcialmente ordenados continuos , que consisten en conjuntos parcialmente ordenados donde cada elemento puede obtenerse como el supremo de un conjunto dirigido de elementos que están muy por debajo del elemento. Si además se pueden restringir estos conjuntos dirigidos a los elementos compactos de un conjunto parcialmente ordenado, entonces el conjunto parcialmente ordenado es incluso algebraico . Ambos conceptos pueden aplicarse a retículos de la siguiente manera:

  • Un retículo continuo es un retículo completo que es continuo como un conjunto parcialmente ordenado (poset).
  • Un retículo algebraico es un retículo completo que es algebraico como un conjunto parcialmente ordenado.

Ambas clases poseen propiedades interesantes. Por ejemplo, los retículos continuos pueden caracterizarse como estructuras algebraicas (con operaciones infinitas) que satisfacen ciertas identidades. Si bien no se conoce una caracterización similar para los retículos algebraicos, estos pueden describirse "sintácticamente" mediante sistemas de información de Scott .

Complementos y pseudocomplementos

Sea un retículo acotado con elemento mayor 1 y elemento menor 0. Dos elementos y de son complementarios entre sí si y solo si: L{\displaystyle L}x{\displaystyle x}y{\displaystyle y}L{\displaystyle L}x∨y=1 and x∧y=0.{\displaystyle x\vee y=1\quad {\text{ and }}\quad x\wedge y=0.}

En general, algunos elementos de un retículo acotado pueden no tener complemento, y otros pueden tener más de uno. Por ejemplo, el conjunto con su ordenación usual es un retículo acotado y no tiene complemento. En el retículo acotado N 5 , el elemento tiene dos complementos, a saber, y (véase la figura 11). Un retículo acotado para el cual cada elemento tiene un complemento se denomina retículo complementado .{0,1/2,1}{\displaystyle \{0,1/2,1\}}12{\displaystyle {\tfrac {1}{2}}}a{\displaystyle a}b{\displaystyle b}c{\displaystyle c} 

Un retículo complementado que también es distributivo es un álgebra booleana . Para un retículo distributivo, el complemento de cuando existe es único.x,{\displaystyle x,}

En el caso de que el complemento sea único, escribimos y, equivalentemente, La operación unaria correspondiente sobre llamada complementación, introduce un análogo de la negación lógica en la teoría de retículos.¬x=y{\textstyle \lnot x=y}¬y=x.{\textstyle \lnot y=x.}L,{\displaystyle L,}

Las álgebras de Heyting son un ejemplo de retículos distributivos donde algunos miembros pueden carecer de complementos. Cada elemento de un álgebra de Heyting tiene, por otro lado, un pseudocomplemento , también denotado El pseudocomplemento es el elemento más grande tal que Si el pseudocomplemento de cada elemento de un álgebra de Heyting es de hecho un complemento, entonces el álgebra de Heyting es de hecho un álgebra booleana.z{\displaystyle z}¬x.{\textstyle \lnot x.}y{\displaystyle y}x∧y=0.{\displaystyle x\wedge y=0.}

condición de cadena de Jordan-Dedekind

Una cadena de a es un conjunto donde La longitud de esta cadena es n , o uno menos que su número de elementos. Una cadena es maximal si cubre para todosx0{\displaystyle x_{0}}xn{\displaystyle x_{n}}{x0,x1,…,xn},{\displaystyle \left\{x_{0},x_{1},\ldots ,x_{n}\right\},}x0<x1<x2<…<xn.{\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.}xi{\displaystyle x_{i}}xi−1{\displaystyle x_{i-1}}1≤i≤n.{\displaystyle 1\leq i\leq n.}

Si para cualquier par, y donde todas las cadenas máximas de a tienen la misma longitud, entonces se dice que la red satisface la condición de cadena de Jordan-Dedekind .x{\displaystyle x}y,{\displaystyle y,}x<y,{\displaystyle x<y,}x{\displaystyle x}y{\displaystyle y}

Calificado/clasificado

Un retículo se denomina graduado , a veces clasificado (pero véase Conjunto parcialmente ordenado clasificado para un significado alternativo), si se le puede asignar una función de rango a veces a , compatible con el ordenamiento (de modo que siempre que ) tal que siempre que cubra entonces El valor de la función de rango para un elemento del retículo se denomina su rango .(L,≤){\displaystyle (L,\leq )}r:L→N{\displaystyle r:L\to \mathbb {N} }Z{\displaystyle \mathbb {Z} }r(x)<r(y){\displaystyle r(x)<r(y)}x<y{\displaystyle x<y}y{\displaystyle y}x,{\displaystyle x,}r(y)=r(x)+1.{\displaystyle r(y)=r(x)+1.}

Se dice que un elemento de la red cubre a otro elemento si pero no existe un tal que Aquí, significa yy{\displaystyle y}x,{\displaystyle x,}y>x,{\displaystyle y>x,}z{\displaystyle z}y>z>x.{\displaystyle y>z>x.}y>x{\displaystyle y>x}x≤y{\displaystyle x\leq y}x≠y.{\displaystyle x\neq y.}

Redes libres

Cualquier conjunto puede utilizarse para generar el semirretículo libre. El semirretículo libre se define como el conjunto formado por todos los subconjuntos finitos de con la operación de semirretículo dada por la unión de conjuntos ordinaria . El semirretículo libre posee la propiedad universal . Para el retículo libre sobre un conjunto, Whitman propuso una construcción basada en polinomios sobre los miembros de . [ 13 ] [ 14 ]X{\displaystyle X}FX.{\displaystyle FX.}X,{\displaystyle X,}X,{\displaystyle X,}X{\displaystyle X}

Retículos planos

Cualquier conjunto (generalmente multielemento) también puede usarse para definir un retículo plano , el retículo más pequeño en el que los elementos del conjunto son incomparables o, equivalentemente, el retículo de rango 3 donde es exactamente el conjunto de elementos de rango intermedio. [ 15 ]X{\displaystyle X}X{\displaystyle X}

Nociones importantes de la teoría de retículos

A continuación, definimos algunas nociones de la teoría del orden importantes para la teoría de retículos. En lo que sigue, sea un elemento de algún retículo llamado:x{\displaystyle x}L.{\displaystyle L.}x{\displaystyle x}

  • Irreducible por unión si implica para todo Si tiene un elemento inferior algunos autores requieren . [ 16 ] Cuando la primera condición se generaliza a uniones arbitrarias se llama irreducible por unión completa (o -irreducible). La noción dual es irreducibilidad por encuentro ( -irreducible). Por ejemplo, en la Fig. 2, los elementos 2, 3, 4 y 5 son irreducibles por unión, mientras que 12, 15, 20 y 30 son irreducibles por encuentro. Dependiendo de la definición, el elemento inferior 1 y el elemento superior 60 pueden o no ser considerados irreducibles por unión e irreducibles por encuentro, respectivamente. En el retículo de números reales con el orden usual, cada elemento es irreducible por unión, pero ninguno es completamente irreducible por unión.x=a∨b{\displaystyle x=a\vee b}x=a or x=b.{\displaystyle x=a{\text{ or }}x=b.}a,b∈L.{\displaystyle a,b\in L.}L{\displaystyle L}0,{\displaystyle 0,}x≠0{\displaystyle x\neq 0}⋁i∈Iai,{\displaystyle \bigvee _{i\in I}a_{i},}x{\displaystyle x}∨{\displaystyle \vee }∧{\displaystyle \wedge } 
  • Unirse primo si implica Nuevamente algunos autores requieren , aunque esto es inusual. [ 17 ] Esto también puede generalizarse para obtener la noción de unirse primo completamente . La noción dual es encontrarse primo . Todo elemento de unión primo es también irreducible de unión, y todo elemento de encuentro primo es también irreducible de encuentro. Lo contrario se cumple si es distributivo.x≤a∨b{\displaystyle x\leq a\vee b}x≤a or x≤b.{\displaystyle x\leq a{\text{ or }}x\leq b.}x≠0{\displaystyle x\neq 0}L{\displaystyle L}

Sea 0 el elemento inferior. Un elemento de es un átomo si y no existe ningún elemento tal que Entonces se llama:L{\displaystyle L}x{\displaystyle x}L{\displaystyle L}0<x{\displaystyle 0<x}y∈L{\displaystyle y\in L}0<y<x.{\displaystyle 0<y<x.}L{\displaystyle L}

  • Atómico si para cada elemento no nulo de existe un átomo de tal que [ 18 ]x{\displaystyle x}L,{\displaystyle L,}a{\displaystyle a}L{\displaystyle L}a≤x;{\displaystyle a\leq x;}
  • Atomístico si cada elemento es un supremo de átomos. [ 19 ]L{\displaystyle L}

Sin embargo, muchas fuentes y comunidades matemáticas utilizan el término "atómico" para referirse a "atomístico" tal como se definió anteriormente.

Las nociones de ideales y la noción dual de filtros se refieren a tipos particulares de subconjuntos de un conjunto parcialmente ordenado y, por lo tanto, son importantes para la teoría de retículos. Encontrará más detalles en las entradas correspondientes.

Véase también

Aplicaciones que utilizan la teoría de retículos

Tenga en cuenta que en muchas aplicaciones los conjuntos son solo retículos parciales: no todos los pares de elementos tienen una intersección o unión.

Notas

  1. ↑ Grätzer 2003 , pág. 52 . 
  2. ↑ Birkhoff 1948 , p. 18. "desdey dualmente". Birkhoff lo atribuye a Dedekind 1897 , p. 8. a=a∨(a∧(a∨a))=a∨a{\displaystyle a=a\vee (a\wedge (a\vee a))=a\vee a} 
  3. ↑ Burris, Stanley N., y Sankappanavar, HP, 1981. Un curso de álgebra universal . Springer-Verlag. ISBN 3-540-90578-2.
  4. ↑ Baker, Kirby (2010). "Complete Lattices" (PDF) . Departamento de Matemáticas de UCLA . Recuperado el 8 de junio de 2022 .
  5. ↑ Kaplansky, Irving (1972). Teoría de conjuntos y espacios métricos (2.ª ed.). Nueva York: AMS Chelsea Publishing . pág. 14. ISBN   9780821826942.
  6. ↑ Birkhoff, Garrett (1967). Teoría de retículos . Sociedad Matemática Americana . pág. 32. 
  7. ↑ Davey & Priestley (2002) harvtxt error: objetivos múltiples (2×): CITEREFDaveyPriestley2002 ( ayuda ) , Ejercicio 4.1, pág.  104 .
  8. 1 2 Davey & Priestley (2002) harvtxt error: objetivos múltiples (2×): CITEREFDaveyPriestley2002 ( ayuda ) , Teorema 4.10, pág.  89 .
  9. ↑ Davey & Priestley (2002) harvtxt error: objetivos múltiples (2×): CITEREFDaveyPriestley2002 ( ayuda ) , Teorema 10.21, págs.  238–239 .
  10. ↑ Davey, BA; Priestley, Hilary (2002). Introducción a las redes y el orden (2.ª ed.). Cambridge: Cambridge University Press. Lema 4.1. ISBN  978-0-511-80908-8.
  11. ↑ Birkhoff, Garrett (1967). Teoría de retículos (3.ª ed.). Providence: American Mathematical Society. Corolario 1 en la sección IV.1 y teoremas 14 y 15 en la sección II.8. ISBN  9780821810255.
  12. ↑ Stanley, Richard P (1997), Combinatoria enumerativa (vol. 1) , Cambridge University Press, pp. 103–104 , ISBN  0-521-66351-2
  13. ↑ Philip Whitman (1941). "Free Lattices I". Annals of Mathematics . 42 (1): 325– 329. doi : 10.2307/1969001 . JSTOR 1969001 . 
  14. ↑ Philip Whitman (1942). "Free Lattices II". Annals of Mathematics . 43 (1): 104– 115. doi : 10.2307/1968883 . JSTOR 1968883 . 
  15. ^ Borde, Chris; Kahl, Wolfram; Schmidt, Gunther (23 de abril de 1997). Métodos relacionales en informática . Viena, Austria: Springer Viena. pag. 127.ISBN​  978-3-211-82971-4.
  16. ↑ Davey & Priestley 2002 , pág. 53. Error de sfn: objetivos múltiples (2×): CITEREFDaveyPriestley2002 ( ayuda )
  17. ↑ Hoffmann, Rudolf-E. (1981). Conjuntos parcialmente ordenados continuos, espectros primos de retículos completos completamente distributivos y compactificaciones de Hausdorff . Continuous Lattices. Vol. 871. pp. 159–208 . doi : 10.1007/BFb0089907 .  
  18. ↑ Grätzer 2003 , pág. 246, Ejercicio 3.
  19. ↑ Grätzer 2003 , pág. 234, después de Def.1.

Referencias

Monografías disponibles gratuitamente en línea:

  • Burris, Stanley N., y Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2.
  • Jipsen, Peter y Henry Rose, Variedades de retículos , Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8.

Textos elementales recomendados para personas con conocimientos matemáticos limitados :

  • Donnellan, Thomas, 1968. Teoría de retículos . Pergamon.
  • Grätzer, George , 1971. Teoría de retículos: primeros conceptos y retículos distributivos . WH Freeman.

El texto introductorio contemporáneo estándar, algo más difícil que el anterior:

Monografías avanzadas:

  • Garrett Birkhoff , 1967. Teoría de retículos , 3.ª ed. Vol. 25 de AMS Colloquium Publications. American Mathematical Society . ISBN 978-0-8218-1025-5. doi : 10.1090/coll/025 .
  • Robert P. Dilworth y Peter Crawley, 1973. Teoría algebraica de retículos . Prentice-Hall. ISBN 978-0-13-022269-5.
  • Grätzer, George (2003). Teoría general de retículos (Segunda  edición). Basilea: Birkhäuser. ISBN 978-3-7643-6996-5.

Sobre redes libres:

  • R. Freese, J. Jezek y JB Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America .
  • Johnstone, PT , 1982. Espacios de piedra . Estudios de Cambridge en matemáticas avanzadas 3. Cambridge University Press.

Sobre la historia de la teoría de retículos:

  • Štĕpánka Bilová (2001). Eduard Fuchs (ed.). Teoría reticular: su nacimiento y vida (PDF) . Prometheus. págs. 250–257 . 
  • Birkhoff, Garrett (1948). Teoría de retículos (2ª  ed.).Libro de texto con numerosas referencias en las notas a pie de página.
  • Schlimm, Dirk (noviembre de 2011). "Sobre el papel creativo de la axiomática. El descubrimiento de retículos por Schröder, Dedekind, Birkhoff y otros". Synthese . 183 (1): 47– 68. CiteSeerX 10.1.1.594.8898 . doi : 10.1007/s11229-009-9667-9 . S2CID 11012081 .  Resumen de la historia de las redes.
  • Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler" (PDF) , Braunschweiger Festschrift , doi : 10.24355/dbbs.084-200908140200-2

Sobre las aplicaciones de la teoría de retículos:

  • Garrett Birkhoff (1967). James C. Abbot (ed.). ¿Qué pueden hacer las celosías por usted? . Van Nostrand.Tabla de contenido
  • "Grupo reticular ordenado" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
  • Weisstein, Eric W. "Lattice" . MathWorld .
  • JB Nation, Apuntes sobre teoría de retículos , apuntes del curso, revisados ​​en 2017.
  • Ralph Freese, "Página principal de la teoría de retículos" .
  • Secuencia OEIS A006966 (Número de redes sin etiquetar con n elementos)
Obtenido de " https://en.wikipedia.org/w/index.php?title=Lattice_(order)&oldid=1353489325#Complements_and_pseudo-complements "
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Teoría del ordenLa teoría del orden es una rama de las matemáticas que investiga la noción intuitiva de orden mediante relaciones binarias . Proporciona un marco f...Imagen de un cubo de RubikÁlgebra abstractaEn matemáticas , más específicamente en álgebra , el álgebra abstracta o álgebra moderna es el estudio de las estructuras algebraicas , que son con...Conjunto parcialmente ordenadoFig. 1 Diagrama de Hasse del conjunto de todos los subconjuntos de un conjunto de tres elementos ordenados por inclusión . Los conjuntos conectados...Ínfimo y supremoÍnfimo y supremoEn matemáticas, el ínfimo (abreviado inf ; pl. : infima ) de un subconjunto de un conjunto parcialmente ordenado es el mayor elemento en que es men...Únete y conoceEste diagrama de Hasse representa un conjunto parcialmente ordenado con cuatro elementos: a , b , el elemento máximo a b igual a la unión de a y b ...