Aritmética i analisi formalment recursives

Pub . Ma . UAB Vol . 28 N4 1 Maig 1984 ambé pe any a R' . ARITMÉTICA I ANALISI FORMALMENT RECURSIVES Rep esen em pe ]N el conjun dels na u als, el ze o inclas . Conside em uncions de IN en7N, pe o s els na u als , en enen que una unció de]N 0 en ]N no és es més que un elemen de ]N . . Si és una unció de ]Nn+l en lN, ep esen en pe Ela unció de IN n en 7N de inida de la mane a següen : les condicions següen s : les p opie a s h(xl, . . .,xn,0)= (xl, . . .,xn) F ancescTomás 1 . In oducció 1, si hl ha algun na u al E(xl, . . . . xn)- 0, en cas con a i de inim la unció  de 7N n en ]N7 con M Y Si E (x 1 , ... . x n )=1 pe cada col " lecció de na u als x 1 1 . . . . X n , alesho es m(xl, . . . . %)=mínim na u al y al que (x 1 ,.. . . xn - # y)=0 al que (xl, . . .,xn,y)=0 Ens in e essa conside a una classe de uncions, que deno a em pe R', que és la mínima classe de uncions de ]N en]N, amb no ix, que sa is á R' .1 . Les uncions cons an s, la unció successo ( S(x)=x+1) i les un- cions p ojeccions ( pi(xl, . . .,xn)=xi) pe anyen a R' . R' .2 . Si : IN n a7N ig : IN n+2 +IN pe anyen a R' ila unció h : IN n+lyIN é h(xl, . . .,xn,S(y))=g(x1, . . .,xn'y,h(x1, .-x n . Y)) pe cada (xl, .. .,xn,y) de IN n+1 , alesho es h ambé pe any a R' . R' .3 .  Si : ]N n i ]N pe any a R'  i, pe j=1, . . . . n, les uncions g j : IIP ->IN pe anyen aR', alesho es la composició h, de inida con h(yl . . . .,ym)= (gl(Y1, . . . . ym ), . . . . 9 n (y l ,.. . . y m )), 1 9 R' .4 . Si (xl, . . .,xn,y) pe anya R' i E(xl, . . .,xn)=1 pe cada (x l 1" . .,x n ), alesho es m(xl, . . .,xn) ambé pe anya R' . R' .S . Si (xl, . . .,xn,y) pe anya R', alesho es E (x l   xn ) ambépe - any~ R' . Es un sob een és queles uncions que s'ob enen de uncions de R' pe pe mu acions de les a iables són ambé uncionsde R' . Con enim en que si :76I n -* IIQ pe anya R' ambé hi  pe any la unció g de inida com g(x l ." " xn'xn+l)= (xl, . . . ,xn) . La m iima classe de uncions que sa is á les es p ime es condicions és la de les ecu si es p imi i es . La mínima que sa is a les qua e p ime es és la de les ecu si es o dio án iques ( egi's, al espec e, 1'a icle [2! de Da is, pe exemple) . Es cla que o es les uncions ecu si es són com- pu ables . Té una g an accep ació la esi de Chu ch, que a i ma que les un- cions ecu si es sónles úniques uncions compu ables de n-ades de na u als en na u áls . També eneng an impo ancia en la demos ació del eo ema d' incomple esa de Gódel .(Vegi's 111, pe exemple) . En el p esen a icle es ac ade mos a la impo áncia que po eni la classe R' en elació a 1'análisi ecu si a i en'p oblemes de onamen a- ció . Reco dem que 1'anomenada a i mé ica ecu si a apa eix, a mansde Skolem, com una mane a de desen olupa 1'a i mé ica sense e ús no cons uc iu dels quan i icado s lógics, amb la idea que aques ús po gene a pa adoxes . El esul a del eball de Skolem és una p esen ació de 1'a i mé ica desen o - llada cons uc i amen ( eu e [3] o V41, pe exemple) . L'análisi ecu si a consis eix en po a la ma eixa idea a 1'análisi, pe a ob eni -ne un desen- olupamen cons uc iu . Aixi, una successió, ecu si a de acionals no nega- ius se á una pa ella, (n),g(n), de uncions ecu si es alque g(n)¢0 pe cada n . La successió se a 20 al successió és de Cauchy hau em d'exhibi una unció ecu si a h(n) al que ( )  -  (s) I .c  1 Ig( )  g (s)  n (0)  (1)  (2) g(0)  g(1) ' g(2) ~ . . Si no olem usa uncions que no siguin ecu si es, pe a mos a que una semp e que >h (n) i s>h (n) Pe o es dóna el cas ( eu e [61, pe exemple) que hi ha successions com les an e io s que són c eixen s i a i ades supe io men pe a les quals no hi ha cap h(n) que sigui ecu si a i sa is ace la condició de Cauchy . Aixó a que 1'análisi ecu si a sigui insa is ac ó ia des del pun de is a ma emá- ic . Una aó pe la que la classe R' po se impo an és que el enomen an- e io no es p esen a si subs i ulm les uncions ecu si es pe les de R' . Es a di : si i g pe anyen a R' i la successió és mono ona i a i ada, po- den oba la h que necessi em en la classe R' . Cal eco da , pe ó, que la aó de ole desen olupa 1'análisi en base a les uncions ecu si es és que un al desen olupamen és cons uc iu ; i deixa de se -ho si ens basen en les uncions de R', ja que aques es no són, en gene al, compu ables . Malg a aixó dedica en una secció, la 3, a e accep able, des del pun de is a ma emá ic, la idea de ecolza 1'análisi en les uncions de R' . En la secció 4 ep end em el pun de is a de la onamen ació i eu em els a an- a ges que po ene , pel que a a consis éncia, un desen olupamen de 1'a- nálisi en base a R', en compa ació amb al es desen olupamen s no cons uc- ius . El o malisme que es p oposa a la secció 4 és de mena ecu si a, co- sa que jus i ica el í ol de l'a icle . La secció 2 es dedica a ob eni una ca ac e i zació de la classe R' ; les idees que s'usen a [21 pe a ca ac e- i za les uncions ecu si es com a dio án iques ens dónen acilmen una ca ac e i zació de les uncions de R' com a "ul ádio án iques" (ab euja UD) La secció 4 és un e inamen de [7] . Aques a seccióés independen de la 2 i la 3 . No s'es udia quina és la elació que po se hi ha en e el o ma- lisme que es p oposa i llanálisi ma emá ica cons uc i a de la que es pa la a V81 . 2 . Conjun s i uncions ul adio án ics Com que ens e e im a (21 cal di que Da is conside a el conjun dels en e s posi ius, en lloc de IN, de mane aque les uncions que ell anomena ecu si es no són les ma eixes que anomenem així a la in oducció,pe qué di e eixen en domini i codomini . Pe o lla icle de Da is es po epensa , pe així di -ho, posan na u als en lloc dlen e s posi ius . D'al a banda, llexposició que a em se a au osu icien ,lle a de pun s no essencials . 2 .1 . De inició . Un subconjun A de ]N n és dio án ic si hi ha  algun (x 1 , . . .,xn.Y1 .. . .,ym)E MIx1, . . .,x n' yl " . .,y m  Cal que (x l ,  .  .xn )EA  q  (3y1, . . .,yn)C (xl, . . . . xn,yl, . . .,ym)=07, on slen én que y, - - .,y__ han de se na u als . 1  Ill 2 .2 . De inició . Una unció de IN en IN és dio án ica si la se a g á ica és un conjun dio án ic . A [21 es demos a que les uncions ecu si es coincideixenamb les dio- án iques . No usa em aques e . A a olem de ini una classe de conjun s que anomena em ul adio án ics , ab euja UD . Pe a e -ho háu em de pa la de p edica s UD . En end em pe p edica s les a i macions ela i es a col " leccions ini es de a iables, suscep ibles de se e dade es o alses cada egada que aques es a iables són subs i uides pe na u als . En el p océs de de inició dels p edica s UD ens e e i em a "exp essions polinomials en x 1 , . . .,x n " en lloc de e e i - nos a "polinomisen xl, . . .,xn" . Així, di em que les exp essions 2 2 (2x-y)y+(1-y)(2x+3)+zy2-(3+2x), zy 2 -y(y+3), són exp essionspolinomials di e en s, a desg a de se exp essions delma- eix polinomi yz 2 -y 2 -3y . Aques polinomi po se pensa com a polinomi en y i z, o en x, y i z, o en w, x, y, z, e c ; pe oen can i podem a i ma que en la p ime a exp essió hi apa eixen les a iables x, y i z, i cap al a, men e que en la segonahi apa eixen y i z, i només elles . Aques a és la mena de dis inció que olem e . Si ep esen em una exp essió polinomia1 pe (x l ,. . . . x n ) es a em suposan que en 1'exp essió hi apa eixen les a- iables xl, . . . . x n , i cap al a . Dona em a con inuació la de inició dels p edica s UD, al ma eix emps que di em en quinscasos una a iable apa eix lliu e en un al p edica ,i en quinscasos hi apa eixlligada . 2 .3 . De inició . PUD .1 . Si (xl, . . .,xn) és una exp essió polinomial amb coe icien s en- e s, la o mula (x1, . . .,xn)=0 és un p edica UD, en el que no hi apa eix cap a iable lligada i en el que o es les x i , pe 1<ibn, hi apa eixen lliu es . PUD .2 . Si P és un p edica UD, la se a negació -,P és un p edica UD . Les a iables que apa eixen lliu es (lligades) en -,P sónles que apa eixen lliu es (lligades) en P . PUD .3 . Si P i Q són p edica s UD i no hi ha cap a iable que apa egui lliu een un d'ells i lligada en 1'al e, alesho es . - P Q, P&Q i P*Qsón p e- dica s UD . Les a iables que apa eixen lliu es (lligades) en qualse ol d , aques s són lesque apa eixen lliu es (lligades) en P o en Q . PUDA . Si P és un p edica UD i la a iable x no apa eix lligada en P, alesho es (Vx)P i (3x)P són p edica s UD, si en enem que el dominidels quan i icado s és IN . En cadaun d'ellsx hi apa eix lligada ; i les al es a iables que hi apa eixen lligades són les que apa eixen lligadesen P . Les a iables que hi apa eixen lliu es sónles a iables di e en s de x que apa eixen lliu es en P . PUD .5 . Un p edica és UD únicamen pe combinació de les aons an e io s . Si xl , . . .,xn són o es les a iables que apa eixen lliu es en un p edica ul adio án ic P, és cla que P és un p edica ela iu a aques es a iables ; pe o P ambé és (o el podem pensa com) un p edica ela iu a xl , . . .,xn , x n+l'" '' m pe qualsse ol a iables x n+l , . . . . xm . Pe indica que pensem en P com p edica ela iu a x l , . . .,x , 1'esc i im P(xl, . . .,x ) . L'única con- dició que ha de sa is e la col " lecció x1 ,. . . . x es la de con eni o es les a iables que apa eixen lliu es en P, enca a que con é, pe aons de cla e- da , que aques a col " leccióno con inguicap a iable que apa egui lligada en P . 24 No a . El p edica Qx)jy+l+x-z=03 _(3 ) x+1+ -z=01 no és UD, segons la de inició que hem dona ; pe o és equi alen a (3u)[y+l+u-z=0' V (3 )Ix+1+ -z=01, que si que n'és . Aixó mos a que la limi ació que sembla imposa PUD .3 només és apa en . 2 .4 . De inició : CUD . Un subconjun A de]N n és UD si hi ha algun p edica ul adio án ic P(xl, . . .,xn) al que, pe qualsse olna u als al   an, (a l ,. . .,an )EA * P(al, . . .,an) FUD . Una uncióde 1N n enIN és UD si la se a g á ica és UD . La ca ac e i zació que ens in e essa és la seguen : 2 .5 . Teo ema . La classe R' cons a p ecisamen de les uncionsUD . La demos ació se á conseqüéncia d'un segui de lemes i conside acions . 2 .6 . Lema . Le s uncions suma i p oduc e de na u als pe anyen a R' . Tenim a+0=a i a+S(b)=S(a+b) . Fem (x)=x i g(x,y,z)=S(z) . . Pe R' .1, eR' . Si p(x,y,z)=z, p«R', pe R' .1 ; i, com, que g(x,y,z)= S(p(x,y,z)) i SER', in- d em que g R', pe R' .3 . De mane a que la suma pe any a R', pe R' .2 . De mane a semblan , dona que a " 0=0 i a S(b)=(a-b)+a, podem eu e que el p o- duc e pe any a R' . 2 .7 . Lema . La suma i el p oduc e de dues uncions de R' (amb ma eix do- mini) pe anyen a R' . E ec i amen ,pe que sónles composicions d'aques es uncions amb la su- ma i amb el p oduc e, i pe anyen a R' pe R' .3 . Co ol la ¡ . Cada polinomi amb coe icien s na u als pe anya R' . 2 .8 . Lema . La unció P de IN en IN, de inida com pe any a R' . ácilmen que P R' . P(x)=1 x-1, si x>0 0, en cas con a i Tenim P(0)=0i P(S(y))=y . Si, en R' .2, em n=0, =0 i g(y,z)=y eu em 2 .9 . Lema . La uncióx= y, de inida com x-Y, si x>,y x-y_ -~ 0, en cas con a i pe anya R' . La demos ació és an ácil com les an e io s, si obse em que x=0=x i x=S (Y)=P(x=Y) . Co ol la ¡ . Si ig són uncions de R' amb el ma eix domini, =gcR' . 2 .10 . Lema . Si  i g són uncionsde IN n en IN que pe anyen a R', ales- ho es la unció D ,4, de inida com D ,4=( =g)+(g= ), pe any a R' i enim, n pe cada (xl, . . .,xn) de ]N , D .4 (xl, . . .,xn)=0  0  (xl, . . .,xn)=g(x11 . . .,xn) La demos ació és i ial . 2 .11 . Lema . Si (xl, . . .,xn) és un polinomi aamb coe icien s en e s, hi ha n una uncióD en R' al que, pe qualse ol (x l ,. . . . x n ) de7N, D (x11 . . .,x n )=0 cp (xl, . . .,xn)=0 El polinomi es po exp essa com =g-h, on gih són polinomis amb coe icien s na u als . Podem escolli D com la D g,h del lema an e io . Di em a a que uná llis a ini a ' A 1 -_A . on cada Ai , és subconjun de lN n(i) , pe algun n(i), és una cons ucció de - conjun s UD si cada A, sa is a una de les condicions següen s : i C .1 . A (xl, . . . .xn(i))=0}, pe algun é7l xl, . . . .xn(i)~ . C .2 .  A i = '(xl,- .. x n(i) ) :  (x l ,. . . . x n(i) ) T' A j 1'  pe algun j<i . C .3 . A i =A 3 UA k , pe alguns j, k meno s que i . CA - A i 4 xl-  xn(i)) .  (3Y)  (xl, . . . . xn(i),Y)EA 7 .1, pe algun j<i . Volem demos a que cada conjun UD és memb e d'algunacons ucció de conjun s UD . Obse em en p ime lloc que o s els p edica s UD es poden es- c iu e sense usa els signes &, :> i Y, degu a que P&Q és equi alen a i(-iP V %Q) , PqQ és equi alen a nPVQ i  (dx) P és equi alen ~a -,(3x) (-,P) . Consi- de em, doncs, els p edica s UD exp essa susan únicamen -1, V, i 3 . Veu em que cada conjun ul adio án ic A és memb e duna cons ucció de conjun s UD pe inducci6 sob e el nomb e de egades que apa eixen signes lógics del conjun j',V ,37 en un p edica UD que de ineixi A . Si en un al p edica P no apa eix cap d'aques s signes, A=í(xl, . . .,xn) : (xl, . . .,xn)=0}, pe algun E a xl, . . .,xn] , i A és el memb e únic duna cons ucció de conjun s UD . En cas con a i P és d'alguna de les o mes -IQ, P 1 VP 2 , (3x)Q En el p ime cas, en Q apa eixen menys signes logics que en -Q, i pe hipo- esi qualse ol conjun A' de ini pe Q és memb e duna cons ucció de conjun s UD . Si pensem nQ com p edica en x l , . . .,x n , pense4ambé a Q com a p edica en aques es a iables, i el conjun A se á el complemen de A' . Si A' és memb e de la cons ucció A 1 ,  .- A , alesho es Al, . . .,A ,A ambé és una cons ucció (de conjun s UD), segons C .2 . Els . al es casos es ac en amb la ma eixa acili a . 2.12 . Lema . Si A és un subconjun UD de Di n , hi ha en R' alguna unci6 26 al que A= {(xl, . . .,xn) : (xl, . . .,xn)=0} Pe les obse acions an e io s és su icien el demos a que cada memb e de qualse ol cons ucció de conjun s UD é aques a p opie a . Conside em la cons ucció Fa em la demos ació pe inducció sob e l'index i de A . . Posa em n en lloc 1 de n(i) . Tenim, pe comen a , Ai {(X11 . . .,xn) : (xl, . . .,xn)=0}, on E a Ix l ,. . . ,xi . Segons el lema 2 .11, Al ~(xl, . . .,xn) : D (xl, . . .,xn)=0} . D E R' . Suposem que Al, . . .,A i-1 enen la p opie a del lema, i conside em A . . Si Ai=I(xl, . . .,xn) : g(xl, . . .,xn)=0}, on g E T Ixl, . . .,xn~, p ocedim com . pe A l . Si Ai = 1 (x l ,. . . .x n ):  (x 1 ,. . . . x n )4A j i pe algun j <i al que A j E IIN n , sabem pe hipb esi d'inducció que Aj= j(xl, . ... %) : (xl, . . .,xn)=0¡¡ pe .al- guna de R',  i alesho es Ai={(xl, . . . . xn ) : 1= (x 1 , . .- x n )=0~ ; i 1 1 - .E R' . Si A i  ~ .=A .VA k ,  on j i k són meno s que i, ind em A j = j(x1, . . .,xn) :  (x l , . . . . x n ) =0" A k =¡(x 1 - . .,xn) : g(xl, . . . . x n )=0}, pe ce es i g de R', i alesho es Ai=J(xl, . . .,xn) : (x )g(x )=0} ; i ja sabem que g E R' . Si, inalmen , A  ~(x l , . . . ,x n ) :  (3Y) [(x l " . . . ,x n . Y) E A j 13 pe algun j<i, sab em que (x 1 ,. ." x n ,y)EA 3 0 h(xl, . . .,xn .y)=0 pe una ce a h de R', i lla o s Ai=l(xl, . . . . x n ) : hE(xl, . . .,xn)=1j =j(X V . . .,x n ):  1=hE(xl .. . .,xn)=01, i ja sabem que h E pe any a R' i 1-h E ambé . A a ja podem demos a que cada unció UD és de la classe R' . Si és UD enim, segons el lema 2 .12, pe alguna g de R', y= (xl, . . .,xn)0 (x l , . . .,x n .Y)E[g á ica de ] Og(xl .. . .,xn .y)=0 c( -g/h)=0 . En aques cas (Y n) (V ) [1( -g/h) (d( - g/h) (n)+ )-( -g/h) (d( -g/h) (n)'< n i d( -g/h)(n) és el minim na u al amb aques a p opie a . b) Si , g i h són UD i c( -g/h)=0, la unciód( -g/h) és UD . Co ol-la i . Si , g i h són UD ila succesió ( -g/h)(n) és c eixen i a i ada supe io men ,alesho es la unció d( -g/h) que la exhibeix com de Cauchy ambé és UD . Com deiem en la in oducció, es dóna el cas que , g i h siguin ecu si- es i que i( -g/h)(n4 sigui c eixen i a i ada men eque d( -g/h) no és ecu si a . El co ol " la i mos aque el enomen análeg no es p esen a en el cas UD . Ens in e essa a a conside a successions de limi s de successions de na- u als . Comenca em pe conside a successions de successions de na u als, que no se an es més que e nes de uncions, (i,n), g(i,n), h(i,n), de DI 2 .en]N als que h(i,n) és5emp e di e en de ze o . Pensem en qualse ol d'a- ques es e nescom en la successió de successions (0,n)-g(0,n)  (l,n)-g(l,n) h(0,n) 'nE]N ' k h(1,n) 'ne]N Fem i(n)= (i,n),gi(n)=g(i,n), hi(n)=h(i,n) . Si cada una de les ( i -gi /h i)(n) és de Cauchy, és cla que la succes- sió dels seus limi s és de Cauchy si i només si és de Cauchy la successió i en cas a i ma iu el limi d'aques asuccessió és 3 4 ( 0-g0 /h 0 ) (d( 0-90/h0)(0»,  ( 1 -g 1 /h l ) (d( 1-gl/h1)(i»,  . . . De inim, en aques cas, lim lim (i,n)-g(i,n) 1 n h(i,n) D (n)= n (d( n-gn /h n ) (n) ) 9D (n)=g n(d( n-gn/h n) (n» hD (n)=h n (d( n-gn /h n )(n)) i ind em : 3 .1 .2 . Lema . Am b la no ació an e io , suposem que cada  ( i -g i )(n) és de Cauchy . Alesho es : a) La successióIlñm ( i-9i) (n)} iEIN es de Cauchy si i només si c( D g D /h D )=0, i en aques cas (i,n)-g(i,n) D(j)-gD(7) 9D (i)  i h D (i)  ambé ho són . Mm lñm  h(i,n)  - ljm  hD(j) b) Si les uncions (i,n), g(i,n) i h(i,n) són UD, les uncions D (i), Res a pe comp o a únicamen la pa b) . Amb aques a inali a econs- ulm les de inicions de D, gD i h D . Si e isem la de inició de d( -g/h), bo i posan i , g j i h j en lloc de , g, i h, ind em dl(j,n,m, )=( (j,m+ )h(j,m)+g(j,m)h(j,m+ ))=(g(j,m+ )h(j,m)+ (j,m)h(j,m+ )) d2(j,n,m, )=(g(j,m+ )h(j,m)+ (j,m)h(j,m+ ))=( (j,m+ )h(j,m)+g(j,m)h(j,m+ )) d3(j,n,m, )= n(d1(j,n,m, ))+d2(j,n,m, ))+1 _ h(j,m+ )h(j,m) d 4 (j,n,m, )=1=d 3 (j,n,m, ) d( j -g j /h j ) (n)=((d4)E)M(j,n) Es cla que ((d4)E)M(j,n) és UD . Si em p(j,n)=n enim d( n-gn/hn)(n)=((d4)E)M(n,n)=((d4)E)M(p(j,n) .p(j,n)) i aques a unció és UD pe queés composició de uncions UD . Pe an D, gD i hD són UD . També podem obse a quec( i-g i /h i ) és UD  com a unció de i  (si , g i h ho són) . Diguem a a : 3 .1 .3 . De inició . Un a successió is nln E IN de acionals és UD si exis e¡- xen uncions, , g, h, de IN en IN quesón UD i als que sn=( -g/h)(n) pe cada n . 3 .1 .4 . De inició . U n nomb e ealés UD si és lími d'alguna successió UD de acionals . 3 5 UD si exis eixen , g i h, uncionsUD de]N Z en IN, als que 3 6 3 .1 .5 . De inició . Un a successió a0 , al , . . . de eals UD és una successió a) IR UD es un cos a,=1im (i,n)-g(i,n) pe cada i 1 n  h(i,n) Així, doncs, o s els memb es duna successió UD de eals són eals UD ; pe o és possible que una successió de eals UD no sigui una successió UD . Deno a em pe IR UD el conjun de eals UD . 3 .1 .6 . Teo ema . b) Si la successió de eals a 0 , al , . . . és UD i de Cauchy, alesho es lim a . c- IR UD 1 La pa b) del eo ema ja es a demos ada . Demos a em a) . Suposem que (n)-g(n) b=1im a=1im h(n) , (n)-s(n) (n) i que , g, h, , s, són UD . Es cla que les uncions +h , g +hs, h , +gs, s+g , +hs, g +h són UD, i amb aixó es mos a que II UD es clos pe sumes, p oduc es i di e encies . Res a pe demos a que a 6 1R UD quan aga0 i a E]R UD . Exis eix, en aques cas, m al que (m+ )pég(m+ ) pe o s els ; i podem suposa sense pe d e gene ali a que m=0 . Tenim alesho es h(n) I (n)-g(n)I -1 hin)  (n)-g(n) a  =1im (n)-g(n) =lim  I (n)-g(n)i (n)-g(n) g(n)- (n) h (n) ( n ) -g (n) - h (n) g ( n ) - (n) -hm j (n)-g(n)u Sabem que I (n)-g(n)I és UD . Pe acaba se a su icien el demos a en ge- ne al, i si de inim c_c =0, que la £unció ~c-d és UD . Tenim, en e ec e _cid _  1, si c-d>0 c-d -~ 0, si c=d=0 ye o és acil eu e que la £unció A al que A(0)=0 i A(S(n))=1 és UD ; i alesho es eiem que ¿c-d es UD pe que és igual a A(c=d) . Podem eu e que IR UD es nume able ; com que la col lecció de conjun s UD és nume able ambé ho és la de les uncions UD, la de les successions UD de acionals i la dels eals UD . Pe o es p esen a una si uació análoga a la que es dóna pe els conjun s UD ; 3 .1 .7 . Obse ació .IR U D no es "ul adio in icamen nume able" . Cada eal es po exp esse de mane a única com n a . 1¡m (a 0 + 5 3 j ), j=1 10 on els a j són en e s, 0 j1 a j <1O pe j > 0 i no exis eix cap al que (1/s) Ia +s -g1 Conside em qualse ol e na , g, h de uncionsUD de IQ 2 en]N, la úl ima de les quals no s'anul " la mai, i suposem que, pe cada j, la successió S (7,h(-g ñj,n) nEIN és con e gen , i ep esen em el seu limi pe c, . A i - J,  7 mem que la llis a c 0 , c l , . . . no po con eni o s els eals UD . E ec i a- men , exp essem cada c . en la o ma 7 i .de inim bo =a (0) +1, Es po demos a que les uncions (n) (n)=10 n són UD, i és cla que el eal n (j) c j =lin m(a (3) +Z al ) i=1 10i 1,  si  j>0  i  a ( j) YÉl 12,  si  j>0  i  aj j) =l n nbO+  10 n-l b i , si b0 >,0 i=1 -1 10 n-l b i , si b0 < 0  Illi 0, si b 0 ,0 s (n)= 1-10 n b 0 , si b 0 < 0 és di e en de o s els c, i és UD . 1 3 .2 . Les algeb es CUD c de uncions con inues . Seguin el me ode de 5j, conside em e nes de uncions de IN 3 en IN que sa is acin les condicions se- guen s : A) h( ,s, )~0 semp e que yé0 ( s )-g( ,s, ) B)  ' ' = h( ,s, )  h( ',s', ')  semp e que y£0, 'y¿0 i -s '-s' ' Si es sa is anaques escondicions la e na , g, h po se in e p e ada com unció de 1p en Q . Usa em, en aques cas, pe #0, les no acions 3 8 ( s)= ( ,s, ), g( -s)=g( ,s, ), h( s)=h( ,s, ) ( -g/h)( -ss)=( -g/h)( ,s, ) - ( ,s, )-g( ,s, )  h( ,s, ) Qualse ol unció de Q en Q es po mi a d'aques a mane a, com no és di- icil comp o a . Si pe una al unció F es sa is a esc iu em F=( -g/h), si , g i h sa is an les condicions A) i B) . 3 .2 .1 . De inició . Di e m que F : Q -9 Q és UD si exis eixen , g, i h que són UD, sa is an A) i B) i són als que F= -g/h . Conside em un in e al ja,b~ amb ex ems acionals . Suposem que b l -b 2 c l-c 2 b J b  ,  c-  , b l ,  b 2 , b, cl , c 2 ,  c 3 na u als c  3 33 Tenim, pe -g/h : Q ->Q, F( -s)=( -g/h) ( s) -g/h és uni o memen con inua en [b,c]nd2 b -b  c -c q (`In) (3 m) (d ,s, , ' ,s' , ') [ =0 V '=0 V s < 1 b 2 V s  'C  2 3  3 V ' -s < b1-b2 V @-s' ~ c1-c2 V -s -  IJ1 ' b 3 ' c 3 ' m d j( -g/h) ( s)-( -g/h) ( ,- s , )l< n n b, lim (b +Y ^ 1 )=1im (n)-s (n) n  0 i=1 101  (n) Si p ocedim de mane a semblan a com s'ha e a 3 .1 a iba em a que -g/h és uni o memen con inua en [b, c] (1Q 0 (dn) (3m) [k(n,m)=01 Id> (Vn) [k E (n)=1] a U([b,c], -g/h)=0, on U([b,c] , -g/h)=(kE)E i k(n,m) és ce a unció, que és UD semp e que , g i h ho siguin . Si -g/h és uni o memen con inua en [b,c] 1 (2, alesho es (1jn) kE (n)=1  i es a de inida la unció D ((b,c] , -g/h) (n) =k m (n) que ens dóna, pe cada n, el minim m alque -s  '-s' 1  -s j( -g/h) ( ) - ( - g/h) (  ,  )I~ ñ  semp e que I -  e  I~ m Tenim, doncs : 3 .2 .2 . Lema . La unció - g/h :C -i Q és uni o memen con inua en [b,c]l1(Q si i només si U([b,c], -g/h)=0 . En aques cas es sa is á, pe s i ~s' en [ b, j, _ -s _ '-s'  1  -s  '-s ')J 9 1 I   '  ~~ D :( b,c  , - g/h) (n)  ~( -g/h) ( )-( -g/h) ( ,  ñ on D([b,c], -g/h)(n) és, pe cada n, el minim na u al amb aques a p opie a . La unció D( b,c , -g/h) és UD semp e que , g i h ho siguin . 3 .2 .3 . De inició . Rep esen a e m pe <Q [ D Ic ] el conjun de les uncions de [b,cl enIR que són ex ensions a [b,c], pe con inui a ,de uncions -g/h de C en Q que siguin UD i uni o memen con ínues en [b,c]gQ . Si k és 1'ex- ensió duna al -g/h posa em k= -g/h 3 .2 .4 . De inició . Conside e m una successió k0, k l , . . . d'elemen s dé QUD  Di em que la successió és UD si exis eixen uncions , g, h de ]N 4 en [b, cl N als que : a)  Pe cada i, si em i ( ,s, )= (i, ,s, ), g i ( ,s, )=g(i, ,s, ), h i ,( ,s, )=h(i, ,s, ), alesho es i-g i /h i és unció de C en Q ; b) , g i h són UD, cada i-gi/hi es un¡ o memen con inua en[b,c)A Q i ki = i . -g i /h  pe cada i . i 39 La elació que hi ha en e UD q  Q(b cl i la classe de uncions con ínues de [b,cj eniR s'assembla a la que hi ha en e C? ¡IR . Així com cada eal és el lími d'una successió de acionals,aixi ma eix cada unció con inua de b,cj enIR és el limi duna successióuni o memen con e gen d'elemen s de Q UD UD c1 (aques a a i mació és consequencia del eo ema de S one-Weie - s ass, de que els polinomisamb coe icien s eals són an ap oximablescom olguem pe polinomisamb coe icien s acionals i de que aques s úl ims són elemen s de C `b c i) . Pe ó de la ma eixa mane a que de inimIR UD diguem a a : 3 .2 .5 . De inició . Rep esen e m pe CUD c1 la classe de uncionsde (b,cj enIR que són limi s de successions UD, uni o memen con e gen s en [ b,j , d'elemen s de Q UD (b, cl . 3 .2 .6 . De inició . Un a successió k O , k l , . . . d'elemen s de CUb c] es UD si exis eixen , g, h, uncions de IN 5 en IN als que : a) , gih són UD b) Si em . .( .s . )= (i .i . .s . ), i analoaamen Pe cT i h, alesho es, 1,] ....  . .- .. . . .  . . pe cada (i,j), i , .j -g l,,j /h i .j és una unció de Q en (Q, uni o memen con i- nua en Ib, c] nQ 40 c) Pe cada i, l ilj -g i,j /h i,j)je IN con e geix uni o memen en Cb,cja ki 3 .3 . Conside ació inal . Les conside acionsque hem es a en en aques- a secció 3 an en el sen i de mos a que 1'análisi UD po unciona mol bé . Pe o : le ) no es em en condicions de e una exposició sis ema ica de 1'análisi UD ; 2 o n) po se el con ex no o malen el que es em en aques a secció no és el millo pe in en a aques a exposició . Pe aques es aons pensem que a d o d'ho ahem de alla en sec aques esconside acions, i escollim aques momen pe e -ho . Les p ime esa i macions que pensemque pod iem demos a ,pe o que ja no demos a em, són les següen s : Si CC UD,c  1 a Ei D , (a)EIR UD . CIb , j es una ]R, Si o , l , . . . és una successió UD d'elemen s de CU b,c 3, uni o memen con e gen en [b,c~, alesho es lim ie CUD,cl' UD x UD Si kEC[Ic], íb kEC (b, cl . Si k E C~b c,  i k' exis eix i és con inua, k' E C [b c] Si a 0 , al ,  . . . és una successió UD d'elemen s de II2 UD , la successió n i  UD a i x és UD (en elacióa qualse ol C Cblc l) i el adi de con e gencia es i=0 un eal UD . En can i,no c eiem pode demos a que qualse ol unció con inua en [b,cl i alque (Vb,cin 7RUD) s]RUD hagi de pe anye a Cíb c] . 4 . La o mali zació de 1'a i me ica i 1'analisi basades en R', o ul- adio an iques . 4 .1 . Conside acions p elimina s . Com eco da em en la in oducció,1'a- nálisi ecu si a es po eu e com un in en de desen olupa 1'análisi ma e- má ica de mane a cons uc i a, in en que ens dóna,pe o, una análisi poc sa is ac ó ia desdel pun de is ama emá ic . I aixó és el queens po a a eng andi la classe de les uncions ecu si es i conside a la classe R` de les uncions ul adio an iques (UD) . A la secció an e io hem is que hi ha indicis de que 1'análisi basada en aques a classede uncions és sa- is ac ó ia, ma ema icámen pa lan . Pe o a aens p egun en, desdel pun de is a de la onamen ació, quin a an a ge po compo a aques a análisi basada en R' (o analisi UD), que ja no és cons uc i a, compa ada amb al- es onamen acions d'aques a disciplina, al com, pe exemple, la que es po basa en una eo ia de conjun s o mal . Reco dem que Hilbe ,en el seu p og ama de onamen ació, p oposa a p esen a les eo iesma emá iques com, a sis emes que a ui anomena iem "sis emes o mals" ; exigin , pe o, que la consis éncia de als sis emes es pogués demos a pe mé odes es ic amen " ini a is", al a di cons uc i s . Pe oes comp o a, his b icamen si més no, que a mesu a que un sis ema o mal o mali za egions més amples de la ma emá ica, més lluny es em de pode demos a cons uc i amen la se a consis éncia . I, així, la consis éncia duna eo ia de conjun s o mal no s'ha demos a de cap mane a, men e que la consis éncia de la "a i mcl ica clássica no s'ha demos a cons uc i amen ( egi's [1]) . Aixó a pensa que pe a onamen a 1'a i mc ica UD de mane a "cons uc i amen consis en " po se cal ce ca o malismes que no siguin, en el sen i écnic del e me, sis emes o mals . Aixó és el que s'ha in en a a [71, on es desc iu un o - malisme "obe " o " ecu siu" pe a la classe R' de les uncionsUD . Aqui p esen a em aques o malisme, amb alguna millo a, i desp ésdona em alguna indicació de com pensem que es po usa pe desen o .lupa 1'analis UD . 4' .2 . El o malisme . P esen a em el o malisme c in una ca ego ice de sis- emes o mals . Aixó no ol di de cal) mane a que ens hágim de basa en la eo ia de ca ego ies ; és, an sols, que el llengua ge ca egó ic és escaien al ema . Els objec es de la ca ego ia se an, doncs, sis emes o mals, que anomena em "segmen s" del o malisme . La consis éncia de cada un d'aques s segmen s es demos a ácons uc i amen (cosa que o en a en conElic eamb cap in ( . : p e ació de cap eo ema de códel, ja que cada segmen només con- ind á o o mali za á un os pe i de 1'a i mé ic ;) . To s els segmen s ind an el ma eix llengua ge ; és a di que de ini em els signes del llen- gua ge, els e mes i les ó mules de la ma eixa mane ape o s els seg- men s . '~es egles d'i e éncia se an ambé les ma eixes . De e la lógica de cada segmen se a el cálcul p oposicional, que p esen a em, pe ó, sense e ús dels signes de conjunció i d'implicació . Hi hau á una col " lecció de d mules, cons i uida pe els "pos ula s inicials", que se an pos ula s de o s el .3 segmen s, i que no se an al es que els que ens dona an les p o- pie a s de la igual a . Pe o cada segmen , lle a iel "segmen inicial", ind á, de més, al e :c pos ula s . Les condicions que ens de ini an, ecu - si amen , o s els segmen s, se an els "p incipis" del o malisme . Demos- 42 a em, al ma eix emps que la consis éncia, 1'impo an me a eo ema de "minimali zació" . Disposa em dels en e s no nega ius pe a comp a , indexa , o qualse ol al e ús cons uc iu que ens con ingui ; i usa em les p ime es lle es de 1'al abe , en minúscules, com a signes auxilia s pe a ep esen a -los .Els signes 1, 2, 3, . . . no se an pa del llengua ge del o malisme . 4 .2 .1 . : :ls signes del llengua ge . Són : 0, S, E, M, _,  (negació), V (disjunció), els pa en esis (9 . les se es a ian s), la coma, les " a ia- bles" i els "ope ado a" ; i a a passem a din quina són aques s úl ims sig nes . Podem usa com a a iables els memb es de qualse ol llis a in ini a de signes ; pe o de e no ind em ocasió d'usa les a iables d'al a mane a que ep esen ades pe signes auxilia s . Pe a cada en e posi iu n hem de eni una llis a in ini ade signes, que se an els ope ado a de g au n . Con enim en que S és un ope ado de g au 1 . Cap dels al es signesque en- cap9alen la llis ade sienes del llengua ge, ni cap a iable, no són ope a- do a . E`s con enien , pe o no indispensable, que inguem + i" en e els ope ado s de g au 2 . Usa em les úl imeslle es de 1'al abe ,en minúscules,indexades . o no, com a signes auxilia s pe a ep esen a a iables . Q'zan en un ma eix con- ex apa eguin lle es di e en s com a ep esen an s 3e a iables, c :on in- d em en que ep esen en a iables di e en s . Usa em las lle es minúscules sob e- a l .iades, indexadas ono, pe a ep esen a ope ado a . 4 .2 .2 . Els e mes . Abans de de ini --los diguem que les lle es minúscu- les sub a llades,indexades o no, ep esen a an e mes . De inim : 1) 0 és un enme ; 2) cada a iable és un e me ; 3) si és un ope ado de g au n, i si b1_ _bn són e mes qualsse ol, alesho es les exp essioüs (b E (b 1  b n-1 ) i M (b1, . . .,bn-l) són *, =e mes (si n és 1, s'en én que hem de posa El j . Mi en lloc dels dos úl ims e mesan e io s) ; 4) les ao :is an e- in odui la suma en no ació uncional . Segons les obse acions de 4 .2 .9, +(x,y) E U(x,y) i é la p opie a UF +(b,0)=b  1 semp e que b, c E N- u U F +(b,S(c)=S(+(b,c)) No amen , com que 0 E NU (x)  i +(z,x) E N u (x,y,z), si " és ope ado de g au 2 podem pos ula F -~ 0=d V " (b,0)=0 F - +( .(b,c),b)=d V " (b, S(c))=d e c i així ob enim un segmen V en el qual ja enim la suma i el p oduc e . Podem ana eng andi .n aques segmen . Si p ep esen a un ope ado de g au 1 di e en de S és acil eu e que PR .2 ens pe me d'a egi els pos u- la s i ob eni un segmen úen el qual ind em ambé la unció p edecesso p, que sa is a 5 0 W 1- p(0)=0 W - p(S(b))=b V -i 0=d p(0)=d F -ib=d V p(S(b))=d e c semp e que b(- NW (També enim, és cla , que els e :o emes de U són eo emes de V, i que aques s ho són de W) . Pe o en lloc de e aques a úl ima pos ulacióhau iem pogu pos ula , pe exemple, si h és un ope ado de g au 1 di e en de S, 1- -~ 0=d V h (0) =d F -i S(0)=d V h(b)_=d e c i hau iem ob ingu , en lloc de W, un segmen W' . També, al comenga a pa i de I, hau iem pogu escolli - en lloc de + i pos ula F  b=d V -(b,0)=d F-  S(-(b,c))=d -(b,S(c))=d e c i hau iem ob ingu un segmen V' en el qual la unció suma es deno a ia pe " . Aques s exemples senzills ja sugge eixen p ou bé una de inició de "mo - isme" . Conside em un segmen U que hagi es a ob ingu mi jangan un se- gui de pos ulacions U U U U  U U P l , Ql , P 2 . Q2 i. . . P , Q Suposem que cada pos ulació Pi s'ha e d'aco d amb PR .2, i que la co es- ponen QU ha es a e a d'aco d amb PR .2 ; pe ó adme em la possibili a que i aques a Qi sigui inexis en . En cada pa ella de pos ulacions Pi , Qi hi in- e enen 1'en e n, 1'ope ado , els e mes i s, els en e a p i q i els e mes h ., k j i  de PR .2 i PR .3, que aqui ep esen a em pe n i ,  i U , U, - 2 . S u , p U  q U , h U  kU  i  (pe o aques s úl ima, a pa i de pu , i  i   J. .j  - 1  j  i .j  i poden no es a de ini s, si la pos ulació QU és inexis en ) . Conside em un al e segmen V, dona pe les pos ulacions P l Ql . . . ., Pu , Q u i i usem la no ació analoga . Conside em una aplicació my de la unió de la col lecció de e mes i la de ó mules, que apliqui e mes en e mes i ó mules en ó mules . Di em que mÚ és un io isme de U en Vsi es sa is an les condiciona següen s : M .1 . Pe qualsse ol e mes b i c, in ~(b=c) = mú(b)=mV-(c) mÚ(-,b=c) _ -IRÚ(b)=cn-(c) eix, que deixa ix S i aplicaope ado s de g au n en ope ado s de g au n, i al que, pe cada e me b, m (b) és el esul a de subs i ui cada ope a- do que apa eix a b pe 1'ope ado que aques a aplicació li associa . M .4 . Exis eixen j(1)< j(2) < . . .< j ( ) < u als que Q7 (i) és exis en sem- p e que Qi ho és i que, excep e pe un possiblecan i de a iables,es sa- is an les condicions p enem com aplicació m de M .3 la que po a " en +, + en "i deixa o s els al es ope ado s ixos . jun de e mes i ó mules en ell ma eix és un mo isme de Y en X . En aques cas posa em Y< X . no, un mo isme de U en V . Si mÚ és un mo isme i U F A, alesho es V F m (A) .  _ Dona s Ui V podem cons ui W pe al qual hi hagi mo ismes mÚ i mV . De e , podem cons ui W pos e io a ü . 4 .3 . El pun eble del o malisme . Pensem en un o malisme, que anomena- em o malisme -*, en el que, a més dels p incipis PR .1,2 i 3 an e io s, inguéssim el p incipi 5 2 M .2 . Pe qualsse ol ó mules quasia ómiques A 1 , . . .,A n , m5(A 1 V . . .V A n ) = MV5(A 1 ) V . . .V M-(A n ) M .3 . Hi ha una aplicacióinjec i a m del conjun d'ope ado s en ell ma- n~ a nV  , m( u) a V  , m-( .) = ~  , m (S .) = s . i j(i) i 3 (i)  U a  -3 (i)  U  1  --J (i)  , Pi _- p j(i) ' qi =_ q j(i)  mp(~ .j)  hj ml ( -1 .j ) - ~ (i) 1j . m (9, l .j ) -Ii (i) 'j Re e in -nos als exemples an e io s, ind em un mo isme de V" en V si Di em que un segmen X és pos e io a Y si 1'aplicació idén ica del con- Obse acions . Es comp o en ácilmen les següen s : Dona s ÚiV, es po comp o e en un nomb e ini de passos si hi ha, o PR* . Si U és un segmen , i si i g són ope ado s de g au n+1 als que pe cada col , lecció de nume als bl _ _b n ,c, es compleix U l- (1?1  bn,c)=g(bl  . .,bn,c) ; alesho es ambé és un segmen el sis ema o mal que s'ob é d'a egi a U 1'esquema selüen de pos ula s, pe qualsse ol nume als bl , . . .,bn : F E (b l __b n)=Eg(bl, . . .,bn) És cla que aques o malismo-* se ia més sa is ac o i, si no os po que no hem es a capagos de demos a cons uc i amen la se a consis éncia . Po se aques acás no és a ibuible exclussi amen a manca d'habili a . Aques a possibili a es sugge eix en obse a que el o malismo-* unciona, pe aixi di -ho, massa bé, en el sen i que dóna la imp essió de pe me e cons ui un model de 1'a i me ica clássica (segons [13, pe exemple) ; i si aques a imp essió os jus _ icada i es pogués demos a cons uc i amen la consis énciadel o malismo-* es ind ia, de e op, una demos ació cons- de la consis éncia, uc i aAde 1'a i me ica clássica . No in en a em a a d'ap o ondi en aques- a ques ió . Només n'hem pa ala pe explica la enúncia a 1'in en d'in- clou e PR* en el o malisme . El no disposa de PR* en el o malisme impli- ca cla amen una debili a del ma eix que, segons eu em a con inuació,ens obliga a onca un cos um a ela pe o que po se no ha d'impedi un bon desen olupamen de 1'analisi . 4 .4 . Sob e el desen olupamen de 1'ana lisi mi jangan el o malisme . No- més ac a em d'algun pun delica , pe a il " lus a les di icul a s que es oben . El que hem de e és u ili za el o malisme de mane a cons uc i- a . Aixo és el que es a quan es ol desen olupa una eo ia ma emá ica en base a un sis ema o mal . En el nos e cas enim, en lloc d'un sis ema o - mal, una ca ego ia de sis emes o mals . No hem oba una mane a de ac- a amb di e en s segmen s simul ániamen . Si ens in e essen els segmen s 9 ¡V, no enimal a mane a de ac a -los alho a que mi jangan mo is- mes mi i mV que ens els englobin en un al e segmen W . Ja hem obse a que podem conside a W pos e io a U o a V . No cal di que aques p ocedi- men és mol comú en ma emá iques ; és el que es segueix quan es . an can is de con ex o de no ació . Així, doncs, eballa em semp een un segmen que podem ana eng andin d'aco d amb PR .2 i PR .3 . Ens con ind á, pe o, que qualse ol segmen en el que eballem sigui pos e io a un ce segmen , que anomena em "básic", i que a a - de ini em . A pa i del segmen inicial I in oduim, successi amen , al com ho hem e a4 .2 .10, els pos ula sin- dispensablespe a in odui les uncions +(x,y), .(x,y) i p(x), aques a úl ima, eco dem-ho, amb la p opie a F- p(0)=0 - p(S(b))=b pe cada nume al b P enem a a, en PR .2, ex, s=p(z), == i a egim al segmen els pos ula s (I)-(VII), que an que 2 (a,0)=a 1 pe nume als a, b 4(a,S(b))=P(=(a,b)) De mane a semblan a egimenca a els pos ula s que in odueixen a(x) i b(x) amb les p opie a s a (0)=0 ~( pe qualse ol nume al _b (a(S(b))=S (0) J b(0)=S(0) pe qualse ol nume al _b F £(S(b))=0 ~ El segmen que enim a a és el segmen básic . Qualse ol segmen que con- side em se a pos e io a ell . Usa em les exp essiona auxilia s b+c, b .c, e c pe a ep esen a e mes o o mules segons les con encions seguen s : b+c a +(b,c) bc = b " c a " (b,c) 54 b=c =(b,c) b-c~ = (b=c)+(c=b) b£c = b=c=0 b<c = S(b)6c Sup imi em pa én esis de la mane a habi ual . Aques segmen básiccon é una pe i a pa de 1'a i mé ica ecu si a . A o 141 es poden oba les demos acions de les p opie a s de les un- cions i elacions an e io s, que són ácilmen adap ablesal o malisme . Fem una con enció sob e la no ació . Suposem que es em conside an un segmen U . Com que només hem de conside a segmen s U',U", . . . als que i com que, en aques cas, U-< .U'-CU-L . . ., U 1-- A implica U' 1- A, U' F A implica U" 1- A, e c b E N  implica b E N~,  ,  b E N~,  implica bE N~ .,  , e c b E N~(xl, . . .,xn)  implica b E N5,(xl, . . .,xn), e c podem sup imi la no ació del segmen da an del signe H , i ambé com a índex, i esc iu e simplemen 1- A , bEN , bEN(xl, . . .,xn) pe a indica que, pe el segmen V que es iguem conside an en un momen dona es compleix Vb A , b E NV  ob &%(x 1 ,.. . .x n ) . Di em que una e na de e mes, deno ada b-c/d,és un acional si bEN, c E N, d EN i b -l d=0 . En aques cas esc iu emb-c/d EQ . Di em queuna e na b-c/d és una unció accioná ia de x l ,.. .,x n si b E N(xl, . . .,xn), c E N(xl, . . .,xn)  i d 6 N(xl, ... .xn) . En aques cas esc iu em b-c/d E Q'(x1, . . . .xn) . Adme em el casn=0 ; de mane a que b-c/d E Q' oldi que bEN, CEN i dEN . A con inuació in odui em ce es exp essions auxilia s pe a ep esen a e mes i ó mules . Si b-c/d E Q'(xl, . . . . xn )  i -2/h C- Q'(x1, . . . .xn) : (b-c/d)=( -S/h) e (bh+ d)-(ch+gdd)/(dh) (b-c/d) ( -g/h) _ (b-c/d) ( -g/h) = (b +cLc)-(bbl+ , - )/(dh) - (b-c/d) = c-b/d (b-c/d) -l = (d(á(b-c)))-(d(á(c=b)))/Ib-cI (b-c/d)- ( -q/h) _ (b-c/d)+(-( - ~/h)) Si b-c/d E Q i -g/h E Q (b-c/d)== bh+cd=ch+d (b-c/d)G( -g/h) _ (bh+gdd)E(ch+ d) (b-c/d)« -g/h) z (bh+gd)<(ch+ d) Donem pe demos ades les p opie a s de les ope acions i elaciona an e- io s, i la de 1'in e s mul iplica iu d'un acionalno nul . Conside em a a una e na de unciona de x, b, c i d . In oduim1'exp es- sió auxilia F(x) i con enim, pe cada enme , en que F( ) _ (bl(x, ))-(c l (x, ))/(dl(x, )) Suposem a a que F és una successió de acionals , és a din que 1- , d `(x,a)=0, pe cada nume al a Adme em la següen de inició : De ini ció . Si F(x) és una successió de acionals i enim un e me m E N (x)  al que (1)  1- IF(mi(x,n))-F'((m~(x,n))+ )I-C(S(0)-0/S(n)) pe cada nume al n i cada nume al , alesho es di em que F(x) és un succes- sió de Cauchy . Suposem que F(x) és (le Cauchy . D'aco d amb les de'-inicions ob ind em un e me , unció de x, y, z, al que la o mula (1) és (2)  'I- I(x,n)I(y,ml(x,n))U Z, )=0, pe qualsse ol nume als n, . Conside em la unció S(0)= .'In oduim pos ula s nous que acin, pe un ce ope ado g i qualsse ol nume als kl , k 2 , k 3 , que 56 F g(k l ,k 2 ,k 3 )=S (0)= I(x,k1)'(Y .k2)'(z,k3) Alesho es (1) se á equi alen a (4)  F g(n,mi(x,n), )=0, pe qualsse ol nume als n, . Pos ulem, d'aco d amb PR .3, (5)  j- -~ n=b 1 y  mI(x,n)=b 2 V Eg(b 1 ,b 2 )=0, pe qualsse ol nume als b l1 112 i n . Com que pe cada n podem oba nume als c, als que (5')  H m 1(x,n)=c l V . . .V m 1(x,n)=c , podem dedui , pe cada nume al n, (6)  b Eg(n,ml(x,n))=0 In oduin pos ula s nous d'aco d amb PR .2 ind em, pe un ce ope a- do h, (7)  F- h(k 1 ,k 2 )=Eg(k 1 ,k 2 ), pe qualsse ol nume als k l , k 2 . Pe an , usan (6), podem in e i (8)  F h(n,ml(x,n))=0 pe cada nume al n U ili zan (5') i el pos ula (IV) (pe h) ind em (9)  H EE(n)=S(0) pe cada nume al n Finalmen , si, pe no es pos ulacions, enim (10)  F k(k)=Eh(k) pe cada nume al k ambé ind em (11)  F- -i k(n)=0 pe cada nume al n, i podem alesho es, segons PR .3, in odui pos ula s que acin que (12)  H Ek=O AiXI, doncs, si F(x) és de Cauchy es sa is á (12) . P ocedim a a a la in e sa . Suposem donada una successió de acionals F(x) i anem in oduin , successi amen , pos ula s que acin que es complei- xin (3), (7) i (10), pe ce s ope ado s g, Suposem que alesho es po- den demos a (12) . Pe l'esquema (IV) (pe k) es sa is a lla o s (11) ; i, 5 7 segons (10), es sa is a (9) . Pe o alesho es ind em (8')  F- h{n,Mh(n))=0, pe cada nume al i aixo ol di , pe (7), que (6')  !- Eg(n,MF(n))=0 pe cada nume al que signi ica, pe (IV), que (4')  H -i g(n,Mh(n), )=0 pe qualsse ol nume als n i . Finalmen , segons (3), (2')  F- I(x,n)1(y,bíh(n))1(z, )=0 pe qualsse ol nume als ne a que F(x) és de Cauchy . n, n, Així, doncs, en esum : si, a pa i d'una succeisió de acionals F(x), in odu m uncions g(> :,y,z), h(x,y) i k(x) que sa is an (3), (7) i(10), alesho es F(x) is de Cauchy si i nomás si li- Ek=O . A a bé, les in oduccions d'aques es uncions es : poden e de mol es ma- ne es . Si en lloc d'el .les in oduim g'(x,y,z), h'( ,y) i !'(x) no podem a i ma (pe que no diFposem de PR*) que les ó mules -1Ek=0 -4 E!'=0 i -1 Ek'=0 Ek=0 siguin eo emes . Aixo ás, les ó mu : .es Ek=0 i E!'=0 no s6n equi alen e, malg a el e que H Ek=0 si i nomás : ;i F- Ek'=0 . n i , de ma- Di duna al a ma e a, si pensem en la ase "F(x) és de Cauchy" com a a i mac .i .ó suscep ible de se e dade a o alsa, aques a ase no é una aducc .ió canónica en una ó mula (o en una classe d'equi alencia de ó mu- les)del llengua ge . Una si uació semblan es p esen a quan s'ha c .e pa la de successions de Cauchy que endeixen a ze o, de la noció d'o d e en e successions de Cauchy, e c . 4 .5 . Demos ació co ns uc i a de la consis enci a i del me a eo ema de minimali zació . 4 .5 .1 . P elimina s . Supose m que A és una col-lecció de o mules cons- an o . Di em que una llis a ini a de o mules, A l , A 2 , . . 5 8 is una deducció a pa i de A si cada memb e A, 2 de la llis a sa is á una de - les condiciona seguen s : A-Ded .l . A, és un elemen de A . . s A-Ded .2 . A . és de la o ma -i b=c c=b, on b i c eón e mes cons an e . A-Ded .3 . Hi ha algun memb e A . de la llis a, an e io a A,, i alguna o mula quasia ómica cons an B, als que A,iA . V B . A-Ded .4 . Hi ha memb es Aj i Ak de la llis a, an e io s a A ~i , i alguna o mula a omica cons an b=c, als que A . = A . V b=c i A k _ . A . V --ib=c . Al amen di , una al llis aés una deducció a pa i de A si cada mem- o e de la Mis a pe any a A o es po dedui de memb es an e io s de la llis a segons les egles R .I .l, 2 i 3 ' (en el cae de R .I .3, A, s'in e eix de dos memb es an e io s ; en el cae de R .I .2 s'in e eixd'un memo e an e io ; en el cae de R .I .1 pod iem di que A, s'in e eix de ze o memb es an e io s) . R Si una o mula C és memo e d'algunadeducció a pa i de A di em que C es dedueix de A, i esc iu em A b C Si A cons a de o s ele pos ula s d'un segmen U 1'a i mació an e io coincideix amo 1'a i mac ó "C és un eo ema de U", que, com ja s'ha di , ambé s'esc iu U 1- C . Pe qualse ol unció 1P del conjun de ó mules cons an e en el conjun esc iu emF(A)=V o F(A)=F pe indica , espec i amen , que el alo de F en la o mula Aés Vo F . Una al dnció F és una alo ació si sa is á les condiciona següen s : V .1 . F(b=c) = F(c=b), pe qualsse ol e mes cons an e b i c . V .2 . V, si F(~ b=c) =F F(b=c)  _  _  pe qualsse ol _b i _c cons an e F, si F(~ b- - c) = V~ V . 3 . Pe qualsse ol A 1 , . . .,A n quasia ómiques, d=á 1 , á2 , . . . , á =c- al que cada di,, s'ob é de en subs i ui pe c .  una p esencia de -q (i) bpe algun j(i) (de 1 a ) . Com que A és Glosa les seguen s o mules pe anyen a A : Com que H és compa ible amo aques es o mules i amo les iden i a sbási- ques ambéhau á de se compa ible a ib 6 6 3 (1) ~ (1) V ~ Cj (2) -b7 (2) V _b  , d =a V d  =c -3 ( -1) - ~ ( -1)  -  -- -1 - d =c V d _1=c - - - , d _1=c V á -2=c -1 d 3 =c V d 2 =c á 2 =c V á 1 =~ Pe ó =c i c El F , de mane a que c=c pe any aA .¡ H(c=c) s V . Pe an H( _1 c)_V . Usan a a les ó mules següen s anem ob enin H( -2 =c)5V , . . ., H(d l =c)=V, aixo és H(d=c)=V . , 1 2 =c á l= c _'!13=c Vá2=_c De mane a semblan mos em que H( =c)=V=H(c= ) Conside em a a les seguen s ó mules de A : -C . =b . V -~ d2  - = d1 = -  (1) ~ (1) -  - Cj ( -1) bj ( -1) V  V -1= P ocedin com abans ob ind em H(d= )=V . Di em que una alo aci6 és A- no mal , pe una A ini a Glosa, si és A- dis ingida, compa ible amo A i mínima amo aques es p opie a s (segons 1 , o - d e pa cial 9 ) . Una alo acióA-dis ingida i compa ible amo A se á A-no mal si i només si no podem sup imi cap iden i a básicasense que deixi de se compa ible amb A (o bé si no hi ha cap iden i a básica) . A con inuació p ocedi em ecu si amen pe a e el segmen : donada qualse olcol " lecció ini a A de pos ula s d'un segmen . conside a emuna col " lecció ini a B de pos ula sdel ma eix segmen que se á closa i con- ind á A ; cons ui em alesho es o es les alo acions B-no mals, que cons- i ui an una col " lecció ini ano buida, i eu em que cada alo ació com- pa ible amh B és compa ible amb o es les iden i a s básiquesd'alguna d'a- ques es alo acions B-no mals i és, pe an , pos e io a ella ; i al ma eix emps demos a em alguns al es e s in e essan s . To aixó ens pe me á de demos a la consis éncia de cada segmen i el me a eo ema de minimali za- ció . 4 .5 .2 . Les demos acions . Conside em qualse ol segmen U . Aques seg- men , obé és el segmen inicial o s'ha d'ha e ob ingu , a pa i del seg- men inicial, pe un segui d'adjuncions de pos ula s, d'aco d amb PR .2 i PR .3 . Cada adjunció ha de e mina un segmen , de mane a que enim una suc- cessió de segmen s U O , Ul , . . . , Un al que U 0 és el segmen inicial, U n és U i, pe cada i<n, Ui+l s'ob éde Ui pe adjunció d'unsesquemes de pos ula s (I)-(VII), d'aco d amb PR .2, o pe adjunció d'un esquema (VIII), d'aco d amb PR .3 . Conside em qualse ol conjun ini A de pos ula s de U . A egim a A casos de E .P.I .l, 2 i 3 ins a ob eni una col " lecció ini a closa B que con é A . Rep esen em la col , leccióde memb es de B que són pos ula s de U i pe Bi . Es cia que cada B, i és closa . Desc iu em pe cada B i , ecu si amen , la col " lecció de alo acions B i .-no mals, al ma eix emps que ani em demos an les a i macions segmen s : a .) La col-lecció de alo acions Bi -no malsés ini a i no buida . i b i ) Cada alo ació compa ible amb Bi és pos e io á una de les alo a- cions B,-no mals . 1 c .) Pe qualse ol ope ado h de g au p+1 i qualsse ol nume als b l , . . ., i bb , si F(Eh(bl, . . .,bb)=S(0)) =V pe cada alo aci6 B 1 .-no mal F, alesho es Mh(bl, . . .,bn) és un U 1 .-nomb e . di ) En cap de les iden i a s básiques de cada alo aci6 Bi -no mal no hi apa eix cap ope ado nou pe U i . La nos a i-éssimahipó esi d'inducci8 o ecu si6 se a que es sa is an a .), bc .) i d i ) pe qualse ol col " lecció ini a closa B de pos ula s de [l . Conside em el cas i=0 . El conjun BO és unió duna col " lecció ini a B0 de casos de E .P .I .1 i una col " leccié ini a de casos de E .P .I .2 i E .P .I .3 . La única alo aci6 B O -no mal és la alo aci6 BO -dis ingida que no é cap iden i a básica, alo aci6 que al V en o es les o mules c=c que pe a- nyen a B¿ i al F en o es les al es o mules a ómiques . Es eu ácilmen que es sa is an a_), b_), c_), d_) . U  U - V  V Suposem a a que enimcons uida la col-lecci6 de alo acions B i .-no - mals, i que es sa is an ai ), b i ), ci ), d i,) . Hem de desc iu e les alo a- cions B,+, no mals i mos a que es sa is an les condicions análogues . Hi ha dos casos . P ime cas . Si Ui+1 s' ob é de Ui pe PR .2 . En aques cas Ui+1 s'ob é d'a egi als pos ula s de Ui els esquemes (I)-(VII), pe uns ce s e mes ,s i algun ope ado , que sa is an les condicions de PR .2 (pe U=U,) . Pensem, pe comenca , en les ope acions de les dues menes següen s, a pa - i duna alo aci6 Bi+l-dis ingida G : d, de inin així una no a alo aci6Bi+l-dis ingida G' . 68 11 ) Si , j(x i ,b)=d (b1, . . .,bn,0)=d és un cas de (I) que pe any a Bi+1' Si G( j(x i ,b i )=d)= V, i si (bl, . . .,b l,0) no es á p esen en cap de les iden i a sbásiques de G, a egi a aques es la iden i a (b l ,.. .,b z_ )_ 2á) Si la o mula -, 2-1 (x i ,bi) 1 (Y . c) I (z, (b l ,. . .bn,c))=d (b l , . . . ,bn ,S (c))=d és un cas de (II) que pe any a Bi+l, si G(sI(x i ,bi)I(y,c)I(z, (b l   b n ,c))=d) = V , i si (b l ,.. . . b n ,S(c)) no es á p esen en cap de les iden i a sbásiques de G, a egi (b 1   n ,S(c))=d a aques es iden i a s, ob enin així una no a alo ació B i+l- dis ingida G' . Conside em a a qualse ol alo acióB,-no mal F . P enem GeF en les des- i c ipcions de les ope acions an e io s i e ec uem, si podem, una ope ació de qualse ol d'aques es dues menes, ob enin així una no a alo ació Bi+l dis ingida F' . P enem a a, en les desc ipcions an e io s, G=F' i o nem a e ec ua , si podem, una ope ació duna d'aques es menes, e c . Ob ind em ai- xí, inalmen , quan ja no poguem e ec ua cap d'aques es ope acions, una alo ació B i+l - dis ingida F1 , que é les p opie a s sequen s : F1 és pos e- io a F i és compa ible wnb o s els casos de (I) i (II) que pe anyen a Bi+l' i cada alo aciópos e io a F que és compa ible amb o s aques s ca- sos és pos e io a F1 . Aques es obse acions es comp o en ácilmen (pod i- em eni di icul a s si oblidéssim alguns de alls als com, pe exemple, que pe cap alo ació dis ingida H no és possible que H(b=c)-_H(b=,c' )=V si c i c' són nume als di e en s) Pensema a en les ope acions de les es menes seguen s, a pa i duna alo ació Bi+l dis ingida G : 3 1 )  Si ~ (1 1 ,. . . . bn ,0)=0 V M (b l ,. . . . b n )=0 és un cas de  (III) 0 que pe - any a Bi+l, si G( (b1, . . .,bn,0)=V, i si M (b l   bn ) no es .T p esen en cap de les iden i a sbásiques de G, a egi M (bl, . . .,bn)=0 a aques es iden i a s, ob enin així una no a alo acióBi+l-dis ingida G' . 4 á)  Si la ó mula (111 ,.. . . b n O)=0 .  Q1 1 ,.... b n O)=0 . . . V (b l , . . . . bn,c)=0 V  -n (b1, . . . . bn ,S(c))=0 M (1 1 ,.. . . bn )=S(c) és un cas de  (III)' que pe any aBi+1' si G( (b1, . . . . bn,S(c))=0) _ , G( (b1, . . .,bn .0)=0) a . . . = G( (bl, . . .,bn,c)=0) i si M (b1, . . .,bn) no es á . p esen en cap de les iden i a s básiques de G, a egi M (b l , . . . . b n )=S(c) a aques es iden i a s, ob enin aixi una no a a- lo ació Bi+l dis ingida G' . 5 1 ) Si la ó mula 7 0 F -, (b1, . .  bn,S(c))=0 . M (b l ,.. . . b n )=S(c) és un cas de (III)' que pe any a Bi+l, si G( (b1, . . . . bn S(c))=0)  . G( (b1, . . .,bn,0)=0) a . . . a G( (bl, . . .,bn,c)=0) (11 .. . .,bn,0)=0 (21, . . .,bn,S(0))=0 y . . .y (1 1 , . . . . bn ,c)=0 G(M (b,, . . . . b_)=S(c))  a F  , - 1 -1l i si d és un nume al de la llis a 0, S(0), . . ., c al que (bl, . . .,bn,d) no es á p esen en cap de les iden i a s básiques de G, a egi (b l ,.... b n d) a aques es iden i a s, ob enin així una no a alo ació Bi+l dis ingida G' . To nem a a a conside a qualse ol alo ació Bi -no mal F, i conside em la alo ació F 1 que hem ob ingu abans pe ope acions de les menes 1 1 ) i 2á) . E ec uem, si podem, p enen G=F 1 , una ope ació de les menes 3á), 4á), 5á), ob enin així una no a alo ació Bi+l dis ingida Fi ; p enem a a G=Fi i o - nem, si podem, a e ec ua una d'aques es ope acions, ob enin una al a a- lo ació Bi+l-dis ingida F1, e c ; ins a a iba a una alo ació F 2 pe a la qual ja no és possible (pe G :-:I 2 ) e ec ua cap ope ació de les di esmenes . La ope aciócompos a que ens po a a F 2 es po e , en gene al, de mol es ane es di e en s . Conside em o es les alo acions que es poden ob eni a pa i de F de la mane a indicada, que deno a em F 2 .1' F 2 .2'  . . ., F 2 . ' Tind em alesho es que cada F 2,j és una alo ació B i+l -dis ingida pos e io aF compa ible amb o s els casos de (I), (11), (111) 0 , (111)', (VI) i (VII) que pe anyen aB i+l , i que cada alo ació pos e io a F compa ible ambels di s casos és pos e io a algunade les F 2,j' Pensem a a en les ope acions de la mena següen , a pa i duna alo a- ció Bi+l-dis ingida G : 6á) Si -n (bl, . . .,bn,c)=0 V E (bl, . . .,b)=S(0) és un cas de (IV) que pe any a Bi l' si G( (bl, . . .,bn,c)=0)=V, i si E (bl, . . .,bn) no es á p e- sen en cap de les iden i a s básiques de G, a egi a aques es iden i a s la ó mula E (bl" . .,bn)=S(0), ob enin així una no a alo ació Bi+l-dis- ingida G' . Escollim una F 2,j i em, pe G=F 2,j, una ope acióde la mena 6á), si és possible ; amb la no aF',jaixí ob inguda o nema e una ope ació d'a- 2 ques a mena, e c, ins a a iba a una F 3,j pe a la qual ja no es po e cap ope ació d'aques a mena . A pa i de cada F 2 .J ob enim aixi una sola F 3,j . Tind em alesho es una col-lecció de alo acions, F 3,l, F3,2' F 3, , que enen les p opie a s seguen s : Cada F 3,j és una alo ació Bi+l dis ingida pos e io a F compa ible amb o s els casos de (I), (II), (III) 0 , (III)', (IV), (VI) i (VII) que pe anyen aB i+l ; i cada alo aciópos e io a F i compa ible amb aques s casos és pos e io a algunade les F 3,j - Conside em, pe acaba , les ope acions de lamena següen , a pa i d'u- na G que sigui Bi+l-dis ingida : 71)  Si E (b l , . . . . bn )=0 V E (b l , . . . . b n )=S(0) és un cas de  (V) que pe - any a B i+1' i si E (bl, . . .,bn) no es á p esen en cap de les iden i a s básiquesde G, a egi a aques es la iden i a ,E (b l , . . ., bn)=0 o la iden i- a E (bl, . . .,b)=S(0), ob enin així una no a alo ació B i+l -dis ingida G' . Escollim algunaF 3 , j , em GZF3,j i em, si podem, una ope ació de la me- na 7á) ; amb la alo ació així ob inguda o nem a e , si podem, una ope a- ció d'aques a mena, i aixi successi amen ins a iba a una alo acióamb la qual ja no poguem e cap ope ació de la mena 7á) . Com que aques segui d'ope acions es po e de mol es mane es di e en s ub ind em, a pa i de cada F3,j, una col " lecció de alo acions,  F 3,j,1'  . . . .  F3,j,n(j)- Can iem de no ació,  designan les alo acions F 3 1 1  ,  . .  1  F 3, ,n( )  pe El 4,1 ' . . . ' F4, (F)' Tind em alesho es : cada F 4 j és una alo ació B i+l - djs ingi - da pos e io a F compa ible amb Bi+l ; cada alo aciópos e io a F compa i- ble amb Bi+l es pos e io a algunade les F4,j' Can iem no amen la no ació, i designem pe G1 , G 2 , . . ., GW els elemen s de la unió de les col-leccions {F4 1' . . . .F4, (F)1, pe o es les alo acions Bi+l-no mals F . Es comp o asensemassa di icul a que les G i són les alo acionsBi+l-no mals, i . que es sa is an a l+l )' b i+l )  i d i+l )' Comp o a em a a que ambé es sa is a c i+l ). Si h és , les condi- cions G (E (b_ _b )=S(0)) s V (pe cada j) signi iquen que no hem ingu _ : _1 1 u  - ocasióde e cap ope ació de la mena 7a ) (ja que en cas con a i ind iem, pe algun j, que G .(E (b1, . . .,b)=0) a V) ; pe o ambé ol di , alesho es, J -  - Ze hem es a obliga s a e G J .(E (b1, . . .,bn)=S(0)) aV pe una ope ació de -  - la mena 6á), pe cada j, cosa que implica que hi ha algun nume al c, al que Gj( (b1, . . . . bn ,cj)=0) = V . Aixo implica, segons b i+l ), que G( (b1, . . .,bn,c1)=0 V . . .V (b1, . . .,bn,cw)=0) a V pe cada G compa ible amb B i+l i, segons el lema 4 .5 .1 .1, que M (b 1 , . . . l b n ) is un U, , ,-nomb e . Suposem a a que h no és , i que Gj(Eh(b1, . . . . bn)=S(0)) V pe cada G J . . Conside em, pe cada j, la alo ació Bi -no mal F a la qual - G j és pos e io . A i mem que F(Eh(b 1   b p )=S(0)) a V . E ec i amen , en ana de inin , a pa i de F, mi janQan ope acions de les menes l a ) - 7a ), les alo acions que ens po en inalmen a G J., no can iem el alo F(Eh(b1, . . .lbn)=S(0)) ; de mane a que, com que pe cada F que és B i -no mal 7 2 hi ha una G . pos e io a ella, ind em F(Eh(bl, . . .,b)=S(0)) a V pe cada 7  - alo ació B1 .-no mal i, pe hipo esi ecu si a, Mh(bl, . . .,bn) és un U i -nom- b e . Pe o cada U i -nomb e és U, + ,-nomb e . Així s'acaba la demos ació en aques p ime cas . Segon cas . Si Ui+l s'ob é de U i pe PR .3 . Sense pe d e gene ali a , po- sem i+l en lloc de i . D'aques amane a podem ap o i a la discussió del p ime cas sense can ia de no ació, si suposem que els segmen s U i V de PR .3 són U i i U i+1' espec i amen . El segmen U i+2 és el que s'ob é d'a e- gi a Ui+l 1'esquema (VIII) : H -~ (h l k l ) ~(z i ,~)  V . . .V  (hp kp ) j(z i ,-) ~glj (z i' d )-b1 V . . .V -~  I(z i , d )=bn V -~El (b1__bn)=S(0) amb el supos que hl, . . .,hp,kl, . . .,kp,~l, . . .,~n són U 1 .- uncions-de z l ,.. ., z q i que, pe qualsse olnume als d l ,.. .,dd c, (1)  U i+l 1- -1 (h 1 =k 1 )I(z i ,d i ) V . . .  (hp k p ) j(z i ,di ) V ' (911bi,dd) .. . . .an1(zi,d Ii ),c)=o la nos a asca, en aques segon cas, se á la de sup imi les G . no com- 7 pa ibles amb B i+2 . Hau emde eu e que les omanen s se an les Bi+2-no - mals, i que sa is a an a i+2 ), b i+2 ) ' c i+2 ) i d i+2 ) . Suposem que els casos de (VIII) que pe anyen a B i+2 són (hlk l )I (z i ,  ) V ... V -, (- p -p ((zi,di) ,1ll(zi,dz)=bi 1/ . . .V .~gnl(zi,di)=  V -,E (bi, . . .,b )=S(0) pe jal, . . . . , on els d,  i b,  són nume als . Les alo acions no compa ibles amb B i+2' que hem d'elimina , són les G k que sa is an, pe algun j : (2)  Gk ( (hlk l )  (zi ,d1) .) a . . . aGk ((-p k~) I (z i ,R)) a G k (g 1 I (z i ,  )=bi) . . . a Gk (gn1(z i ,~)=b)= Gk(E (bi, . . . . b3)=S(0) = V La p ime a cosa que hem . d e eu e és que no sup imim d'aques a mane a o- es les Gk . Usem, pe simpli ica , la no ació Suposem, en con a del que olemdemos a , que cada Gk sa is a (2) pe algun j . Suposem alesho es, amb la no ació del p ime cas, que Gk és pos e io a F 3, . Obse em que Pensem en o s els indexs j als que Si, en el p océs d'ob eni Gk a pa i de F3 , haguéssim ingu opo uni- a de e alguna ope ació de la mena 71) en elació a la o mula pe cada un d'aques s j, hau iem pogu cons ui una alo ació G k, al que, pe cada un d'aques s j, i, pe an , i ind iem alesho esuna alo ació Bi+l-no mal G k, que no sa is a ia (2), con ael que es em suposan . Alxl, doncs, si cada Gk sa is a (2) hi ha d'ha e , pe cada k, un índex j(k) que sa is a (2) al que i pe al qual no enim, a pa i de F3 , ocasió de e cap ope ació de la mena 7 1 ) ela i a a la o mula j (k)  j (k)  j (k)  j (k) El(b1, . . .,b  )=0 V E (b l , . . .,bn  )=S(0) , i aixo ol di que 74 A 3 a (h =k )i(z .,d3), pe lí<s,<p S  -S -s  i i -A P+  g ' (Zi'-dy,)-b ' Pe l~ 6n Gk (~) = F3 W ) pe 1-i<p+n F 3, W ) = V pe 1L--i :lp+n E (bi, . . .,~)=0 V E (bi, . .- l b )=S(0) Gk,(E (bi, . . .,b3)=0) z_ V Gk,(E (bi, . . .,b1)=S(0)) aF F  (A~ (k) ) = V pe l*i< .p+n 3, -2  - F3, (E (bi(k), . . .,b(k))=S(0)) s V Pe ó si a a pensem en la alo ació F2 de la qual s'ob é F 3, pe una ope ació de la mena 6á), eiem que alesho es hem de eni un nume al ck al que F2, ( (bi(k) . . . bn ( i k )=0) s : V Obse em que F 3, al el ma eix que F 2 en la o mula an e io . Fem Tenim, doncs : Si cada Gk sa is á (2) pe algun j, podem oba , pe cada k, un índex j(k) i un nume al c k als que Aixo úl im ol di que (3)  G k ( Ai( 1 1) V A .  V . . .V ~(w)) - V , pe cada k i cada unció i de l1, . . . . wi en Si, . . . .p+n+11 . Gk ( 1 A ~(k))  s : V pe l*ií5p+n+l Dona que les Aj (k) són ó mules a omiques, la hipó esi d'inducció ens R diu alesho es que cada alo ació compa ible amb Bi+1 al V en les o mules (3), i el lema 4 .5 .1 .1 ens diu que B i+l F A .(1) V . . . VAi(w)  Pe cada i :il, . . .,w}i l, . . .,p+n+1} i, pe an , (4)  u  F  A ](l) V . . .V A7 y . (w)  pe cada  . . . .p+n+l1 i+l i(1) -(w) Reco dem ambé que (1) implica, pe cada k, (5)  U i+1 F -, A1 V . . . V ~  V  (911 (zi,d  (k))  (z,,--l (k) ),  )=0 -1  Ek Tenim, doncs, en esum, que si cada Gk sa is és (2) pe algun j, s hau- ien de sa is e (4) i (5) . Pe o, usan alguns casos de E .P .I .3, no és més que un exe cici el mos a que de (4) i (5) es dedueixen Ui+1} (bi(k) . . . .b ;(k)Ek)=0 A a bé, aixo no és possible : en aques cas pod iem oba una col " lecció ini a closa B i+1 de pos ula s de 5i+l de la qual es dedui ien les dues