Significato e verith nell'aritmetica peaniana (*)(*% I~O~E~TO ~ A G ~ I

(Siena)

A Beni~mino S~G~E nel suo 70 m° complcanno Stmto. - Partendo da aleune esigenze di earattere neopositivistico si propone un eoncetto di verith dizerso da quello tarskiano e si costruiseono sistemi logiei che, in un senso che viene chiarito, s]uggono alle eonsuete limita~oni deduttive ed espressive.

Summary. - Starting ]rom some ({philosophieal ~>consideration, we propose a non-tarskian concept of truth and we consequently construct systems which, in a reasonable sense, avoid the ,usual expressive and deductive limitations. (See also [14], which is a short summary in english of this paper).

Premessa. U n notissimo t e o r e m a d o v u t o a T A ~ s x I [25] afferma che n o n esiste Meuna espressione V(x) d e l l ' a r i t m e t i c a p e a n i a n a per cui si a b b i a : ~ V(~) s e e solo se ~ p (per ogni proposizione chiusa, p , Ml'aritmetica) (qui e nel seguito ~ sta per il n u m e r M e det g6deliano d i p e ~ p p e r ~p 5 v a l i d a in o~ ~>) (~). A e c a n t o Mle limitazioni d e d u t t i r e d o v u t e a GODEL la limit~zione espressiva d a t a dM t e o r e m ~ di Taxski costituisce, natuxMmente~ u n o dei risult~ti basilari di cui deve t e n e r e o n t o ogni m o d e r n a discussione sutl~ m a t e m a t i e a . T u t t a v i a i t e o r e m i l i m i t a t i v i d e v o n o essere <~letti ~>con e s t r e m a cautela~ e v i t a n d o di c o n f o n d e r e i concerti usati nella d i m o s t r a z i o n e c o n i e o r r i s p o n d e n t i concerti pifi o m e n o v a g h i del senso c o m u n e (ineluso il senso c o m u n e fflosofico). I1 c o n c e r t o rigoroso di verit~ u s a t o da TIRSKI (e d a Mlora us~to e o m u n e m e n t e in m e t a m a t e m a t i c a ) n o n deve essere a c c e t t a t o di neeessit£ c o m e l ' u n i c o che in qualche m o d o r e n d a c o n t o di cib che il senso e o m u n e i n t e n d e per ~ verit~ ~>o di eib che p o t r e m m o desiderate o p r o p o r r e di i n t e n d e r e per veritY. S e e o n d o u n ' o s s e r v a z i o n e di B. RUSSELL ([22], cap. I I , 13) u n a ffase ~ u n a proposizione (~ eiob sens~ta) se ~ v e r a o fMs~. (*) E n t r a t a in Redazione il 30 giugno 1973. (**) Lavoro eseguito nell'ambito dell'a~tivit~ dei gruppi matematici del C.N.R. (a~no 1972, gruppo G.N.S.A.G.A.). (1) Qu~sto lavoro presuppone solo nozioni istituzlonali di logica ~ di ~eoria delle funzioni ricorsive per le quMi si rimanda a uno dei numerosi tes~i esistenti. Per 1~ teoria delle funzioni ricorsive ci si ~ ri:feriti in genere a H. ]~OGV,RS [20] ¢ per Is logica al testo istituzional~ di E. ~END]~LSON[16] e al trattato di J. R. SHO~ENFI~I,D[22].

344

ROSE,m0 MA~AR~: Signi]icato e verit5 nell'aritmetica peaniana

D ' a l t r o n d e secondo un'esigenzs di carattcre neopositivistico u n a frase 6 sensat~ se esiste un m e t o d o per verificarla (oppure, come suggerisce K. PoPPE~ in [17], per falsificarla). Ciascuna di queste osservazioni (2) h a u n suo contesto e h a d a t o luogo sviluppi e a discussioni lungo mezzo secolo di v i t a filosoficz. Qui ci interess~ per ora prenderle nel loro significato pifl ingenuo e i m m e d i a t o e applicarle in m e t a m a tematica. T r o v e r e m o che ~ proponibile la tesi (o l'esortazione, cfr. n o t a (2)) che non t u t t c le proposizioni dell'aritmetica p e a n i a n a sono sensate e che, dando u n ' o p p o r t u n a deftnizione di proposizione sensatu e limitando la definizione del predicato di verit~ alle proposizioni sensate, la limitazione t a r s k i a n a viene a cadere. Inoltre, c o m b i n a n d o il p u n t o di v i s t a qui i n t r o d o t t o con quello i n t r o d o t t o in [13], si pub costruire un sistems che 6 esente sia dalle limitazioni espressive che da quelle d e d u t t i v e e ehe, in u n senso che si ehiarir~, pub essere assunto come proprio m e t a s i s t e m a senza che si manifestino i difetti, per cosi dire, di aderenza fra linguaggio e metalinguaggio cui i logici e i filosoft della m a t e m a t i c a sono a w e z z i . D a l p u n t o di vista tccnico questo lavoro non presenta difficolt~ di rilievo: si t r a t t a di precisare a qusle tipo di logica conduce u n certo a t t e g g i a m e n t o filosofico e i risult a t i noti di logica e di teoria delle funzioni ricorsive sono pressoeh6 sufficienti alla bisogna anche se~ all'occorrenza, per maggior chiarezza~ si d a r a n n o dimostrazioni di f a t t i che sono pifi o m e n o scontuti. D ' u l t r o canto il lavoro 6 dedic~to pifi s itlustrsre u n p u n t o di v i s t a che a difenderlo; te considerazioni (( filosofiche ~ che si d o v r a n n o fare per i n t r o d u r r e l ' a r g o m e n t o si munteITanno perci5 a u n livello rozzo. L ' a u t o r e si riserv~ di srricchJrle e chiarirle qualora it p u n t o di v i s t a qui esposto risulti ~bb~st~nzs interessante da suseiture delle critiche. ~3 o p p o r t u n a t u t t ~ v i a qualehe eonsiderazione introduttiv~. Mentre 6 10ossibile vedere la m a t e m a t i c s come costitnita di sistemi formali, lasciando a chi intenda applicarli la responsabilit~ di fornir loro dei contenuti, la cosa non 6 a l t r e t t a n t o agevole per ls m e t a m a t e m a , tica, intesa come seienza, a p p u n t o , dei sistemi formuli. Se, u n s volta dimost, rat% per esempio~ la consistenza di u n dato sistema formate/~, ei inertia.too in u n a condizione m e n t a t e per cui s s r e m m o e s t r e m a m e n t e sorpresi dalla seoperts d i u n a contraddizione in /7, b chiaro che non ei l i m i t i a m o a constatare di aver dedotto, nella m e t a t c o r i a / " impiegata, u n a certa sequenza di segni. I n altri termini, in quanto ne t r a i a m o a s p e t t a t i v e , la m e t a m a t e m a t i c a assume uno stato analogo s quello delle scienze naturali ed 6 sostenibile che si t r a t t i proprio d i u n a scienza nsturale. Va ds s6 che niente proibisce che si sviluppi, per riprendere i simboli precedenti, /v, come puro sistema formale, cosl come del resto niente proibisce ehe si sviluppi come puro sistema formale is meccanica. Perb in tal caso non 6 lecito o v v i a m e n t e t r a r r e infcrenze e a s p e t t a t i v e su 17 da quando si 6 dimostrat.o in F'~ non pi~ di q u a n t o sia lecito t r a r r e da u n t e o r e m a di meeeanica (~) La~ paxola <(ossQrvazioni ~ ~ fors~ impropria. Si potrebbe sostenere the si tratta piuttosto di prescrizioni o esortazioni circa i linguaggi da costruire ed usare.

ROSE,TO MASA~: Signi]icato e verit5 nell'aritmetica peaniana

345

<~formals ~ inferenze e aspettative sui m o v i m e n t i della Lnna, se non si sono fissate a p p u n t o dells interpretazioni in termini di osservabili dells proposizioni (o di alcune proposizioni) della meccanica <~formals ~>. Siano allora F, /~' come sopra e supponiamo di voler definire in F ' il concerto di <~verit~ ~>per le proposizioni di F. ]~ chiaro che, se vogliamo poter poi discutere sulla possibilit~ o meno da parte di /~ di <~esprimere ~>il concerto di verit~ che avremo introdotto, dobbiamo riguardare ~ stesso come u n f r a m m e n t o di F ~, quindi in qualehe modo come p a r t s di una scienza naturale, e percib t r a t t a r e i concerti di proposizione sensata e di verit~ secondo le esigenze che appliehiamo di solito alle scienze naturali. Questo ci porta a isolare fra le proposizioni di /7 una sottoelasse S di proposizioni da chiamarsi <~sensate ~> cd a definire solo per quests il concerto di veritY,. Oecorre ora n a t u r a l m e n t e avanzare dells precise proposte per il concerto di ~ sensatezza ~>:g quanto si farm nel seguito, cercando di mostrare che, se si accettano esigenze di tipo neopositivistico, allora non ogni proposizione di F ~ <~sensata ~>. I n t u t t o il lavoro ei si riferir~ all'aritmetica peaniana, ma questa restrizione inessenziale. Sin /~ l'insieme delle proposizioni dell'aritmetiea peania~na e T l'insieme d e l l s sue tesi: u n p u n t o di vista molto restrittivo sul concerto di sensatezza porterebbe a ehiamare sensate le proposizioni dell'insieme S = T ~d { ~ p : p ~ T} e, per conseguenza, vere le proposizioni di T. Avremmo una t e r n a con S, T ~ X~ n e l l a gerarchia aritmetica ed ~ facile vedere che, una volta accettato un concerto di verit~ eosi restrittivo, un tal sistema sfuggirebbe in un certo senso alle ordinarie limitazioni (l'asserzione della sun consistenza sarebbe per esempio ovviamente insensata e cosl la proposizione indecidibile di GSdel, ecc.). I1 sistema <-P, Po, Vo> che studieremo ha molts analogie col banale sistema sopra considerato, solo the si h a / ) o , Vo e X2. Mutatis mutandis per un simile sistema si r i t r o w n o facilmente i risultati classici noti per e percib Vo come insieme delle proposizioni ~(vere ~>.

1. -

Teorie formali

e limiti.

Da u n p u n t o di vista a s t r a t t o possiamo chiamare teoria formals (in senso <~calcolistico ~) ogni coppia
846 (1,1)

I~0B~.RTO M A h d i : Signi/icato e veritd netl.'aritmetica peaniana P ~ un insieme decidibile (insieme delle proposizioni),

(1,2). / ' ~ un sottoinsieme enumerabile non vuoto di P (insieme delle tesi). Si pub supporre senzu perdita di generalit~ che sia P - = (9 e identificare allora addirittur~ il concerto di teoriu formale col concerto di sottoinsieme (ricorsivamente) enumerabile di co. I n genere, naturalmente, si avrh, a c h e fare con una situazione pifi ricca. Avremo cio6: (i) u n operatore di Moore ulgebrico H sui sottoinsiemi di P ehe associ~ ~ sottoinsiemi enumer~bili di P sottoinsiemi ~ncor~ enumer~bili, con Hql = T. (ii) alcuni (( connettivi ,> con condizioni di compatibilit~ con H. Riferendoci per sempticit£ al caso in cui si hanno (( t u t t i ~ i connettivi, eib significa avere per ogni ] e [J 2~', eio~ per ogni ~(funzione verit~ ~), una operuzione ricorsivu della stessu ariet£ su P (che si indicher~ ancora, con f) con le propriet~ (1,3)

se p ( x , , x~, ..., x~; y~, Y2, ...~ Y~,) -~ q(x,, x~, ..., x~; z,, ..., zz) ~ un~identit~ polinomi~le boolean~ ullor~: H{p(xl,

(1,4)

..., x~; y , , ...,

y~)} =

H { q ( x l , ..., x~,; z l , ...,

z,)}

(x~, y~, z~e/))

