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?
Best Answer
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.