Lecture Notes in Mathematics Edited by A. Dold, Heidelberg and B. Eckmann, Z(Jrich
344 I
IIIIIIIIIIIIII
A. S. Troelstra (Editor) Universiteit van Amsterdam, Amsterdam/Nederland
Metamathematical Investigation of intuitionistic Arithmetic and Analysis
Springer-Verlag Berlin-Heidelberg- New York 1973
A M S Subject Classifications (1970): 02C15, 0 2 D 0 5 , 0 2 D 9 9 , 0 2 H 1 0
I S B N 3-540-06491-5 S p r i n g e r - V e r l a g B e r l i n • H e i d e l b e r g - N e w Y o r k I S B N 0-387-06491-5 S p r i n g e r - V e r l a g N e w Y o r k - H e i d e l b e r g • Berlin
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin - Heidelberg 1973. Library of Congress Catalog Card Number 73-14238. Printed in Germany. Offsetdruck: Julius Beltz, Hemsbach/Bergstr.
Dedicated
to
GEORG K R E I S E L
who has c o n t r i b u t e d
so m u c h to the
s u b j e c t of this v o l u m e
Preface
The present volume found its origin in a course on functional and realizability interpretations on intuitionistic formal systems, presented at the Rijksuniversiteit Utrecht
(Netherlands) in the spring of 1970, and a course
on the metamathematics of intuitionlstic formal systems at the University of Amsterdam in 1971 - 1972.
The literature on the subject was widely scattered,
the connection between certain rules was often not made explicit in the literathre,
and some obvious questions were not answered there.
Therefore I thought it would be useful to give a coherent presentation of the principal methods for metamathematical investigation of intuitionistic formal systems and the results obtained by these methods, in the literature,
connecting results
filling gaps and adding some new material.
(for realizability and functional interpretations)
A first attempt
was made in Troelstra
1971, which , however, because of a rather terse style, was not readily assimilated by readers new to the field. ( I t
still provides a useful survey of
the applications to first-order systems however.) presentation,
Therefore a more elaborate
including other techniques of metamathematical research,
seemed
to be called for. Having learnt of the unpublished Ph.D. work of C.Smorynski on applications of Kripke-models to intuitionistic arithmetic,
and of Dr
Zucker's thesis on
the intuitienistic theory of higher-order generalized inductive definitions, subjects which both fitted very well into the scope of the planned volume, I asked them to contribute a chapter each ; their contributions appear as chapters V, and VI respectively°
The models for intuitionistic arithmetic
of finite type, functional and realizability interpretations,
and normaliza-
tion for natural deduction systems, and also the general editing of the volume I undertook myself. Finally, N.Ao Howard contributed an Appendix supplementing discussions in § 2.7 and § 3.5. The organization of the volume is primarily method-centered,
i.e. the
material presented is grouped mostly around methods and techniques, arranged according to the results obtained.
by different methods, appear at various places in the book. the
and not
Hence some results, obtainable This will enable
reader to compare the relative merits of the various methods. As regards intuitionistic arithmetic and closely related systems, the
treatment is almost wholly self-contained ;
some experience with classical
VI
metamathematics,
and the elements of intuitionism,
such as may be gleaned
from Kleene's Introduction to metamathematics and Heyting's book on Intuiticnism suffices°
The parts dealing with arithmetic can therefore be
used in a course for graduate students or a seminar. The sections dealing with analysis are not self-contained, more or less as a running commentary on the literature,
connecting and com-
paring various approaches and adding new results besides. thought of primarily as a help to the beginning researcher, find his way in the subject.
and serve
This part was to help him tc
For use in a seminar, these sections should
usually be supplemented by the reading of other papers. In keeping with this set-up, the listing of applications for intuitionistic arithmetic and closely related systems is rather extensive,
but in
the case of analysis we have often restricted ourselves to some typical examples ; further applications can easily be made by the reader himself once he has understood the method, and its applications to arithmetic. No special attention has been given to intuitionistic propositional logic and predicate logic, because as formal systems they exhibit many properties which do not generalize to arithmetic and analysis,
and therefore
would require a separate treatment. Speedy publication was thought more useful than final polish, to make the material outdated at the moment of its appearance.
so ~s not Hence also
the choice for publication in the "Lecture Notes in Mathematics".
Even
while refraining from a completely self-contained treatment of all parts, it was not possible to take all relevant work into account, not even on arithmetic ; for example, N. Goodman's work on the theory of constructions was left out altogether,
since it would not easily be fitted into the
framework of the other developments and so would consume too much space° We have no doubt that there are still many imperfections in this presentation ; it hardly needs saying that the authors will be grateful for errors, misprints,
additions to the bibliography being brought to their
attention. The contents of the present volume are primarily technical in character ; but it is to be hoped that the material will not inspire a thought- and mind-less multiplication of metamathematical results, without a thought spent on their possible significance for an analysis of intuitionistic basic notions and for foundations of mathematics in general.
On the other hand,
the "philosophical interest" of the subject is not promoted by uncritical analysis. property
(A single example : the interest of the well known disjunction ~A VB
= ~A
or
~ B , and the explicit definability for existen-
tial statements are frequently overrated,
especially as a criterion for the
VII
"constructive
character"
in Troelstra A.)
of the system considered.
As regards potential
tb me to be more promising for well-known
systems
results
(but also more difficult)
interest",
it seems
to look for new results
(possibly different in kind from the results dis-
cussed in this volume), and stronger systems.
See e.g. the discussion
"philosophical
instead of trying to extend known results to stronger Of course,
to be potentially
interesting,
the new
should also have a clear intuitive meaning in terms of the intended
interpretation
of the systems considered.
Directions for use. an analytical
In order to help the reader find his way, there is
table of contents at the beginning,
of notions and notations self-explanatory.
at the end.
§ 3.5 refers
Reference
a bibliography,
and lists
to the bibliography
(except in the appendix)
are
to chapter III,
§ 5, etc. The parts on arithmetic self-contained.
and closely related
11 ; chapter If, §§ I - 4 (2.4.18 excepted), of § 6 are used) ; chapter I I I , § § 4 (3.4.1- 14;
systems are more or less
As such we mention especially:
3.4.29),
Chapter I, §§ I - 8, §§ 10,
§ 5, § 7 (except where results
I (3.1.1 - 18), § 2 (3.2.1 - 28 ;
§ 5 (3.5.1- 11;
3.5.16
3o6.16), § 7 (3.7.1-s), § s (except 3.s.7), § 9;
3.2.33),
( i i i ) ) ; § 6 (3.6.1chapter IV, §§ I-4~
(i),
chapter V, §§ 1 - 6. Chapter I contains
all generalities,
and should usually be consulted
when needed only. Acknowledgements°
As regards my own contribution
especially indebted to G. Kreisel, material in his course notes by the dedication),
ical improvements undertook
expository and mathemat-
and to Miss Judith van Witsen,
the seemingly endless task of typing the manuscript.
acknowledgements
expressed
for his patient and careful reading of
suggesting many stylistic,
and corrections,
I am
the use of unpublished
(apart from the general indebtedness
to J.I. Zucker,
drafts of my chapters,
who permitted
to this volume,
who
Some other
have been made in footnotes.
Amsterdam,
June 1973.
A. S. Troelstra
TABLE OF CONTENTS
I°
INTUITIONISTIC
§I
FOR~L
SYSTE~
(A.S. Troelstra)
I n t U i t i o n i s t i c logic N o t a t i o n a l c o n v e n t i o n s (1,1.2) - Spector's system (1.1o3) - Oodel's s y s t e m (1.1~) - E q u i v a l e n c e of Spector's and Godel's system (1.1.5) - E q u i v a l e n c e of Spector's and K l e e n e ' s f o r m a l i z a t i o n (I°I°6) - A n a t u r a l d e d u c t i o n system (1.1.7 - 1.1.9) - D e d u c t i o n theorem for Spector's system ( 1 . 1 . 9 - 1.1.10) - E q u i v a l e n c e b e t w e e n natural d e d u c t i o n and Spector's system (1.1.11)
I
§
2
Conservative and d e f i n i t i o n a l extensions~ expansions D e f i n i t i o n of predicate logic with equality (1.2.1) D e f i n i t i o n of c o n s e r v a t i v e e x t e n s i o n (1.2.2) - E x p a n s i o n (I~2.3) - D e f i n i t i o n a l extension (1.2.4) A d d i t i o n of symbols for d e f i n a b l e p r e d i c a t e s (1.2.67 - A d d i t i o n of symbols for definable functions (1.2.7) - R e p l a c e m e n t of f u n c t i o n symbols by predicate symbols (1.2.8) - A d d i t i o n of d e f i n e d sorts of v a r i a b l e s ( 1 . 2 . 9 1.2.10)
14
§
3
I n t u i t i o n i s t i e first-order arithmetic Language of HA (1.7.2) - A x i o m s and rules of HA (1.3.3) - D e f i n i n g axioms for p r i m i t i v e recursive functions (1.3.4) - Rule and a x i o m schema of i n d u c t i o n (1.3.5) - N a t u r a l d e d u c t i o n variant Of HA (1.3.6) - E l i m i n a b i l i t y of d i s j u n c t i o n in s y s t e m s ~ o n t a i n i n g a r i t h m e t i c (1.3.7) - F o r m u l a t i o n of H~ without function symbols (1.3.8) - N o t a t i o n a l conventions (pairing, coding of finite sequences, proof predicates, godelnumbers, godel- and r o s s e r s e n t e n c e s , numerals) (1.3.9) - F o r m a l i z a t i o n of e l e m e n t a r y r e c u r s i o n theory (1.3.10)
18
§
4
Inductive d e f i n i t i o n s in HA D e f i n i t i o n of class F ( I ~ . 2 ) - Normal form for elements of F ( 1 . 4 . 5 - 1.4.4) - E x p l i c i t d e f i n a b i l i t y of p r e d i c a t e s i n t r o d u c e d as closed u n d e r a c o n d i t i o n
28
-
from
r
(1.4.5)
Partial r e f l e c t i o n p r i n c i p l e s C ~ d e l n u m b e r i n g of f u n c t i o n constants and terms (1.5.2) - E v a l u a t i o n of closed terms (1.5.3) - C o n s t r u c t i o n of partial truth d e f i n i t i o n s (1.5.4) - Partial r e f l e c t i o n p r i n c i p l e s (1.5.5 - 1.5.6) - R e m a r k on r e f i n e m e n t s (1.5.7) - R e m a r k on q u a n t i f i e r - f r e e systems (1.5.8) - R e f l e c t i o n principle for qf-H~A ( 1 . 5 . 9 - 1.5.10). I n t u i t i o n i s t i c arithmetic in all finite types Type structure ~ (1.6.2) - D e s c r i p t i o n of N - I q A w ( 1 . 6 o 3 - 1.6.7) - D e f i n i t i o n of the k - operator ~ . 6 . 8 ) - HA as a subsystem of N - H A m (1.6.9) - Intensional identity or equality (1.6o10) - D e s c r i p t i o n of ~ _ ~ w (1.6.11) - D e s c r i p t i o n of ~ _ ~ w ~_HA m~ (1.6.12) qf - D e s c r i p t i o n of qf c ~ qf-~ -H~' (1.6o13) - q f - ~-__H~A~, q f - W E - H ~ A as equational calculi (1.6.14) - The systems ~, qf - I ~ w (1.6.15)
33
-
39 -
-
X
S i m u l t a n e o u s r e c u r s i o n and p a i r i n g ; a c o m p a r i s o n of v a r i o u s t r e a t m e n t s (1.6.16) - P a i r i n g operators in q f - W ~ E ~ - H ~ ~ (1.6.17) - Historical notes, v a r i a n t s in the l i t e r a t u r e (1.6.18)
-
§
7
Induction and simultaneous recursion S i m u l t a n e o u s r e c u r s i o n in q f _ N _ y ~ W (1.7.2 - 1.7.7) - The i n d u c t i o n lemma for qf_~_~w ( 1 . 7 . 8 - 1.7.10) - R e p l a c e m e n t of r e c u r s o r by iterator (1.7.11) - S i m u l t a n e o u s r e c u r s i o n and the induction lemma in qf-~ (1.7.12)
51
§
8
~ore about N-HA ~ Cartesian product types and pairing operators (1.8.2) - The X - operator as a p r i m i t i v e n o t i o n (1.8.4) - R e d u c t i o n to pure types ( 1 . 8 . 5 - 1.8.8) - R e d u c t i o n to numerical types in q f - W E - ~ ~ (1.8.9)
6o
§
9
E x t e n s i o n s of a r i t h m e t i c E x t e n s i o n s of a r i t h m e t i c expressed in ~(HA) or ~(H~A) extended by relation constants (reflection principles, g e n e r a l i z e d inductive definitions) (1.9.2) - Language of ~S o (1.9.3) - C o m p r e h e n s i o n principles (1.9.4) - E x t e n s i o n a ! i t y (1.9. 5 - 1.9.7) - HAS o + EXT + ACA is c o n s e r v a t i v e over HA (19.8) - F o r m u l a t i o n of HAS with X - terms (1.9.9) - D e s c r i p t i o n of EL (1.9.10) - Some n o t a t i o n s and c o n v e n t i o n s (1.9.11) - F o r m a l i z a t i o n of e l e m e n t a r y r e c u r s i o n theory in EL ( 1 . 9 o 1 2 - 1.9.16) - D e f i n i t i o n s of A°x, A~x, A ° ~ , ~ ' ~ (1o9.17) - Systems of i n t u i t i c n i s t i c analysis based on the concept of a lawlike sequence ; IDB (1.9.18) - Systems of i n t u i t i o n istic analysis based on a concept of choice sequence I].9.19) - Bar i n d u c t i o n (1.9.20) E x t e n d e d bar induction k- . 9 . 2 1 - 1.9.23) - Fan theorem (I.~o24) - E x t e n s i o n s of N - H A ~ : IDB w (1.9.25) - Theories with bar r e c u r s i o n of
66
Jigger typ~E ~ - ~ + funetionals § 10
§ 11
BR
(1.9.26) - Girard's theory of
(1.9.27)
Relations b e t w e e n classical and i n t u i t i o n i s t i c systems : t r a n s l a t i o n into the negative fragment D e f i n i t i o n of the m a p p i n g ' (1.10.2) - D e f i n i t i o n of H a r r o p formula, and strictly positive part (s.p.p.) (1.10.5) - D e f i n i t i o n of n e g a t i v e formula (1.10.6) - P r o p e r t i e s of the m a p p i n g ' ( 1 . 1 0 . 9 - 1.10.13) General d i s c u s s i o n of various s c h e m a t a and prooftheoretic closure conditions D e f i n i t i o n of admissible rule, and intended i n t u i t i o n istic i n t e r p r e t a t i o n of the logical constants (1.11.1) D i s j u n c t i o n and explicit d e f i n a b i l i t y p r o p e r t y (1.11.2) - The schema Vx(A V B x ) ~ A V VxBx (1.11.3) - The schema Vx ~ A ~ ~oVxA (1.11.4) - ~ r k o v ' s schema and rule 11.5) - Independence of premiss schemata and rules , . 1 1 6) Church,s thesis and ~ l e (1.11;7).
85
9o
XI
MODELS A N D C O M P U T A B I L I T Y
I.
(A.S. Troelstra)
§
I
D e f i n i t i o n s by i n d u c t i o n over the type structure D e f i n i t i o n over the type structure (applicative set, type level) (2.1.1) - E s t a b l i s h i n g properties for a p p l i c a t i v e sets of terms (2.1.2) - D e f i n a b i l i t y aspects (2.1.3) - Sets of terms closed u n d e r ~ - a b s t r a c t i o n (2.1.4)
97
§
2
C o m p u t a b i l i t y of terms in N - H A w 100 D e f i n i t i o n of r e d u c t i o n and--standard r e d u c t i o n for terms of N - H A w (2.2.2) - C o m p a r i s o n of standard and strict r e d u C t i O n (2.2.3) - A l t e r n a t i v e d e f i n i t i o n of ~ (2.2.4) - D e f i n i t i o n of computability, strict -, standard (2.2.5) - All terms of N _ ~ w are standard c o m p u t a b l e ( 2 . 2 . 6 - 9) - ~ - H A ~ W c o n s e r v a t i v e over its i n d u c t i o n - f r e e part for equations b e t w e e n closed terms (2.2.10) - Strong c o m p u t a b i l i t y and strong n o r m a l i z a t i o n ( 2 . 2 . 1 2 - 19) - U n i q u e n e s s of n o r m a l form ( 2 . 2 . 2 0 - 29) - C o m p u t a b i l i t y and strong c o m p u t a b i l i t y for k - b a s e d theories ( 2 . 2 . 3 0 - 34) - D i s c u s s i o n and c o m p a r i s o n of proofs of c o m p u t a b i l i t y for terms of H~Aw in the l i t e r a t u r e (2.2.35)
§
3
More about c o m ~ u t a b i l i t ~ 116 C o m p u t a b i l i t y in ~ - ! ~ w + IE o (2.3.1 - 5) - The equality axioms IE I (2.3.6) - Standard c o m p u t a b i l i t y of terms in languages with Cartesian product type (2.3.7) - Computability relative to assignment of functions ( 2 . 3 . 8 - 10) A r i t h m e t i z a t i o n of c o m p u t a b i l i t y ( 2 . 3 . 1 1 - 13)
§
4
Models b a s e d on p a r t i a l r e c u r s i v e f u n c t i o n a p p l i c a t i o n : HE0, HE0 125 Models : normal, extensional models (2.4oi) - Submodel, homomorphism, e m b e d d i n g (2.4.3) - C o n s t r u c t i o n of inner e x t e n s i o n a l models from a r b i t r a r y models of ~-~H~ w (2.4.5) - The s e t - t h e o r e t i c a l model of E - H A w (2.4.6) - D e s c r i p t i o n of HR0 (2.4.8) - The f e r m a l ~ h e o r i ~ HR0, HR0(2.4.10) - D e s c r i p t i o n of HE0 (2.4.11) - HE0 and h~a inner e x t e n s i o n a l model of HR0 are different (2.4.12) - P r o v a b l e f a i t h f u l n e s s of HRO , u n i f o r m l y in type 0 variables ( 2 . 4 . 1 3 - 14) - Closed type I terms of N _ ~ w are ~ p r o v a b l y recursive (2.4.15) - Sketch of a variant of HR0 satisfying ~ - c o n v e r s i o n (2.4.18) - P a i r i n g in HR0, HE0 (2.4.19)
§
5
Term models of N - H ~ A w D e f i n i t i o n of CTM, CTNF, CTM', CTNF' ( 2 . 5 . 1 - 2 ) Some p r o p e r t i e s of CTM, CTNF, CTM', CTNF' ( ) 2 . 5 . 3 - CTNF I is i s o m o r p h i c to a submodel of HRO for a suitable v e r s i o n of HRO (2.5.5) - A l t e r n a t i v e proof of u n i q u e n e s s of normal form (2.5.6) - HRO can be made into a model for .~w + IE I (2.5.8) - E x a m p l e s of versions of HR0 where distinct normal terms are r e p r e s e n t e d by the same element (2.5.9) - IE o is weaker than IE I (2.5.10)
132
§
6
M o d e l s b a s e d on continuous f u n c t i o n a p p l i c a t i o n : ICF, ECF D e f i n i t i o n of ICF(Z~) (2.6.2) - In ICF a m o d u l u s - o f c o n t i n u i t y functional exists (2.6.3) - ICF(~I) contains a f a n - f u n c t i o n a l if ~ satisfies FAN (2.6.4) H e r e d i t a r i l y continuous functionals ECF(~) (2.6.5) ECF(iL) contains a f a n - f u n c t i o n a l if LL satisfies FAN (2.~.6) - E C F does not contain a modulus of c o n t i n u i t y
138
XII f u n c t i o n a l (2.6.7) - A r e c u r s i v e l y well-founded, but not w e l l - f o u n d e d tree (2.6.9) - Provable f a i t h f u l n e s s of ICF u n i f o r m l y in type I v a r i a b l e s (2.6.11 - 12) - The equivalence b e t w e e n ECF(~) and HRO ( 2 . 6 . 1 3 - 21) - KLS holds in H A + M p R (2.6.15 - 17) - Basis t h e o r e m (2.6.19~ - QF-S£~ T holds for ECF (2.6.20) - The models ECFr(U) and ICFrlU) ( 2 . 6 . 2 2 ) - A v a r i a n t of ICF and E C F (2.6.23) - P a i r i n g operators in ICF, ECF, ICF*, ECF*
§
7
E x t e n s i o n a l i t y and c o n t i n u i t y in N - H ~ w 155 E x t e n s i o n a l i t y and h e r e d i t a r y e x t e n s i o n a l i t y ( 2 . 7 . 2 - 4 ) - Derived rules of e x t e n s i o n a l i t y (2.7.5) - C o u n t e r e x a m p l e to the rule of e x t e n s i o n a l i t y when variables of type level > I are present (2.7.6) - Closed type 3 terms of N - H A w are not extensional in every model (2.7,7) - Provable modulus of c o n t i n u i t y for type 2 terms of N - H ~ w (2.7.8) P r o d u c t topology (2.7.9) - "Floating product topology" (2.7.10) Other models of N - HA w The schemata $I ~ 5 9 ~ ( 2 . 8 . 2 2.8.4) - S o a r p e l l i n i ' s models (2.8.5) - Compact and h e r e d i t a r i l y m a j o r i z a b l e f u n c t i o n a l s (2.8.6)
§
9
166 C o m p u t a b i l i t y and models for extensions of N-HA~ w E x t e n s i o n of c o m p u t a b i l i t y t'o' f u n c t i o n a l s of ~ - IDD~w and related theories (2.9.2) - C o m p u t a b i l i t y for barrecursive functionals (2.9.3) - C o m p u t a b i l i t y for Girard's system of f u n c t i o n a l s (2.9.4) - E x t n e s i o n s of HR0, HE0 to models for other systems (2.9.5) - A p p l i c a t i o n of K - HR0 : C o m p u t a b i l i t y of closed terms of ~ - ID~BBw (2.9.6) - E x t e n s i o n of HE0, HEO to Girard's system of f u n c t i o n a l s (2.9.~) - Similarly for ICF, E C F (2.9.8) - Nodels for - ~ + BR (2.9. 9 - 1 2 ) ,
I. R E A L I Z A B I L I T Y A N D F U N C T I O N A L I N T E R P R E T A T I O N S
§i
162
(AoS. Troelstra)
A theme with v a r i a t i o n s : Kleene's FIC 175 D e f i n i t i o n of F|C (3.1.2) - Soundness theorem (3.1.4) - E x i s t e n c e and d i s j u n c t i o n u n d e r i m p l i c a t i o n (3.1.5) IPR e for H~ (3.1.7) - C h a r a c t e r i z a t i o n of CIC by d e d u c i b i l i t y conditions (3.1.8) - CIC respects logical equivalence, and CIC holds for Harrop formulae (3.1.9) - CIC holds also for f o r m u l a e w h i c h are not e q u i v a l e n t tO a Harrop formula (3.1.10) - IP~ is not derivable in H~ (3@Io11) - D i s j u n c t i o n and explicit d e f i n a b i l i t y p r o p e r t y for H A + M p R (3.1.12) - A v a r i a n t of FIC (3.1.13)- IPR for H~ (3°1.15) - A method of d e a l i n g with variables u s i n g partial r e f l e c t i o n p r i n c i p l e s (3.1.16) - Closure u n d e r Church's rule (3.1.18) - E x t e n s i o n and g e n e r a l i z a t i o n of FIC to h i g h e r - o r d e r systems (3.1.19) - FIC for HAS o + P C A , w i t h a p p l i c a t i o n s (3.1.20) - E x t e n s i o n to HAS (3.1.21 - 23) - E x t e n s i o n of M o s c h o v a k i s ' s methods to ID~B, ID~BI (3.1.2%)
XIII
§
2
Realizabilit~
notions b a s e d on partial recursive
function application 188 D e f i n i t i o n of ~ p - r e a l i z a b i l i t y (3.2.2) - E x a m p l e s (3.2.4) - Soundness theorem (3.2.4) - A n a l y s i s of ~ - r e a l i z a b i l i t y ( 3 . 2 . 9 - 19) - The r8le of almost negative formulae ( 5 . 2 . 9 3.2.15) - The schema ECT~ ( 3 . 2 . 1 4 - 15) - I d e m p o t e n c y of r e a l i z a b i l i t y (3.2.16) - ~ h a r a c t e r i z a t i o n of H ~ - ~ - r e a l -
izability (3.2.18- 19) - C o r o n a r i e s
(3.2.20)
-
Realizability
for M a r k o v ' s schema (3.2.21 - 22) - R e a l i z a b i l i t y for TI(<) ( 3 . 2 . 2 3 - 24) - C h a r a c t e r i z a t i o n of HA c - r - r e a l i z a b i l i t y
~ . ~.-2. 28) - Extensions to othe$ systems ( 3 . 2 . 2 9 )
-
R e a l i z a b i l i t y for IDB (3.2.30) - H A S + CT o + U P is consistent relative to HAS (3.2.31) - Some g e n e r a l i z a t i o n s
-
(3.2.32)
- Comparison
ef-~-
realizability with
~-
real-
izability ( 3 . 2 . 3 3 ) §
§
3
4
R e a l i z a b i l i t y notions based on continuous f u n c t i o n application I D e f i n i t i o n of ~ p - r e a l i z a b i l i t y (3.3°2) - Soundness (3.3.3) - Special instances of soundness (3.3.4) - Soundness for IDB (3.5.6) - The g e n e r a l i z e d continuity schema GC (3°3.9) - C h a r a c t e r i z a t i o n of r I - realizability (3.3.13) =
206
Modified r e a l i z a b i l i t y D e f i n i t i o n of m r p - r e a l i z a b i l i t y (3.4.2) - Examples (3.4.3) - Sound~ess t h e o r e m (3.4.5) - C h a r a c t e r i z a t i o n of m r - r e a l i z a b i l i t y ( 3 . 4 . 7 - 8) - Inessential (but convenient) variants of m r - r e a l i z a b i l i t y (3.4.9) - C o m p a r i s o n of H R O - m r r e a l i z a b i l i t y and r - realizability (3.4.11) - m r - r e a l i z a b i l i t y and n o n - r e a l i z a b i l i t y of various s c h e m a t a ( 3 . 4 . 1 2 25) - m r - r e a l i z a b i l i t y of MpR , CT, CTo (3.4.12-13) HA+CT~TZECTo (3.4.14) - WCT is ICF r - m r - r e a l i z a b l e (3.4.15) - m ~ - reali z a b i l i t y of FAN ~ n d WC-N ( 3 . 4 . 1 6 - 19) - m ~ - r e a l i z a b i l i t y of BI M ( 3 . 4 . 2 0 - 21) - m r - r e a l i z a b i l i t y of + TI(<) (3.4.22 - 25) - M o d i f i e d r e a l i z a b i l i t y for HAS 3 . 4 . 2 7 - 28) - C h a r a c t e r i z a t i o n of provably recursive f u n c t i o n s (3.4.29)
213
~
§
5
The D i a l e c t i c a i n t e r p r e t a t i o n and t r a n s l a t i o n D e f i n i t i o n of the D i a l e c t i c a t r a n s l a t i o n (3.5.2) - M o t i v a t i o n (3.5.3) - Soundness t h e o r e m (3.5.4) _ N_~W is not D i a l e c t i c a i n t e r p r e t a b l e in itself ; d e c i d a b i l i t y of prime formulae (3.5.6) - A x i e m a t i z a t i o n of D i a l e c t i c a i n t e r p r e t a b i l i t y ( 3 . 5 . 7 - 11) - The interp r e t a b i l i t y of the e x t e n s i o n a l i t y a x i o m ( 3 . 5 . 1 2 - 15) - D i a l e c t i c a i n t e r p r e t a b i l i t y of CT, CTo, C - N , FAN, IP (3.5.16) - The D i l l e r - N a h m variant of the D i s l e c t i c a i n t e r p r e t a t i o n (3.5.17) - Shoenfield's variant (3.5.18) - E x t e n d i n g the D i a l e c t i c a i n t e r p r e t a t i o n to stronger systems ( 3 . 5 . 1 9 - 21) - Church's thesis and bar r e c u r s i o n (3.5.20) - Girard's e x t e n s i o n (3.5.21)
230
§
6
Applications: c o n s i s t e n c y and c o n s e r v a t i v e extension r e s u ~ Conservative extension results ( 3 . 6 . 2 - 9) - A x i o m s of choice for HRO, HEO ( 3 . 6 . 1 0 - 16) - E x t e n s i o n s to analysis ( 3 . 6 . 1 7 - 20)
250
XIV
IV.
§
8
Markov's schema and ~ r k o v ' s rule Forms of Narkov's schema and rule (3.8.1) - Not all negations of almost negative formulae are ~ e g a t i v e (3.8.2) - HA + ~ M p R is consistent and closed under Nl°pR (3.8.3) - Characterization of MpR (3.8.4) - Validity of MR ~ , MR in various systems (3.8.5) - HA and HA c have the same provably recursive functions (3.~.6) M~"~I'~ for systems stronger than arithmetic [3.8.7)
263
§
9
Applications of ~ - r ealizabilitF Definition of ? - realizability (5.9.2) - Soundness theorem (3.9.4) ~IJ~A ~vLKLSI ( 3 . 9 . 5 - 12) - Some other results on KLS and the corresponding rules (3.9.12).
267
N O R N A L I Z A T I O N THEOREMS (A.S. Troelstra)
FOR SYSTENS
OF NATURAL
DEDUCTION
§
I
The strong normalization theorem for HA Notational conventions about proof trees (4.1.2) - Description of the reduction processes (4.1.3) - Definitions of thread, segment, maximal segment, normal form, strictly normal form, reduction sequence, reduction tree (4.1.4) - Remarks on reductions, normal deductions (4.1.6) - Strong normalization for ~ ( 4 . 1 . 7 - 18) - Definition of strong validity (4.1.9) Each strongly valid deduction has a finite reduction tree (4.1.13) - Definition of strong validity under substitution (4.1.15) - All deductions are strongly valid under substitution (4.1.16 - 17) - Uniqueness of normal form of deductions ( 4 . 1 . 1 9 - 21)
275
§
2
Appliqations of the n o r m a l i z a t i o n theorem 299 Definition of path and spine ( 4 . 2 . 2 - 3) - Structure of path and spine in normal deductions ( 4 . 2 . 4 - 8) Disjunction and explicit definability property ( 4 . 2 . 9 - 12) - The rule IPR without parameters (4.2.13) - Narkov's rule NRpR (4.2.14) - Disjunction and explicit definability property for H ~ + N p R ( 4 . 2 . 1 5 - 17) - Conservative extensions over quantifier-free fragments ( 4 . 2 . 1 8 - 19) - Reflection principle for closed Z ~ - formulae (4.2.20)
§
3
N o r m a l i z a t i o n for I~ + IP with applications Strong n o r m a l i z a t i o ~ f o r H A + IP 14.3.1 - 2) - Definition of spine (4.3.3) - Structure of spine in normal deductions ( 4 . 3 . 4 - 5) - Disjunction and explicit definability property for ~ + IP (4.3.6)
§
4
Formalization of the normalization theorem~ with applications Formal definition of strong validity (4.4.2) - Theorem on arithmetization of normalization (4.4.3) - Closure under IPR with parameters (4.4.5) - Closure under Church's rule (4.4.6)
307
311
XV
§
5
Normalization for second order logic and arithmetic The system M2(S ) (4.5.2) - Formalizing t~e proof of the normalization theorem (4.5.3) - Construction of a satisfaction relation ( 4 . 5 . 4 - 6) - Properties of the satisfaction relation ( 4 . 5 . 7 - 9) - Partial reflection principle (4.5o10) - Applications (4.5°11) - HAS is closed under a rule of choice from numbers to species
315
(4.5.12). V.
APPLICATIONS
OF KRiPKE
MODELS
(CoA.
Smorynski)
§
I
Kripke models Discussion (5o1.1) - Definition of Kripke models (5.1.2.) - Some basic properties of Kripke models (5.1.3) Examples (5.1o4) - The completeness theorem ( 5 . 1 . 5 - 11) - The Aczel slash ( 5 . 1 . 1 2 - 18) - The operation ( ) ~ (Z)' ( 5 . 1 . 1 9 - 21) - Nodels with equality ( 5 . 1 . 2 2 - 23) Function symbols (5.1o24) - I n t u i t i o n i s m ? (5.1.26)
524
§
2
The treatment of Heytin~'s arithmetic The class of models of H~ is closed under the operation ( ) ~ ( Z ) ' ; disjunction and explicit definability property (5.2.1 - 4) - Applications of the operation ( ) ~ (Z)' ( 5 . 2 . 5 - 8) - Formulae preserved under
339
§
3
( ) ~ (~)' (5.2.9- 12) - Examples. Reflection principles and transfinite induction ( 5 . 2 . 1 3 - 23) Additional information from ( ) ~ (z)': de Jonah's theorem Statement of de Jongh's theorem (5.3.1 - 2) - Preliminaries on the propositional calculus ( 5 . 3 . 3 - 8) - Lemma on Jaskowski's trees (5.3.9) - The G o d e l - R o s s e r M o s t o w s k i - Kripke-;~Tyhill theorem ( 5 . 3 . 1 0 - 12) - de Jongh's theorem for one propositional variable (5.3.16 - 19) - Another theorem of de Jongh ( 5 . 3 . 2 0 - 22) - Further results on de Jongh's theorem (5.3.23)
348
§
4
Markov's schema Markov's schema (5.4.1 - 5) - Independence of MP ( 5 . 4 . 4 - 6) - A comment on proof-theoretic closure properties ( 5 . 4 . 7 - 9) - The operation ( ) ~ (Z + w)' ( 5 . 4 . 1 0 - 14) - The class of models of ~ + ~ is preserved under ( ) ~ (Z + ~)' (5o4.11) - HA +NDP possesses ED, DP (5.4.12) - Closure properties of the class of sets F such that validity of ~.~+ F is preserved by ( ) ~ (Z + w)' (5°4.13)
360
§
5
The schema IP~ Proof-theoretic closure results ( 5 . 5 . 2 - 3) - Mutual independence of ~P and IP~ (5.5.4 - 7) - Final comments on I P ~ (5.5.8) - Uniform independence of
369
iP~, ~ §
6
(5°5.9)
Definability of models of ~ c : appliqations The operation ( ) ~ (Z)* (5.6.1) - Definability ( 5 . 6 . 2 - 7) - The H i l b e r t - B e r n a y s completeness theorem ( 5 . 6 . 8 - 9) - The O o d e l - R o s s e r - M o s t o w s k i - K r l p k e ~lyhill theorem revisited ( 5 . 6 . 1 0 - 12) - Z,-° substitution instances in de Jongh's theorem (5.6.13 - 16) -
372
XVI
- de Jongh's theorem for MP (5.6.20- 22) - Other applications (to systems with RFN(~), T I ( < ) ) (5.6.23- 26) §
VI°
7
Other systems Subsystems of Heyting's arithmetic (5.7.1 - 2) - Extensions of HA: Theory of species (5.7°3) - Other set-theoretic approaches (5.7.4)°
388
ITERATED INDUCTIVE DEFINITIONS, TREES AND ORDINALS (J.I° Zucker) §
I
§
2
Introduction
The systems
392
~2(A)
397
Inductively defined sets of numbers (6~2°I) - The class ; the theory ID2(A ) for A E ~ ; c definition of the ordinals II,~D2I,qI,...,..D~I, II~II, I~,1 (6.2.2) §
3
The theor# ~2 An intuitionistic theory of trees of the first 3 number or tree classes
401
§
4
Computability of closed terms of ~2 Definitions (6.4.1) - Uniqueness of normal form (6.4.3) - Standard computability (6.4.4) - Proof of computability of closed terms (6°4.5 - 7), and hence of their normal-
404
izabiiity (6°4.8) (6.4~o)
Definition of the ordinal
ItlC
§
5
Strong computability Definitions (6.5oi) - All closed terms of ~2 are strongly computable (6.5.2- 11), and hence strongly normalizable (6o5.12) - Hence all terms of T 2 (not necessarily closed) are normalizable (6.5.13~
408
§
6
Models of T2 ; modelling ~2 in ID2(~) Definitions~(6.6- I - 3) - Exampl~s o ~ w e l l - f o u n d e d models : ~2, HR02, HE02 and CTNF 2 (6.6.4) - Extensionality: some general remarks (6.6.5) - Distinctions between well-founded models of ~I and T2 (6.6.6) - Definition of the ordinal I ~ 2 1 (6.6.7) - Theorem: I~21 ~ II~D21
413
(6.~.8)
§
7
Functional interyretation of I~D2(A) Introduction ; definition of modified realizability (mr-)interpretation, the theories T g [ P ] , E - ~2~ e t c . ( < 7 . 1 ) - Pairing functions (6°7.2)-~ Norm~l forms for translations of A E G (6°7.3) - Axioms for PI and P2 (6°7.4) - "Soundness theorems" for interpretation (6.7.5-7) - Theorem: 1~21 < Im21, ( 6 . 7 . 9 ) - Hence main result: |L~al = I~21 (L7.I0~ - Note on extensionality axioms (6.7.11)
421
§
8
Functional interpretations of classical systems IDa( ) ~nd I ~ (m) Introduction ; definitions of ~v((~), ID#((~), ID~(O) (v = 1,2) and the ordinal I~II (6"8"1T- Func~onal interpretations (modified realizability and Dialectica)
435
of
I~DI(O )
and I.,,,D~(O') ( 6 . 8 . 2 - 3) -
XVII
-
Proof
/ IDol = 1 ~ i '
that
technique
(6.8o~-'~)
usin~ a majorizin~
- Historical
survey:
other
methods of characterizating liDS1 (6.s.6) Ftmctional interpretations of ~ 2 ( O ) and I D#(O) ;
un~o~
§
whether
II~l : I~21 (~.8.7- 11)
9 Extensions to
IDa(A) and IDa(A) ~ v> 2. Equivalences with some subsystems of classical analysis Generalization of result to II.Dgl =tier I for certain > 2 ; equivalence of various I~D~(A) with subsystems of classical analysis ; unknown whether II-~D~I = I~vl for ~ > I (6.9.1) - Positive result : c £ II~D<wl = IID<wl (6.9.2) - Theory W - IDw(A ) equivalent tO classical analysis + H~- CA (6.9.3)
APPENDIX : HEREDITARILY (W°A. Howard)
}~JORIZABLE
FUNCTIONALS
OF FINITE TYPE 454
§
I
§
2
Hereditarily
§
3
Primitive recursive functionals
§ 4
45o
Extensionality majorizable
Discussion of
VyE3(y)
functionals
455 457 460 462
BIBLIOGRAPHY INDEX I.
II.
List of symbols A)
Formal systems
476
B)
Schemata and rules
476
C)
Syntactical
478
D)
Other symbols
List of notions
variables
478 482
Chapter I INTUIT!ONISTiC F O ~ A L
SYSTEMS
§ I. ~ ! ~ ~ = ! ~ " 1.1.1.
Contents.
In the present section we describe logical notation and
systems for intuitionistic predicate logic to be used in the sequel.
The
reader already acquainted with these subjects may skip them and use them for reference only.
We shall presuppose acquaintance with classical predicate
logic and the treatment ef "elementary" metamathematics of Classical systems, and elementary recursion theory (for example, as found in Kleene 1952).
In
the sequel, proofs in formal systems are usually not set out in a completely formalized form, but we compromise between readability and rigour ; i.e. the proof is described in sufficient detail so as to make full formalization a routine matter ; but we try to avoid an excess of detail which obscures the underlying idea. In view of this aim, we usually freely employ theorems and rules of intuitionistic predicate logic, whose proof is not to be found in this monograph. For the reader with little previous acquaintance with intuitionistic reasoning, we recommend Heyting 1956, Chapter VII and Troelstra 1969, § 2 for intuitive background,
and Kleene 1952 for formal details.
~remark
here only
that in order to convert an intuitive proof of an intuitionistic logical theorem into a formal argument,
the system of natural deduction described in
1.1.7 is usually very convenient° In agreement with the attitude towards formalization described above, the description of formal systems for intuitionistic predicate logic below does not serve as a basis for deductions in the formal systems to be studied, but as a reference for metamathematical arguments proceeding by induction on the length of deductions.
Nevertheless,
the discussion
is fairly detailed,
to
enable a reader without experience with intuitionistic formal systems to get accustomed to them.
In later sections and chapters the development gradually
becomes more condensed. Ioi.2. (i)
Some notational conventions° As logical symbols we use
&, V, ~, V, --,~
mathematical abbreviations we use Definitions
~, ~, [, ~, 6, ~ ,
(or abbreviating expressions)
acter are usually indicated by
(absurdity) ; as metaetc.
of a more or less permanent char-
~def ; ~ .is used for definitions or abbre-
viations of a more local character (i.e. within a certain argument), express syntactical
identity.
and to
(ii)
x, y, z, u, v, w
(provided with sub- or superscripts if necessary)
will be used as syntactical variables for variables ; in systems containing arithmetic they are usually reserved for numerical variables.
In the sequel
we shall often have to introduce other categories of symbols as syntactical variables for certain sorts of variables in the formal systems studied. Usually we do not use separate sots of symbols for free and bound variables,
with the exception of systems of natural deduction, where we feel
the notational distinction between variables)
(bound)
to be a definite advantage.
a, b, c, ...
variables and parameters
(free
In this case, lower case letters
from the beginning of the alphabet are used to indicate para-
meters. (iii)
Capitals
(primarily from the beginning of the alphabet)
are used as syntactical variables for formulae,
t, s
denote terms (with an exception in chapter IV, where
A, B, C, ...
will be used to s
is reserved for
successor). Variables
x, y, z, ...
a term
are indicated by the use of square brackets
(iv)
t
occurring free (perhaps only as dummy variables)
In all categories of variables introduced,
in
t[x], t[x,y] , etc.
gub- and superscripts may
be added to create more variables of the same category. (v)
Syntactical descriptions of the classes of formulae and terms, in
our various formal systems, are as usual ; if we wish, we may assume the actual notation to be bracket-free in godelization)
("Polish" notation, which is convenient
and think of the usual notations with brackets as "abbre-
viations" for better readability.
Our bracketing conventions are us usal :
unary operators bind stronger than binary ones, ~.
V, &
bind stronger than
In general, we shall omit brackets whenever we can do so without impair-
ing readability. (vi)
Some abbreviations :
~A ~defA~A,
=def ( A ~ ) & (3~A),
A~
VXI"''XnA ~def VxIVx2"''VXn A ' VxEA(B)
~def Vx(Ax ~ B) ,
~x1~''XnA ~def ~x1"''~XnA ' ~xEA(B)
Also in formulae, we sometimes use unary predicates (vii)
x EQ
~def ~ x ( A x ~ B ) . as an alternative to
For substitution of a term
sort) in an expression
t
Quite frequently,
for a variable
x
(generally a term or a formula)
(especially in chapter IV) we writs
[x/tiE,
where
(t, x
for
of the same
or in a deduction
E
is the expression.
when there is no danger of confusion, we shall also
use the more imprecise convention that whenever an expression been introduced,
Qx,
Q.
E(t)
we use square brackets:
denotes t[x,y],
[x/t]E.
E(x)
has
For variables occurring in terms
etc. ; in contrast,
if
~
is a function,
q0t
or
~(t)
(viii)
stand for
~
applied to the armament
t o
Formal systems will be indicated by capitals or combination of
capitals with a wavy underlining (e.g. The language of a formal system formed formulae by
Fm(H)
or
H
FmH,
H~,
qf-~-N~A ~,
is denoted by
~
etc.).
~(H) , the set of well-
the set of theorems by
Thm(H)
or
ThmHo Deducibility in AE H
H
is indicated by
means the same as
H ~A ,
also interpreted as usual. either If in
HU F ~
~,
or
constants of
or, rarely, as
~H
A
is a theorem of
H.
If we add to
H
a set of axioms
F,
o H~HI
is
we write
H + F.
denotes a given language, and we write
H ~
i.e.
~P]
P
a predicate letter not occurring
for the language obtained by adding
P
to the
~°
Similarly, if
H
is a formal system, presented by giving a set of rules,
axioms and axiom schemata,
~[P]
is the system with language
~(~)[P] ,
with the same rules, axioms and axiom schemata (i.e. the schematic letters in an axiom schema now stand for formulae of the extended language). (L~Church's
k - n o t a t i o n will sometimes be used informally to indicate
functions or predicates.
1.1.3. Spector's s~stem. The systems for intuitionistic predicate logic described in this and the next section are "Hilbert-type systems", i.e. based on logical axioms and inference rules. his
The present system, taken from Spector 1962 (leaving out
A2 , in view of footnote 7 on page 10 of Spector 1962), is given by the
following axioms and rules : PL I)
A-~A
PL 2)
A,A-~B = B
PL3)
A-~B, B-~C ~ A - ~ C
PL4)
A &B-~A,
A &B-~ B,
A-~A VB,
PL5)
A-*C,
B-~C = A V B - ~ C
PLg)
A-~B,
A-~C ~ A - ~ B & C
PLS)
A~(B--C) =A~B--C
PL 9)
A-~A °
and for predicate logic ( x C
not containing
x
free)
Q Ii)
B--A(x) ~ B - - W A ( x )
Q 21 ) Q 3i)
VxJ~x-~At At-~ XxAx
B-~A V B
a variable of sort
i ~ t
a term of sort
i ,
Q%i)
Ax~B
= SxAx~Bo
In applications assumptions
of
Q Ii
comtaining
and Q 4 i x
the premiss is supposed not to depend on
free, i.e. has been derived without the use of
such assumptions. 1.1.4.
G~del's systemo
For the purpose of verifying interpretation
the soundness
of the so-called Dialectica
(see chapter III), Godel suggested another system, based on
QI-Q4,
PL2,
3, 7, 8, 9 and
PLI0)
AVA~A~
A~A&A
PL11)
A~A
VB,
A&B~A
PL12)
AVB
~ BVA,
PLY3)
A~B
~ C VA ~ CVB.
A&B
~ B&A
This system has the advantage
of keeping complexities
in the rules and axioms there appear fewer logical previous 1.1.5.
down to a minimum
(i.e.
symbols than in the
system). E~uivalence
of Spector's and G~del's
In Hilbert- type systems, tions be represented
we may either suppose deductions from assump-
as finite
sequence being an axiom,
system.
sequences of formulae,
an assumption,
each formula of the
or obtained from formulae appearing
earlier in the sequence by means of a rule of the system.
(This form is
often quite convenient for actual arithmetization ; however, noted that in some cases it is more natural volved to be indicated pictori~ representation
it should be
to suppose the rule or axiom in-
explicitly at each element of the sequence).
A more
is by means of deduction trees, which we shall use
below. It is perhaps useful to remark already here, themselves
that in case the proof trees
are objects of study (as in chapter IV) we must think of them as
being completely presented by a tree of formulae together with an indication which rule or axiom is applied at each node.
However,
in presenting proof
trees pictorially below, we shall not always explicitly indicate used,
the rules
so as not to encumber typography.
A proof given as a sequence may be thought of as being obtained by consistently extending the partial order of the tree to a linear order. If F
~g
denotes deducibility
a set of assumption formulae,
in Spector's
system,
~G
in G~del's
sense that r~A
~
F~GA
(for first- and higher-order
system,
then the two systems are equivalent in the
languages,
o n , or many-sorted)
F ~sA PL I)
(F~ 3)
follows by the f o l l o w i n g d e d u c t i o n s :
A-~A & A
(PLIO)
A &A-~A
(PL11)
A-~A
PL 4)
A&B~A
(PL 3)
is the second half of
PL11
(PL12) B&A~B
(PLll)
A&B~B&A A&B~B
(PL 3)
A~AVB
is the first half of
B~BVA
(PL11)
BVA~AVB
PL11 (PL12)
B~AVB
PL
5)
(PL13) A-~C (ass) (ps 3)CVA-~CVC Cvc-~C (PZlo) (PL13) B-~C (ass)(PL12) AVC-~CVA CVA~C (PL 3) Av~-~AvC AVC-~ C (pT, 3) AVB
-~ C
(PL I
P~ 6)
deduction)
B&C~B&C (C~B&C) A ~ (C~B&C) (PL (PL12) C & A ~ A & C A&C ~ B&C (PL C&A ~ B & C (PL 7) (ass) ~ c C~(A~B&C) ( ~ 3) A~ (A~B&C) (PL 8) (PLIO) A ~ A & A A&A--B&C (PL 3) (ass)
A ~ B
B~
(p~ 7) (PL 3) 8) 3)
A ~ B&C Conversely,
PLIO)
we v e r i f y that A -" A
~$A
A -~ A
= ~ ~GA
(PL 5)
AVA--A PL11)
is part of
PL12)
(PL 5) B - ~ A V ~
by the f o l l o w i n g d e d u c t i o n s :
A~ A A -~ A & A
PL 4.
BVA
(P~ 4)
A-~AVB
(P~ 4)
A&B~A
(PL 4)
-* A V B
(P~ 6) A & ~
(PL 4) A&B
-~ B & A
A ~ A
(PL 6)
PL13)
(ass) A--B B--CVB (PL4) (PL 3] A - CvB (PL 5)
(PL4) C-- CVB
C VA
1.1.6.
~
C VB
Equivalence of Spector's and Kleene's formalization.
Yet another Hilbert-type system is described in Kleene 1952, chapters IV, V.
The equivalence with Spector's Warning.
system is proved in Specter 1962.
In one respect our conventions differ from Kleene's : Kleene
1952 permits application of Q I, Q 4 assumption formulae
also when the variable occurs in
(i.e. the assumption formulae are treated as if they
are universally closed) ; if Kleene wishes to indicate that certain variables are to be treated as parameters,
and hence are not permitted as proper
variables of an application of Q I, Q 4 the notation 1.1.7.
("variables held constant") he uses
~x1°''Xn
A natural deduction system.
We now distinguish between parameters and (bound) variables. shall use
a, b, c, ...
for the parameters,
x, y, z, .o.
Below, we
for the variables.
We describe the system briefly (a detailed and rigorous description is in Prawitz
1965 ; more briefly in Prawitz
1971).
The rules may be schematically described as follows : AI)
A
B
&El)
A&B
~r)
A AVB
--I)
¢
A&B A
AEr)
B
~l)
A&B B
VE)
~ AVB
~ vB
C
C
c "E)
A
A'B
B A..-, B
VxAx
At
gx.Ax
~
ZxAx ZxAx
C C
mz
~--A
In the explanations below, it should be taken into account that we are primarily concerned with formula ~ccurrenees
(foVs), i.e. a formula together
with a position in a tree-like arrangement of formulas. rence
A "
means "an occurrence of the formula
A " .
"A formula occur-
We shall sometimes
loosely use "formula"~ when~ as is apparent from the context, formula occurrences are meant.
The I - r u l e s rules,
are called introduction rules, the
elimination
since a logical constant is introduced in the conclusion,
ly eliminated from a premiss. .4 I"
E-rules
So we sometimes write . 4
respective-
introduction " for
etc.
We suppose deductions to be represented in tree form ! the top formulas of the tree are then the assumptions,
and the (uniquely determined)
formula (occurrence) is the conclusion of the deduction.
end
Each formula occur-
rence is either a top formula, or the conclusion of an application of one of the inference rules, its immediate predecessors being the premisses in the application of the rule.
At applications of
VE, ~E, ~I
certain assumptions
(of the form indicated by the formulae crossed out in our list of rules)are discharged ; a discharged assumption is said to be closed (by the inference). Only assumptions which have not been discharged previously of the proof tree above the one considered)
(i.e. at a node
can be discharged.
also be stressed that not necessarily all assumptions cf the same form occurring above the application of
It should
(possibly even none) VE, ~E, ~I
are dis-
charged. We shall think of the assumptions
to be grouped into assumption classes;
each assumption class consists of a number of occurrences of the same formula. All formulas of an assumption class are always treated simultaneously,
i.e.
at each application of a rule in the deduction either all formulas of the class are discharged or none of them is discharged. A formula occurrence above
A
A
is said to depend on the assumptions
that have not been closed by some inference above
In the applications of tions containing
a,
VI
the premiss
Aa
and in an application of
the upper occurrence of
C
containing the parameter
standing
A .
must not depend on assump~E
of the form
~xAx
must not depend on assumptions other t h a ~ a.
In applications of
~,
~I
a
C , Aa
is called the
proper parameter of the inference ; a parameter is a proper parameter of a deduction
if it is used as the proper parameter of an
VI, ~E
inference.
The open assumptions of a deduction are the assumptions on which the end formula of the deduction depends.
A deduction is said to be closed if there
are no open assumptions° We shall always assume a completely described deduction to have specified at each node which rule is being applied, and for the assumptions malae), at which inference
(top for-
(if any) they are discharged.
With respect to the rules, we wish to introduce some further terminology. In an application cf an
E-rule,
the constant to be eliminated, the other premisses,
the premiss containing the occurrence of
is called the major premiss of the inference ;
if any, are called minor premisses.
So, in our list of
inferences above, &E, VE, ~E,
A&B,
VE, ZE
A VB, A ~ B ,
respectively.
application of an
I - rule or ~ I
VxAx, ~mAx
are the major premisses of
It is convenient to call any premiss of an also a major premiss.
It will be obvious that deductions which only differ in the naming of their proper parameters may be regarded as assentially the same.
It is easy to
verify that we may always select our proper parameters so as to satisfy the following requirements, (cf. Prawitz (i)
for a given deduction
[
The proper parameter of an application H
(ii)
of
A
from assumptions
~
of
VI
in
H
only in formula occurrences above the consequence of
The proper parameter of an application
~
of
ZE
in
(iii) Every proper parameter in application of the Examples.
H
Vl-rule
occurs in ~o
H
only in formula occurrences mbove the minor premiss of
1.1.8.
F
1965 , chapter I, § 3).
occurs in ~.
is a proper parameter of exactly one or the
ZE-rule
in
H.
We give some examples of deductions in the system of
natural deduction ; the theorems derived will be used later on (§ 10). In the examples,
"(ass)" marks an assumption which is not discharged
"open") in the deduction. number "(I)",'<2)", number.
Assumptions which are discharged are marked by a
etc., all assumptions in the same class getting the same
This number is then repeated at the application of a rule where the
assumption is discharged. I)
(i.e.
(I) A
A -- B (ass) B
B~A
(I)
If)
WA~(1 ) (2) -~ A a
Aa
-~E
A (3) ~ ~ VxAx
~ VxAx A -1~Aa
-i (I) -~E
- I (2) vl
Vx -7-IAx -~ I ~
VxAx -~ Vx -~-~Ax
(3)
zzx)
(1) A
(2)
~A
A (3) m m ~
A
Since also
A--B
z,,
(2) (-1)
"mA ~
"7-7-qA
it follows that mmmA
°
(I) (3)
= (A-~)
(4) A I~I~B
(3) (2)
A -~ -~-7B
-~
(2)
" ~ - q -q A
mA ~
-~B
(I) A
7mA
(2)
-7-~mA -~ m A
(2) A
mi
-.-i--1 A
__A (~) mA (3)
IV)
(1)
(4)
(2)
~k B
(I) _ _
m (A-* B)
A-~B
(~)
(4)
]k
B
-7mA
(2)
mmA
-~ m - 7 B
(5)
x,(3)
-~-~ (A- B) (4)
of
~I
(4)
mB
-TmB
An application
-~ (A- B)
A-*B
(5)
.
in (I) y i e l d s
(~A -- ( T m A
~ ~mB) -- m m B )
(III)
and thus
V)
-7-7(A&B)
-~ m m A
& m-IB
may be proved very similarly
to II.
10
(I) A
Further
A&B
(~) ~ A & B (4) ~-~A & ~ B
B (2)
A
(~)
-m-mA
A :B
& -~-~B ( 4 )
~A
(2)
-~'q B
A
(3) (4)
Hence I. I. 9.
The following schemata and rules are derivable in Spector's
Lemma°
system : (a)
A-
(b)
A = B - A
(B--A)
(o) A ~ B , A--(B--C)=oA--C (d) [(A-- (~--C)) & (A-~B)] & A--0 (e) ( A - (B--C)) -- [(A--B) -- (A-O)I (f) [ ( A - - B ) - (A~C)]-- (A--(B--0)) (~) A - - ( B ~ O ) , A - (c-D) = A - - ( B - D ) (h) #-- (B--C) = B - - (A--C) (i) (A-c) & (B-c) - (A vB ~ o) (j) (A-~) - [(A-o) - ( A - - ( ~ C ) ) ] (k) A -- (B& O--D) = A -- (B--(C--D)) (l) A-- ( B ~ ( C - - D ) ) = A - (~& c-D)) . Proof. (a)
From
A&B
(b)
I=ediate
(o)
A-A
~ A
(PL4), A ~ (B--A)
from (e) with
(PLI)
A-~
by (PL7).
PL2o
(ass)
A~A&B
A--(B~C)
ass
A&B--C A~C
(d)
~e put
B ~ [A -- (B ~ C ) ] & ( A ~ B ) ,
{~Lq) :., ~
B -- (A--B)
A
B (PL4)
: -- ( A ~ ( B ~ C ) )
(PL4)
Here we have used an abbreviated notation for the proof tree ~ (0) next to a horizontal line indicates that the line represents a part of the
11
proof tree of the same f o r m as for the part of (c) above. words, we use
(c) as a derived rule to a b b r e v i a t e
Similar conventions
(e) (f)
our p r o o f trees.
are u s e d below.
A p p l y PL7 twice to (d). We put
D m (A--B) -- (A--C),
E m (D&A)
E -- D (PL4, PL4, PL3)
E -- A (PL4, PL4, PL3) E --
C
A - ( B - c) (ass)
(A-B) -
(PL4)
(c)
(f) is obtained by two a p p l i c a t i o n s
(g)
& B°
D -- (A--C)
E -- (A--C)
of PL7 to
A - (c-D)
(A--C) ( ( e ) ,
PL2)
(A--B) -- (A--D)
E-- C .
(~ss)
(A--C) -- (A--D) ( ( e ) , P~2) (PL3)
(f)
A - (B-D) (h)
B&A
-~ A B&A
B&A
A~
-~ B
-~ A & B
(B~C)
A&B~
B&A~
ass
C (P~3)
C
B - ( A - c) (i)
Let
D
m (A ~ C )
& (B~C) ,
D - ( A - c) (h) A - ( D - c)
E ~ A VB ~ C
D - ( B - c) (h)
B-
( D - c)
A v B -- (D-- c) (h) D--E
(J)
Let
D ~ (A-,B) & ( A - - C ) ,
-- A
~ -, (A-, B) (e)
~ -= D&Ao ~ --, A
E-~B
E -, (A-, C) (e)
E-~C E-~ B&C
]) --, (A -, B & c )
(A-, ~) --, [C.A--' c) -, (A-, B&C) ] (k)
By r e p e a t e d use of PL4, PL3
(A&S) & C --' A ~ ( B ~ C)
A -- (B & C -, D) ( ~ s ~ ) (A&B)
& C -- A & ( B & C ) (A&B)
& C ~ D
(A ~ B ) -- ( C ~ D)
A & (]~&C) --, ])
In other
12
(1)
Similar to (k), but arguing in the inverse direction.
1.1.10. Deduction Proof. of
theorem for Spector's
We write simply
deductions
for
kS"
A~B
from
F, A ~ E B
B
from
F U {AI
itself and therefore
either
I n the f i r s t
ease ,
Fb
B ,
In the second case,
F ~
AHA
by PLI .
In the third case ,
F ~
A--B
by 1.1. 9 (b).
~p.
of length
~k,
can be transformed
F o
The deduction has length I ; then the deduction
Induction
= F ~sA~B"
We show, by induction on the length
, that a deduction of
into a deduction of Basis.
~
system.
B 6 ~,
or
B ~ A , or
B
hence by 1 . 1 . 9 (b)
consists of
B
is an axiom.
F ~ A~B.
Assume the assertion to have been proved for all deductions and let
At, ..., Ak, B
thesis, we have already
shown
be a deduction.
F ~ A~A i ,
If
B
is an axiom, or belongs
If
B
is obtained from the
to
A
By induction hypo-
I < i < k.
F U {A},
we proceed as for the basis step.
by application
of a rule, we must distin-
1
guish various Case PL2 : (1.1.9
Aj
(e))
Case PL3 :
cases.
~A l --S
A i ~ A~A
r b (AM(A''A''))' r~
"
~e have
F~A--Ai,
r~A--
(Ai--B);
r ~ [A--(Ai--B)] -- [(A--Ai)-- (A--B)] , hence '' , A.$ ~ A " ~ A ''' ,
r b
(A-- (A"--A'")) ;
B ~ A'--A'" .
application
of
also
F ~ A--B. ~e have 1.1.9 (g)
yields
A'(A'--A'") o
Case PL5:
Assume,
by hypothesis
~hen r ~ A - - [(B--D)~(C--D)] W[(B'D)~(C'D)]'[(BVC)'D]
r ~ A -- (B--D) ,
~ ~ A -- (C--D) .
(1.1.9 ( j ) ) , a~d (1.1.9 ( i ) ) . so
rbA--[(SvC)--B]
(P~3). Case PL6 :
Similarly,
Case PL7 :
Use 1.1.9 (k)o
Case PL8:
Use 1.1.9 (i).
Case QI
:
Use PLS:
Assume F~
A&C
using 1.1.9 (j).
F ~ A -- ( C ~ B x ) ,
F,
A
-- Bx ; then apply Q1 :
not containing
F ~ A&C
~ VxBx,
x
free.
and thus by PL7
r ~ A - (C--VxSx) Case Q4 : apply Q4 :
Assume F~
F ~ A -- (Bx--C) o
~Bx--
Use 1 . 1 . 9 ( h ) ,
so
(A--C) ; apply 1.1. 9 (h) a g a i n to o b t a i n
r ~ A - (~Sx-- C). 1oto11. Theorem. system.)
P ~N A i f f
from assumptions Proof.
(Equivalence
F
F ~5 A
between natural deduction and Spector's
( F ~NA
indicates
in the natural deduction
First we show that if
F~gA
,
then
that
A
can be deduced
system). F~NA
matter : we have to show that (a) for the axioms
A
.
This is a routine of Spector's
system,
13
~ N A , and (b) that for an instance of a rule system there is a deduction deductions
in
~N
FI,F2 ~ N F 3
FI,F 2 = F3
in Spector's
(in fact, as we shall see, the
for axioms and rules are uniform in the formula variables
used to describe the axiom (schemata)
and rules).
For example, A
is represented by the natural deduction proof A
A ~ B V C
and the rule
Vl
v B
A-~AVB
(PL5) by
A
A-- C..E
AVB
B
etc., etc.
B-~ e
C
C
VE
C AvB-~ It remains
-~I
C
to be shown that
ffF.~NA
,
then
have to show that each rule of the natural to a derived rule in Spectorts
system.
F~sA
°
To see this, we
deduction calculus
For example,
for
vE
corresponds we have to
show : If
F,A
By the deduction
rksAvB-c,
~S C,
F, B ~ S C,
theorem,
F ~S A M C ,
sowithP~
The only crucial case is
then
F,AVB
F ~s B~C,
~S C° and with PL5,
r,AV~sC.
~ I ,
but this is provided by the deduction
theorem. 1.1.12. Remark on the e~uivalence
proofs in 1.1.11 and !°Io5 under addition-
al axioms. The equivalence
proofs remain obviously valid if we add further axioms
(in the case of the natural deduction
system,
formulas but are not counted as assumptions). rules, however,
the equivalence
of the deduction theorem for Spectorls
1.1°13.
system,
essential
in 1.1.11, has to
of further cases corresponding
to the
rules.
Sequent calculi.
We do not make use of Gentzen's (cf. Gentzen 1935 , Kleene is referred to Prawitz 1.1.14.
In the case of additional
proofs have to be extended ; e.g. the proof
be extended with the consideration additional
axioms may appear as top
Convention
istic system).
If
1952 , § 77) ; for an equivalence proof the reader
the classical
is any formal
sorted) predicate logic, al (many-sorted)
and its variants
1965 , Appendix A.
(for indicating ~
calculus of sequents
predicate
~c
equivalent
of an intuition-
system based on intultionistic
denotes the corresponding
logic (,c,, for "classical").
(many-
system with classic-
14
§ 2.
~
1.2.1.
2
~
7
~
=
~
~
=
~
Contents of the section.
some theorems on definitional text becks,
~
=
~
~
"
In this section we have brought
extensions,
together
which are not emphasized
but which will be used quite frequently in this volume,
explicitly or implicitly.
For the proofs,
Under an intuitionistic shall understand
(many-sorted)
we must refer to Kleene
predicate
a system of intuitionistic
in most either 1952, §74.
calculus with equality we
predicate
logic with equality =
satisfying the axiom
x)
Vx(x =
and the schema x=y
~
(Ax~Ay) .
It readily follows that
=
is symmetric
and transitive.
(In what follows equality need not be given for all sorts of variables, one makes some obvious formulation
(many-sorted) additional 1.2.2.
a formal
system
logic with equality, predicate
if
logic,
~ ~
intuitionistic
H', H
predicate
logic,
(the non-logical
be formal and let
is an extension of the language of
H,
contained in the set of theorems of
Thm(H') Let F
F~Fm(H) o (or w.r.t,
H
is said to be based on intuitionistic
the equality axiom and schema, and possibly
Let
servative extension of
situation to the reader.)
is based on the rules of intuitionistic
axioms and axiom schemata
Definition.
if
in the theorems ;but we shall leave the
of the theorems in this more general
In this section, predicate
stipulations
axioms).
systems based on (many-sorted)
H~'
(i.e. the language of
and the set of theorems of
H' ).
(or conservative
Then
H'
over
H),
~
~' is
is said to be a conif
n Fm(H) = Thm(H) . Then
r)
~'
is said to be conservative
over
H
relative
to
if
Thm(~') n r ~ Thm(~) n r (we s h a l l 1.2.3.
Definition.
tuitionistic of
sometimes abbreviate
predicate
Let
H',
logic,
~ ~ if there is a mapping
this H
as
i'
be f o r m a l
and l e t ~
~F = HnF1. s y s t e m s b a s e d on m a n y - s o r t e d
H~H,
Ht
is
of those formulae of
only free variables are of sorts occurring in
Fm(H) ,
in-
s a i d to be an e x p a n s i o n Fm(~') such that
where the
15
(i) (ii)
[, b A~-~ ~ ['WA - ~W~A
(iii)
~
We say that
~ A
for
[i
A 6 Fm(~) . relative to
is an expansion of
F,
F~Fm(H)
if (iii)
is weakened to (iii)' ~A ~ A 1.2.4.
for
Definition.
A 6 F. Let
H', H
be formal systems based on many-sorted
predicate logic, and let the language of
H'
be obtained by adding non-
logical constants (i.e. constants assumed to be in the range of certain sorts of variables, and predicate constants). al extension of
H,
Then
H'
if there exists a mapping
is said to be a definition-
~
such that (i), (ii), (iii)
hold and (iv)
~(~) = ~ ,
(v)
~((Q~)A) ~ ( Q x ) ~
(i.e.
~
1.2.5.
~(Ao B) = ~ o for
~B
for
o ~ V, a,
Q ~ V, ~.
i s a h o m o m o r p h i s m w.r°t, logical operations) Remark.
A definitional extension is an expansion, and an expansion
is a conservative extension. 1.2.6.
Theorem
(Addition of symbols for definable predicates).
be
Let
any theory based on (many-sorted) intuitionistic predicate logic, and let A ( x I ....
,xn) ~ Fm(~),
Xl, ..o, x n o
Let
where
~
all the free v a r i a b l e s
of
A
are a m o n g
be obtained by addition of a predicate symbol
M,
with axiom A(x1,..o,Xn) ~--~M(Xl ..... Xn) . Then
H'
Proof°
is a definitional extension of
H.
Trivial ; see Kleene 1952 , lec. cir.
scribe the mapping P
~o
(Kleene 1952 ' § 74, Example I) For future reference we de-
required by the definition of definitional extension :
(a)
If
is a prime formula, not of the form
(b)
~o(Mt1...tn) ~ A(tl,..o,tn)
(c)
~o
Mtl...t n,
~o P ~ P
is a hemomerphism W.rot. the logical operations.
1.2.7o
Theorem
Let
be a theory based on (many-sorted) intuitionistic predicate calculus
H
with equality.
(Addition of symbols for definable functions).
Assume, for a formula
A
containing free only
Xl,...,Xn,Y :
~ ~ y A ( x I .... ,xn, Y) where Let
~yBy H'
abbreviates, as usual,
be obtained from
together with an axiom
H
~y[By&Vz(Bz--z=y)].
by addition of a new function symbol
f ,
16
A ( x 1 , . . . , x n, f(x I . . . . ,Xn)) and extension of the axiom schemata to formulae in the extended language. Let
~I
be the mapping of
Fm(~)
into
Fm(~)
Let us call a term not containing occurrences of the form
ftl..°t n , an
is a plain
f - term ; if
defined as follows. f , f - less ; and a term
ti,...,$ n
are
f-less,
ftl...t n
f - term.
We define occurrences Assume
~I of
for prime formulae f - terms in
q> 0
for
term in
P ; let
ed from
P
v
P .
P
by induction on the number
~I P ~ P,
if
q=O
ftl...t n
be a variable not occurring in ft1.o.t n
of
of term occur-
be the first occurrence
by replacing the occurrence
q
.
P ; let (on some standard enumeration
rences in prime formulae)
Then
of
of a plain
P ; let by
C(v)
f-
be obtain-
Vo
~I P ~ ~v[F(t1°..tn, v) & ~IC(V)] °
(The variable ~I
v
may be assumed to be chosen in a standard manner.)
is defined for logically
is a homomorphism Wor.t. transform of
compound formulas by the requirement
the logical operations.
~1 A
that it
is called the
f-less
A .
Then the assertion of the theorem is as follows: ~'
is a definitional
extension of
the definition of definitional
~
(with
extension),
~I
as the mapping required by
provided the additional
axiom
schemata satisfy the condition (a)
if
A
Proof.
is an axiom by an additional
Kleene
1.2o8°
Theorem
Let
be a lanEuage
~
(Replacement
(n+1) - a r y predicate of
~
of 1.2.6), and ~, ~'
(i)
~(~)
[
(iii) If
of
F .
~I(A)
(resp.
Let
~o,~I
such that
is the
~ ~I
A .
in
f-less
systems,
be mappings
~o(A) A
symbol
by
f
symbols). and an
of the formulae
is obtained by replacing f(t1,oo.,tn) = t
transform of
A
(cf. proof
(see 1.2.7).
based on intuitionistic
predicate logic
such that from
~
by
omitting
f,
~(~')
~s obtained by
F ;
contains an axiom A
~
n - ary function
F(tl,...,tn,t )
is obtained
omitting
(ii)
symbol
be two formal
with equality,
then
of function s2mbols by predicate
containing an
into the formulae of
every occurrence
Let
axiom schema,
1952, § 74 (Theorem 42).
H~y F(x I ..... xn, Y)
is a non-logical
axiom of
~
(resp. of
~ ~I(A)).
Then
~b~1%( A)~A,
H'W%~I(A) eeA,
~' ) then
~' ~ 0 o ( A )
17
+rbA= Note that
~,+rbA~
~'+~or ~ %A, ~+~Ir~I A
if
the
H"
is
common e x t e n s i o n
of
H
and
H'
containing the axioms and axiom schemata of both, then al extension of
H
as well as
in H"
the language
~,
is a definition-
H' .
Proof.
See Kleene 1952, § 74, theorem 45.
1.2.9.
Theorem
Let
H
be a system based on intuitionistic
let
M(x)
(Addition of defined sorts of variables).
be a formula of
(many-sorted) predicate logic ;
Fm(~) , containing free only
x,
and
~ ~M(x). Let
~'
be obtained by addition of a new sort of variables
(say
~,~,~,...I,
with rules for term and formula construction also extended to the new variables, with the axiom schemata and rules of
H
(but where in an axiom or
axiom schema involving quantified variables,
the axiom or axiom schema is not
to be generalized by replacing quantification over the original variables by quantifiers over the new variables),
and with the new axiom and schemata and
rules ~,
Mt ~ ( V ~ A _ ~ A t ) , Mt ~ ( ~ t ~ A ~ )
Then
H'
Proof.
is an expansion of
,
H.
(K!eene 1952, § 74, Example 13).
as follows.
Let
A
We define a mapping
We describe the correlation
~2
be a formula containing a set
V
~V
by induction on their
for the subformulae of
A
of free variables.
complexity : ~ ( P ( ~ I ..... ~ n ) ~ P[RI'''°'Yn)
for prime formulae
~v(~lO ~2) ~ ~v(B1 ) o ~v(B2) ~V(QX)B) (Qx) ~V(B)
for
P,
o ~ ~, v, &,
for Q ~ v, ~,
~v(V~Bx.i) ~ V Y i ( ~ y i ~ ¥ B ~ i ~
Here
y1,...,y n
are variables not in
V,
and
~i,..,,~ n
be a complete list of the new variables occurring in Then we put
may be assumed to
A o
~2A = ~NA .
1.2.10. Alternative approach ~0 defined In 1.2.9, the defined sort
sorts of variables.
of variables was treated as a subset of the
original set of individual variables,
with respect to the formation rules.
If we wish afterwards to introduce symbols for functions defined on of elements of
{x I N x l ,
as completely disjoint, and state the formation rules segarately. We then need axioms Vx ~ y ( ~ = y ) (with a primitive or defined Vx6 M ~
(x=z) -
n - tuples
it is preferable to treat the new sort of variables
Cf. e.g. K ~ e i s e l - T r o e l s t r a
1970, 3.3.4).
= ) ,
18
§ 3.
Intuitionistic f i r s t - order arithmetic.
======================================
1.3.1.
Contents of the section.
In this section we describe intuitionistic
first-order arithmetic and notational
conventions,
choice of pairing and
sequence codings, and the formalization of elementary recursion theory.
1.3.2.
Language of
I~.
The language of Heyting's arithmetic
first-order language, with logical constants be identified with a constant
O
O = I ),
numerical variables
(indicated by
(zero), a unary function constant
S
=
is a
(which may x, y, z, u, v, w ) ,
(successor),
function symbols for all primitive recursive functions and a single binary predicate constant
~
V, Z, ~, &, V, ~
constant
(see below in Io3o4),
(equality between numbers).
Terms
and formulae are defined as usual. 1.3.3° H~
Axioms and rules of
HA.
is based on intuitionistic first-order predicate logic and contains
in addition the following axioms : "X
=
X
x = y
&
z=y-~x=z
x i = x'11 -* ~(Xq . . . . . F~
for any
SxjO
Xi .....
Xn) = ~ ( x I . . . . .
n - ary function constant
x~ . . . . .
Xn)
I< i < n
,
Sx=Sy-~
x=y
,
the definining axioms for the primitive recursive functions
(see 1.3.4) and
all instances of the schema of induction I~O
A0 & Vx(Ax--A(Sx)) -+ V ~ x .
1.3.4.
Defininin~ axioms for primitive recursive functions°
The precise selection of initial functions and defining schemata is not relevant to our discussion of intuitionistic arithmetic in this volume. A very simple set is as follows : Initial functions are the zero-place n-place
projection function
In i'
0 ,
1~i~n,
I - place successor for all
n,
S , and the
satis[~ng
l~(x I .... ,xi,...,Xn) = x i ° Our defining schemata are composition and recursion. Composition is described as follows. and
~
an
If
~I' "°'' ~m
are
n-place
functions
m - place function which have been defined before, then we may
introduce a new
n-place
function
g
with axiom
19
~(x~ . . . .
'~n ) = * ( ~ ( ~
. . . . '~n ) . . . .
' %(~1 .....
is said to be defined by composition from Recursion : if
~
is an
n - place function and
which have been defined before, function
~
~,
Xn))"
~1,.o.,~m. @
a
n + 2 - place function
then we may introduce a new
(n+1) - place
with axioms
f ~(0, x 1 ' . . . . Xn) = ~ ( X l ' ' ' ' ' X n ) , x n)
~(Sy,Xl,In this case, Io3.5.
Rule
~
is said to be defined by recursion from
•
~, ~.
and axiom schema of induction.
Instead of using
IND , we might also have added the rule of induction
Rule_IND
(x
$ ( ~ ( Y , X 1 ..... X n ) , Y,X I .... , x n)
BO , Bx ~ B(Sx) ~ By
not occurring in assumptions on whieh
Bx ~ B(Sx)
depends).
A minor variant : BO,
Vx(Bx~B(Sx))
It is obvious that
IND
~ By.
implies
R u l e - IND o
For the converse, we must
apply the rule to Bx ~ AO & Vy(Ay--A(Sy)) - - A x .
1.3.6.
Natural deduction variant of
The description in 1.3.2- 1.3.4 of
HA. ~
is independent of the particular
formalization of intuitionistic predicate logic which is used. obtain a natural deduction variant of
~
However,
to
which is especially suited to the
proof-theoretic researches in chapter V, we have to make some changes in the non-logical part also. As in the discussion of intuitionistic predicate logic, we distinguish between parameters and variables.
We have one individual constant,
single unary function constant, denoted by cate constant constants
=
(equality),
FI, F2, F3,
...
S
(successor), a binary predi-
and a denumerable sequence of predicate
for the graphs of primitive recursive functions.
To the rules of predicate logic we add rules (the basic rules)
t= t
i
t
t i = t!
= t'
0 , a
t = t'
t'=
Fktl...tioO.tn
Fktl-..t~...t n
t"
~0
O = St
t=t'
St=St'
#k
St=St'
t = t'
and, for example,
parallel
to the first set of initial functions
schemata given in 1.3.4, we introduce
Fk'S
and defining
such that
FkX I --. x i ... XnX i and if Fk
Fko , Fkl , ..., Fkm
have already been introduced,
we introduce
an
(k ~ ko, kl, ..., km)
Fk2tl.--tnt:,-..,F!~mtl-O.tnt~,Fkot~.*.t~
Fklt1"''tnt ~
t
F k t1°--tn t and if
Fm, F n
have already been introduced,
we introduce
an
Fk
(k> m,n)
with two rules : F m tl...t n t
Fktot I" ..t n t
FkOt1.°-tnt (Thus to each F
Fk(Sto)tl...tnt'
n - ary primitive recursive
such that~ intuitively,
Finally,
Fnttotl...tnt'
function
~
there corresponds
~(Xl,...,Xn) =y~--~ FXl...XnY
an
o)
we add a rule of induction * in the form o
l.o'
A(?a)
Ao ~t
where
a
is a parameter not occurring in assumptions
except of the form a
on which
A(Sa)
depends
Aa.
is called the proper parameter of the
IND - application.
A proper parameter of a deduction may now be a proper parameter of an application
of
VI, ~E, IND.
We shall also agree to call the premisses premisses ; the premiss of the form premiss of the form
A(Sa)
AO
of an application
of
IND
is called the zero premiss,
the inductive
premiss ; the premisses
minor the
of the
basic rules are regarded as major premisseso The conditions formulating
on variables given in 1.1.7 may now be sharpened by re-
(iii) as
(iii) Every proper parameter in application
of
VI, ~E
or
H
is a proper parameter of exactly one IND
in
H~
and adding
• ) In the sequel, IND will be used indiscriminately lation in 1.3.3 and the one given here.
to refer to the formu-
21
(iv)
The proper parameter of an application of INO
in
~
only in formula occurrences above the inductive premiss of The present formulation of
~
(say
Nat -~..)
described in 1 . 3 o 2 - 1.3.4 (to be called simply sense : obviously,
Nat -li~
is equivalent to
HA
below), in the following
Nat-HA*
obtained by reand
IND'
by the
Addition of symbols for the primitive recursive functions H
with their axioms is then an expansion expansion of
IND.
is equivalent to the one
placing the basic rules by corresponding implications, schema of 1.3o5.
ff
occurs in
HA
of
Nat - H A * ;
also,
So there exist mappings
(of. 1.2o7, Io2.8).
H
is an
~, ~'
such
that
(I)
~A
o~at-~
~A
=
I~ ~ ~'A
~ff ff (~ +~A) ~ (~,A +~A). 1.3. 7 .
Eliminability of disjunction in systems containing arithmetic.
In intuitionistic arithmetic,
A VB~-~ ~ [ ( x = O ~ A )
we have
& (x/0~B)].
In order to show that this may be taken as a definition for show that the axioms and rules for
V
V,
we have to
are derivable for this defined connec-
tive from the rules and axioms for the other logical operators. In order to see this for the natural deductive formulation, introduce the following notational sequence of) deductions, where Z
of the form
A.
If
H
convention : [~]
[A]
let us first
stands for a (finite
indicates a set of open assumptions in
is a deduction with conclusion
A ,
II [A] Z denotes the result of substituting in
for the occurrences of the class [A]
Z.
Now
vl
can be shown to be a derived rule as follows :
(I) o~o A 0=0 -~ A
--.I
o=o
sQ,,So
0/0 -~ B
is obtained as follows :
so=o
A
A_ Az s (1)
( 0 = 0 ~ A ) & (0~0-* B) ~ [ ( x = O - - A ) ~ (~/0 -- S)] VE
H
SO=O ~ A
SO/O ~ B
(S0=0 -- A) & (S0/0 ~ B) ~[(~=0
~ A) ~ ( ~ / 0 -- S ) ]
22
[A] Assume
Z
[B] ,
ZI
to be given. b=O O=b
b=Sa
O=Sa
(b=0"A)~(biO"
~)
A
(b=0--A)~(b~0-- ~)
b7 o
b=0 -- A
b=0
blO -
[A] Z
[B] Z'
C
C
b=O -* C
b=Sa -~ C
b=b ~[(x=0--A)
b=b ~ C
& (xl0-B)]
C
Further we note that we obtain corresponding
results for the Spector system
and the Godel system since the proof of equivalence also applies if we restrict ourselves I__nnpractice,
however,
we shall usually treat
this requires only very little additional many developments
between these systems
to the fragments not involving V
as a primitive,
effort in our proofs,
V o since
and moreover
then apply to predicate logic also, almost without change
or additions° 1.3o8.
Formulation
of
~
It is of course possible in favour of predicate
without any function
constants
natural deduction formulation by a binary predicate
x=y
symbols.
to carry the step of eliminating
S(x,y)
function
symbols
one step further than has been done in the
of
~,
and to replace the successor function
such that
~ s(~,~) - s(y,~)
s(x,z) ~ s(y,~) - ~ = y s(x,y) ~ o ~ y and the inductive
clause for a predicate
introduced by the recursion
constant
F
representing
a function
schema now appears as
FkXo...XnX & FnXXo°,oXnY & S(Xo,Z ) ~ FkZXoo°.XnY (where
Fn
has been introduced before
F k)°
Induction appears as A(0) & Vxy(Ax & Sxy -- Ay) This formulation is equivalent
-- V ~ x .
to our original formulations
(again by using
§ 1.2) in the same manner as indicated for Nat - H A in 1.3.6 (formulas A formulation of this type is used in chapter V°
(I)).
23
1.3.9.
Notational
and a b b r e v i a t i o n s
conventions.
We list a n u m b e r of n o t a t i o n a l
to be used in the sequel.
A) For f r e q u e n t l y used primitive notations
conventions
in c o m m o n use,
recursive
functions
and p r e d i c a t e s
such as "prd" for the p r e d e c e s s o r
we adopt
function,
satis-
fying prd 0 = 0 , cut-off
subtraction
prd(Sx) = x ; is d e n o t e d by
x " O=x, signature :
"sg",
x I Sy
~,
= prd(x ~y)
;
satisfies
sg 0 = 0 ,
sg(Sx) = S O ;
absolute d i f f e r e n c e
" I • - " I" :
Ix-yl = ( x ~ y ) + ( y ~ x ) ~ m a x i m u m and m i n i m u m "max",
"min"
max(x,y)
= x + (ylx)
min(x,y)
= max(x,y) %
For Kleene's
T - predicate
Ix-yl
-
and the result - e x t r a c t ~ u g
f u n c t i o n we use
T, U
respectively. B) Pairing° J' it' J2
are assumed to be a p a i r i n g f u n c t i o n f r o m
N×
N
onto
N , with
its i n v e r s e s : (I)
jlj(x,y ) = x ,
j2J(x,y ) = y ,
The use of a p a i r i n g f u n c t i o n
cases,
that
2x3 y
J' J1' J2
2j(x,y)
are p r i m i t i v e recursive.
= (x+y)(x+y+1)+2x
The p a i r i n g f u n c t i o n r e p r e s e n t e d (3)
x < j(x,y) ,
(4)
x < x,-
(x,y) . However,
N.
In n e a r l y all
w h i c h m a t t e r are given by (I), t o g e t h e r with the
may fix on some definite p a i r i n g function, (2)
is not essential ;
to encode the pair
to assume the p a i r i n g to be onto
the only p r o p e r t i e s
information
j2 z) = z.
onto the n a t u r a l numbers
e.g. we might have used Kleene's it is often convenient
j(jlz,
F o r definiteness,
o
by (2) has the additional
y < j(x,y)
O(x,y) < j(x,,y),
w h i c h we shall assume from n o w on.
we
e.g. by r e q u i r i n g
if
X+ y > 0 ;
y < y,-
advantages
j(O,O) = 0
O(x,y) < j(~,y')
that
24
C) ~ d ~ n g numbers
of_fin~e
~equ~ce~.
we also prefer
Troelstra
Of course, variables
to have a coding ontq
1970 , 2.5.3,
is to r a n g e o w z c o d e
running
of sequences
only
over finite
sequences
since they can be coded by natural
and
and V e s l e ~
a separate
1965).
sort of
a conservative
extension,
numbers ; cf. 1.2.9) ; but this is rather resources,
we may assume
the standard
as f o l l o w s :
function
of natural
that a certain variable
(as in Kleene
(obviously
For the sake of definiteness, pairing
sequences
(as used in Kreisel
solution would be to introduce
a heavy draw on our typographical
of
N
in order not to have to specify
numbers
an elegant
For a coding of finite
which N~e wish to avoid. our coding
to be constructed
we first introduce
codings
from
vu
u - tuples v1(x ) = x v2(xl,x2) = j(xl,x2) ~u+1(Xo,Xl, .... x u) = j(~e,~u(Xl .... ,Xu))~
there
.U
exist inverses
Ji
such that .U
J~u(~1 .... 'Xu) " ~ i ' now we fix our coding < >=0,
,U
~u(J1 = .... '~u ~)= ~
of finite
sequences
by
<Xo> ~def Sj(O'Xo) '
<x o .... ,Xu~ = Sj(U,~u+1(Xe, .... xu)), where
<Xo,..~,Xu>
denotes
number for the empty
the code number for
sequence.
The present
x u < <Xo,...,Xu,...> <Xo,.o.,Xu> As an abbreviation ~
ith(n)
def
is used
denotes
the code
choice of coding i m p l i e s :
'
< <xo,...,Xu,...,Xu+v>
for
v> 0 .
we introduce
to denote ,
the length
of the sequence
coded by
n ,
so
lth<xo,..o,Xu_1>=u°
the concatenation,
~Xo~oo.,Xu_1~
< >
<x>.
Ith< > = 0 *
Xo,...,x u,
so
* ~Xu,°o.,Xu+v~
= ~Xo,...,Xu+v~.
We put n~m
=def ~ n ' ( n , n '
n ~m
~def n ~ m
( ~, ~
are used in different
partial
ordering
for an arbitrary
between
= m)
& n~m
o meanings
finite
primitive
in this volume :
sequences,
recursive
I ° ) as the natural
as just defined ; 2 ° ) as a symbol
well-ordering,
in the discussion
of the
25 principle
of transfinite
for "reduces to". Let us write for
induction
TI(<) ;
3 ° ) as a metamathematical
symbol
In all cases the meaning will be clear from the context°)
(n)x
for a primitive recursive function of
n, x
such that,
n = (Xo,...,Xu_1>
tl(n)
(n)i=x i
for
(n)i=o
for i~u°
("tail of
n"
i
is a primitive recursive
tl(O) = 0 ,
tl(~) = 0 ,
The derivation of elementary
function
such that
tl(~* n) = n o
properties
of the codings
(a tedious affair,
which the reader might wish to skip) can be found in Kreisel and Troelstra 1970, § 2.
• e shall frequently have to use formalized proof-predicates provability.
ProofH(x,y ) ,
or
ProofR(x,y )
for ar~v "canonical"
proof-predicate
interpretation : x
is the g~delnumber
number
y.
"ProofH"
"Canonical" ditions,
for the formal
so as to make it possible
~ , with intuitive
of a proof of a formula with g~delrecursive.
some natural
to prove Godel's
(For derivability
II, pp.
system
may be assumed to be primitive
will mean that it satisfies
theorem for them. 1970, Vol.
and formalized
We use
conditions,
derivability
con-
second incompleteness
see Hilbert and Bernays
294- 295 , where they are described in detail.)
We put
Pr~(y) %of ~x Proof~(x,y). "PrH"
is the "provability"- predicate,
form.
(In our versions
of
~,
and may be assumed to be of
"Proof(x,y)"
may be represented
o ZI -
by a prime
formula.) A ~delsentence
for a system
(i.e. of the form
VxAx ,
of consistency
~,
~m
of
~
(containing,
say
primitive recursive)
~VxAx
,
s nd on assumption
~
)
is a
H oI - sentence
such that on assumption of
w- consistency of
~,
VxAx . A rosser-sentence
of
Ax
H
is described like a g~delsentence,
is sufficient for ~
mVxAx.
times called sentences independent In our standard formulation section),
Ax
Numerals. and especially
of
but now consistency
G~del- or tosser-sentences w.r.t. HA
are some-
~.
(the first one described
in this
may be supposed to be a prime formula. As syntactical fi, •
variables for numerals we use
(in chapter V
~, y, z, ~, ~,
there is a deviating local convention
26 concerning numerals). If
A
then
is a formula,
t
rA~
denotes its g~delnumber ; if
denotes its godelnumber.
are among
x1,°..,x n,
wise ~ that
we shall use the convention
A(~ I ..... ~n)
t
If all the free variables
is a term, of
A(Xl,...,x ~
(unless indicated other-
stands for the g~delnumber
of
A(~ I .... ,~n )
as
s(CA(x1,. .. 'Xn) 'Yl , .... Yn ) a function of Xl,..°,x n . is the godelnumber of the formula obtained by substitution of the numerals (More precisely,
~I'"
°o
'Yn
for
--
Xl,...,x n
= rA(~1,o.o,Xn)~ ) o contexts,
in
A , then
represented
VA(~I, ..°, ~ n) 9 by formulae
Note that in view of the preceding
ProofH~(y, WA(x I ..... -Xn) ~ ) , etc. are in
containing
x1~...,x n
HA
free°
of elementary recursion t heor2o
For some of our researches, (chapter I I I , §
,X n ) , y l , . ° . , y n ) =
.°
The notation may cause problems in more complicate~
1°3. I0. Formalization
as the
s(rA(x1,°
but suffices for our purposes.
conventions,
if
notably in the case of formalized
2) it is necessary
to know that the principal
s-m-n- theorem and the recursion
The reader may take this on faith,
realizability
theorems
theorem can be formalized
in
such HA.
or better rely on the detailed formaliza-
tion of recursion theory in Part I of Kleene 1969 ; by omitting there everything pertaining
to function arguments
recursive fun ctionals) theory in
H~A°
(The use of different
finite sequences is completely Kreisel
and Troelstra
formalized
of elementary recursion
pairing functions and encodings
irrelevant
of
in this context ; cf. remarks in
1970 , 2.4.15 , 2°5.3.)
Below we shall list the principal About the
(Kleene 1969 discusses
one obtains a formalization
facts needed.
T - predicate we may assume ff T(x, y, z) & T(x, y, z') ~ z = z' .
In our first version of functions are present, formula
HA ~ where symbols for the primitive recursive we may suppose
Txyz
to be represented
by a prime
CTXYZ = 0 o
We shall freely use Kleene-brackets cursive functions
{° I
as a notation for partial re-
and partially defined terms,
between partially defined terms ; in Kleene detail how these notations
and also the equality
1969, Part I it is shown in great
can be used as systematic
Let us, following Kleene,
denote as
abbreviations.
p - terms the class of expressions
satisfying the formation rules for terms and in addition : If
to, tl, .... t n
are
p-terms
then so is
It In(tl .... ,tn) . O
(Actually,
we have no need for Kleene-brackets
but it is no trouble including them°)
with more than one argument,
Instead of
{tol~(tl)
we usually
27
simply It O}(tl) ° Each p - term r e p r e s e n t s b l e s . We use f u r t h e r m o r e
write
a partial
~t ~def ~ x ( t ~ x ) Note that The
Jt
and
s-m-n-
primitive
t= s
,
recursive
t = s =def
!t
&
can be expressed
!s
as
function
&
free varia-
t ~ s
Z o1 _ formulae°
theorem
recursive
of i t s
may now be stated as follows: m function o ouch that n
There
exists a
l z l m + n ( x l , . . . , x m + n) = t s ~ ( z , x 1 , o . . , x m) }n(x, m+1 , ° . . , x m + n) This makes
it easy
to prove
the recursion
theorem:
n+1 (Consider
~~xl~n+l-(sntu,u),z1,.oO,Zn) t,
Ivln+1(U,Zl .... ,Zn) ~
then
; we can find a
Ix}n+1(s(u,u),zl,...,Zn)
v
; now take
such that y = s(v,v) ,
I~In(zl .... 'Zn) ~ Is(v'v) In(z1""'Zn ) ~ Iv}n+1(v'zl ..... Zn)
= {x}n+1(s(v,v),zl ~e
n
. . . . ,z n) = I x } n + l ( y , Z l , o . o , Z n
shall make frequent A convenient
use of the recursion
abbreviation
) .)
theorem.
is
Itl(tl .... 'tn) ~def I°'°IIt}(tl)l(t2)°'° l(tn) ° (Ackually, Ix}n(yl, .... yn) can be defined in such a way that
IxP(y I... yn ) ~ Ixl(y~ oo. yn) .)
28
§ 4.
Inductive = =definitions in = = = = = = =
HA
= = = = = = = = =
1.4.1.
We intend to show in this section how certain inductive definitions
of sets of natural numbers may be replaced by explicit definitions. result is used repeatedly, especially in § 4.4.
The
The reading of this section
may be postponed until needed.
1.4.2.
Definition.
Let
~X]
~ £(KA)[X]
denote the language of
extended by a single additional unary predicate symbol F
is the least class of formulae of
(i)
the formulae of
(ii)
formulae
(iii) if (iv)
KA
Xt' , t'
A, B E F
if
A E F,
t
a term of
then
X.
such that
are contained in a term of
then
~X]
P;
KA , are in
P ;
A & B , A VB E F ~ x A E P,
Vx i t A E P
(t
not containing
x
free,
H~A).
Our next aim is to show that formulae
A(X, x) E ~ X ]
equivalent to a certain type of standard formula of
can be shown to be ~[X]
(see the statement
of 1.4.4 below) ; we first need a simple lemma : 1.4.3.
Lemma.
Vx o i to[Y] Vx I i
Vx ~ t[y] A(~o(X,y), ~1(x,y), y) , recursive in Proof.
for suitable
is equivalent to
t, ~o' °I'
primitive
x, y, to, t I .
For our standard pairing function
with its inverses y
t1[Xo,Y] A(x o, x I, Y)
J1' J2
we shall assume
j
onto the natural numbers, and x<x'
-- j(x,y) < j(x',y),
-- j(x,y) < j(x,y,) .
We define $(y)
=
t(y)
supIt1[xo,Y] I X o ~ t o [ Y ] l J(to[Y], ¢(y))
~o(X,y)
= { jl x [ 0
if J2 x ! t1[JlX,Y] & Jl x ! to[Y] otherwise ,
~l(x,y)
= ~ j2 x L0
otherwise .
if
J2 x i tl[JlX,Y] & Jl x i to[Y]
Now assume
(1)
Vx° ~ to~Y]Vx I ~ tl[Xo,Y ] A(Xo, Xl, y)
x!t[y]
and let
Now either
%(x,y)
jl x ~ to[Y ] , j2 x ~ t1[JlX , y]
,
and then
~o(X, y) = jl x ,
J 2 x , and by (1) A(%(~,y), % ( x , y ) , y ) , or j l x > to[Y ] v j2x > t l [ J l x , y ] ; in t h i s case, %(~,y) = %(xw) = O,
and
=
since by
(I)
Conversely, let
A(O,O,~) ,
once again
A(~o(x,y), ~ 1 ( x , y ) , y ) .
29
(2)
Vx
and assume
%(x,y)
x it[y]~
1.4.4.
X o ~ t o [ Y ], xl!t1[Xo,Y].
Lemma.
H~A[~] (i.e.
= %,
~l(x,y)
Each formula ~
=x I, A(X,z)
If we put
J(Xo,Xl) = x,
so by (2)
A(x o , x 1 , y ) .
of
F
extended to the language
then
is provably equivalent in ~[X] ) to a formula of the
following general form (I) Proof.
~xVyit(x,z ) [P(x, y, z) V (Q(x, y, z) & Xt'[x, y, z])] . To prove the lemma we have to show that formulae equivalent to &
formula of type (I) satisfy the closure conditions (i) - (iv) in the definition of F. Below we shall omit all variables which are redundant in the context of the argument.
(i)
Let
Pz
be an arbitrary formula of
P~ ~ (x,y (ii)
Xt'
HA.
Then obviously
~vy!o (Pz v [0= I ~ xo])
are assumed not to occur free in
P).
is equivalent to
~Vy<_O (o~ 1 v [o=o & xt,]) (t' (iv)
does not contain
x,y).
We note the following equivalences
(2)
SxyVz<_t[x,y] A(x,y,z) ~
(3)
Vx~tZy A(x,y) ~
( t not containing The closure of
F
~xVzAt[JlX, j2 x] A(JlX, j2 x, z)
~nVx~t i(x, (n)x)
x ). under existential quantification is immediate by (2).
The closure under bounded universal quantificatio~ follows from (5) and the previous lemma : Vu~t* Sy Vxit[u,y ] A(u, x, y) SnVu~t* Vx~t[u, (n)u ] A(u, x, (n)u) <---> *-9 ~nVv~t'[n]
A(~o(V,n), ~1(v,n), (n)$o(V,n)) .
( i i i ) Let A - ~xVyito(X)
[Pc v ( % ~ Xt~)],
B m ~xVyit1(x ) [Pq V (QI & Xt~)]. After contraction of two existential quantifiers, we obtain A&B ~XVYo~to[JlX]VY1~t1[J2x ] l[Po(Jlx,Y) V(Qo(JlX,y)&Xt~[JlX,Y]) ] & &[P1(J2x,Y) V (Ql(J2x,Y) & Nt~[J2x,Y])]} .
3o
We put
P(x,y, u) Q(x, y, u) t[~, u] t,[x,y,u]
~ ~ ~ m
(Po(JlX,y,u) &u=O) V (P1(J2x,y,u)&u~O) (Qo(jlx,y,u)&u=O) V (Q1(J2x,y,u) &u/O) ( l ~ U ) t o [ X ] . s~(u), t l [ ~ ] ( l ~ u ) t ~ [ x , y ] + sg(u).t~[x,y].
Then
A&~
~ ~x Vuil vySt[~,u ] [P
v
(Q&xt,)].
By the previous lemma, this is equivalent to a formula of type (I).
~
AVB
~x IVyito[X ] (Po V ( Q o & X t ~ ) ) V V V y ~ t l [ x ] (P1 V ( Q I & X t l ) ) I "
We put
P,(x,y,u) Q,(x,y,u) c"[x,y,~] t,[x,u] Then
A VB
~
~ ~ ~ ~
(Po~UoO) v (P1~u/°) (Qo&U=°) v ( % & u / O ) (l~)t, + s d u ) . t~ 0 (1~u)t ° . s~(u).t I
Zx~uVy~t"[x,u]
[P' V (Q' &Xt"')] ;
by (2) this is equivalent
to a formula of the form (I). 1.4.5.
Theorem.
Let
A(X,z)
be a formula of the class
an arithmetical predicate (i.e. definable in (I)
A(PA,Z ) ~
PA z
F;
then there is
such that
PA z
and for each arithmetical predicate
(2)
H~)
Q
Vz[A(Q,z) -- az I -- Vz[PAz -- Qz]
are derivable in Proof.
HA.
By lemma 1.4.4, we may restrict our attention to a predicate
A(X,z)
of the form (3)
~Vy~t[x,z][P(x,y,z)
A proof that proof
H
z
V (Q(x,y,z) & Xt'[x,y,z])].
satisfies (3) may be supposed to be in tree form : the
provides an
x , and for each
which either establishes
P(x,y,z)
y~t[x,z]
ff contains a sub-proof
(and then represents an end node of
Z
the tree
T
associated with
in the latter case, with
H
Z
H)
or establishes
Q(x,y,z)
is associated a subtree
T
Z
and of
Xt'[x,y,z] ; T,
which
establishes Zx'Vy'!t[x',t'[x,y,z]](P(x',y',t'[x,y,z])
V
V (Q(x',y',t'[x,y,z])&Xt'[x',y',t'[x,y,z]])) , and so on. It is this intuitive idea which suggests the explicit definition which will
3~
be given below. Any natural number may be supposed to code a finite tree ; < > empty tree, and if
n = <Xo,...,Xu> , then the tree
Tn
codes the
represented by
n
has the structure
where
So,...,S u
Xo, .. .,x u,
are the trees coded by
Below we adept the following notations: [n]m
inductively on [n]o=n,
Now we put for
lth (m)
we write
nu
respectively. for
(n) u , and define
by
[n]
= (n)u=nu,
[n]m * = [[n]m] = (~n]m)u"
PA ~ :
PA z ~ S n B m S p [ n / O & m o= z&VuVy~t[Pu,mu]I(In]u,
& ( [ n ] u . < y >= O& [n]u/O ~ P(pu,Y,mu)) t] ~!
I.
We have to show
~xVy~t[x,z][P(x,y,z) where
A(PA,Z ) -- PA z .
V (Q(x,y,z) & ~InBmBp B(n,m,p,t'[x,y,z]))] ,
~n~m~p B(n,m,p,z)
~ PA z , implies that for a suitable
Vy~t[Xo,Z][P(Xo,Y,Z ) V (Q(Xo,Y,Z)&SnBmBp Hence we can find
w, n, m, p
x°
B(n,m,p,t'[Xo,Y,Z])) ] •
such that
Vy~t[Xo,Zl[(Wy / 0 -- P(xo,Y,Z)) & & (Wy= 0 -- Q(Xo,Y,Z ) &B(ny,my,py,t'[Xo,Y,Z]))] Now we define
n', m', p'
such that
n' = (no ..... nt(xo,Z) > with
ny = 0
for
Wy/O,
~y~ny m ! O
m'
satisfies
p'
satisfies
W y = O.
z
~
(mY)u
!
Then obviously
=
for
=
X
Po o P' * u = (Py)u
•
52
n' / 0 & [mg= z & VuVy<__t(pg,z) [([n']u.<j>/O- ~ ~(Pu I 'y'm ' , m 'u] = mu*) & u) & t l [pu,y, & ([n']u~O & [n']u.: 0 B(n', m', p', z) , which implies Part II.
(Pu,Y,mu)) }] PA z .
Assume
(4) i.e. ~xVy~t[x,z][P(x,y,z) V (Q(x,y,z) & Rt'[x,y,z])] " Rz. We shall prove by induction on (5)
n
VmVpVz[B(n,m,p,z)--Rz] .
Basis : For n= 0 (5) is trivially fulfilled, because the antecedent is then false. Induction step : Now assume (5) to have been proved for all n< n' , hence for all x such that [n']<x>/O. We may rewrite B(n',m,p,z) as n' / 0 & m ° = z
&
& VwVuVy~t[P<w>.u,m<w>.u~l([n']<w>.u. ~ 0 a(P<w>, u, Y, m<w>. u) & t'[P<w>, u, Y, m<w>. u] = m<w>.u.) & ([n']<w>.u.= O & [n']<w>.u ~ O -- P(P<w>*u' y ' m<w>*u))l & & VyAt[Po,mo]{([n' ] / 0 -- Q(Po'Y'mo) & t'[Po'Y'mo] = m) & & ([n'] = O & [n']o/O -- P(Po' y' mo)) i°
"
It follows that [n']<w>/ O -- B([n']<w> , m, p, m<w>) hence
(6)
[n']<w> ~ O ~ R(m<w>)
(induction hypothesis)
and
(7)
i Vy~t[P°'Z]I([n']/O " Q(po,y,z) & t'[po,y,z ] = m) & & ([n']=O & [n']o/O ~ P(po,y,z))l,
therefore, combining (6) and (7) : Vy!t[Po,Z](F(po,y,z ) V (Q(po,y,z) &Rt'[po,y,z]) ) . By assumption (4),
Rz .
33
§ 5.
Partial reflection principles. =============================
Io5.1.
Contents of the section.
Let
Proof (x,rA ~)
indicate
the proof-
n
predicate of
H~
(e.go for Spector's
taining formulae
of logical complexity
logical complexity complexities
is
~n
restricted
only.
to derivations
In other words,
con-
if the
of a proof is described as the maximum of the logical
of the formulae occurring in it, then
ProofHA(X,~A ~) x
system),
and the logical
complexity
Proofn(x,rA~ )
holds iff
of the deduction represented
by
< n °
The principal
aim of this section is to establish i__nn HA
principles
for the subsystems
complexity
of the formulae considered,
(1)
~
b ~
of
Pr°ofn(x''A~)
HA
obtained by putting a bound on the i.e.
~ A .
The main step towards establishing
of a "valuation-
(I) is the construction
function" which assigns to (the g~delnumber value
reflection
of) a closed term its intended
(and which can be shown to do so i__nn ~ ) o
1.5.2~
Godelnumbering
For definiteness
of function constants and terms.
in the formal description,
we specify some details of the
godelnumbering. Ne put
~
for the code number of the function constant
~,
where
m <0> ~ ~i ~<2, n, i> n
~ < ~ ' ~ ' ~ I .... '~m >
if
~
is defined by composition from
~ <4, }, ~>
if
~
is defined by recursion from
The godelnumber
of an arbitrary
Each closed term is of the form function constant (Note that
O
closed term is defined as follows.
gtl~..t n
of our language,
~'%'''''~m" ~, ~.
~e put
(n
possibly gtl...t n
as a function constant has number
0 ), where
~
= <~, t I , ...,
is a tn ) o
, as a term number
<<0>> o ) The sequence of g~delnumbers is to denote the g~delnumber v0 = <<0>>, 1.5.3.
v(Sx)
Evaluation
Any closed term
= <,
of numerals
is primitive
assigned to the numeral
recursive ; if
~ , v
vx
is given by
vx>.
of closed terms. t
in
HA
has a standard deduction of may be described as follows.
can be evaluated by a standard procedure, t =~
for a numeral
~
in
HA.
and
This procedure
34
A contractible introduced
term is a term of the form
by composition
For closed occurrence
terms
of
10 )
0
2° )
rcso(St)
or recursion~
t , we define
t"
o~ a
~
a constant
projcc[{o~.
the "ri6ht most contractible
(shbreviated : rcso(t) )
does not have an
~I.O.~ n ,
imduct~vely
subterm
as follows:
rcso(t) ;
is the occurrence
in
St
corresponding
to
rcso(t) ,
~
constant,
if this exists; 30 )
if
t m ~(tj,...,ti,~i+1,.°.,~n)
a numeral, 4°)
if
rcso(t)
t m ~(~1,.o.,~n)
rcso(t)
is
A contraction form
then
t
,
a function
~
a function
constant,
if
,
~
of
defined
I~Xj.o.~ n
by
¢(~I .... '~n )
A "standard tI ~ t ,
tn
applied
to the
the construction is obviously
n= O,
<2)
z
a)
For
~ m 0 ,
For
~ m S
c)
Suppose
t"
ti+ I
~def W 1 ° ' ' x Val(~)
SRED(~
is defined
ti
by
by recursion
from
from
if
tl, oo., t n
ti
by a contraction
tn ~,
a value
for
t.
is u n i q u e l y
determined,
the
predicate
expressing :
the
constant
sequence
to the term with
~: v(~(xl
'Xn)))
rodef S R E D ( C ~ ~, v(~)) o
for each function
constant
~
this is immediate° also,
from the definition
is defined
by composition
by recursion
~ in
is defined I~A.
In the verification sequence
for
y,
~I "''~ ~
~
quences
~' ~1' "''' ~m'
is a sequence
results
function
Suppose
reduction
~i ' or of a term of the from
has a standard reduction
~hen we e~sily verify
VaI(x)
S, 0 , then
~ Val<~) o
b)
d)
not
rcso(ti) ;
X(~(~,~ 2 ..... ~n),y, x 2 ..... ~n )
Z ol - arithmetical
n-ary
we may put
~
for
ti+ fl out of
be the
term with godelnumber
Now we establish,
~
~nd by
We then call
of
godelnumber z'. Let us write, for each
For
ti to
unique.
S R E D ( z , z')
Val(~)
sequence
such that
rcso(ti) .
Since
(I)
~I ~ ~'
if
reduction
a numeral,
value Let
not
by
by composition
~(~I(~I .... ,~n) , ..o, ~m(~1 .... ,~n)) , and if
~, x,
corresponding
itself.
is the replacement
~(~l,O.O,~n)
,
is the occurrence
of
V o
from
¢' 91' "''' ~m'
Val(~)
~e now establish
from
9
and
X,
(I) by induction
and assume on
of (a) - (d) we have to use repeatedly for
tl, ..., tn o
~tlo..t n
and assume
always
"contains"
Val(9),
XI . that a standard
standard
reduction
se-
55
We have established (2), and now we readily prove, by induction on the logical complexity of ~mong
X1,
(~)
o~
x
n
t , for any term
whose free variables are
:
" ' ~ n] "
~bs~(%[~,..
1.5.4.
t[x1,...,Xn]
' ~t[=~,.
..
°
,xn])
Construction of partial trut h definitions°
By induction on for all formulae
(I)
n A
we construct truth definitions
T n , such that in
~HA,
of logical complexity _
HA ~- T n ( ~ A ( = I '
(the variables free in
"' A
m) ) ~
A(=I' "'~m)
are among
x1~...,x m)o
For prime formulae we put
To( ~ t ( ~ , . . . ,~n) = s(~ t . . . . . ~n)~--~ ~y[ SR~D( ~t(~
....
SR~D(%(~ 1 .... Assume
Tn
to have been defined.
A, B, (Qx)Cx
~
(2)
closed (where
Q
Then we define
stands for
Z
)~
j y ~)
)~JYD]
Tn+ I
or
•
such that for
V)
Tn+I(~AoB~) ~--~Tn(~A~) oTn(~B I)
(for
o ~-~, a~, V)
Tn+l('-(Qx)Cx -~) ~
(for
Q ~ Z, V)
(QX)Tn("C~- ~)
Such a definition is possible,
since for the usual standard godelnumberings
it is primitive recursively decidable what lhe main logical opera~or'~s ; so we may define
Tn+ I
by cases in agreement with (2).
proved by induction over
n°
For
n=O,
Now (I) is readily
(I) is immediate by the result (3)
of 1.5.3, and the induction step is given by (2)° 1.5o5o
Lemmao
(a)
(For Spector's or aSdel's version of
(b)
(For the natural deduction version of
~o)
~ PrOOfn(Y, %(x I .... ,Xn)" ) ~ ~=1oo.X n Tn(rA(~ I ..... ~n )I) . H~.)
Let us write
F(a I .... ,an) = A(a I .... ,an) , where F = IC1(a I ..... an) .... , Cp(a I .... an)}, for : A(a1,°..,an) can be deduced from assumptions F ; let al, o.., a n be a list containing all parameters free in ~
Proofn(x, rHal,...,an)
F, A . Then
~ A(a I ..... an)")
Vx1.°.Xn(Tn(%1(~ I ,.. . ,~ n) ~ ) ~ ,o . ~Tndcp(= - ~ ,° -o,~n >~) Tn(~A(~I, .... ~n)")° Proof.
~e consider case (a) ; the treatment of case (b) is entirely similar.
Let us write
~(z,x)
for the function which is such that
~(%(Vio,...,Vim)~,
=) = ~A(~Tio . . . . . (=)----~mf°
3~ Then we prove by induction on
lthx
that
Proofn(X,Z) ~ VyTn(~(z,y))
o
To give an example of the argument for the induction
step, assume
VxVv < u(Ith(x) = v & Proofn(X,Z ) -- Vy Tn(~(z,y)) o Now assume
lth(x)
=u &
Proofn(X,Z)
.
~e have to distinguish
various cases,
the proof with number
x.
depending on the last rule applied in
For example,
proof obtained by application
of
assume
x
to be the number of a
Q I to some subproof
xI
of
x
of an
assertion of the form
A(Vio , ... ,Vim ) Note that cursively from
~ B(Vil ,...
xl ~ rA ~, rB~ ' rC~
,v.im )
~ C(Vio
and the numbers
,vii ,.
io,.O.,i m
(in fact, for the usual g~delnumberings,
x .
.. ,Vim
) .
can be found re-
primitive recursively)
So by induction hypothesis Vy Tn(~(rA~ , y))
in
I~A ,
which
implies
Vy{Tn(rB((Y)il
in
turn (in
....
HA) :
, (Y)im)~)
-- Tn(rC((Y)io,
(Y)il ..... --
~im)" )t,
i.e.
VY~oi~n<%<<~Til .....
(~#m))
-- Tn(%<~ o, (Y)il .... ' (Y)im)~)}
hence
VY{~n(%<
VyITn(~(rB~,y)) i.e. by the properties
~ Tn(~(rVVioC~,y))} of
T
,
n
Vy ~n(~(% - VVioChY)) as desired. 1.5.6. (a)
(Partial reflection
principles).
For Godel's or Speeter's formulation
~b (b)
Theorem
of
~:
Pr°°fn(x,~A(~l, . . . . ~n )~) " A<~I' . . . . xn)"
For the natural deduction formulation
of
~
:
Proof.
b Pr°°fn(X, ~ A ( ~ l , ' ' ' , ~ n ) ~ ) ~ A(Xl . . . . . Xn) . ~e consider (~)~ (b) i s t r e a t e d s i m i l a r l y .
Assume
Proofn(X, rA(~ I .... ,~n )~) , then by 1.5.5
1
)},
3?
:~n('-'A (~I,...,
~n)-' )
1, ,5.~r
and therefore by
A(x1,-..,x n) . Q.e.d. 1.5.7.
R e m a r k on refinements.
W e may introduce
complexity,
e.g. by c o n t r a c t i n g
occurrences
of the same type of quantifierso
d(rA ~) = 0
d(rA~B I) d(rA1o.°,
conjunctions,
= ~x(d(~A1),
oA~
A I o o.. c A n
or e v e r y w h e r e
d(~1))
where are
A
1.5.8.
AI,..o,A n
• ..
(QXn)A(xl
(Qy)B,
is e v e r y w h e r e
Q
Tn
&,
BOB'. x n) ~
and e i t h e r all of
o
) + I,
are
V
or all
Q
to this new measure.
s,ystems. systems discussed here and in the sequel, restricted
and the systems
d e s c r i b e d in 1 . 6 . 1 5 - 1 . 6 ° 1 5 )
qf
to q u a n t i f i e r - f r e e
N-~w
qf-WE-HA
w
there are two possible
in the f o r m u l a t i o n :
(i) W e state axioms
then be stated as
such as e.g.
x=x
with free variables,
of terms for free v a r i a b l e s ;
AO , A(x) -* A(sx)
and f o r m u l a t e i n d u c t i o n as substitution
and have a
the i n d u c t i o n rule may
= A(y) , or
(ii) we state the axioms for a r b i t r a r y
terms
A(O) , A ( x ) - * A ( S x )
(as schemata), = A(t) ;
e°g.
t = t,
then we may emit the
rule.
Theorem. R u l e - IND
Let
qf-HA
be
~
restricted
instead of induction.
W e may r e f o r m u l a t e
quantifier-free
qf - ! ~
formula c o r r e s p o n d s
to q u a n t i f i e r - f r e e
"
A(x1'''''Xn) °
as an e q u a t i o n a l to an equation
calculus t = s ,
what amounts to the same, we can adapt the d e f i n i t i o n as in 1.5.6 the present
theorem.
formulae,
Then
b P r ° O f q f _ ~ A ( X ' ~ A ( X l .... '~n )~) Proof°
A I,...,A n by in-
(either
.
w i t h a rule of induction,
rule of substitution
with
o
b e i n g d e s c r i b e d as a r i t h m e t i c
qf - I - HA w , q f - HA w
Io5.9.
+ I
. .) .= ~('-A(:,: . . .I ,xn)-'
,.
quantifier-free
qf- P~,
formulae,
variants
, d(rAf))
not b e i n g of the f o r m
R e m a r k on q u a n t i f i e r - f r e e
In the various
by
°o
It is easy to adapt the d e f i n i t i o n
(namely
d
I
.
7
is not of the f o r m
~.
+
) = max(d(rA~),
and the b i n a r y o p e r a t o r
V) ,
d('~(Qxl)
I.e. we define a degree
stands for any f o r m u l a obtained from
sertion of b r a c k e t s
and successive
for prime formulae
n
where
a more r e f i n e d m e a s u r e of
disjunctions
of
(i.e. each
cf. 1.6 ~@), To .
or
We then prove
~8
Io5.10o Corollary to 1.5.3.
(i) (ii)
Let
~
be
qf-HA
with
R u l e - IN~
left out.
]HA ~ t [ x 1 , . . . , x n ] = y - - P r t t ( r t [ [ 1 . . . . . i n ] = [ 1 ) o There e x i s t s a ( p r i m i t i v e ) r e c u r s i v e ~t such t h a t
i~ Proof.
< = I .... 'Xn] =Y ~ P~°°f~(~t(=1"'''xn'Y)'%[~1
..... ~n] = Y"l.
( i ) i s immediate from (3) making use of
~b (ii) A ~o~
sR~D( rt ~, ~t'~) ~ Pr~(~t=t'~) • detailed
inspectie~
of the proof
of (2),
(~) i n
1.5.3 y i e l d s
(ii).
One firs~ establishes
(4)
~
PrOOfqf_HA(k[(Xl . . . . . xn'Y ) , r ~(x~,. ,. ,~n)=y')
b [(x fl' . . . . xn ) =Y
for the constants
[
of
H~,
suitable recursive
(ii) by induction on the complexity of
k[~
and then establishes
t o
For example~ in the proof of (4), we have to consider the case %hat defined by recursion from
b X(xl'''°,x ½
X, ~,
[
is
and assume as induction hypotheses
n) =Y " Pr°°fH(kX(X 1 . . . . . Xn ' y ) ' r x ( ~ 1 . . . . . ~n ) = ~ )
b ¢ ( ~ ' ~ o , % ..... Xn) = Y ~ ~r°°f!~(X¢(~'% ..... ~n 'y)'
r¢(~,~o . . . . . ~n ) = ~ l )
.
Now we note
~(0, x 1 . . . . . hence
=y ~ x(= 1 . . . . . Xn) = y ,
~)
P r o o f H ( k x ( x l . . . . . Xn ' y ) , r X(£I . . . . ,~n) = y l )
There exists a primitive recursive a proof of
X(X I ..... Xn) = y
~I
o
which transforms the g~delnumber of
into a number of a proof of
(since the ne~ proof is obtained by addin¢
[(0, xl .... 'in ) = ~
[(O,= I ..... ~n) = × ( ~ ..... i n)
(instan%iation of an axiom) and applying the equality axioms).
x~(o, x ~ , . . o , = n, y) Suppose Let
k~(z~ x1,°o.,Xn~ y)
[(Sz, xl,oo.,Xn) = y °
Now take
= ~ x ( = ~ .... ,Xn, y). to be defined°
Then
¢([(~, ~ , .... Xn), z, ~ ..... x n) =
and Gbbreviatin¢
¢(z,x~ ..... =n) as
Proo~(~¢([(~,~,ooO,Xn), Proo~(~¢(~,=~,...,=,¢(~, Combining the proofs and the instantiation
of
~)
~, x~ ..... = n, y), ~ ¢(~, ~, ~,...,~n ) =y~) =~ .... ,=n )),
@(~' z' Xl ..... xn ) = y
~ [ ( [ ~ , ~ .... ,~n ) = [ ~ ° and of
$ ( [ ' [1 ..... xn ) = ~
~(S~,~ I ..... Xn ) = ~(~'~'~I ..... Xn) , we obtain, primitive
recursively in %he numbers of these proofs, the proof number
k{(Sz, = I ' . . . . Xn' y)
of a proof of
{(S~, x1,ooO,Xn) = y ,
etc~ etc.
39
1.6.1.
Contents of the section.
This section deals with extensions
to theories involving objects of finite type. inductively
3 - 7 describe
~
defined
("E" from "extensional", free fragments Subsection
of
"WE" from "weakly extensional")
15 describes
8 intro-
9 it is shown
to an intensional
variants
q f - N - H ~ A ~, q f - ~ - H A ~, q f - W E - ~ a weak system
HA~,
~
variant
W E - K A ~, E-H~A m and the quantifier-
are described.
with its quantifier-free
in connection with the Dialectica
The reader who is not interested
(§ 3.5) may decide to skip this section, dealing with Subsection
part
16 discusses
and subsection
of combinators Subsection Directions
in the Dialectica
inter-
interpretation
and also the material
in § 1.7
HA w . pairing operators
17 describes
as a primitive.
for use.
skip §§ 1.6, 1.7,
qf-W~-~
with the
recursion m,
X- operator instead
on these subjects in § 1.7.
The reader who is primarily interested in
with the intuitionistic
in
which can
notes and a discussion of the literature.
1.8 altogether.
H~A, may
If the reader has no previous acquaintance
theory of f~nite types, he may find it enlightening,
after a brief glance at subsection of these theories described
I - 14, to have a look at the models
HR0,
in chapter II.
~.
Type structure
The t y p e s t r u c t u r e
N-~W
~ore material
18 gives historical
and simultaneous
a pairing for
even be used in a suitable version of
1.6.2.
N -HA w
and extensional
The system is of interest
pretation.
HEO
Subsection
in subsection
in a language with only equations between type zero terms as prime
formulae.
general,
of intuitionistic
N - H ~ ~.
10 - 14 the extensions
("I" from "intensional")
q f - ~HA w ,
N-~
~- operator,
is properly contained in
In subsections ~-HA ~
the basic system
in all finite types ("N" from "neutral")°
duces the combinatorially that
HA
in 1.6.2.
Subsections arithmetic
of
The type structure is defined
T
is
defined
inductively
by t h e f o l l o w i n g
two
clauses : TI)
0 E T
T2)
~,T 6 T =
Remarks. represents
(~)T E T.
(i) Intuitively,
each type represents
the natural numbers,
and if
~, T
a class of mappings from objects of type
~
(ii) There are many alternative
for
as
(o,~), ~ ,
~,
notations
a class of objects:
are types,
then
(G)~
to objects of type (~)T
type
•.
in the literature,
such
(~)~, etc.
(iii) Each ~ E ~ is of the form induction over I"
0
represents
(al)...(~n)O , as is readily verified by
4o
1.6.3- 1.6.7. 1.6.3.
Description of the neutral
Language of
for each type
N-~.
N - H A w.
The language contains variables ~ E T.
There is a symbol
theory
(indicated by
(Type superscripts
=
x ~, y~, z~, u~, v~, wa )
are often omitted.)
for equality between objects of type
~,
for each
E T ; we usually omit the type subscript. Furthermore, 0
of type
Z p,O~T
0
, Ra
there are constants (zero) ; S
for all
As logical
for objects of certain types : a constant
of type
p,a,v E T,
constants we use
(O)0
(successor),
and constants
H
a~T
'
whose types will be described below. &, -% v, Vx ~, ~x a
(for each variable
x~ ,
~ E T). 1.6.4. Let
Terms. Tm
denote the class of terms of type
Terms are defined inductively
Constants and variables of type
Tm 2)
t E Tm(a)T , t' E Tm a Notational
=
s, t, T
t1(t2t3)
So if
SXl...SXnA
as
tlt2t3...t n.
stands for
and provided
So
tlt2t 3
abbre-
(t1(t2t})) . for finite
x - (Xl,...,Xn) , VxA,= ~xA=
will be used to denote finite
(possibly empty)
abbreviate
(possibly empty)
that a term is of type
a,
strings of terms.
we often simply write
We shall often omit type superscripts ! but it is always assumed in
writing down an expression, are fitting).
that the terms are well-formed
SO, for example,
y E a, u E T, z E 0,
then
if we write
~ ~def slt1"''tm'
concatenation
however,
stands for
and if we assume
s i E (T1)...(Vm)~i , t
3
E T.
3
"''' Snt1"''tm"
Immediately after variable-binding
~ (Yl ..... Ym )
xyz = u,
(i.e. the types
x E (a)(p)T.
Let s ~ Sl,...,Sn, t -= tl,...,tm, = = (1~i~n, I< j (m) , then
indicates
if necessa-
respectively.
If we wish to indicate t E ~.
for terms,
to create more variables,
x, y, z, u, v, w, X, Y, Z, U, V, W
strings of variables.
s t t, T
variables
for clarity.
(...((tlt2)t3)...tn)
((tlt2)t}) , but
VXl...VXnA,
Tm
.
as syntactical
ry provided with primes or subscripts
We shall use
belong to
(tt,) E Tm
with a type superscript ~ s~, ta
viates
~
conventions.
We will reserve
We abbreviate
I ~ E ~} .
as follows :
Tm I)
1.6.5.
a , Tm = U I T m
so
operators V~
(V, ~
where
Vxi...Vx n VY1...Vy m
~)
juxtaposition~indeed
x= ~ (Xl,...,Xn) , etc.
41 1.6.6.
Formulae.
Let us denote the class of formulae as sions of the form
t~ =
s~ .
Fm
Fm.
Prime formulae
are expres-
is defined as usual by two inductive
clauses : Fm I)
Prime formulae b e l o n g to
Fm
Fm 2)
If
(A&B),
A,B ~ F m ,
(VxeA),
then also
(A--B) ,
(~x=A) .
In b r a c k e t i n g we f o l l o w the usual 1.6.7.
(A V B ) ,
conventions.
A x i o m s and rules.
(a) A x i o m s a~d rules for m a n y - s o r t e d (b) A x i o m s
intuitionistic
predicate logic.
for equality : x
= x
x
= y
& z
x
=y
~z
=y
~ x x
= z
,
= z
,
X ( ~ ) T = y ( ~ ) T . X(~)TZ ~ = y ( ~ ) T Z 0 , and the usual
s~
equality axioms for
Sx ° / O,
x o ~ yO @-9 Sx ° = Sy ° .
(c) The rule or a x i o m schema of i n d u c t i o n
(for arbitrary
formulae
of the
Ianguage ). (d) D e f i n i n g axioms for
H0,S'
~
0,~x 0y~ = x p ,
r~
O,o'
x~(y~)
x 6
(O)(c,)~,
y
~
(9)a,
z 6
O,
((O)(a),)((P)~)(O)~. R xy 0
= x
~x~(Sz) 1.6.8.
Theorem
(Definition
To each term
tT[x ~]
of the
(kx~.tT[xa])(t ') = tT[t ']
(ii)
Ix~ . tx a = t
for
x ~ / t',t" ,
R
t
k - operator).
kxa.t
not c o n t a i n i n g
(a)
x a ~ t ~ = kx~.t ~ ~def ff~,~ t~
Xxa.x %~ za,(o)~, n ,(o)ana, ° x~ / t ;
x a 6 t , or
then
such that
x~ ,
y
a variable
by i n d u c t i o n on the c o m p l e x i t y
(b) (d)
~X~tTIx a]
then
is defined
(c)
a term
(t' 6 ~) ,
t' = t" -- kx~Iy/t'It = k x ~ . i y / t " ] t , Proof.
z 6 0 ,
~ (~)((~)(o)~)(o)~.
we can construct
(i)
(iii) if
x ~ a, y ~ (~)(0)~,
I
y(Rxyz)~
=
different of
kxe'tx~ ~def t (x ~ E t I
Z(kx~.t)(kx~.t,)
.
and
t' / x ~) ;
then
kxa.tt v
def
t :
from
X .
42
Now (ii) is immediate
by clause
proved
by induction
simultaneously
As an example,
we prove
(a)
Let
x ~ ~ t~ .
(b)
Z ,(o)~,
(c)
Let
x ~ ~ t,
(d)
Let
x a E t , or
on the complexity = HT,
()~x~.tT)(t~)
n ,o
x
then
~, (o)
=
Xa(n
t~tl = t T ,
'° x a ) = x~ .
(x a E t'
and
t' / x a) ;
= Z(kx~.t[x~])(kxC.t,[x~])t"
=
In combinatoc~
with square brackets : X-notation
defined
and primitive
HA
the defined
for
kx.t.
X- operators,
~x.t , where
kx1.(kx2.(... 1.6.9.
logic, [x]t
X- operator
We find it more
instead ; but if one has to discuss
Abbreviation=
there
•
as a subsystem
of
is usually
written
suggestive
in a single
to use
context distinction.
stands for
N - I ~ m.
to each function
constant
~
of
~,
a term
T°
of
as f o l l o w s .
TO E 0 , TS ~ S , and if U~(Xl,...,Xn) If
@
Uin
= x i , we put
is explicitly
defined
is the function
T@ ~ kXl,..x n . T % ( T If
~
is defined
such that
T i ~ kx1"''Xn'X i • Un from $o,~I,...,~m
~ ( x 1 . . . . . Xn) = ¢ o ( ~ 1 ( x 1 . . . . ,Xn) . . . . ,~m(Xl . . . . .
(iii)
hypothesis).
should be a notational
x ~ (Xl,...,Xn) ,
(XXn.t)...))
Let us associate - I ~ ~,
(ii)
(induction
etc.
Remark.
(i)
t.
of
= (kxa.t[xa])t '' ((kx~.t'[x~])t ") = tit"It'[t"]
the
can be
(kx~.tx~)(t ') = tt' o
(kx¢.t[x~]t,[xC])t"
Etc.,
and ( i i i )
(i).
Then
~ ,(o)
(i)
(c) of the definition.
IXl...Xn)...(T
by primitive
such that
Xn) ,
we p u t
mX1...Xn) .
recursion
from
@I'
@2
such that
(0,x I .... ,x n) = ¢I(Xi ..... x n) • (Sz,x l ....
we p u t Then,
T
for any
like"
(iv)
A~ ~ T O
= ¢2(~(Z,X 1 ....
of
~
constant
More precisely, by induction
for each function
A~(t I ..... tn) ~ (A~)(Atl)...(Atn) A(t = s) ~ (At = As) ,
(vii)
A
t~ that
is a homomorphism translates A
under
is hi-unique.
w.r.t, A
~
of
HA,
if we define
constant
(v)
then
,x n)
"behaves
T Xl...x n a mapping
A
on the complexity :
(vi)
Note
,Xn)Z,X 1 ....
~ R T ¢ l ( k ~ y z . T¢2(yff)zff) .
n - ary function
~(Xl,..o,Xn).
and formulae
, x n)
~
of
HA,
Ax ° E x ° ,
,
logical
operators,
into a subsystem
of
~-~.
on terms
43
1.6.10.
Intensional identity or equalitF.
A basic feature of intuitionism is that we have to deal with mathematical objects as they are given to us ; for example, a species (set) of natural numbers is ~iven by a description
(definition) of a property of natural
numbers ; the extension of the set (in the classical sense) may then be conceived either as a mode of speech, to avoid speaking about equivalence w.r.t, membership,
or as an equivalence class, i.e. a species of higher type;
the latter point of view makes sense if we accept the concept of a power species. Similarly~
a (lawlike) function is given as a rule;
in the classical sense is a derived notion.
its extension (graph)
From a foundational point of
view, it is therefore natural to pay attention to the concept of definitional or intensional equality : two objects are said to be definitionally or intensionally equal, if they are given to us as the same oBject. We do not a priori suppose the concept of "definition" or "description" to he restricted to definition in a given language. Whatever the precise content of the concept of intensional identity,
it
seems clear that it should be decidable whether two objects are definitionally equal or not.
This is expressed in the extension
I-HA ~
of
N-HA w
described below. 1.6.11. In
Description of
I - H~ ~.
I - HA ~ , the intended interpretation of
ity between objects of type a constant
E
e (~)(a)O
E xay ~ Ecx~y~
a ; I-HA ~
for each type
0 e-~ x a
in~e~sional equal-
is :
~ 6 =T
N-HA ~
by adding
such that
y~
0 V Eaxa y s
=
=
is obtained from
=
I
~
which implies decidability of equality at all types : x 1.6.12.
= y
V xa/y ~ .
Description of
E-~,
WEE-H~A w.
Another way of interpreting equality in extensional equality: argument of type
(I)
~
two objects of type
(a)T
they yield equal values.
vz (~)~ u(~)~(z=u
Adding (1) to
N-HAm
N-HA m
is assuming it to be are equal if for every
This amounts to
*-~ Vya(~y°uy)) .
yields an extensional version of intuitionistic
arithmetic in all finite types, which we may denote by
E - H A ~. ~O
For some purposes (notably the study of the D i a l e c t i c a - i n t e r p r e t a t i o n in Chapter III) it is more convenient to use another version of be denoted by
E - H A w.
Here equality between objects of type
E - H A~ o ~ 0
' to is the only
44
primitive concept, equality for all other types is a defined notion (inductively on the complexity of the types)
~(~)~
u(~)~ -=def VYa(~y:uy) "
:
The axioms for equality of redundant, such as
N-~
are retained (but some of them become
z = u -~ zy = uy,
which now holds by definition) ; the full
force of extensionality is now in
(2)
x ~ = y~
Note that
~
E-HA m
~(=)~= : ~(~)~y. may be interpreted as a definitional extension of
obtained by addition of new symbols to
E- ~ ® ~-~®
is
obtained
from
=
E-t% ~
E-~m
for definable equality of type
weakening
(2)
to the f o l l o w i n g
rule
o f ext ensionalit,y
EX~-~.
t- t ~ l . . . x n
(A(t) in
quantifier-free,
A, t, s , such that
tion
~F
t-A(t)
: sx~...Xn,
x1,...,x n txl...x n
indicates that
F
= ffA(s)
a sequence of variables not occurring
and
sxl..oX n
are of type
0 o
The nota-
has been derived without assumptions.)
A
slightly stronger rule is EXT-R'. ( P
~- P -- t x 1 . . . x n : s x 1 . . . x n ,
ffA(t)
= f f P -- A ( s ) .
quantifier-free, other conditions as before.)
~ - ~
cf. Io9.25- 1.9.27 ) Note also that
(3)
EXT-R
EXT- R
~- t x l . . . X n
where
In certain analogues of
(theories with bar recursion of higher type, or induction over trees;
Fix a]
must be replaced by
EXT-R' .
is equivalent to the following rule
= SXl..-x n
~
ffF[t]
:FIe]
is a term in the language of
formula, we can always find a term
FA[X ~]
,
E-~
~.
For, if
such that
A[x ~]
is a
FA[X~]=O*--~A(xa)
(see 1.6oI~) ; therefore, from (3)
tx1..oXn=
sx1...x n
=
f f F A [ t ] = FA[S ] ,
hence
~txl...~ Conversely, apply viously
holds,
and
: s~l...x EXT-R
n
ffFA[t]
with
A(s) ~ F[t]
= F[x ~]
~
ffFA[S]
for
: o
A(xa) , then
A(t)
ob-
= F[s].
If we would have formulated (4)
F[t]
: 0
A(t), tXloooX n = s x l . . . x
EXT- R
n
as
~ A(s)
(conditions as for
EXT-R,
tx1.o.X n = sX1.o.X n
depends), then the resulting system does not satisfy the
deduction theorem.
For (4) implies the axiom of extensionality (2),~nce (4)
yields
but
Xl,...,x n
not free in assumptions on which
45
x :y=, z (~)Tx a : z(=)~x a
b z(=)~x = : ~(=)~y=
hence the deduction theorem would yield
(2).
From results in Howard
however,
it follows that (2) cannot be proved in
EXT-R)
and that therefore
deduction
W~-~
w
of
qf-N-HA
The quantifier-free qf-N-HA
w
~,
part of
qf_ ~_~w
~ - I ~ ~,
qf_WE_H~
~ - H ~ w,
WE-HA~,
etc., may be obtained from the corresponding
quantifiers
From logic we drop quantifier rules and - axioms. in
of type (ii)
q f - W ~ E - H A w,
t ° = sa
taxl ...x n = s~ xl..°x n,
abbreviation for t, s
denoted as theories with
as follows.
deductions
in
(with (4) replacing
in this version does not satisfy the
theorem.
1.6.13. Description
(i)
WE-HA w
or (open) assumptions
In discussing
is then to be conceived as an Xl,..o,X n
of the deduction,
variables not occurring such that
tx1.o.X n
The induction
schema is replaced by the induction rule :
A(O), A(x) ~ A(Sx °) = Ax ° , for in assumptions
(iii) Ax s ~ At ~ , if
1.6.14.
x
quantifier free,
qf-WE-~
~
systems in
with
EXT-R'
q f - ~ - H A ~,
qf-~.-H~A w
qf_ ~_~w
propositional
not occurring free
qf-WE-~
I 58 ) instead of
theorem holds even if we liberalize
Since in
x
does not occur in (open) assumptions°
on quantifier-free
Note that for deduction
A
of the deduction.
(Cf. our remark
EXT - R'
as equational w
formulae are decidable,
E X T - R,
the
by deleting
~.
calculi°
prime formulae are decidable,
all
and therefore the propositional
ators may be represented by certain constant
terms expressing
oper-
the classical
truth functions. We consider the case of recursive functions
qf- ~-HAW:
(of type
Let
(0)(0)0)
con(Sx,y) = con(x,Sy) = SO,
con(O,0)
=
dis(S~,Sy)
=
imp(Sx,y)
= imp(x,0)
imp(0,Sx)
= S0o
dis(O,x)
Now we construct, T A = 0*--*A Tt= s
=
o ,
= 0
,
for any propositional
con, dis, imp
be primitive
such that
disCo,x)
For
is
0 o
=
O, so,
A , a term
TA
such that
: we take
Ets.
TA& B ~ con(TA,TB) ; TAV B ~ diS(TA,TB) ;
TA~ B ~ imp(TA,TB). Similarly for q f - W ~ E . - HA w ; here we only need to put
Tt= s ~ It-s I .
4g
1.6.15. The szstems
~w
qf_H~Wo
In connection with the Dialectica interpretation subsystem
~w
of
~-HA ~
is of interest.
ed in the Dialectica interpretation
can omit this section,
till he arrives at studying the Dialeetica The only prime formulae of the constant s are those of type
0
as a primitive.
predicate
logic°
x
0
= x
0
Sx ° % 0 substitutivity
x
~
x°
= z
0
0
& y
0
=z
0
~ x
0
=y
0
y° ,
~S
~ o fly ]
=
(which may be viewed as very special instances
of
t[~]
] :
t[xz(yz)] fix],
tERxy(Sz)]
is clearly a subsystem of over
the
rule), for all t E 0 :
t[RxyO]
conservative
schema,
objects :
schemata
lt[nxY
to
intuitionistic
axioms consist of the induction
y°~-cSx°
=
%t[Zxyz]
m ~
0
except that we now only need equality of
~N-HA~,
tie]
the extensionality
are equations between terms of type
equality and successor
for type
and the following
or postpone it
interpretation.)
The logical basis is many-sorted
0 0
,
xo = y e
SUB
HA ~
The nonlogical
usual axioms for type
in § 3.5, the following
(The reader who is not interest-
HA Wo)
~-~o
qf_~w
= t[y(R~yz)Z]o
(~e do not know ~hether
~-~
is defined in the obvious way,
is
similarly
qf - K - m--~"
Remarks~
(i) The schemata
SUB
t [ ( k x ~ o t ' ) t ''] =~[[x~/t"]t '] for
give us for the defined
(te O) , and especially
X- operator :
(>~.t)t'
= [x~/t']t
t E 0.
(ii) If we use F[tt]
t ~I = t2
for all type
0
x~)°-¢~I = x(¢)°-¢~2 ° versely,
taking for
as a metamathematical terms For
abbreviation for
F[x ~] , then we see that
~F[tl]
t I = t2
t I¢ = t 2¢ implies the latter assertion,
x(~)° :
Xx~. F[x~] , we obtain
~F[%1]
=
amounts to and con-
: F[t2] , in
view of the preceding remark. (iii) 1.6.16.
HA
is of course also a subsystem of
HAlo
Simul..t..aneous recursion and pairin~ : a comparison of various
treatments. We have formulated
our system
For certain applications, simultaneous ¢i6 T
for
recursion: I < i
(to be abbreviated
~_~w
however,
for each sequence of types
one requires as
with a primitive
Re.
or
R)
R
for each
(cf. § 3.4, 3.5) one requires
a sequence satisfying
~* ~ <~1,...,~n > ,
of constants
R~.,
c.
constants for
Rn
4? (~)
~zo
~(Sz)
=~,
=~(~z)~
where ~ ~*~ ~ = (YI'''"Yn)' Yi ~ i ~ (~I)'"(%)(0)%' Ri ~. c (~I)'°'(%)(~I)'"(~n)(°)~i, liiin. I% has been shown by Schutte
(see Hindley- Lereher- Seldin 1972, p.156)
that constants for simultaneous
-HA m
(1.7.7)
fier-free
;
the p r o o f
fragment of
reoursion
that
qf-~-HA~
recursion
satisfying
t h e y satisfy ( i )
(1) can be defined in
can be given in t h e q u a n t i -
(1°5°13)o
A more complicated way of constructing course-of-values
l
is described
constants
R , via simultaneous
in Diller- Schutte
1971o
If one wishes to avoid the fairly long and ad hoc argument needed to obtain R =
from
R
, there are various possibilities°
(A) One may i n c l u d e scriptions
constants
of
~-}~9o
satisfying
Since q u i t e
and t e r m s can be d e a l t
variables
~.
with
(1) a s p r i m i t i v e s
consistently
in notation now and then.
followed in Troelstra
sequences o f v a r i a b l e s
difficulties
apart from a
(This alternative has been
1971.)
(B) One may extend the type structure Cartesian-product
de-
i n complete analogy to the t r e a t m e n t of s i n g l e
and terms, this causes no particular
certain awkwardness
in the
types,
T
adding to
to a structure TJ , T 2
T'
including
a third closure condition
( X binds stronger than application) : T3) : ~,T e T' = ~ Xm e T' (and replacing
T
by
T'
and to the set of constants with inverses
D' ~T
in T1 , T2
).
e ( ~ ) ( ~ ) ~ x~
one adds pairing operators
E (~ ×T)~,
(~×~)~
D"
(for a l l
~,,cT')
wit~
~T
axioms
(2)
D,(~xy)
= x,
(3)
D(D,~)(D"~)
~,,(Dxy) = y , = ~.
It is shown in 1.8.2 that this enlargement expansion
(and a f o r t i o r i
a conservative
In the presence of pairing operators (3))~ we are able to define operators a* = (~l,OOO,an)
N_HA m
extension)
("p " for "pairing) of
~_~mo
satisfying (2) (but not necessarily i D . , D ~. for n - tuples
such that
Di(Dxlo°.Xn ) = xi ,
1 < i < no
By a standard trick well known from recursion theory, eursion operators may then reoursiOno
be defined ; we illustrate
simultaneous
T ~ R%~2(Dxlx2)(Xuz. prove by induction
D(Yl(D'u)z)(Y2(D'u)z))
re-
the process for double
We put
Thee ~ c r e a d i l y
is an
.
48
D'(TO)
= x I,
D"(T@=
~2
D'(T(Sz)) = YI(D'(Tz))z, and
therefore
we may
D"T(Sz) = Y2(D"(Tz))z
take
R ~I,~ I 2 ~ kxlx2YlY2Z • D'(Tz) ,
~ KXlX2YlY2Z. D"(Tz) R ~I,~2 2
•
It has been shown in B arendre~t A that it is impossible to define in
types
~ XT 6 T ,
and o p e r a t o r s
D 6 (~)(T)~ Xr,
D' 6 (~ X T ) ~ ,
~-~w
D" 6 ( ~ X r ) T
satisfying (2). In suitable versions of is possible to construct
~-HA w
with the
a × T ~ D, D', D"
k - o p e r a t o r s as a primitive it such that (2) is satisfied
end of 1.6.17) ; then, of course~ the constants A fortiori~ in the extensional system
R=
qf-~E-H~
(see
can be defined. w,
it is possible to
define product types and pairing operators such that (2) is satisfied (of. 1.6.17), so in extensional contexts simultaneous recursion does not cause any problems. It should be noted that the methods o~ Soh~tte from H i n d l e y - L e r c h e r Seldin 1972 , or of Diller and Schutte 1971 do not extend automatically to other schemata for defining functionals which have "simultaneous" and "single" versions, such as bar-recursion, or definition by induction over well-founded trees;
in such cases, we are forced to fall back on the methods of treatment
described under (A) and (B).
For this reason, we have e.g. in § 2.3 indicated
a treatment of computability including pairing operators. 1.6.1~ Pairing operators in
qf-WE-~
w.
A pairing operator for the extensional theory, with inverses, is implicit in the~Y-pure types (1.8.5- Io8.8), since in the description of the reduction pairing operators with inverses for the pure types are given. Assume a product type
0 X 0 6 T , and operators
Do,o, D' D" O,O' 0,0
to be
given such that
(1)
D~ ,o(Do, ° x yo
o)
=x, o
D"
(Do,oX°Y°) = y o
O~O
Then product types D~, r 6 (~ XT)T
~ XT,
and operators
D~,~ 6 (~)(T)~ XT,
(satisfying 1.6.16 (2)) may be constructed relative to
Do,o, D'o,o, D"o,o
as follows.
~ (al)...
(~m)O,
Let
w ~ (T1)...
(Tn)Oo
~e put ~XT
~def (~1) "°" ( ~ m ) ( T 1 ) ' ' "
(~n) OXO
and define 0°
D'a,T £ (~ X T ) a ,
~def 0,
0 (~)* ~ def
H
~,~
0r
49 , ~
D
•
~I
... x m
x I
... x m
D ~~, T
~ ^z
~Z~X~y~11
D"~ , T
TI
~m
T ~ ~x y x I
Tn °°" Yn "Do,o(XXI"'•XmJ(YYI"''Yn
Yl
*
~n
D'O ~ o Z X l
. D"
°'• Yn
o,o
•
zO
..x m 0
"'"
TI o°"
0 Tn ,
Yl "'" Yn
oSm
J'
°
Then
D$,T(Do,TX
) =
Lx I
=
...x m
. D$,o(Do,o(XXl...Xm)(YOT1°..oTn))
~.x I
~m °°-x m
• XXI~..X
= 0 , and
Do,o'
Y
°'I
and similarly
for
We may take pairing
D"
function
j
=
X
.
a,T
0×0
m
with inverses
o,o'D' D"o,o
J1' J2
to be given by the standard
(~ $.9
)
Do, ° ~ ~y.j(x,y), D,o,o ~ it' D"o,o ~ J2' Alternatively,
=
if we take
0 ×0
jlj(x,y) = x, j2j(x,y)=y.
~ ((0)(0)0)0 , and we define
Do,o =def ~Oy%(O)(e)o
~Y,
D'
o,o -=def ~(o)(o)o,o n o,o'
D"
o,o
def ~(o)(o)o,o
H~
o,o
where Aa,T then
~xay ~
def
(I) is satisfied
variant
of
°
y x
again;
qf-N-HA
w
,
o,o
in fact,
with the
~
we can now establish
X - operator
Lx.tx= t
of the induction
(cf. also the discussions
1.6.18.
Historical
notes ; variants
A quantifier-free to
qf-!-H~
only,
~)
extensional
version
In Kreisel
recursion,
1959, Specter
Spector's
x= ( y--= z)
,
contain
constants
for defining
recursive
functionals
1958.
axioms
it is obvious
(correspondirg
The system is sketched
and rules is given. that an intensional,
1962 , and Grzecorczyk
theory is studied. system corresponds O, S , constants
~nP
functionals
paper also contains
use
From not an
was intended.
of the quantifier-free
functionals
x , but without
in 1.8.4, i 2 % [ - 3 q ) -
in Godel
list of primitives,
1958 , however,
(2) in a
with rules
in the literatureo
was first introduced
3 in G~del
does not contain
theory of primitive
i°eo no detailed
footnote
t
1.6.16
as a primitive,
t = t' = kx.t = kx.t', rule
if
Kxy. y ,
def
(projection)
qf-WE-~
and
m.
(substitution)
sat~fying
by composition
the generalized
to ~s
1964 an extensional
If we disregard
His primitives satisfying
for
~s~
=
~ x I o o .x n : xl , and schemata
(primitive)
induction
version
the schema of bar-
rule
recursion.
(1.7.10).
Spector's
5o
In Kreisel
1959, the type structure
section 5 of Specter schemata,
1962 , Kreisel's
The first
1964 describes
R ' x y O = x,
satisfying
Ix=x 7
R'xy(Sz) = y z ( R ' x y z )
°
In Tait
also describes
1967, the full intensional
D i l l e r and Sshutte (contained in The pairing
E~
to
theory. 07 $7
and
D x y = xyy 7 07 S7 I,
and
defined ones.
in detail° with logical
I - ~w
operators
, but with
x
=y
is Vxa~
ya
as a primitive.
1971 seems to be the first paper where a neutral
qf-N-HA
theory
w ) is taken as a starting point.
operators
described
of the subject ; the first variant This v a r i a n t has the advantage al equality for the typed
in Io6o17
seem to belong to the "folklore" ~73. in 1.6.17 is e.g. found in Luckhardt 1970 ~
of being consistent
X - calculus
studies of the f u n c t i o n a l s
theory of combinators,
from p r e v i o u s l y
theory,
studied ; Tait's f o r m a l i s m corresponds
X - abstraction.
and contains
C x z y = xyz,
The second set is based on
pairing operators
as an axiom instead of h a v i n g
As noted in
of the q u a n t i f i e r - f r e e
Bxyz = x(yz)7
five schemata for defining new f u n c t i o n a l s Grzecorczyk
types.
by a schema p e r m i t t i n g
two variants
set is based on closure u n d e r composition7
I, By C 9 D, R~
Other
product
schemata are very similar to Spector's
but have to be supplemented
Grzecorczyk
includes
of
are eogo Sanchis
with a n o t i o n of
(cf. end of Io6o177 N-HA w, 19677
Barendre~t A).
in the context
Stenlund
~mke~sion-
of a typed
1971, ~ 9 7 ~ .
51
§ 7.
Induction and simultaneous
recursion.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
1.7.1.
Contents of the section.
detail concerning and extensions
The section discusses various points of
induction and simultaneous
of these systems.
recurslon in
qf-~-HA
~, HA w
The reading of the section may be post-
poned until the need arises. In 1.7.2- 1.7.7 we describe a method, constants for definition by simultaneous simple recursion. interested
due to Sch~tte,
for obtaining
recursion from the constants for
Proofs are carried out in
qf-~-~.
If the reader is
say in a discussion of modified realizability,
interpretation
(in § 3.4, 3.5 respectively),
and wishes te avoid the tedious
details of 1.7.7, he may either simply believe the result, structure extended by Cartesian product of formation simply postulate
in the description
of
or the Dialectica
N-HA ~
(cf.
or use the type 1.8.2), or
simultaneous
recursion
outright. In 1.7.8- 1.7.10 we obtain an induction lemma, interpretation
In 1.7.11 we briefly discuss iterator may replace Subsection
1.7.2- 1.7.7.
1971) how the
the treatment of simultaneous
recursion and
HA ~ .
Simultaneous
Definition.
(following Diller and Sch~tte
the recursor as a primitive.
1.7.12 discusses
the induction lemma for
1.7.2.
needed for the Dialectica
in § 5.5, taken from Spector 1962.
recursion in
q f - N - H A ~.
We put
prd ~def kx. RO(Xyz . y)x,
x=y ~def Rx(~uv. prd(u))y x>y
~def x ~ y
xZY
~def (x>y) V x = y ,
The following
x
~def y > x
x!y
In
(i)
prd(O) o o ,
(ii)
x;O
= x,
( i i i ) prd(x)/o(iv)
Sx=Sy x=x
(vi)
Sx~x
below,
but espec-
is that we wish to verify that they indeed have quantifier-free
Lemma.
(v)
7
The reason for explicitly proving all these elementary
proofs. 1.7.3.
~def Y Z x
two lemmas will be needed in part in 1 7
ially in |.~.|O. properties
/ O,
= x~y = o = I
qf
N-HA ~
prd(Sx) ° x x~Sy = prd(x=y) x/o
5~
x~0-~
(vii)
x=Sprdx
(viii)
Sy_<x "~ y < x
(i~) (x)
y<x
-~ x "--y- S(x "--Sy)
Sx'--y = 0 "~ x'-Uy = 0 .
Proof.
(i), (ii) immediate
(iii),
Contraposition
of
, Induction on
(iv) Sx~Sz
= x~z
,
y :
then
f r o m the definition. x = 0 -~ prd(x) = 0 . assume
Sx'--SO= prd(Sx--O) = prd(Sx) = x=x'--O ;
Sx~SSz
= prd(Sx~Sz)
= prd(x ~ z )
= x~Sz
apply
;
rule of induction. (v)
: By (iv) and induction on
(vi)
:
Induction on
x.
(vii) :
Induction on
x:
then
x.
O/ 0 ~ O= SprdO;
assume
z / 0 ~ z = S prd z ,
S z ~ 0 ~ S p r d ( S z ) = Sz .
(v~i) : TO show
x±Sy/
x = Sy ~ y . p r d x ,
0 V x = Sy " x = y /
so
x ~y=
~Sy/O-prd(x~y)~O,
Sprdx
so
(ix)
: y<x~
x!y~O
(x)
: By induction
1.7.4.
Lemma.
In
Proof.
I n d u c t i o n on
I
(by vi).
(byiii).
~Sy/O-x~y~O
; x~y~O on
O.
m prdx=
~ Sprd(x~y)=S(x~Sy)
.
y.
qf-N-HA
~
y < x ~ x ~ (x.ty) = ~ .
y.
(I)
O<x--
x:(x±O)=x~x=O
(1.7.5
(2)
so<x - ~
(~=so)
: x= prdx : I
Sz<x -
(x=Sz)
= Sz
, (v)),
(1.7. ~ ,
(~i~).
Assume
(3) If
SSz<x,
x~Sz
then
.....S ( x ~ S S z )
SSz<x,
.
hence
Sz<x
( 1 . 7 . 5 , (viii) ; with 1.7.5(Ix)
(x=Sz)
= Sz/ O,
o
prd(x~ (x~SSz)) (1.7. 5 ,
x=
=x~S(x~SSz)
=x~
so
x~(x=SSz)
= SSz
(vii)).
Hence
(4)
(3) - [(ss~<x) - x ~ ( x = S s ~ )
(2),
: ss~]
.
(4) give the i n d u c t i o n rule
(5)
sy<x-
(x: (x=Sy)
Hence also by i n d u c t i o n f r o m 1.7. 5 .
Simultaneous
sy.
(I),
r e c u r s i o n in
For each sequence of types of constants
=
Ri ~I~.,.~O
(5),the a s s e r t i o n of the lemma. qf-N-HA~.
~I' "''' G n
~ i = 1,...,n n
we wish to construct
(abbreviated
as
R) =
a sequence
such that for
55 sequences of variables
x ~ xl,...,x n , y m yl,...,y n,
where
x i E ~i '
Yl ~ (~I) "'" (%)(°)ai (1)
~o
= ~,
~(s~)
o~(~)~.
In order to ob%ain constants
R
as required in (I), it is sufficient to
=
establish the recursion rule : I If (2)
~, ~
are sequences of closed terms (of fitting types),
is a sequence of closed terms
~
such that
there
~0 = ~,
T(Sz) = Sz(T~). To obtain (I) from (2), we apply (2) with (with
~
and
~
having the same types) for
satisfies the equations for
~O~y = ~ , and therefore
k~
kzx~.
R~z
,
T(Sz)xz o ~(T~)z
b~=y z. T z x y
.x , t, ~
~(~y)v
respectively.
Then
=T
i.e.
,
satisfies the equations
The method for establishing
kv°~.
(I) for
R.
(2) below seems to be due to Schutte * (cf.
Hindley, Lercher and Seldin 1972, page 156) ; a stronger result (simultaneous course- o f - v a l u e s
recursion)
is established in Diller and Schutte
1971 ; this implies (2). 1.7.6.
Pairing functions for objects of equal type.
Let P ~
be a pairing function of type p xS y q O
For
P
= x~ '
Pa xcya(Sz)
(G)(~)(O)~ , satisfying
= ya .
we may take P~ ~def kx~yazC . Rx(ku~v ° . y)z .
1.7.7.
Theorem * (Sch~tte).
Proof.
We establish this by induction on the length of the sequences
The recursion rule (2) of 1.7.5 holds.
For length I the solution is given by hypothesis) to construct (5)
Rt(kuv. svu).
(2) to have been established for t1' "''' ~n+1
~, ~
~, ~.
Assume (induction of length n.
We wish
such that
/ ~i(O) = ai [ ~i(Sz) = biz(~Iz ) .-. (~n+1 z)
where Let
ai, b i
(1~i!n+1)
are constants of the appropriate
R' = kxyz . Rx(kuv. yvu)z , so that
type.
R'xyO = z , R'xy(Sz) = yz(R'xyz) .
I am indebted to R. Hindley for communicating to me a correction to page 156 of Hindley, Lercher and Seldin 1972, together with the proof given below.
We put t = X U l . . . u n . R ' a n + l ( X V . bn+lV(UlV ) . . . (UnV)) t i = XVUl...UnW. P ( u i w ) ( b i v ( u l v ) oo. ( U n V ) ( t u l . . . U n V ) ) ( w : v ) By induction t~O
hypothesis, = ~a.
1
t~(Sz)
i
* "''' t*n t1'
there are
= tiz(t~z )
'
such that,
for
1
(t~z) "'"
"
We put ~. -= ~z. t*zz,
l
tn+ 1 -: X~. t ( t ~ ) . . . Now
(tn~)~.
(3) is proved by induction.
Case a,
I< i< n . {.0 = t~O0 = ~ a , O i
I
{i(Sz)
= a.
1
I
= t~(Sz)(Sz)
= tiz(t~z ) ... (t~z)(Sz)
=
= P(t~z(Sz))(biz(t~zz ) ... (t~zz)(t(u~z)... = biz(t~zz ) ... (t~zz)(t(u~z)...
(u~z)z))1
(u]z)z)
= biz(~iz ) ... ( ~ n Z ) ( t n + l Z ) • Case b,
i = n + I.
We first establish
(4)
t~(z+w)z 1
We prove For
= ttzz
for
I < i < n,
all
w.
1
this by induction
on
w.
For
w= 0
(4) is immediate.
w > O,
t~(~ +S.)~
= t i*(s(~+w))~
=
= ti(~ +.)(t~(= + w))... ( t ~ ( ~ + w))~ = = P ( Z [ ( z + w ) z ) g ( z ~ (z+w)) = t ~ ( z + w ) z = t~zz (the exact form of the expression z ~ (z+w) = 0 , derived Now we establish, (5)
by induction
for all
on
is irrelevant on
w
from 1.7.3
(v) as basis).
bn+ I ~ ( t ~ ( z + w ) v ) . . .
(t~(z+w)v))z.
z.
t~n+10 = t(t~O)...
(t~O)O =
= R ' a n + l ( X V . bn+ 1 v ( t ~ O v ) . . . which is equal to the right hand tn+1(Sz)
here ; we must use
z, w
~n+1 z = R ' a n + l ( X V .
We use induction
~
= t(t~(Sz))...
(t~Ov))O = an+ 1
side of (5) for (t~(Sz))(Sz)
=
= R'an+1(XV.bn+ l v ( t ~ ( S z ) v ) = bn+l~(t~(Sz)~)...(t~(S~)~)*,
...
z = O.
(t~(Sz)v)(Sz)
=
•
55
where
¥ m R'an+1 (~v" bn+ I v ( t ~ ( S z ) v ) By the induction h y p o t h e s i s
for
...
(t~(Sz)v))z
z , using
.
w= I ,
¥ = ~n+1 z • Also,
by the induction
hypothesis
for
z , using
Sw
~n+1 z = V' = R ' a n + l [ X V . b n + I v ( t ~ ( z + S w ) v )
for
...
W
(t*(z+Sw)v)]z
,
hence
~n+l(SZ) = bn+lZ(t~(Sz)z ) ... (t~(Sz)z)V' = b+lz(t~(S~+,)z)... (t~(S,+-))~' (by (4)) = R,an+l[XV.bn+l v(t~(Sz+w)v)... (t~(Sz+w)v)](Sz) . This establishes
Now we can complete
(5).
~n+1(Sz)
= t(t~(Sz))...
the proof :
(t~(Sz))Sz
=
R'an+1[~V.bn+1 ~(t~(Sz)v)...
(t~(Sz)v)](Sz)
=
bn+1~(t~(S~)~) ... (t~(s~)s)~", where ~,,
- R,an+~(~v. b + 1 , ( t ~ ( S , ) v ) . . . = ~n+flz ,
tn+l(Sz)
= bn+iZ(t~zz).-.
bn+1~(~Is)...
=
and since also is irrelevant)
(t~zz)(En+Im)
(~n~)(~n+~),
~n+10 = t ( t ~ O ) . . .
(tnO)O = R'an+IgO = an+ I
(the form of
the proof is completed.
1.7o8-1.7.10.
The i n d u c t i o n
1.7.8.
Let
Lemma.
(t[(S~)v)~ =
hence
~
lemma for
qf-N-HA
w.
be a sequence of terms of
N-~W
and let
a sequence of terms defined by means of the r e c u r s i o n operator tOxv
= v,
=
where in
qf
=
x,y ~ O . N
Let
=
Q
= T(x--Sy)(tyxv) =
=
be a predicate
be
,
=
such that
(x, =v not free in
F)
HA m
rbQ(x, Then in
t (Sy) x v ~
t
such that
~_x_v)-Q(s,,v),
rbQ(o,=~).
qf-N-~®
Proof.
In order not to encumber our t y p o g r a p h y we let
Assume
z< z ,
U.
Then
x--z = S(x--Sz)
(1.7.3,
t -= t , v -=v , T = T .
(ix)) ;
=
=
56
t(x~Z)XV
= t(S(x~Sz))xv
=
= T(x~S(x~Sz))(t(x~Sz)xv)
=
= T ( x ~ (x~ ~))(t(x= s~)xv) = = Tz(t(x=Sz)xv. Since
~Q(x,
Txv) ~ Q(Sx, v) ,
it follows that
Q(~, T, (t(x~Sz)xv)) This implies 1.7.9. then in
Q(z,t(x~z)xv)
Lemma.
When
~ Q(Sz,t(x~Sz)xv)
satisfies
.
the conditions of the previous lemma,
~
qf - ~ -
r p y~ Proof.
Q
- Q(Sz, t ( x ~ S ~ ) x ~ )
- Q(y,~(x~y)x~)
Induction on
.
y.
O i x -- Q(O,~xx~)
( s i n c e C ffQ(O,v)).
A s sume
Then Sz!x
~ z < x,
hence
Sz~x--
Sz!x
" z!x
hence
Sz&x
,
(Q(z,~(x~z)x~)
-- Q ( S z , ~ ( x ~ S z ) x ~ ) )
-- Q ( z , ~ ( x ~ z ) x z ) .
hence
szix 1.7.10.
Induction lemma.
Q(s~,~), Proof.
Q(sz,~(x~ s z ) x S )
then
rp
In
qf-N-HA
Q(~,~)
(x C
By the previous lemma,
r pQ(x,~ox~),
i.e.
Note that for
v
w
n o t o c c u r r i n g f~ee i n
P ~ x~x
~ Q(x,t(x~x)xv)
r). , hence
rpQ(o,~).
consisting of a single variable,
the proof only requires
simple recursion. 1.7.11. Theorem. Schutte
1971.)
corresponding TE T )
(Replacement
of
If we replace in axioms by a constant
Ra
by the iterator
qf.N_~W J
,
J
; Diller and
the constants
R
the iterator of type
with its 7
(for each
satisfying %xyO
= x , J xy(Sz)
then a constant Proof.
The
define
Pa
satisfying
= y(Jjyz)
(x~ 7, y E (~)~) ,
the axioms for
R
becomes definable.
X- operator can be defined as before. In terms of ~ G x~ G as x y "Ja (H @y ) ; then obviously G
Pox y 0 = xa ,
P x~yC(Sz) =
y~
J~
we may
,
57
Next we define
U m kx I . Jo(xI(SO))S.
Ux+O
= x+(SO)
ux+(so)
° s(x~(So)).
Then
This function enables us to define a predecessor
function :
~o y • j(Ho,oO) U y o 0 .
prd ~
We prove by induction on
y
J(Ho,oO)Uy (SO) = y . Then it follows that prdO = J ( H o , o O ) U O 0
prd(Sy) NOW define
QT Q
= Ho, o 0 0
= 0
= J(no,cO)U(Sy)O
° U(J(no,oO)Uy)O
= J~no,oO)Uy~so)
o y.
o
as
~ kxyz[x(y(prdz))(prdz)]
(z~ O, y E (O)v, x E (m)(0)T) .
Then
%xy(S~)
= x(y~)~.
Finally we put
~
~ ~'y(')(°)'~°[j(o),(H,oX)(%y)~
]
and then
RTxTy(m)(O)'o =
RTx'y(')(°)'(Sz
x',
) =
y(Rxyz)z.
Q.e.d. Remark.
In the sequel we have usually dealt directly with
tive ! occasionally,
in applications,
R
as a primi-
there might be a slight advantage in
using the iterator as a primitive. 1.7.12.
Simultaneous
recurs%on and the induction lemma in
We note that the proof of the induction lemma (1.7.10), neous recursion is available, difficulty.
For the case
can be carried over to
v= v
(i.e.
v
qf-HA~. provided
qf-HA m
simulta-
without
consists of a single variable)
we
only need simple recursion. In the proof of closure under simultaneous in establishing
(5) in 1°7.7.
A(z,w) where
3[z,w]
by the following
the crucial
step is
(5) as
~ (~n+l z = S[z,w])
represents
Assume ~n+IZ E ~,
recursion,
Let us abbreviate
~ ~ (T)O.
the left hand side of (5) in 1.7.7. Inspection of the argument in
sequence of equalities:
I.?.7
shows that
58 = ~(bn+IZ(q(Sz)z)... = u~(bn+lZ(t~(Sz)z)... = u~(bn+IZ(t~(Sz)z)... = u~s[S~,.]
u~(~n+1(Sz))
the a s s e r t i o n
u~(~n+1(Sz))
r[ua's[z'']'z]
(I) where
r[u~,v~,z]
Le~ us put
stands f o r
0 ~
n+1
from
then ( I )
(t~(Sz)z)v;)
is equivalent
.
to
T o u , e[,,1].
intuitively :
L"
Vw<x(um({n+1(Sz))
introducing
0 °
f
=
fu%x
(2) can be expressed
f(To~),(Sx)
0
for all
=x
0
recureion,
can be expressed by
such that
- u¢s[z,O]i
. lu~(~n.l,)
- u%[~,S~]
I .
as
= 0 -- f~(S~)x=O.
po x 0 = X 0 ~ qo x
.
quantification
by primitive
lu~(~n+~Z)
fu%(Sx)
pc, q¢
= ums[Sz,w])
system bounded
a function
fu%
N o w let
= =
o
In the q u a n t i f i e r - f r e e
Then
=
,
u~(bn+IZ(t~(Sz)z)...
r[u~,v~,,]~
Tom =(~n+1 ~)
(2)
can be o b t a i n e d
= r[u¢,~n+IZ,Z]
To ~ X u % v ~
Therefore,
= ums[Sz,w]
(t~(Sz)z)s[,,.]) (t~(Sz)z)({n+lZ)) (t~(Sz)z)s[z,Sw])
,
~e T
be defined by
p(¢) X(~)T = pT(X(a)TO¢) q(¢)~
X0
= Xx¢.%x
0
Obviously p~qcx So
q¢
o
provides
= x
o
an e m b e d d i n g of the natural
numbers in type
Now put
B(v(°)~'~) ~ef f(v(°)%)~(P~ v(°)~1)) = 0 and let
T 1 ~ Xv(°)%.
P(To(v(°)%)~)(%(Sp~(~(°)~l))),
then
B(Ttv(°)%,~
) -- B(v(°)~,S~)
e .
59
Since obviously Therefore,
~(qoo)
ua(~n.10)
= uCs[O,w],
by the induction lemma 1.7.10
for v yields
extend the induction lemma for v.
B(v(°)~,O) .
B(v(°)~,z) .
Substitution
~u~(~.l~) ~u°sE~,~l.
Thus we obtain simultaneous
variables
we also have
recursion in qf -HA~ J
qf-HA
W
, and now we can
to an arbitrary
sequence of
of
~0
§ 8.
N -HA w
More about
1.8.1.
Contents of the section.
neous information of
N - H A m,
This section contains further miscella-
which may be consulted by the reader when the
n;ed arises. First the extension of the type structure by Cartesian product formation, together with the addition of pairing operators as primitives is discussed in 1.8.2 it is shown that this extension constitutes an expansion of any theory in the language of
N_~m.
Subsection 1.8.4 is devoted to the discussion of the
X-operator
as a
primitive. Subsections 1.8.2.
1.8.5 - 1.8.9 discuss reductions of the type structures.
Theorem
(Cartesian product types and pairing operators).
Let the type structure
T
be extended to
T'
by adding a clause
~,T E T' = O'XT E T'
T 3)
T I , T 2
and replacing in
~
by
~'
(1.6.~).
Furthermore, we assume the existence of constants D'
E (~)~
D"
E (~x ~)T
D'(D X y ) = x , Let
N - HA m ~ p
q f - N - H A~ m )
D"(D x y ) m y ,
N-HA m , and ~
is an expansion of
,
satisfying D(D'x)(D"x) = x
denote the extension of
is an expansion of
Do,,7 E (a)(7)~ ~
.
N. - HA m . thus . obtained. .
q f - ~N - HA'~ ~ p
Then
N - HA pm
(defined analogously to
N - HA m. ~ ~ p @
Proof.
To each type
a E T'
of types in
we assign a sequence
T,
as
follows :
(i)
O* m ( 0 ) .
Let
~*
(ii)
~ (~1 . . . . . a m ) ' T* ~ (T 1 . . . . . • (~×7)*~(~I,...,%, 71 .... , 7 ) ,
).
(iii) [(~)73" m ((~l)...(~m)T1 ..... ( a l ) . . . ( ~ m ) ~ ) . m I ..., H a.,~.) ~a*,7* m (n~*,~*'
We define a sequence
Further we define a sequence
~p.,~.,T. For
~.
=~,
m X~.
~p.,~. T . ~z(y~)
such that
such that
.
we take the sequence as defined in 1.7.5.
where
~ ~
(t 1 ....
,tm),
m (Sl,...,Sm) , is interpreted as
t i m s I & ... & t m = sm . Now we define a mapping
F
on terms and formulae of
~ pw, N-HA
as follows.
(i)
To each
x a , ~ E ~'
(el,...,~n) and
Fx 'a
~ ~ (x ~I I ..... x an n ) , where
we assign a sequence
~ a*.
If
x a, x 'a
are distinct variables,
(iii) If
Fy T m y ,
Fx a m ~ ,
sequences
Fx a
have no element in common.
Fna, T m ~a*, T* ' FZ p,a,~ E =Z0 * ,a*,~* , rR to=o, r(s)=s.
(ii)
then
of o p e r a t o r s
~ ~a* '
we take for
DDa, ~
~a*,T*
kxy. y , and for
and
the c o n c a t e n a t i o n
of the
rD,
rD"
we take
r%,~
ro,.a,~ = x ~ - - ' [ "
~a.,T.,
(iv) (v)
rtt, m (rt)(rt,). r(t= s) m (rt= rs).
(vi)
r
preserves
propositional
r(A o B) m r(A)o r(B)
operators
for
and Yk , i.e.
r(~) m Yk,
o = ~, V, &.
(vii) r(vxaA) ~ Vrx~(r(A)) , r(~xaA) ~ ~rxa(r(A)) . First note that
r
is the i d e n t i t y on formulae of
n a m i n g of variables). of d e d u c t i o n s
It remains
AW~A N - H.~p
that
=
~-HA w
(modulo re-
to be shown, by i n d u c t i o n on the length ~N - H A w ~ F ( A )
.
This turns out to be com-
pletely trivial. 1.8.3.
Remark.
The theorem also extends
obtained by adding d e f i n i t i o n without
C a r t e s i a n product
additional 1.8.4.
definition
The
schemata for functionals,
types contains
schemata
~-operator
to certain extensions
~
for
variant of the
N- IDB~,
B ~
in § ~.9)-
as a primitive notion.
Instead of h a v i n g a theory
E-HA ~
with p r i m i t i v e s kx ~
,
Z
version
kE-HA w,
ators.
kE-H~A w
is similar to the d e s c r i p t i o n
of
with
H
may c o n s i d e r an a l t e r n a t i v e The d e s c r i p t i o n
~ - ~
if only the theory
a "simultaneous"
(examples
of
we
as p r i m i t i v e
oper-
of
E - HA ~.~w , w i t h the f o l l o w i n g differences~ (a)
Ha, T ,
(b)
The t e r m - d e f i n i t i o n
kx~
Z0,a, T are added.
T m 5) (c)
the operators
are omitted from the list of c o n s t a n t s ;
If
(1.6.4)
tETm T ,
The d e f i n i n g axioms for
is extended with a c l a u s e :
then
kx~.t E Tm(a)T .
H0,a,
Ep,a, ~
are replaced by the rule of
- conversion : ~-CON
(kxa.t[xa])t '~ = tit']
If we make changes
(a),
(b),
(c) i n
(t'
E-HA w t
we
free for
x
in
o b t a i n a theory
t). hE-~
~o
(cf.2,~8). Now
E-HA W
and
hE-HA w
are e q u i v a l e n t
in the f o l l o w i n g
sense : as
w
~2
has been shown in 1.6.8, we can define a the rule of operators
I- operator in
k- conversion holds ; conversely, ~
_, E
_ _
satisfying
lng p r l m l t l
es in
E-HA
zp,~,~ h e f
~(o)(~T~y(~)%p
Hence the union of
,
~-H~ m
kE-HA w
such that
we can define
the defining equations for the correspond-
by p u t t i n g
H~,~ =def kxPy~'x~
. x~(y~) .
E_~m
and
~E-HA~
is a definitional
both ! and similarly for the quantifier-free ~qf-~-HA~
in
theories
extension of
qf-~-~
and
(the latter defined in the obvious way).
The description
of a
i- variant of
(qf -) N - H A w
or
(qf -) ~ - ~
is
not such a simple matter however.
The problem is this : if we simply in-
clude the rule
in our system (say
s = t = kx.s= Âx.t
between closed terms of
s=
( s, t
H
A,B
~),
In fact, if
S, T
are recursively enumerable,
inseparable.
recursively
inseparable
1967 , p. 94) such that
c ~ {xl ~ ¢ A }
Then
C
is recursively
(by completeness So
then equality
= ~.
~ ~An~
Let
then
be a pair of recursively
sets (e.g. as in Rogers
(~)
~),
decidable.
{j(~s~,~t ~ ) l ~ s = t }
closed terms of
For let
cannot be recursively
A,C
of
enumerable,
~
for
Zo I-
is a pair of recursively
Now the statement recursive
P.
Let
istic function of x~ A
*
x~A t
P.
reducible
to
S,T
is equivalent
*
(qf-) ~ - H A ~
restricted
to
recursively VyP(x,y) [
x~ B ~ ~ ~x E B
(by (I))) . inseparable
sets.
for some primitive
representing
the character-
Zy([ ~ t x y ~ 0)
s= t = kx.s= ~x.t ),
respectively, Hence
has therefore "ordinary"
means.
(since
ky.O ; and so the pair
via the mapping
the pair
The problem of the description
distinguishing
BcC
Then
Zy~Pxy
(Ho[ers 1967, p. 80).
enumerable,
be the closed term of
~ ~t~ (by the proposed rule
i 0 C = ~,
predicates) ~ ~~ b ~ ¢ A
of a
S,T
to be solved in a different
A discussion
I - l-
inseparable.
(qf-) ~ - H A ~ manner,
or
namely by
and equality established by
of this possibility
after the treatment of computability
is
k x . j ( ~ t ~ ] rky.0~) .
is alsor¢cursively
~- variant of
provable equality,
ArC
in Chapter II.
is better postponed till
63
1.8.5-1.8.8. 1.8.5.
Reduction to pure t.ypes.
Pure t y p e s . OE
T I)
The p u r e t y p e s
P
are defined
inductively
by
P:
We introduce an abbreviation using natural numbers to indicate pure types : (n)O -=def n+1. We now wish to construct a mapping for
a E ~P' and such that to each
F~ E ( ~ ) a , F
and
F,
P'P f = f,
~
of
T
onto
P,
such that
~ E ~T there exist mappings
definable in
N - HA w,
such that in
~ =
F E (g)~ qf-WE-HA
w
P P'f' = f' .
This is done in a number of steps. 1.8.6.
Injectiq~ in higher types.
We define mappings j
of type I
(I)
mpj , with left-inverses
into objects of type
j+l,
pm.0
~0 0 0 _ . I I~ mPo ~ ~x.y .x , Pmo = ~x .x u, and for XxJyJ.xJ(pmj_1(yJ)) , mpj ~xJ+lyj'1"xj+1(mpj -I(yj-I)) . pmj
One readily verifies that
which map the objects
as follows:
mpj E (j)j+1,
j>0
pmj E (j+1)j.
By induction on
we find that pmj(mpj(xJ))
= xj .
For we have
Pmo(mPoxO ) = Pmo( ~y o .xO~j = ( ~y o .x o )0 = x o , and for
pmj(mpj(xJ))
= pmj(~yJ.xJ(pmj_l(yJ) ) = = ~yJ-1[~vJ.xJ(pmj_1(yJ))](mpj_1(yj-1)) = ~yj-l.xJ(pmj_Impj_1(yj-1))
Now we construct type-increasing mappings m pmj E (m)j ( m ~ j ) by
j>o
=
= ~vJ'1.xJ(y j-l) = x j . m
mpj E (j)m,
with left-inverses
I mp~ ~ kxJ.x j , pm~ ~ XxJ.x j , mpjm+l ~ kx J . mPmmP~(xj) ,
(2)
pmm+1 _ . m+1 m~ m+1\ J = ~x . pmj~x ). 1.8.7.
Coding of
n - tuples for all pure types.
Let
J' J1' J2
denote the standard pairing function with inverses for
the natural numbers.
We extend these to all pure types by putting
j ( x m + l y m+l) ~ XzTM . j(xm+Izm, ym+Izm )
J
~4
•
,
m+1
•
,
m+1
31~x J2~X
.
) ~ ~z m. j1 x )
kz TM
This may be extended .2
_
32x
to
.
.2
z
m+1
z
m m
.
p - tuples, _
.p+1~ n
m+1
.
.2
putting
_
xn
. n n p+~) ~ ~(x~, ~.p (x~n ..... ~p+~))
~x~, ....
.p+1 n ~ n 31 x ~I x ,
.p+1 n ~ .p . n ~k+IX 3k 32x
Now we are able to describe
the coding of
for p - tuples
where As inverses
.
.
.
of different
pure types:
m xn(P)~ ,mPn(p> p
g(x~(~),.. ,xn(P>)~ ~ ~P<~p~(~)x~ (~> .
1~k%p
.
"
m = m~x~n(1) ..... n ( p ) } .
we have
.p,m~ m~ m j~(x m) 3k,l kx ) ~ pm 1 so that k,n(k) 1.8.8. (i)
....
Description
If
~ = O,
(ii) If
of
~, ~ ,
C~ ~ a,
a = (al)...
7' .
F f = f,
(~p)O,
m = maxlnl,...,npl,
then
m x~FV .p,m Fax~ = XY " ~ ~IJ1,nl F'xm+1
1.8.9.
Reducti.on to numerical
O ~ T =o ,
T O 2)
~1,...,an,~ T
~n
1~i~p,
we put
D~ = m+1 , and
ym)
Ft ~p,m ( ~2 e2~n2 ym) ... (F~p J1,np~p'my m ) ,
6 ~TO
~1'''''~n
qf-W.~E-H~ ~.
extension
~ (at× ... X=n)T
(the numerical ~o 2)
t~pes in
the following
To I)
and let
for
= ~Ylal ""Yp~p " xm+1 JP(~IYl .... ' ~pYp)"
Let us consider
restricting
7'f = f.
D~ i = n i
types)
be the
T ~o
6
of the type
~T0
substructure
E ~n
=
(alX'''~an)O
of 1.8.2,
D~,~,
D'D(x,y) is an expansion case which
of
T
obtained
~o
6 =nT .
qf-N-HA
~
when extended
~
Da,~,
T :
to
Note that in virtue constants
structure
D"o,~
= x,
added
D"D(x,y)
of the original
especially
interests
T
and with
~O
such that = y,
system us,
to
D(D'x,D"x) qf-N-~
qf-WE-~
= x
; and similarly ~.
for the
~5
The type structure
T ~o
may be reduced to
T ~n
by mappings
F , F~,
as
follows : (a)
~ = 0 ~ then
(b)
~ : X :t
r
• "
~ :
F x ~ = x~ ,
r:
: x[y~, . , x _ ] ~ ( r
F~ xCW : (~)
Oq = ~ ,
(p¢...×%)0~
n
:
F'x q = x
(np¢...~%,)o.
, y. Pl 1'''''Fpn yn)
xn~(r~Y~'''''r~yn)
kYl ' ' " Yn"
"
( ~ ¢ . . . . ~ % , ) , , n, : ( ~ ¢ . . . ~ m ) O .
C~ = (OOlX . . . OOnx 141x . . . X ~ m ) O ,
Then and
gm
rq X q = X[YI' . "''Yn' . . .z1'
'Zm](F~ xa(F'01YI,..., r ~ Y n ) ) (z I ,...,z m ) ~I ~m F,xO~ = kYl "'" Yn • F~(kz I ...Zm " xCm(ZplY1'''''r'0nYn' z1'''''Zm)) "
Here
k[Y1' .... yn] t[Yl, .... yn]
yl,...,yn;
i.e. if
k[y I, . ..yn] . t(Yl, . .
t
expresses simultaneous abstraction w.r.t.
is of type
.,yn) . . E (alX
v,
Yi ~ ~i
%an)V ; but
(1
abbreviates
~ylXY2... kYn.t , hence is of type (al)(~2) ... (~n)T. x(Yl,...,yn) dicates application to the arguments y1,...,y n (simultaneously).
in-
We leave it to the reader to verify that the following schemata for defining functionals of
T
imply the definition schemata of
qf-WE-HA
~n
w
~
(via the mappings described above) and vice versa. 0
is a constant of type
0
(with the usual axioms).
(ii) S
(i)
is a constant of type
I
(with the usual axioms for successor).
(~di) If
t[Yl,...,yn]
yiE¢i
(1
is a term of type , then
(c[1~... × ~ ) 0 , and for
0,
containing
X[y I ..... Yn]t[Yl,...,yn]
YI'''''Yn
free,
is a term of type
ti~ qi '
(k[yl,...,Yn]t[Y1,...,yn])(tl,.O. ,tn) = t[t I ..... tn] . (iv) There is a term ~ E ((a1~ ...Xap)0 ~ ( ( a 1 ~ . . . × ~ p ) 0 X 0 x a 1 × . . . × a p ) X 0 ~ ~I ~ . . . x ~ p ) 0 , a I
such that
ap
~ , ( x , y , O , Y 1 . . . . . Yp ) = x ( y I . . . . . Yp) cr 1 ~p ~(x'y'Sz'Yl . . . . 'Yp )= Y ( ~ [ Y l . . . . . Y p ] ' ~ ( x ' Y ' ~ ' Y l
.....
Y p ) ' Z ' Y l . . . . 'Yp)
(This reduction may then afterwards be combined with the reduction to pure types as described above.) conditions first reduces
The proof of the equivalence of the closure
(iv) to comparison with the recursion rule, which,
however, is equivalent to asserting the existence of constants
1.7.5).
R
(see
"
66
§ 9°
Extensions
1.9.1.
of arithmetic.
Introduction.
divided,
according
I° ) Extensions by adding to additional
The various types of extensions
to their language,
of arithmetic w.r.t, ~(~)
into three categories :
constants.
or
H~
for species or relations introduced by (iterated) (g.iod'S).
in 1.9.2 below. investigation, first-order
~
generalized
with
induction for
with predicate
Such extensions are briefly described
constants
inductive and discussed
With respect to the various methods for metamathematical they behave in most respects like
HA
itself,
i.e. as typical
systems.
2 °) Extensions
of arithmetic
in a language with variables and quantifiers
for species of natural numbers added. prehension
Examples:
or addition of transfinite
a certain primitive recursive well-ordering,
definitions
may be
the same language or a language obtained
one or more predicate
reflection principles,
of arithmetic
can be studied.
pretations,
as well as normalization
can be adapted to such systems, the systems under
I°).
In this context full impredicat~ecom-
Pure realizability
Variants
and pure functional
theorems for natural
deduction
but not in such a straightforward such a s ~ r e a l i z a b i l i t y
intersystems
way as for
do not readily
=
extend to these systems.
For a more detailed description,
see 1.9.3- 1.9.9
below. 3 ° ) Extensions
of arithmetic
in a language obtained by addition of function
symbols and function quantifiers "non-committal"
to
very elementary ones,
~(H~A) . Such extensions may (apart from such as
E~L
described
be grouped according to their intended interpretation (A) The function variables (i.e. completely determined
in 1.9.10 below)
into two classes:
are thought of as ranging over "lawlike" objects,
sequences
given by a "law" or prescription).
As
long as our concept of "lawlike" has not been analyzed to a degree which prevents identification
with "recursive",
spired by the idea of lawlike that lawlike
we may expect systems to be in-
sequences to be consistent with the assumption
sequences are recursive
(Church's thesis,
obtain systems which are proof-theoretically has also to incorporate
additions as under
see 1.11.7).
and functional
one
1°).
Systems for lawlike sequences behave still very much like to realizability
To
stronger than arithmetic,
interpretations;
HA
with respect
with respect to Kripke
seman~cs and natural deduction they have not yet been investigated. (B) The function variables are thought of as ranging over some kind of choice sequences
(i.eo sequences for which it is not assumed that they are a priori
completely determined by a law). see Treelstra
1968 , 1969 .
For detailed discussions
of this concept
Their essential feature is that they enforce
67
certain continuity conditions on operators defined for all choice sequences. I.e., if
~
is a type 2 operator, defined for all choice sequences of a
certain "universe", v~
where
~
v~(~=
satisfies ~x -
~x= <~0 .... ,~(x-~)>
~ = ~) , o
Continuity conditions do not increase proof-theoretic strength ; but it is also possible to postulate the schema of bar induction for choice sequences (which is simply false for the universe of recursive sequences) and which does increase proof-theoretic strength. Realizability and functional interpretations can be adapted to these systems (replacing partial-recursive-function application
{. I(o)
by continuous-
function application). For a description of the principal systems which fall under this heading, -z4 see 1 . 9 . 1 % 1 O W o 1.9.2.
Extensions of arithmetic eApressed in
~(~)
o__~r ~(~A)
extended
by relation constants° The most obvious extension is obtained by addition of a local reflection principle to
RF(m)
~:
Proof~(~, ~A~) -
( A closed)
A
or a uniform reflection principle
RFN(~)
ProofHA(X,rAy u) -- Ay
( VyAy closed)°
For a general discussion of such principles,
see Kreisel an__~dLevy 1968°
Another me~hod of extension is the addition of the schema of transfinite induction for certain arithmetically definable (in fact, primitive recursive) well-orderings of the natural numbers;
i.e. if
~
is such an ordering,
we add TI(~)
Vx[(Vy<x)iy--Ax]-
VyAy°
A third, and very interesting possibility is the addition of constants for species introduced by generalized inductive definitions (g.i.do)o Assume language
PA
to be a new (unary) predicate constant not occurring in the
~.
such that
A
Let
~
be a system with
~(~)=~,
and let
A(P,x)6~P]
is "monotone" :
~[e,P,] ~ A(P,x) ~ Vx(Px-P,~) - A(P,x) (where Then
[[P,P'] PA
schema :
is as
~,
but relative
~ P , P ' ] )°
is said to be introduced by a g°iod., if we add an axiom and a
,
6S
A(PA,X ) ~ PAx and for all
Q
in
~(PA)
The best known example is Kleene
(see Kleene
0 ~ the set of recursive
1944 , 1955, or Rogers
the definition in the form described
ordinals introduced by
1967, § 11.7, § 11.8).
(To bring
above, we have to rewrite the definition).
A simplified version is obtained by taking e.g.
A0(Q,x ) ~ (x=l) v(a(x)o&x=2 (~)°) v [x=~.5 (x)~ &Vy(~{(x)2}(Y)a ~Q({(x)2}(Y)))]. Still simpler is
here
kxy.[x](y)
functions,
is an enumerating function for all primitive recursive
ky[n](y)
representing
the
n th primitive
recursive
function in
the enumeration. We may then define, when
PI
permitting
over
quantification
has been introduced,
Ap2(Q,x ) ~ P1 x V Vy6 P l ( Q [ x ] ( y ) ) etc.
(cf. chapter VI).
definitions 1.9.3.
a new predicate
P2 '
PI :
This procedure
,
gives rise to generalized
inductive
of higher type.
Language
of
HAS ~o To the language of ~
(n_> O) , to be denoted by
we add variables for X n, yn, Z n
shall often omit the s u p e r s c r i p t ) ,
n-ary
(when irrelevant
and s e o o n d - o r d e r
relations
(species)
to the discussion we
quantifiers
V2' ~2
omit the subscript when the context makes it clear that second-order fiers are i n t e n d e d ) ,
The o n l y s e c o n d - o r d e r
(we
quanti-
terms o o n s i d e r e d a r e s p e o i e s
variables° 1.9o4.
Comprehension
A comprehension
(1) where
principles°
principle
zx n ~ l . o . X n [ A ( x l A
does not contain
is a schema of the form
. . . . . Xn) < ~ x n x l . . . X n ] , Xn
free.
We call the schema (i)
arithmetical
comprehension,
if
A
is a formula of
~
if
A
is a formula of
HAS ~o
(abbreviation :
ACA ) (ii)
predicative
comprehension,
bound species variables
(abbreviation : Pc~
)
not containing
69
(iii)
(full, or impredicative) not containing
Xn
comprehension,
if
A
is any formula of
~So,
free (abbreviation : CA )o
The system in the language of
HAS
based on the axioms,
rules and axiom
~ O
schemata of
I~
(but with respect to the extended language),
quantifier rules and axioms for second-order
quantifiers,
together with
is called
HAS
.
~ O
1.9.5.
Extensionality°
We denote by EKT
EXT
the axiom schema
Vxy[Ax & x=y-~Ay]
~Ve define
HAS
as
HAS ~
Note that in
+ CA + EXT. O
HAS,
EXT
may be replaced by the single axiom
vx I Vxy [ X l x & x = y - X ~ y ] 1.9.6. HAS
Theorem.
+ CA
If
then
First proof°
~H
~
o
is one of the systems
H+EXT
Let
°
is conservative
over
~o' H
HAS~o+ACA ,HAS o + P C A ,
Wor.t.
be a mapping of formulae of
formulae of
HAS
HA
into formulae of
~ O
HAS ~ O
A
, given by : of the form
~(A)
is obtained from
Xtl...t n
by
A
by replacing each sub-formula
~1...Xn(t1=x1&...
&tn=X n&Xxl...xn)
o
Then one readily verifies by induction on the length of deductions systems
H
of
for the
mentioned :
Second proof.
Let
¢
be a mapping of formulae of
HA~S° , which is defined as the relativization
HAS
into formulae of
to extensional
species,
i.e.
~[~nA] ~ ~n(Ext(Xn)-- ~[A]), , [ ~ A ] ~ ¢{n(~xt(Xn) &*[A]) and
¢[Ao B] ~ ¢[A] o 9[B]
,[(Qx)A]
~ (Qx)¢[A] Ext(xn)
for
for
o ~-,
Q ~ V I, ~I '
V, & ,
and where
~xt(X n)
~def Vx1°''XnYl . "Yn(Xnx1°°'Xn&X1=Yl . . . .
Then also, if all free second-order variables of
A
is defined by
&
Xn=Yn'Xny1"'°Yn ) "
are among
XI,.o.,X n ,
one proves by induction on the length of deductions ~+EXT
~ A(X I .... ,Xn) ~ ~ + E x t ( X l ) + o°. +Ext(Xn) ~ ¢[A(XI,.,.,Xn) ] .
The verification 1.9.7.
Lemma.
is quite straightforward If
H
and left to the reader.
is one of the systems
HAS ~ O
HAS
+EXT+PCA,
HAS
~ O
~
ed by restriction servative over
+EXT+CA,
and
H'
+EXT,
HAS
+EXT+ACA,
~ O
is the corresponding
system obtain-
O
of the predicate variables
H' .
to unary ones,
then
H
is con-
7o Proof.
n ~2' "°" ~o' VI'
Let
actual variables
be the list of species variables
in this case, not the syntactical
ables for variables)
with
We define a mapping
T
• (t=s)
n
arguments,
for all
(i.e. the
(= metamathematical)
vari-
n °
as follows.
~ t=so
""
o(n,i)(~ntj'''tn
) "
(~n was
T(Ao B) ~ (TA) o (TB)
for
o = ~, &, V o
• ((Qx)A)
for
Q = ~I' V~,
~ (Qx)~(A)
(QVj(n,k))T(A) This mapping transforms
for
each proof in
~
defined in
1o3o9 C.)
Q = ~2' V2" into a proof in
~' , with a con-
clusion which only differs in the naming of second-order variables. If we wish, we might also have kept the variables for one-argument in the proof unchanged by the translation, of
T
Let
(the modification m
species
by a slightly modified definition
depends on the proof under consideration).
be the maximum index
i
such that
V!
occurs in the given proof.
1
we then
v t,
put
T'((Q~k)A) The verification
VL (k,n)( n t1"''t)
~ (QVI+ =Jik,n) ~ ' ,,)
(A)
for
Q = V2' Z2 , n / J .
that the mapping has the property stated is quite straight-
forward ! we consider the only case which is not quite trivial, of the comprehension
schema for
n - argument
~v~ v~l...~n[A(x1 .... ,x n) ~ This translates
for
into
(under
i.e. instances
(n/ I) species :
~kXl...%].
T )
~E'~j(n,k) 1 Vx I . "°Xn[A(xl .... ,xn) @-~V j(n,k)(VnX1"''Xn I )]"
This follows from ~V 1
.n
I
.n
j(n,k)VZ[A(Jlz,.--,JnZ)
together with 1.9.8.
over
EXT.
Theorem.
Proof.
HAS ~ O
+ EXT + ACA
By the previous lemma, HA,
~--~Vj(n,k)Z]
where
H
is conservative
over
it suffices to prove
is the restriction of
HAS
H
HA. to be conservative
+ EXT + A C A
to unary species
variables. We further remark that we may restrict attention to instances taining
(at most) one free numerical
vxy
~x~w[A(~,y,~) ~->x~]
is a consequence
of
EXT
and
parameter,
since e.g.
of
ACA
con-
71
Let now any proof assume
~
w
in
H
of an arithmetical statement be given ; we may
to use finitely many instances of the comprehension schema, say Vy ~X I Vz[Ai(Y,Z ) ~
We define a predicate
X~z] ,
0
( Vyz Ai(Y,Z )
closed).
C(x,y,z) :
C(x,y,z) ~ (x=O&Ao(Y,Z)) V ( x = I & A I ( Y , Z ) ) Vo.o V . . . V(x=k&Ak(Y,Z)) Let
Vo, VI, v2, ...
be the numerical variables of
let
Vo, V1, V2, ...
be the (unary) species variables of
Let
m
be the maximum index
Now we define a mapping
i
such that
V. I
~,
and ~.
occurs free or bound in
w
a :
~(Ao~) ~ ( A ) o ~ ( B ) for o a((Qvn)A) ~ (Q~n)O(A) for Q
~ v, & , ~ , V 1 , ~I;
~(Vnt ) ~ C(JlVm+n+l, J2Vm+n+l ~ t) ~((Q2Vn)A)~ (QIVm+n+I)~(A) , Note that
~
where
Q ~ ~, V.
is the identity on arithmetical formulae ; a
preserves logical
inferences, axioms for equality and successor and induction (at least as far as they occur in
w )o
Now consider an instance of
ACA
occurring in
w ; it translates under
into Vy~Vn+m+ i Vz[Ai(Y,Z ) e-~ C(JlVn+m+1, J2Vm+n+1 , z)] . This is obviously derivable in that a
~(EXT)
transforms
1.9. 9.
is derivable in w
~, H~.
into a proof in
Formulation of
HASSS
with
since
Ai(Y,Z ) *-~C(i,y,z) ; also note
So, after intercalation of some steps, HA. ~- terms.
Instead of formulating second-order logic with a comprehension schema, it is sometimes more convenient to use a more general class of second-order terms. So
CA
is replaced by a rule of term formation : whenever
a formula of
HAS~o,
then
kx 1..oxnA(xl,...,xn)
A(Xl,..°,x n)
is
is a second-order term, with
the rule {Xx1...Xn.A(x I ..... x n) }(t I .... ,tn) ¢-~ A(t I .... ,tn) • PCA
is represented by a similar rule of term formation where
mitted to contain bound second-order quantifiers, etc.
A
is not per-
72
1.9.10-1.9o11.
Intuitionistic
1.9.10. D e s c r i p t i o n The system EL
EL
as d e s c r i b e d
of
analysis with v a r i a b l e s for sequences°
EL.
to be d e s c r i b e d b e l o w is a slight v a r i a n t in K r e i s e l - T r o e l s t r a
1970 , § 2.5.
For sequence v a r i a b l e s we use either case of
N - H ~ w)
~(~)
by the a d d i t i o n
and an a p p l i c a t i o n
operator
kx,
the term d e f i n i t i o n
and extending
(i)
function variables
(ii)
one-argument
(iii) if
~
as
I,
Z
I,
11 I ~
function
W
HA
I
(as in the
~, 8, Y, ....
~(E~L)
and quantifiers,
R , and a b s t r a c t i o n
operators
by
(i.e. terms for functions) ;
constants t
I,
of sequence v a r i a b l e s
of
are functers
V
are functors ;
a (numerical)
term,
then
Ap ~t
(abbreviated
~ot ) is a term ;
(iv)
if
t, t'
if
t[x]
are terms,
quantifiers,
%0 a functor,
is a term,
is n o w f o r m a l i z e d
a rule
kx.t[x]
Rt~0t'
is a t e r m ;
is a funotor.
by a d d i n g q u a n t i f i e r rules and axioms for f u n c t i o n
of
t-conversion
and d e f i n i n g axioms for REC
y
"Ap" , a r e c u r s o r
is a functor,
(v) EL
x I,
or we use g r e e k lower case letters
is obtained f r o m
of the system
k-CON
(kx.t)t'
= [x/t']t
R
f Rtq00 = t
\ Rt~0(St')
= ~j(Rt~0t', t')
and a q u a n t i f i e r - f r e e QF - AC
a x i o m of choice
Vx Zy A(x,y) -~ Z¢~ Vx A(x, ~x)
(A
quantifier-free) o
OO
EL
is e s s e n t i a l l y
definable
in
a subsystem of
N-~W
o
( kx
N-~
requires,
ice.
only as a syntactical
only deals with equality at lowest type, QF-AC
w,
intuitively
the primitives operator,
of
E~L
but since
are EL
this makes no difference°)
speaking,
%hat the u n i v e r s e
of f u n c t i o n s
CO
is closed u n d e r tension of recursive
"recursive
HA,
in"°
by i n t e r p r e t i n g
EL
is easily seen to be
all f u n c t i o n v a r i a b l e s
a
conservative
ex-
as r a n g i n g over total
functions.
Sometimes we can get by with a system of e l e m e n t a r y restricted
language,
such as
EL
in I ( r e i s e l - T r o e l s t r a
analysis with a 1970 ; EL
more
is a
~O
definitional
extension of such a system.
such systems by The system functions
H
in Howard and Kreisel
to be closed u n d e r
w e a k for the f o r m a l i z a t i o n which
we
need.
In the sequel we shall denote all
E~L o
"primitive
1966 only requires recursive
of the e l e m e n t a r y
in"o
the u n i v e r s e
of
This is somewhat too
theory of reeursive
functionals,
73
1.9.11. Some notations and conventions, ~0 = < > ,
= <~o, hence
=I . . . . , ~ ( x - 1 ) > ,
Ith(~x) = x .
~6 n ~def Vx< Ith(n) we put
(~=
(n)x) o
Furthermore
Jl ~ ~def Lx ° Jinx , J2 ~ ~def kx . J2~x, j(a,~) ~def Ix. j(~x, ~x) . (If we have not included k as a primitive,, jl ~, j2 ~, j(~, ~) can nevertheless be used in contexts like
A(JI~),
A(j2~ )
is taken as an abbreviation for the formula A(~) 8
every occurrence of
has been eliminated.)
Bt
by
jl(~t)
A
etc., where
A(JI~ )
etc.
obtained by replacing in
and repeating this process until
(~)x ~def kyo~j(x,y) .
1.9.12- 1.9.16. Formalization of elementary recursion theory in
E~Lo
1.9.12. We have to rely heavily on the development in Kleene 1969 . developments in Part I of Kleene 1969 can be carried out in QF-AC
includes all instances of Kleene's oo Kleene 1969, cf. footnote 7 in Kleene 1969).
X2oI~
E~L
The
(since
needed in Part I of
That we assume our coding of
sequences of natural numbers to be onto the natural numbers (contrary to Kleene's definition) is inessential.
(~I ~ ) ( x ) ~ y ~(S)~y
~de~ ~ ( ~
We define
rain [ ~ ( ~ . ~ z ) / O ~ ) ± l
~def ~(~ m i n z [ ~ ( ~ z ) / O ] ) °
~IB,
~(B)
by
~ y
I = y°
We may use the partially defined expressions constructed from terms and the partially defined application operations viations, similar to the use of
.!o , °(°)
p - terms (Cfo 1.5. IO ) constructed by
means of partial reeursive f~uction application° terms in this case also.
(~lS)(x)
~, ~ v
We shall speak of
p - functors.
and ~(~)
By virtue of (I), every
are partial recursive functionals of
p - term of type
0
and
{~I}(~, ~')
Io9.13. Coding of sequences and
We put
p-
respectively.
n - tupleso
~u(~1, .... %) = ~ . ~ u ( % ~
no, ~I
~, 8, x
and
such that
corresponds in a standard way
p - term in the sense of Kleene 1969, replacing
kx. {~o}(x , ~, ~')
We denote
....
~, ~ respectively, hence we can find certain numerals
to a
p-
If they are of type I (i.e. when they represent a
partial function) we may distinguish them as functors by
as systematic abbre-
..... ~x)
~I~' ,
~(~')
by
74
~i e =
~"
Furthermore we let
~zo
Ji ~x°
k~
= o,
(0 < i
k~(m.~)
be functions satisfying
o ~ i m * <Jin x> .
We abbreviate ~I(~I .... '~u ) ~def ~ 1 % ( ~ I ..... ~u )
(~I ..... ~U ) ~def ~(~u(~1 ..... ~u )) ° 1.9o14. Theorem.
(i) Let
(primitive) recursive
f
~[%,..°,~n]
..... %]
(ii) Set ~[~I ..... %] be a p-term tive) recursive f~ such that
Proof.
"'' ~")~
By K l e e n e
.....
then there is a (primi-
O~
1969 to prove
the existence
~ ~[~1 .....
%)
(i).
of a numeral
%](x)
By Kleene 1969, such that
.
1969, "34.1, *34.2 (page 69)
{~}(~,~I,.... %) ~e
of type
~[~I ..... %]"
41 we can prove
{~t(x,%
(T, U
"
~e use lemma 41 and § 4 of Kleene
Pc 67, lemma
p - functor ; then there is a
such that
m
f~l (~I ..... %) ~[~I
f$(~'"
be a
primitive
" ~ mi~yT(~
, ~, ~ly .... ,~y)
reoursive)o
put f 0=0 m f
(e.m)
= 0
It is easily verified that
if-,T(B
f
m
, x,
k lnm , . .
. ,knnm) o
satisfies our requirements.
(it) is proved similarly. 1.9o15o Theorem
(s- m - n
theorem analogue).
(i) There exists a primitive recursive function
A
of two arguments such
n
that (writing
~^n ~
for
(~A n ~1)I(~ 2 .....
^n(~,~) )
~n ) ~ ~1(~1 . . . . .
~n) .
(it) Similarly, there is a primitive recursive function
A~ n
such that
(~ ^~ ~I)(~n-~(% . . . . '~n )) ~ ~ ( % ( ~ 1 . . . . ' ~ ) ) " Proof.
(i)
By Kleene 1969, lemma 41, "34.1 there is a numeral
m
such that
75
(~I (81 ..... ~n))(x) ~ ~miny T(~, x, ~,~ly,..o,~j). me put (using 1.9.14 (i) implicitly) (,~^1~1)(o) = o (o~ ^ ~1) (~: * u) = y + I ~ (~A~I)(£*U)
~(lth(u)=y)
A
,",T(m., x , ~ ( l t h u ) ,
~l(lthu),
= 0
cases.
in all
other
n-I k 1 u .....
n-1 kn_lU )
(ii) Similarly. I o 9.16. T h e o r e m (i)
For each
(Recursion ~
there exists a
F o r each
Proof.
~
there
(i) Consider
~1(6,~1 .... Take
~ = cA
n
¢.
(~
~
such that
= ~1(~ . . . . ,~n) •
~l(~,~,'-,~n) (ii)
theorem analogue).
exists
a
~
such t h a t
~ l ( S A n 6' ~I ..... Yn ) "
''n)
~" '~I(6 A,, ~''I .....
There exists an
¢
such that
"n) "
Then
~)1(~t, . . . . 'q) =" st (¢,'I . . . . . %) ~1(¢^~
¢,~I ....
'~n) ~1(~'~I
.....
~n )°
(ii) Similarly. 1.9.17 . D e f i n i t i o n s If
t
is a
x 9 we put If
t
If
t
A°x,
p - term of type
in the p a r a m e t e r s
is a
p - functor,
0,
A°~, A1eo which is p r o v a b l y defined for all values of
of
Similarly
is to be a
AI~.t
t
0 , we take of
t
A1x.t
different
~o
Ao~.t
different
we take
in the parameters
According
A1x,
of type
AOx.t -=def kXot o
is a
reoursive
of
p-term
from
to be any
from
to be any ~,
~,
~,
q0~ primitive
such that
such that
to 1.9.14 and 1.9.15 we can always construct
primitive
such that
such
~.
reoursive
76
1.9.18.
S2stems of i n t u i t i o n i s t i c lawlike
sequence ;
For a universe
of lawlike
seem to be i n t u i t i v e l y the strongest
analysis based on the concept of a
IDBo sequences,
justified,
various forms of axioms of choice
notably
ACoo , but also
- v~[A~- ~[(~)o:~ Vx~((~)~, (~)s~)]] RDC I
ACel , and even
principle
implies
ACol , hence
ACoo ;
see Kreisel
"
and T r o e l s t r a
1970,
t h e o r e m 2.7.2. It follows from the results of G o o d m a n in fact conservative of this book ;
over
HA;
1968, and E,
that
E~L+ RDC I
is
the work of Goodman falls beyond the scope
the proofs are very long and the m e t h o d cannot be readily
fitted into the f r a m e w o r k of the rest of this book. However, pretation, Kreisel
it is not hard to establish, that
E L+RDC I
and T r o e l s t r a
the c o n s i s t e n c y
is consistent
1970 , 3.7).
(of. § 3.2,
To obtain a p r o o f - t h e o r e t i c
strengthening,
i n t r o d u c e d by a g e n e r a l i z e d
example here b e i n g the theories
IDB
is obtained by adding a constant
functions) KI.
to ~
and if
also e s t a b l i s h e s
Church's
thesis state-
involving natural
we have to add a constant for
inductive and K
d e f i n i t i o n ; the principal
ID~I . (for a u n a r y predicate
Q
of
EL , together with two axioms and a schema = kn. Sx ~ K ~
A K ( Q , ~ ) ~def Z y ( ~ = kx. S y ) V ( a O = O & V x Q ( k n . ~ ( ~ * n ) ) )
for all El, K2
1.11.7).
are reduced to statements
inter-
(Cfo 5.6.~6, and
only.
a species
ID~B
~
axiom for systems with f u n c t i o n v a r i a b l e s ;
ments i n v o l v i n g functions numbers
relative
The same i n t e r p r e t a t i o n
of Church's thesis
acts as a r e d u c i b i l i t y
by means of a r e a l i z a b i l i t y
in the language
of
we put
IDB
may be combined into
AX(X,~) -- x ~ IDDBBI
may be defined as
ID~B+ ACol o
(ID~B I
in Kreisel and T r o e l s t r a
here ;
!DB
corresponds
to
1970 is an expansion of
IDB
of K r e i s e l - T r o e l s t r a
ID~BI
as defined
1970. )
v--~- O
The axioms
E l - K3
are in fact equivalent
schema (of. K r e i s e l - T r o e l s t r a
1970 , 3.2.1):
to the f o l l o w i n g a x i o m and
77
(~)
~a
for all
(2)
Q
[Vn(~n/O--~n) ~ V n ( V y ~ ( . . #) ~ n )
-
of the language,
Ka & a n / O
~
~o]
and
~ V~(an= ~ ( n . m ) )
.
(I) is called the principle of induction over unsecured 1.9.19.
Systems of intuitionistic
sequences.
analysis based on a concept of
choice sequence. As already remarked in the introduction
to this section, universes e~fls
of
io na l
choice sequences are supposed to be such that an-~operator of type 2, defined on the whole universe
should be continuous,
i.e. satisfy
~Vithout introducing higher type objects in the language, of expressing
the eimples~ way
this continuity property is by the schema (weak con[i,uity
schema)
wc-~
V ~ X x A ( ~ . x ) -. v~x:: xz v13 ~ ~ : A ( ~ , y )
o
This principle may be conceived as being obtained by combination of the above-mentioned
continuity property for type-2 operators with the following
"selection principle"
(axiom of choice) which is itself not expressible
in
,:(~) : -*
V~A(~,x)
:~
v~A(~, ~ )
A stronger axiom of continuity
C-N
V~XxA(a,x)
-
C-N
.
is expressed as follows
~:~[::o~& v n ( ~ n / o -. V ~ n A(~, ~n "--I))
where Ko(a') ~-def Vnm(~:r~/ 0 ~ ~ a = ~(n*m)) & Vt~ ~Lx:(~'(~x) / 0 ) (C-N C-N
corresponds
to the strong continuity
.
of Howard and Kreisel
1966).
expresses that there is a modulus-of-con[i~luity functional ; W C - N
only expresses local continuity. 1.9o20o Bar induction. The schema of bar induction, 1966 , appears in various forms.
(1)
v~P~
(2)
Vnm(Pn ~ P ( n * m))
(3) (4)
Vn(Fn V ~ P n ) Vn(Pn -- On)
(5)
Vn(VyQ(n.~)
discussed
in Howard and Kreisel
-- Qn) o
Then bar induction with the monotonicity ~S
extensively
~e list some formulae first :
condition,
Bi M,
can be expressed
and bar induction with the decidability condition, BID
as
The weakest version is
(1) & (4) & (5) QO (with I' quantifier-free). B=QF It is shown, in Howard and Kreisel 1966 (Remark 4, page 337) that B I M +
can
be strengthened to
Similarly, if & is supposed to be monotone (i.e. then BID or BIQP may also be strengthened: (1) & ( 3 ) Bc (4) & (5) & km(Qnd&(n*m)) (1) &
(4) & (5)
& Vnm(Qn-.B(n*m))
tfnm(Qn
4
%Qn
+
VnQn
-+
&(n*m))
),
quantifiex free).
(for P
It should be noted that (~owardand Kreisel 1966, theorem 8 ~ ) EL
+
ACol
+ WC - N +
BIM
t
C-N
and also (~owardand Kreisel 1966, theorem 8E)
l.9.21,
Extended bar induction.
The schemaof extended bar induction is described below.
Let
R
be any
unary predicate of functions; then we put
contains all codings of finite sequences of elements of R. denote the coding of a sequence $o,u.,Bx-q by '
R"
Let us
' is a sequence of rp such that ( T ) ~ = Az.x , ( ( P ) ~ =+ By ~ for y < x , (T) =Xz.O for y > x . Y * denotes concatenation; we abbreviate <'@* as < is h , O . Now the schema of extended bar induction EBID is given by
. >'
where
79
(1) (~) (~)
~ V!~ ~ ~" (P~ v ~1~) Vl~ ~ ~ " (P~ - ~ )
(4)
~1~~ ~{* ~ ( ~ $ x )
(5)
v~
~
(v~
R ~(~%)
- ~)
.
1.9.22. Theorem.
E~ c + pc I ~ ~BI~ where
DC I
DC I
is the schema Vc~A(%~)
Proof.
-~ [?[(y)o:~&VzA((~)z,
We first show that
(a form of
DC I
(~)Sz)] °
implies the following more general
RDC I )
To see this, assume
v~
s A(~,~) o
s ~
Let
Then obviously
(using classical
logicS)
v~ ~ A*(~,~) Let
~E S ; by
DC I , there is a
?
such that
[(~)o = ~ ~ vzA*((~)z'(~)s~)] Then we prove by induction on
°
z
v~[(~)~ ~ s ~ A ( ( ~ ) ~ , ( y ) S ~ ) ] . Thus
(6) follows.
Now apply
(6), with
s - ~
~sume
&~q~,
A(~,~) ~ ~
(~)-(~),~(<>~),
Obviously,
if
R~
Hence by c l a s s i c a l
&-~q~,
logic
((~)-(~)
~S~s
as in~.~.2~).
contraposition
Z~ R(-~Q(~.~))
Thus
v~s
~(~ : ~. %)
A(~,~)
of
(5)
yields
and t h e r e f o r e
also
schema
80
By (6) there is a
(~)o
~
such that
< >~ ~ V z ( ( ~ ) ~ s ~ v~A((y)~,(~)Sz)) ,
~
hence, by induction on (7)
z
Vz(RU(7)z & Ith(y)z = z & ZgE R ((Y)Sz= (Y)z* 9) & ~ Q ( V ) z ) "
NOW (7) implies
(8)
(Y)s~ = (~)~ *<((~)Sz)Sz > ~ ((~)Sz)S~
We wish to construct
6
(~)z = ((~)Sz)Sz ' ioeo Now we see from (7) that for all
z
such that
VzmQ(~z)
implies by (3)
1.9.23. Remark.
= (~)
Z
~
R°
This is achieved by taking
Z
6 = Xx((7)sjlx)Si~(j~x
(by (8)), therefore
Vz~Q(Zz)
~
).
; but on the other hand,
8~ R*o
Vz(~P(~z))
This contradicts
(Luckhardt
(4), since
o
Attention has been draw~q to the schema
work of Luckhardt
((?)Sz)Sz E R
1973, and Scarpe!lini
EBI D
1972 A).
by recent They showed
how to construct models for the theory of bar recurslon of higher type which could be shown to be models in a theory corresponding show how
EBI D
tinuous functionals (1 9 10).
EL + EBI D .
are a model for the theory of bar-recursive
By the preceding theorem,
bar-recursive
to
can be applied to show that the so-called extensional
We con-
functionals
this also gives a modelling of the
functionals which can be shown to be a model in
E~Lc + DC I ;
but this is already explicitly in the literature,
e.g. Kreisel 1968 , pp.146-147°
1.9.24. Fan theorem.
in its simplest form may
The so-called
"fan-theorem"
be stated as follows : FAN
V~6 B Z z A ( ~ , x ) -- Zz V~E B Zy V~6 B ( ~ ' z = ~ z ~ A ( ~ , y ) )
Here "~
~6 B
is an abbreviation for
V x ( ~ x ~ I)
( ~6 B
.
may be read as:
belongs to the binary spread"). Kleene's *27.7 in Kleene and Vesley
1965, page 75 is a generalization
FAN ; it is shown there that ~
+ wc-N + BI b b F A
by first showing that EL~..+ BI D ~ FAN where FAN '
( FAN,
Vn(Rn v-.an) & V ~
corresponds
~mR(~)
to Kleene's "26a)~
-~ ~
V~E B ~ _ < z
R(~)
of
81
Here we have restricted our attentions (i.e. satisfying are equivalent
~6 B ) ;
to similar principles
Let us denote by
where
~6 S
For every
implies
if
~
S~S'
~[S'] = S , FAN
belongs
to the
and
FAN'
spreads.
~
fan $ .
~
such that
8 6 S ~ Vx(~x!ax) o
is itself a fan.
for two fans
~=
w.r.t.
FAN
the more general principle
{~I Vx(~xi=)}
Furthermore, such that
FAN*
abbreviates :
S
in the binary spread
for arbitrary finitary
fan S , we can find a function
The species
to functions
but it is not hard to show that
for
S, S'
~6 So
we can find a projection
Therefore
S , as is seen by applying
FAN*
FAN*
w.~.t.
w.r.t.
S'
S' to
v ~ s, ~ A ( ~ , y ) . The following mapping transforms a sequence of
O's
~ where
Ix
and
O, I ~2+I,
I aO+1, O, I ~I+I
stands for
every function of natural numbers into
1's , ioeo an element of the binary spread :
I, I, .o.,
I
(x
times).
It is easy to see this mapping is bi-unique, fan of the binary
spread.
Thus we may derive
1.9.25- 1.9.27~ Extensions 1.9.25. Extensions
A first e x a ~ e
FAN*
from
N-HAWo
inductive
is the theory
definitions ; IDBWo ~2
the natural numbers,
with objects of finite type over three trees of the first class, and trees of
the second class (trees of trees of the first class). ed at length in chapter VI° obtained from
T2
equivalent
is obtained by extending 0
extending
and
K
T2
to
~-HA ~
TI
IDB
as regards proof-theoretic
and the Brouwer-operations)
in the same manner as
A first example of such an extension appears in Howard reworked version in Howard In Troelstra
strength,
~-HA ~
thereby
extends
H~A.
1963 , a completely
1972.
197~ systems
~-ID~5 w,
E - IDB w,
W E - IDB~
We briefly outline these systems by first introducing N - H A~ pw .
~I , the theory
to trees of the second class.
to a theory of finite types over two basic
(the natural numbers
(a variant of)
This theory is discuss-
contains as a sub-theory
by deleting all reference
Another example,
types
FAN .
%o theqries in all finite types with sets introduced
b~,, ~eneralized
basic types:
of
and transforms a fan into a sub-
The type-structure
are described.
N - IDB w
is now extended to a structure
~K:
similar to
82
There are constants D ,T, Da,T,' D"~,T,
0, S, H
,
Furthermore, there is equality a 6 TK° I
Zp,a,T, R
and moreover constants =a
as before, pairing constants 9 I, 92' ~3' ~ '
I(p,~,T 6 TK) .
as a primitive constant for each type
The axioms and rules contain the axioms and rules of
is an "injection"-functional
from
K
into
(0)0,
916 (O)K, ~26 (K)(0)K ; the connection between
I(~1~)y
= s~
is given by:
(x,y6 0, e6 K) 0
e, f, e ~, e", el, .o., f' , f" , .o.
@36 ((0)K)K
I, 41, ~2
N - H~p,
I6 (K)(0)0o
(x,y~o)
I(92ex)y = I e ( < x > . y ) (We use
so
for
K-variables.)
is a "sup"-operator for sequences of elements of
K
and satis-
fies l(~3Y)0 = O,
l ( @ 3 y ) ( ~ * n ) = l(yz)n
(y6 (0)K, z,n6 0) .
&
~
is~constant for definition by recursion over Is0 = Su-~ ~ e x y le0 = 0
and
Z's
= xu,
(o)~, y~ ((o)~)(K)o) o
kv° Y (~2ev)xy
H,s
with axioms
-~ ~ exy = y(lv. Y~(@2ev)xy)e
(u~ o, ~ Here
K,
is assumed to be s~ntactically defined in terms of
(cf.1.6°a).
This completes the description of
N - IDB w .
E - IDB ~
is then obtained by
requiring x K = yK~r-9 Vz°(Ixz = Iyz) and also
hereditary extensionality, ice°
~(~)~ ~ y(~)~ In
WE-IDB
~
If where
P
~-~ w ~ ( ~
= y~).
extensionality is weakened to
b~-t~s,
then
bP~F[t]:F[~],
is a propositional equation between terms of type
0,
and
t,s E ~ ° I-IDB ~ 6 TK
is obtained by adding to
.~N-~D S
a constant
E
for each type
with axioms E xy=0 x=y
V E~Xy= I
~-~E x y = 0
,
thereby making equality decidable for all types. There is still an intermediate type of theory possible, where equality is neither extensional nor intensional (but also not neutral). dicate these extensions of We only add %o
N-HA w
N-~w,
N - ID~B~
respo by
Let us in-
InN.~-HA w,
In~ _ IDBWo
S3
x
I
F o r a model 1.9.26o
~-~ Vz°(xz
Theories
w i t h bar
on (essentially) B~
been first
introduced
For the most
since
the
of h i g h e r
type ; N - H A
+BR.
type are e x t e n s i o n s
structure,
constant
in S p e c t o r
1962.
w i t h a n e w schema
for type
(The most
1968 , G i r a r d
N - ~ PHA °°
of
~ ).
important
1972.
for c e r t a i n
Such s. theory further
Furthermore
has
refer-
Scarpellini
1973. )
of bar r e c u r s i o n
such
in § 2.6.
of h i g h e r
same type
convenient
tion of a type
e.g°
recursion
1968 , Kreisel
Luckhardt
theory
ICF
(the b a r - r e c u r s i o n
are H o w a r d
1972 A,
o
see
of bar r e c u r s i o n
constants
ences
= yz)
of such a theory,
Theories based
I
= y
~
formulation,
as an e x t e n s i o n
of finite
sequences
assume of
sequences
may be i d e n t i f i e d
that we w i s h
N-HA w .
of objects with
We note
of type
special
to describe that
a
the
the addi-
is an expansion,
sequences
of type
(O)a,
as follows. Let the natural
numbers
n O = n, Then
<x
n(~)~
, ooo, x _I > z(O)%
n
be ceded
= kx ~ . nT,
may be coded
= u
,
z(°)°(i+
into h i g h e r
n XT =
as
Dn
z
n T
types
as
n
as fellows:
.
with
I) = x ~
for
i
I
z(°)~i N o w let
c
of type
natural
numbers,
[o]
a,
[el(i) = u i
for
jyEc]<
see,
being
continuous
z )o
If
y[c] < Ith(c),
of type
B
then
ranging
over finite
same n o t a t i o n s
for
for
if
sequences
as for
(u £ ~) ,
(0)~ , w h e r e
[e](i) o o ~
constant
of
sequences
of
Ith(o) o
o = <Us, .oo, Ux_1> ,
i~x.
satisfies
that
(i.e.
B
defines
yz , z 6 (0)~
B yzuc
is r e d u c e d c
- B y~uc o u ( ~ v . ~ y ~ u c ( c . ~ ) ) c .
depending
;
to the c o m p u t a t i o n
such that
of continuity),
eases w i t h
y[e]
is the set of axioms
a functional,
is d e t e r m i n e d
consequence
BR
, the
lib(o) - B y~ue ° ~c
of
If the set of
~u
c I . c2 , d
i<x,
intuitively,
y[c] ~ I t h ( c )
of type
a sequence
[y[c]ilth(c) To
i > u °
and let us adopt
such as
denote
The b a r - r e e u r s i o n
~R
for
be a v a r i a b l e
objects
Let
= 0 °"
y[c]~lth(c)
for all
on a finite
the c o m p u t a t i o n of
Bcyzu(c*V)
is w e l l - f o u n d e d ,
the c o m p u t a t i o n
BR o
we must
c
think
initial
of
y
for all
for v6 ~.
(classically reduced
structure.
as
segment
B yzuc
will be e v e n t u a l l y
of our type
of
to
a
84
1.9.27. Girard's theor 7 qf functionalso This theory is introduced to be able to give a direct Dialectica interpretation of the theory of species (i.e. not via a theory with variables for functions 9 as in S~ector 1962 (Girard 1971 , Girard 1972). The type structure
(i)
$S
is defined by
0~s
(ii)
~, ~, ~', ~ ,
..o
belong to
~S
(4, ~, ~', B ~ . . . .
are called vari-
able types)
(iv)
if
~[~] 6 ~S'
then
V~.o[~],
The functional constants contain
S~.~[~] E ~ S "
S~ E
T, g p , ~ m ' R , Do,m' o,~'D' D"G,T, OO
for all6Tp 6 ~S ' and two injection functionals
Ivan, T
and
I~,T
~ satis-
fying
Finally, there are two operators
DT, ST
(net functionals with a type, but
corresponding to schemata for introducing new funetionals). Let type
%6 ~ ~
be a term, not containing free variables containing in their
free°
Then
DT~t
is a %erm of type
V~°~
with axioms
I V ~ [ @ ] , T ( D T ~ t ~[~]) = t°[ T ] Let
% 6 (o[~])T ,
~
of a variable free in ST ~ t
not
occurring
free
in
m , and not occurring in a type
t ; then
~ (~[~])~
,
with the axiom ST ~ t ( l ~ [ ~ ] , p
s°[d) = t(~[~])~s°[~]
.
Also
O(O)T x
0
~: OT,
Do,T OoOT
= 0o' XT
ST ~t(o~.~[~]) = t(oo[~])
(t6 ( ~ [ d )
p) o
For this theory also intensional and extensional versions are possible. example9 we may add the equality functionals
E
as in
I - }L~~.
For
85
§ 10.
Relations between classical and intuitionistic systems: = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = translation
into the negative fragment.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
1.10.1.
Contents of the section.
For classical
predicate
logic and arith-
metic there exist a number of mappings into the "negative" corresponding
intuitionistic
these translations
systems in the literature ; t h e definition of
can be readily extended to higher order languages.
survey is given in Luckhardt Gentzen
1933 , Kuroda
HA,
~
(i)
Hc ~ ~A ~-~ A
(ii)
He ~
A ~
(iii) For all
let
and let
All translations
197~, chapter III.
1951 ; cf. also Kleene
For definiteness, logic or
fragment of the
~ Hc
1933,
(many-sorted)
predicate
be obtained by addition of the excluded third. properties :
for all
A~ Fm(~)
H b <0A , for all
A ~ Fm(~)
there exists a
negated prime formulae by means of As remarked in Luckhardt
A
are Godel
1952, § 81.
denote intuitionistic
have the following
A E Fm(H)
References
B , constructed V, &, ~, ~
1973~ all these translations
sense that, for any two translations
~, ~'
from doubly
s~
~ ~ ~A ~--~B.
are equivalent,
satisfying
in the
(i) - (iii)
~ ~ ~A *--> ~'A . Below we primarily discuss 1.10.2.
Definition of the mapping'.
higher-order)
language,
of variables), translation")
&, V, ~, A
P' ~ ~ ~ P
(ii)
(A&B)'
(iii)
(A-- B)' ~ A'-- B' (VxA)'
(A vB), ~ ~ ( ~ A , ~
(vi)
(ZxA)'
m VxA' ,
Then we define
P ;
for variables
be any many-sorted
~
V, S
(first-or (for any sort
the mapping ~ (the "negative as fellows :
~ A.
X
of all sorts
x
of all sorts.
B')
~ ~ Vx ~ A' , for variables
Remarks.
In a system
~
with a language
HA, H~Am, [ - ~ )
clause
resulting translation given by (i) - (vi). HAS , we may use as
.
for prime formulae
(iv)
(e.g.
~
~ A'~B'
(v)
1.10.3.
Let
based on the logical primitives
by induction on the formula complexity
(i)
(i)
the variant due to Gentzen.
t= s
in
(ii) If we use
where prime formulae are decidable
(i) may be simplified
to
P' ~ P;
is then obviously logically equivalent
and
P' ~ P
the
to the one
In systems with two types of prime formulae,
P' ~ P
HA~S)
~
such as
for the prime formulae which are decidable p, m ~ ~ p
(such
for the other prime formulae.
for prime formulae,
we have
A" ~ A' ; and we always
8E
have
A" *-~A'
in intuitionistic predicate logic.
We may also let the
treatment of prime formulae depend on the context : if they appear unnegated in
A
then
we put a double negation in front, otherwise we do not change them ; A
is further defined by (ii) - (vi).
1.10.4.
Convention.
that
is defined by 1.10.2,
'
Then also
We shall give our proofs below under the assumption (i) - (vi).
W e sometimes find it convenient, however, prime formulae 1.10.5.
P
A" m A' .
P' ~ P
to assume
for decidable
(cf. our remark ~.I0.3 (ii) above).
Definitions.
(a) We define the strictly positive parts (s.p.p.) of
A , for
A
in a
given language, inductively as follows: (i)
A
(ii)
If
is a s.p.p, of B&C
or
(iii) If
B ~C
is a s.p.p, of
(iv)
VxBx,
If
A ;
BVC
SxBx
are s.p.p, of
A , then so are
A , then so is
is a s.p.p, of
A,
B, C
C
then so is
Bt
for any term
(b) A Harrop formula is a formula which does not c o n t a i n a s.p.p, with or
S
V
as a principal operator.
Alternatively,
the class of Harrop formulae
ly by the clauses (i) prime formulae belong to (ii)
A,BE A =A&B
E A,
(iv)
B ~ A
E A.
1.10.6. A
t.
=A--B
Definition.
(iii)
A
can be defined inductive-
A,
A ~ A = VxAE A,
In any language
~
(as intended in 1.10.2), a formula
is said to be negative, if it is constructed from negated prime formulae
by means of
V, &, ~, ~
.
(In systems with decidable categories of prime
formulae we shall assume that a negative formula may also contain unnegated prime formulae out of the decidable categories.) 1.10.7.
Remark.
In
~
there are Harrop formulae which are not provably
equivalent to a negative formula. SyT(x,x,y)]
(see
3 ~ 2 ) •
An example is But conversely,
m Vx[~ ~yT(x,x,y) every negative formula is
a Harrop formula. 1.10.8.
Lemma.
Let
H
be a formal system based on many-sorted intuition-
istic predicate logic, and let
A
be a Harrop formula constructed from
decidable or doubly negated prime formulae. ~A~-* Proof. (i)
Then
~A.
By induction on the complexity of
A .
The assertion holds for double negations of prime formulae and
87
decidable
prime formulae. -7 m /k *-e /k .
(ii)
A*-e
If
mmA,
B(--e t o m B ,
then
(A&B)
e-~(mmA&m-TB)
4"-e(A&B)
(1.1.8, v) (iii) If
Ax ~
m max,
then
V x A x -~ m - 7 V x A x -~ Vx m m A x - * (iv)
If
m -7 B ~ B
,
VxAx.
then
m re(A-*B) ~-~ (A-*m roB) ~-e (A-*B) 1.10.9. sorted)
Lemma.
Let
predicate
H
logic ; let
Vx -7 m A x
DNS
be a formal
For
A
system b a s e d on i n t u i t i o n i s t i c
be o b t a i n e d from
H
(many-
by a d d i n g the schema
-* ~ m V x A x
(for all sorts of v a r i a b l e s (i)
H'
(1.1.8, IV).
x).
not c o n t a i n i n g
Then
V :
H ~ -n -7 A ~--~ A, (ii)
For all
A
H'~mmA
~-eA' .
(iii) If all subformulae B e-e m -7 B )
in
H~mmA
of
H,
A
are stable
this l e m m a is used in 1.11.4.) (i),
(a) Let
mm
(ii),
(iii) can be proved s i m u l t a n e o u s l y
A.
We consider
B x e - e (Bx), .
1.10.10.
Let
e-* Vx -~-~ B x e - e V x B ' x
Lemma.
Let
H
by i n d u c t i o n on the
cases :
~-~ ( V x B x ) ,
language,
of the excluded
ZxBx.
m m Bx~--~ (Bx)'
denote m a n y - s o r t e d
for a first- or h i g h e r - o r d e r of the principle
(i)
two typical
(~xBx), <--~ m Vx m (Bx), ¢ e I V x -i B x ~ - - ~ m m
(b) (For (il) or (iii) only.) m m VxBx
stable if
~-*A' .
(Note :
of
is called
then
Proof.
complexity
(B
intuitionistic
and let
third.
Hc
predicate
logic
be obtained by a d d i t i o n
Then
HC b A ~-eA' HCbA ~ i b A '
(ii) Proof.
(i) is obvious.
(ii) f r o m left to right can be proved by i n d u c t i o n
on the length of d e r i v a t i o n s is trivial.)
in
Hc .
(The i m p l i c a t i o n
We take for example Codel's
fication. (a) B a s i s : If
~c ~ A ,
A m BVB-*
B,
A
is an axiom.
then
from right to left
system as a basis for our veri-
A' - m (m B , & m
B,) -* B'
88
which
is equivalent
lemma
1.10.8
If since
in
then
roB, & m C ' - ~ m B '
,
VxmB'x-~mB't
,
axiom
Induction
length
k + I.
completely Assume
A'
step.
of l e n g t h
rule applied
hypothesis,
Now
The
in
H
I)
obviously
A,
suppose
various
cases
to be a p p l i e d
rule
is
since
holds
PL2,
if
in
H e ~A
H e ~A
cases
PL15,
A'
H.
PL3,
by a de-
by a d e d u c t i o n
according
so
PLT,
of
to the final
PL8,
and QI
A ~ C V B 1 -~ C V B 2 ,
hence
H~
B'x-~C' .
H~-~C'-~mB'x,
~c,-c,,
so
Theorem.
follows
are
and
Let
from
Since
m C ' &-~B~ -4 m C '
by c o n t r a p o s i t i o n
to be applied
again,
E - HA ~ ,
.
mB~
mC, &~B~ -- mB~
By c o n t r a p o s i t i o n
,
f r o m our i n d u c t i o n
~ C ' &mB~ -- mC' &mB~ . to be
Q4,
so
A = XxBx -~ C .
A' -= m V x m B ' x ' 4 C so w i t h
H ~VxmB'x-~m
QI
mC'
By
'
H ~ ~C'-~VxmB'x. By lemma
1.10.8
and r e m a r k
ffb(~sx'C)' H
be one of the
HAS • P C ~ p H A S .
Then,
systems if
Hc
HA, denotes
N-HA m ,
HA m
the c o r r e s p o n d i n g
system, He ~ A +-->A '
(ii) H c ~ A Proof.
of
etc.
for any f o r m u l a
to d i s t i n g u i s h
mB~-*
hypothesis,
(i)
which
by contraposition.
and
By contraposition,
classical
this is d e r i v a b l e
Then as before,
,
H ~A'
-4 re(me' & m B ~ )
the last
1.10.11.
because
hypothesis
-4 "~C' & ~ B ~
I - HA ~ ~ ,
H
less difficult.
that,
then
in the derivation.
mC~ &mB~-~-~B~
1.1o.7
are even
Assume
_< k ,
We have
A' -= m ( m C ' &-~B~)
induction
in
trivial.
by i n d u c t i o n
Assume
;
(1.1.8,
-~ m B t ' - ' m V x m B ' x
=- m ( ~ B ' &-~-~B')
the last rule
mC' &mB~
A' ~ B ' - ~ m ( m B ' & m C ' )
A' ~ B ' t - ~ - ~ V x m B ' x .
schemata
duction
This holds
so by c c n t r a p o s i t i o n
by c o n t r a p o s i t i o n
A -= B V m B
The other (b)
,
m - u B' -" B' .
etc.
A = Bt-~ZxBx,
If
to
1.10.7.
A ~ B-4 B V C ,
m roB, - * m ( m B ' & m C ' ) If
H
and r e m a r k
We have
additional
= only
axioms
The e q u a l i t y
H~A'
.
to add to the proof of 1.10.10
a discussion
of the
and rules.
axioms
are trivial
to deal with,
as are the d e f i n i n g
axioms
for the constants. Further that
H~
we have A' ;
In the case of
to verify,
for any instance
A
of the i n d u c t i o n
schema,
this is obvious. HAS+ P(~o~HAS
finally,
we have
to check
that f o r ~ i n s t a n c e
s9
A
of
WCA,
resp.
CA , ~
A'
Let e.g. A ~ ~xnvx1"''Xn [B(x1"''Xn ) ~-~xnx1"''Xn ] " We have to show (I)
~
m v x n m v x 1 . . . x n [B,(x1...Xn)
We note that in
H
for some
e--~m mxnx1...Xn ] .
yn
VXl...Xn[B'(x1...Xn)
e-->ynxl...Xn].
Hence also n
vx1...xn ~ ~ [B,(~l...x n) ,~y Xl...xn], and thus using
~ m (D I&D2) *---~m m Dl & m mDz, aria
~ ( D I-D2) e - ~ ( ~ D
I-~D2)
VXl...Xn[m mB'(x I and with 1.10.8,
. . .
(1.1.8, v, iv), Xn)<--em m y n x I
. . .
Xn]
1.10.7
Vx1...Xn[B,(x I ... Xn) ¢--~ m mYnx I ... Xn] . Hence (I) follows,
by
~IYn D ( Y ) ~ V Y
1.10.12.
Corollar 2.
Then
is conservative
Hc
1.1o.13.
Let
~ over
nmD(Y) .
be one of the systems indicated in 1.10.11. H
Some further information
w.r.t, negative formulae. is given in Kreisel
1962C,where
also
lemma 1.10.9 (ii) is stated (Theorem I, Corollary). The concept of a Harrop formula (ice° a formula without strictly positive occurrences of V, Z) appears first in Harrop
196Oo
9o
§ 11.
General discussion of various
schemata and proof-theoretic
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
closure conditions.
1olloio
Introduction°
Certain schemata and rules will appear frequently in
the statements of metamathematical results in the sequel.
In this section
we briefly discuss the principal ones. Let us define a rule as a set of
(n+1) - tuples of formulae ; an element of
this set is an instance of the rule. of a rule,
F1,...,F n
If
are called the premisses,
Fn+ I
A rule is said to be a derived rule for a system (Fo,...,Fn>
~,
is an instance
the conclusion°
if for each instance
of the rule,
~ + r h F o ..... ~+r~rn_ I ~ + r ~ F n o A rule is said to be an admissible rule for a system from null assumptions") if for any instance
H
(or:
"derivable
of the rule
PFo ..... ~ffFn_1 ~ F n . Admissible and derivable rules are instances of proof-theoretic closure conditions of a rather crude kind : they only involve the set of provable theorems.
By a study of normalization for systems of natural deduction,
one
can obtain more delicate proof-theoretic closure conditions involving the deductions themselves. For reference in the discussion below, we now briefly recapitulate the intended interpretation of the intuitionistic logical constants. I°)
A proof of
A&B
consists of a proof of
A
and a proof of
B ;
2° )
A proof of
AVB
consists of a proof of
A
or
B ;
3°)
A proof of
VxA
consists of a construction
proof
c
of the fact that
yields a proof of
A proof of
5° )
A proof of
is in the domain of the variable
A d , together with a proof
~xA
consists of a
Ac , and a proof that
proof that
of
which, applied to a
~'
x,
of this property
H°
4°)
of
Hc
d
a proof of
~
c H
Intuitively,
A--B of
A
c
c
in the domain of
belongs to the domain of
consists of a construction into a proof
nc
of
B
E
x
and a proof x °
which transforms auy
(together with a proof
E'
satisfies this condition). the predicate
HA(C )
("c
proves
A ")
is assumed to be de-
cidable. For a more detailed discussion of this interpretation, Troelstra 1969~ @i.
see Kreisel
1965,
91
1.11.2.
Disjunction
and explicit definability property.
Nearly all intuitionistic satisfy the so-called
ED
ff
~xAx
formal systems discussed in this monograph
"explicit definability
= ~n
(~An)
(~xAx
(x
a numerical variable).
In virtue of
implies the disjunction
property
ffA~ffA
or
fib
~(~x=0--A) & (x/O~B)) <---*A VB,
(AvB
closed).
With respect to other sorts of variables, of
ED
~ gxAx x
= ~t(~At)
(~xAx
is now any sort of variable,
elements of the range of the variable ED, ED', DP (constructive DP,
we often e n c o u ~ e r
a generalization
of the form
ED' where
(ED)
closed)
ED
~P
property"
closed) and
t
x )
ranges over terms (definable
of the same sort as
x.
have often been presented as criteria for the "constructivity" character)
of a formal
system.
Of course,
if we consider e.g.
there is a property of the class of informal proofs which parallels
DP ; a proof of establishing
A vB
DP
should contain either a proof of
fies a similar closure condition° as we stated
(Similar,
DP , the formal proof of
existence follows from the existence be contained as "sub-proof"
A
B ;
but not the same condition :
of a formal proof of
in the proof of
B
whose
A V B , need not
A V B o For a closure condition the condition
on informal
we must establish more J)
Also,
ED, ED', DP
structive character"
are neither
of
HA
(so
sufficient nor necessary
of the system studied,
ly the intended interpretation, HA"
or a proof of
or the formal proof of
on formal proofs which more closely resembles proofs,
A
means that the set of formal proofs of the system satis-
HA' U HA"
since there are divergent extensions
is inconsistent)
and on the other hand, there are systems intuitionistically constants~ systems,
acceptable,
HA+N,
which both possess
~, H A ~
H A + CT
DP.
HA,,
ED, DP ;
, which are obviously
on the intended interpretation
but which do not possess
one may take
for the "con-
i.e. they do not enforce unique-
of the logical
As an example of the diverging
+ IP
(cf. 3.7.4
(i), 3.7.4 (ii),
3.2. ZT). We present an example of an intuitionistieally does not satisfy Let
ED
(from Troelstra
~
justified
system which
; the example is due to Kreisel)°
Proof ~ ProofHA , and Ax ~def Pr°°f(x'rO = I~) V V y m P r o o f ( y , r O = 11) .
Since
}~
is intuitionistically
consistent
(on the intended interpretation),
9~
Vy~Proof(y,~O
for any n u m e r a l
~
is i n t u i t i o n i s t i c a l l y
= 17)
note that because
VyTProof(y,~O
of [.
TmAx .
Further
~ ~Proof(~,rO=17)
Therefore
~ ~-~Vy~roef(y,~O
for any numeral
true, hence also
= I~) , we must have
:
~)
~ o
Also
W~Ax Now assume
~
[~y Proof(y,'-o = I~) v V y ~ P r o o f ( y , %
~ ~ x A x -~ A ~ ,
then it would follows
o I~)] °
that
[ ~ " P r o o f ( y , ~ O = l ~) V V y - T P r o o f ( y , r 0 = l ~)] -~ V y ~ P r o o f ( y , % = l ~) ,
~ y P r o o f ( y , ~ O = I D -- V y ~ P r o o f ( y J 0 = t ~) ,
and thus
~Vy~Proof(y,~O=1 ~) T h e r e f o r e HA+ ~txAx
t h i s c o n t r a d i c t s G o d e l ' s second i n c o m p l e t e n e s s theorem, does not satisfy ED, since m + ~ A x ~ A ~ , but~ot Io11.3.
Schema
D:
Vx(AVBx)
-~ ( A V V x B x )
,
x
~+~Ax~A~.
not free in
Ao
This schema has a t t r a c t e d a t t e n t i o n because i n t u i t i o n i s t i c logic w i t h this schema added, models w i t h constant In G o r n e m a n n schema D
domain
is s e m a n t i c a l l y
characterized
(see e.g. G ~ r n e m a n n
the d i s j u n c t i o n property.
predicate
by K r i p k e -
1971).
1971 it is also n o t e d that i n t u i t i o n i s t i c
possesses
hence
However,
predicate
logic +
this p r o p e r t y
is
lost as soon as we go to arithmetic. Actually, complexity A m ZyBy, ~Bx
HA + D = ~ HA c , as is easily seen ; by i n d u c t i o n on the logical
of
A
then
V Zy By ; if
hypothesis, Vx~Bx If
one v e r i f i e s (Vx~Bx Bx,
V ~By
ZyBy
therefore
D
note that
restricted
Let for example A ~ ~Vx Cx, H~+DC
~ A V VxBx;
which is impossible.
(1)
HA,
~Bx
and if
-TBx V Zy By °
V ZyBy
for all
7Bx,
then
By i n d u c t i o n
x , and thus
Vy(By v - T B y ) -~ Vy(By V-7 V x B x ) <--~
spoil the d i s j u n c t i o n property.
Let
Dc
to closed instances°
Vx Cx
Bx -= Cx
be a
Then hence,
~+~O~vxc~ in
hence also
E.g. if
V -7VxBx o
Even closed instance~ o~ D indicate
Vx(A V ~ A ) .
o
A -= V y B y ,
6--> V x B x
of
V ~yBy)<--9 Vx(-~Bx V ~ y B y ) ;
then
Bx V ~ B x ,
the pmov~6~lity
rossersentence Vx(A V B x )
if
~+D
or ~ +
° Dc
for
holds in would
H~ + D c , snd let F~ ; by
satisfy
Dc
DP,
bWCx
At the same time it follows
that
D°
is not derivable
not even the rule for sentences :
t-W:(AvBx)
=
kAVVxHx.
This contrasts with the ease for i n t u i t i o n i s t i c
predicate
logic, where cut
93
elimination for a calculus of sequents or normalization for natural deduction readily yields tained from by
(I).
(In a closed normal deduction,
V - introduction from
V - i n t r o d u c t i o n ; hence Since
D
A
Vx(A VBx)
A V B a , and this in turn from
or
VxBx
must be obA
or
Ba
can be derived.)
is obviously invalid for our realizability interpretations,
and
the rule is not admissible even for arithmetic, we shall not spend further attention 1.11.4.
on it. The schema
Vx m m A
~ mmVxA
.
(DNS = ~ouble negation _Shift).
To this schema attaches considerable technical interest,
since, as we
have seen in 1.10.9, in theories based on intuitionistic logic + DNS , the negative translation satisfies
mmA
Also it permits us to derive, Assume DNS;
VxmVy~A'(x,y) hence
, then
mm~zVxA'(x,zx)
<--gA'
for all
A o
in intuitionistic analysis, Vx ~ m S y A ' ( x , y )
, i.e.
,
so
m VzmVxA'(x,zx)
(AC)'
from
m~Vx~yA(x,y) o
AC: by
In other words, the
'- translation interprets classical analysis, formulated with sequence variables and the axiom of choice, in the corresponding intuitionistic theory + DNS . This fact constitutes the starting point of Specter 1962. Io11.5o
Narkevts schema and rule.
Marker's schema in its most general form can be stated as
M
Vx[AV~A]
& ~xA--
ZxA.
A simpler and weaker form is MpR
m~XxA c MpR
Let us use for A of
x
~ SxA for
(A
primitive recursive)o
restricted to closed instances.
MpR
ranging over natural numbers,
which can be tested for each :xA
(i.e.
mm~KxA )
x
~
expresses : if we have a property
(i.e.
Vx~ V~A))
for all
x ,
such that
that
A .
and an indirect proof
then this amounts to a direct p r o o f o f
other words, Marker's principle enables us to assert, A
Intuitively,
m~xA
:xA o
In
for a computer testing
guarantees that the computer will find an
x
This is obviously an enlargement of the concept of "con-
structive". o
MpR
is not derivable in
~
(Kreisel 1958A).
Consider e.g. the follow-
ing instance
(I) where
~Vx~Bx Vx~Bx
~ ZxBx
is a
~ossersentence~r
Naking use of the closure of
~
HA °
under
(of. e,~. 3.1,7)
94
it would follow that if
Bx
m~
(I),
is primitive recursive, hence
In the first case HA ~ 9~ ~ B x
o
,
~ B ~ or
~ ~B{
in the second case
° HA ~ ~ V x ~ B x ,
B o t h cases conflict with the assumption that
rossersente,]¢e HA,
HA L ~ V x ~ B x
for
V x ~ Bx
ioeo is a
HA o
and many other intuitlonistio formal
systems, have been shown to be
closed under the rule ]V]R
bVx(Av~A),
~ =~ZxA
= ~ZxA,
and a f o r t i o r i under ~RpR
~ ~ x A
= ~ A c MRpR
and its specialization Using lish
as follows.
For all
assuming Hence
A
primitive recursive,
to closed formulae°
w - consistency and classical metamathematics freely, we can estab-
ZR~R
closed.
for
[,
Assume
~A[
~- consistency of
~n(~
~A~) ;
/ ~ZxAx
or
~ ~A~
H~,
, A
~xA
~ n ( ~ ~ A n ) ; then,
we obtain a conflict with
arguing classically,
For m o r e details on
primitive recursive,
Suppose
~ n ( ~ A [ ) ; hence
~ ~Vx~A ~xAx
° o
}~i9, see § ~.8, § 5.4.
Technical interest of Zarkov~s schema also derives from the fact that it is validated by Godelts Dialeotica interpretation, and that by a result of Godel (Kreisel 1962 , § 3) completeness Worot. intuitionistio validity (conceived as the analogue of classical set-theoretic validity) implies the validity of Markovls schema in intnitionistio arithmetic. In recursion theory, there is a rather special application of Zarkov~s schema in the proof of Post's theorem (a set N\X
are both roeo)°
X~N
is recursive if
X
and
The application involved corresponds to a schema of
predicate logic of the following form : V~y(A V ~ A )
& V~y(B W B )
& Vx~(~A~yv~Bxy)
& V~Xz(A(x,y)
&B(x,z))
- W(~A~yV~Axy).
Or with function variables: ~ Z y Z z ( a y = b z ) & Vx ~ ( Z y ( a y =
x) V Z y ( b y = x ) )
This schema is presumably weaker than
-- Vx(~y(ay: x) V m ~ y ( a y = x ) )
o
MR , but the precise logical relation-
ships are unknown. I°11.6.
Independence-of-premiss schematao
An "independence-of-premiss schema" is a schema of the form (x in
A)
not free
95
(I)
(A--~B) -- ~(A--B)
where
A
in general must satisfy additional
restrictions
~,
either syn-
tactical or logical. The principal
instances of independence-of-premiss
schemata which we shall
encounter are
(so
A
must be of the form
Ie°
~C
here),
Vx(A V--A) & ( V x A - - ~ y B )
and the weaker
-- ~ y ( V x A ~ B )
and the still weaker IPpR
(VxA--[yB)
-- ~y(VxA--B)
On the intended interpretation A~xB
,
the " x
for which
(and not only on
A
~,
primitive recursive).
of the logical constants,
B"
may depend essentially
schema (I) expresses,
that for
the
x
does not depend on the proof of
indicate a priori an
x
which should satisfy
ence-of-premiss
B
schemata do affect the intended
of the logical constants:
they restrict
if
(2)
~A-
(A
admissible
~B
independence-of-premiss A certain technical
1.11.7.
So independinterpretation
of the form
A~xB
.
show more or less the same as the con-
of intuitionistic
that the system discuss-
implication
enforced by the
schemata. interest
by modified realizability
see e.g.
holds.
the type of mappings from proofs to
sistency of the schema relative to the same system:
metic !
satisfying the at all : we can
rules of the form
restriction)
ed permits the interpretation
restricted
A
= b~(A-B)
under an additional
IPpR
A
A A
(constructive)
proofs which can be used to establish implications The corresponding
if we assert on the proof of
being true).
An independence-of-premiss restriction
(A
of
IP
is in the fact that it is validated c (i.e. (see § 3.4). Not even IPpR
interpretations
to closed formulae)
is derivable
in intuitionistic
arith-
3o1.11)o
Church's thesis and ruleo
In a formal
system with function
symbols,
(the intuitionistic
version of)
Church's thesis can be expressed as cT
v~ ~x Vy ~z [Txyz & ~x = uz].
Combined with a choice principle
, we obtain a version which can be co expressed in the language of arithmetic : CT o
Vx ~ A ( x , y )
AC
-- ~z Vx ~u(Tzxu & A(x,Uu)) o
96
The conceptual interest of
is in their bearing on the question: o do the concepts of "humanly computable function" and "mechanically computable
function" coincide ?
CT
and
CT
(here "humanly computable"
should mean "computable by
an idealized mathematician in the intuitionistic of these matters,
see Kreisel
ly in the fact that
CT
sense":
1970, and especially Kreisel
for a discussion 1972)! and second-
implies the incompleteness of intuitionistic predi-
cate logic (sketched in Kreisel 1970, Technical Note I : for a more detailed exposition see van Dalen~). Church's thesis turns out to be consistent with all intuitienistic formal systems not involving the concept of choice sequence, containing the fan theorem or bar induction The underivability of
CT
o "Charch's rule" takes the forms:
where CR
~6 GR
abbreviates
is obvious,
~xVy~u(Txyu
since
CT
& ~=Uu)
o
is
false in
HA c .
and
o
A weaker
version of Church's rules takes the form
WCR
If
~Vx~vAxy,
such that WCR
then there is a recursive function
Vn b A(~, ~ n ) .
is closely connected with
tion,
ED
is equivalent to
0bviously~ f
and especially not
(cf. § 3.2).
WCR
implies
ED : for systems with a recursive axiomatiza-
WCR
ED o
(Kreisel 1972 ) . Conversely,
if
ED
This is seen as follows. holds, we may construct
as fn = min m Proof(jlm, CA(~, J~2m) ~)
which makes
f
recursive, in view of the recursiveness of "Proof"°
As remarked in Kreisel 1972, this result tells us where not to look for a conflict with Church's thesis ; all the usual systems satisfying be expected to yield a refutation.
ED
cannot
Chapter II MODELS AND COMPUTABILITY
2.~.I.
Definition over the tFpe structure~
repeatedly with definitions structures, if
~, T
type structures,
i.e. type
obtained from certain basic types by closure under the condition :
are types,
structure being T
In the sequel we shall meet
over applicative
then so is
T.
(~)~,
our principal
example of such a
In the discussion below, we restrict our attention to
for simplicity. An applicative
t'E ~,
t,t'E M
subset
M'cM
(i.e.
~
set of terms then
M
tt'E M .
is e set of terms such that if A basis for an applicative
such that the closure of
is the smallest applicative
applicative
s~s
M'
set
tE (a)T , M
is a
under application yields
set containing
M' ).
M
Examples of
:
(a) The set of closed terms
CTM
of
N
HA w
with the constants of
~-HA w
as a basis. (b) The applicative and type
0
(c) The applicative the type if
x~
set generated by the basis consisting of the constants
variables of
0
~-HA~
(CTMo).
set generated by the basis consisting of the constants,
variables
is the type
and a single fixed type
~
Further examples of applicative ~
with
(i)
T
l(~)~n
Po(t~ .... ,tn)
(ii)
if
~(~)~(t~, ....,tn)
(i)'
an applicative Po(t)
if
(ii)' P(~)T(t)
set
of an M
t~ ..... the 0
of the
(a), (b), (c). n - ary relation over the type
of terms takes the following form : and
A(t~ ..... tn)
(A
being any given
~t~ ~ ~ ... v t ~ M(p~(t~ .... ,t~) ~ ~(t¢~,...,~oq~).
(for an example
see
2.2.5)
takes the following form
set) :
t6 O, if
if
Ao(t )
A(~)T(t)
and
te
and
~t' ~ ~(P t' = P
Such a definition may be viewed as a superposition over a type structure, applicatively
i((~)~) = l(~) +l(T) + ~.
t~,...,t n E M-
A slight generalization (M
i(0) = 0,
in examples
for an applicative
predicate);
(CTMo(x~),
sets are now provided by restriction
In its simplest form, a definition structure
variable
variable).
Let us define the type level as follows:
types to types
~
from type
where each type 0
~
tt') . of a sequence of definitions
is not only viewed as obtained
but also acts as a "ground type"
for more complex types w.r.t,
the property
A
.
(or "basic type")
98
A definition according to (i), (ii) or (i)', (ii)' is a definition over the type structure of metamathematical properties of metamathematical objects (i.c. terms).
Of course, similar definitions are possible within the system
itself, i.e. we may define properties within the system according to a schema :
(i)"
Pc(X ....
%ef
(ii)
..... x =)~) mdef VY~'''Ynk ckY1'''''Yn) " P~(xlY1''''XnYn))"
and such a schema similarly permits generalizations and variants(cf. Z 5 15 for an example). 2.1.2.
Establishin~ properties for applicative sets of terms.
We consider three types of definitions of a property an applicative set (A)
Q
Q for the terms of
M:
is defined as a unary predicate over the type structure, according to
clauses'(i) and (ii) in 2.1.1. (B)
Qt mde f P(t,...,t) , where
P
is an
n - ary predicate defined over the
type structure according to clauses (i), (ii) in 2.1.1, and holds for (C)
Q
A(t,...,t)
t~ M.
is defined inductively over the type structure according to (i)' and
(ii)' in 2.1.1. In each of these cases, establishing
V t6 M[Qt]
ing
M,
V tE M'[Qt]
Lemma.
If
for a basis
tl,...,t n
M'
of
may be reduced to establish-
because of the following lemma :
are terms such that
Q(ti)
for
1~i~n
defined by a definition of type (A), (B), (C), then for any repeated application from Proof.
tl,...,t n,
Qt
, and
Q
is
obtained by
holds.
Quite straightforward ; we have to show that if
t IE (~)~ , t 26 a , then
t
Q(tl), Q(t2)
and
Q(tlt2) .
Similar lemmas reduce the establishment of properties
Q
defined via defini-
tions of type (i)", (ii)", or one of the many variants, to the establishment of
Q
2.1.3.
for a basis of the set of applicative terms considered. Definabilit 2 aspects.
Suppose
Q
to be an
(A), (B), (C) in 2.1.2. of
Q
(so
Q*
themselves) expect
Q*
n - ary predicate defined by a definition of type If we wish to consider an arithmetical version
Q*
is a predicate of godelnumbers of terms, not of the terms
then if there is no bound on the type level, we cannot in general to be arithmetically definable, since
~*
should satisfy e.g.
for a definition of type (A) : Q*(m)
4--~ S~ (type (m)= r ~ u & Q ~ ( m ) ) ,
Q~)T(m) ~ (where
ra ~
Vn (Q~n ~ Q~(app(m,n)))
denotes the code number of type
~ , app(n,m)
the arithmetical
99
representation of the application operation),
therefore with increasing type
level the logical complexity of the arithmetical formula indefinitely ; for an actual counterexample So for an arithmetiz~8 version,
~(m)
increases
see 2.3.11.
the applicative
set of terms considered
will have a bound on the type level. As we shall see, in our application~,the definability of the arithmetized predicates usually ensures formalizability of the proof of numbers 2.1.4.
n
of terms in the applicative
Sets of terms closed under
@*n for all godel-
set of terms considered.
~ - abstraction.
If we consider sets of terms not only closed under application but also under
~ - abstraction,
the reduction effected by the lemma in 2.1.2 might not
be sufficient since the effect of closure under
~ - abstraction might force
us to consider a very "large" basis in the sense of 2.1.1. Let us call a
k - set of terms any set closed under application and
abstraction w.r.t, variables of the set. which yields
M
A
k- basis for
by closure under application and
~-
is a subset
~- abstraction.
The appropriate trick for establishing a property (A), (B), (C) in 2.1.2 for a
M
Q
defined according to
X- set is then to prove a stronger property
Q*
("Q - u n d e r - substitution"): Q*(t)
holds if
Qt I
holds for any
tI
obtained by substituting for some
(not necessarily all) occurrences of variables in holds
(and possibly renaming bound variables in
free in
t'
becoming bound after substitution),
t t
terms
t'
for which
so as to avoid variables
(see e.g. 2 . 2 . 2 7 - 2.2.51).
Q
100
2.2.1.
In Godel 1958 , the concept of a "berechenbare Funktion"
(= computable
function) is regarded as a primitive concept, and it is considered evident that each primitive recursive functional definable in Godel's theory (i.e. a functional represented by a term of
~_~w)
is "computable".
In Talt 1965 this concept is made the subject of a formal analysis, and it is shown that each constant term of type implies that each term of type version of
~_~w)
O
0
"reduces to" a numeral, which
can be formally proved (in a suitable
to be equal to a certain numeral.
As a by-product,
Tait's analysis yields more : all terms can be brought into a standard form ( "normal form"). This is exploited in Tait ' 1967 , to show that the closed terms of yield a model for
N_~W
I - H ~-~ A ~ , if equality between terms is interpreted in the
model as : reducing to the same normal form.
Tait 1967 also introduces the
inductively defined formal computabil~[N predicates
("Comp"), a device which
has been extensively used since. In the present section we discuss computability predicates and use them to prove normalization and strong normalization theorems for the terms of
~_~w
and extensions. The main novelty is the simplification of the treatment and strengthening of the strong normalization theorem in
2 2 ~9.
We first discuss computability for the terms of with classes of terms with In 2.2.35,
~-operators
instead of
~-~; H, Z
then we deal as primitives.
the various proofs of normalization and normal form theorems
occurring in the literature are discussed and compared. Additional material on computability is given in the next section. We feel the notions of computability and strong computability have a certain intrinsic interest, because of their intuitive simplicity ! hence the rather extensive discussion,
with description of different approaches,
below.
It should be noted, however,
that for all applications of computability given
in the sequel of this chapter, in proofs of results which do not require the notion of computability for their formulation, to standard computability of terms of type 2.2.2.
O ;
we may restrict our attention the remainder is a luxury.
Definition of reduction and standard reduction for terms of
We say that a term is a contraction of
t t ),
contracts to a term
t'
(t
contr,
t' ,
~-~. or
if one of the following clauses is satisfied :
(a)
t ~ Htlt 2 , t' ~ t I
(b)
t ~ Ztlt2t3,
(c) (d)
t ~ Rtlt20, t' ~ t I t Rtlt2(St3) , t' ~ t2(Rtlt2t3)t3.
t' ~ tlts(t2t3)
t'
101
Ne adopt the terminology of C u r r 2 - F e 2 s
195~
and call
t
in
the clauses (a) - (d) a redex (and similarly for other types of contraction introduced in the sequel). If t
t'
is obtained from
(i.e. a subterm of
t' ~I t
t
t
contracting a single subterm (occurrence) of
is replaced by its contraction)
then we write
t ~I t' "
or
A sequence (finite or not)
to, tl, t2, ...
is said to be a reduction sequence o f
to
with
ti+1 ~I t.1
(starting from
for all
i
t o ).
A term which does not admit any contractions, is said to be in normal form. A finite reduction sequence ending in a term in normal form is said to terminate . We say that of
t
t ~ tI
ending with
t'
(t
reduces to
t' )
if there is a reduction sequence
(a reduction sequence from
t
to
t' ).
A reduction sequence is said to be strict, if the contractions (a) - (d) are applied only in case
tl, t2, t 3
are normal.
Attention to strict reduc-
tion sequences implies prescribing a certain (partial) order for the contractions.
The order in which contractions have to be executed can be made
completely deterministic by introducing the concept of the leftmost minimal redex
(lmr).
The
lmr
of
t
is a subterm of
t
when
t
is not normal,
t
(t
assumed to be
of
t
otherwise undefined. We define the
lmr
by induction on the complexity of
non-normal). (i)
If
t ~ ~tl...t n , ~
tl,...,ti_ ~ of
a constant or variable,
are normal,
ti
not, then the
and lmr
is the
lmr
t.. l
(ii) If
t
is a redex and (i) does not apply,
A standard reduction sequence such that We write 2.2.3.
ti+ I t ~w t'
then
to, tl, t2, ...
is obtained from
ti
imr(t)
is
t
itself.
is a reduction sequence
by contraction of the
lmr
if there is a standard reduction sequence from
of t
ti . to
t' .
Comparison of standard and strict reduction.
Intuitively we feel that there is standard and strict reduction :
little essential difference between
strict reduction corresponds to the natural
idea of contracting ("computing")
starting "from the inside"
(i.e. starting
with redexes not containing other redexes) ; standard reductions make in a convenient but arbitrary way (since not directly related to the partial ordering of the tree of subterms)
the procedure completely deterministic.
We show Proposition.
If
t
strictly reduces to
standard reduction sequence from
t
to
t' , t' t'
normal,
then there is a
102
Proof.
By induction on the length of strict reduction sequences.
Suppose (1) the assertion to hold if than
k
t
strictly reduces to
t'
in less
steps ; we now prove the assertion for strict reduction sequences
of length
k
sequence•
So assume (2) also the assertion to have been proved for all
by a sub-induction on the complexity of the first term of the
strict reduction sequences of length
k
starting with a term of complexity
< i. Let
tl, ..., t k
be a strict reduction sequence from
let the complexity of ing
tI
be
i.
Then either
t2
tI
to
tk , and
is obtained by contract-
t I , and then the assertion readily follows from induction hypothesis
(I).
If
t2
is not obtained from contracting
tI ,
tl, ..., t k
starts
with an initial segment tl = ~s~1)... s(ml) q~sl2).., s(2)m' "''' ~ 4 n) "'" s(n)m where
~
normal.
is a constant or variable of N - H A w, and s 1(n), -.., sm(n) are ~I) ~n)~ s. , ..., s (1
Then the sequences
duction sequences after omission of repetitions. (i)
all sequences
s! I), .... s! n) 1
repetitions.
have length
Then either
after omission of
1
Then by induction hypothesis (1), there are standard
reduction sequences from
s! I)
to
1
~S~ n) ... Sin) -= tn
to
tk
reduction sequence froml t I
s!n)
(I < i < m)
l
and from
~
which may be combined into a standard to
t~ ; or
(ii) there is a sequence
s.- ), ..., s (n/ of length k, 1j~i, for 1 1 < j < m , and ~s ~n)
without repetitions s (I) = s (n) s(mn) __ tk J Then the assertion follows by the sub-induction hypothesis (2).
and
(Cf. Tait 1967 , II on page 203.) Corollary.
All terminating strict reduction sequences starting from a given
term terminate in the same term. In the sequel we shall establish a much stronger result (see 2.2.23). 2.2.4.
Alternative definition of may also be defined as a relation between terms, inductively generated
by the following closure conditions: t ~ t, = t~t",
t ~ t' = tt" ~ t't", Htt'~t,
t ~ t' = t"t ~t"t',
Ztt't"~tt"(t't"),
Rtt'0~t,
t ~ t'
and
t I ~t"
=
Rtt'(St")~t'(Rtt't")t" .
The equivalence of this definition with the one given in 2.2.2 is intuitively obvious, and in fact formally provable in
H~,
e.g. by an appeal to the
theory of § 1.4. 2.2.5. ability.
Definition of computabilit2~ strict computability1 standard computWe define a predicate
Comp = U {Comp~ I ~ E T},
defining
Comp~
to3
by induction over the type structure : (i)
ComPo(t ) mde f t E 0
(ii)
Comp(a)v(t ) mde f V t'(Comp~(t')
and
t
reduces to normal form ; ~ Compr(tt'))
and
t
reduces to
normal form. Similarly we define
Comp', Comp~
to" in the definition of
Comp a
and
Comp", Comp~ , replacing "reduces
by "strictly reduces to" and "reduces to
... by a standard reduction sequence" respectively. 2.2.6.
Theorem.
All terms
t
of
~-~.~
satisfy
Comp"(t) , and hence
have a terminating standard reduction sequence. Proof. term
We note that if t
Comp"(tl) , ..., Comp"(tn) , then
constructed by repeated application from
lemma in 2.1.2.)
Comp"(t)
tl, ..., tn.
for any
(Cf. the
This is an immediate consequence of the definition.
Hence it is sufficient to prove
Comp"(~)
for
~
a constant or variable
of cur theory. (i)
Comp"(O)
is immediate°
(ii)
Comp"(t o) = Comp"($t °)
(iii) Comp"(x °) (iv)
Let
is also immediate, hence
~ = (QI) ... (am)O.
If
Compq1"(tl)' "''' ComP~m(tm) , there are
terminating standard reduction sequences for readily combined into a terminating x~tl...t m. (v)
If
Hence
CompS(t3) , then
We put (I)
t3
v(t3)= k°
There is a uniquely determined for any
and
If
Comp"(Ra)
Comp"(t2)
k.
Let
and
by proving
Comp"(t3)
and
~ ~ (~1) °o. (Cm)O°
Comp"(ti) , 1 ~ i ~ m + 3 ,
v(t3) = O .
There are standard reduction sequences from 1~i~m+3.
k
t.
= Comp"(Ratlt2t3) )
by induction w.r.t, Let
t~.
We now establish
Vtl V t2 Vt 3 (Comp"(tq)
(a) Bas~s.
which are
has a standard reduction sequence terminating
t!~ m %kt~ , t~) ~ St
v(t3) = k
tl, ..., t m,
standard reduction sequence for
Comp"(x a) .
in a term in normal form such that
Comp"(S) .
is immediate.
t~ m O,
ti
to
t!1, t~l normal,
there is a standard reduction sequence from
Rtl...tm+ ~
to Rt~.. "t'm+3 ; Rt~t~t~.. "t'm+3 ~I t~ta''" t'm+3 , and since, according to our hypotheses and the remark at the beginning of the proof, Comp"(t~t~t~...t~+3) If
t~ ~ St
for any
(b) ~nduct~o~_~tep. If from
, also
to
t~1,
Rt~t~t~...t'm+3
is already in normal form.
Assume (I) to be established for
Comp"(ti) , 1 ~ i ~ m + 3 ti
Comp"(Rtl...tm+3) .
t , then
t'i
n
, ~(t3) = k , there are standard reduction sequences normal
(I < i < m+3) , t~ m 6kt~
Then there is a standard reduction sequence from
for a suitable
Rtl...tm+ 3
to
t~.
104
Rt~. . ti+3; also Rt~t~(skt~)t~. t'm+3 ~I t2(Rtlt2(~ ' , , k-1 t3))(sk-lt~)t4""t~5; ,, . . . and this term has a terminating standard reduction sequence by our hypotheses and the remark at the beginning of the proof. Cases (vi) and (vii), where it is to be shown that
Comp"(U)
and
Comp"(Z) , are left to the reader. 2.2.7. (i)
Remarks. Comp'(t)
from 2.2.6.
and
Comp(t)
However,
for all terms
Comp'(t)
and
t
Comp(t)
of
N-H~ w
follow directly
can also be proved directly
along the same lines as in 2.2.6. (ii)
In the definition of
the condition
"and
t
Comp',
Comp"
we might actually have left out
reduces to normal form" in clause (ii).
To see this, note that one easily proves by induction that 0 ~ (defined by 0 o O, 0 (~)T = H T0 ~ ) is normal and satisfies Comp~ (with the weakened definition of
Comp").
Comp~(t0~1...oam) quence of of
t
.
Now if
Comp"(t) , ~
~ ~ (~I)... (am)0 , then
Hence there is a terminating
tO GI ... 0 am , from which a terminating
can be extracted.
Similarly for
(iii) If we are interested slight simplification
standard reduction sestandard reduction
sequence
Comp'
in the computability
of closed terms only, a
might have been achieved by omitting clauses
(iii)
and (iv) in the proof of 2.2.6. 2.2.8. then
Lemma. t
If
t~ 0 ,
t
a closed term of
We proceed by induction on the complexity
closed and normal.
Then
t
has (possibly)
0, S, Stl, R, Rtlt2...tn, tl, t2, ...
have type
normal).
tmO,
Stl,
t.
Suppose
t
is
one of the forms
H, ~tl, Z, Ztl, Ztlt 2
we are done.
Rtlt2...t n If
(n h 3 ) .
t ~ St I ,
0)
Finally,
if
t ~ Rtlt2t3...t n ,
numeral,
so
t
by induction hypothesis
then (since tI
tI
is a numeral,
is closed, normal, therefore
then by induction hypothesis
t3
so is
t.
is a
cannot be in normal form.
Theorem.
term of type Proof.
of
But the only forms of this list which could
of type
2.2. 9 .
form,
0 , are O,
If
in normal
is a numeral.
Proof.
(with
N-HA w
0
(On assumption
of consistency
of
reduces to a uniquely determined
N-HAW.)
Each closed
numeral.
Theorem 2.2.6 and lemma 2.2.8 imply that each closed term of type
zero reduces to a numeral. consistency
of
N_~W
The uniqueness
since if
t~,
of the numeral follows from the t~m,
~m,
it would follow that
~o5
2.2.10. type
Theorem.
0
over
Proof.
N-HA ~
is conservative w.r.t, closed prime formulae of
~,~obtained
by omitting induction from
~-~.
By refinement of the argument in 2.2.9, noting that
~ t I= t 2 . t°~,
For let
s°~m,
~_~w
hence
~ t o = s°
~ ~ t ° = ~,
Then we can find
~ ~ s° = m .
t1~t 2 ~, ~
implies
such that
By consistency of
~-~,
hence ~ b to = so
=~, 2.2.11.
Remark.
In
2.5.6
it will be shown how to prove uniqueness of
normal form for all types (i.e. every terminating reduction sequence of terminates in the same term) by means of a model for 2.2.12- 2.2.19 . 2.2.12.
N - H A ~.
Strong cqmputabilitz.
We shall now refine the preceding discussion, by proving a stronger
theorem : each reduction sequence starting from a term
t
shall call such a theorem a strong normalization theorem.
terminates. A term
t
We is
said to be strongly normalizable, if all reduction sequences starting from t
do terminate.
In order to prove this theorem, we have to modify our
definition of computability to a definition of strong computability. 2.2.15. SC
Definition.
Strong computability for terms of type
, is defined for all
(i)
SC (t)
iff
t6 0
a6 ~
~ , denoted by
as follows :
and every reduction sequence starting from
t
O
terminates. (ii)
SC(~)T
We put
iff
SC ~def
2.2.14.
Lemma.
terms such that Proof.
U
~t'(SCa(t' ) = SC (tt')).
{SO Let
Ia e
~1.
x e (el) ... (an)0,
and let
ti e ~ i ' 1 ~ i % n
ti
is strongly normalizable ; then
If
SC(t a) , then
be
SCo(xtl...tn) "
Obvious.
2.2.15.
Lemma.
ta
is strongly normalizable ; also
SC(x°). Proof.
We establish the assertion of the lemma by induction over the type
structure. Assume for al subtypes
O
of
(~)T
Let SC(t(a)T) . Then SC(t(~)~x~) . tion sequence starting from t. We from t(~)TX~, say tx, t~ 1), t~ 2) ,
as for
t (k)
is defined ; if
t (p+I) 0
t (p+2) '
0
..
the assertion of the lemma to hold.
Let
t, t (1), t (2), ...
be any reduc-
now define a reduction sequence starting ...
t(k) E t(k)x as long o breaks off at t (p) , we take
as follows:
t, t (~) , t (2), ...
a standard reduction sequence starting from
t(P)x.
~"
By induction hypothesis and
SC(tx) , tx, t (I), t~ 2)
so has an ir~ial segment of the form
tx, t~1)x . . . . i tik)x
terminates, and such that
lOd
t, t (I)
t (2)
Now assume Then
t,
t( "k"~
is a terminating
and let
~ ~(~1)"'(%/0'
t.
are strongly
normalizable
SCo(X(~)'t~ I ...tm) , and thus 2.2.16.
Remark.
inductively
(where
SC~i(ti/, ;
sequence for
l
t
SC(t).
hence by lemma 2 . 2 . t 4 ,
SC(a),(x(~)" ).
Instead of using
SCp(O p)
reduction
SC (x p) , we might also have established
0 ° ~ O,
PO ~)~" " = ~o,TO
, as in 2.2.7)
to-
gether with the induction hypothesis. 2.2.17.
Definition.
, where sequences
T
A reduction tree of a term
is a non-empty
such that
n*~E
to the elements of (a)
~<>=t
(b)
If
T,
n * E T
for
t~ ..... t~
I < i < n , and
ordering is prescribed
Definition
definite,
t
tl,...,t n,
t' , then
~(n. ) = t!.
contractions
for all terms.
is the number of elements in
(or classically,
Let
Konig's lemma)
The
T. SCo(t ) ; then
the reduction
hence there are only finitely many terms in normal
such that St*
from
we may assume that in a uniform way an
(to be used in the proof of 2.2.19).
is finite,
not of the form
is a complete list of terms(without
among the possible tree
by 2.2.13 and the fan theorem
level)
finite
a function which assigns terms
which are obtained by a single contraction
length of a reduction
Remark.
~
such that
To make the description
form,
set of natural numbers representing
T = n E T , and
q~n= t' , and
repetitions)
tree of
consists of a pair
o
n E T,
2.2.18.
t
t >t i
for any
t*.
Then
In giving this definition, to the fan theorem,
for
I < i
Let
t i = sP(i)t~ ,
we have made an appeal
(on the meta-
by assuming that a finitely branching
all its branches finite is itself finite. theorem in the proof of 2.2.19
t~
~(t) = max Ip(i) I 1 ~ i ~ n l .
The implicit appeal
(via this definition of
~)
tree with
to the fan
can be avoided
in two different ways : (i)
by giving a proof of the uniqueness
on the strong normalization define t'
v(t)
normal,
as the t>t'
p
of normal form which does not depend
theorem itself (2.2.23),
such that
t v~ ~Pt"
t"
(ii) by strengthening
2.2.19 .
SCo(t )
to:the reduction tree of
trees, which is notationally Theorem.
St ''~
; or
This requires in the proof of 2.2.19 manipulation reduction
and which enables us to
not of the form
For all terms
strongly normalizable.
t
of
t
is finite.
and recombination
of
SC(t) , and hence
t
awkward. N - HA w,
is
lo7
Proof. (I)
We first note that If
SC(ti),
from (II)
If
I < i
tl,...,t n ,
(III) If
, then
(ii)
tea
= (~I)... (an)O , then
If
SC(t) * (~tIE SC I)... (VtnE SCan )
is strongly normalizable). SC(~)
for
~
a constant or variable
of
(cf. lemma in 2.1.2).
SC(O)
is immediate.
SCo(t) , then
from
application
SC(t') , as readily follows from the defini-
n By (I), it now suffices to prove (i)
formed by repeated
SC.
( ttl.., t
our theory
t
$C(t) .
SC(t) , t ~ t '
tion of
then for each
St
SCo(St) , since any reduction
must necessarily
t, tl, t2, ... (iii) SC(H ,~)
be of the form
is a reduction
holds.
For let
sequence.
tl, ..., tn
H~, t I ... tn E 0 , and suppose arbitrary
reduction
sequence
sequence
starting
St, Stl, St2, ..., Hence
where
SCI(S ) .
be terms such that
SC(ti)
(1~i~n)
starting from
H
.
Now consider an
Tt I ... t n.
This will be of the form H t (k) t (k) ~a,Ttl "'" tn' H~,~ t(I)I "'" t(1) n ' "''' ~,T I "'" n ' t(k)t (k) t (k) t~k+1)t~ k+1) t (k+1) I 3 "'" n ' "''' "'" n ' "'" (Such a
k
must occur, otherwise
ti' t(1)i ' t!2)i , ... infinite reduction Now
after omission
sequence,
contradicting
tlt3..°tn~t~k)t~k)°°°t~k)
(ii) SC~t(k)t(k) I ~ " ..t(k)~ n - ° o°o t (k+1) n (iv)
,
..o
one of the sequences
would,
of repetitions, SC(t~)
, and by (I)
become an
and 2.2.15.)
SC(tlt3°..tn)
, hence by
t(k)t(k) (k+1)(k+1) 1 } "'" t(k) n ' ~I ~3 "'" sequence starting from t (k)t(k) I 3 ° t(k) n
Now
is a reduction
o.
,
and therefore terminates. SC(Z0,~,~) is proved similarly.
(v)
For
(vi)
Now we have to show that R
SC(x~) ,
see 2 . 2 . 1 5 . Ra
is strongly computable.
E (al) ... (~n)O , we have to show that
tl, ..., t n
such that
SCa (ti) ,
SCo(Rtl...tn)
I < i
Now if for
We apply a sub-induction
~.r.t. ~(t3) . (vi) a. If
v(t3) = O , a reduction
one of the following
forms
sequence ( .
~
starting from
indicating
Rt I ... t n
has
the sequence fo,fl,f2,..°):
l l
(I)