# Thread: Power Set of N-Intersection of finite subsets of N

1. ## Power Set of N-Intersection of infinitely many finite subsets of N

Hello everyone,
This is a problem I'm having a hard time solving:

Let $\displaystyle P(\mathbb{N})$= the power set of $\displaystyle \mathbb{N}$ and for every natural number, n, $\displaystyle P(\mathbb{N}_n)$ be the power set of $\displaystyle \mathbb{N}_n$ which is a finite subset of $\displaystyle \mathbb{N}: \mathbb{N}_n=\left \{ 1,2,3,...,n \right \}$.

Now, if for every n, $\displaystyle A_n=P(\mathbb{N})-P(\mathbb{N}_n)$,

what can be said about $\displaystyle \bigcap_{n=1}^{\infty }A_n?$

Is that an infinite subset of $\displaystyle \mathbb{N}$?

2. ## Re: Power Set of N-Intersection of infinitely many finite subsets of N

Originally Posted by Neutriiino
This is a problem I'm having a hard time solving:
Let $\displaystyle P(\mathbb{N})$= the power set of $\displaystyle \mathbb{N}$ and for every natural number, n, $\displaystyle P(\mathbb{N}_n)$ be the power set of $\displaystyle \mathbb{N}_n$ which is a finite subset of $\displaystyle \mathbb{N}: \mathbb{N}_n=\left \{ 1,2,3,...,n \right \}$.
Now, if for every n, $\displaystyle A_n=P(\mathbb{N})-P(\mathbb{N}_n)$,
what can be said about $\displaystyle \bigcap_{n=1}^{\infty }A_n?$
Is that an infinite subset of $\displaystyle \mathbb{N}$?
We realize that this is your first posting. Nonetheless, it is best if you show some work so that we know where to begin.
If $\displaystyle F$ is a finite subset of $\displaystyle \mathbb{N}$ is it possible for $\displaystyle F\in\bigcap_{n=1}^{\infty }A_n~?$

If $\displaystyle F$ is an infinite subset of $\displaystyle \mathbb{N}$ must for $\displaystyle F\in\bigcap_{n=1}^{\infty }A_n~?$

Tell us what you think?

3. ## Re: Power Set of N-Intersection of finite subsets of N

Note that N is an element of P(N), but cannot be an element of any P(Nn) (since these sets are all finite). Hence N is in every An, and thus in the intersection.

The same exact logic hold for N - S, where S is any finite subset of N. Thus any co-finite subset of N is in the infinite intersection. Since we obtain a co-finite subset of N from any finite set S, simply by taking N - S, there are at least as many co-finite subsets of N, as there are finite subsets of N. Hence the intersection of all the An is indeed infinite.

4. ## Re: Power Set of N-Intersection of finite subsets of N

Thanks Deveno, I got it!
Thank you too, Plato, for your rather Socratic method of instruction through questions.
well, here we go:

If F is a finite subset of $\displaystyle \mathbb{N}$, then $\displaystyle F\subseteq \mathbb{N}_n_m_a_x$, where nmax is the largest number in F. hence $\displaystyle F\notin P(\mathbb{N})-P(\mathbb{N}_n_m_a_x)$, $\displaystyle F\notin A_n$ (for any value of n)

If G is an infinite subset of N, for every n, $\displaystyle G\notin P(\mathbb{N}_n)$, hence $\displaystyle G\in P(\mathbb{N})-P(\mathbb{N}_n)$.
Right?
I found this in a previously held exam in our department, and now I'm wondering where I can find more problems like this.
Thanks, once again.