[proofplan] We prove each [set](/page/Set) identity by testing membership of an arbitrary element $x \in X$. The binary identities follow by expanding the definitions of complement, union, and intersection, then translating the resulting membership statements through the corresponding propositional negations. The indexed identities use the same method, with union represented by an existential quantifier over $I$ and intersection represented by a universal quantifier over $I$. [/proofplan] [step:Expand membership to prove the complement of a union identity] Let $x \in X$ be arbitrary. By the definitions of complement in $X$, union, and intersection, \begin{align*} x \in (A \cup B)^c &\iff x \notin A \cup B \\ &\iff \neg(x \in A \lor x \in B) \\ &\iff (x \notin A) \land (x \notin B) \\ &\iff (x \in A^c) \land (x \in B^c) \\ &\iff x \in A^c \cap B^c. \end{align*} Since the equivalence holds for every $x \in X$, the two subsets of $X$ have the same elements. Hence $(A \cup B)^c = A^c \cap B^c$. [/step] [step:Expand membership to prove the complement of an intersection identity] Let $x \in X$ be arbitrary. By the definitions of complement in $X$, intersection, and union, \begin{align*} x \in (A \cap B)^c &\iff x \notin A \cap B \\ &\iff \neg(x \in A \land x \in B) \\ &\iff (x \notin A) \lor (x \notin B) \\ &\iff (x \in A^c) \lor (x \in B^c) \\ &\iff x \in A^c \cup B^c. \end{align*} Since the equivalence holds for every $x \in X$, the two subsets of $X$ have the same elements. Hence $(A \cap B)^c = A^c \cup B^c$. [/step] [step:Use quantifier negation to prove the indexed union identity] Let $x \in X$ be arbitrary. By the definitions of complement in $X$, indexed union, and indexed intersection, \begin{align*} x \in \Bigl(\bigcup_{i \in I} A_i\Bigr)^c &\iff x \notin \bigcup_{i \in I} A_i \\ &\iff \neg(\exists i \in I \text{ such that } x \in A_i) \\ &\iff \forall i \in I,\ x \notin A_i \\ &\iff \forall i \in I,\ x \in A_i^c \\ &\iff x \in \bigcap_{i \in I} A_i^c. \end{align*} This equivalence is valid also when $I = \varnothing$, since then the existential statement is false and the universal statement is true. Therefore \begin{align*} \Bigl(\bigcup_{i \in I} A_i\Bigr)^c = \bigcap_{i \in I} A_i^c. \end{align*} [guided] Let $x \in X$ be arbitrary. To prove equality of two subsets of $X$, it is enough to show that $x$ belongs to the left-hand side exactly when it belongs to the right-hand side. First expand the complement: \begin{align*} x \in \Bigl(\bigcup_{i \in I} A_i\Bigr)^c \iff x \notin \bigcup_{i \in I} A_i. \end{align*} Now expand membership in an indexed union. The statement $x \in \bigcup_{i \in I} A_i$ means that there exists an index $i \in I$ with $x \in A_i$. Therefore \begin{align*} x \notin \bigcup_{i \in I} A_i \iff \neg(\exists i \in I \text{ such that } x \in A_i). \end{align*} Negating an existential quantifier gives a universal negation: \begin{align*} \neg(\exists i \in I \text{ such that } x \in A_i) \iff \forall i \in I,\ x \notin A_i. \end{align*} For each $i \in I$, the definition of complement in $X$ gives $x \notin A_i \iff x \in A_i^c$. Hence \begin{align*} \forall i \in I,\ x \notin A_i \iff \forall i \in I,\ x \in A_i^c. \end{align*} Finally, membership in the indexed intersection $\bigcap_{i \in I} A_i^c$ means membership in every $A_i^c$, so \begin{align*} \forall i \in I,\ x \in A_i^c \iff x \in \bigcap_{i \in I} A_i^c. \end{align*} Combining the equivalences, \begin{align*} x \in \Bigl(\bigcup_{i \in I} A_i\Bigr)^c \iff x \in \bigcap_{i \in I} A_i^c. \end{align*} This also covers the case $I = \varnothing$: the existential statement over $\varnothing$ is false, while the corresponding universal statement is true. Since $x \in X$ was arbitrary, \begin{align*} \Bigl(\bigcup_{i \in I} A_i\Bigr)^c = \bigcap_{i \in I} A_i^c. \end{align*} [/guided] [/step] [step:Use quantifier negation to prove the indexed intersection identity] Let $x \in X$ be arbitrary. By the definitions of complement in $X$, indexed intersection, and indexed union, \begin{align*} x \in \Bigl(\bigcap_{i \in I} A_i\Bigr)^c &\iff x \notin \bigcap_{i \in I} A_i \\ &\iff \neg(\forall i \in I,\ x \in A_i) \\ &\iff \exists i \in I \text{ such that } x \notin A_i \\ &\iff \exists i \in I \text{ such that } x \in A_i^c \\ &\iff x \in \bigcup_{i \in I} A_i^c. \end{align*} This equivalence is valid also when $I = \varnothing$, since then the universal statement is true and its negation is false. Therefore \begin{align*} \Bigl(\bigcap_{i \in I} A_i\Bigr)^c = \bigcup_{i \in I} A_i^c. \end{align*} Combining this with the previous steps proves all stated identities. [guided] Let $x \in X$ be arbitrary. We again prove equality by comparing membership. First expand the complement: \begin{align*} x \in \Bigl(\bigcap_{i \in I} A_i\Bigr)^c \iff x \notin \bigcap_{i \in I} A_i. \end{align*} Membership in an indexed intersection means membership in every set in the family: \begin{align*} x \in \bigcap_{i \in I} A_i \iff \forall i \in I,\ x \in A_i. \end{align*} Therefore \begin{align*} x \notin \bigcap_{i \in I} A_i \iff \neg(\forall i \in I,\ x \in A_i). \end{align*} Negating a universal quantifier gives an existential negation: \begin{align*} \neg(\forall i \in I,\ x \in A_i) \iff \exists i \in I \text{ such that } x \notin A_i. \end{align*} For each index $i \in I$, the definition of complement in $X$ gives $x \notin A_i \iff x \in A_i^c$. Thus \begin{align*} \exists i \in I \text{ such that } x \notin A_i \iff \exists i \in I \text{ such that } x \in A_i^c. \end{align*} By the definition of indexed union, \begin{align*} \exists i \in I \text{ such that } x \in A_i^c \iff x \in \bigcup_{i \in I} A_i^c. \end{align*} Combining these equivalences gives \begin{align*} x \in \Bigl(\bigcap_{i \in I} A_i\Bigr)^c \iff x \in \bigcup_{i \in I} A_i^c. \end{align*} When $I = \varnothing$, the statement $\forall i \in I,\ x \in A_i$ is true, so its negation is false; the union $\bigcup_{i \in I} A_i^c$ also has no element witnessing membership. Hence the same equivalence holds in the empty-index case. Since $x \in X$ was arbitrary, \begin{align*} \Bigl(\bigcap_{i \in I} A_i\Bigr)^c = \bigcup_{i \in I} A_i^c. \end{align*} Together with the binary identities already proved, this completes the proof. [/guided] [/step]