# Countable and Uncountable subset of $P(\omega)$

Let $\emptyset \not = A \subset P(\omega)$ , find a set $B \subset A$ such that :

1) $B$ is countable

2) $\bigcap B = \bigcap A$

3) $\bigcup B = \bigcup A$

If $B$ was a set that is not necessarily subset of $A$ then i could just take $B = \{0,1,2,3,\cdots\} \cup \{\omega\}$

Easy to show that $B$ is countable and then reduce $B$ till we have that $\bigcap B= \bigcap A$ and $\bigcup B = \bigcup A$

So this condition $B \subset A$ that is making the proof a problem for me.

• Try starting with an arbitrary countable subset of A and making modifications from there. – DaveP Mar 29 '18 at 10:23
• @DaveP if $A$ is not countable, does this means that $\bigcup A = \omega$ ? – Ahmad Mar 29 '18 at 10:31
• No, consider $A$ as the subsets of $\omega$ excluding $0$, then it is uncountable and $\bigcup A = \omega \setminus 0$ – DaveP Mar 29 '18 at 10:37
• With $B$ countable, do you mean it has to be infinite? If yes, it seems to me impossible: for example, take $A=\{\{0\}\}$, then $\bigcup A=\{0\}$ and no infinite $B$ would have $\bigcup B = \{0\}$. If $B$ can be finite, then, $$B=\{\bigcap A,\bigcup A\}$$ seems to work. – amrsa Mar 29 '18 at 11:12
• @amrsa $B$ countable means that $B$ is finite or $|B| = \aleph_0$, and $B \subset A$ so $\bigcap A , \bigcup A$ might not be in $A$. – Ahmad Mar 29 '18 at 11:19

You need to use the axiom of choice here, since otherwise it is consistent that there is a set $A$ which is infinite, but has no uncountably infinite subset.

But let's try to break this down to just one problem. Let's say that you only wanted to have a countable subset $B$ such that $\bigcup A=\bigcup B$. How would you go about doing that? Well, for every $n\in\bigcup A$, choose some $A_n\in A$ such that $n\in A$. Now take $B=\{A_n\mid n\in\bigcup A\}$, and we immediately have that:

1. $B\subseteq A$,
2. $B$ is countable, and
3. $\bigcup A=\bigcup B$.

The last one is true because every $n$ in that union was forced into the union of $B$ by some witness that it is at all in the union of $A$.

Now think about the way this works, try to get the same proof with $\bigcap$ instead of $\bigcup$, and then solving your problem should be visible.

• Thanks, but since AC is like last resort in our course, is there a proof that does not contain AC, to tell the truth i thought of a proof containing AC, granted not elegant as your own but still ... – Ahmad Mar 29 '18 at 12:12
• This is a "nearly harmless" use of choice, I would be surprised if many people would notice it. Who composed this question? – Asaf Karagila Mar 29 '18 at 12:16
• Thanks, last thing : i check your idea and its very good, so i have now to sets $B,C$ and $B,C \subset A$ and $B,C$ are countable and $\bigcup B = \bigcup A$ and $\bigcap C = \bigcap A$ but how to end up with one set from $B,C$, i think that $D = B \cup C$ will work ,but not sure ?! – Ahmad Mar 29 '18 at 12:25
• Well, you can just check that $B\cup C$ works. Even if it's not, checking if it might be is a great use of your time. – Asaf Karagila Mar 29 '18 at 12:27