Formalization
The T predicate is primitive recursive in the sense that there is a primitive recursive function that, given inputs for the predicate, correctly determine the truth value of the predicate on those inputs. Similarly, the U function is primitive recursive.
Because of this, any theory of arithmetic that is able to represent every primitive recursive function is able to represent T and U. Examples of such arithmetical theories include Robinson arithmetic and stronger theories such as Peano arithmetic.
Read more about this topic: Kleene's T Predicate