How many sets are there in a union-closed family over a set of given size?

Question

Let $X$ be a finite set with $n$ elements and let $\eta$ be a "standard" union-closed collection of subsets of $X$, by which I mean a collection $\eta\subseteq\mathcal{P}(X)$ such that $$X\text{ has at least one element}$$ $$A\cup B\in\eta\text{ for every two }A,B\in\eta$$ $$\text{For every two }x,y\in X\text{ there exists an }A\in\eta\text{ which contains one of them but not the other}$$ $$X=\bigcup_{A\in\eta}A$$

I want to prove that, whenever this is the case, we have $$|X|\le|\eta|\le 2^{|X|}$$ The last inequality is trivial but I'm having trouble with the first one. None of the usual tactics work right away (induction, pigeonhole...) and I can't find the right trick to make it work. For example, assume that $m=|\eta|<|X|=n$ so that $\eta=\{A_1,\dots,A_m\}$. Given the conditions there must be at least one $A\in\eta$ with at least two elements. Wlog assume it is $A_1$. Then there must be at least one set, let it be $A_2$ such that $A_1\nsubseteq A_2$. This is as far as I can deduce directly because now $A_2$ could have only one element or who knows what.

Is there an easy proof of the first inequality? If it is true it is best possible because of the collection $$\eta=\{\{1\},\{1,2\},\dots,\{1,2,\dots,n\}\}$$ And, for induction, it is true for collections $\eta$ on sets of size $|X|=1,2,3$

Thanks!

Answer 1

Hints:

Consider a minimal counterexample

Given a counterexample, how would you construct a smaller one?

What's the largest set in $\eta$?

How big is the second largest set in $\eta$?

Proof:

Let $X, \eta$ be an example with $|X|$ minimal such that $\eta$ fulfills the above conditions and $|\eta| < |X|$.
We can easily see that $|X| > 2$, by considering available sets of subsets when $|X|$ is 1 or 2.

First, note that $X \in \eta$ (since $\eta$ is closed under pairwise unions, union of everything is $X$, and it's finite). Also, there must be at least one other set in $\eta$, else the pairwise separation condition would fail.

Let $A \in \eta, A \neq X$ be of maximal size (less than $|X|$)
Suppose $|A| < |X| - 1$. Then there are two elements $x, y$ both not in $A$
Then there is a set $B \in \eta$ with (wlog) $x \in B, y \notin B$.
But then $A \cup B \in \eta$, and $A \cup B \neq X$ as $y \neq A \cup B$, and $|A \cup B| \gt |A|$ as $x \in A \cup B$ and $x \notin A$, meaning $A$ is not maximal.
Hence a maximal $A$ must have $|A| = |X| - 1$.

Now, take maximal $A$ and consider $\eta_1 = \{ Y \cap A | Y \in \eta \}$.
This has size at most $|\eta| - 1$ (as $X \cap A = A \cap A$), which is less than $|A|$ (as $|\eta| \lt |X|$ and $|A| = |X| - 1$). It also satisfies the union and separation conditions above (since $\eta$ does and we have just removed one element from consideration).
But then $A, \eta_1$ contradicts $X, \eta$ being a minimal example above, and hence no such example can exist.