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: 
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.
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.