Mana personīgā interneta lapa - šeit.

Komentārus sūtiet Karlis.Podnieks@mii.lu.lv.

Intuicionisms
un
konstruktīvisms

Kārlis Podnieks, LU profesors

Lekcija studiju kursam
"Pierādījuma jēdziena evolūcija matemātikā"

2008.gada 12.septembris

Avoti

[1] Intuitionism, Stanford Encyclopedia of Philosophy.

[2] Intuitionistic Logic, Stanford Encyclopedia of Philosophy.

[3] Constructive Mathematics, Stanford Encyclopedia of Philosophy.

Kāpēc tas viss iesākās?

Kopu teorijas rašanās 1873.gadā (Georgs Kantors). Kopu teorijas paradoksi (1895.gads). Rasela paradokss (1902.gads).

Trešā krīze matemātikas pamatos...

Sīkāk sk. manas grāmatas
"What is Mathematics: Gödel's Theorem and Around"
2. sadaļu.

Liuvila transcendentais skaitlis. Ž. Liuvils 1844.gadā to uzkonstruēja. Bet Kantors savā jaunajā kopu teorijā jau 1873.gadā vienkārši pierādīja, ka "vairums" reālo skaitļu ir transcendenti (bet nevienu konkrētu transcendentu skaitli no viņa pierādījuma "izlobīt" nevar).

Ar kopu teorijas parādīšanos matemātikā kļuva iespējami ļoti nekonstruktīvi pierādījumi.

Nekonstruktīva pierādījuma piemērs

(Aizgūts no [3], autors Michael Dummett, 1977? Tas nav "pats nekonstruktīvākais pierādījums pasaulē", bet laikam - pats skaistākais no tiem.)

Teorēma. Eksistē divi iracionāli skaitļi a, b, kam pakāpe ab ir racionāls skaitlis.

Pierādījums. a) Paņemsim a=b=sqrt(2). Ja ab = sqrt(2)sqrt(2) būtu racionāls skaitlis, tad teorēma būtu pierādīta.

b) Ja tomēr sqrt(2)sqrt(2) ir iracionāls skaitlis, tad paņemsim a=sqrt(2)sqrt(2) un b=sqrt(2). Tad ab=2. Tātad teorēma ir pierādīta.

Teorēma tiešām ir pierādīta, tikai mēs neesam ieguvuši nevienu konkrētu iracionālu skaitļu pāri a, b, kam ab būtu racionāls skaitlis. Mums ir divi pāri (a, b), bet mēs neprotam pateikt, kurš no tiem ir "īstais".

Tas ir nekonstruktīva pierādījuma piemērs: tiek pierādīta tāda objekta eksistence, kam izpildās uzdotie nosacījumi, bet viens konkrēts objekts uzrādīts netiek.

No Gelfonda-Šneidera teorēmas seko, ka sqrt(2)sqrt(2) ir transcendents skaitlis, tātad "īstais" pāris ir otrais. Šī teorēma ir pierādīta tikai 1934.gadā, un tās pierādījums ir desmitiem lpp. garš.

Secinājums: lai kādas teorēmas nekonstruktīva pierādījuma vietā iegūtu tās pašas teorēmas konstruktīvu pierādījumu, dažreiz ir jāiegulda milzīgs papildus darbs.

Vai no nekonstruktīva pierādījuma vispār ir kāds labums? IR. Ja tas mums izdodas, tātad ir vērts ieguldīt darbu, lai iegūtu konstruktīvu pierādījumu!

Izejas meklējumi

Analizējot matemātikas pamatu trešās krīzes cēloņus, un meklējot izeju no tās, radās dažādi risinājumi.

Visvairāk piekritēju ir risinājumam, ko 1908.gadā piedāvāja Ernsts Cermelo (Ernst Zermelo): aksiomatizēt Kantora kopu teoriju, noskaidrot, kāpēc tajā rodas pretrunas, un tad koriģēt teorijas aksiomas. Tā radās tas ko šodien sauc par Cermelo-Frenkeļa kopu teoriju (ZFC). Pretrunas tajā pagaidām vēl nav atrastas.

Sīkāk sk. manas grāmatas
"What is Mathematics: Gödel's Theorem and Around"
2.3. sadaļu.

Bet gandrīz vienlaicīgi tika piedāvāti vēl divi citi, pavisam savādāki risinājumi:

- Bertrana Rasela (Bertrand Russell) tipu teorija;

