Teorema de Dilworth
En matemáticas , en las áreas de teoría de órdenes y combinatoria , el teorema de Dilworth caracteriza el ancho de cualquier conjunto finito parcialmente ordenado en términos de una partición del orden en un número mínimo de cadenas . Lleva el nombre del matemático Robert P. Dilworth ( 1950 ).
Un antichain en un conjunto parcialmente ordenado es un conjunto de elementos de los cuales no hay dos comparables entre sí, y una cadena es un conjunto de elementos cada dos de los cuales son comparables. Una descomposición en cadena es una partición de los elementos del orden en cadenas separadas . El teorema de Dilworth establece que, en cualquier conjunto finito parcialmente ordenado, el antichain más grande tiene el mismo tamaño que la descomposición de la cadena más pequeña. Aquí, el tamaño del antichain es su número de elementos y el tamaño de la descomposición de la cadena es su número de cadenas. El ancho del orden parcial se define como el tamaño común del antichain y la descomposición de la cadena.
Una versión del teorema para conjuntos infinitos parcialmente ordenados establece que, cuando existe una descomposición en un número finito de cadenas, o cuando existe un límite superior finito en el tamaño de un antichain, los tamaños del antichain más grande y de la descomposición de la cadena más pequeña son de nuevo iguales.
La siguiente prueba por inducción sobre el tamaño del conjunto parcialmente ordenado se basa en la de Galvin ( 1994 ).
Sea un conjunto finito parcialmente ordenado. El teorema es trivialmente válido si está vacío. Entonces, suponga que tiene al menos un elemento, y sea un elemento máximo de .
