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

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!

• Mysterious be n. Jun 26 '21 at 22:41

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.