Induction question regarding Universe

Question

I was given a question that looks like this.

Prove that for each $2 \le n\in \mathbb N$, if $X_1,\ldots,X_n$ are subsets of some universe $U$, then the following is true:

$$(X_1 \cup\cdots\cup X_n)^c = X_1^c \cap \cdots\cap X_n^c.$$

I am so confused i was staring at this question for at least 2 hours and have no idea how to move forward or what exactly does this mean. ​​

Answer 1

You can prove this via induction: Let $X_1, \ldots X_n$ be subsets of a universe $U$.

• Base case: $n = 2$: $$(X_1 \cup X_2)^C = X_1^C \cap X_2^C ,$$ which is true by De Morgan's Law. This can be easily proven through a Venn diagram.

• Assume that this equality is true for $n = k$, i.e. $$(X_1 \cup \cdots \cup X_k)^C = X_1^C \cap \cdots \cap X_k^C.$$

• Try to prove (considering the above equality as true) that the equality holds for $n = k+1$.

Answer 2

For any $x \in \mathcal{U}$, $x \in (X_1 \cup X_2 \cup \ldots \cup X_n)^C$ iff $x \not\in X_1 \cup X_2 \cup \ldots \cup X_n$ iff $x \not\in X_1$ and $x \not\in X_2$ and ... and $x \not\in X_n$ iff $x \in X_1^C$ and $x \in X_2^C$ and ... and $x \in X_n^C$ iff $x \in X_1^C \cap X_2^C \cap \ldots \cap X_n^C$. So $(X_1 \cup X_2 \cup \ldots \cup X_n)^C = X_1^C \cap X_2^C \cap \ldots \cap X_n^C$.

General Case:

In fact, there is no reason why you should stop at finite unions and intersections. Just assume $\mathcal{U}$ is a set. Then, given any family of subsets of your universe $\mathcal{U}$ (finite, countable or even uncountable), $\mathbb{X}$, and an $x \in \mathcal{U}$, $x \in \bigcup\{X:X\in\mathbb{X}\}$ iff for all $X \in \mathbb{X}$, $x \not\in X$ iff for all $X \in \mathbb{X}$, $x \in X^C$ iff $x \in \bigcap\{X^C:X\in\mathbb{X}\}$.