L'equivalenz~ in _P definit~ da:

x~-,y s e e solo se H(x} = H(y}

(1,41)

(x, y e P)

compatibile con le ]. (1,5)

L'oper~tore indotto da H sul quoziente P/.-~ (che risulta, in virt~ delle (1,3) (1,4), un'algebra di Boole) coincide con l'operatore di passaggio al filtro generato.

I n re~lt~ 6 safficiente, come 6 ben noto, supporre di disporre, oltre che dell'operutore H, di due funzioni ricorsive -% c corrispondenti rispettivamente all'opera zione booleuna di tavol~: 0

1

1

1

0

1

e ulrol0er~zione di valore costante O, con le propriet~ (1,3), (1,4), (relative ai soli polinomi nelle operazioni considerate) e: (1,51)

H{c} =

(1,52)

yeH(XW(x})

se c solo se x ~ y ~ H X

(Xc~P;x,y~P).

ROB]~TO ]YIAGA~Z: Signi]icato e verit~ neU'aritmetica peaniana

347

]~ anche ovvio che, noti P, T, -% la (1,52) d c t e r m i n a H . Se si accetta in particolare la tesi di CHvncH il concetto di teoria formale sopra indicate pub essere considerate come u n a valida c o n t r o p a r t e rigorosa del concetto r a g e di teoria d e d u t t i v a < o ~. ]~ b e n n o t e come ci si sia i m b a t t u t i helle cosiddette <. I n genere l'insieme P ~ costruito o i n t r o d o t t o in m o d e tale che nel linguaggio usato (< rispetto a ( P , T}) si definisce in m o d e < (seeondo la p r o p o s t a t a r s k i a n a ) u n concetto di <,si privilegia cio~ u n certo sottoinsieme V di P la eui considerazione proviene, in u n m o d e che non ci oceorre per era rieordare, dalle intenzioni (espresse o inespresse) che h a n n o p o r t a t o , nel e~so concrete di v o l t a in volt~ in esame, alla eostruzione di ( P , T>. (V sar~ di solito l'insieme delle propoposizioni (~v~lide ~>in u n a fissata struttm'a). Si ~ t r o v ~ t o che in molti dei casi interessunti V non ~ enumer~bile, ed 6 anzi prod u t t i v o , cosicch~ fissati P, V esiste u n a funzione ricorsiva ] la quale per ogni [indiee di un] sottoinsieme enumer~bile T di P fornisee u n p e T ~-V (~- s~a per <~differenza s i m m e t r i e a ~>) e quindi in particolare se T _c V (<, validit5 ~>di T) u n a p e V ~ T , eio6 u n a proposizione <m a non < u m a n a sulle macehine, o u n a <(s u p e r i o r i t ~ , delle teorie <~informali ~ sulle teorie formali. I n [13] (*) si ~ osservato che fra i difetti che l ' a r g o m e n t o presenta e'~ u n a insuffieiente analisi del m o d e di proeedere dell' ~>uomo >>(o delle <(teorie informali ~>) menzionato n e l l ' a r g o m e n t o stesso. ~ ' <(uomo ~>di eui l ' a r g o m e n t o p a r l a deve essere infatti (se vuole m o s t r a r e l'asserita <) disposto ad a m m e t t e r e s i s t e m a t i c a m e n t e nuovi assiomi e quindi anche, per cosi dire, a eance]larli Be essi dessero Iuogo ~ contraddizioni, Questo ipotetico <(u o m o ~> ereder~, per cosi dire, all'istante n (di u n t e m p o discrete) in un certo insieme finite A , di proposizioni e la sua <(s u p e r i o r i t ~ , su u n a teoria si concreter£ nella banale circostanza ch% posto A = l i m A , , si h~: (2)

T cA

(inciusione stretta).

Ma allora questo <,uomo ~>pub essere schematizzato da u n a m a c c h i n a che a b b i a p e r cosi dire, il diritto di smentirsi. I n altri termini: se la pretesa s.u19eriorit~ ~ ottenuta

ammettendo un procedimento per tentativi ed errori allora it eon]ronto deve essere ]atto (*) L'autor~ ha ricevuto 1'11 giugno 1973 un <del febbraio 1973 gentilmente inviatogli da R. J. J ~ o s L o w . In esso si sviluppano indipendentemente temi analoghi a quelli di [13] (R. J. J~ROSLOW, Two theorems on expe~imental logics, Res. Rep. 73-4, Dept. of Math. Mellon Institute of Science, Carnegie-Mellon University).

RO~E~:0 MA~AI~: Signi]icato e veritt~ nelFaritmetica peaniana

348

con maechine che procedono a loro volta per tentativi ed errori~ cio~ con sistemi iper]ormali nel senso dette de]inizioni e proposizioni seguenti:

DEF. 1. - Un sottoinsieme A di ~o si dird un limite inferiore se esiste una ]unzione totale ~icorsiva ] con: (3,1)

A--~ lim.D¢ = { x ~ ( o : esiste a n k tale che per ogni n>~k 6 x ~ D ~ } un limite superiore se esiste una ] come sopra con:

si dir~

(3,2) A---= lim~D¢ = { x e w : per ogni k esiste un n > k con x ~ D~} e si dir~ un limite se esiste una ] come sopra con:

(3,3)

(D~.)~e. a m m e t t e limite e A ~ - l i m , D~

