# Set Theory- Generalized form of distributivity of unions over intersections

I am trying to solve this question and stuck in the way. Can someone drop me some hint which direction to go?

Question: Show that if $A_{ij}$ for $i$ ,$j$ $\in$ $\mathbb{N}$ are sets then

$\bigcup_{i=0}^\infty\Bigg(\bigcap_{j=0}^\infty{A_{ij}}\Bigg)$ = $\bigcap\Bigg\lbrace\Bigg(\bigcup_{i=0}^\infty A_{ih(i)}\Bigg)\mid h\in \mathbb N^{\mathbb N}\Bigg\rbrace$ .

Solution: I am trying to prove it by 'Extensionality property of sets'. So if I show that for some arbitrary element $x$,

$x\in L.H.S$ $\iff$ $x\in R.H.S$ then I am done with it.

So on $L.H.S$ I have

$x\in\bigcup_{i=0}^\infty\Bigg(\bigcap_{j=0}^\infty{A_{ij}}\Bigg)\iff x \in \bigcap_{j=0}^\infty{A_{ij}}$ , for some $i \in \mathbb N$.

Now at this point I am struggling to write the set of functions from $\mathbb N\to\mathbb N$ so that I can convert $L.H.S$ to the $R.H.S$.

My efforts so far is given below:- I expanded the $L.H.S$ to get an idea of functions required.

$\bigg(A_{00} \cap A_{01} \cap A_{02} \cap ...\bigg) \cup \bigg( A_{10} \cap A_{11} \cap A_{12} \cap ... \bigg) \cup \bigg( A_{20} \cap A_{21} \cap A_{22} \cap ...\bigg) \cup ...$

So I get that I need following sets of functions:

$h_{1}(i)$=$0$ $\space$ for all $i$ $\in$ $\mathbb N$

So that we get

$\bigg(A_{0h_1(0)} \cup A_{1h_1(1)} \cup A_{2h_1(2)} \cup...\bigg)$ $\mapsto$ $\bigg(A_{00} \cup A_{10} \cup A_{20} \cup ...\bigg)$

That is, I am picking first set from each disjunct to make one conjunct required on $R.H.S$. I can then make $h_{2}(i)=1$ for all $i\in\mathbb N$ , $h_{3}(i)=2$ for all $i\in\mathbb N$ and so on ... So this makes one type of set of functions but we are still not finished as there are more combinations possible..

$g_{1}(i) = \begin{cases} 0 & \text{if } i = 0 \\ 1 & \text{if } i \neq 0 \end{cases}$

So that we get ,

$\bigg(A_{0g_1(0)} \cup A_{1g_1(1)} \cup A_{2g_1(2)} \cup...\bigg)$ $\mapsto$ $\bigg(A_{00} \cup A_{11} \cup A_{21} \cup ...\bigg)$ and so on we can define

$g_{2}(i) = \begin{cases} 0 & \text{if } i = 0 \\ 2 & \text{if } i \neq 0 \end{cases}$ and

$g_{3}(i) = \begin{cases} 0 & \text{if } i = 0 \\ 3 & \text{if } i \neq 0 \end{cases}$

and so on...

We still need to define lots of more functions for other possible combinations...

I don't know how to convert my ideas into $R.H.S$... Any hint please?

• Note: This is not really De Morgan's Law! This is distributivity of unions under intersections. De Morgan's Laws are about complements of unions and complements of intersections. – Arturo Magidin Oct 23 '11 at 20:10
• Thank Arturo for correcting my mistake. – user18096 Oct 24 '11 at 13:04

$\bigcup_{{i=0}}^\infty\left(\bigcap_{{j=0}}^\infty A_{{ij}}\right)=\bigcap_{{h:\mathbb N\to\mathbb N}}\left(\bigcup_{{i=0}}^\infty A_{{ih(i)}}\right)$
Suppose $x$ is in the LHS, then for some $i$, $x\in A_{ij}$ for all $j$. In particular, $x\in A_{ih(i)}$ for all $h:\mathbb N\to\mathbb N$. Hence $x$ is in the RHS.
Now suppose $x$ is not in the LHS.
Then for all $i$ there is $j$ such that $x\not\in A_{ij}$. Define $h(i)$ as the least such $j$. Now $x\not\in\bigcup_{i=0}^\infty A_{ih(i)}$. Hence $x$ is not in the RHS.
Since this holds for all sets $x$, we have the equality.