En el campo matemático de la teoría del orden , un orden de inclusión es el orden parcial que surge como la relación de subconjunto- inclusión en alguna colección de objetos. De una manera simple, cada poset P = ( X , ≤) es ( isomorfo a) un orden de inclusión (al igual que cada grupo es isomorfo a un grupo de permutación - vea el teorema de Cayley ). Para ver esto, asociar a cada elemento x de X el conjunto
entonces la transitividad de ≤ asegura que para todo a y b en X , tenemos
Puede haber conjuntos de cardinalidad menor quede tal manera que P es isomórfica a la orden de inclusión en S . El tamaño del más pequeño posible S se llama el 2-dimensión de P .
Varias clases importantes de poset surgen como órdenes de inclusión para algunas colecciones naturales, como el retículo booleano Q n , que es la colección de los 2 n subconjuntos de un conjunto de n elementos, los órdenes de contención de intervalo , que son precisamente los órdenes de orden. dimensión como máximo dos, y dimensión- n órdenes, que son las órdenes de contención en colecciones de n- cajas ancladas en el origen . Otros órdenes de contención que son interesantes por derecho propio incluyen los órdenes de los círculos , que surgen de los discos en el plano, y los órdenes de los ángulos .
Ver también
- Teorema de representación de Birkhoff
- Árbol (una estructura de datos definida por el orden de inclusión)
- Gráfico de intersección
- Orden de intervalo
Referencias
- Fishburn, PC; Trotter, WT (1998). "Órdenes de contención geométrica: una encuesta". Orden . 15 (2): 167–182. doi : 10.1023 / A: 1006110326269 . S2CID 14411154 .
- Santoro, N., Sidney, JB, Sidney, SJ y Urrutia, J. (1989). "Contención geométrica y órdenes parciales". Revista SIAM de Matemática Discreta . 2 (2): 245-254. CiteSeerX 10.1.1.65.1927 . doi : 10.1137 / 0402021 .CS1 maint: varios nombres: lista de autores ( enlace )