The natural numbers that satisfy a quantifier-free formula are either finitely many, or all the natural numbers except finitely many?

Question

This is an exercise from Chiswell & Hodges's Mathematical Logic. It suggests that it should be solved by an induction on the complexity, but I still have no clue...

Let $\phi(x)$ be a quantifier-free formula LR($\sigma_{arith}$). Show that the set of natural numbers that satisfy $\phi$ in $\mathbb{N}$ consists of either finitely many numbers, or all the natural numbers except finitely many.

(LR: language of relations)

Any thoughts would be appreciated!

Answer 1

The quantifier-free formulas are built out of the atomic formulas via Boolean combinations - $\vee, \wedge, \neg$. The complexity you want to induct on is the complexity in this sense: how many "steps" does it take to build a given quantifier-free formula from atomics? For example, to build the formula $$(*)\quad(x<1)\vee \neg(x=1+1+1+1)$$ I basically need three pieces (i.e. proper subformulas): "$x<1$", "$x=1+1+1+1$", and "$\neg(x=1+1+1+1)$".

Now let's think about the set this formula carves out.

• The atomic formula $x=1+1+1+1$ carves out the set $\{4\}$, which is finite.

• The formula $\neg (x=1+1+1+1)$ carves out $\mathbb{N}\setminus\{4\}$ - the complement of a finite set, so cofinite.

• The atomic formula $x<1$ carves out the finite set $\{0\}$.

• Finally, the whole formula $(*)$ carves out $\mathbb{N}\setminus\{4\}$ - the union of a cofinite set and a finite set, which is cofinite.

This should show that basically, what you want to prove is:

Every set you can form by taking finite and cofinite sets and applying union, intersection, and complement, is either finite or cofinite.

Hopefully it's clear how to frame the induction now! (Of course, we're omitting the base case here: you need to show that every atomic formula defines a finite or cofinite set!)