- holandiešu matemātiķa L. Brauera (Luitzen Egbertus Jan Brouwer) intuicionisms.

Intuicionisms

Brauers savā 1907.gada rakstā apgalvoja, ka matemātikas krīzes cēlonis ir parastās klasiskās loģikas lietošana situācijās, kurās tā nav derīga.

Par galveno pārkāpumu Brauers uzskatīja trešā izslēgtā likuma (F v ~F) izmantošanu eksistences pierādījumos. Ar tā palīdzību var izrīkoties, piemēram, šādi:

Pieņemsim, ka gribam pierādīt, ka ExF(x). Pieņemam no pretējā, ka tas nav tiesa: ~ExF(x) un izvedam pretrunu. Tad no ExF(x) v ~ExF(x) seko ExF(x). Bet konkrētu objektu x mēs no šāda pierādījuma varam arī neiegūt. Pierādījums var būt iznācis nekonstruktīvs. Intuicionisti nekonstruktīvus eksistences pierādījumus neatzīst.

Arī disjunkciju pierādījumos mēs varam izrīkoties līdzīgi. Lai pierādītu, piemēram, FvG, pieņemam no pretējā, ka tas nav tiesa: ~(FvG). Un izvedam pretrunu. Tad no (FvG) v ~(FvG) seko FvG. Bet no šāda pierādījuma mēs ne vienmēr varam uzzināt, kura tieši no disjunkcijas pusēm ir patiesa - F vai G (piemēru sk. lekcijas sākumā). Pierādījums var būt iznācis nekonstruktīvs. Intuicionisti tādus disjunkciju pierādījumus neatzīst.

Brauers noraidīja arī Kantora ievesto priekšstatu par aktuālo bezgalību (piemēram, visi naturālie skaitļi eksistē vienlaicīgi kā gatava "pabeigta" kopa). Viņaprāt, mēs varam iedomāties, ka naturālos skaitļus uzkonstruēt jebkurā skaitā, bet nevaram iedomāties, ka to visi jau ir uzkonstruēti un eksistē vienlaicīgi. Naturālie skaitļi veido potenciālu bezgalību, nevis aktuālu.

Tā būtu Brauera intuicionisma kritiskā (negatīvā) puse, kur īstenībā vēl nekāda intuicionisma nav, tikai normāls ceļa sākums uz konstruktīvu matemātiku.

Intuicionisma filosofija

Bet kā tad, pēc Brauera domām, būtu būvējama "pareizā" matemātika (Brauera pozitīvā programma)?

Brauers deklarēja, ka matemātikas pamatā ir cilvēku priekšstats par naturālo skaitļu potenciāli bezgalīgo virkni (naturālo skaitļu "intuīcija", kas atvasināma no laika tecējuma intuīcijas). To nevajag mēģināt definēt ar aksiomām, tā a priori ir iebūvēta cilvēku prātos. (Brauers atsaucās uz Imanuelu Kantu kā idejas autoru - Kants tāpat domāja arī par Eiklīda ģeometriju.) Patiesību matemātikā mēs noskaidrojam ar prāta konstrukciju palīdzību. Valoda matemātiķiem ir vajadzīga tikai, lai viens cilvēks varētu ierosināt otra cilvēka prātā tos pašus procesus, kas notiek savējā.

Tradicionālo matemātiku Brauers iesāka saukt par klasisko matemātiku, kritizēdams to par nekonstruktīvu spriedumu izmantošanu.

Sīkāk par intuicionisma filosofiju sk. [1].

Novirzes no konstruktīvisma...

Ja filosofijas pamatā cilvēks liek savu intuīciju, tad nav jābrīnās, ka rezultāts ne vienmēr iznāk "regulārs".

Tā, piemēram, Brauers atzīst par "labām" ne tikai rekursīvas naturālo skaitļi virknes, bet arī t.s. free choice sequences, jo viņš spējot iedomāties, kā virkne "attīstās", nepakļaujoties nekādiem likumiem...

Sīkāk par to sk. [1].

Konstruktīvisms

Nebija daudz tādu matemātiķu, kuri pieņēma intuicionisma filosofiju tiešu tādu, kādu to propagandēja Brauers (visievērojamākais no viņiem bija Hermanis Veils). Daudz vairāk bija tādu, kuriem vienkārši likās interesanti izpētīt, kādu matemātiku var uzbūvēt, ja izmanto tikai konstruktīvus objektus un konstruktīvus pierādījumus?

