[Nub]

Hola, he buscado por internet el teorema de dilworth y encuentro variantes entre cada uno que veo y me han dicho que el siguiente ejercicio sale de usar este teorema, ¿alguien podría enunciarlo de tal forma que se puede aplicar al siguiente ejercicio?
Ejercicio:
Demostrar que en un conjunto de 61 personas hay una sucesión de 13 elementos que cada uno de ellos esta relacionado con el siguiente y también que existe un grupo de 6 elementos que ningunos están relacionados con otros

De la letra del ejercicio se puede deducir que la sucesión de 13 elementos es una cadena y la sucesión de 6 elementos es un anti cadena. El teorema de dilworht que tengo dice: Sea (A,≤) parcialmente ordenado, la partición de A de menor tamaño P(A) es igual al tamaño máximo de una anti cadena T(A). P(A)=T(A) aunque no la entiendo mucho, por ejemplo a que se refiere en si con la partición de A de menor tamaño si al final toda partición al unirse dará el conjunto A.
Gracias!

[geómetracat]

El teorema de dilworht que tengo dice: Sea (A,≤) parcialmente ordenado, la partición de A de menor tamaño P(A) es igual al tamaño máximo de una anti cadena T(A). P(A)=T(A) aunque no la entiendo mucho, por ejemplo a que se refiere en si con la partición de A de menor tamaño si al final toda partición al unirse dará el conjunto A.

Es correcto, pero teniendo en cuenta que las particiones sobre las que habla el teorema son aquellas en que cada conjunto de la partición es una cadena (un conjunto totalmente ordenado). Es decir, el teorema te dice que si tienes un conjunto finito parcialmente ordenado \( (A, \leq) \), digamos con \( N \) elementos, tienes una anticadena maximal con \( a \) elementos, y partes el conjunto en \( k \) subconjuntos de manera que cada uno de esos subconjuntos está totalmente ordenado, entonces necesariamente \( k \geq a \).

Ejercicio:
Demostrar que en un conjunto de 61 personas hay una sucesión de 13 elementos que cada uno de ellos esta relacionado con el siguiente y también que existe un grupo de 6 elementos que ningunos están relacionados con otros

Yo diría que el enunciado está mal. Fíjate que puedes tener un orden total y entonces no existe ningún grupo de \( 6 \) personas no relacionadas entre sí. E igualmente podrías tener el orden parcial en que cada persona está únicamente relacionada consigo misma y no tendrías ninguna sucesión de \( 13 \) elementos cada uno relacionado con el siguiente.

Sospecho que lo que tendría que pedir el ejercicio es:  "Demostrar que en un conjunto de 61 personas hay una sucesión de 13 elementos que cada uno de ellos esta relacionado con el siguiente o existe un grupo de 6 elementos que ningunos están relacionados con otros". Es decir, puedes asegurar que siempre pasa una de esas dos cosas, pero no que las dos cosas pasan a la vez. Para demostrar esta versión, fíjate que si no pasara ninguna de las dos cosas, cualquier anticadena tendría como mucho \( 5 \) elementos, mientras que cualquier cadena tendría como mucho \( 12 \) elementos. Ahora, si aplicas el teorema de Dilworth deberías poder obtener una cota superior para el tamaño de \( A \) y ver que esta cota es menor que \( 61 \), contradicción.

[Nub]

Encontré un par de cosas en un pdf de Internet y creo que estas definiciones son mas entendibles (para mi) y un lema que probablemente este es el que debo usar

El conjunto finito es de 61 elementos entonces \( 61=nm+1 \). Y tenemos la cadena de 13 elementos, entonces \( m+1=13 \) y una anticadena de 6 elementos entonces \( n+1=6 \)
Luego consigo el valor de n y m de las 2 ec y \( n=5 \) y \( m=12 \) entonces \( 61=5*12+1 \) y supongo que ahí queda demostrado por el lema o algo asi 

[Nub]

Como consejo, ¿que teorema de dilworth seria mejor quedarme? obviamente que con el lema me quedare, pero cual seria mas directo?

[geómetracat]

El conjunto finito es de 61 elementos entonces \( 61=nm+1 \). Y tenemos la cadena de 13 elementos, entonces \( m+1=13 \) y una anticadena de 6 elementos entonces \( n+1=6 \)
Luego consigo el valor de n y m de las 2 ec y \( n=5 \) y \( m=12 \) entonces \( 61=5*12+1 \) y supongo que ahí queda demostrado por el lema o algo asi 

Sí, está bien.

Como consejo, ¿que teorema de dilworth seria mejor quedarme? obviamente que con el lema me quedare, pero cual seria mas directo?

El segundo es más general del primero. Fíjate que el segundo te dice en particular que si tienes una anticadena maximal con \( m \) elementos, entonces el orden parcial es unión disjunta de \( m \) cadenas. Y no lo puede ser de menos, porque en tal caso sería imposible tener una anticadena con \( m \) elementos. Es decir, que cualquier partición del orden parcial en cadenas tiene al menos \( m \) elementos, que es lo que afirma el primer teorema.

Por otro lado, el lema se deduce de cualquiera de los dos teoremas (por ejemplo del primero), que es lo que apuntaba en mi mensaje anterior. Se prueba el contrarrecíproco: si no existe ni una cadena de longitud \( m+1 \) ni una anticadena de tamaño \( n+1 \), entonces por el primer teorema el orden se puede expresar como unión disjunta de a lo sumo \( n \) cadenas (porque el tamaño de una anticadena maximal es como mucho \( n \)) y cada una de estas cadenas tiene como mucho \( m \) elementos. Es decir, el tamaño del orden cumple \( |A| \leq mn < mn+1 \).

[Nub]

El conjunto finito es de 61 elementos entonces \( 61=nm+1 \). Y tenemos la cadena de 13 elementos, entonces \( m+1=13 \) y una anticadena de 6 elementos entonces \( n+1=6 \)
Luego consigo el valor de n y m de las 2 ec y \( n=5 \) y \( m=12 \) entonces \( 61=5*12+1 \) y supongo que ahí queda demostrado por el lema o algo asi 

Sí, está bien.

Como consejo, ¿que teorema de dilworth seria mejor quedarme? obviamente que con el lema me quedare, pero cual seria mas directo?

El segundo es más general del primero. Fíjate que el segundo te dice en particular que si tienes una anticadena maximal con \( m \) elementos, entonces el orden parcial es unión disjunta de \( m \) cadenas. Y no lo puede ser de menos, porque en tal caso sería imposible tener una anticadena con \( m \) elementos. Es decir, que cualquier partición del orden parcial en cadenas tiene al menos \( m \) elementos, que es lo que afirma el primer teorema.

Por otro lado, el lema se deduce de cualquiera de los dos teoremas (por ejemplo del primero), que es lo que apuntaba en mi mensaje anterior. Se prueba el contrarrecíproco: si no existe ni una cadena de longitud \( m+1 \) ni una anticadena de tamaño \( n+1 \), entonces por el primer teorema el orden se puede expresar como unión disjunta de a lo sumo \( n \) cadenas (porque el tamaño de una anticadena maximal es como mucho \( n \)) y cada una de estas cadenas tiene como mucho \( m \) elementos. Es decir, el tamaño del orden cumple \( |A| \leq mn < mn+1 \).

Entiendo, muchas gracias