Únete y conoce - Join and meet

Relaciones binarias transitivas
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico También conocido como: Total, Semiconnex Antirreflejos Relación de equivalencia Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Reserva total ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Orden total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Ordenamiento previo ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien casi ordenado ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Bien ordenado ✗ Y Y Y ✗ ✗ Y ✗ ✗ Enrejado ✗ Y ✗ ✗ Y Y Y ✗ ✗ Unión-semirrejilla ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Encuentro-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricto ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Orden estrictamente débil ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricto ✗ ✗ Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones: ${\ Displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b \, {\ text {y}} \, S \ neq \ varnothing:}}$ ${\ Displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$ ${\ Displaystyle \ scriptstyle {aRb \, {\ text {y}} \, bRa \ Rightarrow a = b}}$ ${\ Displaystyle \ scriptstyle {a \ neq b \ Rightarrow aRb \, {\ text {o}} \, bRa}}$ ${\ Displaystyle \ scriptstyle {\ min S \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {a \ vee b \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {a \ wedge b \, {\ text {existe}}}}$ ${\ Displaystyle \ scriptstyle {aRa}}$ ${\ Displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$ ${\ Displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$
Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : A " " indica que la propiedad de la columna es requerida por la definición del término de la fila (en el extremo izquierdo). Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Aquí se enumeran las propiedades adicionales que puede satisfacer una relación homogénea. ${\ Displaystyle R}$${\ Displaystyle \ scriptstyle {{\ text {Para todos}} \, a, b, c, {\ text {if}} aRb {\ text {y}} bRc {\ text {luego}} aRc}.}$ Y

En matemáticas , específicamente en la teoría del orden , la unión de un subconjunto de un conjunto parcialmente ordenado es el supremum (mínimo límite superior) de denotado y, de manera similar, el encuentro de es el infimum (mayor límite inferior), denotado En general, la unión y encuentro de un subconjunto de un conjunto parcialmente ordenado no necesita existir. Unirse y encontrarse son duales entre sí con respecto a la inversión de orden. ${\ Displaystyle S}$ ${\ Displaystyle P}$${\ Displaystyle S,}$${\ Displaystyle \ vee S,}$${\ Displaystyle S}$${\ Displaystyle \ wedge S.}$

Un conjunto parcialmente ordenado en el que todos los pares tienen una unión es una unión-semirrejilla . Dualmente, un conjunto parcialmente ordenado en el que todos los pares tienen un encuentro es un semirreticulado de encuentro . Un conjunto parcialmente ordenado que es a la vez un semirremolque de unión y un semirremolque de encuentro es un entramado . Un entramado en el que cada subconjunto, no solo cada par, posee un encuentro y una unión es un entramado completo . También es posible definir una celosía parcial , en la que no todos los pares tienen un encuentro o unión, pero las operaciones (cuando se definen) satisfacen ciertos axiomas.

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

Si un subconjunto de un conjunto parcialmente ordenado también es un conjunto dirigido (hacia arriba) , entonces su combinación (si existe) se denomina combinación dirigida o superior dirigido . Doblemente, si es un conjunto dirigido hacia abajo, entonces su encuentro (si existe) es un encuentro dirigido o un infimum dirigido . ${\ Displaystyle S}$${\ Displaystyle P}$${\ Displaystyle S}$

Enfoque de orden parcial

Sea un conjunto con un orden parcial y sea Un elemento de es el${\ Displaystyle A}$ ${\ Displaystyle \, \ leq, \,}$${\ Displaystyle x, y \ en A.}$${\ Displaystyle z}$${\ Displaystyle A}$ reunirse (omayor límite inferior oinfimum )si se cumplen las dos condiciones siguientes: ${\ displaystyle x {\ text {y}} y}$

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

Si hay un encuentro de, entonces es único, ya que si ambos son los límites inferiores mayores de entonces y, por lo tanto, si el encuentro existe, se denota Algunos pares de elementos en pueden carecer de un encuentro, ya sea porque no tienen ningún límite inferior. , o porque ninguno de sus límites inferiores es mayor que todos los demás. Si todos los pares de elementos de tienen una reunión, entonces la conocen es una operación binaria en y es fácil ver que esta operación cumple las tres condiciones siguientes: Para cualquier elemento${\ displaystyle x {\ text {y}} y,}$${\ Displaystyle z {\ text {y}} z ^ {\ prime}}$${\ displaystyle x {\ text {y}} y,}$${\ Displaystyle z \ leq z ^ {\ prime} {\ text {y}} z ^ {\ prime} \ leq z,}$${\ Displaystyle z = z ^ {\ prime}.}$${\ Displaystyle x \ wedge y.}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle A,}$${\ Displaystyle x, y, z \ en 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, denotado por Un elemento de es el ${\ displaystyle x {\ text {y}} y,}$${\ Displaystyle x \ vee y.}$${\ Displaystyle j}$${\ Displaystyle A}$unirse (omínimo límite superior osupremum ) deensi se cumplen las dos condiciones siguientes: ${\ displaystyle x {\ text {y}} y}$${\ Displaystyle A}$

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

Si no todos los pares de elementos de tienen un encuentro (respectivamente, unión), entonces el encuentro (respectivamente, unión) todavía se puede ver como una operación binaria parcial en${\ Displaystyle A}$${\ Displaystyle A.}$

Enfoque del álgebra universal

Por definición, una operación binaria en un conjunto es un reúnen siempre que cumplan las tres condiciones de un , b , y c . El par es entonces una semirrejilla de encuentro . Además, entonces podemos definir una relación binaria en A , afirmando que si y solo 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 \ en A,}$

• ${\ Displaystyle x \ leq x,}$ya que por c ;${\ Displaystyle x \ wedge x = x}$
• si entonces por a ; y${\ Displaystyle x \ leq y {\ text {y}} y \ leq x}$${\ Displaystyle x = x \ wedge y = y \ wedge x = y}$
• si entonces desde entonces por b .${\ Displaystyle x \ leq y {\ text {y}} y \ leq z}$${\ Displaystyle x \ leq z}$${\ Displaystyle x \ cuña z = (x \ cuña y) = y \ cuña z = x \ cuña (y \ cuña z) = x \ cuña y = x}$

Tanto las reuniones como las combinaciones satisfacen por igual esta definición: un par de operaciones de reunión y unión asociadas producen órdenes parciales que son inversas entre sí. Al elegir una de estas órdenes como las principales, también se fija qué operación se considera una reunión (la que da la misma orden) y cuál se considera una combinación (la otra).

Equivalencia de enfoques

Si es un conjunto parcialmente ordenado , de modo que cada par de elementos en tiene un encuentro, entonces de hecho si y solo si ya que en el último caso es de hecho un límite inferior de y ya que es el límite inferior mayor si y solo si es un límite inferior ligado. 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 {y}} y,}$${\ Displaystyle x}$

Por el contrario, si es una semirrejilla 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 desde ${\ Displaystyle (A, \ wedge)}$${\ Displaystyle \, \ leq \,}$${\ Displaystyle z = x \ wedge y}$${\ Displaystyle x, y \ en A,}$${\ Displaystyle z}$${\ displaystyle x {\ text {y}} y}$${\ Displaystyle \, \ leq, \,}$

y por lo tanto de manera similar, y si es otro límite inferior de entonces de donde ${\ Displaystyle z \ leq x.}$${\ Displaystyle z \ leq y,}$${\ Displaystyle w}$${\ displaystyle x {\ text {y}} y,}$${\ Displaystyle w \ wedge x = w \ wedge y = w,}$ Por lo tanto, hay un encuentro definido por el orden parcial definido por el encuentro original, y los dos encuentros coinciden.

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

Reuniones 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 mínimos con respecto a esto, y es razonable considerar un mínimo como el encuentro del subconjunto. Para subconjuntos finitos no vacíos, los dos enfoques producen el mismo resultado, por lo que cualquiera puede tomarse como una definición de encuentro. En el caso de que cada subconjunto de tenga un encuentro, de hecho es un entramado completo ; para obtener más detalles, consulte integridad (teoría del orden) . ${\ Displaystyle (A, \ wedge)}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle (A, \ leq)}$

Notas

Referencias