Relaciones binarias | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Todas las definiciones requieren tácitamente transitividad y reflexividad . |
En matemáticas , específicamente en la teoría del orden , la unión de un subconjunto S de un conjunto parcialmente ordenado P es el supremo (mínimo límite superior) de S , denotado ⋁ S , y de manera similar, el encuentro de S es el mínimo (mayor límite inferior), denotado ⋀ S . En general, no es necesario que exista la combinación y el encuentro de un subconjunto de un conjunto parcialmente ordenado. Unirse y encontrarse son duales entre sí con respecto a la inversión de orden.
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 semirretículo 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. [1]
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 S de un conjunto P parcialmente ordenado también es un conjunto dirigido (hacia arriba) , entonces su combinación (si existe) se denomina combinación dirigida o supremum dirigido . Doblemente, si S es un conjunto dirigido hacia abajo, entonces su encuentro (si existe) es un encuentro dirigido o un infimum dirigido .
Enfoque de orden parcial
Deje que A sea un conjunto con un orden parcial ≤, y dejar que x y y sea dos elementos en A . Un elemento z de A es el encuentro (o extremo inferior o infimum) de x y y , si se satisfacen las dos condiciones siguientes:
- z ≤ x y z ≤ y (es decir, z es un límite inferior de x y y ).
- Para cualquier w en A , de tal manera que w ≤ x y w ≤ y , tenemos w ≤ z (es decir, z es mayor que o igual a cualquier otro límite inferior de x y y ).
Si hay una reunión de x y y , a continuación, es único, ya que si ambos z y z 'son más grandes límites inferiores de x y y , a continuación, z ≤ z ' y z '≤ z , y por lo tanto z = z ' . Si el encuentro existe, se denota x ∧ y . Algunos pares de elementos en A 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 A tienen un encuentro, entonces el encuentro es una operación binaria en A , y es fácil ver que esta operación cumple las siguientes tres condiciones: Para cualquier elemento x , y , z en A ,
- una. x ∧ y = y ∧ x ( conmutatividad ),
- B. x ∧ ( y ∧ z ) = ( x ∧ y ) ∧ z ( asociatividad ), y
- C. x ∧ x = x ( idempotencia ).
Se une se definen dualmente, y la unión de x y y en A (si existe) se denota por x ∨ y . Si no todos los pares de elementos de A tienen un encuentro (respectivamente, unirse a), entonces el Meet (respectivamente, unirse a) puede todavía ser visto como un parcial operación binaria en A .
Enfoque del álgebra universal
Por definición, una operación binaria ∧ en un conjunto A es un meet si satisface las tres condiciones una , b , y c . El par ( A , ∧) es entonces un semirreticulado de encuentro . Además, podemos definir una relación binaria ≤ en A , al afirmar que x ≤ y si y solo si x ∧ y = x . De hecho, esta relación es un orden parcial en A . De hecho, para cualquier elemento x , y y z en A ,
- x ≤ x , ya que x ∧ x = x por c ;
- si x ≤ y y y ≤ x , entonces x = x ∧ y = y ∧ x = y por a ; y
- si x ≤ y y y ≤ z , entonces x ≤ z , ya que entonces x ∧ z = ( x ∧ y ) ∧ z = x ∧ ( y ∧ z ) = x ∧ y = x por b .
Tenga en cuenta que las reuniones y las combinaciones satisfacen por igual esta definición: un par de operaciones de reunión y combinació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 ( A , ≤) es un conjunto parcialmente ordenado , tal que cada par de elementos en A tiene un encuentro, entonces de hecho x ∧ y = x si y solo si x ≤ y , ya que en el último caso x es un límite inferior de x y y , y puesto claramente x es el mayor límite inferior si y sólo 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.
A la inversa, si ( A , ∧) es un meet-semilattice , y el orden parcial ≤ se define como en el enfoque de álgebra universal, y z = x ∧ y para algunos elementos x y y en A , entonces z es el mayor límite inferior de x y y con respecto a ≤, ya
- z ∧ x = x ∧ z = x ∧ ( x ∧ y ) = ( x ∧ x ) ∧ y = x ∧ y = z
y por tanto z ≤ x . Del mismo modo, z ≤ y , y si w es otro límite inferior de x y y , a continuación, w ∧ x = w ∧ Y = w , de donde
- w ∧ z = w ∧ ( x ∧ y ) = ( w ∧ x ) ∧ y = w ∧ 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 ( A , ∧) es una semirrejilla 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 A 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 A tenga un encuentro, de hecho ( A , ≤) es una red completa ; para obtener más detalles, consulte integridad (teoría del orden) .
Notas
- ↑ Grätzer , 1996 , p. 52 .
Referencias
- Davey, BA; Priestley, HA (2002). Introducción a las celosías y el orden (2ª ed.). Cambridge: Cambridge University Press . ISBN 0-521-78451-4. Zbl 1002.06001 .
- Vickers, Steven (1989). Topología vía lógica . Cambridge Tracts en Informática Teórica. 5 . ISBN 0-521-36062-5. Zbl 0668.54001 . CS1 maint: parámetro desalentado ( enlace )