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

• Jul 21st 2012, 07:26 AM
Neutriiino
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 $P(\mathbb{N})$= the power set of $\mathbb{N}$ and for every natural number, n, $P(\mathbb{N}_n)$ be the power set of $\mathbb{N}_n$ which is a finite subset of $\mathbb{N}: \mathbb{N}_n=\left \{ 1,2,3,...,n \right \}$.

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

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

Is that an infinite subset of $\mathbb{N}$?
• Jul 21st 2012, 08:26 AM
Plato
Re: Power Set of N-Intersection of infinitely many finite subsets of N
Quote:

Originally Posted by Neutriiino
This is a problem I'm having a hard time solving:
Let $P(\mathbb{N})$= the power set of $\mathbb{N}$ and for every natural number, n, $P(\mathbb{N}_n)$ be the power set of $\mathbb{N}_n$ which is a finite subset of $\mathbb{N}: \mathbb{N}_n=\left \{ 1,2,3,...,n \right \}$.
Now, if for every n, $A_n=P(\mathbb{N})-P(\mathbb{N}_n)$,
what can be said about $\bigcap_{n=1}^{\infty }A_n?$
Is that an infinite subset of $\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 $F$ is a finite subset of $\mathbb{N}$ is it possible for $F\in\bigcap_{n=1}^{\infty }A_n~?$

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

Tell us what you think?
• Jul 21st 2012, 08:29 AM
Deveno
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.
• Jul 21st 2012, 11:05 AM
Neutriiino
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 $\mathbb{N}$, then $F\subseteq \mathbb{N}_n_m_a_x$, where nmax is the largest number in F. hence $F\notin P(\mathbb{N})-P(\mathbb{N}_n_m_a_x)$, $F\notin A_n$ (for any value of n)

If G is an infinite subset of N, for every n, $G\notin P(\mathbb{N}_n)$, hence $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.