1
$\begingroup$

Let $E$ be a set, and let $S$ be any set of subsets of $E$, such that $S$ contains the empty set. Can you identify the smallest set of subsets $T$ of $E$ such that $T$ contains all elements of $S$, and $T$ is stable by both finite union and by any intersections ? If possible write the generic form of an element of $T$ by using elements of $S$, with unions and intersections.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

$T$ is the set (say $S^\ast$) of all intersections of finite unions of elements of $S$.

Indeed, clearly $T\supseteq S^\ast$. It is also clear that $S^\ast$ is closed wrt to intersections. Finally, $S^\ast$ is closed wrt to finite unions, because $$\bigcup_{j=1}^n\bigcap_{i_j\in I_j}A_{i_j,j} =\bigcap_{(i_1,\dots,i_n)\in I_1\times\cdots\times I_n}\,\bigcup_{j=1}^n A_{i_j,j}$$ for any sets $A_{i,j}$ and any index sets $I_j$ -- use now the displayed identity for the case when each of the $A_{i,j}$'s is the union of finitely many elements of $S$, and the fact that finite unions of finite unions of sets are finite unions of sets.


Cf. conversion to the conjunctive normal form and the disjunctive normal form.

$\endgroup$
2
  • $\begingroup$ The question asks for finite unions, but arbitrary intersections, not just finite intersections. So the correct answer is that $T$ is the set of arbitrary intersections of finite unions of elements of $S$; you can't do that with unions of intersections. $\endgroup$ Commented Apr 25 at 18:34
  • $\begingroup$ @EmilJeřábek : Oops! I did not pay enough attention to the question. This is now fixed. Thank you for your comment. $\endgroup$ Commented Apr 25 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .