Set of Strictly Negative Integers is Primitive Recursive

Theorem

Let $N \subseteq \N$ be the set of all $n \in \N$ such that:

$n$ codes an integer $k$ such that $k < 0$.

Then $N$ is a primitive recursive set.

Proof

By Set of Strictly Positive Integers is Primitive Recursive:

$P = \set {n \in \N : k > 0}$

is primitive recursive.

By Complement of Primitive Recursive Set:

$P^c = \set {n \in \N : k \le 0}$

is primitive recursive.

It is clear that:

$N = P^c \setminus \set {n \in \N : k = 0}$

By Set Difference as Intersection with Relative Complement:

$N = P^c \cap \relcomp \N {\set {n \in \N : k = 0}}$

By:

• Intersection of Primitive Recursive Sets
• Complement of Primitive Recursive Set

we only need to show that:

$\set {n \in \N : k = 0}$

is primitive recursive.

As $k = 0 \le 0$:

$n = - 2 k = 0$

Therefore:

$\set {n \in \N : k = 0} = \set 0$

which is primitive recursive by:

Set Containing Only Zero is Primitive Recursive

$\blacksquare$