Matematica Costruttiva

Sommario:

Matematica Costruttiva
Matematica Costruttiva

Video: Matematica Costruttiva

Video: Matematica Costruttiva
Video: LIMITI NOTEVOLI, limiti matematica, limiti notevoli esercizi, limiti notevoli dimostrazione 2024, Marzo
Anonim

Navigazione di entrata

  • Contenuto dell'iscrizione
  • Bibliografia
  • Strumenti accademici
  • Anteprima PDF di amici
  • Informazioni sull'autore e sulla citazione
  • Torna in cima

Matematica costruttiva

Pubblicato per la prima volta mar 18 novembre 1997; revisione sostanziale mer 30 maggio 2018

La matematica costruttiva si distingue dalla sua controparte tradizionale, la matematica classica, dalla rigorosa interpretazione della frase "esiste" come "possiamo costruire". Per lavorare in modo costruttivo, dobbiamo reinterpretare non solo il quantificatore esistenziale ma tutti i connettivi e quantificatori logici come istruzioni su come costruire una prova dell'affermazione che coinvolge queste espressioni logiche.

In questo articolo introduciamo la moderna matematica costruttiva basata sull'interpretazione BHK dei connettivi e quantificatori logici. Discutiamo quattro principali varietà di matematica costruttiva, con particolare enfasi sulle due varietà associate a Errett Bishop e Per Martin-Löf, che possono essere considerate come sistemi costruttivi minimi. Descriviamo quindi i progressi nella matematica inversa (informale) costruttiva, un programma di ricerca che cerca di identificare principi, come il teorema dei fan di Brouwer, che, aggiunto alle varietà costruttive minime, facilita le prove di importanti teoremi analitici. Dopo una breve discussione sull'algebra costruttiva, sull'economia e sulla finanza, l'entrata termina con due appendici: una su alcuni principi logici che valgono per la matematica classica, intuizionista e ricorsiva e che, aggiunta a Bishop 's matematica costruttiva, facilitare la dimostrazione di alcuni teoremi utili di analisi; e uno che discute degli approcci allo sviluppo costruttivo della topologia generale.

  • 1. Introduzione
  • 2. L'interpretazione costruttiva della logica
  • 3. Varietà di matematica costruttiva

    • 3.1 Matematica intuitiva
    • 3.2 Matematica costruttiva ricorsiva
    • 3.3 Matematica costruttiva del vescovo
    • 3.4 Teoria costruttiva del tipo di Martin-Löf
  • 4. L'assioma della scelta
  • 5. Matematica inversa costruttiva

    5.1 Teoremi dei fan in CRM

  • 6. Topologia costruttiva
  • 7. Economia e finanza matematica costruttiva
  • 8. Osservazioni conclusive
  • Bibliografia

    • Riferimenti
    • Letteratura correlata
  • Strumenti accademici
  • Altre risorse Internet
  • Voci correlate

1. Introduzione

Prima che i matematici affermino qualcosa (diverso da un assioma), dovrebbero averlo dimostrato vero. Cosa intendono allora i matematici quando affermano una disgiunzione (P / vee Q), dove (P) e (Q) sono affermazioni sintatticamente corrette in alcuni linguaggi matematici (formali o informali)? Un'interpretazione naturale, sebbene, come vedremo, non unica, di questa disgiunzione è che non solo (almeno) una delle affermazioni (P, Q) è valida, ma possiamo anche decidere quale delle due contiene. Quindi, proprio come i matematici affermeranno (P) solo quando avranno deciso che (P) valga dimostrandolo, possono affermare (P / vee Q) solo quando entrambi possono produrre una prova di (P) oppure produce uno di (Q).

Con questa interpretazione, tuttavia, incontriamo un grave problema nel caso speciale in cui (Q) è la negazione, (neg P), di (P). Affermare (neg P) significa mostrare che (P) implica una contraddizione (come (0 = 1)). Ma sarà spesso che i matematici non hanno né una prova di (P) né una di (neg P). Per vedere questo, dobbiamo solo riflettere sulla seguente congettura di Goldbach (GC):

Ogni intero pari (gt 2) può essere scritto come una somma di due numeri primi, che non è né provato né smentito nonostante i migliori sforzi di molti dei principali matematici da quando è stato sollevato per la prima volta in una lettera da Goldbach a Eulero nel 1742. Siamo costretti a concludere che, secondo l'interpretazione della naturale decidibilità di P (vee D), solo un ottimista testardo può mantenere una credenza nella legge del mezzo escluso (LEM):

Per ogni istruzione (P), vale (P) o (neg P).

La logica classica aggira il problema allargando l'interpretazione della disgiunzione: interpreta (P / vee Q) come (neg (neg P / wedge / neg Q)), o in altre parole, "è contraddittorio che entrambi (P) e (Q) sono falsi”. A sua volta, questo porta all'interpretazione idealistica dell'esistenza, in cui (esiste xP (x)) significa (neg / forall x / neg P (x)) ("è contraddittorio che (P (x)) essere falso per ogni (x) "). È su queste interpretazioni della disgiunzione e dell'esistenza che i matematici hanno costruito il grande e apparentemente inespugnabile edificio della matematica classica che serve da base per le scienze fisiche, sociali e (sempre più) biologiche. Tuttavia, le interpretazioni più ampie hanno un costo: per esempio, quando passiamo dalla nostra interpretazione iniziale e naturale di (P / vee Q) all'uso illimitato di quello idealistico,(neg (neg P / wedge / neg Q)), la matematica risultante non può generalmente essere interpretata all'interno di modelli computazionali come la teoria delle funzioni ricorsive.

Questo punto è illustrato da un esempio logoro, la proposizione:

Esistono numeri irrazionali (a, b) tali che (a ^ b) è razionale.

Una chiara dimostrazione classica è la seguente. O (sqrt {2} ^ { sqrt {2}}) è razionale, nel qual caso prendiamo (a = b = / sqrt {2}); altrimenti (sqrt {2} ^ { sqrt {2}}) è irrazionale, nel qual caso prendiamo (a = / sqrt {2} ^ { sqrt {2}}) e (b = / sqrt {2}) (vedi Dummett 1977 [2000], 6). Ma allo stato attuale, questa dimostrazione non ci consente di individuare quale delle due scelte della coppia ((a, b)) abbia la proprietà richiesta. Per determinare la scelta corretta di ((a, b)), dovremmo decidere se (sqrt {2} ^ { sqrt {2}}) è razionale o irrazionale, che è precisamente impiegare la nostra interpretazione iniziale di disgiunzione con (P) l'affermazione "(sqrt {2} ^ { sqrt {2}}) è razionale".

Ecco un'altra illustrazione della differenza tra interpretazioni. Considera la seguente semplice dichiarazione sull'insieme (bR) di numeri reali:

(tag {*} forall x / in / bR (x = 0 / vee x / ne 0),)

dove, per ragioni che divulghiamo a breve, (x / ne 0) significa che possiamo trovare un numero razionale (r) con (0 / lt r / lt / abs {x}). Una naturale interpretazione computazionale di (*) è che abbiamo una procedura che, applicata a qualsiasi numero reale (x), ci dice che (x = 0) oppure ci dice che (x / ne 0). (Ad esempio, una tale procedura potrebbe generare 0 if (x = 0) e 1 if (x / ne 0).) Tuttavia, poiché il computer può gestire numeri reali solo mediante approssimazioni razionali limitate, noi avere il problema del underflow, in cui un numero positivo sufficientemente piccolo può essere letto erroneamente come 0 dal computer; quindi non può esistere una procedura decisionale che giustifichi l'affermazione (*). In altre parole, non possiamo aspettarci che (*) rimanga sotto la nostra naturale interpretazione computazionale del quantificatore (forall) e del connettivo (vee).

Esaminiamo questo da un'altra angolazione. Lascia che (G (n)) funga da scorciatoia per l'affermazione "(2n + 2) è una somma di due numeri primi", dove (n) si estende sugli interi positivi e definisce una sequenza binaria infinita (ba = (a_1, a_2, / ldots)) come segue:

[a_n = / begin {casi} 0 & / text {if} G (n) text {vale per tutti} k / le n \\ 1 & / text {if} neg G (n) text {hold per alcuni} k / le n \\ / end {casi})

Non c'è dubbio che (ba) sia una sequenza computazionalmente ben definita, nel senso che abbiamo un algoritmo per il calcolo (a_n) per ciascuno (n): controlla i numeri pari (4, 6,8, / ldots, 2n + 2) per determinare se ciascuno di essi è una somma di due numeri primi; in tal caso, impostare (a_n = 0) e, in caso contrario, impostare (a_n = 1). Ora considera il numero reale la cui (n) th cifra binaria è (a_n):

(begin {align *} x & = (0 / cdot a_1 a_2 / cdots) _ {2} & = 2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots \& = / sum_ {n = 1} ^ { infty} 2 ^ {- n} a_n. / End {* align})

Se (*) vale sotto la nostra interpretazione computazionale, allora possiamo decidere tra le seguenti due alternative:

  • (2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots = 0), il che implica che (a_n = 0) per ogni (n);
  • possiamo trovare un numero intero positivo (N) tale che (2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots / gt 2 ^ {- N}).

