Únete y conoce

Concepto en la teoría del orden

Este 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 , y el elemento mínimo a b igual al encuentro de a y b . La unión/encuentro de un elemento máximo/mínimo y otro elemento es el elemento máximo/mínimo y, a la inversa, el encuentro/unión de un elemento máximo/mínimo con otro elemento es el otro elemento. Por lo tanto, cada par en este conjunto parcial tiene tanto un encuentro como una unión y el conjunto parcial puede clasificarse como un retículo . ${\displaystyle \vee }$ ${\displaystyle \wedge }$

En matemáticas , específicamente en teoría del orden , la unión de un subconjunto de un conjunto parcialmente ordenado es el supremo (límite superior mínimo) de denotado y, de manera similar, el encuentro de es el ínfimo (límite inferior máximo), denotado En general, la unión y el encuentro de un subconjunto de un conjunto parcialmente ordenado no necesitan existir. La unión y el encuentro son duales entre sí con respecto a la inversión de orden. ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S,}$ ${\textstyle \bigvee S,}$ ${\displaystyle S}$ ${\textstyle \bigwedge S.}$

Un conjunto parcialmente ordenado en el que todos los pares tienen una unión es un semirretículo de unión . Dualmente, un conjunto parcialmente ordenado en el que todos los pares tienen un encuentro es un semirretículo de encuentro . Un conjunto parcialmente ordenado que es a la vez un semirretículo de unión y un semirretículo de encuentro es un retículo . Un retículo en el que cada subconjunto, no solo cada par, posee un encuentro y una unión es un retículo completo . También es posible definir un retículo parcial , en el que no todos los pares tienen un encuentro o una unión pero las operaciones (cuando se definen) satisfacen ciertos axiomas. ^[1]

La unión/encuentro de un subconjunto de un conjunto totalmente ordenado es simplemente el elemento máximo/mínimo de ese subconjunto, si tal elemento existe.

Si un subconjunto de un conjunto parcialmente ordenado es también un conjunto dirigido (hacia arriba) , entonces su unión (si existe) se denomina unión dirigida o supremo dirigido . Dualmente, si es un conjunto dirigido hacia abajo, entonces su encuentro (si existe) es un encuentro dirigido o ínfimo dirigido . ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$

Definiciones

Enfoque de orden parcial

Sea un conjunto con un orden parcial y sea Un elemento de se llama ${\displaystyle A}$ ${\displaystyle \,\leq ,\,}$ ${\displaystyle x,y\in A.}$ ${\displaystyle m}$ ${\displaystyle A}$conocer (olímite inferior máximo oínfimo ) dey se denota porsi se cumplen las dos condiciones siguientes: ${\displaystyle x{\text{ and }}y}$ ${\displaystyle x\wedge y,}$

1. ${\displaystyle m\leq x{\text{ and }}m\leq y}$(es decir, es un límite inferior de ). ${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$
2. Para cualquier si entonces (es decir, es mayor o igual que cualquier otro límite inferior de ). ${\displaystyle w\in A,}$ ${\displaystyle w\leq x{\text{ and }}w\leq y,}$ ${\displaystyle w\leq m}$ ${\displaystyle m}$ ${\displaystyle x{\text{ and }}y}$

No es necesario que exista el encuentro, ya sea porque el par no tiene límite inferior en absoluto o porque ninguno de los límites inferiores es mayor que todos los demás. Sin embargo, si hay un encuentro de entonces es único, ya que si ambos son los mayores límites inferiores de entonces y por lo tanto ^[2] Si no todos los pares de elementos de tienen un encuentro, entonces el encuentro todavía puede verse como una operación binaria parcial en ^[1] ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m{\text{ and }}m^{\prime }}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle m\leq m^{\prime }{\text{ and }}m^{\prime }\leq m,}$ ${\displaystyle m=m^{\prime }.}$ ${\displaystyle A}$ ${\displaystyle A.}$

Si el encuentro existe, entonces se denota Si todos los pares de elementos de tienen un encuentro, entonces el encuentro es una operación binaria en y es fácil ver que esta operación cumple las siguientes tres condiciones: Para cualquier elemento ${\displaystyle x\wedge y.}$ ${\displaystyle A}$ ${\displaystyle A,}$ ${\displaystyle x,y,z\in A,}$

1. ${\displaystyle x\wedge y=y\wedge x}$( conmutatividad ),
2. ${\displaystyle x\wedge (y\wedge z)=(x\wedge y)\wedge z}$( asociatividad ), y
3. ${\displaystyle x\wedge x=x}$( idempotencia ).

Las uniones se definen dualmente con la unión de si existe, denotada por Un elemento de es el ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\vee y.}$ ${\displaystyle j}$ ${\displaystyle A}$unirse (olímite superior mínimo osupremo ) deensi se cumplen las dos condiciones siguientes: ${\displaystyle x{\text{ and }}y}$ ${\displaystyle A}$

