0
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ Mysterious be n. $\endgroup$ Jun 26 '21 at 22:41
1
$\begingroup$

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.

$\endgroup$

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.