May 11, 2014

Pikakurssi vanhan logiikan rajoista, rajoituksista ja rajoittuneisuudesta sekä uuden logiikan ‘ratkeamattomuudesta’: – ylipäätään koko logiikkapelin konstruktiivisesta kikkailusta, joka johtaa tautologiaan/kehämäisyyteen, ristiriitaan, kvanttorien 'inflaatioon' ja siten ratkeamattomuuteen

Ilmestynyt teoksessa: Kaisa Luoma, Erna Oesch & Risto Vilkko (eds.) Filosofisia tutkielmia – Philosophical Studies in honorem Leila Haaparanta, Acta Philosophica Tamperensia Vol. 4, Tampere University Press, Tampere, 2004.

Mitä uutta modernissa logiikassa?

Panu Raatikainen

Perinteisen aristoteelisen logiikan valtakausi kesti parisen tuhatta vuotta. Niinpä vielä Kant julisti, että aristoteelinen logiikka on lopullinen ja täydellinen logiikka. Sittemmin logiikka on kuitenkin kokenut melkoisen mullistuksen. Käsitykset siitä, mikä tässä muutoksessa oli olennaista ja milloin se todella tapahtui, vaihtelevat.

Yleinen näkemys on, että nykyaikaisen logiikan perinteisestä erottavia olennaisia piirteitä ovat kvanttoreiden käyttöönotto sekä perinteisen luonnolliseen kieleen perustuneen lauseanalyysin ja subjekti–predikaatti-analyysin korvaaminen matemaattisemmalla argumentti–funktio-analyysilla (ks. esim. Haaparanta 1998; vrt. Vilkko 2003). Niin pitkälle kuin se menee, tämä pitää tietysti paikkansa. Kuitenkin minusta tuntuu, että tämä kuvaus jättää jotain olennaista pois tai ainakin julkilausumattomaksi ja piileväksi. Koetan seuraavassa lyhyesti esittää, mikä oman näkemykseni mukaan tekee uudesta logiikasta radikaalisti erilaisen perinteiseen logiikkaan verrattuna.  

I

Tunnetusti Kant ajatteli, ettei geometrinen eikä aritmeettinen päättely voi edetä analyyttisesti tai loogisesti vaan edellyttää puhtaan intuition konstruktioita, siis synteettistä päättelyä. Michael Friedman (1985) on (osin Hintikan ajatuksia kehitellen) korostanut, että tämä on olennaisesti seurausta siitä, että Kant otti annettuna perinteisen aristoteelisen logiikan. Erityisesti, Kantin tuntema logiikka ei mitenkään pystynyt tavoittamaan tai esittämään äärettömyyttä. Sen välineistö ei voi pakottaa predikaatin ekstensiota äärettömäksi. Äärettömyys oli sen puitteissa esitettävä intuitiivisesti. Tämä logiikka on siten auttamattoman riittämätön toimimaan matemaattisen päättelyn teoriana — siksi Kantin oletus, että tarvitaan synteettistä intuitiota. Taustalla oletetun logiikan ominaisuuksilla on näin pitkälle meneviä filosofisia seurauksia.

Nykyaikaisessa logiikassa predikaatin ekstension pakottaminen äärettömäksi käy sen sijaan helposti. Se edellyttää välttämättä ainakin yhtä kaksipaikkaista predikaattia ja useampia sisäkkäisiä, toisistaan riippuvia kvanttoreita. Perinteinen aristoteelinen logiikka toisaalta rajoittui yksipaikkaisiin eli monadisiin predikaatteihin ja salli lauseen alussa vain yhden kvanttorin. Siksi se ei voi esittää äärettömyyttä. Tässä näen yhden tärkeän eron vanhan ja uuden logiikan välillä.   

II

