Trellis (juego ordenado)

En matemáticas , una celosía (en inglés  : celosía ) es una de las estructuras algebraicas utilizadas en álgebra general . Es un conjunto parcialmente ordenado en el que cada par de elementos tiene un límite superior y un límite inferior . Una celosía puede verse como la celosía de Galois de una relación binaria .

En realidad, existen dos definiciones equivalentes de la red, una relativa a la relación de orden mencionada anteriormente, la otra algebraica.

Ejemplos preliminares y contraejemplos

Cualquier conjunto provisto de una relación de orden total es una celosía. Por ejemplo, cualquier conjunto de números reales proporcionados con el orden habitual.

Entre los conjuntos provistos de una relación de orden parcial, ejemplos simples de celosías resultan de las relaciones de orden "se incluye en" y "divide".

Definición algebraica

Una celosía es un conjunto E provisto de dos leyes internas generalmente señaladas ⋁ y ⋀ que verifican:

La ley de absorción implica la idempotencia de cualquier elemento a de E para las dos leyes:

.

A partir de tal estructura podemos definir en E una relación de orden , aquí indicada ≤, como sigue:

.

Podemos mostrar que esta relación es de hecho una relación de orden (posiblemente parcial). La propiedad de asociatividad asegura la transitividad . La propiedad de la idempotencia asegura la reflexividad . La conmutatividad asegura la antisimetría . Gracias a las dos propiedades de absorción, también podemos demostrar que

.

Luego podemos verificar que

,

lo que asegura que efectivamente sea un enrejado en el sentido de las órdenes.

Definición por relación de orden

Una celosía es un conjunto E provisto de una relación de orden que verifica:

para todos los elementos de una y b de E , existe un límite superior y un límite inferior para el conjunto { a , b }.

Para proporcionar a E una estructura de celosía algebraica, notamos que el límite superior y el límite inferior definen dos leyes internas:

Las propiedades de la red algebraica para estas dos leyes se derivan bastante directamente de la definición.

Por lo tanto, las celosías se definen algebraicamente o por una relación de orden.

Glosario de celosía

Un conjunto ordenado en el que cada par de elementos tiene un límite superior (o un límite inferior) es una media celosía .

Un morfismo de media rejilla de ( L , ∨ L ) a ( M , ∨ M ) es un mapa f  : L → M tal que para todo a , b ∈ L , f ( a ∨ L b ) = f ( a ) ∨ M f ( b ). Decimos que es una incrustación (de medio entramado) si f también es inyectiva . Las definiciones de un morfismo y una incrustación de una celosía son evidentes.Ejemplo: la celosía de las particiones de un conjunto X - isomorfa a la celosía de las relaciones de equivalencia sobre X - se sumerge en la celosía de subgrupos del grupo simétrico S ( X ) , asociando a cada partición π el subgrupo ∏ A ∈ π S ( A ) .Cualquier morfismo (resp. Cualquier incrustación) de una celosía (o incluso de una media celosía) es un morfismo (resp. Embebido) de conjuntos ordenados pero los recíprocos son falsos, e incluso: cualquier celosía está inmersa en la celosía de las relaciones de equivalencia en un determinado conjunto, que además puede elegirse finito si el enrejado es.

Se dice que una celosía es distributiva  (en) si la ley ⋁ es distributiva con respecto a la ley ⋀, o nuevamente (que en una celosía es equivalente) si la ley distr es distributiva con respecto a la ley.

Se dice que una celosía está acotada si tiene un máximo y un mínimo. Así, el conjunto de enteros naturales dotado de la relación de orden ≤ no está acotado pero el mismo conjunto dotado de la relación de orden "divide" es un retículo acotado cuyo mínimo es 1 y el máximo es 0.

Se dice que una celosía acotada se complementa si cada uno de sus elementos x tiene un complemento y que satisface x ⋀ y = 0 y x ⋁ y = 1, donde 0 designa el elemento mínimo de la celosía y 1 el elemento máximo.

Una red distributiva acotada y complementada también se llama álgebra de Boole .

