# Cardinality of a semi-independent system of a finite set

We say a system $S$ is semi-independent of subsets of $X$ if it contains no three sets $A,B,C$ such that $A\subset B \subset C$. Show that 1. $\mid S \mid \leq 2{{n}\choose{\lfloor n/2\rfloor}}$ where $n=\mid X \mid$ and 2. For odd $n$, the estimate in 1 cannot be improved.

I want to use the Sperner's theorem to prove this statement but I don't know how to proceed. https://en.wikipedia.org/wiki/Sperner%27s_theorem

Any idea how to tackle this problem?

## 1 Answer

HINT: Let $S^+$ be the set of $A\in S$ that are not proper subsets of any $B\in S$, and let $S^-$ be the set of $A\in S$ that are not proper supersets of any $B\in S$. (In other words, if you view $\langle S,\subseteq\rangle$ as a partial order, $S^+$ is the set of maximal elements, and $S^-$ is the set of minimal elements.) The semi-independence of $S$ ensures that $S=S^+\cup S^-$. What can you say about the cardinalities of $S^+$ and $S^-$?

For the second question you can make use of the fact that $\left\lfloor\frac{n}2\right\rfloor<\left\lceil\frac{n}2\right\rceil$ when $n$ is odd.