Set theory - induction - countable sets

Question

need help with the following question:

Let $S \subseteq P(\mathbb N)$ be defined inductively so that:

• $\mathbb N \in S$
• for all$ ~ a \in \mathbb N \Longrightarrow \mathbb N\setminus\{a\}\in S$
• for all $A,B \in S \Longrightarrow A\cap B \in S$

Prove that if $A\subseteq \mathbb N~ $ and $~ \mathbb N $ \ $A$ is finite then $A \in S$

thanks!

Answer 1

You can prove it by induction on $\#(\mathbb{N}\setminus A)$:

• If $\#(\mathbb{N}\setminus A)=0$, then $A=\mathbb N$ and therefore $A\in S$.
• Let $n\in\mathbb N$ and suppose that $\#(\mathbb{N}\setminus A)=n\implies A\in S$. Then, if $\#(\mathbb{N}\setminus A)=n+1$, take $a\in(\mathbb{N}\setminus A)$ and let $A^\star=A\cup\{a\}$. Then $\#(\mathbb{N}\setminus A^\star)=n$ and therefore $A^\star\in S$. So,$$A=A^\star\cap(\mathbb{N}\setminus\{a\})\in S$$

Answer 2

If $B\subset\mathbb N$ is finite, then there exists a unique $n\in\mathbb N$, such that $|A|=n$ and a bijection $f:\{0,1,2,\ldots,n-1\}\to A$.

In Set Theory $0=\varnothing$ and $n=\{0,1,\ldots,n-1\}$.

Let $$ J=\{k\in n: f[k]\in S\} $$
We want to show that $J=n$.

Clearly, $f[0]=\mathbb N\in S$. If $J\ne n$, then there exists a least $m\le n$, such that $f[m]\not\in S$. But this also means that $m>0$ and $f[m-1]\in S$

Note that $$ f[m]=f[m-1]\cup\{f(m)\} $$ and $$ \mathbb N\setminus f[m]=(\mathbb N\setminus f[m-1])\cap(\mathbb N\setminus \{f(m)\}) $$ But $\mathbb N\setminus f[m-1],\,\mathbb N\setminus \{f(m)\}\in S$, and thus $\mathbb N\setminus f[m]\in S$. Contradiction.