13. RETROSPETTIVA STORICA: l'aritmetizzazione dell'analisi.

   In questo (e, in parte, nei prossimi due paragrafi) illustreremo alcuni pezzi di storia della matematica che costituiscono premesse al travaglio di cui si è discusso nella sezione 1 e, per vari aspetti, allo sviluppo sia della logica che della formalizzazione del concetto di algoritmo.

Su numeri naturali, analisi e geometria

   L'analisi si appoggiava alla geometria: i numeri reali erano intesi come grandezze geometriche, il significato delle operazioni era fondato su considerazioni geometriche. Somma e differenza erano ricondotte alla somma e alla differenza di segmenti. La divisione veniva introdotta come rapporto tra segmenti.   Moltiplicazione:
se a e b sono le misure di due segmenti S1 e S2 rispetto all'unità di misura OU, a·b è la misura del segmento QT costruito nel modo seguente:
preso P su r tale che UP sia uguale a S1, presa comunque s passante per O e diversa da r, preso Q su s tale che OQ sia uguale a S2, tracciata la parallela a UQ passante per P, T è il punto in cui questa interseca s.
   La giustificazione di questa scelta si appoggia sul teorema delle proiezioni parallele:
   QT / OQ = UP / OU.
   Fino agli inizi del XIX secolo (prima della messa a fuoco della esigenza di dare status autonomo alla matematica, di cui abbiamo già parlato) ci si accontentava di questa impostazione. Ma chi ci garantisce che esista un modello per gli assiomi della geometria euclidea?
   Questo problema non turbava i matematici di allora: gli assiomi della geometria venivano intesi come una descrizione dello spazio fisico: la matematica aveva nella fisica i suoi fondamenti (analogamente non ci si preoccupava di definire matematicamente che cos'è una funzione: veniva intesa come la descrizione di una "legge" che lega una grandezza fisica a un'altra grandezza). Solo tra la fine del XIX e l'inizio del XX secolo, messa nitidamente a fuoco la necessità di dimostrare la non contraddittorietà degli assiomi della geometria euclidea, si raggiunge questo obiettivo dimostrando che R3 (punti: terne di numeri reali, piani: equazioni lineari, distanza come funzione R3xR3 in R, ...) ne è un modello. Ma, supposto di definire R mediante un sistema di assiomi, chi mi garantisce che esista un (solo) modello di essi, cioè che R esista effettivamente? (l'esistenza di un modello degli assiomi, per altro, mi garantirebbe che gli assiomi non presentano contraddizioni)
   Il problema della definizione di R, invero, lo avevano già affrontato (intorno al 1870) Dedekind e, separatamente, Cantor. Non lo inquadravano nell'ambito delle questioni a cui abbiamo accennato sopra (esistono modelli degli assiomi di R e degli assiomi della geometria euclidea?), che sono state formulate successivamente, ma avevano l'obiettivo di dare una costruzione di R autonoma dalla geometria, a partire dai numeri naturali. Questo obiettivo viene usualmente descritto come aritmetizzazione dell'analisi ed era, in qualche modo, una prosecuzione del lavoro di precisazione dei concetti dell'analisi infinitesimale (che superasse il ricorso all'idea intuitiva di infinitesimo) avviato da Cauchy e da Bolzano (sviluppi di questo lavoro saranno la messa a punto del concetto di funzione e la trattazione dei numeri transfiniti, che Cantor affronterà dando origine alla teoria degli insiemi).

   Vediamo, dunque, a flash, la costruzione di R a partire da N, assunto come noto (e inteso come struttura (N,+,0,·,1)), seguendo (con un linguaggio più "moderno" ) più o meno l'itinerario di Dedekind.

#    Z viene introdotto come NxN; l'idea è quella di introdurre i numeri relativi come differenze tra numeri naturali: le coppie (7,5), (3,1), ... hanno differenza "positiva" pari a 2, le coppie (0,4), (2,6), ... hanno differenza "negativa" pari a -4.
   Così come consideriamo uguali come numeri naturali le diverse espressioni 3, 03, 003, ..., così ci poniamo il problema di quando due coppie (x,y) e (z,w) (x,y,z,wN) siano da considerate uguali come numeri relativi.
   Per ricondursi a (N,+,0) possiamo porre:
(x,y) =Z (z,w) sta per: x+w = y+z
(idea: sottrazione come operazione opposta dell'addizione: x-y=z-w sse x+w=z+y).
   =Z è una buona definizione di uguaglianza?
   Si può verificare facilmente che è riflessiva, simmetrica e transitiva.
   Possiamo definire l'opposto di un numero relativo (m,n) così: -(m,n) sta per: (n,m). È una buona definizione, cioè se (p,q) =Z (m,n) ho che -(p,q) =Z -(m,n)? Anche questa verifica è facile.
   Per l'addizione l'idea è semplice: (m,n) +Z (p,q) sta per: (m+p,n+q). È una buona definizione?
Se (*): (x,y) =Z (m,n) e (z,w) =Z (p,q) devo avere: (x,y) +Z (z,w) =Z (m,n) +Z (p,q),
cioè: (x+z,y+w) =Z (m+p,n+q), cioè: (n+q)+(x+z) = (m+p)+(y+w),
che, per le proprietà di (N,+,0,·,1), equivale a: (x+n)+(z+q) = (y+m)+(w+p), e ciò segue da (*).

#    Q: ZxZ    (x,y) =Q (z,w) sta per (scrivendo = invece di =Z e · invece di ·Z) x·w=y·z
(si noti l'analogia formale con la definizione di =Z; ora l'idea è quella di divisione come operazione opposta della moltiplicazione)    Poi si definiscono addizione, ...

Nota.   Ai nostri giorni gli "algebristi" soppiantano la parola "uguaglianza" con la parola "relazione di equivalenza" e, ad esempio, considerano come numeri interi la classi di equivalenza indotte da =Z, riconducendo così l'eguaglianza tra numeri interi all'uguaglianza tra insiemi. La sostanza non cambia.

#   R (secondo Dedekind) come insieme degli intervalli "(" di Q (intervalli finali senza primo elemento, pensabili come intersezioni con Q di intervalli di R del tipo (a,))
[dato un insieme ordinato (I,<), un intervallo di I è un sottoinsieme A di I tale che (x,yA, x<z<y) => zA; un intervallo finale è un sottoinsieme A tale che (xA, x<y) => yA; un sottoinsieme A è senza primo elemento se xA => y(yA, y<x)]
   Ad esempio 2 verrebbe rappresentato come {x Q / x·x>2}.
-   Se x è A e y è B l'eguaglianza di x e y viene ricondotta all'eguaglianza tra A e B,
-   come x+Ry si prende C={a+b / aA, bB}; è meno semplice (occorre qualche trucco) si possono definire le altre operazioni. 
   Cantor definì, invece (con un approccio più semplice e per vari versi più significativo, su cui ritorneremo) i numeri reali come successioni di numeri razionali soddisfacenti la condizione di Cauchy, definì due successioni x e y uguali "come numeri" se x(n)-y(n 0 per n  , definì x+y come (x+y)(n)=x(n)+y(n), ... . La condizione di Cauchy è infatti equivalente (in R) all'esistenza del limite e, quindi, permette di individuare l'insieme di tutte le successioni convergenti senza menzionare i numeri a cui esse convergono, che, appunto, costituiscono l'insieme dei numeri reali.
   Non è altro che la formalizzazione della pratica didattica di introdurre i numeri reali come numeri decimali illimitati (o sessagesimali illimitati, come sostanzialmente facevano i Babilonesi, o binari illimitati …): la successione delle approssimazioni per troncamento di un numero reale non è altro che un rappresentante delle successioni di Cauchy convergenti ad esso. Il fatto che 1.999… e 2.00… sia diverse come espressioni ed uguali come numeri (vedi) trova traduzione del fatto che la successione 2.0-1.9, 2.00-1.99, 2.000-1.999, … tende a 0.
   Potremmo anche dire che, come il passaggio da N a Z permette di rendere sempre definita la sottrazione , il passaggio a Q permette di rendere sempre definita la divisione per numeri diversi da 0, così il passaggio a R consente di determinare il limite di ogni successione di Cauchy.

   Ci siamo ricondotti a (N,+,0,·,1). Ma che cos'è (N,+,0,·,1)? Una soluzione proposta intorno al 1890 (Peano e altri), formulata in linguaggio "moderno":

   A=(A,@,f) struttura,  @: elemento ( @A),  f: operazione unaria (f:A  A)
   (1)   non esiste x in A t.c. f(x) = @
   (2)   f è iniettiva
   (3)   @  I A  &  f(I) I   =>   I = A
   Queste proprietà sono state scelte per cercare di catturare l'idea intuitiva di numero naturale (@ sarebbe 0, f l'operazione S di passaggio al successore): 0 non è successore di altri numeri, numeri diversi hanno successori diversi, principio di induzione [indichiamo P(x) la proprietà: xI; (3) diventa: P(0) & n (P(n) => P(Sn)) =>n (P(n)].
   Verifichiamo che le proprietà (1), (2) e (3) sono tra loro indipendenti:

# A sia {a,b}, @ sia a, f(a) sia b, f(b) sia a.    Verifica (2),(3), ma non (1)
# A sia {a,b,c}, @ sia a, f(a) sia b, f(b) sia c, f(c) sia b.    Verifica (1),(3), ma non (2)
# A sia {a,aa,aaa, ...}{b,bb,bbb, ...}, @ sia a, f(xa) sia xaa, f(xb) sia xbb (x stringa generica).   Verifica (1),(2), ma non (3).

Due strutture A=(A,@,f) e B=(B,#,g) che verifichino (1), (2) e (3) sono tra loro isomorfe, cioè che esiste F:A  B bigettiva tale che F(@) = #, F(f(x))=g(F(x)) (avanzare con il successore di A e poi passare a B mediante F o viceversa (passando a A con F-1) dà luogo sempre agli stessi risultati.  

   A questo punto abbiamo l'unicità "a meno di isomorfismi" della struttura che verifica (1)-(3), struttura che d'ora in poi indicheremo con (N,0,S) [questa "categoricità" della descrizione è possibile in quanto si tratta di una descrizione insiemistica, non formulata in un linguaggio del primo ordine: vedi sezione 9]. Useremo le usuali notazioni per indicare gli elementi di N: 1 al posto di S(0), 2 al posto di S(S(0)), ...

   Vediamo come definire l'addizione e la moltiplicazione:
{ x+0 = x(a)      { x·0 = 0
x+S(y) = S(x+y)   (b) x·S(y) = x·y + x   

   Calcoliamo usando {(a),(b)} 1+2:    1)   1+2 = S(1+1)   
2)   1+1 = S(1+0)
3)   1+0 = 1
4)   1+1 = 2
5)   1+2 = 3
per (b)
per (b)
per (a)
per 3), 2)
per 4), 1)

