Únete y conoce

Concepto en 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 a la unión de a y b . La unión/unión de un elemento máximo/mínimo y otro elemento es el elemento máximo/mínimo y, a la inversa, la unión/unión de un elemento máximo/mínimo con otro elemento es el otro elemento. Por lo tanto, cada par en este poset tiene tanto un encuentro como una unión y el poset puede clasificarse como una red . ${\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 mayor), denotado. En general, la unión y el encuentro de un subconjunto de un conjunto parcialmente ordenado no tiene por qué existir. Unirse y encontrarse 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 una semired de unión . Dualmente, un conjunto parcialmente ordenado en el que todos los pares se encuentran es una semired de encuentro . Un conjunto parcialmente ordenado que es a la vez una semirretícula de unión y una semirretícula de encuentro es una celosía . Una red en la que cada subconjunto, no solo cada par, posee un encuentro y una unión es una red completa . También es posible definir una red parcial , en la que no todos los pares se encuentran o se unen, 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 llama unión dirigida o supremo dirigido . Dualmente, si es un conjunto dirigido hacia abajo, entonces su encuentro (si existe) es un encuentro dirigido o un ínfimum dirigido . ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$

Definiciones

Enfoque de orden parcial

Sea un conjunto con orden parcial y sea Un elemento de se llama ${\displaystyle A}$ ${\displaystyle \,\leq ,\,}$ ${\displaystyle x,y\in A.}$ ${\displaystyle m}$ ${\displaystyle A}$reunirse (olímite inferior máximo oinfimum ) 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 if 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 ningún límite inferior 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 límites inferiores máximos de entonces y por lo tanto ^[2] Si no todos los pares de elementos de tienen un encuentro, entonces el encuentro aún 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 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 osupremum ) deinsi 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 if 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 de álgebra universal

Por definición, una operación binaria en un conjunto se cumple si satisface las tres condiciones a , b y c . El par es entonces una semirretícula de encuentro . Además, entonces podemos definir una relación binaria en A , afirmando que si y sólo si De hecho, esta relación es un orden parcial en De hecho, 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,}$ya que 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 los encuentros como las uniones satisfacen igualmente esta definición: un par de operaciones de encuentro y unión asociadas producen órdenes parciales que son inversas entre sí. Al elegir una de estas órdenes como principal, también se fija qué operación se considera meet (la que da la misma orden) y cuál se considera join (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 desde en el último caso de hecho es un límite inferior de y desde es el límite inferior mayor si y solo si es un conjunto inferior atado. Por 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 una semirretícula de encuentro , y el orden parcial se define como en el enfoque del álgebra universal, y para algunos elementos entonces es el mayor límite inferior de con respecto a desde ${\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, los dos enfoques producen conceptos esencialmente equivalentes, un conjunto equipado tanto con una relación binaria como con una operación binaria, de modo que cada una de estas estructuras determina a la otra y cumple las condiciones para pedidos parciales o cumple, respectivamente.

Reuniones de subconjuntos generales

Si es una semired 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 ínfima con respecto a este, y es razonable considerar dicho mínimo como el encuentro del subconjunto. Para subconjuntos finitos no vacíos, los dos enfoques producen el mismo resultado, por lo que cualquiera de ellos puede tomarse como una definición de encuentro. En el caso de que cada subconjunto de tenga un encuentro, de hecho es una red completa ; para más detalles, consulte integridad (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 mnemónico para recordar que denota la unión/supremum y denota el encuentro/infimum ^{[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 If es cerrado bajo uniones arbitrarias e intersecciones arbitrarias y si pertenece a then ${\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}.}$$

menos ${\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 ).}$

Ver también

• Red vectorial localmente convexa

Notas

1. Grätzer, George (21 de noviembre de 2002). Teoría general de la red: segunda edición. Medios de ciencia y negocios de Springer. pag. 52.ISBN _ 978-3-7643-6996-5.
2. Hachtel, Gary D.; Somenzi, Fabio (1996). Algoritmos de síntesis y verificación lógica . Editores académicos de Kluwer. pag. 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 to y of to puede usarse como mnemónico para recordar que, en el contexto más general, denota el supremum (porque un supremum es un límite desde arriba, al igual que "arriba" y ), mientras que denota el infimum. (porque un mínimo es un límite desde abajo, al igual que "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 una unión que se vea similar a la "unión" debe denotarse por De manera similar, dos conjuntos deberían " encontrarse " en su intersección que se parece a "encontrarse" debe indicarse con ${\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, Licenciatura en Letras; Priestley, HA (2002). Introducción a las celosías y al orden (2ª ed.). Cambridge: Prensa de la Universidad de Cambridge . ISBN 0-521-78451-4. Zbl  1002.06001.
• Vickers, Steven (1989). Topología vía Lógica . Tratados de Cambridge sobre informática teórica. vol. 5.ISBN _ 0-521-36062-5. Zbl  0668.54001.