Keskeinen logiikan ominaisuus on sen ratkeavuus tai ratkeamattomuus.1 Logiikka on ratkeava, jos on olemassa yleinen menetelmä, jolla pystytään täysin mekaanisesti, askel askeleelta sääntöjä seuraten ratkaisemaan äärellisessä ajassa mistä tahansa logiikan lauseesta, onko se loogisesti tosi (pätevä) vai ei. Muussa tapauksessa logiikka on ratkeamaton. 

Hilbert esitti aikanaan, että ”ratkaisuongelma” (Entscheidungsproblem) on matemaattisen logiikan pääongelma (Hilbert & Ackermann 1928). Hilbert oletti, että uusi logiikka on kokonaisuudessaan ratkeava. Tämän osoittaminen muodostikin keskeisen osan Hilbertin ohjelmaa, jonka piirissä monet tuon ajan parhaista loogikoista työskentelivät.

Toisaalta onnistuttiin rajoittumalla tiettyihin kvanttorirakenteen mukaan erityisiin lauseluokkiin osoittamaan, että kyseinen lauseluokka on ratkeava; tämä onnistui yhä monimutkaisemmille lauseluokille (ks. alla). Toisaalta logiikan yleinen ratkaisuongelma onnistuttiin palauttamaan tiettyihin kvanttorirakenteeltaan rajoitettuihin lausejoukkoihin (palautusluokkiin). Koko logiikan ratkeavuuden osoittaminen näytti näin olevan lähellä — lopulta kyse oli vain yhden kvanttorin erosta. Vuonna 1936 Church ja Turing kuitenkin osoittivat, että tämä kuilu on ylittämätön: yleinen ensimmäisen kertaluvun predikaattilogiikka on ratkeamaton (Church 1936a, b; Turing 1936).  

III

On mielenkiintoista katsoa hieman tarkemmin, missä ratkeavuuden ja ratkeamattomuuden raja tarkemmin ottaen kulkee, ja mihin se perustuu. Ensiksikin, kaikki seuraavat (ensimmäisen kertaluvun kielen ilman funktiosymboleja) lauseiden luokat ovat ratkeavia:
— lauseet, jotka sisältävät vain monadisia (yksipaikkaisia) predikaatteja (Löwenheim 1915);
— puhtaasti universaaliset lauseet (Bernays & Schönfinkel 1928);
— puhtaasti eksistentiaaliset lauseet  (Bernays & Schönfinkel 1928).

Edelleen, ensimmäisen kertaluvun logiikassa (ilman identiteettiä2) lauseluokat, joiden lauseiden kvanttorietuliite (prefiksi) on seuraavaa muotoa, ovat ratkeavia (toteutuvuuden suhteen):3
              ...  (Bernays & Schönfinkel 1928);
              ......  (Gödel 1932).

Kaikista edellä mainittuihin lauseluokkiin kuuluvista lauseista voidaan siis mekaanisesti ratkaista, ovatko ne toteutuvia vai ei. Sen sijaan lauseiden, jotka ovat seuraavia kvanttorimuotoja, luokat ovat jo ratkeamattomia:
                (Suranyi 1950);
                (Kahr, Moore & Wang 1962).

Itse asiassa viimeksi mainittujen lauseluokkien ratkeamattomuus pätee, vaikka sallittaisiin lauseiden sisältävän, yksipaikkaisten predikaattien ohella, vain yhden kaksipaikkaisen predikaatin (relaation).4 Molemmat viimeksi mainitut, ratkeamattomat lauseluokat ovat myös nk. palautusluokkia; koko yleisen predikaattilogiikan ratkaisuongelma voidaan palauttaa niihin.5 Ne siis tietyssä mielessä jo sisältävät koko yleisen predikaattilogiikan voiman. Askel ratkeavista lauseluokista niihin, mikä vaatii vain yhden kvanttorin lisää, merkitsee siis hyvin radikaalia siirtymää.

