# Definability using rudimentary function

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

• 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.... – Thomas Benjamin Jun 16 '16 at 18:33

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.

• Is there a restriction on rudimentary functions for which the OP's conjecture holds? – Thomas Benjamin Jun 17 '16 at 16:06