Infinitary union combined with infinitary intersection

[bert2612]

I am struggling with combining infinite unions with infinite intersections, the problem i have is to show that, for Sets A_ij where i,j $\in$N (N=Natural Numbers)
∞...∞
$\bigcup$ ( $\bigcap$ A_ij)
i=0 j=0


is equal to
...∞
$\bigcap${($\bigcup$A_ih(i):h$\in$N^N}
... i=0

please could someone point me in the right direction,
I can show that

∞...∞
$\bigcup$ ( $\bigcap$ A_ij)
i=0 j=0

is a subset of
∞...∞
$\bigcap$ ( $\bigcup$ A_ij)
i=0 j=0

however i am struggling with the function h(i) used in the above question to make the two sets equal
Thanks!

 

[AKG]

If I'm reading that right, what you want to show is:

$$\bigcup _{i=0}^{\infty} \left(\bigcap_{j=0}^{\infty} A_{ij}\right) = \bigcap\left\{\bigcup_{i=0}^{\infty}A_{ih(i)}\ :\ h \in \mathbb{N}^{\mathbb{N}}\right\}$$

To show two sets are equal, you show that they are subsets of one another. To show something is a subset of something else, you take an arbitrary element of the first thing and show it belongs to the second thing: "$x \in$ one set $\Longrightarrow x \in$ other set." Now the questions are: (a) how do I use the assumption that $x$ is in some set, and (b) how do I prove that $x$ is in some set? For both question, the answer is to look at what the defining property of the set is. I.e. if $A = \{x : \phi(x)\}$, then "$x \in A$" is equivalent to "$\phi(x)$."

So to get you started, the first half of what you want to do is:

Assume: $\exists i \in \mathbb{N}\ \forall j \in \mathbb{N}\ x \in A_{ij}$

and Deduce: $\forall h \in \mathbb{N}^{\mathbb{N}}\ \exists i \in \mathbb{N}\ x \in A_{ih(i)}$

How do you deduce something of the form of what you want to deduce? It starts with a $\forall$, so you say, "let $h\in \mathbb{N}^{\mathbb{N}}$" be arbitrary. Then your goal is to find an $i \in \mathbb{N}$ such that $x\in A_{ih(i)}$. Given such an $h$, which $i$ should you choose? Well, look at your assumption to see if it gives you any suggestions: $\exists i \in \mathbb{N} \dots$. There's only one thing you can do with such an assumption: instantiate it. So let $i^\ast$ be such that $\forall j \in \mathbb{N}\ x\in A_{i^\ast j}$. Does this $i^\ast$ work for your purpose? You need to check, will $x \in A_{i^\ast h(i^\ast)}$? Yes, by choice of $i^\ast$, $x \in A_{i^\ast j}$ for all $j$, in particular for $j = h(i^\ast)$. So you're done (one half of the problem).

Normally I don't like to provide solutions, but I have given you half the solution here. What you should take away from this is that there is essentially no thinking involved, you just have to unpack the definitions and think about the standard ways to do things like:

• Prove two sets are equal
• Prove one set is a subset of another
• Prove an implication
• Use an assumption that has an existential quantifier
• How to "update" what your given assumption is once you've eliminated an existential quantifier via an instantiation
• Use an assumption that has a universal quantifier
• Deal with a conclusion that has a universal quantifier
• How to "update" what your goal is once you've eliminated a universal quantifier from the desired conculsion via a "let ... be arbitrary" type of statement.
• Deal with a conclusion that has an existential quantifier
• etc.

Just as everyone needs to learn basic, purely mechanical things like adding, subtracting, multiplying, and dividing so they can use these tools creatively to do some actual useful and interesting computations, one needs to learn the basic mechanics of dealing with sets, quantifiers, and logical connectives in order to do interesting, creative mathematics. The problem here is purely mechanical, so don't over think it. Rather, try to approach it very analytically and logically, break things down into definitions and routine steps and at some point you will just fly through them.

 

[bert2612]

this helped a lot, thank you