The statement of the problem:

Let $S$ be a finite set having $n$ elements where $n>2$. Let $P$ be a family of subsets of $S$ such that $P$ has at least $2^{n-1}$ elements. Prove that there are $A,B \in P$ such that $A\subset B$.

My idea:

Proceed with induction.

Base case: Let $n=3$. Then for $P\subset 2^S$, if $S \in P$, or if $\emptyset \in P$ we are done. Thus, $P$ has at most 6 elements. There must be at least one set of the form $\{a,b\} \in P$ or else $\vert P \vert \leq 3$. Thus, if all the singletons are in $P$, we are done. However, if only two singletons are in $P$, then there is no pair which does not contain a singleton, so we are done. If $P$ has only one singleton, then there is only one pair which does not contain the singleton, and we are done.

Inductive step: Assume that for a finite set $S$ where $\vert S\vert = n$ that $P \subset 2^S, \vert P \vert \geq 2^{n-1} \implies \exists A,B \in P$ such that $A\subset B$.

Let $T$ be a finite set with $|T| = n+1$ and $P\subset 2^T$ such that $|P| \geq 2^n$. Let $t \in T$. We can count all elements of $P$ with $t$ and all those without $t$. These partition $P$, so it suffices to show that each subfamily has cardinality between $2^{n-1}$ and $2^n$. Then we can apply our inductive hypothesis.

This is where I need help, counting all of the possible sets with or all those without $t$.


For $|S|=n+1$, you divide the subsets of $S$ into those containing $t$ and those not. The subsets not containing $t$ are just the inductive hypothesis. The subsets containing $t$ are the same in number and all have $t$, so the number of them is the same as the subsets without $t$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.