# How to count elements in a family of subsets.

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

## 1 Answer

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$