Anàlisi formalment recursiva

Pub . Mat . UAB Vol . 30 ne 2-3Des . 1986 ANALISI FORMALMENT RECURSIVA Francesc Tomás 1 . Introducci6 Aquest article és una continuaci6 de [1], treball en el qual es descriu el formalisme anomenat "aritmética formalmentrecursiva" (secci6 4 de (11), i on es fan diverses consideracions sobre la possibilitat de desenrotllar una "análisi formalment recursiva" basada en ell . Aquesta aritmética formalment recursiva és un formalisme (no un sistema formal) qué és finitáriament consistent . En el present article es desenvolupa un tros redult, peró fonamental, d'análisi formalment recursiva . Cal no confondre1'análisique desenvoluparem aquí, que és una análisi formalitzada, amb 1'análisique es presentaesquemáticament a [11, secci6 3, que és la versi6que podriem dir "informal" (o basada en la teoria de conjunts) de la mateixa . Una part del presenttreball ha estat feta en col .laboraci6 amb Edgar Becerra . Recordarem breument-la descripci6 del formalismede (11, sense~peró, repetir les demostracions (finitáries) de la consisténcia i del "metateorema de minimitzaci6" . Algunes vaguetatsque potseres presentaran podran ser aclaridesautomáticament, o bé consultant [11 . Així, doncs, recordem que la aritmética formalment recursiva és una r categoriaque té com a objectes certes sistemesformals, que anomenarem "segments" . Tots els segments tindran el mateix llenguatge i la mateixa lógica, que no será altra que el cálcul proposicional o lógica sense quantificadors (que en [1] es presenta sense usar els connectius Ai ° , peró que aquí presentarem de la manera habitual) . . Els signes del llenguatge s6n 0, S, E, M, _, els parentesis, la coma,  , V, A,  les "variables" i els "operadors" . Usarem com a variable els membres de qualsevol llista infinita de,símbols ; peró no usarem les variables d'altra manera que representades per signes auxiliars ; i aquésts signes auxiliars seran, preferiblement, si bé no exclusivament, les darreres lletres de 1'abecedari, possiblement indexades : u, v, x, y, z, x 1 , x', etc . Per cada enter positiu n tindrem una llista infinita de simbols, que seran els operadors de grau n . Convenium en que S és'un operador de grau 1 (el successor) .` Cap del símbols 0, E, M, ni cap connectiu lógic, ni cap variable, no será un operador . Els operadors es representaran per minúscules testades : a, b, f, g, f 1 , f', etc . Els termes, que ara definirém,seran representatsper minus-* cules subratllades : a, .b, a l , a', etc . Definim : 1)'0 és un terme ;'2) cada variable és un terme ; 3) si f és un operador de grau n, i si b1__b n s6n termes, áleshores f(bl, . . .lb~), Éf(b1, . . .lbn-) i Mf(b1, . . .,bn-1) s6n 1 termes (si n ' és 1, s'entén'que hem d'escriure Ef i Mi en lloc de les dues darreres expressions) ; 4) les raons anteriors s6n les soles que fan que una expressi6 sigui un terme . Entre els termes tenium, doncs, les expressions 0, S(0), S(S(0)), . . . Aquestesexpressions,s'anomenaran . numerals . Seran fórmules atómiques les expressions a=b, on a i b s6n termes . A partir de les atómiques es formen totes les fórmulesde la manera habitual, mitjangant els connectius l,  V, A, - i b . Les fórmules es representaran per A, B, A l , A', etc . El llenguatge que s'acaba de descriure será el de tots els segments . Un segment diferirá d'un altre nomás en els postulats . Les regles d'inferénciaseran : 1) cada fórmula tautólogica constant (aixó és, en la que no apareix cap variable) i cadapostulat del segment (que será sempre una fórmula constant) s6n teoremes del segment ; 2) si A i A ~ B s6n teorems d'un segment, aleshores B també és teorema del segment . Escriurem UfA per a indicar que la formula A és un teorema del segment U . Representarem els segments (encara no definits) per S, T, U, V, etc . Usarem el signe 2 en una expressi6 X = Y per a indicar que X representa Y, o que Y representa X, o bé que X i Y representen la mateixa expressi6 . Si b, c i d s6n termes i A és una fórmula, les expressions b l (c,d) i A I (c,d) representaran els resultats de substituir totes les preséncies de c per d, en b i en A, respectivament . Així, per exemple, si f és un operador de grau 2, [f(f(0,0),Ef(f(0,0)))=Mf(0)] 1(1(0,0)0) - f(0,Ef(0))=Mf(0) Els postulats inicials , donats com esquemes, i que segons veurem, seran postulats de tots els segments, s6n els seguents : E .P .I .1b=b, per cada numeral b . E .P .I . 2 lb=c, per cada dos numerals, b i c, que no siguinel mateix . E .P .I .3 b=c A d=f - d'=f', sempreque b, c, d, f,  siguin termes i que la fórmula d'=f' s'obtingui de d=f en substituir una preséncia de c per b . Aquests postulats contenen les propietats de la igualtat . Podem notar, pero, que comí que f(b1, . . . .lb ) no está .presenten Ef(b , . . .,b  ), 1'esquema E .P .I .3 po ens permetdeduir  U .r--Ef(b l   bn-1)=Eg(b1, . . .,bn-1) del fet que U f-f(b1, . . .,bn)=g(b1_ . .,b .) per cada b n . Aixó és, E no és un operador en un sentit .que .ens agradaria que,ho fós . Tal com es fa notar a [1, secci6 4 .3], el demanar que ho fós ens impediria, probablement, el poder demostrarfinitáriamente la consisténcia del formalisme . Abans d'exposar els "principia" que ens diranquins sistemes formals seran els segments del formalisme hem d'ampliar un xic la nostra terminologia . Per un segment . U i un terme b, direm que -b és un Unombre , i escriurem b E N-,  si per algun natural r podem trobar r numerals, c 1   cr ,  per ala quals  poguem demostrar que f~(xi .bi) EN U (on, naturalment,  fl(x i ,b i ) . - fj(x 1 ,b 1 )1 . . .1 (xn,bn))- . .  . Si b és un numeral i c un terme, SI(c)representará un terme, d'acord amb la convenció U sb=c 1 . V .  . V b=c r , Direm també que un terme f és U-funci6 de les variables x 1 , . . .,xn , i escriuremaleshores  f E N-(X 1 , . . .,x n ),  si per cada col .lecci6 de nume- , rals b 1 , . . .,b n . tenim que  , 50 (c)  E c, SS ( 0)(c )  E S(c),  SS(S(0))(c)  --_ S(S(c)),  etc bonat un segment U, direm que 1'operador f és nou per U si f no apareix en cap postulat de U que no sigui un cas de E .P .I .3 . Recordem ara els,principis PR . 1, 2, 3 i 4 que defineixenrecursivament els segments . PR .1 . El sistema formal que té el llenguatge i la .lógica que s'acaben de descriure i que té, com a únicspostulats, els postulats inicials (els casos de E .P .I . 1, 2 i 3) és un segment , el segmentinicial , representant per I . _ PR . 2 . Si : 1) U és un segment in un enter no negatiu ; . 2) r E N-(x l x n )  i  s E Nú (xl  . .,%C11, y, Z) ;  3)  f  és un operador nou per U ; aleshores també és un s~ent el sistema formal que s'obté d'afegir als postulats de U els següents esquemes de postulats, (1)-(VII), per tots els numerals  b 1' . . . . b n , c, d : (Z)  ri(x , , b,) =  f(b1, . . .,bn ,0)=d -  ~ (II)  s 1 (xi ,b i WY,c)PZ,f(b a . . .,bn,c))=d =" f(b1, . .  bn.S(c))=d (122) 0  f(b1, . . .,bn,0)=0 ='> Mf(bl, . . .,bn)=0 (III)'  lf(b 1 , . . . . bn ,0)=0 A  . . .  A lf(b 1 ,.... b n ,c)=0 A f(b 1 " " ,bn .S(c))=0 1 Mf(bl, . . .,bn)=S(c) (IV)  . f(bl, . . .,bn .c)=0 - Ef(bl, . . .,bn)=S(0) (V)  ' Ef(b1' . . .,bn)=0 V Ef(b,' . . .,bn)=S(0) (VI)  Mf(b,, . . .lbn)=c - f(b1, . . .lbn,c)=0 (VII)  SS(c)(d)=Mf(bl, . . .,bn) " .lf(bbn,d)=0 PR .3 . Si : 1) les condicions 1), 2) i 3) de PR .2 es satisfan i V és el segment que s'obté d'afegir a U els esquemes (I)-(VII) com a nous postulats ; 2) h 1 -  h p , k t ,. . . . k p , 5t " " ,g n són U-funcions de z t , . . .,z q ; 3) podem demostrar, per qualssevol numerals dt, . . . .,dq,c, que V  ( h =kt  A  . . . A  h =k  )  (z i Po -p  di )  - If(g t (z i ,d i ) , . . .,g n 1 (z i ,d i ) ,c)=0 ; -  -  - - aleshores també és un segment el sistema fonnal que s'obté en afegir a V el segment esquema de postulats, per qualssevol numerals d t , . . . d , b 1 , , . . . . b n : (VIII)  (h, =l,  A . . . A  h =k  A  g =b  A  . . .  A  q =b  )I(z .,d .) -  - p - P  t - t  n -n  1 -1 (es permet el cas p '-_ 0) Direm que el segment  W  és extensió del  V,  i escriurem  V -< W,  si tots els postulats de V són postulats de W . Metateoremad'inducció .  Si  U¡-- Al(x i .,bi ,)  per qualsevol col .lecció - - de numerals  b l , .... b ,  aleshores  U F-Aj(x .,b,)  sempreque  b . E N-  per -  -n  -  i -i  -i  U i = 1, . n . aleshores també tenim _lEf(bt, . . .,bn )=S(0) -- PR . n . Res no és un segment si no és per les raons anteriors . No necessitaremrecordarqué són els morfismes . Es indispensable recordar també dos metateoremes . La demostració d'aquest metateorema és trivial . Metateorema de minimització .  Si tenim UfE!(bt, . . .,bm)=S(0), Mh(bt, . . .,b-m) E Nú i U F-h(bt, . . .lbm,Nht(bt, . . .,bm)=0 . Corol .lari .  Si  5 >- Eh(bt, ... .bm)=S( 0)  per cada col .lecció de nume- rals b l ,.. .~b -m' aleshores  Mh(x 1' . . . . x m ) E NG(x l,  . . .x m ) . La demostraci6 d'aquestmetateorema es fa a [1], lligada amb la demos traci6de la consisténcia . En la demostraci6 es d6na la manera, si U t--Eh(b,, . ... b_)=S(01,  de trobar, efectivament, certs numerals, c l , . ... l t ,  per ale quals es pot demostrarque U FMh(bl, . . .,bn)=c1 V . . . V Mh(bl, . . .,bn)=ct Les propietats més importante del formalisme s6n : 1)  Donades funcions  r  i  s,  de  x l , .... x n ,  i de  x l,.. .,x n ,y,z, - - respectivament, podem introduir la funci6 f(xl, . . .,xn .y) definida per recursi6 primitiva a partir de  r i s .  Aixo és, si  r E N-(x,, . . .,x n )  i s E Nu-(xl, . . . . x n .y,z),  i si escollim  f  nou per  U,  aleshores en el seg ment V obtingut de U afegint ele postulats (I)-(VII) de PR .2 podem demostrar que  f(x 1 - .-x n .y) E NV(xl, . . .,xn .y)  i que, per qualssevol numerals  bl, . . .lb n ,c, - V  Ff(bl, . . .lbn ,0)=ri(x i .,b,) -  -i V 1--f(b1, . . .,bn,S(c))=sl(xi .b .)1(y .c)1(z,f(b1, ... .~~g)) 2)  Donadauna funci6  t de  x 1' . . . . x n podem, per PR .2, canviar la notaci6 de t a una notaci6 funcional . Aixó és, si t E N~(xl, . . .,xn) podem prendre, en PR .2, n-1 en lloc de n, r = t l (x n ,0), s = tl(xn .S(y)) i aleshores, afegint a U ele correspondents postulats (I)-(VII), amb algun operador f nou per U, tindrem,en el nou segment V, ti - V F--f(bl, . . .,b )=tl(xi,b,), per qualssevolnumerals b . . Al mateix temps -- -n -1 tindrem  Ef(x l ,- : . .,x  ) E N-(x, . . .,x  ) . n-1  U - 1 - _  n-1 3)  Si  u E NV(x l,. . . . x m )  i  v3 E NV(yl, . . . . Yn )  per  i=  1, . . .,n, aleshores  ul(x i , v~) E % (y,, . . . . y n ).  Aixó és, la composici6 de funcions d'un segment es funci6 en el segment . 4)  Per qualsevol numeral  c  i qualsevol  U,  c E N~(x,- .-x n ) . També tenim  xi E Nu(xi, . . . . x n),  per  i = 1, . . .,n,  i  S(x) E Nu (x) . Aixó, junt amb lo observat a 1), 2) i 3), i amb el metateorema de minimitzaci6, mostra que podem introduir totes les funcions recursives que es vagin necessitant . 5)  El que tenim, en el nostre formalisme, a més de 1'aritmética recursiva, és la possibilitat d'introduir la funci6  Eh(x,, . . . . x m_1 )  associa da a h(xl, . . .,xm) en la qual, pero, com ja s'ha indicat, E no funciona ben bé com un operador . Aprofitem la ocasi6 per senyalar certes inexactituds o errades de [1] : a) En la condici6 CL .3 (pag . 64) hi manca : si c és un numeral present en alguna fórmula de A que no sigui un cas de E .P .I . 3, aleshores c=c pertany a A . b) Des del rengle 20 de la página 72, on diu "Aixó implica . . .", fins al rengle 23 de la mateixapágina, on diu " . . . .Un U, 4 .1 -nombre", tot s'ha de suprimir, i en el seu lloc s'hi ha de posar el segment : "Suposem, per cada j, que c,_ és el primer numeral amb aquesta propietat, i sigui c' el més gran de tots el c . . Fem ara una hipótesi addicionAl, que després eliminarem : suposem que, per els nostres b l,.. .,bn , el cas corresponent de (III)0,i+1 i tots els casos de (III)i +1 per tots els c que s6n anteriors a c' pertanyen a A i, en consequéncia, a" B i a B  Aleshores considerem ; per cada j, el cas de (III)' i+li+l  , si c : = 0, i si no el cas de (III)i +l corresponent a S(c) =c j , i aleshores tindrem 42 G .(Mf( b ,.. .,bn)=cj) = V per cada j, i aixó implica, per cada G compatible amb Bi+t, G(Mf(bt, . . . . bn )=c t V . . . V Mf(b t , . . . . b n)=cw)  = ;Ji aixó mostra que Mf(bt, . . .,b) hipótesi addicional : si els casos (III)í +t no pertanyen aA, per alguna B' finita closa . que c' no s'incrementa ; peró cada valoració Bi+t-normal és valoració Bi+t-normal de les j anteriors ." immediates . El que aixó compatible amb G' tindrem c)  En la página 75, formula (5), ha de ser Úi+t~1Aj (k)  V  . . .  V 1A~j (k)  . . . en lloc de 2 . L' argot técnic . El segment básic que és un U, . . 1 -nombre . Tornem ara a la que hem considerat de (III)  i O,i+t aleshores li els adjuntem necessitem i tornem a comengar, comprovarés, unicament, és una consequéncia de b  perqué t B i+,t .  Aixó és, per cada G'(f(b  ,.. .,b  cJ .)=0)  = V  per alguna . t  - n - U i+t r1A k V . . .V Ap  . . Desenvolupar 1'análisi matemática en base al . formalisme vol dir, vagament, usar el formalisme de qualsevolmanera finitária o constructiva per a fer el tal desenvolupament . Per un procés d'aproximació, assajant de desenvolupar un mínim d'análisiamb un minim d'elegáncia i simplicitat, s'ha arribat a el que anomenarem un "argottécnic", que ara descriurém . No afirmem que aquest argot ens permeti fer totes les manipulacions finitáries possiblesdel formalisme ; peró és adequat per les nostresfinalitats Per comengar, necessitarem alguns símobls nous, els "pseudooperadors" . Per cada enter positiu n hem de tenir una llista infinita de símbols, els pseudooperadors de grau n . Representem els pseudooperadors per els mateixos símbols que usem per a representar operadors :  a, b, f, f t , etc . Trencarem, no una convenció, peró un hábit : en lloc de representar convencions del tipus X - Y, que indiquen que X representa Y, o Y representa X, o bé que X i Y representen el mateix . En aquestes convencions X i Y poden ser termes, fórmules,_neotermes, neofórmules, formes o qualsevol expressión auxiliar que ene convingui, inclas expressions del llenguatge ordinari . Aixi, per exemple, podem conveniren que 3 . Els nombres reals (si A, aleshores E) - (A implica B) - (A k B) o bé, si suprimim ele paréntesis, que no són necessaris, si A, aleshores B - A implica B - A kB El desenvolupament que farem de 1'análisi está inspirat en 1'exposicib de 1'análisirecursiva deguda a Goodstein [3] . Com se sap, 1'análisi recursiva té molt serioses limitacions, tals com el fet que en ella hi ha successions creixents i afitades que no són de Cauchy (recursivament parlant) (veure, per exemple, [4]) . Aquests fenómens tan inconveniente ja no es donen en análisi formalment recursiva . Així, doncs, aquesta última es una análisi mes poderosa que 1' .análisi recursiva, que ja no és constructiva peró que, en cánvi, és finitáriament consistent . Introduiremexpressions sp'(x),(P(y), 41(x), etc, on x,y representen variables, per representarexpressions de la mena f-g/h, on f, g i h són neotermes . Si posem convenim, per qualsevol neoterme t, en que IP (x)  =  f -9/h 'p(t) _ (fl (x,t))-(gl (x,t))/(hl (x,t)), on el'significat de fl(x,t), etc  .ás-el,mateix per .negtermes que per termes (el resultat de substituir x pert en f) . Es clar que el cas interessant és quan en f, g, h no apareixen altresvariablesque x . Suposarem que aquest és el cas . Eventualment suprimirem la x i només escriurem (P . També posem -En particular, 3 .1  Definicié .  W  és un real  =  -P E R  -  -P (x) E R(x)  -  SP(x) E Q' (x)  & (3 m)[m(x)  EN (x)  &  (Vn,r)[ I~p(M(n)+r)-~p(m(n))  <1/n]] . Si la forma representada per 9 E Rés closa, que és el cas que es dóna si en 9(x) no apareix altra variable que x, tenim, d'acord amb V .1-6, que V : WE R si aixó és, si Ara tenim 1 = S(0), 2 - S(S(0)), 3 - S(S(S(0))), etc m/n = m-0/n 1/n = 1-0/n = S(0)-0/n m/1 - m-0/1 - m-0/S .(0) 1/1 - 1-0/1 V : w (x)  E Q' (x) v : (3m)[m(x) E N(x) & (Vn,r)[ ISp(m(n)+r)-s?(m(n)) 1 <1/n]] , (*1  f E Nv(x) & g E Nv(x) & h E Nv(x) i, per algun operador que ara denotarem per m podem demostrar que (**) v F-1~P(m(n)+r)-+p(m(n))I <1/n per tots els numerals n i r . 3 .2  Lema .  Per qualsevol termes  f, g i h,  i si  W (x)  = f-9-/lh, W (x)  E R (x)  k  (3m,n) (Vr) [ 19 (n+r) 1 <m/1] Per demostrar el lema hem de considerar qualsevol segment V extensie de  B  i suposar que  V :9 (x) E R(x) ;  és a dir, que es satisfan Aleshores d'on, per una propietat del valor absolut (que suposem demostrada), Ion, ara, V i .-19(1(1)+r)-+p(m(1)) 1 <1/1  per tots el numerals V 1IW (m(1)+r)j<1-P(m(1)I+1/1,  per tots el numerals  r . Tenim, per certs a i b, que  jW (m(1))_I  = a-0/b,  i llavors V 1-- 19 (m (1) +r) I < (a+1) /1  per tots els numerals  r, de manera que, d'acord amb V .S i V .6, m,r . i r V : (3m,n) (Vr)[ I'P(n+r) I <m/1] r, representen variables/' , 1 aiXu és el que s'havia de demostrar, segons V .4 (on el W de V .4 és el mateix V) . 3 .3  Proposició .  Si  " P 1 (x)  = f l -9 l /h l i, 9 2 (x) = f 2 -9 2 /h~, on els f 1 , h i sen termes qualssevol (sense altres variablesque  aleshores (P1 E R & `p2 E R)  V-  (SP1+9 2ER & wl .'P2 ER &-W1 E R) Demostrarem, per cada V,  que V : (91 E R & % P2 E R) kSp j SP z E R . Supqsem que V :(P 1 E R& SP2 E R .  D'acord amb la definicie anterior i la demostració del lema tenim, per uns certs m l , m 2 , n l , n 2 , m l i m 2 , afegirn una observació trivial : demostrem W : V :  (Vn,r)[  sP1 (m l (n) +r) -91 (m l (n))  < 1/n1 V :  (Vn,r)[ ¡TI (m 2 (n)+r)-'P2 (m2 (n)) 1 < 1/n1 V : V : (Vr)[ I'P 1 (p . +r) I <M,/1 (Vr)[ I,P2 (n s +r)  < m2 /1 1 Ara adjuntem a V alguns postulats, d'acord amb PR .2, que garanteixin, per el segment W així obtingut, i un cert operador m, que w :  (ds)[ m(s)=m 1 (4m 1 s)+m 2 (4ín 2 s)+n1+n2 com que les quatre afirmacions anteriors continuen essent certes a W, tindrem, usant el principi d'inducció, (Vn,r)[ I~1 (m (n)+r)-P, (m(n))  <1/2m,n1 w : w :  (Vn,r)[ IsP 2 (m (n)+r) - -9 2 (m(n))  < 1/2m, W :  (Vn,r)[ 191 (m (n) +r) I < m l /11 w :  (Vn,r)[ I(P2 (m(n)+r) 1 <m2/11 . (Vn,r)[ i~P1(m(n)+r)%PZ(m(n)+r)-AP(m()bPZ(m(n)) 5 I~1 (m(n)+r)  (m (n) +r) -4PZ (m(n))  +I~2 (m(n))  " IsP1 (m (n)+r)-fP, (m (n) ) W :  (Vn,r)[ 19, (m(n)+r)SP Z (m(n)+r-O l (m(n)9 Z (m(n))  < 1/n1 Aixó últim vol dir, si ara m representa un pseudooperador, i si w :<3m)[ m(x)EN(x)  s  (Vn,r)[ 191 (m(n)+r)'P2 (m(n)+r)  P1(m(n) )~P Z (m(n))  < 1/n11 De manera que, d'acórd amb V .4, haurem demostrat la proposicib si 1 :  -P, (x) w 2 (x)  E 4' (x) Per! aixl, com abans la demostraci6 de que m(x) E N-(x),  és trivial W- (només cal demostrar que, en general,si a E NU i b EN - ,  aleshores a+b E N5 i ab E NE) . 3 .4 . Definici6 .  SP . .0 - 9(x) - 0 3 .5 . Definici6 . (3 m)(m(x)  E N (x)  &  (dn,E)[ ~SP(M(n)+r) 1 < 1/n 11 W 'és equivalent a  ~ - 9 -~ - w(x)- q(x) = Ip(x)-0(x) -0 . Suposarem, per expressions  W (x), 'P(x), etc,  de la forma  f - 9/h,  i quan aixi ho indiqui el context, que f, 9 i h son termes (no neotermes qualssevol) en els quals no aparegui altra variable que x . 3 .6 .  Proposici6 .  Per qualssevol  9, 0, ip l . ; p2 , ~l' 'P 2' X ' 1) :NER kfp-~p 2) ;(IQEP & IPER&~p 3) ;«PER& ;P ER&XER&-p&xksp-X 4)  ;(91  E R & SP2  E  R &  01  E  R  & ;k 2 ER & wl  . . w2  &  01 (W 1 + wl  9 2 + I%/ 2 & ip l ~ 19 2 0 2 & -SPI- -Sp2) 5) Les lleis formals de la suma i el producte , 3 .7 .  Definici6 .  Per  14(x)  = r- (x) - s(x)/t(x),  on  r, s i t  s6n pseudoperadors de grau 1, posem (») com abreviatura de (3r, s, t) . Alesho res definim 9(x) ' és invertible  =  (3~G)[  ER & -P (x) " 0 (x) - 1/1] 3 .8 . Pr oposici 6 . Recordem la definici6 de f P - ' . Aleshores, per cada (1P E R & SP -1 E R) b (IP és invertible  & Vo -1 - 1/1) 3 .9 . Nota . No tenim una dicotomia que afirmique cada real hagi de ser invertible o equivalent a zero . Al respecte es pot veure la observaci6 3 .13, més endavant . 3 .10 .  Definici6 .  W  és no negatiu  = fp ;b 0 = 0 sis (p 3 .12 . Definici6 . =  (3m)[m(x) E N (x)  &  (Vn,r)[0/1 < ;p(m(n)+r)+1/n]1 3 .11 .  Definici6 .  sp  és negatiu  = Ip Z . 0 = 0 A Ip (3m,n) (Vs)[m(s) EN & 0/1 > (P(S+m(S))+1/n], SP 4 0 = 0á (P = 0--' 44-W ,p z 0 = 0 a ~p = -P-0 .c 0 3.13 . Observaci6 sobre la tricotomia . No tenim una tricotomia de 1'estil "si 9  és un real,  SP < 0,  ~P -.. 0  6  SP a 0"  ni dicotomies "si #p  és real,  cP X 0  6  Wa 0"  o "si  oP  és real,  ,p . ?A 0  6  ;p ti 0" .  Tenim, perb, succedanisd'aquestes afirmacions . Un exemple, que no usarem, és : Proposici6 . Per cada 'P E R A (3S)[ (S=0 . V s=1) & (s=1 kI0 4 O) & ú0 4 0 1= s=1) &  (s=0 k IP á 0)  &  (o ,, 0 1= s=0) ] La demostraci6 és com segueix : Suposem que V :~p E R,  on  = f-g/h,  f E NV(x),  g E N-(x), h E NV(x) .  Considerem l'expressi6 0/1 <W(Y+z)+1/x y recordem que, segons les definicions de la secci6 2, aquesta expressi6 no és res més que la representaci6 d'unacerta fórmula k=0, on k E NV(x, y,'z) .  Aixó és, 0/1 <IP(y+z)+1/x = k=0 i, per qualssevól termes a, b, c, ' un cert f2 , 56 D'acord amb PR .2, podem obtenir una extensió V 1 de V en la que, per alg6noperador f l tinguem V 1 : OX,y,Z)[f l (x,y,z)=1sk] V 1 : (VX,y)[,Ef,l(x,y) E N & (Efl(x,y)=0 cert f 3 , En una certa extensió  V L de  V 1 tindrem, de la mate¡ xa manera, per De la mateixa manera, en una certa extensió V 3 de V 2 i per un V 3 :  (Vx)[ f 3 (x)=Ef 2 1x V 3 : Ef 3 EN & (Ef 3 =0 V Ef 3 =1) Fem Tenim  V 3 1-- s=0 V s=1 . Hem de demostrar ara 1)  V 3 : s=1 k tp z_ 0 2)  V 3 : s=0 k w -? 0 3) " V 3 z 0 k s=1 4)  V3 : 9 á 0 k s=0 0/1 <9 (b+c)+1/a E k'I(x,a)I(y,b) J (z,c)=0  ' V 2 :  (Vx,y)[f2(x,y)=Ef l (XM ] V 2 :  (Vx) , [ Ef e (x) E N&(Ef 2 (x)=0 V Ef e (x)=1)] s = Ef Suposem que  V 3 I--s=1 .  Aixb vol dir que  V 3 FEf 3 =1, i que, per tant, segons els metateorema de minimitzaci6, V Efl(x,y)=1)] V 3 : Mf 3 E N,  i  V 3 Ff 3 (Mf 3 )=0,  d'on V 3 F-Ef 2 (Mf 3 )=0, que implica, per el postulat (IV) de PR .2 relatiu a f 2 , que i, en consequéncia, (VY)[1f 2 (Mf 3 ,Y)=0 ] V 3 :  (Vy)[ - lEf l (mi3'E) =0 1 V3 :  (VY) [Ef 1 (Mf 3 ,Y) = 11 i, per el metateorema de minimització, V 3 :  (VY)[Mf l (Mf3,Y) E N & f(Mf3 .y, Mfl(Mil ,y))=01 . V 3 : (Vy)1MI 1 (Mf 3 ,Y) EN & -'k1 (x,Mf 3 )1(z,Mf l (Mf 3 ,y))=01 V 3 : (Vy)(Mf l (Mf 3 *y) EN 5 0/1 > ip(y+Mfl(Mf3,Y))+1/Mf3] Fem, per alguna extensió V 4 de V 3 , que V 4 : (Vy)[m(Y_)=Mf1(Mf3 .Y)] . i fem també  n = mi 2*  Hem demostratque V 4 :  (3 m,n) (Vy)[m(y)  E N & 0/1  > 50 (y+m (y))+1/n] , aixó és, que  V 3 :9 '< 0 ;  i aixó demostra (1) . Suposem ara que  V3 1q=0 .  Aixó vol dir que  V 3 F-Ef 3 =0  i que, segons el postulat (IV) per f3, V3 :(Vic)[1f3(-X)=01, d'on V 3 : (Vx)[Ef 2 (x)=11  i, per el metateorema de minimització, V 3 :  (Vx)[Mf 2 (x) E N & f2(x,Mf2(x))=01 V 3 :  (Vx)[Mf 2 (x) E N & Efl(x,Mf2(x))=01 V 3 :  (VX,Z)[Mf 2 (x) E N & 1f 1 (x, Mf 2 (x)=z)=01 . . V 3:  (Vx,z)[ Mf 2 IXL E N & kl (V,Mf 2 (x)) = 01 V 3 :  (VX,z)[Mf 2 (x) EN & 0/1 <W (Mf2(x)+z)+1/x] Si fem,, en algun V4 extensió de V 3 , que, per un cert m, haurem demostrat que Vy :sP á 0 ; 'i aixó demostra (2) . una certa m(t) E NV (t), tenim 3 . . aixo es, Suposem araque  V 3 : (p o-' 0,  que vol din que per un cert tenme  n  i V 3 F -f 1 (n, t, m(t))=0  per cada numeral  t,  d'on, per (IV), (A)  V 3 F - - )f 2 (n,t)=0  per cada numeral  t En aquestmoment tenim un pas delicat,en el que afirmem que d'aquesta afirmaci6 (A) podem concloure que (B)  V2 F1f 2 (n,t)=0 per cada numeral  t Per no perdre el fil de la demostraci6deixarem la justificaci6 del pas de (A) a (B) per una mica més endavant . Vy :  (Vx)( M - (X) (x)] , V 3 : (dt)[ 0/1 > 9(t+m(t) )+1/n], V 3 F - Ef l (n,t)=1 per cada numeral t Tenim ara, de (B), per PR .3, un segment VZ extensi6 de V Z que V 2 d'aquest en afegir el postulat 1 Ef 2 (n)=1 .  Es adir que tenim V2 - Ef2(n)=0 Recordem ara que hem passat de V Z a V 3 afegint uns postulats (I)-(VII), d'acord amb PR .2, que e :is han permésintroduiruna nova notaci6, f 3 (x), "  per  Ef 2 (x) .  Observem que PR .2 permetafegir exactament,els mateixos postul a" a V2,  obtenint aixi un riou segment . VZ  que és, al mateix temps, extensi6 de VZ i de V 3 , i en el qual tenim V ., , Ff 3 (n) =E f 2 (n) Per tant, i,  per  (IV)  (relatiu a  13), VZ rf 3 (n)=0 i, como que ja hem observat que V" ~- V 3 , aixódemostra (3), excepte per que ens faltaveure com podem passar de  (A) a .(B), que'és el que ara farem . Observem,per comengar, que, com que f 2 (x,y) només pot prendre els valors 0 i 1, (A) i (B) equivalen a (A')  V3 Ff 2 (n,t)=1  per cada numeral  t (B')  V2 Ff 2 (n,t)=1  per cada numeral t Considerem qualsevol numeral t . Segons (A'), f 2 (n,t)=1 és un teorema en V 3 , i volem demostrar que també ho és en V 2 . Suposem que C és una col .lecció finita de postulats de V 3 tal que C tf 2 (n, t)=1 Sigui C' el conjunt de membres de C que també sónpostulats de V 2 . Si suposem que f 2 (n,t)=1 no és teorema de V 2 hi ha d'haver una valoraciólógicaque sigui compatible amb C' i no amb aquesta formula . Podem modificar aquesta valoració fent que valgui F (fals) en qualsevol fórmula atómica a=b que no aparegui en cap membre de C', i aquesta va ti loració, que denotarem G, continaurá essent compatible amb C' i no amb f 2 (n,t)=1 . Veurem ara que G es pot "estendre" a una valoració G' compatible amb C i no amb f 2 (n,t)=1, cosa que dóna una contradicció, ja que C F- .f2(n,t)=1 . Que G' sigui "extensió" de G voldrádin que G'(a=b) = V (veritat) sempre que G(a=b) = V . Aquesta G' es pot (20')  V S :  (Vn,m)[rl-sl/tl)+((Mh(n)=1)/2a)'((r2-s2 /t2)-(r1-sl/tl)) < IP(m+Mf(n,Mh(n)=1,m))1 Si prenem Mf(n,ME(n)=1,Mg(n,Mh(n)))+n per r i Mg(n,Mh(n))+n per m tindrem (21) V 5 : (Vn)[ (E,-sl/tl}t((Mh(n)=1)/2n~°((r2-s1/tz)-(Ey-II/t-l)) <SP(n+Ml(n,Mh(n))+Mf(n,MFi(n)=1, Mg(n,Mh(n))))1 (22)  V S :  (Vn)[W (n+Mg(n,Mh(n))+Mf(n,Mh(n)s1,Mg(n,Mh(n)))) /ti)+(Mh(n)/2"I .((r2-s2/~)-(1-sl/t,))1 Tenim, en alguna extensi6 V 6 de V 5 , i per algun k, (23) V 6 : (Vn)[k(n)=n+Mg(n,Mh(n))+Mf(n,Mh(n)=1,Mg(n,--Mh(n)))1 així que, si fem Ara afirmem que a=r l -s l /t l , R=r 2 -s 2 /t 2 , (24)  V . :  (Vn)[ a+((Mh(n) =1) /2a) ° ($-a)  < W (k (n) ) &~p(k(n) Sa+(ME(n)/2n) " (R-a)1 (25) V 6 : (Vn)[ (Mh(n)=1)/2L< (Mh(n+1)_1)/21+11 (aixó és,  (Vn)[ 2Mh(n)_2 5 Mh(n+1)=11 ) tindrem, per (21) i (22), En efecte, observem que  V 6 : (Vn)[ (2Mh(n)=2)/21+1=(ME(n)=1)/2' ]  i tenim, per (20') i (1), (26)  V~ :  (Vn,m)[f(n+1,2t4i(n)=2,m,Mf(n,Mh(n)=1, m))=01 Per'o' de (14), per n+1 en lloc de n, (27)  V 6 :  (Vn,r)[ 1f(n+1),Mh(n+1),M9(n+1,Mh(n+1)),r= 01 Per Mg(n+1),Mh(n+1))  en' lloc de m en (26) i Mf(n,Mi(n)= 1 .,Mg(n+1,Mh(n+1))) en lloc de r en (27) tenim així que que demostra (25) . d'on També afirmem que V 6 : (Vn)[ f(n+1,2Mh(n)-*2,Mg(n+l,MFi(n+l)), Mf(n,Mh(n)=1,Mg(n+l,Mh(n+1))))=0] V 6 : (Vn)[-lf(n+1 ,Mh(n+1) ,Mg(n+l ,Mh(n+1)) , Mf(n,Mh(n)-1,Mg(n+1,Mh(n+1))))=0], V 6 : (Vn)[Mh(n+1) > 2Mh(n)=2], V 6 : (Vn)[ Mh(n+1)=1 > 2Mh(n)=2], (28)  V 6 : (Vn)[ Mh(n+1/2 n+1 < Mh(n)/2n] (aixo és,  V 6 : (Vn)[ Mh(n+1) < 2Mh(n)]) . En efecte, tenim de (14), amb un petit ábús de notación, v s : (Vn,r)[2Mh(n)/2 n±1 =Lvh(n)/2 n >,p(Mg(n,Mh(n))+r)] (29) V 6 : (Vn,r)[1f(n+1,2Mh(n),i-1g(n,Mh(n)),r)=0] Pero d'acord amb (20), per n+1 en lloc de n, (30) V 6 : (Vn,m)[f(n+1,Mh(n+1)-1,m,Mf(n+1,Mh(n+1)=1,m))=0] així que Si prenem, a (29) i a (30), i Mg(n,Mh(n)) per m, tenim Mf(n+l,Mh(n+1)=1,Mg(n,Mh(n))) per r V . :  (Vn)[ - lf (n+1 ,2Mh(n) ,Mg(n,Mh(n)) , Mf(n+1,Mh(n+1)=1,Mg(n,Mh(n))))=0] , V 6 : (Vn)(f(n+1,Mh(n+1)-1,Mg(n,Mh(n)), Mf(n+1,Mh(n+l)=1,Mg(n,Mh(n))))=0], V 6 :  (Vn)[ 2Mh(n)  > Mh(n+1) _1 ] V 6 :  (Vn)[ 2Mh (n)  > Mh (n+1) ] ,  (per  (15)) , que demostra (28) . un  r (x)  i un  q  tal que De (25) i (28) tenim, amb algun abis de notaci6, (31)  V 6 :  (V n)[ (F4i(n)-1)/2 11 < (Mh(n+1)_1)/2n±i < Mh(n+1)/2 n+1 IQ Mh(n)/2 n ] Finalment, és fácilveure que existeix, en alguna extensi6 W de v 6 , W : (Vn)[q(n)=k(r(n))] i q(x) és estrictament creixent . I aleshores de (24) i (31) demostrem fácilment que -P(q(x)) és un real, en alguna extensi6 de w, que és el que haviem de demostrar . 5 . Funcions 5 .1 Definici6 . Fem que (f-g/h) j (x-y/z, x' - X_'/z') representi el resultat de posar x' ;y' i z' en lloc de x, y 1 - 1 z, respectivament, a f-g/h . Definim f-g/h, per neotermes f, g, h en els quals no apareixenaltresvariables que x, y, z . En les proposicions frequentment suposarem tácitament que f, 9 i h  s6n termes, depenent del context .  Fem convencions tals com : Si l=x-y/z,a= a-b/c i (D (x-y/z) f-g/h, aleshores f-g/h E Q(x-y/z) = f E N(x,y,Z) &gE N(x,y,z) & h E N(x,y,z) & (Vx,y,Z)[1h=0] &  (VX,y,z,x'y',Z')[ 1Z=O AIZ'=0 A X-y/Z=X'- y '/Z' f-g/h=(f-g^)PX-y/Z,x'-y'/z')1 Usarem expressions de la mena O(x-y/z) per representarexpressions I (a)  = 0(a-b/c)  =  (f -g - /!!) 1 (E, a) venir en que m(a,d) = m(a,b, c,d), si a = a-b/c . També, en aquest cas, posarem Usarem abreviatures tals cqm posar  (Va)  en lloc de (Va,b,c) denom a =c 5 .2 Definici6 . Sigui l= x-Y-/z . Definim (C) és uniformement contínua en conjunts afitats '-_ $(1) E Q C (E) $(1) E Q(1) & (3m)1m(a,B,n) E N(a,0,n) & (Va,B,Y,6,n)( - ldenoma =0n - IdenomO=0 nldenomy=O A ldenom6=0 n a < Y n Y<0 n a < 6 n 6<0 n ¡Y-61 < 1/m(a,B,n) ~~(Y)< 1/n J1 5 .3  Observaci6 .  Cada element de  Q C (E),  que associa a cada  a E Q  un element I(a) E 0 pot ser "estés per continuitat" als reals . Més precisament . 5 .4 Proposicib . Per qualssevol ID,9,X peradors), (en els que no apareixen pseudoo- $(1) E Q C (E)  & 9(v) E R (v)  & X (v)  E  R (v)  & 9 X b (D (TM )  E  R (v)  & $ (X (v) )  E  R (v)  &  <D (X (v) )  $ (IP (v) ) 5 .5 Nota . Definirem les funcions continues en un intérval clos com les successions fonamentals (relatives a 1'int ¬ rval) d'elements de Q C , de la mateixa manera com hem definit els reals, a 3 .1, com successions fonamenta15 de racionals . Usarem notacions tals com per qualsevol a-a-b/c i neotermes ~(w,C) = ~( w,x-y/z) = per, ~ n (a) = 0(n,a) =  (w,n) 1 (1,a) . n, a, b, c . o con- 5 .6 Definici6 . *(w,C)  és una successi6 d'elements de Q C (1) _ (Hm)[*m(C) E Q(1)] & (3m)[ m(k,ot,s,n) E N(k,a,s,n) & (tlk,(x,B,Y,6,n)[ ldenoma=0 A ldenoms=0 A ldenomy=O A ldenom6=0 A a < Y A Y  B Aa < 6 A6 < B A ~Y-6~ < 1/m(k,a,s,n) 14'k(Y)-*k(5) 1 < 1/P ] 5 .7 Definici6 . Sigui I =['P,X] . Aleshores definim VW,C)  és una funci6 continua en  I= O¿(w,E) EC I (1) E R & XER & 0(w,E)  és una successi6 d'elements de Q C (E) & (3 ;P',X',m)['p' E R &  X' E R &  (p'-9 & X '~X & m (x) E N (x) & (an)['P' (n) G 'P' (n+1) & X' (n) < X' (n+1)]  & (lfn,r,a,b,c)[1c=0 AIp'(m(n)+r) < a-b/c A a-b/e < X'(m(n)+r) on el significat de (39') és com fp'(x)  = r' (x)-s'(x)/t'(x),  - per un certs pseudooperadors  r',s',t',  i llavors (3'0') significa (3r', s',  Análogament per X' . Nota .  Una part de la definici6 és  (Vn) [ W' (n) 6 W' (n+1) ] ,  que significa (o esta representat per)  "V' és monótona no decreixent" . També tenim, és clar, 5 .8 Observacions . b 10 dí (n)+r (a-b/c)-Dm(n)(a-b/c)j  < 1/n]], segueix : suposem que 1'  és monótona no creixent  = (1Fn)[ ;P'(n) > 41' (n+1)]] a) Análogament al que ha estat fet a 3 .4 i 3 .5, podem definir la noci6 (Du(1)  _0  i la noci6  (P u (E)  - . ú(1),  per  (D u  i  ú  en  CI ,  i demostrar que aquesta és una relaci6 d'equivaléncia b) Podemveure cada element de C I com a "funci6 de I en R" . Donat 'P E R  tal que 'k G 9 - X,  i donat  $u E C I ,  si  e  és un real al qual convergeix  (D u (sP(x)),  podem definir  e  com el valor de  (D u  en  W .  És clar que aquest valor e només está definit módulo equivaléncia . Si, en un segment  V,  tenim que . V : <D u (C) E CI (1)  i  V :W (x) E R(x), representarem, amb notaci6 ambigua, per 1('P) aquest valor de 1 en 'P, que acabem de definir, móduloequivaléncia . Quan fem alguna afirmaci6, en el segment V, relativa a sevol dels reals representats per 1(9) un real particular segurs que la mateixa afirmaci6 es compleix per qualsevol real equivalent a ell . (D(W), estarem fent la afirmaci6 per qualper 1D(W) ; o bé, si fixem com a representat al qual  1u (9(x»  convergeix, hem d'estar - c)  Amb el que s'ha dit es pot precisar i demostrar 1'afirmaci6  "C I  és una R-álgebracompleta" . 5 .9  Proposici6 .  (existéncia de máxim i minim per elements de  C I ).  Sigui I - ( J1,XI .  Per qualsevol  <D u (1) , (u, j) E CI (1)  F  (3T 1 ,T 2 )IT i ER & T z ER & T I tiX & 46er,  & T 2 '-X &  (ven e ER .& ~-4 e&e  X k (D(9) ti <>(T 1 )  & (D (e) á (D(TZ)11 Veuremcom construir T 1 . Recordem que T 1 (x) = r(x)-s(x)/u(x) per certs pseudooperadors r, s, t, i que (3T 1) significa (3r,s,u) . Primer definim (a-b/c)=(d-e/f) _ ((af+ec)-(bf+dc))- 0/M) La funcio a(x) definida a la secci6 2 s'estén com a(a-b/c) = a(a-b) Ara suposem V : $(u,&) EC I (~) . Aix£ que tenim, per algun m, algun t, i certes V' i X', monótones, no decreixent i no creixent', respectivament, i tals que X - X'  i 0 ~ ~' : (~)  V : (Vk,CI,B,Y,d,n)[ldenoma=0 A - ldenomB=0 A - ldenomY=O Aldenomd=0 A a 6 Y A Y < BA (% < 6 A 6 5 B ¡Y -6 1 < l/m(k, «,B,n) = I> I'D k (Y)-D k (6)1 < 'l/n] (bn,r,C)[ ldenomC=0  A 'P'(t(n)+r) < C  AC < X' (t(n)+r) Llavors tenim, en alguna extensi6 V' de V, per algun f, i si V : [ c > X' (0)-o' (0)] , on Usemla notaci6 i T l (x) és r(x)-s(x)/u(x) ->j(Dt(n)+r(J)- ot(n)(1)1 < 1/n] V' : (1fn)[ f(n,0)=0] V' : (Vn,i)[f(n,i+1)=f(n,i)+[ ((i+1)-f(n,i)) . á(0t'(n)(IP'(t'(n))+((Y+1)/d) " s)4 t(n)(V'(t(n))+(f(n,i)/d) " e))31 6  - X' (t (n) ) - ;k` (t (n) ) P(n) _ ;P'(t(n))+(f(n,n)/d) .s Llavors,en alguna extensi6 W' de V' tenim, per certs q, r, s, u, P(q(x)) E R(x), W' :  Ox)[r(x)-s (x) /u (X) =p(q(x))] , La construcci6 de T Z és análoga, i d6nalloc , a un segment W . Resta per demostrar ., per qualsevol e, d - c .m(t(n)  (t(n)) , X' (t(n))  n) w : e E R s ~y~e & 0 11X  k (D(6) ;Ir (D(T,)  s (D(0) a (D(T2 5 .10 Proposició .  (teorema de Bolzano) . Posem I = [IL,X] . per qualssevol ~, X, (D, 6, sió V' tinguem V' : E  C I (  )  &6 E  R & (D(0)  0 e  & e Z- (D (X) k (3T)[p~T &T!C0 &(D(T) -e], i 1'analeg per (D(0) á e  ie ? $(X) . Per la demostració suposarem, sense perdre generalitat, que v : ~D (41) i~- 0/1  & 0/1  ~(X)  & 6 . . 0/1 Aixó, junt amb (*) i (**) de la proposició anteriorés la nostra hipótesi . Fácilment podem substituir 1 per alguna $' tal que, per algunaextenV' :  (d n)[ ~t(n)  (n»<  0/1  &0/1  < ~t(n) )X' (n»] , amb la mateixa notació de la proposicióanterior (per 1' en lloc de (D) . Suposem que $ ja té aquesta propietat, per V' - V . La condici6 és equivalent, en alguna extensió V' de V, per algun f, a Com que v' : (Vn)[f(n,d)=0]  tenim V' :  (Vn)[ El (n)=1  & Mi (n)  E  N &  f (n,Mf (n) )=0 & 1f (n,Mf (n)=1=0] Tenim aleshores V ~ (Dt(n)(~~(t(n))+(i/d) " E > 0/1) V'  kf (n, i)=0 V' : (Vn)[ (Dt(n)(P'(t(n))+(Mf(n)/d) " E > 0/1 & ~t(n)(~'(t(n))+((Mi(n)_ 1)/d) " e < 0/1] Fem a(n) _ ~'(t(n))+(Mf(n)/d) " E i tindrem, per qualsevolsubsuccessi6 O(q(n)) de a(n) que sigui un real, en alguna extensi6 V" de V', Instituto de Matemáticas U .N .A .M . V" : $(a(q(n)))^ 0/1 Referéncies [1] F . Tomás . Aritmética i análisi formalmentrecursives . Pub . Mat . UAB, 28, No . 1, pp . 19-78 . [2]  R .L . Goodstein . Recursive Arithmetic . North Holland, 1957 [3]  R .L . Goodstein . Recursive Analysis . North Holland, 1961 [4]  E . Specker . Nicht konstruktiv beweisbAre Sátze der Analysis . The J . of Symb . Logic, 14, No . 3, (1949), 145-158 . Rebut el día 14 d'abtíl de 1986 Instituto de Matematicas U .N .A .M . México .