# Generalized DeMorgan's Law proof

We wish to verify the generalized law of DeMorgan $(\bigcup_{i \in \mathcal{I}} A_i)^c = \bigcap_{i \in \mathcal{I}} A_i^c$.

Let $x \in (\bigcup_{i \in \mathcal{I}} A_i)^c$. Then $x \notin \bigcup_{i \in \mathcal{I}} A_i$ and $x \notin A_i$ for $i \in \mathcal{I}$, and so $x \in A_i^c$ for all $i$. Hence $x \in \bigcap_{i \in \mathcal{I}} A_i^c$. We have shown that $(\bigcup_{i \in \mathcal{I}} A_i)^c \subset \bigcap_{i \in \mathcal{I}} A_i^c$.

We must now show that $\bigcap_{i \in \mathcal{I}} A_i^c \subset (\bigcup_{i \in \mathcal{I}} A_i)^c$. Now let $x \in \bigcap_{i \in \mathcal{I}} A_i^c.$ Then $x \in A_i^c$ for all $i \in \mathcal{I}$ and so $x \notin A_i$ for all $i \in \mathcal{I}$. Hence $x \in A_i^c$ for all $i \in \mathcal{I}$ and so $x \in (\bigcup_{i \in \mathcal{I}} A_i)^c$.

Then $\bigcap_{i \in \mathcal{I}} A_i^c \subset (\bigcup_{i \in \mathcal{I}} A_i)^c$, and since $(\bigcup_{i \in \mathcal{I}} A_i)^c \subset \bigcap_{i \in \mathcal{I}} A_i^c$ we have that $(\bigcup_{i \in \mathcal{I}} A_i)^c = \bigcap_{i \in \mathcal{I}} A_i^c$, which is what we set out to show.

I just want to make sure that my proof makes sense and I was hoping for some constructive criticism regarding proof style/format -- would really appreciate any feedback whatsoever.

You should not write

for $i= 1,2, \dots$

since you do not know that $\mathcal{I}$ is countable (or even consists of integers - perhaps $\mathcal{I}=\mathbb{Q}$ or $\mathcal{I}=\mathbb{R}^2$ or some set that doesn't even contain numbers).

In the reverse direction, you jump from $y \notin A_i$ for all $i \in \mathcal{I}$ to $y \in (\bigcup_{i \in \mathcal{I}} A_i)^c$. That jump is probably fine in most proofs, though you may want to stick closer to the definitions like you did in the forward direction if this is for an intro to proofs course. I would recommend adding an intermediate step there.

• Thanks a lot for the feedback. It's not for any class, I'm just trying to learn proof on my own or at least work on my proofs because I haven't gotten much feedback/critique before. I see what you mean re I being countable and adding another intermediate step in the forward direction. Is it okay to say instead "for all $i \in I$" then? – Hugo Nov 23 '15 at 9:07
• Is it necessary to switch from x to y when going from one direction to the next as I did? I assumed it made sense to do so because it hadn't been established yet the two sets were equal. – Hugo Nov 23 '15 at 9:14
• Yes, "for all $i \in I$" is probably the best way to phrase it. And no, it is not necessary to switch from $x$ to $y$. I think it's understood that when you switch directions and say "now let $x \in$..." this is a different $x$ from the $x$ you chose in the first direction. I hope that makes sense. – kccu Nov 24 '15 at 0:06
• The fact that $\mathcal{I}$ may not be a countable set prevents me from using a proof by induction here -- is that correct? I know the standard way to show equality between sets is to show that the two sets contain one another, but I was thinking to mess around with a proof by induction, but that seems to not be possible if $\mathcal{I}$ is uncountable. – Hugo Nov 24 '15 at 9:10
• It's not even possible if $I$ is countable. The only sort of result you could show by induction is $\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c$ for all $n \in \mathbb{N}$. But this only holds for finite (though arbitrarily large) $n$. A proof by induction would not tell you that $\left(\bigcup_{i=1}^\infty A_i \right) ^c = \bigcap_{i=1}^\infty A_i^c$. – kccu Nov 24 '15 at 17:37