1. ${\displaystyle x\leq j{\text{ and }}y\leq j}$(es decir, es un límite superior de ). ${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$
2. Para cualquier si entonces (es decir, es menor o igual que cualquier otro límite superior de ). ${\displaystyle w\in A,}$ ${\displaystyle x\leq w{\text{ and }}y\leq w,}$ ${\displaystyle j\leq w}$ ${\displaystyle j}$ ${\displaystyle x{\text{ and }}y}$

Enfoque del álgebra universal

Por definición, una operación binaria sobre un conjunto es un encuentro si satisface las tres condiciones a , b y c . El par es entonces un semirretículo de encuentro . Además, podemos definir una relación binaria sobre A , al afirmar que si y solo si De hecho, esta relación es un orden parcial sobre En efecto, para cualquier elemento ${\displaystyle \,\wedge \,}$ ${\displaystyle A}$ ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle x\leq y}$ ${\displaystyle x\wedge y=x.}$ ${\displaystyle A.}$ ${\displaystyle x,y,z\in A,}$

• ${\displaystyle x\leq x,}$desde por c ; ${\displaystyle x\wedge x=x}$
• si entonces por un ; y ${\displaystyle x\leq y{\text{ and }}y\leq x}$ ${\displaystyle x=x\wedge y=y\wedge x=y}$
• si entonces desde entonces por b . ${\displaystyle x\leq y{\text{ and }}y\leq z}$ ${\displaystyle x\leq z}$ ${\displaystyle x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x}$

Tanto las operaciones de encuentro como de unión satisfacen igualmente esta definición: un par de operaciones de encuentro y de unión asociadas dan lugar a órdenes parciales que son inversas entre sí. Al elegir una de estas órdenes como principal, también se fija qué operación se considera un encuentro (la que da la misma orden) y cuál se considera una unión (la otra).

Equivalencia de enfoques

Si es un conjunto parcialmente ordenado , tal que cada par de elementos en tiene un encuentro, entonces de hecho si y solo si ya que en el último caso de hecho es un límite inferior de y ya que es el límite inferior máximo si y solo si es un límite inferior. Por lo tanto, el orden parcial definido por el encuentro en el enfoque del álgebra universal coincide con el orden parcial original. ${\displaystyle (A,\leq )}$ ${\displaystyle A}$ ${\displaystyle x\wedge y=x}$ ${\displaystyle x\leq y,}$ ${\displaystyle x}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x}$

Por el contrario, si es un semirretículo de encuentro , y el orden parcial se define como en el enfoque del álgebra universal, y para algunos elementos entonces es el límite inferior más grande de con respecto a ya que y por lo tanto De manera similar, y si es otro límite inferior de entonces de donde Por lo tanto, hay un encuentro definido por el orden parcial definido por el encuentro original, y los dos encuentros coinciden. ${\displaystyle (A,\wedge )}$ ${\displaystyle \,\leq \,}$ ${\displaystyle z=x\wedge y}$ ${\displaystyle x,y\in A,}$ ${\displaystyle z}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\leq ,\,}$ $${\displaystyle z\wedge x=x\wedge z=x\wedge (x\wedge y)=(x\wedge x)\wedge y=x\wedge y=z}$$ ${\displaystyle z\leq x.}$ ${\displaystyle z\leq y,}$ ${\displaystyle w}$ ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle w\wedge x=w\wedge y=w,}$ $${\displaystyle w\wedge z=w\wedge (x\wedge y)=(w\wedge x)\wedge y=w\wedge y=w.}$$

En otras palabras, ambos enfoques producen conceptos esencialmente equivalentes, un conjunto equipado con una relación binaria y una operación binaria, de modo que cada una de estas estructuras determina a la otra y cumple las condiciones para órdenes parciales o encuentros, respectivamente.

Encuentros de subconjuntos generales

Si es un semirretículo de encuentro, entonces el encuentro puede extenderse a un encuentro bien definido de cualquier conjunto finito no vacío , mediante la técnica descrita en operaciones binarias iteradas . Alternativamente, si el encuentro define o está definido por un orden parcial, algunos subconjuntos de de hecho tienen ínfimo con respecto a este, y es razonable considerar dicho ínfimo como el encuentro del subconjunto. Para subconjuntos finitos no vacíos, los dos enfoques producen el mismo resultado, y por lo tanto cualquiera puede tomarse como una definición de encuentro. En el caso en que cada subconjunto de tiene un encuentro, de hecho es un retículo completo ; para más detalles, véase completitud (teoría del orden) . ${\displaystyle (A,\wedge )}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle (A,\leq )}$

Ejemplos

