[Math] Do De Morgan’s laws hold for arbitrary infinite expressions with union and intersection

elementary-set-theory

It can be shown that De Morgan's laws hold for infinite union and infinite intersection:

$$ \left( \bigcup_{i \in I} A_i \right)^c = \bigcap_{i \in I} A_i^c \tag{1} $$
$$ \left( \bigcap_{i \in I} A_i \right)^c = \bigcup_{i \in I} A_i^c \tag{2} $$

even if the index set $I$ is uncountable. Here superscript $c$ denotes complement w.r.t. universe $U$.

Now consider an arbitrary expression of the form

$$ A_1 \cup A_2 \cap A_3 \cup A_4 \cup … $$

I will denote union with $0$ and intersection with $1$ so the form of above expression looks like $0100…$

Some such expressions can be converted to laws $(1), (2)$, for example, complement of $101010101…$ simply means

$$ \left( \bigcup_{i \in \mathbb{N}} (A_{2i-1} \cap A_{2i}) \right)^c = \bigcap_{i \in \mathbb{N}} (A_{2i-1} \cap A_{2i})^c = \bigcap_{i \in \mathbb{N}} (A_{2i-1}^c \cup A_{2i}^c) $$

But what about other examples like $011011100101110111…$ (the string contains all binary numbers in order)? Can we rewrite complements of all such expressions in terms of $A_i^c$?

Edit: Assume that $\cap$ takes precedence over $\cup$, i.e., $A \cap B \cup C = (A \cap B) \cup C$

Best Answer

I believe we can deal with any infinite (including uncountable) string $(A_i)_{i\in I}$ in just two applications of De Morgan's laws. In preparation, looking at just $(A_i)$ and not yet taking the complement: first we deal with the intersections by defining $B_i=\bigcap_{s\le i\le f}A_i$ for any $i\in I$ that's included within a string of consecutive 1s starting at position $s$ and ending at $f$, and $B_i=A_i$ if $i\in I$ isn't included in such a string. Secondly when taking the union $\bigcup_{i\in I}B_i$ we get a set equal to the original union/intersection chain that we wanted.

Now, taking the complement $(\bigcup_{i\in I}B_i)^c$, this is equal to $\bigcap_{i\in I}B_i^c$ (De Morgan application), and we may apply De Morgan's law again casewise to each $B_i$.

Related Question