Esta pregunta viene de Ejercicios III.4.5 y III.4.6 de Bourbaki la Teoría de conjuntos. Son sobre el uso de Dilworth del Teorema a demostrar Hall del Matrimonio Teorema (lo hizo) y una leve extensión de la misma (no puede hacerlo).
Dilworth del Teorema: Vamos a $E$ ser finito conjunto ordenado y $k$ ser el máximo número de elementos de un antichain en $E$. Entonces existe una partición de $E$ a $k$ totalmente de conjuntos ordenados.
Ayuntamiento de Matrimonio Teorema: Vamos a $E$ $F$ dos conjuntos finitos y deje $x\rightarrow A(x)$ ser una asignación de $E$ a $\mathfrak{P}(F)$ tal que $\text{Card}(\bigcup_{x\in H}A(x))\geq\text{Card}(H)$ para cualquier subconjunto $H$$E$. Entonces existe una inyección de $f$ $E$ a $F$ tal que $f(x)\in A(x)$ por cada $x\in E$.
Para demostrarlo, se define un orden en la inconexión de la unión de $E$ $F$ tal que $x>y$ si y sólo si $x\in E$$y\in F$$y\in A(x)$. Es fácil ver que $F$ es un antichain y que no hay antichain con más elementos de los que $F$. De modo que existe una partición de $E\sqcup F$ a $\text{Card}(F)$ totalmente de conjuntos ordenados, que son necesariamente un punto de subconjuntos de a $F$ o pares de $\{x,y\}$ tal que $y\in A(x)$. Los pares de definir el afirmado de la inyección.
Ayuntamiento de Matrimonio Teorema (Versión Extendida): En el marco de lo anterior, supongamos, además, que $G$ es un subconjunto de a$F$, y para cada uno de los $L\subset G$, $\text{Card}(\{x\in E|A(x)\cap L\neq\emptyset\})\geq\text{Card}(L)$. Podemos optar $f$ como el anterior y con la propiedad adicional $G\subset f(E)$.
La prueba está esbozado por Bourbaki como sigue: Considerar la inconexión de la unión de $G$, $F$, y $E$, lo que denota aquí como $(\{1\}\times G)\cup(\{2\}\times F)\cup(\{3\}\times E)$, y definir un orden en ella, estableciendo como única relaciones
- $(1,z)<(2,y)$ si y sólo si $z=y$
- $(1,z)<(3,x)$ si y sólo si $z\in A(x)$
- $(2,y)<(3,x)$ si y sólo si $y\in A(x)$
A continuación, aplicar Dilworth del Teorema.
El problema es que no sé bien cómo. El mayor número de elementos en un antichain es de nuevo $\text{Card}(F)$. Así que tenemos una partición de $G\sqcup F\sqcup E$ a $\text{Card}(F)$ totalmente de conjuntos ordenados. De nuevo, cada uno de esos conjuntos contiene exactamente un elemento de $F$, en la mayoría de los una de $E$, y en la mayoría de los una de $G$. De esta manera podemos definir una inyección de $f$ como antes definiendo $f(x)$ a ser el elemento de $F$ que se encuentra en el mismo conjunto de la partición como $x$, pero para $G\subset f(E)$ a celebrar, cada conjunto de la partición que contiene un elemento de $G$ tendría que contener un elemento de $E$. Pero obviamente esto no es cierto para todas las particiones de $G\sqcup F\sqcup E$ a $\text{Card}(F)$ totalmente de conjuntos ordenados.
Así que yo creo que uno tiene que encontrar una manera más sofisticada de la definición de $f$ a partir de una determinada partición o se tiene que modificar el orden de la relación antes de la aplicación de Dilworth del Teorema, utilizando de alguna manera la condición en la que los subconjuntos de a $G$. ¿Alguien vea una forma de terminar la prueba?