(se x ~ co con D~ si indica l'insieme finito di indice eanonico x). ]~ facile vedere e si ~ mostrato del resto in [13] (cfr. anche M. GoLD [6]) che: P~oP. 1. - Sono limiti in]eriori tutti e soli gli insiemi di X~ (nella gerarchia aritmetica, cfr. It. I~0GE~S [20], cap. 14) sono Iimiti superiori tutti e soli gli insiemi di I12 e sono limiti tutti e soli gli insiemi di A~ = Z~ (~ ]Is. DEF. 2. - Si dird sistema iper/ormale o Z~-sistema ogni eoppia
P si~ un insieme decidibile (insieme delle proposizioni),

(4,2)

L sia port~to~ da una biiezione computabile da P a d

co, in un timite inferiore.

Di solito si supporr~ P = co e si identificher~nno i sistemi iperformali con i limiti inferiori. stato in parte discusso in [13] lo status delle teorie iperformali (e della loro sottoclasse costituita dai cosiddetti <~sistemi dialettici ~) e si ~ t r o w t o che esse non sfuggono (come del resto era d~ aspettarsi) a certi ana6oghi delle limitazioni dedutt i r e (non si 5 f~tto in sostanza che spostarsi di un grado nel]a catena principale dei gradi di insolubilitY) anche se appare arduo rip~odurre al nuovo livello l'argomento relativo atl~ ~, superiorit~ ~. Non si ~ dato in [13] u n t r a t t a m e n t o an~togo delle Hmitazioni espressive. Nella line~ di quanto si ~ detto nella premessa sembr~ ragionevole arrivare alla consider~zione di terne con J5 ~ S ff P in cui si~ isolato nell'insieme P delle proposizioni un sottoinsieme ~q di proposizione ~ sensate ~>e, su]la base delle considera, zioni fatte in [13], considerare in particol~re teorie meta]ormali secondo l~ seguente: DEF. 3. - Si dir~ teoria meta]ormale ogni terna (_P, S, ~> in cui:

(5,1)

P si~ u n insieme decidibile,

(5,2)

~5_c~ c p ,

(5,3)

S, ~, siuno port~ti da una bilezione computabile da P a d

co in limiti inferiori.

~OBERTO ~ A G A ~ : Signi]icato e verit5 nell'aritmetica peaniana

349

Di solito si supporr~ _P = o~ e si intender£ allora per teoria m e t a f o r m a l e u n a coppi~ <~, iS> con ~5 c S _~~o e L, S limiti inferiori. Se T b u n a teoria formale con T _~L si dir£ ehe cui r a r i t m e t i c a p e a n i a n a al p r i m o ordine sia riducibile (nel senso di S. F E ~ E ~ A ~ [4]) di un insieme Po di proposizioni da ehiamarsi sensate ( o v v i a m e n t e scelto in m o d o da costituire u n a c o n t r o p a r t e rigorosa a b b a s t a n z a convincente di cib che il senso c o m u n e (o il senso c o m u n e (( filosofieo ~) fa cadere sotto questo concerto) tale che, detto V l'insieme delle proposizioni di P vere in senso tarskiano nel modello ~(naturale ~) scelto per ( P , T>, (supporremo T _~ V, cio~ la validit£ di ) e posto Vo = V (~ Po risulti che: (6,1)

Po: Vo sono limiti inferiori,

(6.2)

/ ' c Vo c V,

cosicch6, r e l a t i v a m e n t e al n u o v o concerto di veritg, la teoria m e t a f o r m a l e ( P , Po, Vo> risuttg esente dg limit~zioni dednttive. T r o v e r e m o che essa 6 esente altresl d~ limitazioni espressive, nel senso ehe 6 in grado di esprimere sensatamente verit~ (nel nuovo senso) e sensatezza. (I1 significato preeiso di qugnto ora v a g a m e n t e asserito sar~ chiarito pig oltre).

2. - R i c h i a m i sull'aritmetiea p e a n i a n a (s).

~Ncl seguito ci riferiremo s e m p r e ~ll'aritmetiea peani~na al p r i m o ordine, F . Q u a n t o si dir~ g perb valido per ogni sistema formale cui essa si~ riducibile. Con P s i indicher~ l'insieme delle sue proposizioni (espressioni chiuse~ ~ sentences ~), con T l'insieme delle sue tesi, con V l'insieme delle sue proposizioni vere nel modello w.

Si suppo~'rd la validitY, ossia T c_ V. Molti dei risultati, beninteso, possono essers stabiliti sotto ipotesi piit dsboli. Identificherem% come g possibile t r a m i t e u n a o p p o r t u n a biiezione comput~bile~ k, P con ¢o (~) eosicchg T risult~ a n sottoinsieme (ricorsiwmcnte)

(3) In questo paragrafo vengono richiamati alcuni risultati noti soprattutto per precisare la terminologia che si adotter£. Questi risul~ati, per evitare coraplicazioni nel simbotismo, vengono dati nella forma pi~ atile per it seguito, che non sempre ~ la pill forte versione in cui sono noti. Per trattazioni pi~ esaurienti e per la dimostrazione dei risultati cfr. S. FEPER~A~ [4] e J. R. SHO3Z~FIELD[23] capp. 6 e 8, LOB [11] etc. (~) In genere P viene identificato con un opportuno sottoinsieme ricorsivo proprio di (cfr. F]~FERMA~ [4]) ma dovendosi qtti SolO richiamare e non dimostrare corti risultati noti la convenzione del testo ~ la pih comoda e, per un'opportuna scelta di k, non d~ luogo a inconvenienti.

RO:~ERT0 M~An~: Signi/icato e veritd nell'aritmetica peaniana

350

enumer~bile di w e V un insieme di grade di insolubilitg (o. Come simboli linguistici useremo quelli consueti. S e x ~ co con ~ si indicher£ il numerule corrispondente. J~ ben n o t e ehe: PI%OP. 2. -

Una relazione R c_ o9~ ~ ricorsiva s e e solo se esiste una espressione R(x~,x~, ...,x~) di ~ con n variabili libere tale ehe:

(7,1)

eR s e e solo se ~ / ~ ( ~ , ~ , , . . . , ~ )

(7,~)

~R se e solo se ~ - ~ R ( ~ , ~ , ..., ~ )

(x~e~o)

(cfr. ud esempio E. MENDELS0N [16], cap. 3, § 5 0 J. 1~. S~0ENFIE:LD [23], cap. 6, § 7) Si dir~ e h e / ~ rappresenta o (con S. FEF:ER~AN [4]) binumera t~. Pres~ un~espressione E(x~, x ~ ...~x~) di _F con n v~riubili libere si dir~ ehe essu 8 unu rappresentante se ruppresentu unu rel~zione. I n tul e~so ovviamente essu rappresentu precisumente lu J~ definitu du:

~ ? se e solo se ~ E ( ~ ' ~ , . ~ , . . . , ~ , )

(s)

(x~e~o)

che, per lu prop. 2, risultu ricorsivu. I n purtieol~re risultuno essere ruppresentunti (di re]~zioni ricorsive primitive, err. S. F E F E ~ A ~ [4], §3) t u t t e le P. l~.-formule. unche note che: PRo]'. 3. - Una relazione R c_w , ~ ricorsivamente enumerabile s e e solo se esiste un'espressione R(x~,x~, ...,x~) di t z soddis]aeente la (7,1). Si dir~ che/~ semirappresenta o (con S. FEPER~A~ [4]) numera R. Presu un'espressione E(x~, x2, ..., x~) di F si dir~ poi che essa b unu semirappresentante se semiruppresentu la ~ definita dalla (8) (5). ]~ ovvio ehe: PRo]'. 4. - Sia R ~ oJ~+~ rieorsiva, sia 1~ una sua rappresentante e sia S de/inita da: (9)


con
(x,~w)

alIora la Hy ~ ( x l , x~, ... ~x,) numera S (ed ~ quindi addirittura una semirappresentante).

J~ note che: PROP. 5 (lemmu di di~gonalizzuzione). - Per ogni espressione E(x) con una variabile libera esiste atmeno una p ~ ~ con:

(10)

~--p ~-~ E ( ~ ) .

(~) ]~ ovvio che ogni espressione semirappresent~ un'opportun~ relazione: non per questo, con 1~ definizione d~t~, ess~ risulter~ un~ semirappresentante.

RO]~E~T0 I ~ A S A ~ : Signi]icato e veritd nell'aritmetiea peaniana

351

infine b e n n o t e che P u m m e t t e u n a s e m i r ~ p p r e s e n t a n t e P(x) (~) t~le che: e inoltre: (11,1)

~- ~ ( ~ ) A P(~) +~ P ( ~ A ~ )

P ( p -~ q) -~ (P(~) -~ P(~))

(11,2)

(p, q e ~o) (11,3) ~-T(~) see

(11,4)

solo se ~-p (7)

PROP. 6. -- Se E(x~, x~, ..., x~) ~ una R-/ormula con n variabili libere (cir. J. R. SHOE~~IEL;) [23], cap. 8, §2) 0 un'espressione esistenziale allora:

~- B ( ~ , ~ , ..., ~ ) -~ "2(~,(~, ~ , ..., ~ ) )

(x, e ~)

Infine: PROP. 7 . - Per ogni p ~ w se F - P o ~- -~p allora r-p-->P(~) (cfr. ad e s e m p i o C. M A ~ I O ~ . [15], teor. 2, i). C o n v e r r £ n o t ~ r e e s p l i c i t ~ m e n t e che, dalle p r o p r i e t £ d~te di P (de1 resto gi~ ridondanti) si d e d u c o n o f u c i l m e n t e le: se ~-P(p-->q) u11or~ ~ - ~ ' ( ~ ) - ~ ' ( ~ )

~- P ( ~ ) v ~'(~) -* P(p-v-q) •

3. -

Sensatezza

I

/

(P, qe~o)

e verith.

Si t r ~ t t ~ or~ di d a r e u n a accett~bfle definizione degli insiemi 1)o, ~ di cui nel § 1.

