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!

  • $\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 '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.

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

Your Answer

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

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