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$
    – M a m a D
    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$
    – David Durrleman
    Feb 12, 2015 at 13:52
  • 1
    $\begingroup$ This link nayuki.io/page/primitive-recursive-functions says $\sqrt {x}$ is primitive recursive $\endgroup$
    – M a m a D
    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$
    – David Durrleman
    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$
    – M a m a D
    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$
    – Michael Hahn
    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$
    – David Durrleman
    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$
    – M a m a D
    Feb 14, 2015 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.