(6) In genere la P ~ ottenut~ nel mode seguente (o in modi ad esso equivalenti). Anzitutto si stabilisce un'apportuna biiezione computabile c$ d~ un sottoinsieme ricorsivo di all'insieme delle dimostrazioni di /~. Detta D la relazione ricorsiva definita da: (p, ~ ) ~ D

se e solo se 8n 6 una dimostrazione di P

se ne eostruisce in mode ~,naturale ~ una rappresentante D(x, y) e si pone poi ~'(x) = 3yD(x, y). Nel processo hanno importanza le scelte di/~ e 8 (per un'analisi approfondita cir. S. F]~FER~A~ [4]). Quel che qui interessa 6 solo il fatto che 6 possibile scegliere k, 8 (e D(x, y)) in mode che siano validi i risultati ehe seguono. La scelta si suppone fatta in mode che D risulti primitiva ricorsiva. (7) Notiamo ~nche che P(x) 6 un~ semirappresent~nte, onde risultano equivalenti le:

P(9) ~- P(p)

ROBERTO )/IA~)~R~: Signi/icato e verith nell'aritmetica peaniana

352

Secondo le indicazioni della 9remess~ si d o v r a i n t a n t o avere:

(12)

Po -- Vo w { -~p: p + Vo}

(13)

Vo = v c~ -Po

(14)

r c Vo.

Se per <(metodo di verificazione o di falsificazione >~i n t e n d i a m o un metodo di cui, per cosl dire, F disponga, s e m b r e r e b b e a p r i m a vista di dover proporre l'uguaglianza: P~O~OSTA 1. - Po =- T ~ { -~p: p ~ T } , che o v v i a m e n t e banalizzerebbe l'intero problem~. Ci sono per6 forti a r g o m e n t i per scart~re questa proposta. Sia p ~ P e sis ud esempio: ~p,

non ~-p, ~ - , p - ~ T ( - , p ) .

]~ facile vedere che esistono proposizioni in questa da.to d~ll~ proposizione indecidibile di G6del (err. stanza o w d o ehe, p u r non essendo ~ p o ~ -~p, F per la falsificazione d i p : per esprimersi in t e r m i n i nisce col sapere )> che, se p ~ falsa, lo dimostrer~. Si perviene per questa vi~ alla:

situ~zione, un notissimo esempio C. ~L~GIO~E [15], es. 1). J~ abb~possiede, per cosi dire, u n metodo grossolani F <(sa )>, o meglio <
PI~OPOSTA 2. -- P+Po se e solo se ~-p o ~- ~ p o ~ p ~ ' ( ~ ) o ~ ~p+T(~p)

o

che, poichb 1~ p r i m a e la seconda possibilit~ implicano la terza e la quarta, si riduce alla: pc-Po see

solo se ~-p-->~'(~6) o ~ - - ~ p - ~ ( ~ - - p )

.

Cib porterebbe ~ porre:

p e V o s e e solo se ~ - , p - + ~ ( ( - ~ p )

e non ~ - - ~ p .

Sull~ base di questa p r o p o s t a non ~ difficile d i m o s t r a r e che si ottengono risultati ~ b b a s t a n z a soddisf~centi e eio~ fr~ l'altro:

Esistono due espressioni Po(X) Fo(x) tali ehe: (15)

Sono equivalenti per ogni p ~ P le:

(i)

~Po(~)

(ii)

Po(p)~ Vo

(iii) p~_po.

R0]~ERT0 MAGA~I: Signi]icato e verit~ nell'a~itmetica p e a n i a n a

353

Sono equivalenti p e r ogni p ~ P le:

(16)

(i)

Vo (~)

(ii)

~'o(~) e Vo

(iii)

p ~ Vo.

(17)

t)o e Vo sono l i m i t i , Po ~, anzi, enumerabile.

T u t t a v i a a n c h e l a p r o p o s t a 2 si p r e s t a a serie obiezioni. L e d u e p r i n c i p a l i s o n o : OB~EZ. 1. - ]~ facile v e d e r e che e s i s t o n o delle p , qeo~ c o n :

~ p -+ q

(e a f o r t i o r i p --->q e Vo)

p ~ Vo

q~ Vo (~). V i e n e m e n o cio~ u n r e q u i s i t e e l e m e n t a r e d a chiedere a ogni c o n c e t t o di v e r i t ~ che si p r o p o n g a . OB~EZ. 2. - N e l t a s u a d e f i n i z i o n e P~ a p p a r e t r o p p o s t r e t t a m e n t e legato a T e a11a s u a r a p p r e s e n t a z i o n e .

(s) Non sia cosl e siano R, S, C le relazioni definite da: (x, y, z, w) ~ R s e e solo se la x-esima macchina di T a r i n g a partire da y ealeola z in al pifl w passi, (~, v, x, y, z, w> E S s e e solo se la x-esima maeehina di T u r i n g con oracolo a partire d a y calcola z in al piff w passi qualora le siano date risposte affermative sugli elementi di D u e negative sugli elementi di D~;

< x , ~ > ~ g s e e solo se x ~ D ~ . Le B, S, C sono primitive ricorsive e siano /~, ~, C eerte P.R.-formule lore rappresent a n t i i n F. Ovviamente la ~ ( x ) = Sw 3y R(x, x, y, w) numera K. S e x ~ K, K(~)~ cio~ u n a tesi e a f o r t i o r i in V0. Se x ~ K Consideriamo era l'espressione:

allora b- /~(~)-+~'(K(~)) e n o n [ - / ~ ( ~ ) o n d e - ~ / ~ ( ~ ) ~ Vo.

/~'(x) = Bu By 3z 3w (¥r(0(r, u)->/~(r)) A Vs(C(s, v)-> -~/~(s))A~(u, v, x, x, z, w)). chiaro ehe:

x ~ K " s e e solo so t~--K'(~) (notazioni det Rogers [20], cap. 13: K ' = (x: x~D~i~)}). ]~ facile vedere che se D~ = c_ K e D~ = {Yl, Y~ ..... Yk} c K e (u, v, x, x, z, w> ~ S per eerti z, w, atlora ~- (~(~)A~:(.~)A ...A~(~) A'TK(y~)A-~K(Y~)A...A-~~:(Y~))--> -->K'(~), onde K ' ( ~ ) ~ Vo. Cosi si ha K ' ( ~ ) ~ Vo so e solo so x ~ K ' . Ci5 infine fornisce u n procedimento di riduzione di K" a Vo che a sua volta ~ riducibile (essendo u n limite) a K. Ci6 ~ assurdo e ne segue l'affermazione del testo. 23

-

Annalf d~ Matematica

354

I~0:SERTO MAGARI: Signi]icato e veritd nell'aritmetica peaniana OSSERVAZlO~E. - A prima vista sembrerebbe possibile una terza obiezione.

S i a p ~ T e p-->~"(~) e Vo. Da u n lato app~re ragionevole a m m e t t e r e che p si~ sensata, 4alFaltro sembrerebbe poter accadere che p - ~ T ( ~ ) ~ T cosicchb -~p, p u t essendo ovvi~mente ver~ e, in senso intuitivo, sensata, non a p p a r t e r r e b b e a ]70. Senonch~ il caso non si present~ perch6, sulla base delle ricordate propriet~ di ~, si vede f~citmente ch% scrivendo per comodit~ q* per q->~(~) si h~ per ogni p e o n : ~-p* ~:>(-~p*)*. D ' a l t r o n d e dalla definizione di V. si ric~va che se p * e Vo allora ( - ~ p * ) * e T . L e obiezioni viste suggeriscono una terza propostu, riassunta nelle definizioni seguenti: DEy. 4. - Si indichercl con ]To il m i n i m o insieme per eui:

(16) (17) (18)

T _~ Vo se p , p - - > q e Vo allora q e Vo se ~ p - + ~ ( ~ ) ~ V o e ~ p 6 2 r' u 1 1 o r a p c V o

Le proposizioni di Vo si diranno vere (o, per non ]at eon]usione con la veritd in senso tarskiano, s-vere ((( s ~) per sensate)). Si scriverh t ~ p p e r p e Vo. DEF. 5. - Si indicherd con Po l'insieme V o w { -~p: p ~ V0}. Le proposizioni di Po si diranno sensate e si scriverd IP per p ~ t'o.

Da,lla definizione si ricavu fueilmente ih Cot¢. 1. - Valgono le: (19)

VoC_V

(20)

Vo---- V n P o

(21)

se p ~ - ~ q ~ V o (in partieolare se v-pc-~q) atlora p e V o

(22)

se p, q e Vo allora p A q e Vo

(23)

se p - - ~ ( ~ ) ~ V o

(24)

se q e Vo, --1p --~ T(q --~ -7 p) ~ Vo e q - , -~ p ~ T allora p ~ Vo

e pet

s e e solo se q ~ V o (p, q~o~)

anora - ~ p e V o

Si ha poi: L E ~ v ~ 1. - Vo e t)o sono limiti in]eriori.

D ~ . - ]~ unzitutto o w i o che Vo 6 costituito da t u t t i e soli gli elementi finali di sequenze finite (p~)~+l(n e co) tali che per ciascun i ~ n + 1 v~lg~ un~ delle:

