Let A1,A2,...,An be distinct subsets of a set X. Then there is subset Y with size <=n-1, s.t. all intersections are all distinct. Let $A_1,A_2,\dotsc,A_n$ be distinct subsets of a set $X$. Then there is subset $Y$ with size $\le n-1$, s.t. all intersections of $A_i$ with $Y$ are all distinct.
I am trying to prove it with induction, but I already got stuck at the base case.
When there are only two sets, how could I construct a set Y such that it satisfies the condition?
 A: Suppose the statement is known to hold for all families of size less than $n$; we will show that it holds for families of size $n$.
Let $\mathcal A=\{A_1,\dots,A_n\}$ be a family of $n$ distinct sets. If $n=1$ we can just take $Y=\emptyset$, so we assume $n\gt1$. Choose an element $y$ which belongs to one and only one of the two sets $A_1,A_2$.
Now split $\mathcal A$ into two subfamilies $\mathcal A',\mathcal A''$ where $\mathcal A'=\{A\in\mathcal A:y\in A\}$ and $\mathcal A''=\{A\in\mathcal A:y\notin A\}$. Let $|\mathcal A'|=n'$ and $|\mathcal A''|=n''$; thus $n',n''$ are positive integers, and $n'+n''=n$.
By the induction hypothesis we can choose a set $Y'$ of size $|Y'|\le n'-1$ such that the members of $\mathcal A'$ have distinct intersections with $Y'$; and we can choose a set $Y''$ of size $|Y''|\le n''-1$ such that the members of $\mathcal A''$ have distinct intersections with $Y''$.
Finally let $Y=\{y\}\cup Y'\cup Y''$. Then $|Y|\le1+(n'-1)+(n''-1)=n-1$, and the members of $\mathcal A$ all have distinct intersections with $Y$.