Ratkeamattomuuden yhteys kykyyn ilmaista äärettömyyttä on tässä läheinen: kaikkien em. ratkeavien lauseluokkien ratkeavuus perustuu niiden nk. äärellinen malli -ominaisuuteen (joskus myös sanotaan, että ne ovat ”äärellisesti kontrolloitavissa”); ts. luokan kaikille lauseille pätee seuraava ehto: jos lause on toteutuva, sillä on äärellinen malli. Jos siis lause ei ole loogisesti pätevä, sille voidaan aina mekaanisesti löytää äärellinen vastaesimerkki (tämähän ei päde yleisesti). Lauseluokat ovat ratkeavia, koska tämänmuotoiset lauseet eivät pysty takaamaan mallin äärettömyyttä.6 Ratkeamattomat luokat toisaalta sisältävät ”äärettömyysaksioomia” eli lauseita, joilla on vain äärettömiä malleja.

Perinteinen aristoteelinen logiikka sisältyy kokonaisuudessaan monadiseen predikaattilogiikkaan. Se on siis ratkeava. Nykyaikainen logiikka on sen sijaan ratkeamaton — ja kuten edellä on nähty, jo sen varsin yksinkertaiset osat ovat. Tässä näen toisen olemuksellisen eron vanhan ja uuden logiikan välillä.

Voidaan ehkä ajatella, että ratkeamattomuus on nykylogiikan heikkous tai puute. Itse asiassa se on kuitenkin logiikan riittävyyden välttämätön ehto: mikäli logiikka on ratkeava, se ei kykene esittämään edes alkeisaritmetiikassa esiintyviä päätelmiä. On siis varmasti parempi vain elää logiikan ratkeamattomuuden kanssa.  

IV

Äärettömän käsitteeseen epäilyksellä suhtautuva — ja heitä on — voi tietysti ajatella, että koko äärettömän mallin käsite on tarpeeton. Mitäpä jos vain unohdamme äärettömät mallit ja rajoitumme tarkastelemaan pelkästään äärellisiä malleja? Lauseen looginen totuus tai pätevyys voitaisiin tällöin tietysti määritellä lauseen totuutena kaikissa äärellisissä malleissa. Saataisiinko näin hallittavampi logiikka? Ei — päinvastoin!

Trakhtenbrotin lause (Trakhtenbrot 1950) sanoo, että näin määriteltyä äärellisesti pätevien lauseiden joukkoa ei voida aksiomatisoida — toisin sanoen lopputuloksena saatu logiikka on olennaisesti epätäydellinen; lisäksi sekin on ratkeamaton. Rajoittuminen äärellisiin malleihin johtaa siis vain hallitsemattomampaan tilanteeseen. Nykyisen vakiologiikkamme riittävyys, tai täydellisyys, perustuu siis oleellisesti valintaan kohdella äärellisiä ja äärettömiä malleja tasa-arvoisina. Pidän täydellisyyttä tyydyttävän logiikan keskeisenä vaatimuksena.  

V

Jotta logiikka pystyisi sisällyttämään itseensä matematiikassa käytetyt päättelyt, sen kielen on kyettävä esittämään äärettömyyden käsite. Tämä puolestaan edellyttää vähintään yhtä kaksipaikkaista relaatiota ja useampia sisäkkäisiä, toisistaan riippuvia kvanttoreita. Samat ehdot on täytettävä myös lauseluokan, jotta se olisi ratkeamaton (siihen tarvitaan vähintään kolme sisäkkäistä kvanttoria ja ainakin yksi kaksipaikkainen predikaatti).

Vasta nämä piirteet yhdessä antavat nykyaikaiselle logiikalle sen perinteistä logiikkaa olennaisesti suuremman voiman; kvanttorit ja funktio–argumentti-analyysi sinänsä, tai usempipaikkaiset predikaatit tai relaatiot sinänsä, eivät erikseen sitä tee. Kunnia kaikkien tarvittavien ainesten yhdistämisestä kuulunee Fregelle: siksi ajattelen itse hieman epätrendikkäästi, että moderni logiikka todellakin syntyi vasta 1879.  

