Another extension of Van de Wiele's theorem (Q1102277)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Another extension of Van de Wiele's theorem
scientific article

    Statements

    Another extension of Van de Wiele's theorem (English)
    0 references
    0 references
    1988
    0 references
    Van de Wiele showed that if a total function F is \(\Sigma_ 1\)-definable uniformly over all admissible sets, then it is actually E-recursive (the converse being easy). He did this by giving a construction of F in \(\Pi\) \(1_ 2\) logic, which is weaker than E-recursion theory, which yields immediately that F is E-recursive. Slaman then proved this theorem using only the constructions of E-recursion theory, and not those of \(\Pi\) \(1_ 2\) logic. Moreover, he generalized it to functions F with a hereditarily countable parameter p, or with an arbitrary parameter if the domain of F is the ordinals. The conclusion of his theorem is that such an F is \(ES_ p\)-recursive: E-recursive where selection from p is allowed also. The current paper continues this cycle by proving Slaman's theorem via \(\Pi\) \(1_ 2\) logic. Moreover, it shows that selection from p is unnecessary: having p as a parameter suffices.
    0 references
    0 references
    Pi-1-2-logic
    0 references
    E-recursion theory
    0 references
    0 references