Tos cilvēkus, kuri šādu konstruktīvo matemātiku uzskata par "vienīgo īsto matemātiku", tad arī sauc par konstruktīvistiem (sk. [3]). Bet viņu ir tikpat maz kā "īstu" intuicionistu.

Tad nu palūkosimies (pārāk neaizraujoties...), kāda izskatās matemātika, ja to būvē tikai ar konstruktīviem līdzekļiem.

Konstruktīvā matemātika

Naturālie skaitļi konstruktīvajā matemātikā ir tie paši, kas klasiskajā: 0, 1, 11, 111, 1111, ...

Bet naturālo skaitļu kopas jau vairs drīkst būt tikai rekursīvas vai vismaz - rekursīvi sanumurējamas ("pusrekursīvas").

Veselie skaitļi un racionālie skaitļi - te nekādas problēmas nerodas.

Bet kādus reālos skaitļus drīkstam saukt par konstruktīviem?

Definīcija. Konstruktīvs reāls skaitlis (krs) ir divu rekursīvu funkciju pāris (f, g), kur f uzdod racionālu skaitļu virkni:

f(0), f(1), f(2), ... f(n), ...,

bet g "regulē" šīs virknes konverģenci šādā nozīmē: visiem m, n1, n2, ja n1, n2 > g(m), tad

|f(n1)-f(n2)|<2-m.

Fakts. Visi skaitļi, kuriem mēs protam izrēķināt patvaļīgi tālus decimālā pieraksta ciparus, ir konstruktīvi reāli skaitļi. Tādi ir visi racionālie skaitļi, sqrt(2), skaitlis e, pi, ln 2 utt.

Konstruktīvie kompleksie skaitļi - varam izmantot to pašu definīciju, tikai racionālo skaitļu vietā tad jāliek racionālie kompleksie skaitļi.

Teorēma. Visi algebriskie skaitļi ir konstruktīvi kompleksie skaitļi.

Fakts. Visi konstruktīvie skaitļi veido sanumurējamu kopu.

Konstruktīvists vārdu "kopa" te liktu pēdiņās. Bet mēs, tieši otrādi, ja vēlamies, varam secināt, ka "vairums reālo skaitļu ir nekonstruktīvi".

Tālāk aplūkosim dažas neparastas parādības, kas konstruktīvo matemātiku atšķir no klasiskās...

Špekera skaitlis

Ernst Specker, 1949. gadā.

Teorēma. Eksistē rekursīva racionālo skaitļu virkne, kas konverģē, bet kuras robeža nav konstruktīvs reāls skaitlis.

Pierādījums. Ņemam kādu rekursīvi sanumurējamu nerekursīvu naturālo skaitļu kopu S, un algoritmu, kas ģenerē tās elementus: a(0), a(1), s(2), ...

Definējam šādu rekursīvu racionālo skaitļu virkni: s(0)=0; s(n+1)=s(n)+2-a(n).

1. uzdevums. Pārliecinieties paši, ka šī virkne konverģē, un ka tās robeža ir mazāka par 2. Pieņemiet, ka šī robeža sakrīt ar kādu konstruktīvu reālo skaitli (f, g), un parādiet, ka tad jebkuram k Jūs varat noteikt, vai k pieder kopai S, t.i. ka S ir rekursīva kopa.

Pretruna. Teorēma pierādīta.

Vai dotais skaitlis ir vienāds ar nulli?

Teorēma. Neeksistē algoritms, kas par katru konstruktīvu reālu skaitli r=(f, g) var pateikt, vai r=0, vai nav.

Secinājums. Neeksistē algoritms, kas par katriem diviem konstruktīviem reāliem skaitļiem r, t var pateikt, vai r=t, vai nav.

Pierādījums. Ņemam kādu rekursīvi sanumurējamu nerekursīvu naturālo skaitļu kopu S, un algoritmu, kas ģenerē tās elementus: a(0), a(1), s(2), ...

Definējam šādu racionālo skaitļu matricu s(m, n). Tās m-tā rinda būs virkne, kas tiecas uz konstruktīvu reālu skaitli r(m), kurš būs nulle tad un tikai tad, ja m nepieder kopai S. Tas tad arī nozīmēs, ka neviens algoritms pēc dotā m nevarēs pateikt, r(m)=0 vai nav.

Rēķinām s(m, n). Ģenerējam S elementu virkni a(0), a(1), a(2), ... un paralēli definējam, n augot: s(m, n) = 2-n.