(i) p,: e T, (ii) esistono certi h, k < i con p~¢----ph-~p~, (iii) esiste un j < i per cui:

I~O~E~T0 MA~A~: Signi]ieato e veritd nell'aritmetlea peaniana

355

P e r comodit~ si c h i a m e r a n n o queste sequenze, buone T-sequenze. Pifi in generale presa u n a qualunque sequenza f m i t a a e u n X _c ~o si dir~ che a ~ u n a b u o n a X - s e q u e n z a se soddisfa la condizione suesposta con X al posto di T. P o n i a m o T~ : (p ~ o : esiste un m<~n con ( p , m~ ~D~. Una b u o n a T~-sequenza si dir~ per comodit~ u n a b u o n a n-sequenza. Fissiamo ora u n a biiezione c o m p u t a b i l e a d a ~o all'insieme delle sequenze finite non nulle di elementi di eo in m o d o tale c h e l a Ro definita da: (x, y, z) e R o s e e solo se ~y ~ u n a b u o n a z-sequenza a v e n t e x come elemento finale (che, s e a ~ comput~bile, risulta ricorsiva) sin p r i m i t i v a ricorsiva. Mostriamo che si h a per ogni p e w: (iv) p e V o se e solo se esistono un k e u n n tali che per ogni m>~n sin ( p , k, m~ e Ro. Sin p e Vo. Allora esiste u n k tale che ~(k) ha p come elemento finale ed ~ u n a b u o n a T-sequenza: ~ chiaro che da u n ccrto n in poi a(k) ~ anche u n a b u o n a n-sequenzu. L ' i n v e r s o ~ anch'esso ovvio. Essendo Ro ricorsiva la (iv) m o s t r a che Vo e / 2 cio~ che Vo ~ un limite inferiore. Sar~ o p p o r t u n o osservare c h e l a relazione W o = {(p, k): esiste un n tale che per ogni m>~n sin (p, k , m ) e R o } . coincide con: {(p, k): per ogni n esiste a n m>~n con (p, k, m ) e Ro} onde ~ a d d i r i t t u r a u n limite (~ cio~ in A~---=l ~ (3//2). Si h a o v v i a m e n t e : Vo = {p: esiste un k con e Wo}, /Do= {P: esiste un k con e Wo o < ~p~ k > e Wo} e anche /Do risulta u n limite inferiore. Si b cosl costruita u n a teoria m e t a f o r m a l e F*---- che estende /~.

4. - F*-rappresentabilith. Poniamo: DEF. 6. - Sia R c_o~" una relazione. Si dird che essa ~ F*-semirappresentabiIe se esiste una espressione 1~(xl, x2, ..., x~) con n variabiti libere tare che sia: (25)

I~/~(~1, x2, ..., x~) s e e solo se (x~, x2, ..., x n ~ R .

Si dird poi che la R ~ F*-rappresentabile se esiste una R come sopra per cui valga la (25) e inoltre la: (26)

I ~ ~/~(x~,x2,...~x~) s e e

solo se ( x l , x2, ..., x ~ R .

I~0BERTO M h G ~ :

356

Significato e verltd nell'aritmetica peaniana

Si dirh e h e l a ~ Iz*-semirappresenta (F*-rappresenta) la R. Un'espressione R si dirh una l~*-rappresentante se F*-rappresenta un'opportuna relazione (e quindi ovviamente la R de]inita da : (27)

(x~, x~, ... x~} e R s e e solo se ~ R ( ~ ,

~ , ..., ~ )

ehe si dirh la sua retazione associata). Si dir5 poi che R ~ una ~*-semiral~presentante se F*-semirappresenta la R sopra defi/aita. Mostriamo che: L E n A 2. - Sia ~(x~, x~, ..., x,,) una R-]ormula o u,na ]ormula esistenzia~e (cfr. J. R. SHOEI~F~ELD[23], cap. 8, § 2). Allora essa (e quindi la sua negazione) ~ una ~*rappresentante. D I M . - Siano x ~ , x ~ , . . . , x , e o ) e s i a p = E ( ~ , ~ 2 , . . . , 5 , ) , ~-p -+ ~"(~).

per la prop. 6 si ha

Se ~ p allora ovviamente ~-p (perch~ le R-formule esistenziuli sono particolari semirappresentanti~ cfr. J. t~. SHOENYIELD [23], cap. 8, § 2, lemma 1 e l e m m a 3) onde a f o r t i o r i i ~ P . Se ~ -~p ~ non ~-p onde, per lu (23), i ~ - ~ p . Come ovvio corolla.rio si ha: CoR. 2. - Se E(x~, x~, ..., x , , y) ~ una PR-form~la (nel senso di S. FEFE~I~AN [4], §3) alIora Vy E(x~, x:; ..., x,~, y) e 3y E(xa, x2, ... x , , y) sono t~*-rapp~'esen$anti. D ~ . - Poich~ la negazione di una P-R-formula ~ dimostrabilmente equivalente ad u n a P R - f o r m u l a e la quantificazione esistenzi~le di una P/~-formula ~ dimostrabilmente equivalente a una R-formula l'asserto segue dal lemma precedence. Si ha: LE~)~A 3. - (i) se E(x~,, x~., ..., x~, y) ~ ~na )F*-semirappresentante anche la 3y. •E(x~, x~, ..., x~, y) to ~. (ii) Se E(x~, x~, ...~ x,, y, z) ~ q~na PR-]orm~da allora 3y Vz E(x~, x:~ ..., x ~ y~ z) q~na :F*-semirappresentante. D~v~. - Siano xl, x2, ..., x~ ~ o~, poniamo p : 3y E(~I, ~ , ...~ ~ , y) e sia ~ p . A1lora esiste u n y e c o per eui la q = E ( ~ , ~ , ..., ~ , ~) ~ vera e quindi ] ~ q . Ma ~ - q - ~ p onde i ~ q - > p e infine l ~ p . V iceversa se [ ~ p ~ ~ p per la (19). L a (ii) segue dalla (i) t e n u t o conto del cot. 2. Si ha infine: TEOR. 1. - ~ono F*-rappresentabili tutte e sole le relazioni the stanno nella elasse As = X~ (7It2 della gerarchia aritmetica (che sono cio~ limiti) e F*-semirappresentabili tutte e sole le relazioni ehe stanno in Z~ (the sono eio~ limiti in]eriori). D ~ . - Che le relazioni di Z2 siano /V*-semirappresentabili segue dal lemma 3. Sia R g c o ~, R ~ A ~ . R ~ allora u n limite nel senso di [13] e percib esiste ([6]~ [13])

l~o]3n~To ~ A ~ A ~ : Signi]icato e verit~t netl'aritmetica peaniana

357

una relazione ricorsiva S g co'~+~ tale che sono equivalenti, per x~, x~, ..., x,~ ~ o~, le:

