Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What is the meaning of $\mathrm{ran}(f)$ –  hivert Jul 17 '13 at 10:59
1  
@hivert, that would be the range of $f$, also known as the image. –  goblin Jul 17 '13 at 11:05
1  
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. –  Asaf Karagila Jul 17 '13 at 11:12
    
@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? –  goblin Jul 17 '13 at 13:01

1 Answer 1

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

share|improve this answer
    
Good one! I should have thought of that. –  goblin Jul 17 '13 at 13:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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