# Set Theory- Uncountable sets

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 - Are all the A_{ij} \subseteq \mathbb{N}? – Ross Millikan Oct 24 '11 at 16:56 – Austin Mohr Oct 24 '11 at 17:42 @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 ## 2 Answers 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. - 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\} \spaceif 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?

-
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