6
$\begingroup$

Denote by RUD the set of all rudimentary functions, together with the function that takes any set to its transitive closure.

Assume that I know that a binary relation $R$ is definable by some function in RUD. Is there a way to define $R^+$, the transitive closure of the relation $R$, using functions in RUD? Maybe there isn't one, but I strongly feel there should be a way and I cannot seem to find it. I can be even more specific, I want to be able to define the function that given a set $x$ returns the set $\{ y | R^+(x,y) \}$, given that I know there is a function in RUD which defines the function that takes $x$ to $\{ y | R(x,y) \}$.

Thanks for your help!

Improve this question
$\endgroup$
1
  • $\begingroup$ Are you asking (in essence) if the transitive closure $R^+$ (where $R$ is rudimentary) is equal to the rudimentary closure of $R$? I hope this question is not too stupid. If it is , I will retract.... $\endgroup$
    – Thomas Benjamin
    Jun 16, 2016 at 18:33

1 Answer 1

Reset to default
8
$\begingroup$

If I understand you correctly I believe the answer is no. Let $S(x)$ be the rud. function that returns $x \cup \{x\}$. Let $R(x,y) \leftrightarrow y = S(x)$. Then $F(x) = \{y\mid R(x,y)\} = \{S(x)\}$ is rud. But $G(x)=\{y\mid R^+(x,y)\}\supseteq \{y \mid \exists p<\omega\,\, y = SS...SS(x)\, (p \mbox{ times }) \}$. However then there is no $q$ so that $\forall x : rk(G(x))\leq rk(x)+q$. Hence $G$ cannot be rud.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there a restriction on rudimentary functions for which the OP's conjecture holds? $\endgroup$
    – Thomas Benjamin
    Jun 17, 2016 at 16:06

Your Answer

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

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