3
$\begingroup$

From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates

$(\forall t)_{\le y}$  $P(t,x_1,...,x_n)$

$(\exists t)_{\le y}$  $P(t,x_1,...,x_n)$

But what about the unbounded quantifier? what difference does it make if I replace $(\forall t)_\le$ with $(\forall t)$ and also $(\exists t)_\le$ with $(\exists t)$ ?

Davis in his book page 43 says:

Theorem 3.3: A function is primitive recursive if and only if it belongs to every PRC class

I saw a problem related to what I said that I couldn't solve, here it is :

If $P(x)$ and $Q(x)$ are primitive recursive predicates which one of the following may not be primitive recursive:

  1. $P(x) \rightarrow Q(x)$

  2. $Q(z) \wedge P([\sqrt{x}])$

  3. $\forall x(x \le y \rightarrow P(x))$

  4. $\exists x(P(x) \wedge Q(x)) $

Since only one of the above choices is right, so I don't know 3 is the answer or 4!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

If $P(t,x_1,\dots,x_n) \in \zeta$, then clearly $(\forall t)_{\le 0}P(t,x_1,\dots,x_n) = P(0,x_1,\dots,x_n) \in \zeta$.

Moreover, if for some $y$, we have $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, then it can easily be shown that $(\forall t)_{\le y+1}P(t,x_1,\dots,x_n) = P(y+1,x_1,\dots,x_n) \land (\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, noting that taking the logical and is a primitive recursive operation.

By induction, we have that for any $y$, $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$. Things work similarly for $(\exists t)_{\le y}$. However, this reasoning doesn't extend to unbounded quantifiers, and in the general case, $\forall t P(t,x_1,\dots,x_n) \notin \zeta$.

If you think of PRC predicates as things that can be checked by a computer in finite time, the underlying meaning is that

  • if it takes finite time to check whether a given proposition is true for any given value, then it also takes finite time to check whether it's true for any/all values in a finite set (at most the sum of the finite times taken to check for each element in the set)
  • on the other hand, it's not necessarily possible to check that it's true for any/all values in an infinite set. Naively checking for $0$, then $1$, then $2$, etc..., could take forever.

The answer to your second question is proposition 4. Indeed, in proposition 3, the universal quantifier over $x$ is bounded by the free variable $y$, which is a finite value. In other words, proposition 3 could be rewritten as $(\forall x)_{\le y}P(x)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, one more question. If $\sqrt{x}$ was not primitive recursive would this cause that $P(\sqrt{x})$ to be non primitive recursive ? $\endgroup$ Commented Feb 12, 2015 at 13:39
  • $\begingroup$ If $g(x)$ and $f(x)$ are primitive recursive, then $g(f(x))$ is too. If either of them isn't, then $g(f(x))$ is likely not primitive recursive either, although it could still happen to be, but it would have to be proven in some other way. $\sqrt x$ is not primitive recursive, so in general neither is $P(\sqrt x)$. However in your questions above, we're looking at $P([\sqrt x])$. $[\sqrt x]$ happens to be primitive recursive even though $\sqrt x$ isn't, which is an example of $g(f(x))$ being primitive recursive where $f(x)$ isn't (with $g(x) = [x]$ and $f(x) = \sqrt x$). $\endgroup$ Commented Feb 12, 2015 at 13:52
  • 1
    $\begingroup$ This link nayuki.io/page/primitive-recursive-functions says $\sqrt {x}$ is primitive recursive $\endgroup$ Commented Feb 12, 2015 at 14:10
  • 2
    $\begingroup$ Primitive recursive functions map to $\mathbb{N}$. The mathematical $\sqrt x$ is defined from $\mathbb{N}$ to $\mathbb{R}$ and as such can't be primitive recursive. Your references identifies $\sqrt x$ with it's integral part, in order to define $\sqrt x$ as a function that maps from $\mathbb{N}$ to $\mathbb{N}$ and is indeed primitive recursive. This function is what I would call $\lfloor\sqrt x\rfloor$, where $\lfloor x\rfloor$ represents taking the integral part (floor). So we're just using different notations. $\endgroup$ Commented Feb 12, 2015 at 14:20
3
$\begingroup$

Agree with David that 3 is primitive recursive, but depending on what is meant exactly, the predicate in 4 is also primitive recursive - as a predicate, $\exists x(P(x) \wedge Q(x))$ has zero arguments and therefore is simply a truth value - and thus trivially primitive-recursive. On the other hand, if you took primitive-recursive predicates $P(x,y), Q(x,y)$ with (say) two arguments, then $\exists x(P(x,y) \wedge Q(x,y))$ is indeed in general not primitive-recursive. Furthermore, while $\exists x(P(x) \wedge Q(x))$ is a constant, there is no computable method for determining its value from the definitions of $P(x)$ and $Q(x)$. This contrasts with bounded quantification, where a primitive-recursive definition for the result can be obtained computably from the definitions of the input predicate.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Micheal, I know nothing about the relation between the number of arguments of predicates and their property to be primitive recursive. Would you give me more details? $\endgroup$ Commented Feb 12, 2015 at 16:57
  • 1
    $\begingroup$ If a predicate has no arguments, it is either always false or always true (so it is equal to one of the predicates $\top$ and $\bot$). So its characteristic function is simply a constant function which either always yields 0 or always yields 1. Constant functions are primitive recursive. On the other hand, whether a predicate has, say, one or two arguments does not really make a difference, as one can encode sequences of arguments in a single argument in a primitive-recursive manner. Hope that elucidates it. $\endgroup$ Commented Feb 12, 2015 at 17:32
  • $\begingroup$ @MichaelHahn: Good catch, I indeed overlooked the absence of free variables in predicate 4, which also makes it primitive recursive. Thanks for pointing it out :-) $\endgroup$ Commented Feb 12, 2015 at 19:56
  • $\begingroup$ @MichaelHahn so as a result both 3 and 4 are primitive recursive, yes? Interesting! I've never thought the option 4 could be primitive recursive. $\endgroup$ Commented Feb 14, 2015 at 4:10

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.