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

  • 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
    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
    @BrianM.Scott Oh!! I see the point. I will go with your solution then. Thank you for clearing it up.2011-10-25