First order logic: structural induction

Question

I am having trouble trying to prove the following.

$\mathcal{S}\subset \mathcal{P}(\mathbb{N})$ is the minimal set that satisfies the following:

1. $\mathbb{N} ∈ \mathcal{S} $

2. for every $a \in \mathbb{N}$, $\mathbb{N} \setminus \{a\} ∈ \mathcal{S}$

3. for every $A,B \in \mathcal{S}$, $A\cap B \in \mathcal{S}$

prove that $\mathcal{S}$ is the set of all co-finite sets of $\mathbb{N}$

As I understand, this is structural induction, though I don't really know how to approach it. I would appreciate both an explanation of how to use structural induction in general and a solution to this question.

Edit: $\mathbb{N}$ is the set of natural numbers

Answer 1

$\newcommand{\N}{\mathbb{N}}$ Given a finite set $X \subseteq \N$, we can induct on $|X|$ that $\N \setminus X \in S$ (which proves that all cofinite sets lie in $S$). The case is trivial for $|X| = 0$, as by hypothesis $\N \in S$. The second condition also proves the case for $|X| = 1$. Now suppose for all $X \subseteq \N$ such that $|X| = n$, we have $\N \setminus X \in S$. Let $a_1,a_2,\dots,a_n,a_{n+1} \in \N$. Then by inductive hypothesis, we have that: $$ A = \N \setminus \{a_1,a_2,\dots,a_n\} \in S \\ B = \N \setminus \{a_2,\dots,a_n,a_{n+1}\} \in S $$ Therefore, by the third condition: $$ \N \setminus \{a_1,a_2,\dots,a_n,a_{n+1}\} = A \cap B \in S $$ Since $a_1,\dots,a_{n+1}$ are arbitrary, the induction is complete, so all cofinite sets lie in $\N$. Since $S$ is minimal, and the set of all cofinite sets satisfy the three conditions, $S$ must be precisely the set of all cofinite sets.

Answer 2

Let $\mathcal{C}$ be a set of all co-finite sets of $\mathbb{N}$. Then clearly elements in $S$ satisfies 1. and 2. condition by the definition of cofinitnes.

Let also $A,B\in \mathcal{C}$, then $A'$ and $B'$ are finite so $A'\cap B'$ is finite so $A\cap B\in \mathcal{C}$, so clearly $\mathcal{C}$ satisfies all conditions and thus $$\mathcal{C}\subseteq \mathcal{S}$$

Now, since $S$ is minimal we have $\mathcal{S}=\mathcal{C}$.