Pieņemsim, ka brīdī, kad n=N, virknē a(i) parādās skaitlis m. Tad n turpinot augt uz priekšu, mēs s(m, n) vairs nemainām, t.i. s(m, n)=2-N visiem n>=N.

Tātad, ja m pieder kopai S, tad r(m)>0. Un ja nepieder, tad r(m)=0. Teorēma pierādīta.

Joks? Jums liekas, ka visi r(m) ir racionāli skaitļi? Jā, bet tas nav konstruktīvs apgalvojums: pēc dotā m Jūs neprotat atrast veselus skaitļus (p, q), tādus, ka r(m)=p/q.

2. uzdevums. Parādiet, ka eksistē algoritms, kas par jebkuriem diviem konstruktīviem reāliem skaitļiem r, s, par kuriem ir zināms, ka r nav vienāds ar s, spēj pateikt: r<s vai r>s.

Konstruktīvās reālā mainīgā funkcijas

Ja konstruktīvi reāli skaitļi (krs) ir rekursīvu funkciju pāri (f, g), tad visur definēta konstruktīva reālā mainīgā funkcija ir rekursīva funkcija, kas katram pārim (f, g), kas uzdod krs, piekārto pāri (f', g'), kas arī uzdod krs.

Negaidīti:

Teorēma. Visur definētas konstruktīvas reālā mainīgā funkcijas ir nepārtrauktas (pat - vienmērīgi konstruktīvi nepārtrauktas).

Pierādījums ir diezgan sarežģīts. Bet ideja "kāpēc tā notiek" ir ļoti vienkārša: pieņemsim, ka konstruktīvai funkcijai h punktā x ir "lēciens", t.i. ja y<x, tad h(y)<a<h(x). Tātad, pietiekami precīzi izrēķinot h(z), mēs varam pateikt, z=x vai nav. Bet tas nav iespējams.

Teorēma par starpvērtībām

Klasiskās matemātikas teorēma. Ja h ir segmentā [0, 1] visur definēta nepārtraukta funkcija, kam h(0)=-1 un h(1)=1, tad eksistē x, 0<x<1, tāds, ka h(x)=0.

Konstruktīvajā matemātikā šo teorēmu pierādīt nevar:

Teorēma. Neeksistē algoritms, kas katrai konstruktīvai reālā mainīgā funkcijai h, kas ir definēta (un tātad - nepārtraukta) segmentā [0,1], un kam h(0)=-1 un h(1)=1, atrod x, 0<x<1, tādu, ka h(x)=0.

Pierādījums. Paņemsim S1, S2 - divas rekursīvi sanumurējamas rekursīvi neatdalāmas naturālu skaitļu kopas, un katram m definēsim funkciju hm, kas apmierina teorēmas nosacījumus. Beigās izrādīsies, ka ja m pieder kopai S1, tad funkcijai hm segmentā [0, 1] ir tikai sakne 1/3, bet ja m pieder S2, tad ir tikai sakne 2/3. No tā arī sekos, ka minētais algoritms neeksistē (jo izrēķinot dotajai hm sakni pietiekami precīzi, mēs varētu pateikt, ka m nepieder S1, vai ka m nepieder S2, kas nav iespējams).

Funkciju hm definējam kā funkciju virknes gmn robežu, kad n->oo. Ģenerējam kopas S1 elementu virkni a(0), a(1), a(2), ... un kopas S2 elementu virkni b(0), b(1), b(2), ..., paralēli definējam, n augot: gmn = funkcija, kas pie x=0 pieņem vērtību -1, tad līdz x=1/3 lineāri aug līdz vērtībai 0, no 1/3 līdz x=2/3 pieņem vērtību 0, un tālāk līdz x=1 lineāri aug līdz vērtībai 1. Pagaidām funkcija gmn nav atkarīga ne no m, ne no n.

Bet tiklīdz mēs konstatējam, ka skaitlis m parādījies virknē a(0), a(1), a(2), ... (t.i. m pieder kopai S1), tā funkciju gm,n+1 iegūstam, no gmn, pieskaitot tai 2-n (n ir tekošā n vērtība), un pārbīdot grafiku nedaudz pa labi, lai vienīgā sakne būtu 1/3. Un turpmāk, n augot, funkciju gmn vairs nemainām.

