teoría de sistemas de conjuntos

Question

Tengo el siguiente problema
Deje que $A_1...A_n$ ser n conjuntos. Una secuencia $x_1...x_n$ se llama representante de $A_1 ... A_n$ si $x_i \in A_i$ y $x_i \neq x_j$

Prueba lo siguiente: Una secuencia representativa existe si y sólo si la unión de $m \in \{1,2,3...n \}$ conjuntos de diferentes $A_i$ tiene al menos $m$ elementos

Que P sea tal unión y $x_n$ ser la secuencia representativa entonces $\{ x_{k_1},x_{k_2} ...x_{k_m} \} \subset P$ y por lo tanto $|P| \ge m$

Sin embargo, no sé cómo mostrar la otra dirección.
Apreciaría cualquier ayuda

Answer 1

Considere los conjuntos $A_{i}=\{a_{i_{j}}\}.$ Consideremos ahora dos conjuntos $X=\cup_{i=1}^{n}A_{i}=\{a_{1_{1}},a_{1_{2}},a_{1_{3}}....\}$ y $Y=\{1,2,3...,n-1,n\}$ . Consideremos ahora un grafo bipartito $G$ tener bipartición $X$ y $Y$ y bordes $a_{i_{j}}\sim i$ para todos $i\in\{1,2,3....n\}$ y $j$ tal que $a_{i_{j}}\in A_{i}$ . Ahora utilizamos aquí el Teorema del Matrimonio de Hall.

Así que en $G$ existe una saturación coincidente $Y$ si $\forall S\subseteq Y, |N(S)|\geq |S|.$

En $G$ diga $S=\{i_{1},i_{2},...i_{k}\}\subseteq Y$ entonces $N(S)=\cup_{j=1}^{k}A_{i_{j}}.$

Así que aquí supongamos que tenemos representantes para los conjuntos. Esto implica que tenemos $x_{i}\in A_{i}$ tal que $x_{i}\neq x_{j}$ . Esto es lo mismo que decir que hemos emparejado $i\in Y$ a algunos $z_{i}\in X$ $\forall i\in Y$ . Por lo tanto, tenemos una saturación coincidente $Y$ . Por lo tanto, por el Teorema de Hall $\forall S\subseteq Y, |N(S)|\geq |S|.$ Es decir, tomar cualquier $m$ conjuntos dicen $A_{i_{1}},A_{i_{2}},..A_{i_{m}}$ entonces $S=\{i_{1},i_{2},..i_{m}\}$ entonces $|N(S)|=|\cup_{j=1}^{m}A_{i_{j}}|\geq |S|=m.$

Supongamos ahora que, dado cualquier $m$ establece el tamaño de la unión de tales $m$ conjuntos es mayor o igual que $m$ . Ahora toma cualquier $S\subseteq Y$ . Diga $|S|=k$ y $S=\{i_{1},i_{2},...i_{k}\}$ . Ahora, por la afirmación anterior, tenemos $|\cup_{j=1}^{k}A_{i_{j}}|=|N(S)|\geq k=|S|$ . Ahora $S$ era la arbitrariedad. De ahí que $\forall S\subseteq Y, |N(S)|\geq |S|$ . Por lo tanto, por el Teorema de Hall tenemos $G$ tiene una saturación correspondiente $Y$ . Por lo tanto, $\forall i\in\{1,2,...n\} \exists x_{i}\in X$ tal que $i$ se ajusta a $x_{i}$ . Ahora demostramos que $Z=\{x_{1},x_{2}....x_{n}\}$ es un conjunto de representantes necesarios. Tome cualquier $x_{i}$ y $x_{j}$ . Por la forma en que se definen las aristas tenemos $x_{i}\in A_{i}$ y $x_{j}\in A_{j}$ . También $x_{i}\neq x_{j}$ ya que pertenecen a un emparejamiento. Esto es cierto para todos los $i,j$ . Por lo tanto, Z es un conjunto de representantes necesarios. Por lo tanto, se ha demostrado.