Kirjoitin Gödelin ensimmäisestä epätäydellisyyslauseesta aiemmin. Koska teen oppimateriaalia aiheesta, perehdyn useampaan erilaiseen todistustekniikkaan asian tiimoilta. Mainitsin Gödel-numeroinnin aiemmin. Numerointeja voidaan tehdä monta, mutta ehkä helpoimmin hahmotettavan luin kirjasta A Course in Mathematical Logic. Siinä symbolinen esitys koodataan tekijöihinjakoon niin, että voimme koodata mielivaltainen määrä lukuja, y0,...,yn lukuun x niin, että x = p0y0 * ... *pnyn, missä pn on n:s alkuluku (p0 = 2). Tämä esitys on yksikäsitteinen, koska alkutekijöihin jako on yksikäsitteinen. n:s alkuluku voidaan ilmaista lukuteorian käsittein ensimmäisen kertaluvun kaavalla, joten mitään ongelmaa tässä ei ole.
Tätä esitystapaa noudattaen jokaiselle kaavalle voidaan antaa hyvinkin helposti numerointi. Hyvä johdanto epätäydellisyyslauseeseen on ns. Tarskin lause. Me voimme antaa aritmeettisille kaavoille numeroinnin, esimerkiksi niin, että vakiolle nolla annetaan numero 1. Numeroimme kaikki muuttujat juoksevalla numeroinnilla v1, v2... ja annamme muuttujalle vi numeroin 3i. Seuraajafunktio s() toimii niin, että kaavalle s(r) annetaan numero, joka on 2*3#r missä #r on r:n numerointi. Kaavalle r + t annetaan numero joka on 4*3#r*5#t, ja niin edelleen. Olennaista on, että numerointi on yksikäsitteinen kaikille kaavoille. esimerkiksi kaavalle v1 = 1 tulisi numeroinniksi 6750000.
Tarskin lause sanoo, että predikaatti T(x) joka on tosi kun x on numero jollekin todelle aritmeettiselle lauseelle, ei ole esitettävissä aritmetiikan avulla. Todistus perustuu ns diagonalisointiin. Siinä rakennetaan aritmeettisesti diagonaalisekvenssi d(x) joka käyttäytyy siten, että kun A on kaava, jossa on yksi vapaa muuttuja, ja #A on kaavan numero, niin d(#A) = #(A(#A)), eli d(#A) antaa sen kaavan numeron, joka saadaan kun kaavan parametriksi laitetaan kaavan oma numerointi. Esimerkiksi jos A on kaava "v1 = 1", niin d(6750000) arvoksi tulee kaavan "6750000 = 1" numero. (se on valtavan suuri..)
Jos T(x) olisi aritmeettisesti esitettävä (totuusarvoinen) funktio, meillä olisi kaava joka olisi tosi kun x on toden kaavan numero. Tällöin olisi, yhtä lailla, aritmeettisesti esitettävissä funktio !T(d(x)), eli meillä olisi kaava, joka olisi tosi silloin kun d(x) ei ole toden kaavan numero. Olkoon tämä kaava B.
Tällöin B(x) pätee tasan silloin kun T(x) on epätosi. Koska B olisi aritmeettinen kaava, sillä olisi numerointi. B(#B) olisi siis tosi tasan silloin kun T(d(#B)) olisi epätosi. Mutta kun T(d(#B)) on määritelmällisesti tosi silloin kun B(#B) on tosi, mikä johtaa ristiriitaan. Tämä ristiriita johtuu oletuksesta, että T(x) olisi esitettävissä aritmeettisesti; se ei siis voi olla. Aritmeettiset totuudet eivät siis ole aritmeettisia väittämiä!
Gödelin epätäydellisyyslause on tästä tavallaan hieman hienostelevaisempi versio. Siinä todistetaan, että jos meillä on konsistentti aksiomatisointi aritmetiikalle, niin voimme löytää aritmeettisesti toden kaavan, joka ei ole seuraus tästä aksiomatisoinnista; jokainen aksiomatisointi aritmeettisille totuuksille on epätäydellinen. Myös tämä perustuu diagonalisoinnille.
Aiemmin esittämäni versio epätäydellisyyslauseesta, siis siitä että on olemassa aritmeettisia tosiasioita joita ei voi todistaa, on tavallaan tämä esitettynä toisin. Siinä lähdetään oletuksesta, että aksiomat ja ja päättelysäännöt mumeroidaan, ja johdetaan väittämä "tälle lauseelle ei ole todistusta". Kyseinen lause siis ei voi seurata niistä aksiomista jotka on numeroitu. Se on kuitenkin yhteensopiva aksiomien kanssa, mikäli ne ovat konsistentit. Standardi aritmetiikka siis pysyy voimassa, vaikka lisäsisimme ko. lauseen aksiomien joukkoon. Tästä ei seuraa ristiriitaista aksiomajoukkoa, koska uusi aksioma on oikeastaan muotoa "Tälle lauseelle ei ole todistusta joukosta X lähtien", mutta lause itse ei tietystikään kuulu X:ään. Lisäämisen jälkeen jokainen aksioma on teoreema, tietenkin.
tiistai 29. lokakuuta 2013
perjantai 25. lokakuuta 2013
Toiset tasa-arvoisempia kuin toiset...
Aamulehden uutisen mukaan Suomi on maailman paras paikka naiselle elää. Suomi onkin BBC:n artikkelin mukaan sangen edistyksellinen useilla mittareilla. Täällä naisten hyvinvointiin panostetaan.
Pengoin hieman tuota sivustoa, ja keskityn tässä terveyteen. Kyseinen artikkeli nimittäin puhuu "Gender gap"-ilmiöstä. Korostan vielä Euroopan tilannetta.
Yksi terveysmittareista on "Health and survival", jossa mitataan tasa-arvoisuutta. Kiinnittäkää huomiota siihen, miten feminismin mallimaa Ruotsi on kartassa keltaisella - siis toiseksi huonompana - kun taas Venäjä on vaalean vihreällä. Asiaan saa valoa hieman, kun katsoo esimerkiksi eliniän odotetta.
Suomessa miehet kuolevat keskimäärin kuusi vuotta aiemmin kuin naiset. Venäjällä ero on peräti 12 vuotta, kun taas Kanadassa ja Ruotsissa (joissa tilaston mukaan on kehno tasa-arvo, uskoo ken tahtoo) ero on vain neljä vuotta. Ranskassa ero on 7 vuotta, joten se pärjää tässä hyvin.
Minä mietin vaan, että kun tämä on nyt saatu jo käännettyä selkeästi siihen, että naisten elämänlaatua näiden mittarien mukaan voidaan parantaa sillä, että miehet laitetaan kuolemaan nuorena (vrt. Venäjä), niin miksi enää puhutaan "tasa-arvosta"? Ja miksi siinä puhutaan "gender gap"-ilmiön vähäisyydestä, kun tosiasiassa mittareissa on osittain kyse siitä, että *suurempi* gäppi on parempi?
Elämme kummallisessa maailmassa, kun minun täytyy jotenkin erikseen sanoa, että kannatan kyllä tasa-arvoa, mutta kun tämä ei ole sitä. Tämä on feminismiä, eikä sillä ole mitään tekemistä tasa-arvon kanssa.
Pengoin hieman tuota sivustoa, ja keskityn tässä terveyteen. Kyseinen artikkeli nimittäin puhuu "Gender gap"-ilmiöstä. Korostan vielä Euroopan tilannetta.
Suomessa miehet kuolevat keskimäärin kuusi vuotta aiemmin kuin naiset. Venäjällä ero on peräti 12 vuotta, kun taas Kanadassa ja Ruotsissa (joissa tilaston mukaan on kehno tasa-arvo, uskoo ken tahtoo) ero on vain neljä vuotta. Ranskassa ero on 7 vuotta, joten se pärjää tässä hyvin.
Minä mietin vaan, että kun tämä on nyt saatu jo käännettyä selkeästi siihen, että naisten elämänlaatua näiden mittarien mukaan voidaan parantaa sillä, että miehet laitetaan kuolemaan nuorena (vrt. Venäjä), niin miksi enää puhutaan "tasa-arvosta"? Ja miksi siinä puhutaan "gender gap"-ilmiön vähäisyydestä, kun tosiasiassa mittareissa on osittain kyse siitä, että *suurempi* gäppi on parempi?
Elämme kummallisessa maailmassa, kun minun täytyy jotenkin erikseen sanoa, että kannatan kyllä tasa-arvoa, mutta kun tämä ei ole sitä. Tämä on feminismiä, eikä sillä ole mitään tekemistä tasa-arvon kanssa.
torstai 24. lokakuuta 2013
Supercell ja kurkunpää.
Menetin ääneni taas kerran. Jostain kumman syystä sairastun Suomessa vuosittain kurkunpään tulehdukseen. En juuri saa muita flunssan oireita kuin hyvin lievinä, mutta ääneni menetän hyvin herkästi. Tämän vuoksi en voi siis pitää luentoja tänään. Mikä on sääli, sillä olisin juuri päässyt mielenkiintoiseen aiheeseen, aksiomatisoinnin ja boolen algebrojen suhteeseen. Tämän vuoksi olisin sitten päässyt ensi viikolla käsittelemään malliteoriaa jo tiistaina.
Viime viikolla uutisiin nousi SuperCell-kauppa, kun suomalainen pelifirma myi puolet omistuksestaan japanilaisille. Asiaan suhtauduttiin pääsääntöisesti positiivisesti, mutta muutamissa kirjoituksissa tätä positiivisuutta pyrittiin hieman painamaan alaspäin toteamalla että eihän peliala työllistä paljoakaan. Tämä sai minut miettimään. Miksi me suomalaisina haluaisimme, että jokin kauppa nimenomaan työllistää?
Jos ajattelen omaa perhettäni - ja älkää vielä syyttäkö kategoriavirheestä, otan tämän nyt vain esimerkkinä - ja minulla on autotallissa rakentamani hilavitkutin, ja tämän lisäksi minulla on lapio. Voin valita kahdesta strategiasta: joko myyn hilavitkuttimen jollekin ja saan siitä 50 000 euroa, joka maksetaan minulle osamaksulla 500 euroa viikossa. Vaihtoehtoisesti otan lapion ja menen kaivamaan ojaa 500 euron viikkopalkalla pariksi vuodeksi. Tässä esimerkissä on ilmeistä, että perheeni hyvinvointi ei todellakaan ole jälkimmäisessä tilanteessa parempi. Saan palkkaa saman verran parille vuodelle kuin hilavitkuttimen myynnistä, mutta sen lisäksi minun on kaivettava ojaa selkä vääränä. Tässä mikroesimerkissäni siis mikään "työllistävyys" ei todellakaan ole argumentti. Jos joku sanoisi minulle hilavitkuttimen myynnistä, että se oli huono valinta, parempi olisi ollut mennä kaivamaan ojaa, kun se työllistää, niin oikeutetusti pitäisin tätä aivan pöhkönä.
Perheen sisällä tietystikään ei ole mitään ongelmaa tulonjaon suhteen. Hilavitkuttimen myyntitulot ovat samalla lailla meidän käytettävissämme kuin lapiointitulotkin, koska saamme rahat yhtenä yksikkönä. Kansantalouden tasolla on tietenkin toisin. Se, että Supercellin omistajat saavat miljoonia, on heille hyväksi, mutta minä en kostu siitä kovinkaan paljoa. Jos taas Ojankaivajat OY tekee miljardilla vuoden ojankaivuudiilin Japaniin, niin sinne voidaan pistää 40 000 lapiomiestä, ja jokainen heistä saa 500 euroa viikossa, sensijaan että meillä on kourallinen miljonäärejä. Verotus tasaa tätä efektia tietysti huomattavasti, koska veroilla kustannetaan vaikka kuinka paljon työtä, opettajia, sairaanhoitajia jne, mutta karsastan tätä argumenttia, koska se perustuu ajatukselle että ihmisten ensisijainen tehtävä on maksaa veroja, eikä esimerkiksi, you know, elää omaa elämäänsä.
Mutta katsotaanpa kansantaloutta tarkemmin. Sivuutan tässä sen, että Supercellin Paananen on ilmoittanut investoivansa saamansa rahat Suomeen. Jos miljardi menee 20 ihmiselle (sanotaan), pikemminkin kuin 40 000 ihmiselle, niin miten käy utiliteetin noin yleensä? Ensinnäkin, on selvää, että 40 000 työmiestä vuoden töissä, tienaamassa 25 000 euroa (ja huomatkaa, tässä itse luvuilla on kovin vähän merkitystä, ne voivat olla toisetkin, kunhan käytän tätä argumenttina ja esimerkkinä) per pää, tuovat rahaa omiin koteihinsa niin, että näissä sitten voidaan kuluttaa tuon verran. Kuitenkin, jos oletamme että markkinat toimivat edes joten kuten, niin näiden työntekijöiden työllisyys vaihtoehtoisessa tilanteessa ei ole 0%, vaan nämä marginaalilla työllistetyt ovat pois jostain muusta työstä joka kotimaassa jää tekemättä. Ojat kaivetaan Japaniin, eikä Suomeen. Koska kaupat syntyivät, niin ilmeisesti Suomessa ei ole kysyntää ojille miljardin arvosta, tai siis, jotta miljardilla ostettaisiin ojia, niitä pitäisi tehdä enemmän, eli siis niistä saisi vähemmän palkkaa.
Fiksataan nyt jokin prosentti tälle joustolle ja sanotaan että se on puolet. Siis, ceteris paribus, oletataan että 25% näistä kavereista olisi kaivelemassa ojia Suomessa jos ei tulisi kauppoja. Suomeen siis tehtäisiin 250 miljoonalla ojia. Koska parhaat kaivajat ovat Japanissa kaivelemassa, ojia tehtäneen vähemmän, mutta oletan yksinkertaisuuden vuoksi, että ne jäävät tekemättä. Koska palkanmaksu on vain varallisuuden siirtoa, ja vain ne itse tehdyt ojat ovat utiliteettia, niin Suomeen syntyy ojankaivuuskenaariossa 250 miljoonalla vähemmän hyötyä. Rahaa tosin tulee miljardi, joten netto on - olettaen että rahalla hankitaan lopulta jotain ulkomailta - 750 miljoonaa. Tulonjaollinen aspekti koskeekin siis vain 30 000 ihmistä.
Puhumattakaan sitten siitä, kuinka paljon tulonjaollista hyötyä on siitä, kun ne miljardin tulot investoidaan ja kulutetaan kotimaassa. Tällöin ne lapiomiehet pääsevät kaivelemaan ojia. Eikä tarvitse pistää koko sitä 750 miljoonaa, että päästään tasoihin, koska ne lapiomiehet eivät joudu tekemään töitä japanilaisille, vaan suomalaisille.
Ei työllistäminen siis ole mikään erityinen "hyöty" missään muussa mielessä kuin että se levittää hyvinvoinnin vähän laajemmalle. Ja niille joiden mielestä julkinen sektori loputtomine veroineen on hyve numero 1, muistuttaisin että kaupoista maksetaan kyllä vero, ja lisäksi maksetaan kaikesta siitä, mitä sillä sisään tulleella rahalla ostetaan, ja kotimaassa työllistäminen on helpompaa kotimaisiin tarpeisiin jos se rahaa tuottava kauppa ei työllistä niin paljon. Tässä kohtaa Wahlroos osui harhaan. Se, mitä vähemmän vienti työllistää, sen parempi, ceteris paribus.
Viime viikolla uutisiin nousi SuperCell-kauppa, kun suomalainen pelifirma myi puolet omistuksestaan japanilaisille. Asiaan suhtauduttiin pääsääntöisesti positiivisesti, mutta muutamissa kirjoituksissa tätä positiivisuutta pyrittiin hieman painamaan alaspäin toteamalla että eihän peliala työllistä paljoakaan. Tämä sai minut miettimään. Miksi me suomalaisina haluaisimme, että jokin kauppa nimenomaan työllistää?
Jos ajattelen omaa perhettäni - ja älkää vielä syyttäkö kategoriavirheestä, otan tämän nyt vain esimerkkinä - ja minulla on autotallissa rakentamani hilavitkutin, ja tämän lisäksi minulla on lapio. Voin valita kahdesta strategiasta: joko myyn hilavitkuttimen jollekin ja saan siitä 50 000 euroa, joka maksetaan minulle osamaksulla 500 euroa viikossa. Vaihtoehtoisesti otan lapion ja menen kaivamaan ojaa 500 euron viikkopalkalla pariksi vuodeksi. Tässä esimerkissä on ilmeistä, että perheeni hyvinvointi ei todellakaan ole jälkimmäisessä tilanteessa parempi. Saan palkkaa saman verran parille vuodelle kuin hilavitkuttimen myynnistä, mutta sen lisäksi minun on kaivettava ojaa selkä vääränä. Tässä mikroesimerkissäni siis mikään "työllistävyys" ei todellakaan ole argumentti. Jos joku sanoisi minulle hilavitkuttimen myynnistä, että se oli huono valinta, parempi olisi ollut mennä kaivamaan ojaa, kun se työllistää, niin oikeutetusti pitäisin tätä aivan pöhkönä.
Perheen sisällä tietystikään ei ole mitään ongelmaa tulonjaon suhteen. Hilavitkuttimen myyntitulot ovat samalla lailla meidän käytettävissämme kuin lapiointitulotkin, koska saamme rahat yhtenä yksikkönä. Kansantalouden tasolla on tietenkin toisin. Se, että Supercellin omistajat saavat miljoonia, on heille hyväksi, mutta minä en kostu siitä kovinkaan paljoa. Jos taas Ojankaivajat OY tekee miljardilla vuoden ojankaivuudiilin Japaniin, niin sinne voidaan pistää 40 000 lapiomiestä, ja jokainen heistä saa 500 euroa viikossa, sensijaan että meillä on kourallinen miljonäärejä. Verotus tasaa tätä efektia tietysti huomattavasti, koska veroilla kustannetaan vaikka kuinka paljon työtä, opettajia, sairaanhoitajia jne, mutta karsastan tätä argumenttia, koska se perustuu ajatukselle että ihmisten ensisijainen tehtävä on maksaa veroja, eikä esimerkiksi, you know, elää omaa elämäänsä.
Mutta katsotaanpa kansantaloutta tarkemmin. Sivuutan tässä sen, että Supercellin Paananen on ilmoittanut investoivansa saamansa rahat Suomeen. Jos miljardi menee 20 ihmiselle (sanotaan), pikemminkin kuin 40 000 ihmiselle, niin miten käy utiliteetin noin yleensä? Ensinnäkin, on selvää, että 40 000 työmiestä vuoden töissä, tienaamassa 25 000 euroa (ja huomatkaa, tässä itse luvuilla on kovin vähän merkitystä, ne voivat olla toisetkin, kunhan käytän tätä argumenttina ja esimerkkinä) per pää, tuovat rahaa omiin koteihinsa niin, että näissä sitten voidaan kuluttaa tuon verran. Kuitenkin, jos oletamme että markkinat toimivat edes joten kuten, niin näiden työntekijöiden työllisyys vaihtoehtoisessa tilanteessa ei ole 0%, vaan nämä marginaalilla työllistetyt ovat pois jostain muusta työstä joka kotimaassa jää tekemättä. Ojat kaivetaan Japaniin, eikä Suomeen. Koska kaupat syntyivät, niin ilmeisesti Suomessa ei ole kysyntää ojille miljardin arvosta, tai siis, jotta miljardilla ostettaisiin ojia, niitä pitäisi tehdä enemmän, eli siis niistä saisi vähemmän palkkaa.
Fiksataan nyt jokin prosentti tälle joustolle ja sanotaan että se on puolet. Siis, ceteris paribus, oletataan että 25% näistä kavereista olisi kaivelemassa ojia Suomessa jos ei tulisi kauppoja. Suomeen siis tehtäisiin 250 miljoonalla ojia. Koska parhaat kaivajat ovat Japanissa kaivelemassa, ojia tehtäneen vähemmän, mutta oletan yksinkertaisuuden vuoksi, että ne jäävät tekemättä. Koska palkanmaksu on vain varallisuuden siirtoa, ja vain ne itse tehdyt ojat ovat utiliteettia, niin Suomeen syntyy ojankaivuuskenaariossa 250 miljoonalla vähemmän hyötyä. Rahaa tosin tulee miljardi, joten netto on - olettaen että rahalla hankitaan lopulta jotain ulkomailta - 750 miljoonaa. Tulonjaollinen aspekti koskeekin siis vain 30 000 ihmistä.
Puhumattakaan sitten siitä, kuinka paljon tulonjaollista hyötyä on siitä, kun ne miljardin tulot investoidaan ja kulutetaan kotimaassa. Tällöin ne lapiomiehet pääsevät kaivelemaan ojia. Eikä tarvitse pistää koko sitä 750 miljoonaa, että päästään tasoihin, koska ne lapiomiehet eivät joudu tekemään töitä japanilaisille, vaan suomalaisille.
Ei työllistäminen siis ole mikään erityinen "hyöty" missään muussa mielessä kuin että se levittää hyvinvoinnin vähän laajemmalle. Ja niille joiden mielestä julkinen sektori loputtomine veroineen on hyve numero 1, muistuttaisin että kaupoista maksetaan kyllä vero, ja lisäksi maksetaan kaikesta siitä, mitä sillä sisään tulleella rahalla ostetaan, ja kotimaassa työllistäminen on helpompaa kotimaisiin tarpeisiin jos se rahaa tuottava kauppa ei työllistä niin paljon. Tässä kohtaa Wahlroos osui harhaan. Se, mitä vähemmän vienti työllistää, sen parempi, ceteris paribus.
perjantai 18. lokakuuta 2013
Boolen algebrat
Lähdetään tilanteesta, jossa meillä on osittaisjärjestetty joukko, pari (S, ≤), joka on samalla ns. hila. Hilalla tarkoitetaan rakennetta, jossa osittaisjärjestyksen suhteen voidaan löytää kullekin alkioparille pienin yläraja (sup) ja suurin alaraja (inf). Näitä voidaan merkitä useammallakin symbolilla, mutta usein käytetään merkintöjä x ∨ y ja x ∧ y. Hila on täydellinen, jos jokaisella osajoukolla on sup ja inf, ja näinollen koko joukolla on suurin ja pienin alkio. Näitä on tapana merkitä symboleilla 1 ja 0, joskus myös T ja ⊥. (Tarkkaanottaen ensimmäinen ei ole "T", mutten löytänyt symbolia). Täydellinen hila on komplementoitu, jos jokaiselle alkiolle on komplementti, x*, siten että x ∨ x* = 1 ja x ∧ x* = 0. Hila on distributiivinen, jos x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). Komplementoitu distributiivinen hila on Boolen algebra.
Jos meillä on ensimmäisen kertaluvun logiikka, sen kaavojen ekvivalenssiluokista voidaan muodostaa boolen algebra, jossa x ∨ y tarkoittaa kaavojen x ja y disjunktiota, x ∧ y konjunktiota ja x* negaatiota. Lisäksi pätee että x ≤ y jos ja vain jos x* ∨ y = 1. Tämä voidaan todistaa ominaisuuksista teoreemana. Operaatiota x* ∨ y merkitään logiikassa tavallisesti implikaationuolella.
Algebrallinen lähestymistapa kohtaa topologian myös logiikan kohdalla. Filtteri (suomeksi "suodatin", mutten käytä tätä sanaa koska mielestäni se ei ole sopiva tässä kohtaa) voidaan ajatella algebran osajoukoksi, jolla on muutama ominaisuus: Se ei sisällä alkiota 0, ja jos x ja y kuuluvat filtteriin, x ∧ y kuuluu filtteriin, ja se on ylöspäin suljettu, eli jos x on filtterissä, niin jokainen y siten että x ≤ y on myös filtterissä. Filtterit vastaavat logiikan struktuureina konsistentteja teorioita. Maksimaalinen filtteri on filtteri, jota ei voi kasvattaa. Maksimaalista filtteriä nimitetään myös ultrafilttereiksi.
Tärkeä algebrassa käytettävä kuvaus on homomorfismi. Kuvaus f algebralta X algebralle Y on homomorfismi, jos f(x * y) = f(x) * f(y) kaikille algebran operaatioille. Homomorfismin ja filtterin suhde on mielenkiintoinen. Nimittäin, jos f on homomorfismi X:ltä Y:lle, niin alkion 1 alkukuva X:ssä on filtteri. Jos homomorfismi on 2-arvoinen (eli saa vain arvoja 0 ja 1), niin alkukuva on ultrafiltteri.
Kun filtteri vastaa teoriaa, niin ultrafiltteri vastaa täydellistä teoriaa, siis teoriaa, joka määrittää jokaisen logiikan kaavan totuusarvon.
Filtterin F osajoukko X on kanta, jos jokaiselle filtterin alkiolle löytyy alaraja X:stä. Kanta vastaa aksiomatisointia.
Jos meillä on ensimmäisen kertaluvun logiikka, sen kaavojen ekvivalenssiluokista voidaan muodostaa boolen algebra, jossa x ∨ y tarkoittaa kaavojen x ja y disjunktiota, x ∧ y konjunktiota ja x* negaatiota. Lisäksi pätee että x ≤ y jos ja vain jos x* ∨ y = 1. Tämä voidaan todistaa ominaisuuksista teoreemana. Operaatiota x* ∨ y merkitään logiikassa tavallisesti implikaationuolella.
Algebrallinen lähestymistapa kohtaa topologian myös logiikan kohdalla. Filtteri (suomeksi "suodatin", mutten käytä tätä sanaa koska mielestäni se ei ole sopiva tässä kohtaa) voidaan ajatella algebran osajoukoksi, jolla on muutama ominaisuus: Se ei sisällä alkiota 0, ja jos x ja y kuuluvat filtteriin, x ∧ y kuuluu filtteriin, ja se on ylöspäin suljettu, eli jos x on filtterissä, niin jokainen y siten että x ≤ y on myös filtterissä. Filtterit vastaavat logiikan struktuureina konsistentteja teorioita. Maksimaalinen filtteri on filtteri, jota ei voi kasvattaa. Maksimaalista filtteriä nimitetään myös ultrafilttereiksi.
Tärkeä algebrassa käytettävä kuvaus on homomorfismi. Kuvaus f algebralta X algebralle Y on homomorfismi, jos f(x * y) = f(x) * f(y) kaikille algebran operaatioille. Homomorfismin ja filtterin suhde on mielenkiintoinen. Nimittäin, jos f on homomorfismi X:ltä Y:lle, niin alkion 1 alkukuva X:ssä on filtteri. Jos homomorfismi on 2-arvoinen (eli saa vain arvoja 0 ja 1), niin alkukuva on ultrafiltteri.
Kun filtteri vastaa teoriaa, niin ultrafiltteri vastaa täydellistä teoriaa, siis teoriaa, joka määrittää jokaisen logiikan kaavan totuusarvon.
Filtterin F osajoukko X on kanta, jos jokaiselle filtterin alkiolle löytyy alaraja X:stä. Kanta vastaa aksiomatisointia.
tiistai 15. lokakuuta 2013
Epätäydellisyys
Kuuluisia Gödelin epätäydellisyyslauseita on kaksi. Ensimmäinen koskee formaalin todistuksen ja "totuuden" suhdetta ja toinen koskee konsistenssin ja epäkonsistenssin todistettavuutta. Käsittelen tässä lähinnä ensimmäistä, mutta mainitsen myös toisen.
Jotta Gödelin lause voidaan ymmärtää, pitää ensin määritellä ns Gödel-numerointi. Oletetaan että meillä on ensimmäisen kertaluvun kieli, siis ensimmäisen kertaluvun predikaattilogiikka ja sillä esitetyt kaavat. Oletamme tässä yksinkertaisuuden vuoksi että käytössämme on yhtäsuuruus (=) ja funktiosymbolit "+", "*" ja "s", missä "s(x)" tarkoittaa samaa kuin "x:stä seuraava". Lisäksi voimme kvantifioida muuttujia - muuttujat ovat kotoisin numeroituvasta joukosta, esimerkiksi x, x', x'', jne. Vakioita on yksi, "a", ja sen tulkinta fiksataan niin, että se on tutummin nolla.
Gödel-numerointi tarkoittaa sitä, että annamme jokaiselle logiikan kielessä esiintyvälle symbolille - muuttujille, vakioille, funktiosymboleille, kvanttoreille, sulkumerkeille ja välimerkeillä - oman numeron. Varaamme lisäksi numeroita erilaisille yhdistelmämerkeille; voimme tehdä tämän "helposti" koska numeroitahan on äärettömästi. Täytyy vain pitää tarkkaan huolta, että jokaisella luvulla on yksikäsitteinen tulkinta.
En aio esittää varsinaista Gödel-numerointia tässä, mutta numerointi voidaan tehdä siten, että jokaiselle syntaktisesti oikein kirjoitetulle kaavalle, tai kaavojen sekvenssille saadaan uniikki luku, jonka tulkinta on yksikäsitteinen. Yksi mahdollinen numerointi löytyy Wikipedian artikkelista.
Lisäksi otamme lähtökohdaksi jonkin täydellisen 1-kertaluvun päättelyjärjestelmän. Esimerkki tällaisesta on vaikkapa Hilbertin järjestelmä. Ei ole olennaista, mikä tällainen järkestelmä on, kunhan se on täydellinen - eli jokainen tautologia predikaattilogiikassa voidaan sillä todistaa - ja äärellinen. Tällaisen järjestelmän säännöille voidaan siten antaa omat numeronsa, ja voimme näiden numeroiden avulla määritellä relaatio R(x,y) joka pätee tasan silloin kun x koodaa jonkin päättelyn niin, että y on laillinen seuraava askel tässä päättelyssä. Tällä tavoin saamme itseasiassa relaation joka sanoo, että luku y koodaa tietyn väittämän logiikassa ja x koodaa sen todistuksen, käyttäen pelkästään alkeellista aritmetiikkaa.
Voimme tunnistaa tällä järjestelmällä mielivaltaisen kaavan F joka on laillisesti kirjoitettu ja jossa on yksi vapaa muuttuja; vapaa muuttuja on osa kaavaa. joten jos annamme sille jonkin tietyn arvon, esimerkiksi 5, niin saamme toisen kaavan, F(5). Kaavan itsensä numeroa merkitsemme vaikkapa #F, ja tietysti #F on eri numero kuin #F(5).
Nyt predikaattio R(n,#F(5)) on tosi tasan silloin kun n on koodaus F(5):n todistukselle. Tarkastellaan väittämää R(n,#(F(#F)), joka sanoo, että n on koodaus sille todistukselle, joka todistaa että F(#F) pätee. Jokaisella tällaisella kaavalla on myös hyvinmääritelty yksikäsitteinen Gödel-numero.
Tämän jälkeen tarkastellaan kaavaa P(#F) joka sanoo että "Ei ole olemassa x:ää niin että R(x, #(F(#F))". pahoittelen loogisten symbolien puutetta, mutta ne on työlästä lisätä. Joka tapauksessa, koska tällekin kaavalle on Gödel-numerointi, se on ihan hyvin määritelty kaava.
Ja nyt se kikka: Mikä onkaan P(#P):n totuusarvo? Se nimittääin sanoo, että ei löydy x:ää niin, että R(x,#P(#P)) pitäisi paikkaansa. Tämä tarkoittaisi siis, että ei ole olemassa sellaista numeroa, joka koodaisi P(#P):n todistuksen.
Tämä predikaatti on aivan hyvinmääritelty. Se on väittämä joka joko pitää paikkansa tai sitten ei pidä. Jos se ei pidä paikkaansa, niin luonnollisista luvuista löytyisi sellainen alkio joka koodaisi väittämän todistuksen. Tiedämme kuitenkin, että esimerkiksi Hilbertin järjestelmä (tai mikä ikinä äärellinen päättelyjärjestelmä meillä onkaan käytössä) voi todistaa vain tosia väittämiä. Joten väittämälle ei voi olla todistusta.
Gödelin - ja kanoninen tulkinta ylipäänsä - tälle lauseelle on, että on olemassa aritmeettisia "totuuksia" joita ei voi todistaa. Tämä on todistusteoreettinen tulos; me emme voi todistaa että P(#P) on tosi kaikissa aritmetiikan malleissa. Se on selvästi tosi siinä mallissa jonka me yleensä ymmärrämme luonnollisiksi luvuiksi, ja joista Gödel-numerotkin olemme poimineet. Sensijaan se ei ole tosi kaikissa malleissa. Jos se nimittäin olisi tosi kaikissa malleissa, niin se olisi tautologia, ja me tiedämme, että kaikki tautologiat voidaan todistaa. On siis mahdollista luoda aritmetiikkajärjestelmä, jossa tämä väittämä on todistettavissa. Se on kuitenkin erilainen kuin se, jonka ominaisuuksiin nojaamme kun esitämme tämän todistuksen.
Tietojenkäsittelyllinen näkökulma ensimmäiseen epätäydellisyyslauseeseen on, että ei voida esittää sellaista algoritmia, joka tulostaisi ulos paikkansapitäviä aritmeettisiä väittämiä niin, että jokainen tosi väittämä tulee lopulta ulos, mutta ei yhtään epätotta väittämää. Tämä näkökulma tarjoaa lyhyemmän ja - joidenkin mielestä - ymmärrettävämmän tuloksen: Jokaiselle syntaktisesti erilaiselle kaavalle voidaan antaa numero, ja tästä johdetaan muutamalla tempulla ns. Berryn paradoksi. Berryn paradoksi menee jotenkin niin, että postuloidaan "Pienin luonnollinen luku, jota ei voi määritellä alle 11 sanalla", mikä itsessään on määritelmä joka on ristiriidassa itsensä kanssa; tietokoneohjelmasta joka tuottaa kaikki aritmeettiset totuudet, saadaan johdettua samantapainen paradoksi.
Toinen epätäydellisyyslause on samansukuinen, mutta siinä puhutaan aksioomajärjestelmän konsistenssista. Konsistenssilla tarkoitetaan sitä, että aksiomien joukosta ei voida löytää ristiriitoja, eli ei voida yhtä aikaa todistaa jotakin väittämää ja sen negaatiota. Gödel rakentaa tämän tuloksen samaan tapaan kuin ensimmäisen epätäydellisyyslauseenkin, mutta tämän lisäksi tarvitaan hyvin monimutkainen konstruktio jolla ilmaistaan konsistenssiväittämä. Konsistenssiväittämä on jotakuinkin se että "Ei ole olemassa toditusta epätodelle väittämälle". Konsistenssiväittämän todistus itsessään johtaa tilanteeseen, jossa samalla todistetaan ristiriita.
Jotta Gödelin lause voidaan ymmärtää, pitää ensin määritellä ns Gödel-numerointi. Oletetaan että meillä on ensimmäisen kertaluvun kieli, siis ensimmäisen kertaluvun predikaattilogiikka ja sillä esitetyt kaavat. Oletamme tässä yksinkertaisuuden vuoksi että käytössämme on yhtäsuuruus (=) ja funktiosymbolit "+", "*" ja "s", missä "s(x)" tarkoittaa samaa kuin "x:stä seuraava". Lisäksi voimme kvantifioida muuttujia - muuttujat ovat kotoisin numeroituvasta joukosta, esimerkiksi x, x', x'', jne. Vakioita on yksi, "a", ja sen tulkinta fiksataan niin, että se on tutummin nolla.
Gödel-numerointi tarkoittaa sitä, että annamme jokaiselle logiikan kielessä esiintyvälle symbolille - muuttujille, vakioille, funktiosymboleille, kvanttoreille, sulkumerkeille ja välimerkeillä - oman numeron. Varaamme lisäksi numeroita erilaisille yhdistelmämerkeille; voimme tehdä tämän "helposti" koska numeroitahan on äärettömästi. Täytyy vain pitää tarkkaan huolta, että jokaisella luvulla on yksikäsitteinen tulkinta.
En aio esittää varsinaista Gödel-numerointia tässä, mutta numerointi voidaan tehdä siten, että jokaiselle syntaktisesti oikein kirjoitetulle kaavalle, tai kaavojen sekvenssille saadaan uniikki luku, jonka tulkinta on yksikäsitteinen. Yksi mahdollinen numerointi löytyy Wikipedian artikkelista.
Lisäksi otamme lähtökohdaksi jonkin täydellisen 1-kertaluvun päättelyjärjestelmän. Esimerkki tällaisesta on vaikkapa Hilbertin järjestelmä. Ei ole olennaista, mikä tällainen järkestelmä on, kunhan se on täydellinen - eli jokainen tautologia predikaattilogiikassa voidaan sillä todistaa - ja äärellinen. Tällaisen järjestelmän säännöille voidaan siten antaa omat numeronsa, ja voimme näiden numeroiden avulla määritellä relaatio R(x,y) joka pätee tasan silloin kun x koodaa jonkin päättelyn niin, että y on laillinen seuraava askel tässä päättelyssä. Tällä tavoin saamme itseasiassa relaation joka sanoo, että luku y koodaa tietyn väittämän logiikassa ja x koodaa sen todistuksen, käyttäen pelkästään alkeellista aritmetiikkaa.
Voimme tunnistaa tällä järjestelmällä mielivaltaisen kaavan F joka on laillisesti kirjoitettu ja jossa on yksi vapaa muuttuja; vapaa muuttuja on osa kaavaa. joten jos annamme sille jonkin tietyn arvon, esimerkiksi 5, niin saamme toisen kaavan, F(5). Kaavan itsensä numeroa merkitsemme vaikkapa #F, ja tietysti #F on eri numero kuin #F(5).
Nyt predikaattio R(n,#F(5)) on tosi tasan silloin kun n on koodaus F(5):n todistukselle. Tarkastellaan väittämää R(n,#(F(#F)), joka sanoo, että n on koodaus sille todistukselle, joka todistaa että F(#F) pätee. Jokaisella tällaisella kaavalla on myös hyvinmääritelty yksikäsitteinen Gödel-numero.
Tämän jälkeen tarkastellaan kaavaa P(#F) joka sanoo että "Ei ole olemassa x:ää niin että R(x, #(F(#F))". pahoittelen loogisten symbolien puutetta, mutta ne on työlästä lisätä. Joka tapauksessa, koska tällekin kaavalle on Gödel-numerointi, se on ihan hyvin määritelty kaava.
Ja nyt se kikka: Mikä onkaan P(#P):n totuusarvo? Se nimittääin sanoo, että ei löydy x:ää niin, että R(x,#P(#P)) pitäisi paikkaansa. Tämä tarkoittaisi siis, että ei ole olemassa sellaista numeroa, joka koodaisi P(#P):n todistuksen.
Tämä predikaatti on aivan hyvinmääritelty. Se on väittämä joka joko pitää paikkansa tai sitten ei pidä. Jos se ei pidä paikkaansa, niin luonnollisista luvuista löytyisi sellainen alkio joka koodaisi väittämän todistuksen. Tiedämme kuitenkin, että esimerkiksi Hilbertin järjestelmä (tai mikä ikinä äärellinen päättelyjärjestelmä meillä onkaan käytössä) voi todistaa vain tosia väittämiä. Joten väittämälle ei voi olla todistusta.
Gödelin - ja kanoninen tulkinta ylipäänsä - tälle lauseelle on, että on olemassa aritmeettisia "totuuksia" joita ei voi todistaa. Tämä on todistusteoreettinen tulos; me emme voi todistaa että P(#P) on tosi kaikissa aritmetiikan malleissa. Se on selvästi tosi siinä mallissa jonka me yleensä ymmärrämme luonnollisiksi luvuiksi, ja joista Gödel-numerotkin olemme poimineet. Sensijaan se ei ole tosi kaikissa malleissa. Jos se nimittäin olisi tosi kaikissa malleissa, niin se olisi tautologia, ja me tiedämme, että kaikki tautologiat voidaan todistaa. On siis mahdollista luoda aritmetiikkajärjestelmä, jossa tämä väittämä on todistettavissa. Se on kuitenkin erilainen kuin se, jonka ominaisuuksiin nojaamme kun esitämme tämän todistuksen.
Tietojenkäsittelyllinen näkökulma ensimmäiseen epätäydellisyyslauseeseen on, että ei voida esittää sellaista algoritmia, joka tulostaisi ulos paikkansapitäviä aritmeettisiä väittämiä niin, että jokainen tosi väittämä tulee lopulta ulos, mutta ei yhtään epätotta väittämää. Tämä näkökulma tarjoaa lyhyemmän ja - joidenkin mielestä - ymmärrettävämmän tuloksen: Jokaiselle syntaktisesti erilaiselle kaavalle voidaan antaa numero, ja tästä johdetaan muutamalla tempulla ns. Berryn paradoksi. Berryn paradoksi menee jotenkin niin, että postuloidaan "Pienin luonnollinen luku, jota ei voi määritellä alle 11 sanalla", mikä itsessään on määritelmä joka on ristiriidassa itsensä kanssa; tietokoneohjelmasta joka tuottaa kaikki aritmeettiset totuudet, saadaan johdettua samantapainen paradoksi.
Toinen epätäydellisyyslause on samansukuinen, mutta siinä puhutaan aksioomajärjestelmän konsistenssista. Konsistenssilla tarkoitetaan sitä, että aksiomien joukosta ei voida löytää ristiriitoja, eli ei voida yhtä aikaa todistaa jotakin väittämää ja sen negaatiota. Gödel rakentaa tämän tuloksen samaan tapaan kuin ensimmäisen epätäydellisyyslauseenkin, mutta tämän lisäksi tarvitaan hyvin monimutkainen konstruktio jolla ilmaistaan konsistenssiväittämä. Konsistenssiväittämä on jotakuinkin se että "Ei ole olemassa toditusta epätodelle väittämälle". Konsistenssiväittämän todistus itsessään johtaa tilanteeseen, jossa samalla todistetaan ristiriita.
maanantai 14. lokakuuta 2013
Pitkä Juoksu 2, vol IV + vähän muuta.
Kävin perjantaina kokeilemassa polveani. Olen venytellyt ohjeiden mukaan - tosin joidenkin lähteiden mukaan ITBS:ää ei voi hoitaa venytyksin. Perjantainen juoksu sujui paremmin kuin aiemmat, joten paranemista lienee tapahtunut. Kipu alkoi kuudennella kilometrillä, ja vahingosta viisastuneena en yrittänyt juosta kipua vastaan. Pysähtelin ja venyttelin välillä, mutta luovutin noin kahdeksan kilometrin kohdalla ja vaihdoin hitaaseen kävelyyn.
Sunnuntaina juoksin reilu neljä kilometriä ilman kipua. Toistaiseksi suunnitelmani on, että juoksen nopeita lyhyitä lenkkejä ja toisinaan kokeilen paljonko polvi kestää.
Tämä myös sikäli helpotti päätöstäni Lanzaroten suhteen: en missään nimessä voi osallistua täysmaratonille. Puolikaskin voi olla liian pitkä, joten jos en ole pystynyt siihen mennessä luotettavasti ilman kipuja juoksemaan vähintään 20 kilometrin matkaa, osallistun esimerkiksi vain kympille. Matkaa en aio tietenkään perua, koska siitä on jo varausmaksu maksettu.
Tällä viikolla ei ole luentoja, ja teen ensi viikoksi luentomateriaalia. Kävin Ben-Arin ne osat läpi jo, joita pidän olennaisina: Propositiologiikan, Herbrandin teoreema, Löwenheim-Skolemin, kompaktisuuden, täydellisyyden ja Gödelin ensimmäisen epätäydellisyyden. Täydennän materiaalia algebrallisella lähestymisellä, mistä laajennan malliteoriaan juuri sen verran, että täydellisyys, kompaktisuus ja Löwenheim-Skolem saadaan käsiteltyä tästä näkökulmasta. Jos aikaa jää, otan rekursioteoriaa sen verran, että voin esittää laskennallisuustulkinnan Gödelin epätäydellisyyslauseesta.
Sunnuntaina juoksin reilu neljä kilometriä ilman kipua. Toistaiseksi suunnitelmani on, että juoksen nopeita lyhyitä lenkkejä ja toisinaan kokeilen paljonko polvi kestää.
Tämä myös sikäli helpotti päätöstäni Lanzaroten suhteen: en missään nimessä voi osallistua täysmaratonille. Puolikaskin voi olla liian pitkä, joten jos en ole pystynyt siihen mennessä luotettavasti ilman kipuja juoksemaan vähintään 20 kilometrin matkaa, osallistun esimerkiksi vain kympille. Matkaa en aio tietenkään perua, koska siitä on jo varausmaksu maksettu.
Tällä viikolla ei ole luentoja, ja teen ensi viikoksi luentomateriaalia. Kävin Ben-Arin ne osat läpi jo, joita pidän olennaisina: Propositiologiikan, Herbrandin teoreema, Löwenheim-Skolemin, kompaktisuuden, täydellisyyden ja Gödelin ensimmäisen epätäydellisyyden. Täydennän materiaalia algebrallisella lähestymisellä, mistä laajennan malliteoriaan juuri sen verran, että täydellisyys, kompaktisuus ja Löwenheim-Skolem saadaan käsiteltyä tästä näkökulmasta. Jos aikaa jää, otan rekursioteoriaa sen verran, että voin esittää laskennallisuustulkinnan Gödelin epätäydellisyyslauseesta.
torstai 10. lokakuuta 2013
Mallit vol 2.
Moni käsittää logiikan jonkinlaisena kaavojen manipulaationa, jolla ei ole sen kummempaa merkitystä. Puhtaan formalistisessa mielessä näin onkin, mutta tämä ei ole koko totuus. Joskus aikanaan käsittelin kirjoituksissani runsaasti operationalisoinnin käsitettä. Operationalisoinnilla tarkoitetaan karkeastiottaen sitä, että kun meillä on jokin teoria, niin teorian käsitteet kytketään havaittavissaoleviin suureisiin tai tapahtumiin, jonka jälkeen voimme ikäänkuin verrata teorian ja todellisuuden käyttäytymistä.
Logiikassa operationalisoinnin vastine on mallin käsite. Malli loogisessa mielessä ei suinkaan tarkoita mallia siinä mielessä kuin esimerkiksi "pienoismalli" tai "mallinnos", vaan kyse on pikemminkin loogikkojen kummallisesta huumorintajusta: Malli on struktuuri jonka käsitteistöön logiikan symbolit operationalisoidaan; se on siis pikemminkin ns todellisuuden vastine. Filosofisemmat loogikot puhuvatkin toisinaan "maailmoista", mitä pidän hieman turhan juhlavana. Malliteorialla tarkoitetaan sitä matemaattisen logiikan osa-aluetta, joka tutkii sitä, miten eri mallien "ominaisuudet" riippuvat loogisten konstruktioiden ominaisuuksista.
Craig:n interpolaatio on yksinkertainen lause joka pätee ensimmäisen kertaluvun logiikassa. Yksinkertaisesti ilmaistuna se tarkoittaa sitä, että jos loogisesti pätee, että A:sta seuraa B, niin on olemassa kaava C siten, että C on seuraus A:sta ja B on seuraus C:stä, ja C ottaa kantaa vain niihin asioihin jotka ilmenevät sekä A:ssa että B:ssä. Interpolaatioteoreemasta voidaan johtaa myös sellainen mielenkiintoinen teoreema, että jos väittämä "A ja B" on ristiriitainen, niin voidaan löytää välikaava C siten, että C on seuraus A:sta, "C ja B" on ristiriitainen, ja C viittaa vain niihin asioihin jotka ilmenevät sekä B:ssä että A:ssa. Malliteoreettisesti voidaan ajatella tämä niin, että kaavalla A on jotain malleja, kaavalla B on jotain muita malleja; koska "A ja B" on ristiriita, niillä ei ole yhteisiä malleja. C:n voi ajatella rajaukseksi, joka sulkee pois tarkalleen ne mallit jotka ovat B:n malleja, eikä mitään niistä malleistä jotka ovat A:n malleja: koska C on A:n seuraus, niin jokainen A:n malli on C:n malli ja koska C ja B ovat ristiriitaisia, niin mikään C:n malli ei ole B:n malli. Koska C ottaa kantaa vain niihin käsitteisiin jotka ilmenevät sekä A:ssa että B:ssä, se ei rajaa pois malleja jotka eivät jollakin tapaa "liity" B:hen.
Interpolaatioteoreema ei vaikuta kovin syvälliseltä kun sitä tutkii tarkemmin. Itseasiassa sama pätee matemaattisessa logiikassa noin ylipäänsä: Kun jonkin tuloksen ymmärtää todella, niin päällimmäinen kokemus ei ole juuri koskaan että asia on syvällinen, vaan käytännössä kaikki todistukset ovat puhtaasti "teknisiä". Yksi esimerkki tällaisesta tuloksesta on Herbrandin teoreema, joka voidaan muotoilla monella eri tavalla, mutta joka periaatteessa palauttaa ensimmäisen kertaluvun logiikan propositionaaliseksi päättelyksi. Jotta teoreeman voi ymmärtää, tarvitaan hieman pohjustusta. Sivuutan tässä muutamia yksityiskohtia ja olen hieman epätäsmällinen - yritän keskittyä olennaiseen.
Jokainen suljettu predikaattilogiikan kaava voidaan esittää ns klausaalisessa muodossa, eli joukkona klausuuleja joissa ei esiinny kvanttoreita. Jos kaava ei ole tässä muodossa, se voidaan siihen saattaa: Kaikki kvanttori siirretään kaavan eteen, tarvittaessa uudelleennimeämällä muuttujat. Tämän jälkeen olemassaolokvanttorit poistetaan Skolemisoinnilla. Kvanttorivapaa osa kaavasta saatetaan Konjunktiiviseen normaalimuotoon. Tämän lisäksi täytyy ymmärtää niin sanottu ground instanssin käsite. Ground termi on termi, jossa ei esiinny muuttujia, vaan ainoastaan funktioita ja vakioita; ground term on termi jonka arvo periaatteessa aina tunnetaan (kun malli on tiedossa). Kaavan kvanttorivapaassa osassa on predikaatteja joissa on vapaita muuttujia, siis esimerkiksi muotoa P(x). Ground instanssi tästä on esimerkiks P(f(a)) missä a on jokin vakio.
Herbrandin teoreema sanoo, että mielivaltainen joukko klausuuleja on ristiriitainen jos ja vain jos siitä voidaan ottaa äärellinen joukko ground instansseja siten, että se on puhtaasti syntaktisesti ristiriitainen; siis niin, että kukin syntaktisesti erilainen ground instanssi tulkitaan omaksi propositiosymbolikseen ja kaavaa kohdellaan tämän jälkeen kuten propositiologiikan kaavaa yleensäkin. Kyseessä on siis puhtaasti merkkijonomanipulaatioon perustuva kikka.
Herbrandin teoreema perustuu siihen, että jokaisella klausaalimuodolla jolla ylipäänsä on malli, on olemassa niinsanottu Herbrandin malli. Herbrandin malli on puhtaasti syntaktinen konstruktio. Se rakennetaan niin, että yksinkertaisesti oletetaan että jokainen symbolinen esitys ground termeille on mallissa esiintyvä oma alkionsa. Herbrandin mallit ovatkin tyypillisesti äärettömiä, koska ground termejä on ääretön määrä jos kaavassa on yksikin funtiosymboli. Koska skolemisointi tuottaa funktiosymboleja, niin niiden kaavojen joukko joille Herbrandin malli on äärellinen, on hyvin pieni.
Logiikassa operationalisoinnin vastine on mallin käsite. Malli loogisessa mielessä ei suinkaan tarkoita mallia siinä mielessä kuin esimerkiksi "pienoismalli" tai "mallinnos", vaan kyse on pikemminkin loogikkojen kummallisesta huumorintajusta: Malli on struktuuri jonka käsitteistöön logiikan symbolit operationalisoidaan; se on siis pikemminkin ns todellisuuden vastine. Filosofisemmat loogikot puhuvatkin toisinaan "maailmoista", mitä pidän hieman turhan juhlavana. Malliteorialla tarkoitetaan sitä matemaattisen logiikan osa-aluetta, joka tutkii sitä, miten eri mallien "ominaisuudet" riippuvat loogisten konstruktioiden ominaisuuksista.
Craig:n interpolaatio on yksinkertainen lause joka pätee ensimmäisen kertaluvun logiikassa. Yksinkertaisesti ilmaistuna se tarkoittaa sitä, että jos loogisesti pätee, että A:sta seuraa B, niin on olemassa kaava C siten, että C on seuraus A:sta ja B on seuraus C:stä, ja C ottaa kantaa vain niihin asioihin jotka ilmenevät sekä A:ssa että B:ssä. Interpolaatioteoreemasta voidaan johtaa myös sellainen mielenkiintoinen teoreema, että jos väittämä "A ja B" on ristiriitainen, niin voidaan löytää välikaava C siten, että C on seuraus A:sta, "C ja B" on ristiriitainen, ja C viittaa vain niihin asioihin jotka ilmenevät sekä B:ssä että A:ssa. Malliteoreettisesti voidaan ajatella tämä niin, että kaavalla A on jotain malleja, kaavalla B on jotain muita malleja; koska "A ja B" on ristiriita, niillä ei ole yhteisiä malleja. C:n voi ajatella rajaukseksi, joka sulkee pois tarkalleen ne mallit jotka ovat B:n malleja, eikä mitään niistä malleistä jotka ovat A:n malleja: koska C on A:n seuraus, niin jokainen A:n malli on C:n malli ja koska C ja B ovat ristiriitaisia, niin mikään C:n malli ei ole B:n malli. Koska C ottaa kantaa vain niihin käsitteisiin jotka ilmenevät sekä A:ssa että B:ssä, se ei rajaa pois malleja jotka eivät jollakin tapaa "liity" B:hen.
Interpolaatioteoreema ei vaikuta kovin syvälliseltä kun sitä tutkii tarkemmin. Itseasiassa sama pätee matemaattisessa logiikassa noin ylipäänsä: Kun jonkin tuloksen ymmärtää todella, niin päällimmäinen kokemus ei ole juuri koskaan että asia on syvällinen, vaan käytännössä kaikki todistukset ovat puhtaasti "teknisiä". Yksi esimerkki tällaisesta tuloksesta on Herbrandin teoreema, joka voidaan muotoilla monella eri tavalla, mutta joka periaatteessa palauttaa ensimmäisen kertaluvun logiikan propositionaaliseksi päättelyksi. Jotta teoreeman voi ymmärtää, tarvitaan hieman pohjustusta. Sivuutan tässä muutamia yksityiskohtia ja olen hieman epätäsmällinen - yritän keskittyä olennaiseen.
Jokainen suljettu predikaattilogiikan kaava voidaan esittää ns klausaalisessa muodossa, eli joukkona klausuuleja joissa ei esiinny kvanttoreita. Jos kaava ei ole tässä muodossa, se voidaan siihen saattaa: Kaikki kvanttori siirretään kaavan eteen, tarvittaessa uudelleennimeämällä muuttujat. Tämän jälkeen olemassaolokvanttorit poistetaan Skolemisoinnilla. Kvanttorivapaa osa kaavasta saatetaan Konjunktiiviseen normaalimuotoon. Tämän lisäksi täytyy ymmärtää niin sanottu ground instanssin käsite. Ground termi on termi, jossa ei esiinny muuttujia, vaan ainoastaan funktioita ja vakioita; ground term on termi jonka arvo periaatteessa aina tunnetaan (kun malli on tiedossa). Kaavan kvanttorivapaassa osassa on predikaatteja joissa on vapaita muuttujia, siis esimerkiksi muotoa P(x). Ground instanssi tästä on esimerkiks P(f(a)) missä a on jokin vakio.
Herbrandin teoreema sanoo, että mielivaltainen joukko klausuuleja on ristiriitainen jos ja vain jos siitä voidaan ottaa äärellinen joukko ground instansseja siten, että se on puhtaasti syntaktisesti ristiriitainen; siis niin, että kukin syntaktisesti erilainen ground instanssi tulkitaan omaksi propositiosymbolikseen ja kaavaa kohdellaan tämän jälkeen kuten propositiologiikan kaavaa yleensäkin. Kyseessä on siis puhtaasti merkkijonomanipulaatioon perustuva kikka.
Herbrandin teoreema perustuu siihen, että jokaisella klausaalimuodolla jolla ylipäänsä on malli, on olemassa niinsanottu Herbrandin malli. Herbrandin malli on puhtaasti syntaktinen konstruktio. Se rakennetaan niin, että yksinkertaisesti oletetaan että jokainen symbolinen esitys ground termeille on mallissa esiintyvä oma alkionsa. Herbrandin mallit ovatkin tyypillisesti äärettömiä, koska ground termejä on ääretön määrä jos kaavassa on yksikin funtiosymboli. Koska skolemisointi tuottaa funktiosymboleja, niin niiden kaavojen joukko joille Herbrandin malli on äärellinen, on hyvin pieni.
Tilaa:
Blogitekstit (Atom)