Si algún conjunto de potencias está parcialmente ordenado de la forma habitual (por ), entonces las uniones son uniones y los encuentros son intersecciones; en símbolos, (donde la similitud de estos símbolos puede usarse como un mnemónico para recordar que denota la unión/supremo y denota el encuentro/ínfimo ^{[nota 1]} ). ${\displaystyle \wp (X)}$ ${\displaystyle \,\subseteq }$ ${\displaystyle \,\vee \,=\,\cup \,{\text{ and }}\,\wedge \,=\,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge \,}$

De manera más general, supongamos que es una familia de subconjuntos de algún conjunto que está parcialmente ordenado por Si está cerrado bajo uniones arbitrarias e intersecciones arbitrarias y si pertenece a entonces Pero si no está cerrado bajo uniones entonces existe en si y solo si existe un único -pequeño tal que Por ejemplo, si entonces mientras que si entonces no existe porque los conjuntos son los únicos límites superiores de en que posiblemente podría ser el límite superior mínimo pero y Si entonces no existe porque no hay un límite superior de en ${\displaystyle {\mathcal {F}}\neq \varnothing }$ ${\displaystyle X}$ ${\displaystyle \,\subseteq .\,}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A,B,\left(F_{i}\right)_{i\in I}}$ ${\displaystyle {\mathcal {F}}}$ $${\displaystyle A\vee B=A\cup B,\quad A\wedge B=A\cap B,\quad \bigvee _{i\in I}F_{i}=\bigcup _{i\in I}F_{i},\quad {\text{ and }}\quad \bigwedge _{i\in I}F_{i}=\bigcap _{i\in I}F_{i}.}$$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A\vee B}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \,\subseteq }$ ${\displaystyle J\in {\mathcal {F}}}$ ${\displaystyle A\cup B\subseteq J.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}=\{1,2,3\}}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{1,2,3\},\{0,1,2\},\mathbb {R} \}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}{\text{ and }}\{1,2,3\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq )}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{0,1,2\}\not \subseteq \{1,2,3\}}$ ${\displaystyle \{1,2,3\}\not \subseteq \{0,1,2\}.}$ ${\displaystyle {\mathcal {F}}=\{\{1\},\{2\},\{0,2,3\},\{0,1,3\}\}}$ ${\displaystyle \{1\}\vee \{2\}}$ ${\displaystyle \{1\}{\text{ and }}\{2\}}$ ${\displaystyle ({\mathcal {F}},\subseteq ).}$

Véase también

• Red vectorial localmente convexa

Notas

1. Grätzer, George (21 de noviembre de 2002). Teoría general de redes: segunda edición. Springer Science & Business Media. pág. 52. ISBN 978-3-7643-6996-5.
2. Hachtel, Gary D.; Somenzi, Fabio (1996). Algoritmos de síntesis y verificación lógica . Kluwer Academic Publishers. pág. 88. ISBN. 0792397460.

1. Se puede determinar inmediatamente que los supremos y los ínfimos en este ejemplo canónico y simple son respectivamente. La similitud del símbolo a y de a puede usarse así como una regla mnemotécnica para recordar que en el contexto más general, denota el supremo (porque un supremo es un límite desde arriba, al igual que es "arriba" y ) mientras que denota el ínfimo (porque un ínfimo es un límite desde abajo, al igual que es "abajo" y ). Esto también se puede usar para recordar si los encuentros/uniones se denotan por o por La intuición sugiere que " unir " dos conjuntos debería producir su unión que se parece a por lo que "unir" debe denotarse por De manera similar, dos conjuntos deberían " encontrarse " en su intersección que se parece a por lo que "encontrarse" debe denotarse por ${\displaystyle (\wp (X),\subseteq )}$ ${\displaystyle \,\cup \,{\text{ and }}\,\cap \,,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\cup \,}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle \,\cap \,}$ ${\displaystyle \,\vee \,}$ ${\displaystyle A\cup B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\wedge \,}$ ${\displaystyle A\cap B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \,\vee \,}$ ${\displaystyle \,\wedge .\,}$ ${\displaystyle A\cup B,}$ ${\displaystyle A\vee B,}$ ${\displaystyle \,\vee .\,}$ ${\displaystyle A\cap B,}$ ${\displaystyle A\wedge B,}$ ${\displaystyle \,\wedge .\,}$

Referencias

• Davey, BA; Priestley, HA (2002). Introducción a los retículos y el orden (2.ª ed.). Cambridge: Cambridge University Press . ISBN 0-521-78451-4.Zbl 1002.06001  .
• Vickers, Steven (1989). Topología a través de la lógica . Cambridge Tracts in Theoretic Computer Science. Vol. 5. ISBN. 0-521-36062-5.Zbl 0668.54001  .