Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)


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$





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

share|cite|improve this question
Are all the $A_{ij} \subseteq \mathbb{N}$? – Ross Millikan Oct 24 '11 at 16:56
@RossMillikan Not necessarily. only $i,j\in \mathbb N$ – user18096 Oct 24 '11 at 17:55
@AustinMohr The equation is same but question is not same. – user18096 Oct 24 '11 at 17:56
up vote 3 down vote accepted

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.

share|cite|improve this answer
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.. – user18096 Oct 25 '11 at 17:51
@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.) – Brian M. Scott Oct 25 '11 at 18:01
where shall I write it ? I should edit my post or choose 'Answer your question' – user18096 Oct 25 '11 at 18:07
@user18096: Go ahead and post it as an answer. – Brian M. Scott Oct 25 '11 at 18:11
ok I will post it – user18096 Oct 25 '11 at 18:14

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$



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

share|cite|improve this answer
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$. – Brian M. Scott Oct 25 '11 at 18:46
@BrianM.Scott Oh!! I see the point. I will go with your solution then. Thank you for clearing it up. – user18096 Oct 25 '11 at 18:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.