Conjunto parcialmente ordenado

En matemáticas , un conjunto parcialmente ordenado (a veces llamado poset del inglés parcialmente ordenado conjunto ) formaliza y generaliza la noción intuitiva de orden o disposición entre los elementos de un conjunto . Un conjunto parcialmente ordenado es un conjunto provisto de una relación de orden que indica que para ciertos pares de elementos, uno es más pequeño que el otro. Todos los elementos no son necesariamente comparables, a diferencia del caso de un conjunto provisto de un pedido total .

Si el conjunto es finito, tenemos una representación gráfica del conjunto parcialmente ordenado, el diagrama de Hasse , que puede facilitar el trabajo en él. Si el conjunto es infinito, podemos dibujar parte de su diagrama de Hasse.

Definición y ejemplos

Definición

Un orden (u orden parcial) es una relación binaria en un conjunto P que es reflexiva , antisimétrica y transitiva . Se anota ≤.

Los tres axiomas anteriores se reescriben:

a ≤ a (reflexividad).
Si a ≤ b y b ≤ a , entonces a = b (antisimetría).
Si un ≤ b y b ≤ c , a continuación, un ≤ c (transitividad).

Por tanto, no es necesariamente un pedido total .

Ejemplos de

El conjunto de enteros naturales, provisto de divisibilidad, es un conjunto infinito parcialmente ordenado.
Un conjunto de personas con la relación de ascendencia genealógica es un conjunto parcialmente ordenado. Por ejemplo, dos hermanas son inferiores a su madre pero no son comparables entre sí.
El conjunto de partes de un conjunto dado, provisto de la inclusión, forma un conjunto parcialmente ordenado. Si el conjunto dado es finito, su conjunto de partes es finito (más precisamente , tenemos ). La siguiente figura representa el diagrama de Hasse de un conjunto con 3 elementos. $\ # A = n$ $\ #P (A) = 2 ^ {n}$

