I'm pretty confident reasoning about expressions involving the following operations.

  • binary unions
  • binary intersections
  • complementation

However, I am less confident in my ability to reason about expressions that also involve:

  • indexed unions, and/or
  • indexed intersections.

What are the major laws that apply here?

To get the ball rolling, here's 5 that I know of.

Notation. Let $\Omega$ denote a set. Define $A^c = \Omega \setminus A$ for all $A \subseteq \Omega.$ Suppose furthermore that $X$ and $Y$ are functions $I,J \rightarrow \mathcal{P}(\Omega),$ where $I$ and $J$ are just some arbitrary index sets. We will use the $X_i$ in preference to $X(i)$. Lastly, define that the empty intersection equals $\Omega.$ That is, $$\bigcap_{i \in \emptyset} X_i = \Omega.$$

Then we have the following.

  1. If $\mathrm{ran}(X) \subseteq \mathrm{ran}(Y)$, then $$\bigcup_{i \in I}X_i \subseteq \bigcup_{j \in J}Y_j, \quad \bigcap_{i \in I}X_i \supseteq \bigcap_{j \in J}Y_j$$

  2. (Corollary). If $\mathrm{ran}(X) = \mathrm{ran}(Y),$ then $$\bigcup_{i \in I}X_i = \bigcup_{j \in J}Y_j, \quad \bigcap_{i \in I}X_i = \bigcap_{j \in J}Y_j$$

  3. Distributivity Laws. For all $A \in \mathcal{P}(\Omega)$ we have $$A \cap \bigcup_{i \in I}X_i = \bigcup_{i \in I}A \cap X_i,\quad A \cup \bigcap_{i \in I}X_i = \bigcap_{i \in I}A \cup X_i.$$

  4. De Morgan's Laws $$\left(\bigcup_{i \in I}X_i\right)^c = \bigcap_{i \in I}X_i^c,\quad \left(\bigcap_{i \in I}X_i\right)^c = \bigcup_{i \in I}X_i^c$$

  5. If $Z : K \rightarrow \mathcal{P}(\Omega)$ is a function with the property that $\mathrm{ran}(Z) = \mathrm{ran}(X) \cup \mathrm{ran}(Y)$, then

$$\bigcup_{k \in K}Z_k = \left(\bigcup_{i \in I}X_i\right) \cup \left(\bigcup_{j \in J}Y_j\right).$$

Okay, but what else? What major laws are missing from the above list?

  • $\begingroup$ What is the meaning of $\mathrm{ran}(f)$ $\endgroup$
    – hivert
    Jul 17 '13 at 10:59
  • 1
    $\begingroup$ @hivert, that would be the range of $f$, also known as the image. $\endgroup$ Jul 17 '13 at 11:05
  • 1
    $\begingroup$ This really seem like just the observation that functions induce homomorphisms of complete Boolean algebras of the power set of the domain and codomain. I also feel that this was asked before, even more so: there was a big list related to this topic. $\endgroup$
    – Asaf Karagila
    Jul 17 '13 at 11:12
  • $\begingroup$ @AsafKaragila, I'm not really getting what you're saying. I mean, yes, given a function $f : I \rightarrow \mathcal{P}(\Omega)$, we can obtain a new function $F : \mathcal{P}(I) \rightarrow \mathcal{P}^2(\Omega)$ in a natural way, and $F$ will have some structure-preserving tendencies, like it will definitely preserve unions. But, how does that give rise to the identities listed? $\endgroup$ Jul 17 '13 at 13:01

What about things like if $K\subset I$ then $\bigcup_{k \in K} X_k \subset \bigcup_{i \in I} X_i\,?$

  • $\begingroup$ Good one! I should have thought of that. $\endgroup$ Jul 17 '13 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.