2
$\begingroup$

Can someone help me finish my solution?

Question: Show that there are sets $A_{ij}$ for $i,j$$\mathbb N$ such that for no countable $\space$H$\subseteq\mathbb N^{\mathbb N}$

$\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 H\Bigg\rbrace$..............(1)

Solution:

Assume for all sets $A_{ij}$ , H is countable such that equation (1) holds. As H is countable we can list its elements so we have $\space$

$h_0(0), h_0(1),h_0(2),...$$\space$

$h_1(0),h_1(1),h_1(2),...$$\space$

$h_2(0),h_2(1),h_2(2),...$$\space$

.

.

Now I define a function $g(i)$ as such so that it does not appear in the above list. So I go about using Cantor's diagonal argument and define as

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

So clearly $g(i)$ is not in the above list. I am now struggling to define $A_{ij}$ so that when I use definition of $g$ on $R.H.S$ I get $L.H.S=R.H.S$. Thus showing that indeed $g(i)$ satisfies equation (1) and yet not listed so it follows that 'there are sets $A_{ij}$ for which H has to be uncountable to satisfy equation (1)'

Can someone help me finish this solution? Thank

  • 0
    Are all the $A_{ij} \subseteq \mathbb{N}$?2011-10-24
  • 0
    Exact duplicate of [Set Theory- Generalized form of distributivity of unions over intersections](http://math.stackexchange.com/questions/75140/set-theory-generalized-form-of-distributivity-of-unions-over-intersections)2011-10-24
  • 0
    @RossMillikan Not necessarily. only $i,j\in \mathbb N$2011-10-24
  • 1
    @AustinMohr The equation is same but question is not same.2011-10-24

2 Answers 2

4

I don’t at the moment see a way to make your approach work, so I’m going to suggest a different one. Each of the sets $A_{ij}$ will be a subset of $\mathbb{N}^\mathbb{N}$. Specifically, try letting $$A_{ij} = \{f\in\mathbb{N}^\mathbb{N}:f(i)=j\}$$ for each $\langle i,j \rangle \in \mathbb{N}^2$. Note that with this choice of the $A_{ij}$, $$\bigcup_{i\in\mathbb{N}} A_{ih(i)}$$ is simply the set of functions from $\mathbb{N}$ to $\mathbb{N}$ that agree with $h$ on at least one element of $\mathbb{N}$.

Your lefthand side is then clearly empty, but if $H\subseteq \mathbb{N}^\mathbb{N}$ is countable, you shouldn’t have too much trouble finding a member of $\mathbb{N}^\mathbb{N}$ that belongs to the righthand side.

  • 0
    I understand your answer up to the point where you mention 'Your lefthand side is then clearly empty'... I didn't get the rest part though, "but if $H\subseteq \mathbb{N}^\mathbb{N}$ is countable, you shouldn’t have too much trouble finding a member of NN that belongs to the righthand side." I would be grateful if you could throw more light on it. Also I figured out how to define the $A_{ij}$ my way. Can you check if it makes sense to you..2011-10-25
  • 0
    @user18096: If $H$ is countable, let $H=\{h_n:n\in\mathbb{N}\}$ and define $f\in\mathbb{N}^\mathbb{N}$ by $f(n)=h_n(n)$. Then $(\forall h\in H)(\exists i\in\mathbb{N})[f\in A_{ih(i)}]$, so $f\in RHS$. (I can’t check your version of the $A_{ij}$, since you haven’t given it yet.)2011-10-25
  • 0
    where shall I write it ? I should edit my post or choose 'Answer your question'2011-10-25
  • 0
    @user18096: Go ahead and post it as an answer.2011-10-25
  • 0
    ok I will post it2011-10-25
1

If we define $A_{ij}$ as below then it will turn L.H.S into $\emptyset$ and $R.H.S$ empty for only function $g(i)$ but $\{x\}$ for any $h\in H$

$\forall i\in \mathbb N$

define $A_{ij}$ as below:-

$A_{i0}=\emptyset$ $\space$ if $g(i)=0$

$A_{i0}=\{x\}$ $\space$if $g(i)=1$

$A_{i1}=\emptyset$$\space$ if $g(i)=1$

$A_{i1}=\{x\}$ $\space$if $g(i)=0$

$A_{ij}=\{x\}$ $\space$ $\forall j>1$

Then

$\bigcup_{i=0}^\infty\Bigg(\bigcap_{j=0}^\infty{A_{ij}}\Bigg)=\emptyset$

$\bigcap\Bigg\lbrace\Bigg(\bigcup_{i=0}^\infty A_{ih(i)}\Bigg)\mid h\in H\Bigg\rbrace=\{x\}$

$\bigcap\Bigg\lbrace\Bigg(\bigcup_{i=0}^\infty A_{ih(i)}\Bigg)\mid h\in H \bigcup g\notin H\Bigg\rbrace=\emptyset$

Does it make sense?

  • 0
    This doesn’t work: you have to choose the $A_{ij}$ so that (1) is false for **every** countable $H\subseteq\mathbb{N}^\mathbb{N}$; you can’t pick a different collection of $A_{ij}$ for each $H$.2011-10-25
  • 0
    @BrianM.Scott Oh!! I see the point. I will go with your solution then. Thank you for clearing it up.2011-10-25