Līdzīgi rīkojamies, kad konstatējam, ka skaitlis m parādījies virknē b(0), b(1), b(2), ... (t.i. m pieder kopai S2), tad funkciju gm,n+1 iegūstam, no gmn, atņemot tai 2-n (n ir tekošā n vērtība), un pārbīdot grafiku nedaudz pa kreisi, lai vienīgā sakne būtu 2/3. Un turpmāk, n augot, funkciju gmn vairs nemainām.

3. uzdevums. Pārliecinieties, ka teorēma tiešām ir pierādīta.

Secinājums

Kā redzat, konstruktīvā matemātika iznāk sarežģītāka nekā mums pierastā klasiskā matemātika. Kāda tā izskatās, ja to attīsta līdz zināmai pilnībai, sk.

B. A. Kushner. Lectures on Constructive Mathematical Analysis. Amer. Math. Soc. 1985, 346 pp. (Latvijas bibliotēkās var dabūt šīs grāmatas oriģinālo krievu izdevumu.)

Sk. arī:

Constructive Mathematics. Frequently Asked Questions. University of Canterbury - Christchurch, New Zealand.

Matemātiķu vairākums konstruktīvo matemātiku neuzskata par nopietnu "pasākumu".

Intuicionistiskā loģika

Ja Jūs pārzināt parastās klasiskās loģikas aksiomas, tad varat jautāt, kādu daļu no šīs loģikas atzīst par labu intuicionisti un konstruktīvisti?

Sk. [2], kā arī:

V.Detlovs, K.Podnieks. Introduction to Mathematical Logic (Doc. Detlova 1964.gada grāmatas paplašināts angļu tulkojums.)

Par loģikas aksiomām sk. sadaļu 1.3.

Detlova izmantotās loģikas aksiomu sistēmas priekšrocība - tajā kā klasiskās loģikas aksioma tiek izmantots arī trešā izslēgtā likums Bv~B. Izrādās, ka tad intuicionistiskās loģikas aksiomu sistēma no klasiskās atšķiras TIKAI ar to, ka jāatmet trešā izslēgtā likums.

[2] un citās mācību grāmatās Bv~B vietā tiek kā aksioma tiek izmantots dubultās negācijas likums ~~B->B. Tas ļauj "ietaupīt" vienu aksiomu, jo likumu "no pretrunas seko jebkas" ~B->(B->C) var izvest no dubultās negācijas likuma. Detlova sistēmā ~B->(B->C) ir jāpieņem kā atsevišķa aksioma.

BET: ietaupot vienu aksiomu, mums nākas "locīties", definējot atšķirību starp klasisko in intuicionistisko loģiku: lai no pirmās iegūtu otro, dubultās negācijas likuma ~~B->B vietā jāliek likums "no pretrunas seko jebkas" ~B->(B->C). Jocīgi... kaut arī rezultāts iznāk tas pats, kas Detlova sistēmas gadījumā.

Markova princips

Konstruktīvisti pievieno intuicionistu loģikai vēl vienu aksiomu (no pārējām intuicionistu loģikas aksiomām to nevar izvest):

Markova princips. No Ax(B(x)v~B(x))&~Ax~B(x) var izvest ExB(x).

Pamatojums. Ja x vērtību apgabals ir naturālie skaitļi, tad Ax(B(x)v~B(x)) nozīmē, ka mums ir algoritms, kas nosaka, vai dotajai x vērtībai B(x) ir patiess vai nav, un tad, zinot, ka ~Ax~B(x), mēs varam vienkārši pārlasīt x vērtības vienu pēc otras, kamēr atrodam x, kam B(x) ir patiess. Tā mēs iegūstam konstruktīvu pierādījumu apgalvojumam ExB(x).

Sīkāk sk. [2].

Andrejs A. Markovs, vecākais, viņa vārdā saucas Markova ķēdes.

Andrejs A. Markovs, jaunākais (dēls), viņa vārdā saucas Markova princips un Markovas normālie algoritmi (Tūringa mašīnas ekvivalents - Detlova teorēma, Detlovs bija Markova aspirants 1950jos gados).

Kripkes semantika

Sauls Kripke, 1965.gadā.

Ja Jūs pārzināt parastās klasiskās loģikas interpretācijas un modeļus, tad Jums varētu būt interesanti aplūkot Kripkes izgudrotās struktūras, kurās intuicionistiskās loģikas aksiomas iznāk patiesas un pilnīgas.

Sk. [2] un Detlova-Podnieka grāmatas sadaļu 4.4.