The De Morgan Formulas (for finite sets )

73 Views Asked by At

Pick an arbitrarily but fixed $w\in\Omega\;$ where $\mathbb{N}_n^* = \{1,2,...,n\}$. Then

$$ \begin{align} w\in\left(\bigcup_{k\in\mathbb{N}_n^*} A_k \right)^C &\Longrightarrow w \notin \left(\bigcup_{k\in\mathbb{N}_n^*} A_k \right)\\ &\Longrightarrow \neg \left[w \in \left(\bigcup_{k\in\mathbb{N}_n^*} A_k \right) \right]\\ &\Longrightarrow \neg \{w\in\Omega:\exists k\in\mathbb{N}_n^*\; s.t.\; w\in A_k \}\\ &\Longrightarrow \{w\in\Omega:\forall k\in\mathbb{N}_n^*;s.t.\;w\notin A_k\}\\ &\Longrightarrow w\in\left(\bigcap_{k\in\mathbb{N}_n^*} A_k^C\right)\\ \end{align} $$

Similarly, with regards to de Morgans 2nd Law:

$$ \begin{align} w\in\left(\bigcap_{k\in\mathbb{N}_n^*} A_k \right)^C &\Longrightarrow w \notin \left(\bigcap_{k\in\mathbb{N}_n^*} A_k \right)\\ &\Longrightarrow \neg \left[w \in \left(\bigcap_{k\in\mathbb{N}_n^*} A_k \right) \right]\\ &\Longrightarrow \neg \{w\in\Omega:\forall k\in\mathbb{N}_n^*\; s.t.\; w\in A_k \}\\ &\Longrightarrow \{w\in\Omega:\exists k\in\mathbb{N}_n^*\; s.t.\; w\notin A_k \}\\ &\Longrightarrow w\in\left(\bigcup_{k\in\mathbb{N}_n^*} A_k^C\right)\\ \end{align} $$

1

There are 1 best solutions below

2
On BEST ANSWER

What you have shown is that if $w \in \left(\cup_k A_k\right)^c$ then $w \in \cap_k A_k^c$, that is $\left(\cup_k A_k\right)^c \subset \cap_k A_k^c$. You must also show the reverse inclusion. In fact, all your implications ($\implies$) are equivalences $(\iff)$, but I leave you to check that.

Other than that your proofs are fine. You may observe that you never explicitly use that your index set is the 'finite naturals', so you may exchange it for any arbitrary index set (hence the general De Morgan's).