Se dice que una celosía E está completa si cualquier parte de E tiene un límite superior, o nuevamente (que es equivalente, ver más abajo ) si alguna parte de E tiene un límite inferior.

En una red E que tiene un mínimo denotado por 0, los átomos son los elementos mínimos de E \ {0}. Por ejemplo, en la red del conjunto de partes de un conjunto, los átomos son los singleton. Algunas redes con un mínimo pueden no tener átomos. Es por ejemplo el caso de ℝ + , así como del conjunto de aberturas regulares (abiertas iguales dentro de su adhesión ) de un espacio topológico provisto de la inclusión.

Un ideales celosía E es un no vacío I que es estable en la operación ⋁ y que es tal que si x ∈ E y y ∈ I , entonces x ⋀ y ∈ I .

Dado un subconjunto A de un conjunto X , el conjunto de partes de A es un enrejado perfecta de todas las partes de X .

Enrejado completo

En una celosía, cualquier parte finita de E tiene un límite superior y un límite inferior, pero este no es siempre el caso de las partes infinitas, incluso si está acotada: el conjunto de racionales entre 0 y 2 es una celosía acotada pero es no completo porque el conjunto de números racionales de este conjunto cuyo cuadrado es menor que 2 no tiene límite superior.

Garrett Birkhoff introdujo el siguiente significado del epíteto "completo": se dice que un conjunto ordenado está completo si alguna parte tiene un límite superior (incluido el conjunto vacío, que requiere que E tenga un mínimo). Esto es equivalente a cualquier parte que tenga un límite inferior (incluido el conjunto vacío, que impone que E tenga un máximo).

También decimos que E es un espacio completamente reticulado. En informática teórica, el acrónimo español CPO , aunque su traducción literal es "orden parcial completo" tiene un significado diferente. Para evitar cualquier confusión con otra noción de espacio completo , que en el sentido de espacios métricos o más generalmente de espacios uniformes , Bourbaki había propuesto el término completo , que no se impuso. Por lo tanto, ℝ (que está completo para la distancia habitual) no se completa pero = ℝ ⋃ {–∞, + ∞} sí , de ahí su nombre de línea real completa . es de hecho el completo  (in) (en el sentido de Dedekind - MacNeille  (in) ) de ℝ, es decir, el enrejado completo más pequeño que contiene ℝ.

Otros ejemplos.

Teorema de Knaster-Tarski  : cualquier mapa creciente de una red completa en sí mismo tiene un punto fijo.

Dualidad

Si es una celosía, entonces su celosía dual es .

Teorema de dualidad  : si un teorema T es verdadero para todas las celosías, entonces el teorema dual de T, obtenido al reemplazar todas las apariciones de por (y viceversa) y todas las apariciones de por (y viceversa) es un teorema verdadero para todas las celosías.

Notas y referencias

  1. N. Bourbaki , Elementos de las matemáticas  : teoría de conjuntos [ detalle de ediciones ], p.  ER.28 , visto en Google Books , habla de "  red (o celosía ) completa reticulada u ordenada " .
  2. Efectivamente, e igualmente invirtiendo las dos leyes.
  3. (en) Philip Whitman  (en) , "  Celosías, relaciones de equivalencia y subgrupos  " , Bull. Amargo. Matemáticas. Soc. , vol.  52,1946, p.  507-522 ( leer en línea ).
  4. (in) Pavel Pudlak Jiří Tůma, "  Cada celosía finita se puede incrustar en una partición de celosía finita  " , Algebra Universalis , vol.  10,1980, p.  74-95 ( leer en línea ).
  5. De hecho, si, por ejemplo, ⋁ es distributivo en comparación con ⋀, entonces por lo tanto, ⋀ es distributivo con respecto a ⋁.
  6. Ver, por ejemplo, este ejercicio corregido sobre Wikiversity .
  7. Ver también las páginas de desambiguación Complétude y CompletEste enlace se refiere a una página de desambiguación Este enlace se refiere a una página de desambiguación

Ver también

Artículos relacionados

Bibliografía

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">