examples of primitive recursive predicates

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

1. 1.

$\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 $\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, $\Phi$ is primitive recursive.

2. 2.

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

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

Proof.

Let $S,T$ be the sets associated with the predicates $\Phi$ and $\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 $\neg\Phi$. Since $1\dot{-}c_{S}$ is primitive recursive, so is $\neg\Phi$.

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

Finally, the set associated with $\Phi\vee\Theta$ is $S\cup T$, which is $\mathbb{N}^{k}-((\mathbb{N}^{k}-S)\cap(\mathbb{N}^{k}-T))$, which is primitive recursive. Hence $\Phi\vee\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. 3.

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

2. 4.

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

3. 5.

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 $\Phi(x_{1},\ldots,x_{m})$ is primitive recursive, so is $\Theta(x_{1},\ldots,x_{n})$, defined by simultaneous substitution of the variables $x_{i}$ in $\Phi$ by $n$-ary primitive recursive functions $f_{i}$:

 $\Theta(x_{1},\ldots,x_{n}):=\Phi(f_{1}(x_{1},\ldots,x_{n}),\ldots,f_{m}(x_{1},% \ldots,x_{n})).$
Proof.

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

 $c_{\Phi}(f_{1}(x_{1},\ldots,x_{n}),\ldots,f_{m}(x_{1},\ldots,x_{n}))$

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

Let us list two more examples:

1. 6.

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

2. 7.

the predicate “$y” 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 $\Phi(\boldsymbol{x},y)$ is primitive recursive, so are

 $\Theta(\boldsymbol{x},y):=\forall z\leq y\>\Phi(\boldsymbol{x},z)\qquad\mbox{% and}\qquad\Psi(\boldsymbol{x},y):=\exists z\leq y\>\Phi(\boldsymbol{x},z).$
Proof.

The set associated with $\Theta(\boldsymbol{x},y)$ is $\{(\boldsymbol{x},y)\mid\mbox{ for all }z\leq y,\Phi(\boldsymbol{x},z)\}$, which is just

 $S:=\{(\boldsymbol{x},y)\mid\Phi(\boldsymbol{x},0)\}\cap\{(\boldsymbol{x},y)% \mid\Phi(\boldsymbol{x},1)\}\cap\cdots\cap\{(\boldsymbol{x},y)\mid\Phi(% \boldsymbol{x},y)\}$

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

 $c(\boldsymbol{x},y):=\prod_{i=0}^{y}d(\boldsymbol{x},i).$

So $1=d(\boldsymbol{x},i)=c_{i}(\boldsymbol{x})$ iff $\Phi_{i}(\boldsymbol{x})$ iff $(\boldsymbol{x},i)\in\{(\boldsymbol{x},i)\mid\Phi(\boldsymbol{x},i)\}$ iff $(\boldsymbol{x},y)\in\{(\boldsymbol{x},y)\mid\Phi(\boldsymbol{x},i)\}$.

As a result, $1=c(\boldsymbol{x},y)$ iff $(\boldsymbol{x},y)\in\{(\boldsymbol{x},y)\mid\Phi(\boldsymbol{x},i)\}$ for all $i\in\{0,\ldots,y\}$ iff $(\boldsymbol{x},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 $\Theta$ is primitive recursive as well.

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

Our final example is the following:

1. 8.

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

 $\Phi(x)\equiv(1

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,

 $\Phi(x)\equiv(1\neg(x=yz\wedge 1

As each of $x=yz,1, and $1 is primitive recursive, so are their conjunction:

 $x=yz\wedge 1

the negation of which:

 $\neg(x=yz\wedge 1
 $\forall y\leq x(\forall z\leq x\>\neg(x=yz\wedge 1

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

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

Title examples of primitive recursive predicates ExamplesOfPrimitiveRecursivePredicates 2013-03-22 19:05:43 2013-03-22 19:05:43 CWoo (3771) CWoo (3771) 9 CWoo (3771) Example msc 03D20 ExamplesOfPrimitiveRecursiveFunctions