Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T16:31:05.331Z Has data issue: false hasContentIssue false

Alternative proof of a theorem of Kleene

Published online by Cambridge University Press:  12 March 2014

Hao Wang*
Affiliation:
University of Oxford

Extract

We offer a simple alternative proof of Theorem II, Kleene [1]:

Theorem. For certain primitive recursive -predicates R and S,

We separate the definitions of < o and O:

Definition 1. (1) 1 <o2; (2) for all y, if 1 <oy, then y <o 2v; (3) for all e, if (n)(Ey)T(e, no, y) and (n)(e(no) <oe((n+1)o)), then (n)(e(no) <o 3·5e); (4) for all x, y, z, if x <oy, y <oz, then x <oz; (5) a <ob only as required by (1)–(4).

Definition 2. a ϵ O if and only if 1 <o 2α.

If we write α(2a·3b) = O for a <ob in Conditions (1) to (4) of Definition 1 and take their conjunction, we get an arithmetic predicate P(α). By the Frege-Dedekind device for handling inductive definitions,

Hence, by Theorem 1 (Part 2) of [2], we have a primitive recursive S such that a <o b ≡ (α)(Ey)S(a, b, α, y). By Definition 2,

The classical use of the function quantifier (α) in the above proof is conspicuous. It is not clear that the constructive or intuitionistic content of Kleene's proof (cf. [1] Footnote 40) can be obtained by this method.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1958

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Kleene, S. C., On the forms of the predicates in the theory of constructive ordinals (second paper), American journal of mathematics, vol. 77 (1955), pp. 405428.CrossRefGoogle Scholar
[2]Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312340.CrossRefGoogle Scholar