How to prove that $N\setminus A$ is finite?

Question

$A \subseteq \mathcal{R}(N)$ and given that (by inductive definition):

1. $N ∈ S$.
2. If $a \in R$, then $R \setminus \{a\} \in A$.

I need to prove that for each $A \in S$, $N\setminus A$ is finite. How can I prove this formally?

Answer 1

I'm assuming that you mean that $S$ is the smallest subset of $\mathcal P(\Bbb N)$ satisfying:

1. $\Bbb N\in S$,
2. if $A,B\in S$, then $A\cap B\in S$,
3. if $a\in\Bbb N$, then $\Bbb N\setminus\{a\}\in S$.

There are two ways to approach this:

1. Show that $\{A\subseteq\Bbb N\mid\Bbb N\setminus A\text{ is finite}\}$ satisfies all three properties, and therefore $S$ is a subset of this collection.

2. Show that for every $A\in S$ there are finitely many $a_0,\ldots,a_{n-1}\in\Bbb N$ such that $A=\bigcap_{i<n}\Bbb N\setminus\{a_i\}$, and then apply DeMorgan's law. Or, similarly, show that $S$ can be written as the union of $S_n$'s such that $S_n$ are those given by the intersection of at most $n$ complements of singletons.

You can note that both are essentially the same argument, presented in different ways. This is because defining a set via "closure under operations" can be defined as either the intersection of all sets closed an operation, or as a union of sets which are "increasingly more closed under the operation".

---

Note that if you don't mean that $S$ is the smallest such set, but just that "it has these three properties", then the claim is false. $\cal P(\Bbb N)$ also satisfies all three properties, but $\varnothing$ has an infinite complement.