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

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.

• What does the theorem actually say? In your headline you write $|S| \ge 2n -1 + 1$, which is probably a type (so you should fix it). In your question, you say "$S$ has $2^n + 1$ elements" (I assume that's what you mean). But if $S \subseteq \mathcal{P}(n)$ then $|S| \le 2^n$, so probably you mean that $S$ is a sequence of subsets of $n$. In that case the pigeonhole principle applies. Commented Oct 11, 2015 at 23:27
• I've edited the question, please make sure I'm using the correct exponents (and that I haven't done anything else undesirable). It was a little unclear what was meant as the exponent. Commented Oct 11, 2015 at 23:29
• Ah that's better. Commented Oct 11, 2015 at 23:30
• (I just noticed I made a typo trying to type "typo".) Commented Oct 12, 2015 at 0:07
• I think I found an inclusion exclusion approach. Let A sub k be the set of all subsets that contain k, and so on. Commented Oct 12, 2015 at 0:36

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.

• Thanks. I'll check this out. I was expecting a pigeonhole approach, but this looks good. Commented Oct 11, 2015 at 23:46
• Is n/X the set 1,....,n minus each set in S. Commented Oct 11, 2015 at 23:48
• I'm using $n = \{i \in \mathbb{N} \mid i < n\}$, which in set theory is not just a convention but is actually true. So it's not $\{1, 2, \dots, n\}$ but rather $\{0, 1, \dots, n-1\}$ – logicians count starting at 0 :) Thus for $X \in S$, $n \setminus X$ is the complement of $X$ relative to $n$, namely $\{y \in n \mid y \notin X\}$. Commented Oct 11, 2015 at 23:54
• Nice. I like that. I've seen the set theory contraction of the natural numbers. Great stuff. Commented Oct 12, 2015 at 0:03
• "contraction" --> "construction" :) Commented Oct 12, 2015 at 0:04

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.

• Thanks. I'll give that a try and mark your suggestion correct if I see the path. I want to wait for as much insight as possible. Commented Oct 11, 2015 at 23:43

$$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)$$