Primitive recursive functions/sets

[mathmari]

Hey!

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)

 

[Evgeny.Makarov]

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

Yes.

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).

 

[mathmari]

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?

 

[Evgeny.Makarov]

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".

 

[mathmari]

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?

 

[Evgeny.Makarov]

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.

 

[Evgeny.Makarov]

$$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.

$$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))$.

$$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$.