examples of primitive recursive predicates

In this entry, we give some examples of primitive recursive predicates. In particular, we will show that the predicate “x is a prime number” is primitive recursive.

In the examples, we use $\mathrm{\Phi }(𝒙)$ to indicate a predicate (over the natural numbers $\mathbb{N}$). First, two very simple examples:

1. $\mathrm{\Phi }(x)$ given by “$x=n$” for a fixed $n\in \mathbb{N}$ is primitive recursive. To see this, note that the set associated with $\mathrm{\Phi }$ is $\{n\}$, and its associated characteristic function is primitive recursive by example 3(l) in this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions). As a result, $\mathrm{\Phi }$ is primitive recursive.

2. $\mathrm{\Phi }(x,y)$ given by “$x\le y$” is primitive recursive. The associated set is $\{(x,y)\mid x\le y\}$ whose characteristic function is $\mathrm{sgn}(s(y)\dot{-}x)$, which is primitive recursive.

Before exhibiting more examples, we prove some basic facts about primitive recursive predicates:

Proposition 1.

If $\mathrm{\Phi }$ and $\mathrm{\Theta }$ are primitive recursive predicates, then so are $\mathrm{\neg }\mathit{}\mathrm{\Phi }$ (negation), $\mathrm{\Phi }\mathrm{\vee }\mathrm{\Theta }$ (disjunction), and $\mathrm{\Phi }\mathrm{\wedge }\mathrm{\Theta }$ (conjunction).

Proof.

Let $S,T$ be the sets associated with the predicates $\mathrm{\Phi }$ and $\mathrm{\Theta }$. We may assume that $S,T\subseteq {\mathbb{N}}^k$ for some positive integer $k$. Let $c_S$ and $c_T$ be the associated characteristic functions.

First, $1\dot{-}{c}_S$ is the characteristic function of ${\mathbb{N}}^k-S$, which is the associated set of the predicate $\mathrm{\neg }\mathrm{\Phi }$. Since $1\dot{-}{c}_S$ is primitive recursive, so is $\mathrm{\neg }\mathrm{\Phi }$.

Next, $\mathrm{mult}(C_S,C_T)$ is the characteristic function of $S\cap T$, which is the associated set of the predicate $\mathrm{\Phi }\wedge \mathrm{\Theta }$. Since $\mathrm{mult}(C_S,C_T)$ is primitive recursive, so is $\mathrm{\Phi }\wedge \mathrm{\Theta }$.

Finally, the set associated with $\mathrm{\Phi }\vee \mathrm{\Theta }$ is $S\cup T$, which is ${\mathbb{N}}^k-(({\mathbb{N}}^k-S)\cap ({\mathbb{N}}^k-T))$, which is primitive recursive. Hence $\mathrm{\Phi }\vee \mathrm{\Theta }$ is primitive recursive as well.∎

In short, primitive recursiveness is preserved under Boolean operations on predicates. By induction, we also see primitive recursiveness is preserved under finite disjunction and finite conjunction.

Using this fact, we list three more examples:

1. the predicate “$x=y$” is primitive recursive, since it is the conjunction of primitive recursive predicates “$x\le y$” and “$y\le x$”.

2. the predicate “” is primitive recursive, since it is the conjunction “$y\le x$” and “$\mathrm{\neg }(x=y)$”, both of which are primitive recursive.

3. the predicate “$x\in S$”, where $S$ is a fixed finite set, is primitive recursive, as it is the disjunction of primitive predicates of the form “$x=n$”, where $n$ ranges over $S$. Since the disjunction operation is finitary, “$x\in S$” is primitive recursive also.

Here’s another useful fact about primitive recursive predicates:

Proposition 2.

If $\mathrm{\Phi }\mathit{}\mathrm{(}{x}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_m\mathrm{)}$ is primitive recursive, so is $\mathrm{\Theta }\mathit{}\mathrm{(}{x}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n\mathrm{)}$, defined by simultaneous substitution of the variables $x_i$ in $\mathrm{\Phi }$ by $n$-ary primitive recursive functions $f_i$:

$$\mathrm{\Theta }(x_1,\mathrm{\dots },x_n):=\mathrm{\Phi }(f_1(x_1,\mathrm{\dots },x_n),\mathrm{\dots },f_m(x_1,\mathrm{\dots },x_n)).$$

Proof.

Let $c_{\mathrm{\Phi }}$ be the characteristic function of (the set associated with) $\mathrm{\Phi }$, then

$$c_{\mathrm{\Phi }}(f_1(x_1,\mathrm{\dots },x_n),\mathrm{\dots },f_m(x_1,\mathrm{\dots },x_n))$$

