system set theory I got the following problem
Let $A_1...A_n$ be n sets. A sequence $x_1...x_n$ is called representative of $A_1 ... A_n$ if $x_i \in A_i$ and $x_i \neq x_j$
Proof the following: A representative sequence exists if and only if the union of $m \in \{1,2,3...n \}$ sets of different $A_i$ has at least $m$ elements
Let P be such a union  and $x_n$ be the representative sequence then $\{ x_{k_1},x_{k_2} ...x_{k_m} \} \subset P$ and hence $|P|\ge m$
However, I dont know how to show the other direction.
Would appreciate any help
 A: Consider the sets $A_{i}=\{a_{i_{j}}\}.$ Now consider two sets $X=\cup_{i=1}^{n}A_{i}=\{a_{1_{1}},a_{1_{2}},a_{1_{3}}....\}$ and $Y=\{1,2,3...,n-1,n\}$. Now consider a bipartite graph $G$ having bipartition $X$ and $Y$ and edges  $a_{i_{j}}\sim i$ for all $i\in\{1,2,3....n\}$ and $j$ such that $a_{i_{j}}\in A_{i}$. Now we use Hall's Marriage Theorem here.
So in $G$ there exist a matching saturating $Y$ iff $\forall S\subseteq Y, |N(S)|\geq |S|.$ 
In $G$ say $S=\{i_{1},i_{2},...i_{k}\}\subseteq Y$ then $N(S)=\cup_{j=1}^{k}A_{i_{j}}.$
So here suppose we have representatives for the sets. This implies we have $x_{i}\in A_{i}$ such that $x_{i}\neq x_{j}$. This is same as saying we have matched $i\in Y$ to some $z_{i}\in X$ $\forall i\in Y$. Hence we have a matching saturating $Y$. Hence by Hall's Theorem $\forall S\subseteq Y, |N(S)|\geq |S|.$ That is take any $m$ sets say $A_{i_{1}},A_{i_{2}},..A_{i_{m}}$ then $S=\{i_{1},i_{2},..i_{m}\}$ then $|N(S)|=|\cup_{j=1}^{m}A_{i_{j}}|\geq |S|=m.$
Now suppose that given any $m$ sets the size of union of such $m$ sets is greater than or equal $m$. Now take any $S\subseteq Y$. Say $|S|=k$ and  $S=\{i_{1},i_{2},...i_{k}\}$. Now by above statement we have $|\cup_{j=1}^{k}A_{i_{j}}|=|N(S)|\geq k=|S|$. Now $S$ was arbitatry. Hence $\forall S\subseteq Y, |N(S)|\geq |S|$. Hence by Hall's Theorem we have $G$ has a matching saturating $Y$. Hence $\forall i\in\{1,2,...n\} \exists x_{i}\in X$ such that $i$ is matched to $x_{i}$. Now we show that $Z=\{x_{1},x_{2}....x_{n}\}$ is a set of required representatives. Take any $x_{i}$ and $x_{j}$. By the way edges are defined we have $x_{i}\in A_{i}$ and $x_{j}\in A_{j}$. Also $x_{i}\neq x_{j}$ since they belong to a matching. This is true for all $i,j$. Hence Z is a set of reuired representatives. Hence proved.
