I recently encountered a question
Let $n \in \mathbb{Z} ^+$, Let $U$ be a set containing $n$ elements. Let $\mathcal{S} \subseteq P(U)$. Let $m \in \mathbb{Z}^+, m \leq n$.
Prove that
$$ |\mathcal{S}| > \sum_{i=0}^{m - 1} \binom{n}{i} \Rightarrow \exists S' \in P(U). (|S'|=m) \wedge \left(\{S \cap S':S \in \mathcal{S}\} = P(S')\right) $$
Currently, I am inducting on $n$ and $m$. I have proved the cases when $n = 1$ or $m = 1$.
For the induction step, I have three cases.
The first case is when none of the sets in $\mathcal{S}$ contains the $n$th element of $U$.
The second case is when exactly half of the sets in $\mathcal{S}$ contain the $n$th element of $U$.
The last case is when the previous two cases are false.
I can prove the first two cases. However I am strugling with the third case.
I have tried using the induction hypothesis on $n - 1, m - 1$ and $n, m - 1$, but I didn't get anywhere. My idea is to use a non-constructive probabalistic method, but that turned real messy real fast, due to each event being dependent on the others.
So I guess I am missing something obvious here? Maybe there is an observation that can make things more elegant? Or should I keep going down that probabalistic method path?
What you are trying to prove is the well-known Sauer–Shelah lemma. The core idea to make induction on the size of $\mathcal{S}$ work is to modify what you wanna prove a little. Namely, instead of proving that there exists some subset $S'$ of $U$ of cardinality $m$ such that $\{S \cap S': S\in \mathcal{S}\} = P(S')$, prove that there exist at least $|\mathcal{S}|$ subsets of $U$ without restriction on their cardinalities such that $\{S \cap S': S\in \mathcal{S}\} = P(S')$. The full proof of this fact is on the Wikipedia page. The initial claim now follows from the fact that $|\mathcal{S}|$ is strictly greater than the number of subsets of $U$ of cardinality up to $m-1$.