Prove that if $|S| \ge 2^{n−1} + 1$, then $S$ contains two elements which are disjoint from each other.

Question

I'm trying to use the pigeonhole principle to prove that

if $S$ is a subset of the power set of the first $n$ positive integers, and if $S$ has at least $2^{n-1}+1$ elements, then $S$ must contain a pair of pairwise disjoint sets.

I've been playing around with a small set $\{1,2,3\}$ and I can see the theorem seems to be true in this case. But I can't see, for instance, how to construct the pigeonholes so that $\{2\}$ and $\{3\}$, for instance, end up in the same pigeonhole. I've been looking at which subsets of the power set the elements in $S$ do NOT contain, to no avail.

Can someone give me a hint about which pigeonholes to look at?

I'm adding this in response to the comments below: Demonstrate that it is possible for |S| (i.e., the number of subsets of {1, . . . , n} contained as elements of S ) to equal 2n−1 without any two elements of S being disjoint from each other. I can do this. This provides context.

Answer 1

Given $S \subseteq \mathcal{P}(n)$ with $|S| \ge 2^{n-1} + 1$, suppose $S$ does not contain a disjoint pair of sets. Let $T = \{n \setminus X \mid X \in S\}$. Then $S, T$ are disjoint subsets of $\mathcal{P}(n)$ having the same cardinality ($X \mapsto (n \setminus X)$ bijects $S \leftrightarrow T$), so: $$ \begin{align} |S \cup T| &= |S| + |T| \\ &= 2 |S| \\ &\ge 2(2^{n-1} + 1) \\ &= 2^n + 2 \end{align} $$ which can't be.

This isn't quite a proof by pigenhole, but maybe it is if you squint.

Answer 2

Try this: there are always as many even-cardinality subsets of a set as there are odd-numbered subsets. Use even-cardinality subsets and odd-cardinality subsets as your pigeonholes.

Answer 3

$S$ contains at most one of $(A,A^c)$ for each $A \in \mathcal{P}(n)$. Hence at most contains $\frac{1}{2}$ of the elements of $\mathcal{P}(n)$