(i) ~R, (ii) esiste a n y ~ ~o tale the per ogni z/> y ~ ~ S, (iii) per ogni y esiste uno z>~y per eui eS. facile vedere che si pub seegliere la S primitiva rieorsiva (per esempio dimostrando prima la cosa per l'insieme di arresto K e poi riesaminando la dimostrazione de1 lemma 5 di [13]): sia dunque S c o~+1 primitiva ricorsiva con la propriet~ suddetta e sia ~(x~, x~, ...,x~, z) una P-R-formula che la rappresenti. Siano ora x~, x~, . . . , x , ~ o~ e poniamo per eomodi~g:

P ~ , z) = r >~y ~ ~(Y~, Y~, ..., ~ , z) , Q(y, z) = z>yA~(~'~, Y~ , . . , ~ , z), eosiceh~ P(y, z) e Q(y, z) sono [dimostrabilmente equivalenti a] P-R-formule. Si ha:

~ 3y Vz P(y, z) e-~ Vy 3zQ(y, z).

(28) 1~ o w i o poi che: (29)

~- 3y VzP(y, z) -> Vy 3zQ(y, z),

(30)

~- (Vy 3z Q(y, z) -+ 3y Vz P(y, z)) ¢-+ (3y Vz P(y, z) '~/ 3y Vz ( -, Q(y, z)):.

Ma u n a delle 3yVzP(y,z), 3 y V z ( - , Q ( x , y ) ) 1emma 3, (ii) in Vo onde infine si trova:

(31)

I~

~, per la (28), in V e quiadi per il

3y VzP(y, z)+-+ Vy 3zQ(y, ~) .

Se ora ~ ¢0 ~ ~ . 3 y Vz P(y, z) e quindi (lemma 3, ii) i ~ 3y Vz P(y, z) e, per ta (3,1) i ~ Vy 3zQ(y, z). Se inveee ~ o~ allora ~ 3y Vz( -, Q(y~ z) c (lemma 3, ii) I ~ 3 y V z ( -,Q(y, z)) (la ~Q(y, z)) b dimostrabilmente equivalente a una PR-formula, err. S. FErEa~fA~ [4], 3.7, (i)) onde i ~ -- Vy 3zQ(y, z) e, per la (31) 1~ ~ 3yYzP(y, z). ~'c segue che le:

3y Vz(z >1y -+ S(xl, x~ ~ ..., x~, z) Vy 3z(z>~yA~(xl, x~, ..., x~, z) F*-rappresentano ambedue la R. Sia ora R_cog~ P-semiralopresentata. da una R(x~, x2, ..., x~). Si ha:

Ea) s e e solo se ~ @ 1 , ~ , . . . , ~ ) ~

Vo

(xi~(D)

358

~RoBERTO ~V~AGAI~I: Signi]icato e verit~t nell'aritmetica peaniana

e looich~ Vo ~ in ~ e 1~ funzione / definit~ da: /(x~, x~, ..., x~) = R ( ~ , ~ , ..., ~ )

(x~e~)

ricorsivu, anche R ~ 27~. Che le reluzioni/~*-r~ppresent~bili stiuno in A~ ---- X~ ~ H~ ~ ~ questo punto ovvio. I1 teorem~ ~ cosi dimostr~to.

5. -

F * - s e m i r a p p r e s e n t a z i o n e della s-verith e della s e n s a t e z z a .

D~I teor. i segue subito che Vo e Po sono E*-semirappresentubili e che T ~ E*rappresentabile. Scegli~mo or~ un~ P.R.-formul~ Ro(x, y, z) che rappresenti Ro cosicch~ lu:

Wo(x, y) = 3z Vt(t>~z-> Ro(X, y, z) ) . /7*-r~ppresent~ Wo. ]~ ovvio che, in virtfi del lemma 3, (i) 1~:

~(x) = 3y ~(o(X, y) una E*-semirappresentunte e/~*-semirappresentu precisumente Vo. Siu ora/~(x, y) unu PR-formulu che rappresenti 1~ ~unzione primitiv~ ricorsivu che m~nd~ p in -~ p. Sempre dal lemma 3, (i) si ricava facilmente che 1~: Po(x) = 3y 3z(:V(x, y)A (Wo(X, z)V Wo(y, z) una lV*-semir~ppresentunte e/~*-semirappresenta precisumente Po. Si ha cosi: TEOI~. 2. - Sono equivalenti, per ogni p E o~, le: (~) ~ Vo(~) ,

(ii) I ~ ~o(P), (iii) I ~ p . TEOR. 3. - Sono equivalenti, per ogni p ~ oJ~ le: (i) ~ P o ( P ) , (ii) l ~ P o ( f i ) , (iii) tP.

I~O~ER~O ) I A ~ A ~ : Signi]icato e veritd~ nell'aritmetica peaniana

359

I1 legame fra P0 e V0 espresso dalla def. 5 ~ riproducibile a livello linguistico nel senso che:

TEo~. 4. -

~VxVy(~T(x,y))-~ (Po(~)~(~o(x)V~o(y))) ~, ~ /o~o,-~, I ~ Vx Vy(N(x, y)) -~ (Po(X) ~ (~o(x) V ~o(y))).

Come ow-io corollario si h a : Cor. 3. - Per ogni p e ( 9

~:

Po(P) e-~ Fo(P)~/ Vo( ~P) e, a ]ortiori:

Mostriamo ora che le (( nuturali ~)traduzioni linguistiche delle (16) (17) (18) stanno in V0. Si ha:

• ~o~. 5 . -

I ~ V x ( ~ ( x ) - + ~o(x)).

D ~ . - Possiamo supporre di aver scelto la ~ del lemm~ 1 coincidente con la 8 della nora (7) eosicch~ si avr~:

Vx Vm Vn( JO(x, n) )/\ m >~n --> ~o(X, n, m) , da cui~ per il cor. 1:

I ~ Vx Vm Vn( JO(x, n) )A m > n -+ l~o(X, m, n) e da banali tesi predicative segue il teorema. O v v i a m e n t e allora: CoR. 4. - Per ogni p ~:

I ~ T(~) ~ ~o(~) . Sia oru _](x~ y, z) un~ P R - f o r m u l a che rappresenti la funzione primitiva ricorsiva che m a n d a la eoppia (p~ q) in p - ÷ q; si ha: TEo~. 6. - I ~ Vx Vy Vz( ~7o(x)A~(x, y, z)A ]?o(z) ~ ~o(y)) (si tr~tta della tracluzione (~n~turale ~ dell~ (17)). D ~ . - Si~ ~ u n a LPR-~ormula che rappresenti la funzione primitiva rieorsiva (~) che alla coppia (x, y) ussocia lo z e co per cui ~z ~ l~ concatenazione di a x e a y e ~ /

(9) Non stiamo qui a. preeisare la seelta della a: si supporr~ di averla scelta in modo abbas~anza (, naturate, da far si the ol~re alla Bo anche eerie relazioni e f~anzioni che considereremo siano primitive ricorsive. Che eib sia possibile ~ facile da controllare.

360

Ro]~EI~o /V[A~.~I~I: Signi]icato e veritd nell'aritmetica peaniana

una PR-formula che rappresenti la funzione primitiva ricorsiva (9) che alla coppia (x, y) associa max{x, y}. Via cot. 2 si trova allora: I ~ V(P0(x, k, n)Ai(x, y, z)A/~o(z, h, m)AC(k, h,/)AM(n, m, p) -->/~0(y, l, p)) da cui, usando o w i e tesi predicative, il teorema. O w i a m e n t e 6: Co~. 5. - Quali the siano p, q e c9 si ha:

?o(~)A ~o(~.~q) -~ V0(~) •

~=

Sia ora ~ 1~ funzione definita in co da:

~(x) = ~"(~)

(x eco).

Essa ~ primitiva ricorsiva: sia dunque T(x, y) una PR-formula che la rappresenti. Si ha: •

,~

TEOR. 7. - 1 ~ V(_~(x, Y)A Vo(t)AT(y, z)Ai(y, z, t)A -~ ~r(y) _-> Vo(x)) (si t r a t t a della traduzione (( naturale ~) della (18)). DI~L - Consideriamo la relazione /) definita da:

(x,y)eD

se e solo se esiste uno z < y con ( x , z ) e D .

Per il lemma 3.7 (iii) di S. FEFEn)~A~ [4] la formula: 2-

D(x, y) = 3z(z
I ~ ~o(-~ p--> ~r(-~ p)) A -~ T(~) ~ ~o(~).

Ro]~E~ro MAG~RI: Signi]icato e verit~ nell'aritmetiea peaniana

361

6. - Invarianza di /~o e Vo per certi eambiamenti di T, ~ .

Quanto si ~ visto nei §§ precedenti mostra che il sistema metaformale ~*, oltre a evitare l'obiezione 1, possiede, per cosi dire, un notevole grado di adeguutezza, nel senso che per esso ~engono a cadere molte delle usuali limitazioni espressive e dedutrive. L~ questione sara ripresa nel § 7. Occorre ors indagare sul c o m p o r t a m e n t o di/~* rispetto alt'obiezione 2. Vo e Po sono stati definiti con riferimento alla qua~erna (T, D, D(x~ y),T(x)}. Si mostrer~ c h e l a medesima costruzione upplicata a certe altre quaterne porta ancora a Vo, Po. P o n i a m o anzitut~o: DEF. 7. - Una quaterna i = ( T (~), D ~), f)(~)(x, y), ~'l~)(x)} si dir~ lecita se: (32,1)

T (~) ~ u n sottoinsieme enumerabile di co con TC_T(~)g Vo,

(32,2)

D (~) ~ una relazione p r i m i t i v a ricorsiva con:

T (t) = {x: esiste u n y (32,3) (32,4)

~(x,

con (x, y} e D (~)} ,

y) ~ un~ P R - f o r m u l a che r a p p r e s e n t a / ~ ) ,

~(~)(x) = 3yD(i)(x,y) e pea' ogni R-formula E(xl, x2...,x~) si ha, quali che s i a I I O X 1 ~ X~, . . . , X~ @ CO:

2~(~, ~ , ..., ~.) -+ T(~)(E(~, ~ , ..., ~.)) e/~(*) A partire da i si definiscono al solito modo -o v(~), --oP(~)' Si t r a t t a ora di dimostrare che per ogni quaterna lecita i e ~oV(~)----Vo, --oP(~)-----Po. Esaminiamo anzitutto il caso di due quaterne lecite i, j con T (~)-- T (j). Sia p ~w con: p -~ ~'(~)(~) e v~ ) , ossia:

o anehe: 3y(p ~ D'i'(~, y)) e _V(i) .. Dalla liceitg di i si deduce facilmente V~)_¢ V onde 3y(p -+ D(~)(~, y) ~ V e allora anche 3y(p-+/)(~)(~, y ) ) ~ V da cui, applicando in relazione a j il cor. 2 (come possibile per la liceit~ di j) si t r o v e :

3y(p -7 D'~'(~, ~)) e yg,

362

I~OBEI~T0 MAGAI~I: Signi]icato e verit5 nell'aritmetica peaniana

ossia:

p -~ ~'~>(~) e V(,~) . Poich~ V~°'oe V~~ dipendono d~ ~'"), T(~) solo tr~mite la (18) ne segue: Ln~v~ 0

~@

4. - Se i, j sono due quaterne lecite con

T (~)

T (~) allora v ( ° -

v ~)