"+" è definita su tutto NxN (a) garantisce che è definita su Nx{0}. La la proprietà (3) (induzione) mi permette di completare la dimostrazione:
sia I l'insieme degli n per cui + è definita su Nx{n}; abbiamo ora visto che 0  I; da (b) si deduce che se n  I allora anche S(n I; quindi, per (3), I = N.

   A partire dagli "assiomi" (1)-(3) si possono dimostrare le proprietà associativa e commutativa (per "+" e "·"), la proprietà distributiva, ....
Esercizio: dimostrare la commutatività di "+". [soluz.]

   Abbiamo risolto tutti i nostri problemi? ... No: chi ci garantisce che esiste un modello di (1)-(3)?

   Si può tentare di trovare una soluzione alternativa definendo i numeri naturali all'interno della teoria degli insiemi: definizione di insieme finito, numero naturale come classe di equipotenza nell'insieme degli insiemi finiti, addizione come unione disgiunta di insiemi finiti, ... ma nella teoria degli insiemi per poter trattare insiemi infiniti (e, in particolare, N) bisogna introdurre un "assioma dell'infinito" che, sostanzialmente, postula l'esistenza di N (ciò verrà richiamato nella prossima sezione). E allora?
   Si potrebbe tentare di dimostrare la non contraddittorietà di (1)-(3) senza cercare di costruire un modello e usando metodi dimostrativi più elementari delle argomentazioni aritmetiche (ragionamenti di tipo combinatorio che si basino su assunzioni più deboli di (1)-(3), altrimenti non usciremmo dal circolo vizioso, e si riferiscano alla manipolazione di insiemi finiti, in modo da avere un'evidenza più concreta). Questo era, grosso modo, l'obiettivo che aveva definito Hilbert nei primi anni del XX sec., ma Gödel, con il suo secondo teorema di incompletezza (1931), ha messo praticamente la parola "fine" a questi tentativi (vi era, poi, il fatto che, espressa in una logica del 1° ordine, l'aritmetica perdeva la categoricità: vedi sezione 9).

   Non abbiamo, dunque, prove "assolute" della coerenza degli assiomi di R e degli assiomi della geometria euclidea, ma abbiamo solo la prova che se uno dei due sistemi di assiomi è coerente allora è coerente anche l'altro (dimostrazione "relativa" di coerenza).
   Ci si può accontentare di prendere per buono il concetto intuitivo di successione e cercare di "costruire" la matematica sulla base di questo, attraverso procedimenti "algoritmici", o si possono assumere come presupposto la consistenza della teoria dei numeri naturali (basando questa assunzione sull'esperienza secolare degli uomini nel campo dei calcoli e delle dimostrazioni relative ai numeri naturali) e la possibilità di lavorare con enti infiniti. Queste due diverse prospettive sono note come matematica "costruttiva" e matematica "classica", fondata sulla teoria degli insiemi.
   Osserviamo, tuttavia, che, ormai, il dibattito sui "fondamenti della matematica" non è più una guerra di religione tra "fedi" diverse (anche se c'è qualche "filosofo" che discetta ancora con questo spirito) ma è una riflessione più strettamente legata all'analisi del modo in cui lavorano i matematici, che non è tanto alla ricerca di presupposti metafisici o "prematematici" ma è soprattutto rivolto all'analisi del ruolo di linguaggi formali e metodi dimostrativi, dei problemi legati ai passaggi tra teorie matematiche diverse (la traduzione della geometria nell'algebra, un problema dei numeri reali affrontato nell'ambito dei numeri complessi, un problema di aritmetica elementare affrontato topologicamente, la dimostrazione della consistenza di una teoria svolta in un'altra teoria, ...).
   La natura degli "oggetti matematici" non si può definire cercando l'idea platonica giusta o la realtà concreta fondante, ma, più laicamente, il significato degli oggetti della matematica si chiarisce attraverso la loro rappresentazione in linguaggi e teorie diverse, attraverso la possibilità di dare interpretazioni diverse dello stesso formalismo, attraverso l'individuazione di analogie e differenze di fondo, attraverso processi di successiva delimitazione/estensione e raffinamento dei concetti (intuitivi o più o meno formalizzati) che possono anche biforcarsi, ... . Questa è la matematica dei "matematici", sia la matematica "pura" che la matematica "applicata".

Nota didattica.  In vari libri delle superiori, per evidenti incomprensioni degli autori, si cerca di riprodurre questo tentativo di ricostruzione di R a partire da N senza mettere in luce gli obiettivi puramente fondazionali che esso aveva. Si arriva, persino, a parlare di numeri interi senza segno e a distinguerli dai numeri interni non negativi − si scrivono cose del tipo (+2)+(+5)!!! − manifestando un evidente confusione tra la natura dei numeri reali e i tentativi di di ricondurre essi, con sofisticate tecniche logiche (e sofisticati obiettivi), a concetti più "elementari".

   Nelle prossime sezioni esamineremo un po' più da vicino i fondamenti dell'approccio classico e quelli dell'approccio costruttivo.


14. MATEMATICA CLASSICA. TEORIA DEGLI INSIEMI

   Abbiamo già osservato (nelle sezioni 1 e 13) che, in relazione a sviluppi economico-tecnologico-culturali, variamente intrecciati, si sviluppa l'esigenza di dare uno status autonomo alla matematica; fenomeno che, con linguaggio moderno, potremmo identificare con la nascita del concetto di modello matematico [qui "modello" è usato in modo "rovesciato" rispetto a quanto si fa in Logica: è la rappresentazione astratta di una realtà, mentre in Logica è, in qualche modo, la esemplificazione concreta di una teoria) : ai concetti matematici come enti perfetti che trovano nei rapporti con il mondo reale il loro fondamento, alle proprietà matematiche come verità relative a questi enti, subentrano i concetti matematici come oggetti definiti indipendentemente dalla realtà fisica, che "possono" essere usati per rappresentare diversi aspetti della "realtà", sia fisica che sociale o frutto di costruzioni del pensiero umano - anche realtà matematica, quindi - e le cui proprietà hanno natura formale, essendo legate ad essi da contesti definitori o deduttivi, non da concezioni metafisiche.
   Lo sviluppo di questo passaggio dall'ontologia (concetti matematici come enti a priori e/o come raffinamento di enti reali) alla logica si compie alla fine del XIX secolo e si innesta su due diversi filoni di indagine "logica" già avviatisi, miranti a (1) formalizzare completamente le argomentazioni e (2) rendere autonome la definizioni dei concetti matematici (in particolare dell'analisi).

(1)  Questo filone va, grosso modo, da Boole (~1850, algebrizzazione dei connettivi) a Frege, che (~1880) introdusse la nozione di sistema formale e, in particolare, il calcolo dei predicati, ma in mezzo ci sono molti altri personaggi (De Morgan, Peirce, Peano, ...).
(2)  Sull'aritmetizzazione dell'analisi (precisazione dei concetti infinitesimali, tentativo di ricondurre i numeri reali ai numeri naturali, definizione autonoma del concetto di funzione, ...) ci siamo già soffermati; essa conduce alle prime assiomatizzazioni dei numeri naturali, alle prime definizioni di insieme "finito", all'esigenza di precisare il concetto di numero transfinito (in relazioni ad alcune questioni di analisi matematica) e, infine, alle prime formulazioni, non formalizzate, della teoria degli insiemi (Bolzano, Dedekind, Peano e, infine, ~1880, Cantor).

   Si tratti di filoni che in qualche modo erano già presenti (pur se mescolati a considerazioni filosofiche, fisiche, ...) al tempo dei "Greci" (Aristotele, Euclide, ... da una parte; Archimede dall'altra). Ora i due filoni tendono a fondersi.
   Possiamo emblematizzare la fusione con il tentativo dello stesso Frege (~1890) di formalizzare la teoria degli insiemi, ossia di realizzare una presentazione della "matematica" come "logica" + "teoria degli insiemi". Sostanzialmente questa è la presentazione "classica" che caratterizza l'insegnamento universitario di base dei nostri giorni; più avanti vedremo come si è differenziato da questa impostazione l'approccio costruttivista, a cui abbiamo già accennato nelle sezioni 1 e 13.

Teoria degli insiemi di Frege (presentata "modernamente"):

Teoria del 1° ordine con identità.
Simbolo specifico: (lettera predicativa a 2 posti)
Termini: variabili e espressioni del tipo {x / A} con x libera in A 
F1 (assioma [schema] di astrazione):   x{y / A(y)} A(x)  
   Che cosa garantisce che {y / A(y)} è unico? L'assioma:  
F2 (assioma di estensionalità):   x=y z(zx zy) 
   Volendo si può fare a meno di {.../...}, o si può introdurlo dopo, come abbreviazione:
F1 diventerebbe   yx (xy A(x))

   Non tutto filò liscio. Infatti:
definito V come abbreviazione di {x/x=x} (sarebbe l'"universo") si dimostra facilmente il teorema  VV;
indicato con F il termine {x / ¬xx}, si può dimostrare (Russel, 1902) il teorema  FF ¬FF.
    Questo "paradosso" fu risolto analizzando più a fondo gli usi del concetto insieme nella pratica matematica e individuando due possibili strade, sostanzialmente equivalenti: (1) restringere l'astrazione alla costruzione di sottoinsiemi di insiemi già costruiti (Zermelo, 1908, con revisione di Fraenkel, 1922: teoria ZF) o (2) distinguere tra classi - termini generici - e insiemi - classi che sono elementi di altre classi - (Von Neumann, 1924, Bernays, 1937, e Gödel, 1940: teoria NBG). Esaminiamo (1).

Teoria ZF

ZF1 (schema di separazione o di comprensione): yx (xy xz & A(x))

ZF2: uguale a F2
L'unicità dell'"y" di ZF1 è garantita da ZF2. Uso l'abbreviazione {xz / A(x)}.

Dobbiamo avere qualche insieme da cui partire. Introduciamo la costante Ø e: 
ZF3 (assioma dell'insieme vuoto): Ø = {xØ / ¬x=x}
[si ha facilmente che è un (l'unico) insieme senza elementi: da x(xØ), ZF1 e ZF3 si avrebbe x(¬x=x)]

ZF4 (assioma dell'insieme coppia): wx (xw (x=y V x=z))
[ w diventerà {y,z}: grazie a ZF2 ho l'unicità di w, e posso quindi fare un'estensione conservativa introducendo il simbolo {.,.} ]

ZF5 (assioma dell'insieme unione): zx (xz w(xw & wy))
[ U(y); es.: U({a,b}) = aUb ]

ZF6 (assioma dell'insieme potenza): zx (xz w(wx    wy))
[ P(y): collezione dei sottoinsiemi di y ]

Fin qui possiamo ottenere solo insiemi finiti. 
ZF7 (assioma dell'infinito): x (Øx & y(yx    P(y)x))
[ N: idea 0 è Ø, 1 è {Ø}, 2 è {Ø, {Ø}}, 3 è {Ø, {Ø}, {Ø, {Ø}}}, ...; N è la loro collezione; ZF7 garantisce che esiste un insieme x che contiene N; N, indicato con ω nel contesto della teoria degli insiemi, è poi costruibile usando ZF1: ω = {zx / z=0 V y z=y{y}]

ZF8 (schema di rimpiazzamento):
(A(x,y) & A(x,z)    y=z)    zy (yz x(xw & A(x,y))
[ l'immagine mediante una funzione (la premessa dice che la relazione A è una funzione) di un insieme è un insieme; consente di costruire insiemi collezionando insiemi (w è l'insieme degli "indici": z è {ax / xw} se indichiamo y con ax); ZF1 è derivabile da ZF8 ]

Assioma non di "costruzione", ma "limitativo", per evitare catene "discendenti" di "" senza fine (occorre partire da degli "atomi"), e, quindi, evitare anche insiemi come l'"F" di Russel (usando ZF9 si ottiene che z ¬zz in quanto altrimenti avremmo una catena ...zzzz...; z ¬zz è ottenibile anche direttamente: poiché z è l'unico elemento di {z}, da ZF9 ho z{z}=Ø; F sarebbe quindi l'universo, che non può essere costruito in ZF): 
ZF9 (assioma di fondazione o regolarità): ¬ x=Ø    y(yx & yx=Ø)
[ se ...x3x2x1 l'insieme { x1,x2,x3,...} non avrebbe elementi privi di elementi in comune con se stesso ]

Assioma per "costruire" nuovi insiemi, ma, intuitivamente, poco "costruttivo", per cui per lungo tempo si è sospettato che potesse condurre a nuove contraddizioni (Fun(y) e Dom(y)=x rappresentano opportune formule che esprimono il fatto che y è una funzione e che x è il suo dominio): 
ZF10 (assioma di scelta): ¬ Ø x    y(Fun(y) & Dom(y)=x & zx    y(z)z)
[ garantisce che, se ho una collezione x di insiemi, posso scegliere un elemento da ciascuno di essi (che non sia vuoto); y è la funzione di scelta, che sceglie un elemento da ciascun insieme della famiglia di insiemi x. Equivalgono all'assioma di scelta, presenti gli altri assiomi, il "teorema di Zorn" (ogni insieme ordinato induttivo ha un elemento massimale) e varie altri teoremi d'uso comune (es.: x≤y V y≤x, per numeri transfiniti) ]
Gödel dimostrò (1938) che l'assioma di scelta è coerente con ZF1-ZF9: se si può derivare una contraddizione usando ZF10, allora la si può derivare senza usarlo.

Esercizio.  Prima di affrontare l'approccio costruttivista, vediamo come, alla luce della considerazioni sulla teoria della calcolabilità, possono sorgere dei dubbi sull'uso indiscriminato dell'estensionalità. Osserviamo in particolare che,
- se Fn è una numerazione delle funzioni calcolabili da N in N, definite rispetto a una qualunque formalizzazione (come programmi TP, come macchine TM, come macchine a registri, … o come funzioni ricorsive), numerazione realizzabile in vari modi (ad es., nel caso TP, ordinando i programmi per lunghezza e, a parità di lunghezza, alfabeticamente, e indicando con Fn la funzione a input e output in N che a x associa il successore della lunghezza della eventuale stringa di "1" che si ottiene come output dall'n-esimo programma di TP se gli si dà in input la stringa di x+1 "1"), e
- se usiamo "=est" per indicare che due funzioni calcolabili sono estensionalmente equivalenti, ossia se lo sono le loro controparti insiemistiche, ossia quelle ottenute considerando gli insiemi delle loro coppie (input, output) [F =est G se F(x) è definito sse lo è G(x) e, in caso affermativo, F(x) = G(x)],
si ha che:
() non esiste un procedimento per stabilire se, presi m e n, Fm =est Fn.
Da ciò deriva la non accettabilità di una "proprietà di estensionalità" definita come:  "Fm =est Fn → m = n", ossia la non identificabilità di funzioni che a parità di input diano gli stessi output, cosa che, invece, accade nella matematica "classica" (per la definizione insiemistica di funzione - "insieme di coppie tale che …" - ivi usata).
Si provi a dimostrare ()   [traccia: si deduca dall'esistenza del procedimento la possibilità di decidere la totalità di una funzione calcolabile, e si derivi da ciò un assurdo in modo simile a quanto si fa nella prova della indecidibilità dell'halting problem] [soluz.]


15. MATEMATICA COSTRUTTIVA

1. Sul costruttivismo

1.1    L'aggettivo COSTRUTTIVO è comunemente usato dai matematici per specificare quando il procedimento attraverso cui viene dimostrata l'esistenza di una soluzione di un dato problema permette di esibire esplicitamente tale soluzione.

1.2    Per un semplice esempio si pensi al problema dell'esistenza di due numeri irrazionali x e y tali che xy sia razionale.
   Un procedimento risolutivo non costruttivo è il seguente:

se 22 è razionale basta prendere x=y=2, altrimenti basta prendere x=22 e y=2.
   Un procedimento costruttivo consisterebbe invece nel determinare una particolare coppia di numeri x e y verificando che essi sono irrazionali e che xy è razionale.
[invero si può dimostrare che 22 è irrazionale, anzi trascendente]

1.3    Sia Q(n) (n numero intero positivo) una proprietà decidibile per cui sia ancora aperto (o si sia dimostrato essere indecidibile) il problema "per ogni n Q(n)".
   Per ogni n indichiamo con P(n) la proprietà: "per ogni kn Q(k)".
   Consideriamo la seguente successione x(.) di numeri razionali:
x(n):=0 se P(n) è vera,
x(n):= 1/m altrimenti, dove m è il minimo tra gli interi h per cui P(h) è falsa (che è anche il minimo intero h per cui Q(h) è falsa)
   La successione x(.) – costituita di valori nulli, fino all'eventuale posto m per cui Q(m) è falsa, dopo il quale proseguirebbe col valore 1/m – è definita costruttivamente poiché fissato comunque n possiamo verificare (almeno in via di principio, cioè con un calcolatore sufficientemente veloce) se P(n) è vera o è falsa e quindi determinare il valore di x(n).
   Inoltre x(.) è di Cauchy, cioè per ogni k intero positivo è possibile determinare un intero positivo M(k) tale che se M(k) ≤ mn allora |x(m)-x(n)|<1/k; basta prendere M(k)=k+1; infatti sia  k+1 ≤ n < m:
se P(m) è veraanche P(n) è vera e quindi |x(m)-x(n)|=0-0=0
se P(n) è falsaanche P(m) è falsa e quindi |x(m)-x(n)|=1/h - 1/h = 0
se P(m) è falsa e P(n) è vera  |x(m)-x(n)|=x(m) = 1/h < 1/n [poiché Q(n) è vera] ≤ 1/(k+1) < 1/k
   x(.) definisce quindi un numero reale x.
   Notiamo che è costruttiva anche la verifica che x(.) è di Cauchy; infatti non viene solo dimostrata l'esistenza della successione M(.), bensì M(.) viene esplicitata.
   Sicuramente x non è negativo; tuttavia non siamo in grado di verificare costruttivamente che x>0 (cioè determinare N tale che P(N) sia falsa) né di verificare che x=0 (cioè di dimostrare che per ogni n P(n) è vera).
   Più in generale, dato un numero reale x di cui siamo in grado di calcolare per ogni n l'approssimazione x(n) senza disporre di altre informazioni, non è detto che possiamo stabilire se, ad esempio, x>0.
   Supponiamo infatti che M(k)=k. Se troviamo che x(1000)=0.002 possiamo concludere che x>0 poiché |x(1000)-x(1000+n)|<0.001. Ma se troviamo che x(1000)=0 o che x(1000)=0.00001 non possiamo concludere nulla e non è detto che riusciamo a trovare m>1000 tale che il calcolo di x(m) ci permetta di concludere se x>0 o no.
   Questi esempi illustrano come, dati a e b numeri reali, non è sempre possibile verificare costruttivamente che una delle relazioni a<b, a=b, b<a è vera; quindi non si può provare costruttivamente la proprietà di tricotomia.

1.4    La seguente dimostrazione che per ogni numero primo m esiste un numero primo n maggiore di m è costruttiva:
       Dato m si possono determinare i numeri primi minori o uguali a m. Sia p il loro prodotto. Allora tra i numeri m+1, m+2,..., p, p+1 esiste un numero primo. Infatti o p+1 è primo o, poiché 2, 3, 5,..., m non possono essere fattori di p+1=(2·3·5·...·m)+1 (sia p=ab; se ab+1=ax allora x=b+1/a, che è intero solo se a=1), deve esserlo almeno un numero compreso tra m+1 e p.
   Quindi attraverso un numero limitato di operazioni è determinabile il più piccolo numero primo maggiore di m.
   La costruttività della dimostrazione risiede nell'aver descritto un procedimento meccanico che ad ogni numero primo associa un numero primo maggiore di esso. Che il procedimento sia meccanico deriva dall'esistenza di un algoritmo per verificare in un numero finito di passi se un numero è primo o no e dal fatto che per ogni m abbiamo visto come si può calcolare un numero t tale che partendo da m dopo al più t passaggi al numero successivo si incontri un numero primo.

1.5    Anche il fatto che esistono infiniti numeri primi è dimostrabile costruttivamente. Infatti, comunque fissi n, mediante quanto visto in 1.4, posso trovare n+1 numeri primi.
   E' possibile, costruttivamente, dedurre l'esistenza di infiniti numeri trascendenti dal fatto che i numeri algebrici sono numerabili mentre i numeri reali non lo sono?
   Sì, in quanto con il metodo diagonale, fissato comunque un insieme numerabile di numeri reali, posso costruire un numero che non sta nell'elenco. In questo modo posso, fissato comunque n, posso costruire n numeri trascendenti.
   Infatti se a1,a2,... è una numerazione dei numeri algebrici e t1,t2,...,tn sono i numeri trascendenti che voglio costruire, posso prendere:
- come prima cifra decimale di t1 una cifra diversa dalla prima cifra decimale di a1,
- come seconda cifra di t1 una cifra diversa dalla seconda cifra di a2 e come prima cifra di t2 una cifra diversa dalla prima cifra di t1,
- come terza cifra di t1 una cifra diversa dalla terza cifra di a3, come seconda cifra di t2 una cifra diversa dalla seconda cifra di a1 e come prima cifra di t3 una cifra diversa dalla prima cifra di t1,
- come quarta cifra di t1 una cifra diversa dalla quarta cifra di a4, come terza cifra di t2 una cifra diversa dalla terza cifra di t1, come seconda cifra di t1 una cifra diversa dalla seconda cifra di t2 e come prima cifra di t4 una cifra diversa dalla prima cifra di t1,
- ecc.
   In questo modo ottengo t1 diverso da tutti i numeri algebrici, t2 diverso da t1 e da tutti i numeri algebrici, ...

1.6    La dimostrazione del teorema di LIMITATEZZA DELLE FUNZIONI CONTINUE ("se f è una funzione reale continua su [a,b] allora esiste c tale che per ogni x in [a,b] |f(x)|<c") ottenuta per assurdo usando la tecnica delle bisezioni successive non è costruttiva in quanto non permette di determinare un particolare maggiorante dell'immagine di f. Tuttavia è possibile dare una dimostrazione costruttiva del teorema:
"se f è una funzione uniformemente continua su [a,b] allora esiste c tale che |f(x)|<c"
(Nota:  non esiste una dimostrazione costruttiva del teorema dell'uniforme continuità: per ogni funzione continua su [a,b] si riesce a dimostrare che esiste un modulo di uniforme continuità (vedi sotto), ma non si riesce a determinarlo. Dal punto di vista costruttivista, come vedremo, si considera solamente la continuità su intervalli definita direttamente come uniforme continuità)
[Dimostrazione, idea: costruisco partizioni di [a,b] man mano più fitte; infittendo le x(i) della partizione posso infittire le loro immagini in modo che abbiano un salto piccolo quanto voglio; posso allora man mano scegliere maggioranti di esse sempre più vicini e tali da dar luogo a una successione che definisce un numero reale maggiore dell'immagine di ogni x di [a,b];  traccia:
   Sia M un modulo di uniforme continuità per f, cioè per ogni intero positivo n il numero intero positivo M(n) sia tale che per ogni x,y in [a,b] con |x-y|<1/M(n) si abbia |f(x)-f(y)|<1/n.
   Si costruisce una partizione a(n,j) [j=0, ...,k] di [a,b] con maglia minore di 1/M(n).
   Determino J tale che f(a(n,J))>f(a(n,j))-1/n per ogni j (non posso prendere il valore f(a(n,J)) massimo tra i valori f(a(n,j)), j=0,..., k, ma solo un valore che a meno di 1/n è maggiore di tutti gli altri: non è infatti detto che dati due o più numeri reali si riesca a individuarne costruttivamente il massimo - cfr. 1.3). Indico con y(n) il numero f(a(n,J))+1. .
   Si dimostra che y(n) è di Cauchy e che il suo limite è un maggiorante dell'immagine di f. Analogamente posso costruire un minorante di f.]

1.7    Del TEOREMA DEGLI ZERI ("se f è una funzione reale continua su [a,b] tale che f(a)<0 e f(b)>0, allora esiste c in (a,b) tale che f(c)=0") non esiste alcuna prova costruttiva (neanche sostituendo la continuità con l'uniforme continuità).
   La dimostrazione (sostanzialmente ideata da Bolzano) che si basa sul principio dell'estremo superiore (dal quale si ricava l'esistenza dell'estremo superiore c dell'insieme degli x in [a,b] tali che f(x)<0, dopo di che si prova che né f(c)<0 né f(c)>0) non fornisce un procedimento che data f permetta di determinare effettivamente c e di verificare direttamente che f(c)=0.
   Del resto, evidentemente (si pensi all'insieme costituito dagli elementi della successione considerata in 1.3), la formulazione classica del principio dell'estremo superiore non vale costruttivamente.
   Anche la dimostrazione (successivamente ideata da Cauchy) che si basa sul metodo dicotomico (bisezioni successive) non è costruttiva: non è detto che sia possibile determinare costruttivamente il segno di f((a+b)/2) (cfr. 1.3).
   Si possono ottenere dimostrazioni costruttive imponendo particolari condizioni su f. Oppure si può ottenere una dimostrazione costruttiva di:
se f è uniformemente continua in [a,b], f(a)<0 e f(b)>0, allora per ogni k esiste x in [a,b] tale che |f(x)|<1/k.
    Vediamo un esempio di funzione (uniformemente) continua in [0, 1] che cambia segno in tale intervallo ma per la quale non si può determinare l'input per cui vale zero:
 F(x) = 3x-1   se  x ≤ 1/3+q/3
 F(x) = q   se  1/3+q/3 ≤ x ≤ 2/3+q/3
 F(x) = 3x-2   se  2/3+q/3 ≤ x
dove q è un numero di cui non siano in grado di determinare il segno, come il numero x considerato in 1.3.
    Non conosciamo il segno di q, per cui il grafico di F potrebbe attraversare l'asse x in 1/3 (se q>0), in 2/3 (se q<0) o nell'intervallo [1/3, 2/3]: abbiamo un'incertezza di ampiezza 1/3; non possiamo quindi costruire una successione convergente a uno zero di F.
 

1.8    In 1.2-1.7, appoggiandoci su una concezione "intuitiva" dell'aggettivo "costruttivo" abbiamo considerato alcuni esempi di dimostrazioni e di definizioni "costruttive", abbiamo visto che vi sono teoremi di cui sono note dimostrazioni non costruttive ma di cui è possibile ottenere una versione costruttiva e teoremi di cui invece non si hanno dimostrazioni costruttive ma di cui è possibile ottenere una versione costruttiva aggiungendo delle ipotesi "ad hoc".
   Il termine "COSTRUTTIVISMO" si riferisce alle scuole o alle tendenze che, andando oltre alle episodiche ricerche di risoluzioni costruttive di "particolari" problemi e superando la concezione "naive" della costruttività, mirano a "definire" principi e metodi costruttivi generali e a ricostruire servendosi solo di questi "intere" aree della matematica.
   Inizialmente (primi decenni del nostro secolo) sia i platonisti ("esiste" = "non porta a contraddizioni") che i costruttivisti ("esiste" = "è esibibile") ritenevano (ciascuno come argomento a proprio favore) che la rinuncia all'uso libero dei metodi insiemistici per limitarsi all'impiego di metodi costruttivi avrebbe condotto a una edificazione della matematica più "sicura" ma molto più "ridotta".
   Successivamente, anche per lo sviluppo dello studio e dell'impiego degli algoritmi (in contesti teorici e, poi, con la diffusione dei calcolatori, anche applicativi), si è esteso l'impiego di procedimenti costruttivi. In quasi tutti i settori della matematica si è diffusa una maggiore attenzione alla ricerca di prove di esistenza che, contestualmente, individuino algoritmi per esplicitare gli oggetti di cui si vuole provare l'esistenza.
   Da ciò è derivato un nuovo e maggiore interesse verso le ricerche costruttiviste, che ha permesso di riformulare in termini costruttivi gran parte della "matematica moderna", mettendo in luce la superabilità della originaria contrapposizione tra "sicurezza" e "potenza".
   E' bene sottolineare che il costruttivismo non è nato come tentativo di rifondare ex novo la matematica fino ad allora sviluppata.
   Infatti sino a buona parte del 19° secolo la matematica si è sviluppata quasi esclusivamente attraverso definizioni e dimostrazioni di tipo costruttivo. E' stato con l'introduzione dei numeri transfiniti, con la generalizzazione del concetto di funzione e, più in generale, con lo sviluppo della teoria degli insiemi, che si è sviluppata la matematica non costruttiva. Il costruttivismo è sorto come tentativo organico di delimitare l'impiego delle tecniche dimostrative che non erano ritenute intuitivamente ben fondate.
   Da un punto di vista più generale, si può dire che il costruttivismo tende a rivalutare, nell'ambito del significato dei teoremi, l'importanza dell'attività dimostrativa rispetto a quella del mero risultato di essa. Ciò in contrapposizione al matematico standard che si è venuto a delineare in questo secolo, il quale, adagiatosi su una concezione "naturalistica" della teoria degli insiemi, tende a concentrare l'attenzione sulla elaborazione di oggetti e proprietà, senza preoccuparsi di riflettere sulla struttura dei ragionamenti impiegati e sugli aspetti "formali" del linguaggio in cui li articola.
   Questa caratteristica del costruttivismo è uno dei motivi per cui esso ha trovato grande attenzione e interazioni profonde con ricerche in logica matematica, così come è avvenuto per la teoria delle categorie, che, da un versante diverso, ha anch'essa svolto una funzione di critica della chiusura/appiattimento della matematica nella dimensione insiemistica.

1.9    All'origine del costruttivismo vi sono state motivazioni "filosofiche" di contrapposizione al platonismo matematico (non si tratta, comunque, di una contrapposizione di tipo metafisico, incanalabile nei tradizionali filoni della filosofia della matematica dei "filosofi", ma essa è sorta nell'ambito di un dibattito fondazionale radicato nella storia del costituirsi della matematica come "matematica pura" e nei suoi sviluppi e interazioni con le applicazioni).
   Non si può tuttavia parlare di un'unica concezione costruttivista della matematica. Infatti all'INTUIZIONISMO (che si è avviato con Brower -inizio '900 - ed è proseguito con Heyting e i suoi allievi) si sono poi affiancate altre scuole di costruttivismo: il COSTRUTTIVISMO RUSSO e l'ANALISI RICORSIVA, a volte chiamate analisi ricorsiva russa e analisi ricorsiva classica (le due scuole, pur avendo impostazioni programmatiche differenti, hanno come risultato riformulazioni costruttive equivalenti di una stessa parte della matematica classica), e, infine, il costruttivismo di Bishop (fine anni '60) e dei suoi seguaci, detto anche NUOVO COSTRUTTIVISMO (la "matematica costruttiva" sviluppata con questo approccio è diventata negli ultimi anni quella maggiormente studiata).

2. Aspetti della concezione costruttivista comuni alle diverse scuole

2.1    GLI OGGETTI MATEMATICI o sono enti INTUITI direttamente dalla mente umana o sono ottenuti da questi mediante successive COSTRUZIONI, e le loro proprietà o sono intuite direttamente o possono essere ricavate basandosi su un'analisi del processo attraverso cui essi sono stati costruiti.
   Ad esempio la successione dei numeri naturali non è definita assiomaticamente o comunque servendosi di altri concetti più generali, ma è un concetto di base, e il principio di induzione vale in quanto connaturato al modo stesso in cui la successione dei numeri naturali viene intuita.
   Per contrapposizione si pensi che nella concezione "platonista" sono oggetti matematici di base gli insiemi, concepiti come enti esterni alla mente umana e di cui si può discutere anche senza saperli costruire.

2.2    Di un enunciato A non interessa stabilire se è vero o se è falso, basandosi su un concetto a priori di verità. Quel che interessa stabilire è se esiste (e si sa esibire) una PROVA di A, dove:
(1)  una prova di B&C consiste in una prova di B e in una prova di C, cioè in una coppia <p,q> tale che p prova B e q prova C;
(2)  una prova di B V C consiste in una coppia <j,p> dove j=1 e p prova B o j=2 e p prova C; ciò significa che tra B e C sappiamo individuare un enunciato che sappiamo dimostrare;
(3)  una prova di B=>C consiste in un'operazione costruttiva h che trasforma ogni prova p di B in una prova h(p) di C;
(4)  ¬B sta per B=>0=1; in altre parole provare ¬B significa verificare costruttivamente l'assurdità di B (ovviamente non è possibile dimostrare in generale B V ¬B poiché non è detto che si possa trovare una prova di B o una prova di B=>0=1);
(5)  una prova di xB(x) consiste in una coppia <c,p> dove c è un oggetto e p è una prova di B(c);
(6)  una prova di xB(x) consiste in un'operazione costruttiva h che trasforma ogni oggetto c (del dominio in cui varia x) in una prova h(c) di B(c).
    Nella concezione che per comodità continuiamo a chiamare "platonista" per ogni enunciato A si può provare A V ¬A, ovvero ¬¬A=>A; in particolare è possibile ottenere indirettamente risultati esistenziali: per provare xA(x) è sufficiente provare ¬x¬A(x), cioè l'assurdità di x¬A(x).
   Si noti che le dimostrazioni per assurdo sono costruttivamente accettate: si veda la definizione della negazione. Ciò che non è ammesso è il loro impiego, or ora citato, per ottenere risultati di esistenza. In particolare l'usuale dimostrazione per assurdo dell'irrazionalità di 2 è costruttiva in quanto non si dimostra l'esistenza di qualcosa, ma la sua impossibilità di esistere.

2.3    Per OPERAZIONE COSTRUTTIVA (o regola algoritmica o processo algoritmico o operazione meccanica o ...) si intende un procedimento descrivibile concretamente mediante un elenco finito di istruzioni esplicite, eseguibili meccanicamente senza implicare né attività creative né libere scelte. L'operazione può essere applicata a un oggetto o a una sequenza di oggetti. Non è detto che l'operazione produca sempre risultati, cioè sia sempre definita (in altre parole può essere "parziale").
   Del concetto di operazione costruttiva esistono interpretazioni più o meno restrittive a seconda delle diverse scuole.
   Un semplice esempio è costituito dalla operazione di coppia, che alla sequenza x,y associa il nuovo oggetto <x,y>. Questa operazione è sempre definita.
    Un INSIEME è un oggetto X definito da:
(i1)   un procedimento per costruire gli elementi di X e
(i2)   una relazione di equivalenza su X (detta EGUAGLIANZA) definita costruttivamente.
   Quest'ultima può essere rappresentata come un'operazione costruttiva t applicabile a coppie di oggetti tale che , se a, b e c sono elementi di X:
- t(<a,a>)=0
- t(<a,b>)=0 implica t(<b,a>)=0
- t(<a,b>)=0=t(<b,c>) implica t(<a,c>)=0
   Indicheremo tale relazione di equivalenza con =/X/, cioè a=/X/b sta per t(<a,b>)=0.
   Alcuni chiamano PREINSIEME un oggetto X definito solo da (i1).
    Ad esempio dati S e T insiemi, l'insieme SxT è definito così:
gli elementi di SxT sono gli oggetti generati dall'operazione di coppia applicata a sequenze in cui il primo oggetto è un elemento di S e il secondo è un elemento di T; =/SxT/ è data da:
<a,b> =/SxT/ <c,d> sse a=/S/c e b=/T/d.
    Se definiamo Z come {0,1}xN e definiamo l'eguaglianza su Z nel seguente modo:
<a,m>=/Z/<b,n> sse m=/N/n=/N/0 oppure (m=/N/n e a=/N/b)
allora abbiamo che Z e {0,1}xN coincidono come preinsiemi ma non come insiemi.
    Non vale l'ESTENSIONALITA': due insiemi possono avere gli stessi elementi ma non è detto che i due procedimenti che ne definiscono gli elementi siano eguali e quindi (vedi def. di insieme) che lo siano i due insiemi.
    F è una FUNZIONE dall'insieme S all'insieme T (f:S  T) se f è una operazione e:
(f1)   se x è un elemento di S allora si può verificare costruttivamente che f(x) è un elemento di T,
(f2)   se x=/S/y allora f(x)=/T/f(y).
    Non è detto che un insieme abbia una funzione caratteristica:
sia S l'insieme costruito verificando per n=1,2,3,... la proprietà P(n) considerata in 1.3 e prendendo man mano come eventuale nuovo elemento di S 1 se P(n) è falsa e 2 se P(n) è vera; S è un sottoinsieme di N definito costruttivamente, ma non è possibile definire costruttivamente una f:N  {0,1} t.c. sia provabile (costruttivamente) che xN (xS <=> f(x)=0).
   Quindi il concetto di insieme non può essere derivato da quello di funzione.
   A sua volta il concetto di funzione non può essere derivato da quello di insieme, cioè non è possibile considerare una f:S  T come una relazione RSxT.
Non è accettabile infatti la proprietà:   (%)    xS !y <x,y>R => f xS <x,f(x)>R
   Vediamo perché.
   L'ipotesi significa che esiste un procedimento h che a ogni x e a ogni prova p di xS associa un y, una prova q che <x,y>R e una prova r che che se <x,z>R allora z=y. Quindi y dipende sia da x che da p, non solo da x. Si può perciò concludere in genere solo che:
fxp ((p è una prova di xS) => <x,f(x,p)>R)
   In altre parole, per determinare l'immagine di x occorre conoscere p.

   Nella concezione "platonista", invece, vale l'estensionalità (due insiemi sono distinti solo in base ai loro elementi, al di là di come siano stati definiti: per un platonista un insieme esiste indipendentemente da come noi lo "descriviamo") e funzioni e insiemi sono interscambiabili (le prime sono riducibili ai secondi considerandole come insiemi di coppie ordinate, i secondi sono riconducibili alle prime mediante le funzioni caratteristiche).

2.4    L'ASSIOMA DI SCELTA, che possiamo esprimere nella forma:
xS y A(x,y) =>    f xS A(x,f(x))
per considerazioni analoghe a quelle svolte in 2.3 per (%), non è accettato in generale nella concezione costruttivista.
    Val la pena di ricordare che le difficoltà nei tentativi di costruire un buon ordinamento dei numeri reali (era il "1° problema di Hilbert") e la successiva enunciazione e i successivi impieghi dell'assioma di scelta in un certo senso segnano la nascita della matematica non costruttiva e sono all'origine delle prime consistenti divaricazioni all'interno dei matematici. E' soprattutto in questo contesto (e non tanto in occasione della scoperta dei "paradossi", fatto che rimase abbastanza marginale rispetto agli interessi e ai problemi della comunità matematica dell'epoca) che si sviluppò la consapevolezza che i nuovi metodi insiemistici introducevano un "salto" rispetto all'usuale pratica matematica e richiedevano nuove e più profonde riflessioni sulla natura degli oggetti e dei metodi della matematica.

2.5    Un INSIEME T viene detto FINITO se è possibile metterlo in corrispondenza biunivoca con un segmento iniziale di N+, cioè se esiste n e esistono f:{1,...,n}  T e g:T  {1,...,n} tali che g(f(i))=i e f(g(t))=t; in tal caso si dice che ha n elementi. Viene detto NUMERABILMENTE INFINITO se è possibile metterlo in corrispondenza biunivoca con N+. Viene detto NUMERABILE se esiste f: N T surgettiva.
   La condizione con cui abbiamo definito la finitezza non equivale alla finitezza-secondo-Dedekind, cioè alla non esistenza di alcun sottoinsieme proprio di T che sia in corrispondenza biunivoca con T. Infatti la dimostrazione che questa seconda condizione implica la prima richiede l'assioma di scelta e quindi, per quanto detto in 2.4, non è costruttivamente accettabile.

3. Formalizzazioni della matematica costruttiva

   Non entriamo nei dettagli delle diverse concezioni della matematica costruttiva, che differiscono per aspetti quali:
- accettare come funzioni da N in N solo le funzioni ricorsive o accettare metodi meno restrittivi o non ritenere che il concetto di algoritmo sia formalizzabile
- ammettere o no principi come: ¬x=0=>x<0 v 0<x
- ...
   Limitiamoci
-   agli assiomi e regole del calcolo proposizionale intuizionista, che possono essere date ad es. così:
(1.1)   da A e A=>B deriva B (1.2)   da A=>B e B=>C deriva A=>C
(1.3)   AvA=>A e A=>A&A (1.4)   A=>AvB e A&B=>A
(1.5)   AvB=>BvA e A&B=>B&A (1.6)   da A=>B deriva CvA=>CvB
(1.7)   da A&B=>C deriva A=>(B=>C) (1.8)   da A=>(B=>C) deriva A&B=>C
(1.9)   =>A

è il simbolo che rappresenta una formula indimostrabile (introdotta l'"aritmetica" - successore, ... - se ne potrebbe fare a meno mettendo 0=S(0) al suo posto); ¬A può essere definita come A=>. La logica proposizionale classica può essere ottenuta aggiungendo l'assioma Av(A=>).
-   e (a una parte) di quelli per l'uso delle variabili:
(2.1)   da B=>A(x) deriva B=>xA(x) se x non è libera in B
(2.2)   da A(x)=>B deriva xA(x)=>B se x non è libera in B


16. COLLEGAMENTI CON ALTRE AREE MATEMATICHE

1.  Il calcolo delle probabilità

   Sia LEN la funzione che a una stringa associa la sua lunghezza.
   Data una stringa di bit w, la complessità I(w) di w è il minimo n tale che:
esistono un programma P (di Turing-Post) e una stringa v per cui LEN([P]+v)=n e P(v)  w.

   I permette di distinguere le stringhe di una data lunghezza in livelli di casualità.

Se sei interessato ad approfondimenti dei collegamenti con il calcolo delle probabilità (e la teoria dei codici) clicca QUI (vedi anche l'"indice a piena pagina") [il concetto di "complessità è ivi definito in modo un po' diverso, ed è quindi un po' diversa anche la dimostrazione del teorema che segue].

Esercizio.  Dimostrare che la complessità della stringa 111…1 costituita da 1024 (milleventiquattro) "1" è minore di 200 [traccia: usare il programma "duplicatore" considerato in sezioni precedenti]. [soluz.]

2° TEOREMA DI INCOMPLETEZZA DI CHAITIN-GÖDEL
   Supponiamo di disporre di un sistema formale S per dimostrare formule del tipo I(w)>n (supponiamo, ovviamente, che il sistema sia "corretto" - cioè tale che se S |    I(w)>n allora affettivamente accada che I(w)>n). Allora esiste un numero naturale k tale che non è possibile dimostrare in S alcuna formula del tipo I(w)>n con n>k.
[quindi in S è possibile determinare la complessità solo di stringhe non troppo lunghe e "casuali"]

Dim   Idea: argomentazione con "autoriferimento".
   In accordo con le richieste di "calcolabilità" dei sistemi formali (avere procedimenti meccanici per stabilire se una formula è ben formata o no, per stabilire se una formula è un assioma, ... per realizzare le inferenze), se pi è l'i-esima prova rispetto a un dato ordinamento delle prove, possiamo ritenere realizzabile un programma P che, data in input la codifica 'h' di un numero naturale h, implementi il seguente algoritmo:
(1)   i=1
(2)   se pi dimostra una formula del tipo I(w)>n con n>2h fermati con output w, altrimenti poni i=i+1 e vai a (2)
   In altre parole, P con input 'h' trova (se esiste) una stringa w che si possa dimostrare essere di complessità maggiore di 2h.
   Se P('h')  w, per definizione di I deve essere: I(w)≤LEN([P]+'h')=LEN([P])+h+1.
   Se prendo h=LEN([P])+1 avrei: I(w)≤2h, contraddicendo il fatto che (per come ho costruito P) I(w)>2h. Quindi, per h=LEN([P])+1, P('h') non converge, cioè non esistono prove in S di formule del tipo I(w)>n con n>2h.
End dim

Il fattore limitativo (2h) dipende da P che a sua volta dipende dalla "dimensione" del sistema formale.

(Poiché i sistemi formali sono finiti, non è possibile dimostrare che una successione infinita di bit è casuale, cioè che i suoi segmenti iniziali di lunghezza n, a partire da un certo n in poi, hanno complessità maggiore di n, cioè non sono descrivibili con meno di n bit)

2.  Il calcolo numerico

Abbiamo visto che non esiste un procedimento generale per stabilire se due algoritmi sono estensionalmente equivalenti, ossia se calcolano la stessa funzione, intesa insiemisticamente come insieme di coppie input-output (vedi). Anche nel caso in cui si riesca a stabilire se due algoritmi sono estensionalmente equivalenti si possono fare ulteriori distinzioni:
– in relazione alla complessità della loro struttura (ad es. del "programma" che li descrive), a cui in qualche modo si è accennato sopra;
– in relazione alla quantità di "spazio" che impiega la loro esecuzione ("porzione di nastro", "numero di registri", … "bit");
– in relazione al tempo di calcolo.
    Tutti questi argomenti rientrano nel cosiddetto studio della complessità computazionale, che ha intersezioni sia con la logica che con l'informatica e il calcolo numerico.
Ci occuperemo brevemente della complessità temporale. Il fatto che una funzione sia computabile non significa che essa sia "praticamente" computabile, nel senso che il tempo di calcolo potrebbe essere eccessivo rispetto alla scala temporale "umana". Facciamo qualche esempio, riferendoci, per semplicità, a un linguaggio stile Basic del tipo di quello considerato nella sezione 6. Supponiamo che il tempo per le operazioni aritmetiche sia costante, indipendente dall'ordine di grandezza degli argomenti (TA per ogni addizione, TS per ogni sottrazione, un tempo TM per ogni moltiplicazione); naturalmente se avessimo considerato le macchine a registri questo non sarebbe stato vero (avremmo avuto un tempo costante per ogni incremento o decremento unitario, una addizione - ottenuta iterando incrementi unitari - avrebbe avuto un tempo crescente linearmente con il secondo argomento, …).
Esaminiamo il calcolo del coefficiente binomiale C(n,k) con CBIN:
  SUB CBIN(n,k,c)
  IF k=0 THEN> c=1 : EXIT SUB    
  IF k=n THEN c=1 : EXIT SUB
  CALL CBIN(n-1,k-1,a)
  CALL CBIN(n-1,k,c)
  c=a+c
  END SUB
            k=0
    C(n,k) / k=1
 n=0      1 / k=2
 n=1     1 1 / k=3
 n=2    1 2 1 / k=4
 n=3   1 3 3 1 /
 n=4  1 4 6 4 1

Nei casi "ottimi", ossia k=n e k=0 (corrispondenti ai lati obliqui del triangolo di Tartaglia-Pascal), il tempo di calcolo è costante. I casi "pessimi" sono quelli corrispondenti alla "bisettrice" del triangolo, gli n pari con k=n/2. In questi casi la procedura CBIN richiama sé stessa 2 volte, e ripete questa cosa fino a che arriva ai casi iniziali (ossia ai lati obliqui):
C(4,2) = C(3,1) + (3,2) = (1) C(3,1) = C(2,0) + C(2,1) = (2) C(2,0) = 1 C(2,1) = C(1,0) + C(1,1) = (3) C(1,0) = 1 C(1,1) = 1 (3) = 1+1 = 2 (2) = 1 + 2 C(3,2) = C(2,1) + C(2,2) = (4) C(2,1) = C(1,0) + C(1,1) = (5) C(1,0) = 1 C(1,1) = 1 (5) = 1+1 = 2 C(2,2) = 1 (4) = 2+1 = 3 (1) = 3+3 = 6
    Sostanzialmente, ad ogni incremento unitario di n il tempo di calcolo raddoppia. Quindi al crescere di n nei casi pessimi il tempo cresce esponenzialmente.
Questo algoritmo non è praticamente utilizzabile per valori di n troppo grandi.
    Consideriamo un altro algoritmo, estensionalmente equivalente al precedente. Esso consiste nel costruire il triangolo di Tartaglia-Pascal fino alla riga n-esima, e poi all'interno di questa pescare l'elemento k-esimo. In questo caso il tempo di calcolo cresce col quadrato di n. Infatti il numero degli elementi che formano il triangolo cresce con l'"area" del triangolo stesso (se vogliamo essere pedestri, possiamo ragionare in termini di serie aritmetica: 1+2+...+(n+1) sono gli elementi del triangolo; la loro somma è (n+2)(n+1)/2, che è un infinito dello stesso ordine di n2). Questo algoritmo è particolarmente comodo se vogliamo calcolare parecchi coefficienti binomiali: costruiamo il triangolo fino all'n massimo che ci interessa e li memorizziamo in una variabile indiciata (array).
    Infine consideriamo l'algoritmo descrivibile così (con k-1 divisioni e moltiplicazioni, 2k-2 decrementi unitari):
        C(n,k) = n/k·(n-1)/(k-1)·…·(n-k+1)/1.
È realizzabile mediante una semplice iterazione. Il suo tempo di calcolo cresce con k. Il caso pessimo è k=n. Temporalmente questo algoritmo è il più efficiente, ha complessità lineare.


17. ALTRI ESERCIZI

1) a)  Qual è il dominio della funzione N  N calcolata dalla TM  {q1 1 1 q1}? [sol.]
b)  Quale funzione N  N calcola la TM  {q1 1 1 q2}? [sol.]
c)  Definire le stesse funzioni mediante TP, CE e funzioni ricorsive (funz. base, composizione, minimizzazione). [sol.]

2) Descrivere col calcolo equazionale e come funzione ricorsiva:
a)  dist(x,y) (ossia |x-y|) [sol.]
b)  min(x,y) [sol.]
c)  max(x,y) [sol.]
d)  min(x,y,z) [sol.]

3) Descrivere col calcolo equazionale e come funzione ricorsiva:
a)  sgn(x) (1 se x>0, 0 altrimenti) [sol.]
b)  f>(x,y) (funz. caratteristica di ">": 1 se x>y, 0 altrimenti) [sol.]

4) Descrivere col calcolo equazionale:
a)  re(x,y) (resto della divisione intera di x per y) [sol.]
b)  qu(x,y) (quoziente intero della divisione di x per y) [sol.]
c)  fR(x,y) (con x R y se x è divisibile per y) [sol.]
d)  D(x) (numero dei divisori di x, def. per x>0) (difficile) [sol.]

5) Descrivere col calcolo equazionale:
P(x) che vale 1 se x è primo e 0 altrimenti, sia nel caso in cui si ammetta 1 come numero primo che nel caso contrario [sol.]

6) Descrivere come funzione ricorsiva:
x parte intera di √(x) [sol.]

[Prossimamente verranno aggiunti gli altri esempi relativi alla complessità computazionale e ai cenni di teoria dei modelli svolti a lezione, come completamento culturale - non sono oggetto di domande d'esame]

indice