Given the next alphabets: $\,\,\Sigma_1=\{R^2,P^1,=^2\}\,\,,\Sigma_2=\{c,f^1,=^2\}.$
Prove of Disprove: There's exists an algorithm, that given formula $A$ above $\Sigma_2$, builds formula $A'$ above $\Sigma_1$ such that:
$A$ is valid $\iff$ $A'$ is valid.

I could not come up with a solution, but I have two directions.

  1. I taught maybe the idea is to represent the function $f$ by using the binary relation $R$, and to force every element in the domain to be in the relation but with only one other element. With the relation $P$ I taught to force existence of one element that will "play" the role $c$ plays in $\Sigma_2$ - I will force realtion $P$ to contain exactly one element- the representor.
  2. Then I taught to change accordingly the formula $A$ in a way that will save validity, but it became so messy, so I'm no longer sure if I'm in the right direction.
  3. I'm also not sure how to express formulas as $\exists \,x\,(f(f(c))=x)$. I mean, how can I express the "power" of the function $f$. So I'm wandering maybe the claim is false, and by using some reduction I need to show that if the claim is true, some un-decidable problem is solved.

I would appreciate some help!

  • $\begingroup$ Hint: $f(f(t))=s$ is equivalent to $\exists x\,(f(t)=x\land f(x)=s)$. And yes, your strategy is right. $\endgroup$ – Emil Jeřábek Jun 18 at 14:30
  • $\begingroup$ But assume $A$ is of the next form: $A=\,$ $\exists x(f(x)=x)$. I'm still not sure how to deal with $f$ inside relation. I $\endgroup$ – Ella Jun 19 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.