1
$\begingroup$

I have the following assignment question, and I'm having trouble even getting started:

Consider the set of functions $\mathcal{F}=\{f,g\}$, with $f:\mathbb{R}^2\to\mathbb{R}$, and $g:\mathbb{R}\to\mathbb{R}$, defined by $f(x,y)=xy$ and $g(x)=x+1$. Let $A=cl_\mathcal{F}(B)$, with $B=\{0\}$. I.e., $A$ is the closure of $B$ under the operations in $\mathcal{F}$. Then clearly $A=\mathbb{N}$. How would you go about showing that the following three equations, uniquely determine a function $h$?

$h(f(x,y))=f(h(x),h(y))$,

$h(g(x))=h(x)+2$, and

$h(0)=0$.

What is $A$ good for? Is it necessary to show what we're being asked to show? And also, we're on the topic of primitive recursive functions and such, so I don't understand how this would fit into that topic anyway.

  • 0
    Are you sure about $h(f(x,y))=f(h(x),h(y))$? Maybe a typo for $h(f(x,y))=f(h(x),y)$ or something similar.2012-08-16

1 Answers 1

1

Using the second two equations, we have that $h(0)=0$ and $h(x+1)=h(x)+2$. Thus we can use induction to find the value of $h(x)$ for any value $x\in\Bbb N$. In fact, it is easy to see that if $x\in \Bbb N$ we have $h(x)=2x$.

Now the first condition $h(xy)=h(x)h(y)$ provides a contradiction, however, since we can take $y=1$ and find that $h(x)=2h(x)$, i.e. $2x=4x$ for $x\in\Bbb N$. Thus no function $h$ exists satisfying all three conditions, which is why André Nicolas asked if there was perhaps a typo.

  • 0
    Nice and simple.2014-12-10