7
$\begingroup$

Let $X$ be a set and $\{Y_\alpha\}$ is infinite system of some subsets of $X$. Is it true that: $\bigcup_\alpha(X\setminus Y_\alpha)=X\setminus\bigcap_\alpha Y_\alpha,$ $\bigcap_\alpha(X\setminus Y_\alpha)=X\setminus\bigcup_\alpha Y_\alpha.$ (infinite DeMorgan laws)

Thanks a lot!

  • 0
    @DonAntonio: Yes, this is true.2012-10-05

3 Answers 3

12

The first thing to do is the write and understand the definitions of all the symbols in the equation.

Let us recall those:

  1. $\bigcup_\alpha A_\alpha=\{a\mid\exists\alpha.a\in A_\alpha\}$
  2. $\bigcap_\alpha A_\alpha=\{a\mid\forall\alpha.a\in A_\alpha\}$
  3. $A\setminus B=\{a\in A\mid a\notin B\}$

Now we can write a simple element chasing proof:

Let $x\in X\setminus\bigcap_\alpha Y_\alpha$. Then $x\in X$ and $x\notin\bigcap_\alpha Y_\alpha$, therefore for some $\alpha$, $x\notin Y_\alpha$, fix such $\alpha$. Therefore $x\in X\setminus Y_\alpha$, and therefore there exists $\alpha$ such that $x\in X\setminus Y_\alpha$, and by definition we have that $x\in\bigcup_\alpha (X\setminus Y_\alpha)$.

The other direction is as simple, take $x\in\bigcup_\alpha(X\setminus Y_\alpha)$, then for some $\alpha$ we have $x\in X\setminus Y_\alpha$. Therefore $x\in X$ and $x\notin Y_\alpha$, so by definition $x\in X$ and $x\notin\bigcap_\alpha Y_\alpha$, i.e. $x\in X\setminus\bigcap_\alpha Y_\alpha$.

The second identity has a similar proof. I like these proofs because they not hard and give a good exercise in definitions and elements chasing.

  • 0
    @Axion004: I did not reject the edit, but I am guessing that the reason is that you've added too much content. Answers are supposed to reflect a user's mind. Changing someone's answers too much is not considered a good edit. If you want to elaborate or expand on someone's answer, you should post your own answer. This, on its own, might be frowned upon by some users, especially as a function of how old the question is (e.g. here were we are almost six years past the original post date). So handle with care.2018-08-23
2

For example:

$x\in \bigcup_\alpha(X\setminus Y_\alpha)\Longrightarrow \exists \alpha_0\,\,s.t.\,\,x\in X\setminus Y_{\alpha_0}\Longrightarrow x\notin Y_{\alpha_0}\Longrightarrow$

$\Longrightarrow x\notin\bigcap_\alpha Y_\alpha\Longrightarrow x\in X\setminus\left(\bigcap_{\alpha} Y_\alpha\right)$

2

(i) The following statements are equivalent:

  1. $ y \in X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} $
  2. $ y \in X \wedge y \notin \bigcap\limits_{\alpha \in I} A_{\alpha} $
  3. $ y \in X \wedge \neg((\forall \alpha \in I)\: y \in A_{\alpha}) $
  4. $ y \in X \wedge (\exists \alpha \in I)\: y \notin A_{\alpha} $
  5. $ (\exists \alpha \in I)(y \in X \wedge y \notin A_{\alpha}) $
  6. $ (\exists \alpha \in I)(y \in X \setminus A_{\alpha}) $
  7. $ y \in \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha}) $

(ii) The following statements are equivalent:

  1. $ y \in X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} $
  2. $ y \in X \wedge y \notin \bigcup\limits_{\alpha \in I} A_{\alpha} $
  3. $ y \in X \wedge \neg((\exists \alpha \in I)\: y \in A_{\alpha}) $
  4. $ y \in X \wedge (\forall \alpha \in I)\: y \notin A_{\alpha} $
  5. $ (\forall \alpha \in I)(y \in X \wedge y \notin A_{\alpha}) $
  6. $ (\forall \alpha \in I)(y \in X \setminus A_{\alpha}) $
  7. $ y \in \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha}) $

Since the first and the last statements are equivalent for all $y$, we have $ \underbrace{X \setminus \bigcap\limits_{\alpha \in I} A_{\alpha} = \bigcup\limits_{\alpha \in I}(X \setminus A_{\alpha})}_{(i)} \wedge \underbrace{X \setminus \bigcup\limits_{\alpha \in I} A_{\alpha} = \bigcap\limits_{\alpha \in I}(X \setminus A_{\alpha})}_{(ii)}. $ $\Box$