Viitteet

1. Tärkeä logiikan ominaisuus on tietysti myös täydellisyys. Sekä perinteiselle että nykyaikaiselle (ensimmäisen kertaluvun) logiikalle on kuitenkin mahdollista esittää täydellinen päättelysääntö­järjestelmä, joten tässä ei ole mitään olennaista eroa näiden kahden välillä. 

2.  Identiteetin kanssa jo luokka  on ratkeamaton (Goldfarb 1984).

3. Merkintä ...  (tai ...) tarkoittaa, että mielivaltaisen pitkä äärellinen jono samaa kvanttoria on sallittu. 

4. luokka ... on ratkeamaton, vaikka lauseet eivät sisältäisi yhden kaksipaikkaisen predikaatin lisäksi mitään muita (edes yksipaikkaisia) predikaatteja.

5. Lauseluokka P on palautusluokka, jos mielivaltaiselle annetulle predikaattilogiikan lauseelle  voidaan mekaanisesti löytää luokkaan P kuuluva lause  siten, että  on loogisesti pätevä jos ja vain jos  on loogisesti pätevä.

6. Lauseluokka on ratkeava, jos sillä on äärellinen malli -ominaisuus (ts. se on äärellisesti kontrolloitavissa), mutta seuraussuhde ei välttämättä päde vastakkaiseen suuntaan. Luonnollisten kvanttorietuliitteen avulla luokiteltujen lauseluokkien joukossa kuitenkin tosia asiassa käy niin, että jokaisella ratkeavalla lauseluokalla on äärellinen malli -ominaisuus.   

Lähteet

Bernays, P. & M. Schönfinkel [1928] ”Zum Entscheidungsproblem der mathematischen Logik”, Mathematische Annalen 99, 401–419.
Church, A. [1936a] “An unsolvable problem of elementary number theory”, American Journal of Mathematics 58, 345–363.
Church, A. [1936b] “A note on the Entscheidungsproblem’. Journal of Symbolic Logic, 1, 40–41.
Friedman, M. [1985] “Kant’s theory of geometry”, Philosophical Review 94, 455–506.
Goldfarb, W. [1984] “The unsolvability of the Gödel class with identity”, Journal of Symbolic Logic 49, 1237–1252.
Gödel, K. [1932] “Ein spezialfall des Entscheidungsproblems der theoretischen Logik”, Ergebnisse eines Mathematischen Kolloquiums, vol. 2, 27–28.
Haaparanta, L. [1998] ”Moderni logiikka”, teoksessa P. Korkman & M. Yrjönsuuri (toim.) Filosofian historian kehityslinjoja, Helsinki: Gaudeamus, 383–399.
Hilbert, D. & W. Ackermann [1928] Grundzüge der theoretischen Logik, Berlin: Springer.
Kahr, A., E. Moore & H. Wang [1962] “Entscheidungsproblem reduced to  class”, Proceedings of the National Academy of Sciences of the U.S.A. 48, 364–377.
Löwenheim, L. [1915] “Über Möglichkeiten Relativkalkül”, Mathematische Annalen 76, 447–470.
Suranyi, J. [1950] “Contributions to the reduction theory of decision problem, second paper”, Acta Mathematica Academiae Scientarium Hungaricae, vol. 1, 261–270.
Trakhtenbrot, B. A. [1950] “Nevozmoznost’algorifma dla prblemy razresimosti na konecnyh klassah” (‘Impossibility of an Algorithm for the Decision Problem in Finite Classes’), Doklady Akademii Nauk SSSR 70, 569–572.
Turing, A.M. [1936] “On computable numbers, with an application to the Entscheidungs­problem”, Proceedings of the London Mathematical Society, series 2, 42 (1936-37), 230–265.
Vilkko, R. [2003] ”Immanuel Kant — logiikan kehityksen tärkeä taustavaikuttaja”, Ajatus 60, 121–136.
*

No comments: