Download gradu02989.pdf

Contents : TAMPEREEN YLIOPISTO Pro gradu -tutkielma Tanja Lehtinen Sekventtikalkyylin t ydellisyyden todistaminen Matematiikan ja tilastotieteen laitos Matematiikka Toukokuu 2008 Tampereen yliopisto Matematiikan tilastotieteen ja loso an laitos LEHTINEN TANJA: Sekventtikalkyylin t ydellisyyden todistaminen Pro gradu -tutkielma 49 s. Matematiikka Toukokuu 2008 Tiivistelm T ss tutkielmassa tarkastellaan t ydellisyyslauseen todistamista sekventtikalkyylin avulla ensimm isen kertaluvun logiikassa. Aluksi luvussa 1 tutustutaan aiheen kontekstiin ja tarkastellaan tarvittavia k sitteit . Sen j lkeen luvussa 2 k sitell n logiikan syntaksia. T ss luvussa esitell n hieman propositiologiikkaa ja sen j lkeen siirryt n tarkastelemaan ensimm isen kertaluvun logiikkaa jossa tutustutaan muun muassa aakkostoihin termeihin kaavoihin ja induktiolla todistamiseen. Luvussa 3 tutkitaan logiikan semantiikkaa. J lleen ensimm isen k sitell n propositiologiikkaa jossa tarkastellaan kaavojen totuusarvoja. Ensimm isen kertaluvun logiikkaa k sittelev ss luvussa m ritell n struktuuri tulkintafunktio ja tulkinta. T m n j lkeen tarkastellaan kaavojen totuutta loogista seurausta ja lopuksi sijoitusta. Valmisteluna p aihetta varten esit mme luvussa 4 luettelomaisesti useita sekventtikalkyylin s nt j . Luvun lopussa tarkastellaan joukkojen ristiriidattomuutta ja todistetaan eheyslause joka on eritt in t rke sekventtikalkyylin t ydellisyyden todistamisessa. Kaikki n m edelt v t luvut valmistelevat t ydellisyyslauseen todistamista joka esitet n viidenness ja viimeisess luvussa. Ennen t ydellisyyslauseen todistusta todistetaan kuitenkin Henkinin lause ja ristiriidattomien joukkojen toteutuvuus. L hdeteoksena k ytet n H.D. Ebbinghaus J. Flum ja W. Thomasin kirjaa Mathematical Logic. Asiasanat: Kurt G del t ydellisyyslause sekventtikalkyyli propositiologiikka ensimm isen kertaluvun logiikka eheyslause Henkinin lause. 1 Sis lt 1 Johdanto 3 2 Syntaksi 2.1 Propositiologiikka . . . . . . . . . . . . . 2.2 Ensimm isen kertaluvun logiikka . . . . 2.2.1 Ensimm isen kertaluvun logiikan kaavat . . . . . . . . . . . . . . . 2.2.2 Induktio . . . . . . . . . . . . . . 2.2.3 Vapaat muuttujat ja lauseet . . . 4 5 5 ........... ........... aakkosto termit ja ........... ........... ........... 3 Semantiikkaa 3.1 Propositiologiikan semantiikkaa . . . . . . . . 3.2 Ensimm isen kertaluvun logiikan semantiikkaa 3.2.1 Struktuurit ja tulkinnat . . . . . . . . 3.2.2 Totuusrelaatio . . . . . . . . . . . . . . 3.2.3 Looginen seuraus . . . . . . . . . . . . 3.2.4 Lis lauseita . . . . . . . . . . . . . . 3.2.5 Sijoitus . . . . . . . . . . . . . . . . . 4 Sekventtikalkyyli 4.1 Sekventtis nn t . . . . . . . . . . . . 4.2 Struktuuri- ja konnektiivis nn t . . . 4.3 Todistuvat konnektiivis nn t . . . . . 4.4 Kvanttori- ja identiteetti-s nn t . . . 4.5 Lis todistuvia s nt j ja sekventtej 4.6 Eheyslause . . . . . . . . . . . . . . . . 4.7 Ristiriidattomuus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 .8 . 11 . . . . . . . 12 12 13 13 15 15 16 21 . . . . . . . 24 25 26 28 31 33 34 35 5 T ydellisyyslause 5.1 Henkinin teoria . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Ristiriidattomien kaavajoukkojen toteutuvuus (numeroituva tapaus) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Ristiriidattomien kaavajoukkojen toteutuvuus (yleinen tapaus) 5.4 T ydellisyyslause . . . . . . . . . . . . . . . . . . . . . . . . . 37 37 Viitteet 49 42 45 47 2 1 Johdanto Jokaisen matemaattisen teorian rakentaminen alkaa v itelauseiden eli propositioiden j rjestelm st joka siis on kyseisen teorian aksioomaj rjestelm . Propositio seuraa aksioomaj rjestelm st jos on tosi jokaisessa struktuurissa joka toteuttaa kaikki aksioomaj rjestelm n aksioomat. Proposition todistus aksioomaj rjestelm ss osoittaa ett seuraa j rjestelm st . T m johdattaa meid t vastakkaisen ongelman reen: Onko jokainen propositio joka seuraa j rjestelm st my s todistuva j rjestelm ss Kysymykseen vastataan positiivisesti t m n tutkielman lopussa. T t lausetta kutsutaan t ydellisyyslauseeksi ja se on olennaisen t rke matemaattisessa logiikassa. Mit sitten tarkoittavat propositio struktuuri olla tosi seuraus ja todistuva Proposition k site selitet n luvun 2.1 alussa struktuurin k site puolestaan luvussa 3.2.1 totuus ja seuraus vastaavasti luvuissa 3.2.2 ja 3.2.3. Proposition matemaattinen todistus aksioomaj rjestelm ss mu

INFO HASH : 62a912018fcd7636e0ea5aa08c3263dcb274f77e

Download now

File Size: 366.2 kb