Para tomar un caso concreto (de hecho, isomórfico ) del ejemplo anterior, un conjunto de personas dotadas de la relación pueden donar sangre para formar un conjunto parcialmente ordenado según los sistemas ABO y Rhesus . Los elementos x , y y z en el ejemplo anterior más general están instanciados por los antígenos A, B y D (Rh +) del individuo. Por ejemplo, un individuo del grupo O + puede dar a un destinatario del grupo B +, pero ninguno puede dar ni recibir de un individuo del grupo A-.
El conjunto de números complejos proporcionan en la siguiente relación de orden está parcialmente ordenado: . $a + ib <a '+ ib' \ Leftrightarrow \ left \ {{\ begin {matrix} a <a '\\ b <b' \ end {matrix}} \ right.$

Por ejemplo, no podemos comparar 1 e i . Este orden no es compatible con la estructura de la carrocería de . $\ mathbb {C}$

El conjunto de funciones de in , provisto de la relación de orden si , es un conjunto infinito parcialmente ordenado. Intuitivamente, una función es más pequeña que otra si su curva siempre está por debajo de la otra curva. Podemos generalizar este ejemplo a las funciones de un conjunto X en un conjunto P parcialmente ordenado. $\ mathbb {R}$ $\ mathbb {R}$ $f <g$ $\ forall x, f (x) <g (x)$
El conjunto de particiones de un conjunto dado está parcialmente ordenado, con el orden dado por el refinamiento de las particiones: por definición, una partición es más fina que otra si divide las partes de la otra en partes más pequeñas.
Podemos proporcionar el conjunto de polinomios con n variables con una relación de orden parcial. Comenzamos comparando los monomios con n variables a través del orden lexicográfico inducido por (este orden lexicográfico es total). Comparamos dos polinomios y decimos que es estrictamente más pequeño que si cualquier monomio distinto de cero de es estrictamente más pequeño que cualquier monomio distinto de cero de . Esta relación de orden en los polinomios es parcial. $R [X_ {1}, ..., X_ {n}]$ $1 <X_ {1} <X_ {2} <... <X_ {n}$ $PAG$ $Q$ $PAG$ $Q$ $PAG$ $Q$

Especificidades de conjuntos parcialmente ordenados

Elemento más grande , elemento máximo y límite superior

Sea P un conjunto parcialmente ordenado:

Un elemento a de P es un elemento mayor si para cualquier elemento b de P, b ≤ a. Un conjunto parcialmente ordenado solo puede tener un elemento más grande.

Un elemento a de P es un elemento máximo si no hay un elemento b de P tal que b> a. Si P tiene un elemento más grande, es el único elemento máximo de P.

Para un subconjunto A de P, el elemento x de P es un límite superior de A si a ≤ x para cualquier elemento a de A. x no pertenece necesariamente a A. El elemento más grande de P, s 'que existe, es un límite superior de P.

Ejemplo : considere el conjunto de números enteros positivos, ordenados por división. 1 es el elemento más pequeño. Por otro lado, este conjunto no tiene un elemento más grande. Si ahora excluyéramos el elemento 1, el conjunto parcialmente ordenado ya no tendría un elemento más pequeño sino una infinidad de elementos mínimos: los números primos .

Si E es un conjunto parcialmente ordenado, no necesariamente existe un elemento mayor. Si E es un conjunto finito parcialmente ordenado, contendrá al menos un elemento máximo. Si E es un conjunto inductivo infinito, podemos usar el lema de Zorn para tener la existencia de un elemento máximo.

Ciertas condiciones sobre los elementos más grandes y los elementos más pequeños de un conjunto parcialmente ordenado conducen a la definición de una celosía .

Por el mismo razonamiento obtenemos el elemento más pequeño, los elementos mínimos y el límite inferior.

Comparabilidad

Si a ≤ bo a b, entonces ayb son comparables. En el diagrama de Hasse anterior, {x} y {x, y, z} son comparables, mientras que {x} e {y} no lo son. Un orden parcial en el que cualquier par de elementos es comparable se llama orden total y el conjunto se llama cadena . Un conjunto en el que no se puede encontrar un par comparable se llama antichain (por ejemplo, el conjunto {{x}, {y }, {z}} en la figura anterior) $\ geq$

Recuperación

Decimos que un elemento a está cubierto por un elemento b, que se escribe a <: b, si a es estrictamente menor que by no hay ningún elemento c interpuesto entre los dos. Por ejemplo, {x} está cubierto por {x, z} en la figura anterior pero no por {x, y, z}.

Vínculos con complejos simpliciales.

Una clase importante de complejos simpliciales proviene de conjuntos finitos parcialmente ordenados. Definimos el complejo de orden D (P) de un conjunto finito parcialmente ordenado P como el conjunto de cadenas de P. El complejo de orden es trivialmente un complejo simplicial.

El estudio del conjunto parcialmente ordenado proporciona información sobre su complejo de orden, por lo que es interesante estudiar un complejo simplicial como el complejo de orden de un conjunto parcialmente ordenado.

Operación en juegos parcialmente ordenados

Conjunto de producto cartesiano parcialmente ordenado

Para eliminar la multiplicidad de posibles relaciones de orden durante un conjunto parcialmente ordenado, podemos definir tres reglas diferentes:

El orden lexicográfico : ( a , b ) ≤ ( c , d ) si a < c o ( a = c y b ≤ d );
El orden multiplicativo : ( a , b ) ≤ ( c , d ) si un ≤ c y b ≤ d ;
El cierre reflexivo del producto directo : ( a , b ) ≤ ( c , d ) si ( a < c y b < d ) o ( a = c y b = d ).

Todas estas reglas también se aplican a productos de más de dos conjuntos parcialmente ordenados.

Finitud local

Se dice que un conjunto E parcialmente ordenado es localmente finito si, para todos , el intervalo es finito. Esta suposición permite generalizar la fórmula de inversión de Möbius . $x, y \ en E$ $[x, y]$

Referencias

(en) Richard P. Stanley , Combinatoria enumerativa , vol. 1 [ detalle de ediciones ] ( presentación en línea )

Ver también