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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Oct 23 '11 at 20:10
  • $\begingroup$ Thank Arturo for correcting my mistake. $\endgroup$ – user18096 Oct 24 '11 at 13:04

We consider the equation

$\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.


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.