"

Si~ ora q e V o \ T e poniamo T(~)= T w {q}. Definiamo una D (~) ponendo: (33)

( p , n > G D (~) s e e solo se ( q - - * p , n > e D .

Poniamo unche:

(3~)

~)<"(x,y)

= Vz(i(~, x, z) -~/)(z, y ) ) ,

(35)

~)(x) =

~y b<*~(x,y).

T e n u t o conto del fatto che -](x, y, z) ~ unu P/~-formula che rappresenta una funzione ~ facile vedere che D(~)(x, y) ~ (dimostrabflmente equivalente u) tm~ PR-formula e c h e l a i----(T (~),D (~),/)~)(x, y), T(~)(x)> ~ una qu~terna lecit~. P e r il lemm~ 4 V(~~) indipendente dull~ scelta di D (~), /)(~)(x, y), T(~)(x) purch~ formino con T (~) un~ quat e r n s lecita; possiamo dunque rifer'~ci ulla p~rticolare scelta fatty. Si ha: LE)I~IA

5.

-

Nelle condizioni suddette Vo = -V(~) Po ~ ~P(~) -0 ~ 0 "

D ~ . - Si pub procedere per induzione sulle sequenze di cui ul lemma 1. L'unico p u n t o che merita ~ttenzione ~ il p~sso induttivo con riferimento allu (18). Si~ p e Vo, i n t r o d o t t a mediante la (18) in quanto: - ~ p - > ~ ( - ~ p ) e Vo, - ~ p ~ T . Poich~ p e V0_c V, T(~)_cV(~>_cV sar~ - ~ p ~ T (~). Dalla (11,2) si ha:

onde infine, tenuto conto dul fatto che T c T " ) c- - ov (° e dell'ipotesi induttiva (che porta -~p --> ~'(-~p) e V(o~)) si t r o v a : -~p --> T(i>(-~p) e V(o~) e cosl p G v- o(~) risaltu ~pplicando ta (18) (con riferimento alla quaterna i). Sia p G V(i) -o introdott~ mediante lu clausola (18) (con riferimento ~ i). S~:%:

RO~ERTO M h ~ A ~ : Signi]icato e verith nell~aritmetiea peaniana

363

Poich~ T a_T (~) sar~ -~p ~ T e a p p l i c a n d o il cor. 1 (formula 24) si t r o v ~ p e V. o(~. Siamo ora in grado di dimostrare che:

TEOI¢. 8. - Per ogni quaterna leeita i ~ V (~)- - Vo ~ ~P(~) --0 0 -

-

Po.

D ~ . - Anzitu%o la cosu ~ o v v i a dai l e m m i ~, 5 se T(~)\T ~ finito. Possiumo dunque supporre T(~)\T infinito, T(~)\T = {q~: i~co). A1 solito si m o s t r a per induzione che V o _~ V (~). I1 p u n t o che merita uttenzione il passo i n d u t t i v o nel caso in cui unu p ~ Vo sia i n t r o d o t t u m e d i a n t e ]a (18). A v r e m o -~ p --> ~( ~ p) e Vo, -~ p ~ T. A1 solito da p e Vo c V, T (~)a V(o~)_c V si ricava -~ p ~ T (~). L a -~p - ~ T ( ~ p ) essendo in V ~ vera (in senso classieo) onde lo ~ (essendo T _c T (~)) ~nche 1~ ~ p -~ T('~)(-~p) che allora (per il cor. 2 appticato ~ i) uppurtiene ~ V (~ (~). P e r dimostra.re che v (~)a Vo conviene porre per n ~ co: --0

--

T (~)-- T ~ {q~: i e n } , e riferirsi ai vari V(o") che, per il l e m m a 5, coincidono t u t t i con Vo. L a dimostrazione si conduce poi ~1 solito per induzione e il p u n t o rilevante ~ il passo i n d u t t i v o nel caso della etausola (18) (applieu~u con riferimento ~ i). Sia p ~ ~ ) i n t r o d o t t a m e d i a n t e la (18). Sar~ ~ p -+ T(~)(~-~) e v- o(~) , ~ p ¢ T (~). A1 solito m o d o si d i m o s t r a sfruttundo l'ipotesi i n d u t t i v ~ che, per un opportuno n ~ w:

-~p-~T(~)(-~p)e V~~) ,

- ~ p 6 T (') d~ cui p e V(o'~= V o .

I1 teor. 8 h a notevole i m p o r t a n z a per due motivi. A n z i t u t t o m o s t r a t h e l'obiezione 2 inapplicabile ~ F*, in secondo luogo, qu~lor~ si vogliano consider~re sistemi compositi del tipo (co, Po, T'} con T ' _c Vo enumerabile, cioS~ per cosi dir% sistemi met~formali con menzione del sistema formale di p~rtenza ci p e r m e t t e di inserire in T ' le proposizioni chc ci interess~no, per esempio quelle dei teor. 4~ 5, 6, 7.

7. -

II sistema

F*

e le asserzioni

di consistenza.

facile vedere, usando il cor 2. che, parl~ndo imprecis~mente:

(o)

F* ~ in grado di decidere sulla consistenza di ogni sistema ]ormale dato.

~ a t u r a l m e n t e in questa f o r m a 1~ (o) ~ ambigu~ e, anzi, in certe possibili letture, errone~. ]~ imprecisa perch~ non ~ chi~ro che cosa si in~end~ per sistema formale ~(dato ~ (non si ~ infatti precisato come si i n t e n d a indici~re i sistemi form~li) e sopr~t(10) I1 segno V preposto sta ora in segui~o per ~ ohiusur~ universMe di ~. (~) La dimostrazione ~ pi~ semplice di quella data nel lemm~ 5 per un easo partioolare, ma in alcuni punti la preced~nte dimos~razione ha aspetti pi~ eostruttivi, il the pub avere interesse in vist~ di una parziale form~lizzazione,

ROBERTO ~AGARI: Signi]icato e veritd ndl'aritmetica peaniana

364

