The photo below was taken from textbook A Course in Mathematical Analysis by Prof D. J. H. Garling.
The excerpt is about the proof of Recursion Theorem. In this proof, the author mentions the set of all recursive relations.
I would like to ask: How do we know (or prove) that the set of all recursive relations exist?
Many thanks for your help!
I'm going to assume the author uses the ZFC axioms for set theory here. It's also quite possible that they're working in "naive set theory," in which case "basic" constructions like the set of all relations with a certain property on a family of sets are simply assumed.
Well, it's even better: the set $\mathcal{R}$ of all relations (on a given family $X_1, ..., X_n$ of sets) exists. We can prove this by first showing that the Cartesian product $X_1\times ...\times X_n$ exists, and then applying the Powerset axiom.
Then the set of recursive relations can be proved to exist by applying Separation to $\mathcal{R}$, using the definition of "recursive relation." (Note that I'm ignoring what exactly "recursive" means here; the point is that the set of [adjective] relations on a tuple of sets always exists, so long as [adjective] is definable in the language of set theory.)