examples of primitive recursive predicates


In this entry, we give some examples of primitive recursive predicates. In particular, we will show that the predicateMathworldPlanetmathPlanetmath β€œx is a prime numberMathworldPlanetmath” is primitive recursive.

In the examples, we use Φ⁒(𝒙) to indicate a predicate (over the natural numbersMathworldPlanetmath β„•). First, two very simple examples:

  1. 1.

    Φ⁒(x) given by β€œx=n” for a fixed nβˆˆβ„• is primitive recursive. To see this, note that the set associated with Ξ¦ is {n}, and its associated characteristic functionMathworldPlanetmathPlanetmath is primitive recursive by example 3(l) in this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions). As a result, Ξ¦ is primitive recursive.

  2. 2.

    Φ⁒(x,y) given by β€œx≀y” is primitive recursive. The associated set is {(x,y)∣x≀y} whose characteristic function is sgn⁑(s⁒(y)⁒-˙⁒x), which is primitive recursive.

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

Proposition 1.

If Φ and Θ are primitive recursive predicates, then so are ¬⁒Φ (negationMathworldPlanetmath), Φ∨Θ (disjunctionMathworldPlanetmath), and Φ∧Θ (conjunctionMathworldPlanetmath).

Proof.

Let S,T be the sets associated with the predicates Ξ¦ and Θ. We may assume that S,TβŠ†β„•k for some positive integer k. Let cS and cT be the associated characteristic functions.

First, 1⁒-˙⁒cS is the characteristic function of β„•k-S, which is the associated set of the predicate ¬⁒Φ. Since 1⁒-˙⁒cS is primitive recursive, so is ¬⁒Φ.

Next, mult⁑(CS,CT) is the characteristic function of S∩T, which is the associated set of the predicate Φ∧Θ. Since mult⁑(CS,CT) is primitive recursive, so is Φ∧Θ.

Finally, the set associated with Φ∨Θ is SβˆͺT, which is β„•k-((β„•k-S)∩(β„•k-T)), which is primitive recursive. Hence Φ∨Θ is primitive recursive as well. ∎

In short, primitive recursiveness is preserved under Boolean operations on predicates. By inductionMathworldPlanetmath, 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≀y” and β€œy≀x”.

  2. 4.

    the predicate β€œy<x” is primitive recursive, since it is the conjunction β€œy≀x” and β€œΒ¬β‘(x=y)”, both of which are primitive recursive.

  3. 5.

    the predicate β€œx∈S”, where S is a fixed finite setMathworldPlanetmath, is primitive recursive, as it is the disjunction of primitive predicates of the form β€œx=n”, where n ranges over S. Since the disjunction operationMathworldPlanetmath is finitary, β€œx∈S” is primitive recursive also.

Here’s another useful fact about primitive recursive predicates:

Proposition 2.

If Φ⁒(x1,…,xm) is primitive recursive, so is Θ⁒(x1,…,xn), defined by simultaneous substitution of the variables xi in Ξ¦ by n-ary primitive recursive functions fi:

Θ⁒(x1,…,xn):=Φ⁒(f1⁒(x1,…,xn),…,fm⁒(x1,…,xn)).
Proof.

Let cΦ be the characteristic function of (the set associated with) Φ, then

cΦ⁒(f1⁒(x1,…,xn),…,fm⁒(x1,…,xn))

is cΘ, the characteristic function of Θ. Since cΦ, fi are primitive recursive, cΘ, obtained by functionalMathworldPlanetmathPlanetmathPlanetmathPlanetmath composition, and hence Θ, are primitive recursive too. ∎

Let us list two more examples:

  1. 6.

    the predicate β€œx⁒yβ‰ z” is primitive recursive.

  2. 7.

    the predicate β€œy<x!” 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 Φ⁒(𝐱,y) is primitive recursive, so are

Θ⁒(𝒙,y):=βˆ€z≀y⁒Φ⁒(𝒙,z)β€ƒβ€ƒπ‘Žπ‘›π‘‘β€ƒβ€ƒΞ¨β’(𝒙,y):=βˆƒz≀y⁒Φ⁒(𝒙,z).
Proof.

The set associated with Θ⁒(𝒙,y) is {(𝒙,y)∣ for all ⁒z≀y,Φ⁒(𝒙,z)}, which is just

S:={(𝒙,y)∣Φ⁒(𝒙,0)}∩{(𝒙,y)∣Φ⁒(𝒙,1)}βˆ©β‹―βˆ©{(𝒙,y)∣Φ⁒(𝒙,y)}

For each fixed i, let Ξ¦i⁒(𝒙):=Φ⁒(𝒙,i). Then by propositionPlanetmathPlanetmathPlanetmath 2, Ξ¦i is primitive recursive. Let ci be the characteristic function of Ξ¦i, and d the function such that d⁒(𝒙,i) is ci⁒(𝒙) if i∈{0,…,n}, and 0 otherwise. So d is primitive recursive (see this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions)). Now, define function c by

c⁒(𝒙,y):=∏i=0yd⁒(𝒙,i).

So 1=d⁒(𝒙,i)=ci⁒(𝒙) iff Ξ¦i⁒(𝒙) iff (𝒙,i)∈{(𝒙,i)∣Φ⁒(𝒙,i)} iff (𝒙,y)∈{(𝒙,y)∣Φ⁒(𝒙,i)}.

As a result, 1=c⁒(𝒙,y) iff (𝒙,y)∈{(𝒙,y)∣Φ⁒(𝒙,i)} for all i∈{0,…,y} iff (𝒙,y)∈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 Θ is primitive recursive as well.

Next, since the characteristic function of Ψ⁒(𝒙,y) is the same as the characteristic function of Β¬β’βˆ€z≀y⁒(¬⁒Φ⁒(𝒙,z)), we conclude that Ξ¨ is primitive recursive by proposition 1 and what we have just proved. ∎

Our final example is the following:

  1. 8.

    Φ⁒(x) given by β€œx is prime” is primitive recursive. One way to characterize Ξ¦ is the following: 1<x, and x can not be written as a productPlanetmathPlanetmath of two natural numbers, both greater than 1. In other words,

    Ξ¦(x)≑(1<x)βˆ§βˆ€y(βˆ€zΒ¬(x=yz∧1<y∧1<z)),

    where ≑ means β€œcan be characterized by” (they share the same characteristic function). Observe that since x=y⁒z, both y and z are in fact boundedPlanetmathPlanetmath by x. Therefore,

    Ξ¦(x)≑(1<x)βˆ§βˆ€y≀x(βˆ€z≀xΒ¬(x=yz∧1<y∧1<z)).

    As each of x=y⁒z,1<y, and 1<z is primitive recursive, so are their conjunction:

    x=y⁒z∧1<y∧1<z,

    the negation of which:

    ¬⁑(x=y⁒z∧1<y∧1<z),

    two successive applications of bounded universal quantifiersMathworldPlanetmath:

    βˆ€y≀x(βˆ€z≀xΒ¬(x=yz∧1<y∧1<z)),

    and finally its conjunction with the primitive recursive predicate 1<x, which is just Φ⁒(x). Therefore, Φ⁒(x) is primitive recursive.

Remark. The empty setMathworldPlanetmath βˆ…, corresponding to the predicate β€œx<x”, is clearly primitive recursive. However, βˆ… as a function, is not primitive recursive.

Title examples of primitive recursive predicates
Canonical name ExamplesOfPrimitiveRecursivePredicates
Date of creation 2013-03-22 19:05:43
Last modified on 2013-03-22 19:05:43
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Example
Classification msc 03D20
Related topic ExamplesOfPrimitiveRecursiveFunctions