Maximal subset iff maximum size

82 Views Asked by At

Let $X$ be a finite set with at least one element and $\eta\subseteq 2^X$ a collection of subsets of $X$ such that $$A\cup B\in\eta\text{ for every }A,B\in\eta$$ $$X=\bigcup_{A\in\eta}A$$ $$\text{For every }x,y\in X\text{ there exists }A\in\eta\text{ which contains one of them but not the other}$$ Now, for every $x\in X$ let $$\eta_x=\{\,A\in\eta\;:\;x\in A\,\}$$ The $\eta_x$ can be ordered either by size or by set inclusion. Is it true that $\eta_x$ is maximal (not a subset of any other $\eta_y$) if and only if $|\eta_x|=\max_{z\in X}|\eta_z|$ ?

Of course, if $|\eta_x|$ is the maximum then $\eta_x$ is maximal, but I'm having trouble proving the converse. All I know is that 1) If $A\in\eta$ has maximum size then $|A|=|X|-1$ and 2) Every $\eta_x$ contains one such set of maximum size.

For an attempt at a proof, if $|\eta_x|$ is not the maximum then 1) There exists $y\in X$ with $|\eta_x|<|\eta_y|$ and 2) One can choose an $A\in\eta_x$ of maximum size and take the only element $z\in X\setminus A$. The proof must continue trough one of these two because there aren't any other "interesting" points that we can focus on, but I can't finish the proof.

Thanks!

1

There are 1 best solutions below

4
On BEST ANSWER

For a simple counterexample, let $X=\{a,b,c\}$ and let $\eta$ be the collection of subsets $A\subseteq X$ such that if $c\in A$ then $b\in A$. Then $\eta_a$ and $\eta_b$ are both maximal, with $$\eta_a=\{\{a\},\{a,b\},\{a,b,c\}\}$$ having 3 elements and $$\eta_b=\{\{b\},\{a,b\},\{b,c\},\{a,b,c\}\}$$ having 4 elements.