t u t t o non si ~ chi~'ito quMe esatta proposizione intendiamo esser quella che (( esprime ~) la consistcnza di un (~dato ~) sistema formMe. Si vedr£ pifi oltre che, in certe (poco (( natur~li ~)) letture, lu (o) ~ falsa). Fissiam% ad esempio come in It. I~o~E~s [20] cap. 5~ una biiezione primitiva ricorsiva • da ~o: ad co, invertitu da due funzioni primitive ricorsive ~ , z2. Se xeo~ indichiamo con F (~) il sistema (o~, W , ~ , ~ x } (dove W~,~ sur~ l'insieme della (( tesi ~) di /7(~) e ~ x la (( contraddizione ~)). F (~) si dir~ consistente se e solo se ~2x~ W ~ . 1~ o~vio che i sistemi formMi ctassici possono esser vis~i come particolari /7(~) e c h e l a loro consistenzu ~ bene espressa dalla definizione che precede. Sia ora C -----{x: ~(~) ~ consistente}. Si ha: C ---- (x: per ogni w ~ (o la macchina P ~ compie, sull'(( input ~) ~ x almeno w passi}. P e r il cot. 2 C ~ F*-rappresentabile e 1~ (o), con le precisazioni implicite in quanto si ~ de,to, ~ ver~. Va da s~ che molte Mtre possibili precisazioni dalla (o) sono vere. P e r esempio facile vedere che l'espressione gSdeliana classica della consistenza di /~ ~ in Vo. Come ci si p o t e v a a t t e n d e r e / 7 * non ~ invece in grado di decidere circa certe formulazioni della sua eonsistenzn, ~ a cui quelle pih (( na~urali ~. P e r vcderlo osservi~mo int~nto che molte delle dimostrazioni ~atte nel § 5 sono formulizzabili i n / 7 . :Non ci interessa per ora ricavare il massimo in tale direzione ma solo dare Mcune ovvie proprietg di 17o. F a c i l m e n t e si t r o v e : TEol~. 9. - Se E(x~,x~, ..., x~, y , z ) ~ una PR-]ormula (con le variabili libere x~, x2 ~ ..., x~, y, z) allora~ quali che siano x~, x~, ..., x~ ~ c9 si ha:

i ~ 3y V z E ( ~ ~ , ..., ~ , y, z) -> ~/~(~y V z E ( ~ ~ , ..., ~,, y, z) ) TEOIL 10. - Va[gono le: (36,1) (36,2) (36~3)

I ~ I?o(pA q)~-~ 7o(7)1\ ?0(77)

(36,4) (36,51)

se I ~ p

(36,52)

se I~l?0(~) a11ora l ~ p

allora [ ~ I~0(~)

Si ~ fin qui ragionato supponendo la validit~ di F : in realt~ gran parte di quanto si 5 visto pub essere stabilito sotto ipotesi assai pi/1 deboli usando, oltre a t~li ipotesi, solo i mezzi di F. I n p~rtieolare il teor. 9 e le (36) ad eecezione della (36,52) possono essere dimostrati sotto l'ipotesi che F sis eonsistente e la {36,52) sotto l'ipotesi della o~-coerenza.

~0BE~T0 ~AGA~: Signi]icato e verith nell'aritmetiea peania~,a

365

Usando le propriet~ elencate e il l e m m a di diagonalizzazione si possono ora facilm e n t e riprodurre i ragionamen¢i elassici che portano al primo e al secondo teorema di indecidibilit~ di GSdet. Anzitutto dal lemma di diagonalizzazione si rieava l'esistenza d i u n a p per eui: (37,1)

~-p¢-~ ~ l?o(~) ossia:

(37.2)

~- -~pe-+ 17o(~).

Se fosse p E Vo sarebbe Fo(~) e Vo (per la (36,51) e quindi -~p e Fo). Se fosse -~p e Vo si avrebbe 17o@)~ Vo da eui, per la (36,52), p ~ Vo. Se F b eonsistente b d u n q u e p ~ Vo e se 2' ~ ~o-eoerente -~ p ~ Vo onde infine p ~ P o , p e v - vo. I1 primo teorema di GSdel assume nel nostro caso la forma: T~ol~. 11. - Se ~ ~ o)-eoerente allora esistono proposizioni insensate (10.). Dalla (37,2) t e n u t o eonto della (36,2) si ricavu:

(3s)

Vo(

onde ancora dalla (37,2) e dalla (36,4): (39)

I ~ ~?o(P) --> I?o( ~-P)-

Supponiamo ora ehe sia in Vo una formulazione della eonsistenza di F * cla cui si ricavi in particolare:

I ~ -1 ~o(0 # 0 ) . Si avrebbe successivamente:

I~-~ ~o(p/~p)

e, dalla (36,3):

[ ~ -~ (l?0(~)A l?o(~-p) e, t e n u t o conto della (39)):

I ~ -~ Fo@) da eui: J~p contro q u a n t o prima si b visto. Si ha eosi: TEol¢. 12. - Ogni ]ormulazione della consistenza di E* da vui si rieavi I ~ -~ Vo(O # O) (cib inelude ovviamente tutte te ]ormulazioni (~naturali ~>) ~ insensata. (12) Questo teorema ammette vari rafforzamenti di cui ci occuperemo ia ua lavoro suecessivo. ]~ chiaro ad esempio che, imitando il procedimento di Rosser [21], l'ipotesi di o)-coerenza pltb essere sostituita dall'ipotesi di consistenza.

366

R OBE~O )IAGARI: Signi]icato e veritd nell'aritmetica peaniana

Poich~, dati i legami Ira le consistenzu di F e lu consistenza di F * ogni formulazione plausibile della consistenza di F* ~ una formalazione sia pure non <(naturMe ~) della consistenza di F resta chiarita la riserva fatt~ all'inizio di questo paragrafo sulla validit~ indiscriminata della (o). Le situazioni rapidamente accennute in questo paragr~fo merit~no un'ulteriore analisi cui sar£ dedicato un successivo lavoro.

8. - P r o b l e m i aperti e t e m i per ulteriori rieerche.

1) AnMisi dettagtiata di quanto della metateoria di F* ~ formalizzabile in F o in F*. I n particolare per quest'ultimo aspetto sorgono problemi metodologiei legati alla concezione di F * come teoria che procede per t e n t a t i v i ed errori, nello spirito indieato in [13]. 2) AnMisi dei rapporti fra i concetti qui proposti e la concezione intuizionistica. 3) Analisi del rapporto fra Vo e le teorie ordinMi (Tv~z~G [26], FEFER~A~ [3]). 4) J~ o w i a m e n t e possibile definire certi V. ponendo (tenuto presente l'insieme Vo definite in questo l~voro). V~+I ~ il minimo insieme per eui:

(i)

V~ c V~+~

(ii) se p, p -~ q ~ V.+I ~llora q ~ V.+I (iii) se -~p -~ l?~(-~p) e V~+~ e ~ p ~ V~ allor~ p ~ V~+I (pifl precisamente dei V~, F~).

oceorre

dare

un~

definizione i n d u t t i v a

simult~ne~

5) L a considerazione dell'algebra di L i n d e n b a u m del sistema F (o del sistema F*) suggerisce lo studio della variet£ di algebre definita come segue. Definiumo per induzione incrociata il tipo e le identitY. t)asso O. Sono simboli di operazioni cerfi simboli per le operazioni booleane e un ulteriore simbolo di operazione unariu, ~. Sono identit~ le identit~ booleane e inoltre le:

T=I~ T(p. q) = ~p. ~q ~(p -> q) < ~p --> ~q,

ROB]~RT0 MAGARI: Signi]icato e verit5 nell'aritmetica peanlana

367

Passo (n ~-1). Sin /(x, y~, ...~ y~) u n polinomio a s t r a t t o costruito con le operazioni fin qui introdotte~ tale che la variabile x occorra solo sotto l'azione di (per esempio si p o t r e b b e considerate il polinomio ~(x ~ y ) . z - + (u-+ rx')). Si introduce ~llor~ u n n a o v o simbolo di oper~zione n-aria ]* e Fidentit~: ]*(y~, Y2, ...,

..., y ° ) ,

..., yo).

facile vedere t h e le algebre di questa variet~ h~nno molte dene propriet~ rilev a n t i del sistema F(F*). Lo studio della variet~ e della sun sottoclasse costituita dalle algebre per cui se ~p = 1 atlora p = l d o v r e b b e chiarire certi aspetti di F(F*).

BIBLIOGRAFIA (*)

[1] A. R. ANDERSON, Minds and Machines, Englewood Cliffs, N.J., Prentice Hall, 1964. [2] P. BENACERRAF, God, the Devil and GSdel, Monist, 51 (1967). [3] S. F~:FERMAN, Ordinal logics re.examined and On the strenght o/ ordinal logics, J.S.L., 23 (1958), pp. 105-106. [4] S. FEFERMAN, Arithmetization o/ metamathematics in a general setting, Fund. Math., 49 (1960), loP. 35-92. [5] F. H. GEORGE, The Brain as a Computer, London, Pergamon Press, 1961. [6] M. GOLD, Limiting reeursion, J.S.L., 30 (1965), loP. 28-48. [7] HINTIKKA, The philosophy o/ Mathematics, London, Oxford, Univ. Press (1969). [8] G. KREIS~L, Mathematical Logic, sta in: Bertrand t~ussell: Philosophy o/ century, ed. da R. SI~OENMAN~¢, Boston, 1967. [9] G. KR~ISEL, Mathematical logic, sta in. Lectures on Modern Mathematics, vol. I I I , PP. 95-196, ed. da T. L. SAATV, John Wiley and Sons Inc., New York, 1965. [10] LACEY - GEOFFREY, What the GSdel /ormula says, Mind, 77 (1968). [11] ~f. H. L6B, Solution o/ a problem o/ Leon Henkin, J.S.L., 20 (1955), pp. 115-118. [12] J. R. LuCAs, Minds, Machines and G6del, Philosophy, 36 (1961), pp. 112-127. [13] R. MAG.~RI, Su certe teorie non enumerabili (Sulle limitazioni dei sistemi /ormali, I), in eorso di pubblicazione su questi Annali. [14] R. MAGARI, Meaning and truth in the Peano arithmetic, in eorso di loubblicazione sugli Atti dell'Aecademia Nazionale dei Lineei. [15] C. MANGIONE,Su alcune questioni connesse con i principi di riflessione, Symloosia Mathematic~ dell'Istituto Nazion~le di Alta Matomatica, $ (1969), 10p. 189-201. [16] E. MENDELSON, Introduction to Mathematical Log@, New York, 1964. [17] K. POPPER, Congetture e eon/.utazo~i, I1 Mulino, Bologna, 1969. [18] H. PVTNAM, Trial and error predicates, J.S.L., 30 (1965), PP. 49-57. [19] H. PUTNAM, Minds and Machines, sta in: Dimensions o/ Mind, ed. da SIDNEY HOOK, New York, Collier, 1961, pp. 138-164. [20] H. ROGERS jr., Theory o/ reeursive /unctions and ef/eetive computability, McGraw.Hill, New York, 1967. [21] J. B. R o s s ~ , Extension o/some theorems o/Gddel and Church, J.S.L., 1 (1936), pp. 87-91.

(*) La presente bibliografia 6 limitata ai tavori direttamente citati e a poehi altri e non ha ovviamente loretese di comloletezza (e nemmeno di raloloresentativit~).

368

ROBERTO MAGARI: Signi]icato e verit5 nell'argtmetica peaniana

[22] B. RVSSELL, I principi della matema~ica (trad. italiana di: The Principles of Mathematics, 1903), Longanesi, Milano, 1963. [23] J. R. S~OE~-~'I~LD, Mathematical Logic, Addison-~Veslcy Publ. Co., London, 1967. [24] J. J. C. SMART, Philosophy and scientific realism, Int. Library of Philosophy and scientific method, Routledgc and Kegan Paul Ltd., London, 1963. [25] A. T.~RSKI, Der Wahrheitsbegriff in den formalisierten Sprachen, Studia philosophica, vol. 1, pp. 261-405. [26] A. M. TuRI~G, Systems of logic based on ordinals, Proc. London Math. Soc., ser. 2, 45 (1939), pp. 161-228.