is $c_{\mathrm{\Theta }}$, the characteristic function of $\mathrm{\Theta }$. Since $c_{\mathrm{\Phi }}$, $f_i$ are primitive recursive, $c_{\mathrm{\Theta }}$, obtained by functional composition, and hence $\mathrm{\Theta }$, are primitive recursive too.∎

Let us list two more examples:

1. the predicate “$xy\ne z$” is primitive recursive.

2. the predicate “” is primitive recursive.

Finite disjunctions and finite conjunctions of predicates can be thought of as special cases of bounded quantification (http://planetmath.org/BoundedQuantifier) on predicates. In view of this, we have the following facts:

Proposition 3.

If $\mathrm{\Phi }\mathit{}\mathrm{(}𝐱\mathrm{,}y\mathrm{)}$ is primitive recursive, so are

$$\mathrm{\Theta }(𝒙,y):=\forall z\le y\mathrm{\Phi }(𝒙,z)\mathit{\hspace{1em}\hspace{1em}}\text{𝑎𝑛𝑑}\mathit{\hspace{1em}\hspace{1em}}\mathrm{\Psi }(𝒙,y):=\exists z\le y\mathrm{\Phi }(𝒙,z).$$

Proof.

The set associated with $\mathrm{\Theta }(𝒙,y)$ is $\{(𝒙,y)\mid \text{ for all }z\le y,\mathrm{\Phi }(𝒙,z)\}$, which is just

$$S:=\{(𝒙,y)\mid \mathrm{\Phi }(𝒙,0)\}\cap \{(𝒙,y)\mid \mathrm{\Phi }(𝒙,1)\}\cap \mathrm{\cdots }\cap \{(𝒙,y)\mid \mathrm{\Phi }(𝒙,y)\}$$

For each fixed $i$, let ${\mathrm{\Phi }}_i(𝒙):=\mathrm{\Phi }(𝒙,i)$. Then by proposition 2, ${\mathrm{\Phi }}_i$ is primitive recursive. Let $c_i$ be the characteristic function of ${\mathrm{\Phi }}_i$, and $d$ the function such that $d(𝒙,i)$ is $c_i(𝒙)$ if $i\in \{0,\mathrm{\dots },n\}$, and $0$ otherwise. So $d$ is primitive recursive (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions)). Now, define function $c$ by

$$c(𝒙,y):=\prod _{i=0}^{y}d(𝒙,i).$$

So $1=d(𝒙,i)=c_i(𝒙)$ iff ${\mathrm{\Phi }}_i(𝒙)$ iff $(𝒙,i)\in \{(𝒙,i)\mid \mathrm{\Phi }(𝒙,i)\}$ iff $(𝒙,y)\in \{(𝒙,y)\mid \mathrm{\Phi }(𝒙,i)\}$.

As a result, $1=c(𝒙,y)$ iff $(𝒙,y)\in \{(𝒙,y)\mid \mathrm{\Phi }(𝒙,i)\}$ for all $i\in \{0,\mathrm{\dots },y\}$ iff $(𝒙,y)\in S$. In other words, $c$ is the characteristic function of $S$. Since $c$ is obtained from $d$ by bounded product, $c$ is primitive recursive. This shows that $\mathrm{\Theta }$ is primitive recursive as well.

Next, since the characteristic function of $\mathrm{\Psi }(𝒙,y)$ is the same as the characteristic function of $\mathrm{\neg }\forall z\le y(\mathrm{\neg }\mathrm{\Phi }(𝒙,z))$, we conclude that $\mathrm{\Psi }$ is primitive recursive by proposition 1 and what we have just proved.∎

Our final example is the following:

1. $\mathrm{\Phi }(x)$ given by “$x$ is prime” is primitive recursive. One way to characterize $\mathrm{\Phi }$ is the following: , and $x$ can not be written as a product of two natural numbers, both greater than $1$. In other words,

   where $\equiv$ means “can be characterized by” (they share the same characteristic function). Observe that since $x=yz$, both $y$ and $z$ are in fact bounded by $x$. Therefore,

   As each of , and is primitive recursive, so are their conjunction:

   the negation of which:

   two successive applications of bounded universal quantifiers:

   and finally its conjunction with the primitive recursive predicate , which is just $\mathrm{\Phi }(x)$. Therefore, $\mathrm{\Phi }(x)$ is primitive recursive.

Remark. The empty set $\mathrm{\varnothing }$, corresponding to the predicate “”, is clearly primitive recursive. However, $\mathrm{\varnothing }$ as a function, is not primitive recursive.