3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – BrianO
    Commented Oct 11, 2015 at 23:27
  • $\begingroup$ 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. $\endgroup$
    – pjs36
    Commented Oct 11, 2015 at 23:29
  • $\begingroup$ Ah that's better. $\endgroup$
    – BrianO
    Commented Oct 11, 2015 at 23:30
  • $\begingroup$ (I just noticed I made a typo trying to type "typo".) $\endgroup$
    – BrianO
    Commented Oct 12, 2015 at 0:07
  • $\begingroup$ I think I found an inclusion exclusion approach. Let A sub k be the set of all subsets that contain k, and so on. $\endgroup$
    – Daniel H
    Commented Oct 12, 2015 at 0:36

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks. I'll check this out. I was expecting a pigeonhole approach, but this looks good. $\endgroup$
    – Daniel H
    Commented Oct 11, 2015 at 23:46
  • $\begingroup$ Is n/X the set 1,....,n minus each set in S. $\endgroup$
    – Daniel H
    Commented Oct 11, 2015 at 23:48
  • $\begingroup$ 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\}$. $\endgroup$
    – BrianO
    Commented Oct 11, 2015 at 23:54
  • $\begingroup$ Nice. I like that. I've seen the set theory contraction of the natural numbers. Great stuff. $\endgroup$
    – Daniel H
    Commented Oct 12, 2015 at 0:03
  • $\begingroup$ "contraction" --> "construction" :) $\endgroup$
    – BrianO
    Commented Oct 12, 2015 at 0:04
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel H
    Commented Oct 11, 2015 at 23:43
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .