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
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
Pi-1-2-logic
0 references
E-recursion theory
0 references