In quest'ultimo caso, testando (a_1, / ldots, a_N), possiamo trovare (n / le N) tale che (a_n = 1). Quindi l'interpretazione computazionale di (*) ci consente di decidere se esiste (n) tale che (a_n = 1); in altre parole, ci consente di decidere lo stato della congettura di Goldbach. Un esempio di questo tipo, che mostra che una dimostrazione costruttiva di un risultato classico (P) ci consentirebbe di risolvere la congettura di Goldbach (e, per argomenti simili, molti altri problemi finora aperti, come l'ipotesi di Riemann), è chiamato un esempio di Brouwerian per, o persino un controesempio di Brouwerian, la frase (P) (sebbene non sia un controesempio nel senso normale di quella parola).

L'uso della congettura di Goldbach qui è puramente drammatico. Perché, l'argomento del paragrafo precedente può essere modificato per mostrare che, sotto la nostra interpretazione computazionale, (*) implica il principio limitato dell'onniscienza (LPO):

Per ogni sequenza binaria ((a_1, a_2, / ldots)) o (a_n = 0) per tutti (n) oppure esiste (n) tale che (a_n = 1), che è generalmente considerato un principio essenzialmente non costruttivo per diverse ragioni. Innanzitutto, la sua interpretazione ricorsiva, Esiste un algoritmo ricorsivo che, applicato a qualsiasi sequenza binaria definita ricorsivamente ((a_1, a_2, / ldots)), genera 0 if (a_n = 0) per tutti (n) e genera 1 se (a_n = 1) per alcuni (n), è dimostrabilmente falso nella teoria delle funzioni ricorsive, anche con la logica classica (vedi Bridges & Richman [1987], Capitolo 3); quindi se vogliamo consentire un'interpretazione ricorsiva di tutta la nostra matematica, non possiamo usare LPO. In secondo luogo, esiste una teoria dei modelli (modelli di Kripke) in cui si può dimostrare che LPO non è derivabile in modo costruttivo (Bridges & Richman [1987], Capitolo 7).

2. L'interpretazione costruttiva della logica

Ormai dovrebbe essere chiaro che uno sviluppo computazionale della matematica a sangue pieno non consente le interpretazioni idealistiche della disgiunzione e dell'esistenza da cui dipende la maggior parte della matematica classica. Per lavorare in modo costruttivo, dobbiamo tornare dalle interpretazioni classiche a quelle costruttive naturali:

(vee) (o): per provare (P / vee Q) dobbiamo avere una prova di (P) o avere una prova di (Q).
(wedge) (e): per dimostrare (P / wedge Q) dobbiamo avere sia una prova di (P) che una prova di (Q).
(Rightarrow) (implica): una prova di (P / rightarrow Q) è un algoritmo che converte qualsiasi prova di (P) in una prova di (Q).
(neg) (not): per dimostrare (neg P) dobbiamo dimostrare che (P) implica (0 = 1).
(esiste) (esiste): per dimostrare (esiste xP (x)) dobbiamo costruire un oggetto (x) e dimostrare che (P (x)) vale.
(forall) (per ognuno / tutti): una prova di (forall x / in SP (x)) è un algoritmo che, applicato a qualsiasi oggetto (x) e ai dati che dimostrano che (x / in S), dimostra che (P (x)) detiene.

Queste interpretazioni BHK (il nome riflette la loro origine nel lavoro di Brouwer, Heyting e Kolmogorov) possono essere rese più precise usando la nozione di realizzabilità di Kleene; vedi (Dummett [1977/2000], 222–234; Beeson [1985], capitolo VII).

Che tipo di cose stiamo cercando se prendiamo sul serio lo sviluppo della matematica in modo tale che quando un teorema afferma l'esistenza di un oggetto (x) con una proprietà (P), allora la prova del teorema incarna algoritmi per costruire (x) e per dimostrare, con qualunque calcolo necessario, che (x) abbia la proprietà (P). Ecco alcuni esempi di teoremi, ciascuno seguito da una descrizione informale dei requisiti per la sua dimostrazione costruttiva.

  1. Per ogni numero reale (x), (x = 0) o (x / ne 0). Requisito di prova: un algoritmo che, applicato a un dato numero reale (x), decide se (x = 0) o (x / ne 0). Nota che, per prendere questa decisione, l'algoritmo potrebbe usare non solo i dati che descrivono (x) ma anche i dati che mostrano che (x) è in realtà un numero reale.
  2. Ogni sottoinsieme non vuoto (S) di (bR) che è limitato sopra ha un limite minimo.

    Requisito di prova: un algoritmo che, applicato a un insieme (S) di numeri reali, un membro (s) di (S) e un limite superiore per (S),

    1. calcola un oggetto (b) e mostra che (b) è un numero reale;
    2. mostra che (x / le b) per ciascuno (x / in S); e
    3. dato un numero reale (b '\ lt b), calcola un elemento (x) di (S) tale che (x / gt b').
  3. Se (f) è un mapping continuo a valori reali sull'intervallo chiuso ([0,1]) tale che (f (0) cdot f (1) lt 0), allora esiste (x) tale che (0 / lt x / lt 1) e (f (x) = 0).

    Requisito di prova: un algoritmo che, applicato alla funzione (f), un modulo di continuità per (f) e i valori (f (0)) e (f (1)),

    1. calcola un oggetto (x) e mostra che (x) è un numero reale compreso tra 0 e 1; e
    2. mostra che (f (x) = 0).
  4. Se (f) è una mappatura continua a valori reali sull'intervallo chiuso ([0,1]) tale che (f (0) cdot f (1) lt 0), quindi per ogni (varepsilon / gt 0) esiste (x) tale che (0 / lt x / lt 1) e (abs {f (x)} lt / varepsilon).

    Requisito di prova: un algoritmo che, applicato alla funzione (f), un modulo di continuità per (f), i valori (f (0)) e (f (1)) e un numero positivo (varepsilon),

    1. calcola un oggetto (x) e mostra che (x) è un numero reale compreso tra 0 e 1; e
    2. mostra che (abs {f (x)} lt / varepsilon).

Abbiamo già ragioni per dubitare che (A) abbia una prova costruttiva. Se i requisiti di prova per (B) possono essere soddisfatti, quindi, data qualsiasi affermazione matematica (P), possiamo applicare la nostra prova di (B) per calcolare un'approssimazione razionale (z) al supremum (sigma) del set

[S = {0 } cup {x / in / bR: P / wedge x = 1 })

con errore (lt / bfrac {1} {4}). Possiamo quindi determinare se (z / gt / bfrac {1} {4}), nel qual caso (sigma / gt 0) o (z / lt / bfrac {3} {4}), quando (sigma / lt 1). Nel primo caso, esiste (x / in S) con (x / gt 0), quindi dobbiamo avere (x = 1) e quindi (P). Nel caso (sigma / lt 1), abbiamo (neg P). Quindi (B) implica la legge del mezzo escluso.

Tuttavia, nella teoria costruttiva di Bishop dei numeri reali, basata su sequenze di Cauchy con un tasso di convergenza prestabilito, possiamo dimostrare il seguente principio costruttivo dal limite superiore:

Sia (S) un sottoinsieme non vuoto di (bR) che è limitato sopra. Quindi (S) ha un limite superiore se e solo se si trova nell'ordine superiore, nel senso che per tutti i numeri reali (alpha, / beta) con (alpha / lt / beta), o (beta) è un limite superiore per (S) oppure esiste (x / in S) con (x / gt / alpha) (Bishop & Bridges [1985], p. 37, Proposition (4.3)).

Per inciso, menzioniamo uno sviluppo alternativo della teoria costruttiva di (bR) basata sull'aritmetica degli intervalli; vedi capitolo 2 di Bridges & Vîță [2006].

Ciascuna delle istruzioni (C) e (D), che sono classicamente equivalenti, è una versione del teorema del valore intermedio. In queste affermazioni, un modulo di continuità per (f) è un insieme (Omega) di coppie ordinate ((varepsilon, / delta)) di numeri reali positivi con le seguenti due proprietà:

  • per ogni (varepsilon / gt 0) esiste (delta / gt 0) tale che ((varepsilon, / delta) in / Omega)
  • per ogni ((varepsilon, / delta) in / Omega) e per tutti (x, y / in [0,1]) con (abs {x - y} lt / delta), abbiamo (abs {f (x) - f (y)} lt / varepsilon).

L'istruzione (C) implica un altro principio essenzialmente non costruttivo, il principio limitato minore dell'onniscienza (LLPO):

Per ogni sequenza binaria ((a_1, a_2, / ldots)) con al massimo un termine uguale a 1, (a_n = 0) per tutti i pari (n) oppure (a_n = 0) per tutti i dispari (n).

L'istruzione (D), una forma debole di (C), può essere dimostrata in modo costruttivo, usando un argomento dimezzante l'intervallo di un tipo standard. Il seguente teorema di valore intermedio costruttivo più forte, che è sufficiente per la maggior parte degli scopi pratici, è dimostrato usando un argomento dimezzante l'intervallo approssimativo:

Sia (f) una mappatura continua a valori reali sull'intervallo chiuso ([0,1]) tale che (f (0) cdot f (1) lt 0). Supponiamo anche che (f) sia localmente diverso da zero, nel senso che per ogni (x / in [0,1]) e ciascuno (r / gt 0), esiste (y) tale che (abs {x - y} lt r) e (f (y) ne 0). Quindi esiste (x) tale che (0 / lt x / lt 1) e (f (x) = 0).

La situazione del teorema del valore intermedio è tipica di molti nell'analisi costruttiva, dove troviamo un teorema classico con diverse versioni costruttive, alcune o tutte che possono essere equivalenti nella logica classica.

C'è un principio di onniscienza il cui stato costruttivo è meno chiaro di quello di LPO e LLPO -cioè, il principio di Markov (MP):

Per ogni sequenza binaria ((a_n)), se è contraddittorio che tutti i termini (a_n) equivalgono a 0, allora esiste un termine uguale a 1.

Questo principio equivale a una serie di semplici proposizioni classiche, tra cui le seguenti:

  • Per ogni numero reale (x), se è contraddittorio che (x) è uguale a 0, allora (x / ne 0) (nel senso che abbiamo menzionato in precedenza).
  • Per ogni numero reale (x), se è contraddittorio che (x) è uguale a 0, allora esiste (y / in / bR) tale che (xy = 1).
  • Per ciascuna una mappatura continua (f: [0,1] rightarrow / bR), if (x / ne y), quindi (f (x) ne f (y)).

Il principio di Markov rappresenta una ricerca illimitata: se si ha la prova che tutti i termini (a_n) essendo 0 portano a una contraddizione, quindi, testando i termini (a_1, a_2, a_3, / ldots), si è garantito per incontrare un termine uguale a 1; ma questa garanzia non si estende alla certezza che troverai il termine desiderato prima della fine dell'universo. La maggior parte dei professionisti della matematica costruttiva considera il principio di Markov con almeno sospetto, se non addirittura incredulità. Tali punti di vista sono rafforzati dall'osservazione che esiste un modello Kripke che mostra che MP non è derivabile in modo costruttivo (Bridges & Richman [1987], 137–138).

3. Varietà di matematica costruttiva

Il desiderio di mantenere la possibilità di un'interpretazione computazionale è una motivazione per usare le reinterpretazioni costruttive dei connettivi logici e quantificatori che abbiamo dato sopra; ma non è esattamente la motivazione dei pionieri del costruttivismo in matematica. In questa sezione esaminiamo alcuni dei diversi approcci al costruttivismo in matematica negli ultimi 130 anni.

3.1 Matematica intuitiva

Alla fine del diciannovesimo secolo, alcuni individui - in particolare Kronecker e Poincaré - avevano espresso dubbi o addirittura disapprovavano i metodi idealistici e non costruttivi usati da alcuni dei loro contemporanei; ma è negli scritti polemici di LEJ Brouwer (1881–1966), a partire dalla sua tesi di dottorato ad Amsterdam, Brouwer [1907], e proseguendo nei successivi quarantasette anni, che sono alla base di un approccio preciso e sistematico alla matematica costruttiva furono deposte. Nella filosofia di Brouwer, nota come intuizionismo, la matematica è una libera creazione della mente umana ed esiste un oggetto se e solo se può essere (mentalmente) costruito. Se uno prende quella posizione filosofica, allora è inesorabilmente attratto dalla precedente interpretazione costruttiva dei connettivi logici e dei quantificatori:come può una prova dell'impossibilità della non esistenza di un determinato oggetto (x) descrivere una costruzione mentale di (x)?

Brouwer non era l'espositore più chiaro delle sue idee, come dimostra la seguente citazione:

La matematica sorge quando il soggetto della dualità, che risulta dal passare del tempo, viene sottratto da tutte le occorrenze speciali. La forma vuota rimanente [la relazione di (n) con (n + 1)] del contenuto comune di tutte queste due divinità diventa l'intuizione originale della matematica e ripetuta senza limiti crea nuove materie matematiche. (citato in Kline [1972], 1199–2000)

Una versione moderna del punto di vista di Brouwer fu data da Errett Bishop (Bishop [1967], p. 2):

La preoccupazione principale della matematica è il numero, e questo significa gli interi positivi. Pensiamo al numero come Kant percepiva nello spazio. Gli interi positivi e la loro aritmetica sono presupposti dalla natura stessa della nostra intelligenza e, siamo tentati di credere, dalla natura stessa dell'intelligenza in generale. Lo sviluppo degli interi positivi dal concetto primitivo dell'unità, il concetto di annettere un'unità e il processo di induzione matematica porta la completa convinzione. Nelle parole di Kronecker, gli interi positivi sono stati creati da Dio.

Per quanto oscuri possano essere gli scritti di Brouwer, una cosa era sempre chiara: per lui, la matematica aveva la precedenza sulla logica. Si potrebbe dire, come fece Hermann Weyl nel passaggio seguente, che Brouwer considerava la matematica classica imperfetta proprio nel suo uso della logica classica senza riferimento alla matematica sottostante:

Secondo l'opinione di Brouwer e la lettura della storia, la logica classica è stata sottratta alla matematica degli insiemi finiti e dei loro sottoinsiemi. … Dimenticando questa origine limitata, uno in seguito ha scambiato quella logica per qualcosa sopra e prima di tutta la matematica, e infine l'ha applicata, senza giustificazione, alla matematica di insiemi infiniti. Questa è la caduta e il peccato originale della teoria degli insiemi, per i quali è giustamente punito dalle antinomie. Non è che tali contraddizioni si sono rivelate sorprendenti, ma si sono presentate in una fase così avanzata del gioco. (Weyl [1946])

In particolare, questo uso improprio della logica ha portato a prove di esistenza non costruttive che, nelle parole di Weyl, "informano il mondo che esiste un tesoro senza rivelare la sua posizione".

Per descrivere la logica usata dal matematico intuizionista, è stato prima necessario analizzare i processi matematici della mente, da cui è possibile estrarre l'analisi dalla logica. Nel 1930, l'allievo più famoso di Brouwer, Arend Heyting, pubblicò una serie di assiomi formali che caratterizzano così chiaramente la logica usata dall'intuizionista che sono diventati universalmente conosciuti come gli assiomi per la logica intuizionista (Heyting [1930]). Questi assiomi hanno catturato l'interpretazione informale BHK dei connettivi e dei quantificatori che abbiamo dato in precedenza.

La matematica intuitiva differisce da altri tipi di matematica costruttiva nella sua interpretazione del termine "sequenza". Normalmente, una sequenza nella matematica costruttiva è data da una regola che determina, in anticipo, come costruire ciascuno dei suoi termini; si può dire che una tale sequenza è simile alla legge o predeterminata. Brouwer ha generalizzato questa nozione di una sequenza per includere la possibilità di costruire i termini uno a uno, la scelta di ciascun termine è fatta liberamente o soggetta solo a determinate restrizioni stabilite in anticipo. La maggior parte delle manipolazioni delle sequenze non richiede che siano predeterminate e possano essere eseguite su queste sequenze di libera scelta più generali.

Quindi, per l'intuizionista, un numero reale (bx = (x_1, x_2, / ldots)) - essenzialmente, una sequenza di numeri razionali di Cauchy non deve essere data da una regola: i suoi termini (x_1, x_2, / ldots), sono semplicemente numeri razionali, costruiti successivamente, soggetti solo a una sorta di restrizione di Cauchy come quella seguente usata da Bishop [1967]:

(forall m / forall n / left (abs {x_m - x_n} le / left (frac {1} {m} + / frac {1} {n} right) right])

Una volta che le sequenze di scelta libera sono ammesse in matematica, quindi, forse con sorpresa iniziale, sono determinati forti principi di scelta. Sia (P) un sottoinsieme di (bN ^ { bN} times / bN) (dove (bN) indica l'insieme dei numeri naturali e, per gli insiemi (A) e (B, B ^ A) indica l'insieme di mappature da (A) a (B)) e supponiamo che per ogni (ba / in / bN ^ { bN}) esista (n / in / bN) tale che ((ba, n) in P). Da un punto di vista costruttivo, ciò significa che abbiamo una procedura, applicabile alle sequenze, che calcola (n) per ogni dato (ba). Secondo Brouwer, la costruzione di un elemento di (bN ^ { bN}) è per sempre incompleta: una sequenza generica (ba) è puramente estensiva, nel senso che in un dato momento non possiamo sapere nulla circa (ba) diverso da un insieme finito dei suoi termini. Ne consegue che la nostra procedura deve essere in grado di calcolare, da una sequenza iniziale finita ((a_0, / ldots, a_N)) dei termini di (ba), un numero naturale (n) tale che (P (b bis, n)). Se (bb / in / bN ^ { bN}) è una sequenza tale che (b_ {k} = a_ {k}) per (0 / le k / le N), allora la nostra procedura deve restituire lo stesso (n) per (bb) come per (ba). Ciò significa che (n) è una funzione continua di (ba) rispetto alla topologia su (bN ^ { bN}) fornita dalla metricaCiò significa che (n) è una funzione continua di (ba) rispetto alla topologia su (bN ^ { bN}) fornita dalla metricaCiò significa che (n) è una funzione continua di (ba) rispetto alla topologia su (bN ^ { bN}) fornita dalla metrica

(varrho: (ba, / bb) rightsquigarrow / inf {2 ^ {- n}: a_k = b_k / text {per} 0 / le k / le n }.)

Siamo quindi condotti al seguente principio di scelta continua, che dividiamo in una parte di continuità e una parte di scelta.

CC1: Qualsiasi funzione da (bN ^ { bN}) a (bN) è continua.

CC2: Se (P / subseteq / bN ^ { bN} times / bN), e per ogni (ba / in / bN ^ { bN}) esiste (n / in / bN) tale che ((ba, n) in P), quindi esiste una funzione (f: / bN ^ { bN} rightarrow / bN) tale che ((ba, f (ba)) in P) per tutti (ba / in / bN ^ { bN}).

Se (P) e (f) sono come in CC2, allora diciamo che (f) è una funzione scelta per (P).

I principi di onniscienza LPO e LLPO sono manifestamente falsi secondo le ipotesi CC1–2; ma MP è coerente con esso. Tra le notevoli conseguenze di CC1–2 ci sono le seguenti.

  • Qualsiasi funzione da (bN ^ { bN}) o (2 ^ { bN}) a uno spazio metrico è puntualmente continua.
  • Ogni mappatura da uno spazio metrico separabile completo non vuoto a uno spazio metrico è puntualmente continuo.
  • Ogni mappa dalla linea reale (bR) a se stessa è puntualmente continua.
  • Sia (X) uno spazio normato completamente separabile, (Y) uno spazio normato e ((u_n)) una sequenza di mappature lineari da (X) a (Y) tale che per ogni vettore di unità (x) di (X), (phi (x) = / sup { Vert u_n (x) rVert: n / in / bN }) esiste. Quindi esiste (c / gt 0) tale che (lVert u_n (x) rVert / le c) per tutti (n / in / bN) e tutti i vettori di unità (x) di (X) (Principio di delimitazione uniforme).

Ognuna di queste affermazioni sembra contraddire teoremi classici noti. Tuttavia, il confronto con la matematica classica non dovrebbe essere fatto in modo superficiale: per capire che qui non c'è vera contraddizione, dobbiamo apprezzare che il significato di termini come "funzione" e persino "numero reale" nella matematica intuizionista è abbastanza diverso da quello nell'ambientazione classica. (In pratica, la matematica intuizionista non può essere paragonata, prontamente e direttamente, alla matematica classica.)

L'introspezione di Brouwer sulla natura delle funzioni e del continuum lo ha portato a un secondo principio, che, a differenza di quello della scelta continua, è classicamente valido. Questo principio richiede un po 'più di background per la sua spiegazione.

Per ogni set (S) indichiamo con (S ^ *) l'insieme di tutte le sequenze finite di elementi di (S), inclusa la sequenza vuota (()). Se (alpha = (a_1, / ldots, a_n)) è in (S ^ *), allora (n) è chiamata lunghezza di (alpha) ed è indicata da (abs { alpha}). Se (m / in / bN) e (alpha) è una sequenza finita o infinita in (S) di lunghezza almeno (m), allora denotiamo con (bar { alpha} (m)) la sequenza finita costituita dai primi termini (m) di (alpha). Nota che (bar { alpha} (0) = ()) e (abs { bar { alpha} (0)}) = 0. Se (alpha / in S ^ *) e (beta = / bar { alpha} (m)) per alcuni (m), diciamo che (alpha) è un'estensione di (beta) e che (beta) è una limitazione di (alpha).

Si dice che un sottoinsieme (sigma) di (S) sia staccabile (da (S)) se

(forall x / in S (x / in / sigma / vee x / not / in / sigma).)

Un sottoinsieme staccabile (sigma) di (bN ^ *) viene chiamato fan se

  • è chiuso sotto restrizione: per ogni (alpha / in / bN ^ *) e ciascuno (n), se (bar { alpha} (n) in S), quindi (bar { alpha} (k) in S) ogni volta che (0 / le k / le n); e
  • per ogni (alpha / in / sigma), il set ({ alpha ^ * n / in S: n / in / bN }) è finito o vuoto, dove (alpha ^ * n) indica la sequenza finita ottenuta avvicinando il numero naturale (n) ai termini di (alpha).

Un percorso in un fan (sigma) è una sequenza (alpha), finita o infinita, tale che (bar { alpha} (n) in / sigma) per ogni applicabile (n). Diciamo che un percorso (alpha) è bloccato da un sottoinsieme (B) se una limitazione di (alpha) è in (B); se nessuna limitazione di (alpha) è in (B), diciamo che (alpha) manca (B). Un sottoinsieme (B) di un fan (sigma) viene chiamato barra per (sigma) se ogni percorso infinito di (sigma) è bloccato da (B); una barra (B) per (sigma) è uniforme se esiste (n / in / bN) in modo tale che ogni percorso di lunghezza (n) sia bloccato da (B).

Finalmente possiamo affermare il prossimo principio di intuizionismo di Brouwer, il teorema dei fan per le barre staccabili (FT (_ D)):

Ogni barra staccabile di un ventilatore è uniforme.

Nella sua classica forma contrapposta, FT (_ D) è noto come Lemma di König: se per ogni (n) esiste un percorso di lunghezza (n) che manca (B), allora esiste un infinito percorso che manca (B) (vedi Dummett 1977 [2000], 49–53). (Naturalmente, la condizione della staccabilità è classicamente superflua.) È semplice costruire un controesempio di Brouwerian al Lemma di König.

Brouwer in realtà ha postulato il teorema del fan senza la limitazione della staccabilità della barra. I tentativi di dimostrare che il teorema del fan più generale si basano costruttivamente su un'analisi di come potremmo sapere che un sottoinsieme è una barra e hanno portato Brouwer a una nozione di induzione della barra; questo è discusso nella sezione 3.6 della voce sull'intuizionismo nella filosofia della matematica; un altro buon riferimento per l'induzione da barra è van Atten (2004). Ritorneremo ai teoremi dei fan nella Sezione 4.

Tra le molte applicazioni dei principi di Brouwer, la più famosa è il suo teorema di continuità uniforme (che segue dalle conseguenze della continuità puntuale di CC1-2 insieme una forma di teorema di fan più generale di FT (_ D)):

Ogni mappatura da uno spazio metrico compatto (cioè completo, totalmente limitato) in uno spazio metrico è uniformemente continuo.

Il lettore viene nuovamente ammonito di interpretarlo attentamente all'interno del quadro intuitivo di Brouwer e di non saltare alla conclusione errata che l'intuizionismo contraddice la matematica classica. È più sensato considerare i due tipi di matematica incomparabili. Per ulteriori discussioni, vedere la voce sulla logica intuizionistica.

Sfortunatamente - e forse inevitabilmente, di fronte all'opposizione di matematici di tale statura come Hilbert - la scuola intuizionista di matematica e filosofia di Brouwer divenne sempre più coinvolta in ciò che, almeno per i matematici classici, sembrava essere una speculazione quasi mistica sulla natura del pensiero costruttivo, a scapito della pratica della matematica costruttiva stessa. Questa sfortunata polarizzazione tra Brouwerians e Hilbertians culminò nella famigerata Grundlagenstreit degli anni 1920, i cui dettagli si possono trovare nelle biografie Brouwer di van Dalen [1999, 2005] e van Stigt [1990].

3.2 Matematica costruttiva ricorsiva

Alla fine degli anni '40, il matematico russo AA Markov iniziò lo sviluppo di una forma alternativa di matematica costruttiva (RUSS), che è, essenzialmente, teoria delle funzioni ricorsive con logica intuizionista (Markov [1954], Kushner [1985]). In questa varietà gli oggetti sono definiti mediante numerazioni di Gödel e le procedure sono tutte ricorsive; la principale distinzione tra RUSSIA e la classica analisi ricorsiva sviluppata dopo il lavoro di Turing, Church e altri nel 1936 ha chiarito la natura dei processi calcolabili è che la logica utilizzata in RUSSIA è intuizionistica.

Un ostacolo affrontato dal matematico che tenta di fare i conti con la RUSS è che, essendo espresso nel linguaggio della teoria della ricorsione, non è facilmente leggibile; anzi, aprendo una pagina delle eccellenti lezioni di Kushner [1985], si potrebbe essere perdonati per essersi chiesti se si tratti di analisi o logica. (Questa osservazione dovrebbe essere temperata con riferimento ai due libri relativamente leggibili sull'analisi ricorsiva classica di Aberth [1980, 2001].) Fortunatamente, si può arrivare al cuore della RUSSIA con un approccio assiomatico dovuto a Richman [1983] (vedi anche Chapter 3 of Bridges & Richman [1987]).

Innanzitutto, definiamo un set (S) numerabile se esiste una mappatura da un sottoinsieme staccabile di (bN) su (S). Con la logica intuizionista non possiamo dimostrare che ogni sottoinsieme di (bN) sia staccabile (il lettore è invitato a fornire un esempio di Brouwerian per dimostrarlo). Sottoinsiemi numerabili di (bN) nell'approccio assiomatico di Richman sono le controparti di insiemi ricorsivamente enumerabili nel normale sviluppo della RUSSIA.

Per funzione parziale su (bN) intendiamo una mappatura il cui dominio è un sottoinsieme di (bN); se il dominio è (bN) stesso, allora chiamiamo la funzione una funzione parziale totale su (bN). L'approccio di Richman alla RUSSIA si basa sulla logica intuizionistica e su un singolo assioma di funzioni parziali calcolabili (CPF):

Esiste un'enumerazione (phi_0, / phi_1, / ldots) dell'insieme di tutte le funzioni parziali da (bN) a (bN) con domini numerabili.

È straordinario ciò che può essere dedotto in modo pulito e rapido usando questo principio. Ad esempio, possiamo dimostrare il seguente risultato, che mostra quasi immediatamente che LLPO, e quindi LPO, sono falsi nell'impostazione ricorsiva.

Esiste una funzione parziale totale (f: / bN / times / bN / rightarrow {0,1 }) tale che

  • per ogni (m) esiste al massimo uno (n) tale che (f (m, n) = 1); e
  • per ogni funzione parziale totale (f: / bN / rightarrow {0,1 }), esistono (m, k) in (bN) tali che (f (m, 2k + f (m)) = 1).

Di maggiore interesse, tuttavia, sono risultati come i seguenti all'interno della RUSS.

  • Teorema di Specker (Specker [1949]): esiste una sequenza strettamente crescente ((r_1, r_2, / ldots)) di numeri razionali nell'intervallo chiuso ([0,1]) tale che per ciascuno (x / in / bR) esistono (N / in / bN) e (delta / gt 0) tali che (abs {x - r_n} ge / delta) per tutti (n / ge N).
  • Per ogni (varepsilon / gt 0), esiste una sequenza ((I_1, I_2, / ldots)), con intervalli aperti limitati in (bR) tale che (inizio {allinea} tag {i} bR & / subseteq / bigcup_ {n = 1} ^ { infty} I_n, / text {and} / \ tag {ii} sum_ {n = 1} ^ N / abs {I_n} & / lt / varepsilon / text {per ogni} N. / end {align}) (Una tale sequenza di intervalli è chiamata (varepsilon) - singolare copertina di (bR).)
  • Esiste una funzione continua puntuale (f: [0,1] rightarrow / bR) che non è uniformemente continua.
  • Esiste una funzione uniformemente continua valutata positivamente (f: [0,1] rightarrow / bR) il cui infimo è 0.

Da un punto di vista classico, questi risultati si adattano quando si comprende che parole come "funzione" e "numero reale" devono essere interpretate rispettivamente come "funzione ricorsiva" e "numero reale ricorsivo". Si noti che il secondo dei quattro teoremi ricorsivi sopra è un forte controesempio ricorsivo alla proprietà di compattezza a copertura aperta della linea reale (ricorsiva); e il quarto è un controesempio ricorsivo al teorema classico secondo cui ogni mappatura uniformemente continua di un insieme compatto in (bR) raggiunge il suo infimo.

3.3 Matematica costruttiva del vescovo

I progressi in tutte le varietà di matematica costruttiva sono stati relativamente lenti per il prossimo decennio e mezzo. Ciò che era necessario per elevare il profilo del costruttivismo in matematica era un matematico classico di alto livello per dimostrare che era possibile uno sviluppo costruttivo approfondito di analisi approfondita senza un impegno nei principi non classici di Brouwer o nel meccanismo della teoria delle funzioni ricorsive. Questa esigenza fu soddisfatta nel 1967, con l'apparizione della monografia di Errett Bishop Foundations of Constructive Analysis [1967], il prodotto di una sorprendente coppia di anni in cui, lavorando nello stile informale ma rigoroso usato dai normali analisti, Bishop fornì uno sviluppo costruttivo di gran parte dell'analisi del ventesimo secolo, compreso il teorema di Stone-Weierstrass, l'Hahn-Banach e i teoremi di separazione,il teorema spettrale per operatori autoaggiunti su uno spazio di Hilbert, i teoremi di convergenza di Lebesgue per integrali astratti, la misura di Haar e la trasformata astratta di Fourier, i teoremi ergodici e gli elementi della teoria dell'algebra di Banach. (Vedi anche Bishop & Bridges [1985].) Così, ad un tratto, diede la menzogna all'opinione comune espressa con tanta forza da Hilbert:

Prendere il principio del mezzo escluso dal matematico sarebbe lo stesso, diciamo, che proibire al telescopio all'astronomo o al pugile l'uso dei suoi pugni. (Hilbert [1928])

Non solo la matematica di Bishop BISH ha il vantaggio della leggibilità: se apri il libro di Bishop su qualsiasi pagina, ciò che vedi è chiaramente riconoscibile come analisi, anche se, di volta in volta, le sue mosse nel corso di una prova possono sembrare strane a uno istruito sull'uso della legge del mezzo escluso - ma, a differenza della matematica intuizionista o ricorsiva, ammette molte interpretazioni diverse. La matematica intuitiva, la matematica costruttiva ricorsiva e persino la matematica classica forniscono tutti modelli di BISH. In effetti, i risultati e le prove in BISH possono essere interpretati, con al massimo modifiche minori, in qualsiasi modello ragionevole di matematica calcolabile, come, ad esempio, la teoria dell'efficacia di tipo due di Weihrauch (Weihrauch [2000]; Bauer [2005]).

Come si ottiene questa interpretabilità multipla? Almeno in parte dal rifiuto di Bishop di fissare la sua nozione primitiva di "algoritmo" o, nelle sue parole, "routine finita". Questo rifiuto ha portato alla critica che il suo approccio manca della precisione che un logico si aspetterebbe normalmente da un sistema di base. Tuttavia, questa critica può essere superata osservando più da vicino cosa fanno realmente i praticanti di BISH quando dimostrano i teoremi: in pratica, stanno facendo matematica con logica intuizionista. L'esperienza dimostra che la restrizione alla logica intuizionista costringe sempre i matematici a lavorare in un modo che, almeno informalmente, può essere descritto come algoritmico; così la matematica algoritmica sembra essere equivalente alla matematica che usa solo la logica intuizionistica. Se le cose stanno così,allora possiamo praticare la matematica costruttiva usando la logica intuizionistica su qualsiasi oggetto matematico ragionevolmente definito, non solo una classe di "oggetti costruttivi".

Questo punto di vista, più o meno, sembra essere stato presentato per la prima volta da Richman [1990, 1996]. Prendendo la logica come caratteristica principale della matematica costruttiva, non riflette il primato della matematica sulla logica che faceva parte della convinzione di Brouwer, Heyting, Markov, Bishop e altri pionieri del costruttivismo. D'altra parte, cattura l'essenza della matematica costruttiva in pratica.

Quindi si potrebbe distinguere tra il costruttivismo ontologico di Brouwer e altri che sono portati a matematica costruttiva attraverso la convinzione che gli oggetti matematici sono creazioni mentali, e il costruttivismo epistemologico di Richman e quelli che vedono la matematica costruttiva caratterizzata dalla sua metodologia, basata sull'uso della logica intuizionista. Naturalmente, il primo approccio al costruttivismo porta inevitabilmente al secondo; e quest'ultimo non è certamente in contrasto con un'ontologia brouweriana.

Per fare matematica effettiva abbiamo bisogno di qualcosa di più della semplice logica intuitiva. Per Bishop, i mattoni della matematica erano numeri interi positivi (vedi la citazione di Bishop [1967] nella sezione 3.1 sopra). Tra i primi sistemi formali di BISH c'erano le basi assiomatiche di Myhill [1975] basate su nozioni primitive di numero, set e funzione; Il sistema di matematica esplicita di Feferman [1975]; e la teoria degli insiemi ZF intuitiva di Friedman [1977]. Le due basi formali preferite di BISH in questa fase sono la teoria degli insiemi CZF di Aczel e Rathjen [2000] e la teoria del tipo intuizionista di Martin-Löf [1975, 1984].

3.4 Teoria costruttiva del tipo di Martin-Löf

Prima di terminare il nostro tour di varietà della moderna matematica costruttiva, visitiamo una quarta varietà, basata sulla teoria del tipo intuitivo di Per Martin-Löf (ML). Martin-Löf pubblicò il suo Notes on Constructive Mathematics [1968], basato su lezioni tenute in Europa nel 1966-1968; quindi il suo coinvolgimento con il costruttivismo in matematica risale almeno al periodo di scrittura di Bishop of Foundations of Constructive Analysis. Il libro di Martin-Löf è nello spirito della RUSS, piuttosto che BISH; infatti, il suo autore non ebbe accesso al libro di Bishop fino a quando il suo manoscritto non fu terminato. Martin-Löf in seguito rivolse la sua attenzione alla sua teoria dei tipi come base per la matematica costruttiva in stile vescovile.

Ecco, con le sue stesse parole, una spiegazione informale delle idee alla base di ML:

Penseremo a oggetti o costruzioni matematici. Ogni oggetto matematico è di un certo tipo o tipo [… e] è sempre dato insieme al suo tipo. … Un tipo viene definito descrivendo cosa dobbiamo fare per costruire un oggetto di quel tipo. … In altre parole, un tipo è ben definito se comprendiamo … cosa significa essere un oggetto di quel tipo. Pertanto, ad esempio (bN / rightarrow / bN) [funzioni da (bN) a (bN)] è un tipo, non perché conosciamo particolari funzioni teoriche numeriche come quelle primitive ricorsive, ma perché pensiamo di comprendere il concetto di funzione teorica dei numeri in generale. (Martin-Löf [975])

In particolare, in questo sistema ogni proposta può essere rappresentata come un tipo: vale a dire, il tipo di prove della proposizione. Al contrario, ogni tipo determina una proposizione: vale a dire, la proposizione che il tipo in questione è abitato. Quindi, quando pensiamo a un certo tipo (T) come una proposizione, interpretiamo la formula

[x / in T)

come "(x) è una prova della proposizione (T)".

Martin-Löf continua a costruire nuovi tipi, come i prodotti cartesiani e le unioni disgiunte, dai vecchi. Ad esempio, il prodotto cartesiano

[(Pi x / in A) B (x))

è il tipo di funzioni che accettano un oggetto arbitrario (x) di tipo (A) in un oggetto di tipo (B (x)). Nell'interpretazione delle proposizioni come prove, dove (B (x)) rappresenta una proposizione, il suddetto prodotto cartesiano corrisponde alla proposizione universale

[(forall x / in A) B (x).)

Martin-Löf distingue attentamente tra prove e derivazioni: un oggetto prova è una testimonianza del fatto che alcune proposizioni sono state dimostrate; mentre una derivazione è la registrazione della costruzione di un oggetto di prova. Inoltre, esercita due forme di base (una non osa dire "tipi" qui) di giudizio. Il primo è una relazione tra oggetti di prova e proposizioni, il secondo una proprietà di alcune proposizioni. Nel primo caso, il giudizio è uno che un oggetto di prova (a) è testimone di una proposizione (A), oppure uno che sono due oggetti di prova (a) e (b) uguale ed entrambi testimoniano che (A) è stato dimostrato. Il primo caso della seconda forma di giudizio afferma che una proposizione (A) è ben formata, e la seconda registra che due proposizioni (A) e (B) sono uguali.

Esiste un insieme attento e altamente dettagliato di regole per la formalizzazione di ML. Non entreremo in quelli qui, ma rimandiamo il lettore ad altre fonti come Sambin & Smith [1998].

Quando si fa effettivamente matematica costruttiva nella teoria dei tipi, è spesso necessario equipaggiare insiemi (tipi) completamente presentati con una relazione di equivalenza, la combinazione essendo nota come un setoide. Le mappature sono quindi funzioni che rispettano tali relazioni di equivalenza. Ciò è in stretto accordo con il modo in cui Bishop ha presentato la sua teoria informale degli insiemi. I tipi dipendenti di Martin-Löf sono utili per costruire sottoinsiemi. Ad esempio, i numeri reali possono essere costruiti usando il tipo (Sigma) (vedi Martin-Löf [1984]):

[(Sigma x / in / bN _ + / rightarrow / bQ) (Pi m / in / bN _ +) (Pi n / in / bN _ +) left (abs {x_ {m} - x_ {n }} le / left (frac {1} {m} + / frac {1} {n} right) right],)

Un elemento di questo tipo (B) è quindi una coppia costituita da una sequenza convergente (bx) di razionali e una prova (p) che è convergente. Una relazione di equivalenza adeguata ({ sim}) su (R) viene definita prendendo ((x, p) sim (y, q)) per significare

(forall m / in / bN_ + / left (abs {x_ {m} - y_ {m}} le / frac {2} {m} right).)

Il setoid risultante di numeri reali è (bR = (R, { sim})). Possiamo facilmente dimostrarlo

(forall x / in / bR \, / esiste n / in Z (n / lt x / lt n + 2))

e quindi, usando l'assioma teorico-tipo di scelta (vedi Sezione 4 sotto), trova una funzione (f: / bR / rightarrow / bZ) tale che (f (x) lt x / lt f (x) 2). Tuttavia, non vi è motivo di ritenere che la funzione (f) rispetti le relazioni di equivalenza, ovvero che (f (x) = f (y)) valga se (x / sim y).

Ogni dimostrazione costruttiva incarna un algoritmo che, in linea di principio, può essere estratto e rifuso come programma per computer; inoltre, la dimostrazione costruttiva è essa stessa una verifica della correttezza dell'algoritmo, ovvero della sua specifica. Un grande vantaggio dell'approccio formale di Martin-Löf alla matematica costruttiva è che facilita notevolmente l'estrazione di programmi dalle prove. Ciò ha portato a un serio lavoro sull'implementazione della matematica costruttiva in varie località (vedi Martin-Löf [1980], Constable [1986], Hayashi & Nakano [1988], Schwichtenberg [2009]). Alcune recenti implementazioni della teoria dei tipi per l'estrazione delle prove sono Coq e Agda (vedere i collegamenti in Altre risorse Internet).

4. L'assioma della scelta

L'intero assioma della scelta può essere dichiarato come segue:

Se (A, B) sono insiemi abitati e (S) un sottoinsieme di (A / times B) tale che

(forall x / in A \, / esiste y / in B ((x, y) in S),)

allora esiste una funzione scelta (f: A / rightarrow B) tale che

(forall x / in A ((x, f (x)) in S).)

Ora, se questo deve essere tenuto sotto un'interpretazione costruttiva, quindi per un dato (x / in A), il valore (f (x)) della funzione scelta dipenderà non solo da (x) ma anche sui dati che dimostrano che (x) appartiene a (A.) In generale, non possiamo aspettarci di produrre una funzione di scelta di questo tipo. Tuttavia, l'interpretazione BHK delle ipotesi nell'assioma è che esiste un algoritmo (mathcal {A}) che, applicato a qualsiasi dato (x / in A), produce un elemento (y / in B) tale che ((x, y) in S). Se (A) è un set completamente presentato, uno per il quale non è richiesto alcun lavoro oltre la costruzione di ciascun elemento nel set per dimostrare che l'elemento appartiene effettivamente a (A), allora potremmo ragionevolmente aspettarci che l'algoritmo (mathcal {A}) per essere una funzione scelta. Nella teoria dei tipi di Martin-Löf, ogni set è completamente presentato e,in linea con l'interpretazione di BHK, l'assioma della scelta è derivabile.

D'altra parte, nella matematica in stile vescovile, gli insiemi completamente presentati ––– o, nella sua terminologia, gli insiemi di base ––– sono rari, un esempio è (bN); quindi potremmo aspettarci che l'assioma della scelta non sia derivabile. Infatti, come dimostrato da Diaconescu [1975] e Goodman & Myhill [1978], e prefigurato dallo stesso Bishop nel Problema 2 a pagina 58 di Bishop 1967, l'assioma della scelta implica la legge del mezzo escluso. Chiaramente, il teorema di Diaconescu-Goodman-Myhill si applica solo supponendo che non tutti i set siano completamente presentati.

I matematici costruttivi che non lavorano in ML in genere rifiutano l'intero assioma della scelta ma abbracciano l'assioma della scelta numerabile, in cui il dominio della scelta è (bN) e la scelta dipendente. Ma alcuni preferiscono lavorare senza una scelta nemmeno numerabile, in quanto parlare di un'infinità di scelte senza dare una regola presenta una difficoltà altrettanto grande se l'infinito sia o meno numerabile. È interessante notare che Lebesgue ha fatto proprio questo punto in una lettera a Borel (vedi Moore [2013], pagina 316):

Concordo pienamente con Hadamard quando afferma che parlare di un'infinità di scelte senza dare una regola presenta una difficoltà altrettanto grande se l'infinito sia o meno numerabile.

L'effetto di abbandonare anche le scelte numerabili è l'esclusione di molti teoremi che, così come sono, sono dimostrati usando argomenti sequenziali basati sulla scelta. Ma coloro che sostengono di evitare la scelta sostengono che evitare la scelta ti costringe a formulare le cose meglio.

Un caso particolare di interesse è il teorema fondamentale dell'algebra: ogni polinomio complesso ha almeno una radice nel piano complesso. Richman [2000] ha dimostrato che senza una scelta numerabile, sebbene possiamo costruire solo radici isolate (possibilmente multiple), possiamo costruire approssimazioni arbitrariamente vicine al multiset di radici. Tale approccio si concentra sulla ricerca di una fattorizzazione lineare approssimativa del polinomio, piuttosto che sulla ricerca di approssimazioni separate per ciascuna delle sue radici.

Per ulteriori analisi dell'assioma della scelta nella teoria degli insiemi e nella teoria dei tipi si veda Martin-Löf [2006], e le voci del SEP sulla teoria delle categorie, la teoria dei tipi e la teoria dei tipi intuizionisti.

5. Matematica inversa costruttiva

Negli anni '70, Harvey Friedman iniziò un programma di ricerca di matematica inversa, con l'obiettivo di classificare i teoremi matematici in base alla loro equivalenza a uno di un numero limitato di principi teorici stabiliti (Friedman 1975). Questa classificazione rivela differenze interessanti, a volte notevoli, nella complessità della teoria della prova. Ad esempio, sebbene il teorema di Ascoli-Arzelà sia usato nella dimostrazione standard del teorema di esistenza di Peano per soluzioni di equazioni differenziali ordinarie (Hurewicz [1958], pagina 10), un'analisi matematica inversa mostra che il primo è equivalente a un rigorosamente più forte principio di teoria dell'insieme rispetto a quello equivalente al teorema di Peano (Simpson [1984], Teoremi 3.9 e 4.2). Il trattato standard sulla matematica inversa classica è (Simpson [1999/2009]).

Verso la fine di questo secolo, Veldman (vedi Altre risorse Internet), nei Paesi Bassi e Ishihara [2005, 2006], in Giappone, avviarono in modo indipendente un programma di matematica inversa costruttiva (CRM), basato su intuizionisti, piuttosto che classici, logica. (Si noti, tuttavia, che il primo lavoro pubblicato nell'era moderna del CRM è probabilmente quello di Julian e Richman [1984], che era venti anni in anticipo sui tempi.) In questa sezione dell'articolo, descriviamo un approccio meno formale a CRM, nello stile e nella struttura di BISH. Lo scopo di quel programma CRM è quello di classificare i teoremi nei tre modelli standard: CLASS, INT e RUSS, secondo quali principi dobbiamo, e dobbiamo solo aggiungere, a BISH per dimostrarli.

Sottolineiamo che qui ci limitiamo al CRM informale, in cui diamo per scontati i principi di funzione e costruzione del set descritti nei primi capitoli di Bishop [1967] o Bishop & Bridges [1985], e lavoriamo nell'informale, sebbene rigoroso, stile dell'analista praticante, algebrista, topologo, …

In pratica, CRM si divide naturalmente in due parti. Nel primo di questi, consideriamo un teorema (T) di INT o RUSS, e proviamo a trovare qualche principio, valido in quel modello e diverso da (T) stesso, la cui aggiunta a BISH è necessaria e sufficiente per una dimostrazione costruttiva di (T). Nella seconda parte di CRM trattiamo un teorema (T) di CLASS che sospettiamo non sia costruttivo, e proviamo a dimostrare che (T) è equivalente, rispetto a BISH, a uno di un numero di noti essenzialmente- principi non costruttivi, come MP, LLPO, LPO o LEM. Per un esempio di questa parte di CRM, citiamo la nostra prima prova che il classico principio del limite inferiore implica, e quindi è equivalente a, LEM.

Per inciso, c'è una forte argomentazione per cui Brouwer [1921] è il primo a occuparsi di idee matematiche inverse: i suoi controesempi Brouwerian (vedi quello che usa la congettura di Goldbach, nella Sezione 1 sopra) si trovano esattamente nella seconda parte di CRM. Anche se Brouwer non ha indicato quegli esempi come equivalenze logiche, ma come implicazioni del tipo

[P / Rightarrow / text {qualche principio non costruttivo},)

è difficile credere che non fosse a conoscenza del fatto che il lato destro implicava la sinistra in questi casi.

5.1 Teoremi dei fan in CRM

Per illustrare la prima parte di CRM, ora ci concentriamo su teoremi del tipo

(text {BISH} vdash / text {FT} _? / Leftrightarrow T,)

dove FT (_?) è una forma del teorema dei fan di Brouwer e (T) è un teorema di INT. Per fare ciò, dobbiamo distinguere tra alcuni tipi di barra per il fan binario completo (2 ^ *) (l'insieme di tutte le sequenze finite in ({0,1 })).

Sia (alpha / equiv (alpha_1, / alpha_2, / ldots)) essere una sequenza binaria finita o infinita. La concatenazione di (alpha) con un'altra stringa (beta) è

(alpha ^ { frown} beta / equiv (alpha_1, / alpha_2, / ldots, / alpha_n, / beta_1, / ldots, / beta_m).)

Per (b) in ({0,1 }) scriviamo (alpha ^ { frown} b) anziché (alpha ^ { frown} (b)). Con un (mathsf {c}) - sottoinsieme di (2 ^ *) intendiamo un sottoinsieme (B) di (2 ^ *) tale che

(tag {1} B = {u / in 2 ^ *: / forall v / in 2 ^ * (u ^ { frown} v / in D) })

per alcuni sottoinsiemi staccabili (D) di (2 ^ *). Ogni sottoinsieme staccabile di (2 ^ *) è un sottoinsieme (mathsf {c}). D'altra parte, per (Pi ^ {0} _1) - sottoinsieme di (2 ^ *) intendiamo un sottoinsieme (B) di (2 ^ *) con la seguente proprietà: esiste un sottoinsieme staccabile (S) di (2 ^ * / times / bN) tale che

(forall u / in 2 ^ * \, / forall n / in / bN \, ((u, n) in S / Rightarrow (u ^ { frown} 0, n) in S / wedge (u ^ { frown} 1, n) in S))

e

[B = {u / in 2 ^ *: / forall n / in / bN ((u, n) in S) }.)

Ogni (mathsf {c}) - sottoinsieme (B) di (2 ^ *) è un (Pi ^ {0} _1) - sottoinsieme: semplicemente prendere (S = D / times / bN), dove (D) è un sottoinsieme staccabile di (2 ^ *) tale che (1) vale.

Se (?) Indica una proprietà di sottoinsiemi di (2 ^ *), il teorema del fan di Brouwer per (?) - bars ci dice che ogni barra con la proprietà (?) È una barra uniforme. Siamo particolarmente interessati al teorema dei fan per le barre staccabili (già discusso nella sezione 3.1):

FT (_ D): ogni barra staccabile dell'intera ventola binaria è uniforme;

il teorema del fan per (mathsf {c}) - bars (ovvero, barre che sono (mathsf {c}) - subset):

FT (_ { mathsf {c}}): ogni barra c della ventola binaria completa è uniforme;

il teorema del fan per (Pi ^ {0} _1) - bars (ovvero barre che sono (Pi ^ {0} _1) - subset):

FT (_ { Pi ^ {0} _1}): ogni (Pi ^ {0} _1) - la barra del fan binario completo è uniforme;

e il teorema del fan completo:

FT: Ogni barra del ventilatore binario completo è uniforme.

Si noti che, rispetto a BISH, FT (Rightarrow) FT (_ { Pi ^ {0} _1} Rightarrow) FT (_ c / Rightarrow) FT (_ D).

Lubarsky e Diener [2014] hanno dimostrato che queste implicazioni sono rigorose.

In genere, vogliamo dimostrare che FT (_?) È equivalente, rispetto a BISH, alla proposizione che, per ogni set (S) di un tipo appropriato, alcune proprietà puntuali del modulo

(tag {2} forall x / in S / esiste t / in TP (s, t))

in realtà tiene uniformemente nella forma

(tag {3} esiste t / in T / forall s / in SP (s, t).)

La nostra strategia per attaccare questo problema è duplice. Innanzitutto, dato un set (S) del tipo appropriato, costruiamo un? -Subset (N) di (2 ^ *) tale che

  • se (2) è valido, allora (B) è una barra e
  • se (B) è una barra uniforme, quindi (3) vale.

Questa, tuttavia, è solo metà della soluzione. Per dimostrare che le implicazioni da (3) a (2) implicano FT (_?), Consideriamo un? -Subset (B) di (2 ^ *) e costruiamo un insieme corrispondente (S) tale che

  • se (B) è una barra, quindi (2) vale e
  • se (3) è valido, allora (B) è una barra uniforme.

L'esempio canonico di tali risultati è quello di Julian e Richman [1984], in cui (S) è l'insieme di valori di una data mappatura uniformemente continua (f: [0,1] rightarrow / bR, T) è l'insieme di numeri reali positivi e

[P (s, t) equiv (s / ge t).)

La proprietà puntuale che consideriamo è

(forall x / in [0,1] esiste t / gt 0 (f (x) ge t),)

essendo la sua versione uniforme

(esiste t / gt 0 / forall x / in [0,1] (f (x) ge t).)

I risultati di Julian-Richman sono i seguenti.

Teorema 1: Sia (f: [0,1] rightarrow / bR) essere uniformemente continuo. Quindi esiste un sottoinsieme staccabile (B) di (2 ^ *) tale che

  • se (f (x) gt 0) per ogni (x / in [0,1]), allora (B) è una barra e
  • se (B) è una barra uniforme, quindi (inf f / gt 0).

Teorema 2: Sia (B) un sottoinsieme staccabile di (2 ^ *). Quindi esiste un (f: [0,1] rightarrow / bR) uniformemente continuo tale che

  • se (B) è una barra, quindi (f (x) gt 0) per ciascuno (x / in [0,1]) e
  • se inf (f / gt 0), allora (B) è una barra uniforme.

Le prove di questi due teoremi sono sottili e complicate; vedi Julian & Richman [1984].

I due teoremi di Julian-Richman rivelano insieme che, rispetto a BISH, il teorema del fan FT (_ D) è equivalente al principio di positività, POS:

Ogni funzione a valore positivo, uniformemente continua su ([0,1]) ha un infimo positivo.

Ne consegue che POS è derivabile in INT, in cui l'intero teorema del fan, non solo FT (_ D), è un principio standard. La situazione è tranquilla al contrario in RUSSIA, dove esiste sia una barra staccabile di (2 ^ *) che non è uniforme sia una funzione con valore positivo, uniformemente continua su ([0,1]) che ha infima uguale a 0; vedere i capitoli 5 e 6 di Bridges & Richman [1987].

Berger e Ishihara [2005] hanno preso una strada diversa, indiretta, per stabilire l'equivalenza di POS e FT (_ c). Stabiliscono una catena di equivalenze tra POS, FT (_ c) e quattro principi del tipo "se esiste al massimo un oggetto con proprietà (P), allora esiste un oggetto del genere". I quattro principi di esistenza unica sono:

CIN!: Ogni sequenza discendente di sottoinsiemi situati chiusi abitati di uno spazio metrico compatto con al massimo un punto comune ha un'intersezione abitata (teorema di intersezione di Cantor con unicità.) Si noti che un sottoinsieme (S) di uno spazio metrico ((X, / rho)) si trova se per ogni (x) in (X) esiste la distanza minima da (x) a (S).

MIN!: Ogni funzione uniformemente continua, con valori reali su uno spazio metrico compatto con al massimo un punto minimo ha un punto minimo.

WKL! Ogni albero infinito con al massimo un ramo infinito ha un ramo infinito (il debole lemma di König con unicità).

FIX!: Ogni funzione uniformemente continua da uno spazio metrico compatto in se stessa con al massimo un punto fisso e con punti fissi approssimativi ha un punto fisso.

Ad esempio, nell'ultimo di questi, diciamo che una mappa (f) di uno spazio metrico ((X, / varrho)) in se stessa

  • ha al massimo un punto fisso se (varrho (f (x), x) + / varrho (f (y), y) gt 0) quando (varrho (x, y) gt 0);
  • ha punti fissi approssimativi se per ogni (varepsilon / gt 0) esiste (x / in X) tale che (varrho (f (x), x) lt / varepsilon).

Un grave problema aperto nel CRM è quello di trovare una forma del teorema del fan che sia equivalente, rispetto a BISH, al teorema di continuità uniforme per ([0,1]), UCT (_ {[0,1]}): ogni mapping continuo puntuale di ([0,1]) in (bR) è uniformemente continuo, la proposta per la quale Brouwer sviluppò originariamente la sua prova del teorema dei fan. (Si noti che UCT (_ {[0,1]}) è equivalente, rispetto a BISH, al teorema di continuità uniforme generale per gli spazi metrici: ogni mappatura continua puntuale di uno spazio metrico completo e totalmente limitato in uno spazio metrico è uniformemente continuo. Vedi, ad esempio, Loeb [2005].)

Ne consegue dai risultati di Berger [2006]

BISH (vdash) UCT (_ {[0,1]} Rightarrow) FT (_ c).

Inoltre, Diener e Loeb (2008) lo hanno dimostrato

BISH (vdash) FT (_ { Pi ^ {0} _1} Rightarrow) UCT (_ {[0,1]}).

Tuttavia, non sappiamo se nessuna di queste implicazioni può essere sostituita da una bi-implicazione. Forse UCT (_ {[0,1]}), e quindi il teorema di continuità uniforme per spazi metrici compatti, è equivalente, rispetto a BISH, ad una versione naturale, ma non ancora identificata, del teorema del fan.

Per materiale aggiuntivo sul teorema dei fan nella matematica inversa costruttiva, vedi, ad esempio, Berger & Bridges [2007]; Diener [2008, 2012]; Diener & Loeb [2009]; e Diener & Lubarsky [2014]. In Dent [2013], c'è un diagramma chiaro, sebbene complesso, che illustra le interconnessioni tra i teoremi dei fan, la continuità e i principi di onniscienza (vedi Altre risorse su Internet).

I lettori interessati possono approfondire l'argomento della matematica inversa costruttiva nel seguente documento supplementare:

Il principio di Ishihara (BDN) e la proprietà anti-Specker

6. Algebra costruttiva e topologia

I matematici costruttivi hanno teso a concentrare i loro sforzi nel campo dell'analisi, con notevole successo a testimonianza della ricchezza di analisi funzionale sviluppata in Bishop [1967]. Ciò non significa che, ad esempio, l'algebra sia stata messa da parte dall'impresa costruttiva: il materiale nella monografia di Mines et al [1986] può essere considerato una sostanziale controparte algebrica dell'analisi costruttiva condotta da Bishop. Molto più recentemente, Lombardi e Quitté [2011] hanno pubblicato il primo grande volume di una proposta di lavoro in due volumi sull'algebra costruttiva. Tuttavia, non essendo esperti di algebra e consapevoli del pericolo di rendere questo articolo troppo lungo per attirare l'attenzione del lettore, scegliamo di non discutere l'analisi costruttiva o l'algebra in alcun dettaglio; piuttosto, nel seguente documento supplementare,passiamo alla topologia costruttiva, descrivendo alcuni approcci piuttosto diversi a tale argomento:

Approcci alla topologia costruttiva

7. Economia e finanza matematica costruttiva

Le ricerche in economia matematica costruttiva risalgono a una serie di articoli su preferenze, utilità e domanda dal 1982 in poi; vedi Bridges [1999]. Nella sua tesi di dottorato, Hendtlass [2013] ha sostanzialmente indebolito le condizioni per l'esistenza di una funzione di domanda; ha anche prodotto una vasta gamma di risultati nella teoria dei punti fissi e nelle sue applicazioni, in particolare per la costruzione di due prove classiche dell'esistenza di un equilibrio economico.

Nel 2015, Berger e Svindland hanno avviato un progetto di ricerca sulla finanza matematica costruttiva, presso Ludwig-Maximilians-Universität a Monaco di Baviera, dimostrando per la prima volta che il teorema fondamentale sui prezzi delle attività, il teorema dell'iperpiano di separazione e il Principio di Markov sono costruttivamente equivalenti (Berger & Svindland [2016]). Il loro lavoro più recente si è concentrato su come eludere la non costruttività del teorema del valore estremo classico al fine di dimostrare l'esistenza di punti estremi per funzioni in presenza di proprietà di convessità anche relativamente deboli (Berger & Svindland [2016a]). Il loro progetto suggerisce che la finanza matematica, come l'economia matematica, può essere una ricca fonte di teoremi costruttivi eleganti e pratici.

8. Osservazioni conclusive

Il percorso tradizionale seguito dai matematici che desiderano analizzare il contenuto costruttivo della matematica è quello che segue la logica classica; per evitare decisioni, come se un numero reale sia uguale o meno a 0, che non può essere preso da un computer reale, il matematico deve quindi mantenere entro limiti algoritmici rigorosi come quelli formati dalla teoria delle funzioni ricorsive. Al contrario, il percorso intrapreso dal matematico costruttivo segue la logica intuizionista, che si occupa automaticamente delle decisioni computazionalmente inammissibili. Questa logica (unitamente a una struttura teorica set o tipo appropriata) è sufficiente per mantenere la matematica entro limiti costruttivi. Pertanto, il matematico è libero di lavorare nello stile naturale di analista, algebrista (ad es. Mines et al. [1988]), geometra, topologo (ad es. Bridges &Vîță [2011], Sambin di prossima pubblicazione), o altro matematico normale, gli unici vincoli sono quelli imposti dalla logica intuizionista. Come hanno dimostrato Bishop e altri, la credenza tradizionale promulgata da Hilbert e ancora oggi ampiamente diffusa, secondo cui la logica intuizionistica impone restrizioni tali da rendere impossibile lo sviluppo di una matematica seria, è palesemente falsa: gran parte della matematica moderna profonda può essere e avere stato, prodotto con metodi puramente costruttivi. Inoltre, il legame tra matematica costruttiva e programmazione è molto promettente per la futura implementazione e sviluppo della matematica astratta sul computer.la credenza tradizionale promulgata da Hilbert e ancora oggi ampiamente diffusa, secondo cui la logica intuizionista impone restrizioni tali da rendere impossibile lo sviluppo della matematica seria, è palesemente falsa: gran parte della matematica moderna profonda può essere, ed è stata, prodotta con metodi puramente costruttivi. Inoltre, il legame tra matematica costruttiva e programmazione è molto promettente per la futura implementazione e sviluppo della matematica astratta sul computer.la credenza tradizionale promulgata da Hilbert e ancora oggi ampiamente diffusa, secondo cui la logica intuizionista impone restrizioni tali da rendere impossibile lo sviluppo della matematica seria, è palesemente falsa: gran parte della matematica moderna profonda può essere, ed è stata, prodotta con metodi puramente costruttivi. Inoltre, il legame tra matematica costruttiva e programmazione è molto promettente per la futura implementazione e sviluppo della matematica astratta sul computer.il legame tra matematica costruttiva e programmazione è molto promettente per la futura implementazione e sviluppo della matematica astratta sul computer.il legame tra matematica costruttiva e programmazione è molto promettente per la futura implementazione e sviluppo della matematica astratta sul computer.

Bibliografia

Riferimenti

  • Aberth, O., 1980, Analisi calcolabile, New York: McGraw-Hill.
  • –––, 2001, Calcolo calcolabile, New York: Academic Press.
  • Aczel, P. e Rathjen, M., 2001, Note sulla teoria dei set costruttivi (Rapporto n. 40), Stoccolma: Institut Mittag-Leffler, Royal Swedish Academy of Sciences.
  • Bauer, A., 2005, "Realizzabilità come connessione tra matematica calcolabile e costruttiva", Appunti di lezione per un tutorial in un seminario satellitare del CCA2005, Kyoto, Giappone [disponibile online].
  • Beeson, M., 1985, Fondamenti della matematica costruttiva, Heidelberg: Springer Verlag.
  • Berger, J., 2006, "La forza logica del teorema della continuità uniforme", in Approcci logici alle barriere computazionali, A. Beckmann, U. Berger, B. Löwe e JV Tucker (a cura di), Heidelberg: Springer Verlag.
  • Berger, J. e Bridges, DS, 2007, "Un fan-teorico equivalente dell'antitesi del teorema di Specker", Atti della Royal Dutch Mathematical Society (Indagationes Mathematicae) (Indag. Math. NS), 18 (2): 195 -202.
  • –––, 2009, “Il teorema del fan e funzioni uniformemente continue a valore positivo su intervalli compatti”, New Zealand Journal of Mathematics, 38: 129–135.
  • Berger, J. e Ishihara, H., 2005, "Teorema dei fan di Brouwer ed esistenza unica nell'analisi costruttiva", Mathematical Logic Quarterly, 51 (4): 360–364.
  • Berger, J. e Schuster, PM, 2006, "Classificare il teorema di Dini", Notre Dame Journal of Formal Logic, 47: 253–262.
  • Berger, J. e Svindland, G., 2016, "Un teorema di iperpiano di separazione, il teorema fondamentale dei prezzi delle attività e il principio di Markov", Annals of Pure and Applied Logic, 167, 1161-111170.
  • –––, 2016a, “Convessità e infima costruttiva”, Archive for Mathematical Logic, 55: 873–881
  • Bishop, E., 1967, Foundations of Constructive Analysis, New York: McGraw-Hill.
  • –––, 1973, Schizofrenia in Matematica Contemporanea (American Mathematical Society Colloquium Lectures), Missoula: University of Montana; ristampato in Errett Bishop: riflessioni su di lui e le sue ricerche, American Mathematical Society Memoirs 39.
  • Bishop, E. and Bridges, D., 1985, Analisi costruttiva, (Grundlehren der matematischen Wissenschaften, 279), Heidelberg: Springer Verlag.
  • Bourbaki, N., 1984, Éléments d'histoire des mathématiques, Parigi: Masson; Edizione in lingua inglese, Elements of the History of Mathematics, J. Meldrum (trans.), 2006, Berlino: Springer Verlag.
  • Bridges, DS, 1999, "Metodi costruttivi in economia matematica", in Zeitschrift für Nationalökonomie (Supplemento), 8: 1–21.
  • Bridges, DS e Diener, H., 2007, "La pseudocompatibilità di [0, 1] equivale al teorema di continuità uniforme", Journal of Symbolic Logic, 72 (4): 1379–1383.
  • Bridges, DS e Richman, F., 1987, Varietà di matematica costruttiva, London Mathematical Society Appunti di lezione 97, Cambridge: Cambridge University Press.
  • Bridges, DS and Vîță, LS, 2006, Techniques of Constructive Analysis, Heidelberg: Springer Verlag.
  • –––, 2011, Apartness and Uniformity-A Constructive Development, Heidelberg: Springer Verlag
  • Brouwer, LEJ, 1907, Over de Grondslagen der Wiskunde, tesi di dottorato, Università di Amsterdam; ristampato con materiale aggiuntivo, D. van Dalen (a cura di), di Matematisch Centrum, Amsterdam, 1981.
  • –––, 1908, “De onbetrouwbaarheid der logische principes”, Tijdschrift voor Wijsbegeerte, 2: 152–158.
  • –––, 1921, “Besitzt jede reelle Zahl eine Dezimalbruchentwicklung?”, Mathematische Annalen, 83: 201–210.
  • –––, 1924, “Beweis, dass jede volle Funktion gleichmässig stetig ist”, Atti della Royal Dutch Mathematical Society, 27: 189–193.
  • –––, 1924A, “Bemerkung zum Beweise der gleichmässigen Stetigkeit voller Funktionen”, Atti della Royal Dutch Mathematical Society, 27: 644–646.
  • Cederquist, J. e Negri, S., 1996, "Una dimostrazione costruttiva dell'Heine-Borel che copre il teorema dei reali formali", in Tipi di prove e programmi (Appunti di lezione in Informatica, Volume 1158), 62–75, Berlino: Springer Verlag.
  • Constable, R., et al., 1986, Implementing Mathematics con Nuprl Proof Development System, Englewood Cliffs, NJ: Prentice-Hall.
  • Coquand, T., 1992, “Una dimostrazione intuitiva del teorema di Tychonoff”, Journal of Symbolic Logic, 57: 28–32.
  • –––, 2009, “Spazio delle valutazioni”, Annali di logica pura e applicata, 157: 97–109.
  • –––, 2016, "Type Theory", Stanford Encyclopedia of Philosophy (Winter 2016 Edition), Edward N. Zalta (ed.), URL (= / lt) https://plato.stanford.edu/entries/ tipo-teoria / (gt)
  • Coquand, T. e Spitters, B., 2009, “Integrals and Valuations”, Journal of Logic and Analysis, 1 (3): 1–22.
  • Coquand, T., Sambin, G., Smith, J. e Valentini, S., 2003, "Topologie formali generate induttivamente", Annali di logica pura e applicata, 124: 71–106.
  • Curi, G., 2010, “Sull'esistenza della compactificazione di Stone-Čech”, Journal of Symbolic Logic, 75: 1137-1146.
  • Dent, JE, 2013, Proprietà Anti-Specker in Matematica inversa costruttiva, Ph. D. tesi, Università di Canterbury, Christchurch, Nuova Zelanda.
  • Diaconescu, R., 1975, “Assioma di scelta e complementazione”, Atti della American Mathematical Society, 51: 176–178
  • Diener, H., 2008, Compattezza sotto esame costruttivo, Ph. D. tesi, Christchurch, Nuova Zelanda: Università di Canterbury.
  • –––, 2008a, “Compattezza generalizzante”, Logica matematica trimestrale, 51 (1): 49–57.
  • –––, 2012, “Riclassificazione dell'antitesi del teorema di Specker”, Archive for Mathematical Logic, 51: 687–693.
  • Diener, H. e Loeb, I., 2009, "Sequenze di funzioni reali su [0, 1] in matematica inversa costruttiva", Annali di logica pura e applicata, 157 (1): 50–61.
  • Diener, H. e Lubarsky, R., 2013, "Separare il teorema dei fan e i suoi indebolimenti", in Logical Foundations of Computer Science (Lecture Notes in Computer Science, 7734), S. Artemov e A. Nerode (eds.), Berlino: Springer Verlag.
  • Dummett, Michael, 1977 [2000], Elements of Intuitionism (Oxford Logic Guides, 39), Oxford: Clarendon Press, 1977; 2a edizione, 2000. [I riferimenti alla pagina si riferiscono alla 2a edizione.]
  • Ewald, W., 1996, Da Kant a Hilbert: A Source Book in the Foundations of Mathematics (Volume 2), Oxford: Clarendon Press.
  • Feferman, S, 1975, “Un linguaggio e assiomi per la matematica esplicita”, in Algebra e Logit, JN Crossley (a cura di), Heidelberg: Springer Verlag, pagg. 87–139.
  • –––, 1979, “Teorie costruttive di funzioni e classi”, in Logic Colloquium '78, M. Boffa, D. van Dalen e K. McAloon (a cura di), Amsterdam: Olanda Settentrionale, pp. 159–224.
  • Friedman, H., 1975, "Alcuni sistemi di aritmetica del secondo ordine e il loro uso", in Atti del 17 ° Congresso Internazionale dei Matematici, Vancouver, BC, 1974.
  • –––, 1977, “Imposta le basi teoriche per l'analisi costruttiva”, Annals of Mathematics, 105 (1): 1–28.
  • Goodman, ND, e Myhill, J., 1978, "La scelta implica il mezzo escluso", Zeitschrift für Logik und Grundlagen der Mathematik, 24: 461.
  • Hayashi, S. e Nakano, H., 1988, PX: A Logica computazionale, Cambridge MA: MIT Press.
  • Hendtlass, M., 2013, Costruzione di punti fissi ed equilibri economici, Ph. D. tesi, Università di Leeds.
  • Heyting, A., 1930, "Die formalen Regeln der intuitionistischen Logik", Sitzungsberichte der Preussische Akadademie der Wissenschaften. Berlino, 42–56.
  • –––, 1971, Intuitionism-an Introduction, 3a edizione, Amsterdam: Olanda Settentrionale.
  • Hilbert, D., 1925, “Über das Unendliche”, Mathematische Annalen, 95: 161–190; traduzione, "Sull'infinito", di E. Putnam e G. Massey, in Filosofia della matematica: letture selezionate, P. Benacerraf e H. Putnam (a cura di), Englewood Cliffs, NJ: Prentice Hall, 1964, 134–151.
  • Hurewicz, W., 1958, Conferenze su equazioni differenziali ordinarie, Cambridge, MA: MIT Press.
  • Ishihara, H., 1992, “Proprietà di continuità nella matematica costruttiva”, Journal of Symbolic Logic, 57 (2): 557–565.
  • –––, 1994, “Una versione costruttiva del teorema della mappatura inversa di Banach”, New Zealand Journal of Mathematics, 23: 71–75.
  • –––, 2005, "Matematica costruttiva inversa: proprietà di compattezza", in Da insiemi e tipi a analisi e topologia: verso basi praticabili per la matematica costruttiva, L. Crosilla e P. Schuster (a cura di), Oxford: The Clarendon Press.
  • –––, 2006, “Matematica inversa nella matematica costruttiva di Bishop”, Philosophia Scientiae (Cahier Special), 6: 43–59.
  • –––, 2013, “Correlazione degli spazi funzionali di Bishop con gli spazi del vicinato”, Annali di logica pura e applicata, 164: 482–490.
  • Johnstone, PT, 1982, Stone Spaces, Cambridge: Cambridge University Press.
  • –––, 2003, “Il punto della topologia inutile”, Bollettino dell'American Mathematical Society, 8: 41–53.
  • Joyal, A. e Tierney, M., 1984, “Un'estensione della teoria di Grothendieck di Galois”, Memorie dell'American Mathematical Society, 309: 85 pagg.
  • Julian, WH e Richman, F., 1984, "Una funzione uniformemente continua su [0, 1] che è ovunque diversa dal suo infimo", Pacific Journal of Mathematics, 111: 333–340.
  • Kushner, B., 1985, Conferenze di analisi matematica costruttiva, Provvidenza, RI: American Mathematical Society
  • Lietz, P., 2004, Dalla matematica costruttiva all'analisi calcolabile attraverso l'interpretazione della realizzabilità, Dr. rer. nat. tesi di laurea, Universität Darmstadt, Germania.
  • Lietz, P. e Streicher, T., "Modelli di realizzabilità che confutano il principio di delimitazione di Ishihara", Annali di pura e logica applicata, 163 (12): 1803–1807.
  • Loeb, I., 2005, “Equivalents of the (Debole) Fan Theorem”, Annals of Pure and Applied Logic, 132: 51–66.
  • Lombardi, H., Quitté, C., 2011, Algèbre Commutative. Costruttori di Méthodes, Nanterre, Francia: Calvage et Mounet.
  • Lorenzen, P., 1955, Einführung in Die Logik und Mathematik (Grundlehren der matematischen Wissenschaften, Volume 78), 2a edizione, 1969, Heidelberg: Springer.
  • Lubarsky, R. e Diener, H., 2014, “Separare il teorema dei fan e i suoi indebolimenti”, Journal of Symbolic Logic, 79 (3): 792–813.
  • Markov, AA, 1954, Teoria degli algoritmi, Trudy Mat. Istituta imeni VA Steklova, 42, Moskva: Izdatel'stvo Akademii Nauk SSSR.
  • Marquis, J.-P., "Theory Categoria", The Stanford Encyclopedia of Philosophy (Winter 2015 Edition), Edward N. Zalta (ed.), URL (= / lt) https://plato.stanford.edu / archives / win2015 / voci / categoria teoria / (gt).
  • Martin-Löf, P., 1968, Note sull'analisi costruttiva, Stoccolma: Almquist & Wiksell.
  • –––, 1975, “Una teoria intuitiva dei tipi: parte predicativa”, in Logic Colloquium 1973, HE Rose e JC Shepherdson (a cura di), Amsterdam: Olanda settentrionale.
  • –––, 1980, “Matematica costruttiva e programmazione informatica”, in Proc. 6 °. Int. Congresso di logica, metodologia e filosofia della scienza, L. Jonathan Cohen (a cura di), Amsterdam: Olanda settentrionale.
  • –––, 1984, Intuitionistic Type Theory, Appunti di Giovanni Sambin di una serie di lezioni tenute a Padova, giugno 1980, Napoli: Bibliopolis.
  • –––, 2006, “100 anni dell'assioma di scelta di Zermelo: qual è stato il problema?”, The Computer Journal, 49 (3): 345–350.
  • Menger, K., 1940, “Topologia senza punti”, Rice Institute Pamphlet, 27 (1): 80–107 [disponibile online].
  • Mines, R., Richman, F., and Ruitenburg, W., 1988, A Course in Constructive Algebra, Universitext, Heidelberg: Springer Verlag.
  • Moerdijk, I., 1984, “Heine-Borel non implica il teorema dei fan”, Journal of Symbolic Logic, 49 (2): 514–519.
  • Moore, GH, 2013, Assioma della scelta di Zermelo: origini, sviluppo e influenza, New York: Dover.
  • Myhill, J., 1973, "Alcune proprietà dell'intuizionista Zermelo-Fraenkel Set Theory", a Cambridge Summer School in Mathematical Logic, A. Mathias e H. Rogers (a cura di), Appunti di lezione in matematica, 337, Heidelberg: Springer Verlag, 206-231.
  • –––, 1975, “Costruttivo Set Theory”, Journal of Symbolic Logic, 40 (3): 347–382.
  • Naimpally, S., 2009, Approccio di prossimità ai problemi di topologia e analisi, Monaco: Oldenbourg Verlag.
  • Naimpally, S. e Warrack, BD, 1970, Proximity Spaces (Cambridge Tracts in Math. And Math. Phys., Volume 59), Cambridge: Cambridge University Press.
  • Nordström, B., Peterson, K. e Smith, JM, 1990, "Programmazione nella teoria dei tipi di Martin-Löf", Oxford: Oxford University Press.
  • Palmgren, E., 2007, “Un incorporamento costruttivo e funzionale di spazi metrici localmente compatti in locali”, Topologia e sue applicazioni, 154: 1854–1880.
  • –––, 2008, “Risoluzione del problema uniforme del limite inferiore nell'analisi costruttiva”, Logica matematica trimestrale, 54: 65–69.
  • –––, 2009, “Dall'intuizionista alla topologia formale: alcune osservazioni sui fondamenti della teoria dell'omotopia”, in: Logicismo, intuizionismo e formalismo: che ne è stato?, S. Lindström, E. Palmgren, K. Segerberg e V. Stoltenberg-Hansen (a cura di), 237–253, Berlino: Springer Verlag.
  • Petrakis, I., 2016, "Un approccio costruttivo teorico-funzionale alla compattezza topologica", in Metodi logici in informatica 2016, Pubblicazioni IEEE Computer Society: 605–614.
  • –––, 2016a, “Il teorema di estensione di Urysohn per Bishop Spaces”, a S. Artemov e A. Nerode (a cura di), Simposio sui fondamenti logici in informatica 2016 (Appunti di lezione in informatica 9537), Berlino: Springer Verlag, 299–316.
  • Picado, J. e Pultr, A., 2011, Cornici e locali: Topologia senza punti, Basilea: Birkhäuser Verlag.
  • Richman, F., 1983, “Tesi della Chiesa senza lacrime”, Journal of Symbolic Logic, 48: 797–803.
  • –––, 1990, “Intuizionismo come generalizzazione”, Philosophia Mathematica, 5: 124–128.
  • –––, 1996, “Intervista con un matematico costruttivo”, Modern Logic, 6: 247–271.
  • –––, 2000, “Il teorema fondamentale dell'algebra: un trattamento costruttivo senza scelta”, Pacific Journal of Mathematics, 196: 213–230.
  • Riesz, F., 1908, “Stetigkeitsbegriff und abstrakte Mengenlehre”, Atti IV Congresso Internationale Matematica Roma II, 18–24.
  • Sambin, G., 1987, "Spazi formali intuitivi - una prima comunicazione", in Logica matematica e sue applicazioni, D. Skordev (ed.), 187–204, New York: Plenum Press.
  • –––, di prossima pubblicazione, The Basic Picture: Structures for Constructive Topology, Oxford: Oxford University Press.
  • Sambin, G. e Smith, J. (a cura di), 1998, Venticinque anni di teoria dei tipi costruttivi, Oxford: Clarendon Press.
  • Schuster, PM, 2005, "Che cos'è la continuità, in modo costruttivo?", Journal of Universal Computer Science, 11: 2076–2085
  • –––, 2006, “Topologia di Zariski formale: positività e punti”, Annali di logica pura e applicata, 137: 317–359.
  • Schwichtenberg, H., 2009, "Estrazione di programmi in analisi costruttiva", in Logicismo, Intuizionismo e Formalismo: che fine hanno fatto?, S. Lindström, E. Palmgren, K. Segerberg e V. Stoltenberg-Hansen (a cura di), Berlino: Springer Verlag, 255–275.
  • Simpson, SG, 1984, "Che imposta gli assiomi dell'esistenza sono necessari per dimostrare il teorema di Cauchy / Peano per le equazioni differenziali ordinarie", Journal of Symbolic Logic, 49 (3): 783–802.
  • –––, 2009, Sottosistemi di aritmetica del secondo ordine, seconda edizione, Cambridge: Cambridge University Press.
  • Specker, E., 1949, “Nicht konstruktiv beweisbare Sätze der Analysis”, Journal of Symbolic Logic, 14: 145–158.
  • Steinke, TA, 2011, Nozioni costruttive di compattezza in Apartness Spaces, M. Sc. Tesi, Università di Canterbury, Christchurch, Nuova Zelanda.
  • Troelstra, AS, 1978, “Aspetti della matematica costruttiva”, nel Manuale di Logica matematica, J. Barwise (ed.), Amsterdam: Olanda Settentrionale.
  • Troelstra, AS e van Dalen, D., 1988, Costruttivismo in matematica: un'introduzione (due volumi), Amsterdam: Olanda Settentrionale.
  • van Atten, M., 2004, Su Brouwer, Belmont: Wadsworth / Thomson Learning.
  • van Dalen, D., 1981, Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
  • –––, 1999, Mystic, Geometer and Intuitionist: The Life of LEJ Brouwer (Volume 1), Oxford: Clarendon Press.
  • –––, 2005, Mystic, Geometer e Intuitionist: The Life of LEJ Brouwer (Volume 2), Oxford: Clarendon Press.
  • van Stigt, WP, 1990, Intuitionism di Brouwer, Amsterdam: Olanda Settentrionale.
  • Vickers, S., 2005, "Completamento locale di spazi metrici generalizzati I", Teoria e applicazioni delle categorie, 14 (15): 328–356.
  • Waaldijk, F., 2005, Sulle basi della matematica costruttiva, Foundations of Science, 10 (3): 249–324.
  • Wallman, H., 1938, “Grate di spazi topologici”, Annali di matematica, 39: 112–126.
  • Weihrauch, K., 2000, Analisi calcolabile (testi EATCS in informatica teorica), Heidelberg: Springer Verlag.
  • Weyl, H., 1946, “Mathematics and Logic”, American Mathematical Monthly, 53 (1): 2–13.
  • Whitehead, AN, 1919, Un'indagine riguardante i principi della conoscenza naturale, Cambridge: Cambridge University Press, seconda edizione, 1925.

Letteratura correlata

  • Heijenoort, Jean van, 1967, Da Frege a Gödel: un libro di fonti in logica matematica 1879–1931, Cambridge, MA: Harvard University Press.
  • Hilbert, David, 1928, "Die Grundlagen der Mathematik", Hamburger Mathematische Einzelschriften 5, Teubner, Lipsia. Ristampato in traduzione inglese in van Heijenoort 1967.

Strumenti accademici

icona dell'uomo sep
icona dell'uomo sep
Come citare questa voce.
icona dell'uomo sep
icona dell'uomo sep
Visualizza l'anteprima della versione PDF di questa voce presso Friends of the SEP Society.
icona di inpho
icona di inpho
Cerca questo argomento nell'Internet Philosophy Ontology Project (InPhO).
icona di documenti phil
icona di documenti phil
Bibliografia avanzata per questa voce su PhilPapers, con collegamenti al suo database.

Altre risorse Internet

  • Agda Wiki, un linguaggio di programmazione funzionale digitato e assistente di prova, Università di Göteborg e Chalmers University of Technology.
  • Agda, entrata in Wikipedia.
  • The Coq Proof Assistant, Inria, 1984-2017.
  • Coq, voce su Wikipedia.
  • Diagramma di James Dent.
  • Aczel, P. e Rathjen, M., 2018, Teoria costruttiva set, PDF online.
  • Bauer, A., 2005, "La realizzabilità come connessione tra matematica calcolabile e costruttiva".
  • Veldman, W., 2014, "Teorema dei fan di Brouwer come assioma e in contrasto con l'alternativa di Kleene", arxiv: 1106.2738https://arxiv.org/abs/1106.2738.

Raccomandato: