Proving DeMorgan's law for arbitrary unions/intersections

Question

I am trying to prove DeMorgan's law for arbitrary unions and intersections using Munkres's notation. One of the laws takes the form $$B - \bigcup\limits_{A \in \mathcal{A}} A = \bigcap\limits_{A \in \mathcal{A}} (B - A).$$ This is the not the notation I am accustomed to, which would instead take the form $$\bigcup\limits_{A \in \mathcal{A}} A^c = \left(\bigcap\limits_{A \in \mathcal{A}} A^c\right)^c,$$ but I am trying to prove this fact using Munkres's notation, which uses set differences in place of complements. Here is what I have so far. \begin{align*} x \in B - \bigcup\limits_{A \in \mathcal{A}} A & \iff x \in B \text{ and } x \not \in \bigcup\limits_{A \in \mathcal{A}} A \\ & \iff x \in B \text{ and } \forall A \in \mathcal{A}, \; x \not \in A \end{align*} At this point, I am immediately stuck because I want to say something to the effect of: \begin{align*} & \iff x \in (B - A_1) \text{ and } x \in (B - A_2) \ldots \end{align*} But the collection is arbitrary, so I cannot quite do that. In effect, I am using some sort of "pairing" and using the rule $p \wedge (q \wedge r)$ an arbitrary number of times. If I were to do that without writing it out in a misleading way, I would get something like: \begin{align*} & \iff x \in \bigcap\limits_{A \in \mathcal{A}} (B - A). \end{align*} But the problem is, I am essentially asserting the conclusion without showing any of the steps. The proof using the usual, complement notation I know to be far more involved in this. It seems that I am missing intermediary steps that are difficult to formalize with this notation. What am I missing?

Answer 1

You have deduced that $x \in B \text{ and } \forall A \in \mathcal{A}, \; x \not \in A$, and you are trying to prove that $\forall A \in \mathcal{A}, \; ( x \in B \text{ and } x \not \in A )$. This is an instance of a general rule for any statements $P$ and $Q(A)$: $$ P\land (\forall A\in\mathcal A,\, Q(A)) \implies (\forall A\in\mathcal A,\, P\land Q(A)). $$ (Indeed this is an equivalence, at least when $\mathcal A\ne\emptyset$, but you only need this one implication.) This is easy to prove: given an arbitrary $A\in\mathcal A$, you need to prove the statement $P\land Q(A)$, which can be done from the assumptions $P$ and $\forall A\in\mathcal A,\, Q(A)$.

Edited to add: For the backward implication, we need to prove two things: $P$, and $\forall A\in\mathcal A,\, Q(A)$.

• For a proof of $P$, we can do:
  • Since $\mathcal A$ is nonempty, we can choose $A_0\in \mathcal A$.
  • Since $\forall A\in\mathcal A,\, P\land Q(A)$, we know in particular that $P\land Q(A_0)$.
  • In particular, we know $P$.
• For a proof of $\forall A\in\mathcal A,\, Q(A)$, we can do:
  • Suppose that $A_1$ is any element of $\mathcal A$.
  • Since $\forall A\in\mathcal A,\, P\land Q(A)$, we know in particular that $P\land Q(A_1)$.
  • In particular, we know $Q(A_1)$.
  • Since $A_1\in\mathcal A$ was arbitrary, we have proved $\forall A\in\mathcal A,\, Q(A)$.

(Note the subtle difference between the two parts; the first part requires $\mathcal A$ to be nonempty, but the second part is perfectly valid if $\mathcal A$ is empty, since a universal statement is vacuously true in that case.)

Moral of the story, at least for me: the logical structure of the statement to be proved is what tells us the structure of the proof itself, and hence how we should arrange our steps in that proof.