0
$\begingroup$

I am reading a survey on Frankl's Conjecture. It is stated without commentary that the set of complements of a union-closed family is intersection-closed. I need some clearer indication of why this is true, though I guess it is supposed to be obvious.

$\endgroup$
1
1
$\begingroup$

This is because we can rewrite $(A \cup B)^C = A^C \cap B^C$ using DeMorgan's laws. Now, if $\mathbb{S}$ is the family of sets closed under union and $A, B \in \mathbb{S}$, then $A \cup B \in \mathbb{S}$ (since it's closed under union). Therefore, $(A\cup B)^C \in \mathbb{S}^C$ (by the definition of the complement family). Hence, $A^C \cap B^C = (A \cup B) ^C \in \mathbb{S}^C$

$\endgroup$
1
  • $\begingroup$ thanks. I know how I went wrong now. I was trying to do a proof by contradiction and it's more straightforward than that! $\endgroup$ – user136920 Mar 28 '19 at 5:31
1
$\begingroup$

It is not clear if you are talking about union of two sets or arbitrary unions. In either case the result is true and it is an easy consequence of DeMorgan's Law: $(\cup_i A_i)^{c}=\cap_i A_I^{c}$.

$\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.