Primitive recursive functions/sets

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Primitive
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

I have to show that the following functions and sets are primitive recursive:
  1. $$f(x,y)=x+y$$
  2. $$f(x,y)=x \cdot y$$
  3. $$sign (x)=\left\{\begin{matrix}
    1 &\text{ if } x=0\\
    0 &\text{ if } x>0
    \end{matrix}\right. $$
  4. $$x \dot - y=\left\{\begin{matrix}
    x-y &\text{ if } x \geq y\\
    0 &\text{ else }
    \end{matrix}\right. $$
  5. $$f(x)=\left\{\begin{matrix}
    1 & \text{ if } g(x)=0 \\
    0 & \text{ if } h(x)=0
    \end{matrix}\right. \\ g,h: \mathbb{N}_0\rightarrow \mathbb{N}_0 \text{ primitive recursive and } \forall x: g(x) \cdot h(x)=0, g(x)+h(x)>0 $$
  6. $$f(y)=\sum_{x=0}^y g(x) \text{ if } g \text{ is primitive recursive } $$
  7. $$f(y)=\prod_{x=0}^y g(x) \text{ if } g \text{ is primitive recursive } $$
  8. $$\{y \mid \exists x \leq y : x \in A\}, \{y \mid \forall x \leq y : x \in A\} \text{ if } A \text{ is primitive recursive}$$
I have done the following:

The basic primitive functions are the constant, the succesor $S(x)$, the projection $P_n^m(x_1, \cdot , x_m)=x_n, m \geq n$.

  1. $$f(0,y)=P_1^1(y) \\ f(x+1,y)=S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y)$$
  2. $$f(0,y)=0 (\text{ constant } ) \\
    f(x+1, y)=(x+1)\cdot y=x \cdot y +1 =S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y)$$
  3. $$sign(0)=1 ( \text{ constant } ) \\
    sign(x+1)=0 (\text{ constant } ) $$
  4. $$f(x,y)=x \dot - y \\ f(0,y)=0 (\text{ constant } ) \\
    f(x+1,y)=\left\{\begin{matrix}
    x+1-y=(x-y)+1=S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y) &\text{ if } x+1 \geq y\\
    0 &\text{ else }
    \end{matrix}\right. $$
  5. $$f(0)=\left\{\begin{matrix}
    1 & \text{ if } g(0)=0 \\
    0 & \text{ if } h(0)=0
    \end{matrix}\right. \\ \Rightarrow f(0) \text{ constant } \\
    f(x+1)=\left\{\begin{matrix}
    1 & \text{ if } g(x+1)=0 \\
    0 & \text{ if } h(x+1)=0
    \end{matrix}\right. \\ \Rightarrow f(x+1) \text{ constant } $$
  6. $$f(0)=\sum_{x=0}^0 g(x)=g(0)$$ which is a primitive recursive function, since $g$ is a primitive function
    $$f(y+1)=\sum_{x=0}^{y+1} g(x)=\sum_{x=0}^y g(x) + g(y+1)=f(y)+g(y+1)=sum(f(y),g(y+1))$$
    where $sum(x,y)$ is the first function $f(x,y)=x+y$.
    But this is not of the form $h(y,f(y))$ What could I change?? Should I use a composition?? But with which function ??
  7. $$ f(0)=\prod_{x=0}^0 g(x)=g(0)$$ which is a primitive recursive function, since $g$ is a primitive function
    $$f(y+1)=\prod_{x=0}^{y+1} g(x)=\left (\prod_{x=0}^y g(x) \right ) \cdot g(y+1)= f(y) \cdot g(y+1)=prod(f(y), g(y+1))$$
    where $prod(x,y)$ is the first function $f(x,y)=x \cdot y$.
    But this is not of the form $h(y,f(y))$ What could I change?? Should I use a composition?? But with which function ??

Is this correct?? (Wondering) Could I improve something?? (Wondering)

For the last one we have that a set is primitive recursive iff its characteristic function is primitive recursive, right??

Could you explain to me how I could apply this?? (Wondering)
 
Physics news on Phys.org
  • #2
mathmari said:
For the last one we have that a set is primitive recursive iff its characteristic function is primitive recursive, right?
Yes.

mathmari said:
Could you explain to me how I could apply this?
For $\exists$, take the sum of the values of the characteristic function on all $0\le x\le y$, for $\forall$ take the product (or vice versa).
 
  • #3
Evgeny.Makarov said:
For $\exists$, take the sum of the values of the characteristic function on all $0\le x\le y$, for $\forall$ take the product (or vice versa).

Why does this stand? Could you explain it to me?
 
  • #4
mathmari said:
Why does this stand?
What do you mean by "this"? I did not make any claim. I suggested taking bounded sums and products. Have you tried it? Have you considered some examples? What if you have a singleton set $A=\{2\}$ and you take a product $\prod_{x\le 5}\chi_A(x)$ where $\chi_A(x)$ is the characteristic function of $A$?

Also, in my experience one usually says, "This statement holds" rather than "This statement stands".
 
  • #5
Evgeny.Makarov said:
What do you mean by "this"? I did not make any claim. I suggested taking bounded sums and products. Have you tried it? Have you considered some examples? What if you have a singleton set $A=\{2\}$ and you take a product $\prod_{x\le 5}\chi_A(x)$ where $\chi_A(x)$ is the characteristic function of $A$?

Also, in my experience one usually says, "This statement holds" rather than "This statement stands".

Do we take the sum becasuse we want that there exists at least one x in A that smaller or equal to y?

And if we had at the set $\forall$ instead of $\exists$ we would tasks the product so that it is equal to 1 only if all x satisfy this property?
 
  • #6
Yes. The details depend on how the return values of a characteristic function correspond with truth values. Some textbook take 0 to be true and 1 to be false, some 0 to be false and anything non-zero to be true and so on.
 
  • #7
mathmari said:
$$f(x,y)=x \dot - y \\ f(0,y)=0 (\text{ constant } ) \\
f(x+1,y)=\left\{\begin{matrix}
x+1-y=(x-y)+1=S(P_2^3(x,f(x,y),y))=S \circ P_2^3(x,f(x,y),y) &\text{ if } x+1 \geq y\\
0 &\text{ else }
\end{matrix}\right. $$
Making a choice is not a part of the definition of PRF. I recommend defining the left inverse of $S$ first.

mathmari said:
$$f(0)=\left\{\begin{matrix}
1 & \text{ if } g(0)=0 \\
0 & \text{ if } h(0)=0
\end{matrix}\right. \\ \Rightarrow f(0) \text{ constant } \\
f(x+1)=\left\{\begin{matrix}
1 & \text{ if } g(x+1)=0 \\
0 & \text{ if } h(x+1)=0
\end{matrix}\right. \\ \Rightarrow f(x+1) \text{ constant } $$
Again, it is not clear how you implement choice. I believe $f(x)=\operatorname{sign}(g(x))$.

mathmari said:
$$f(0)=\sum_{x=0}^0 g(x)=g(0)$$ which is a primitive recursive function, since $g$ is a primitive function
$$f(y+1)=\sum_{x=0}^{y+1} g(x)=\sum_{x=0}^y g(x) + g(y+1)=f(y)+g(y+1)=sum(f(y),g(y+1))$$
where $sum(x,y)$ is the first function $f(x,y)=x+y$.
But this is not of the form $h(y,f(y))$
Yes, it is, for a suitable chosen $h$.
 

Similar threads

Replies
1
Views
986
Replies
4
Views
1K
Replies
0
Views
2K
Replies
0
Views
1K
Replies
1
Views
1K
Replies
3
Views
2K
Replies
2
Views
2K
Back
Top