Teise Ja Kõrgema Järgu Loogika

2023 Autor: Noah Black | [email protected]. Viimati modifitseeritud: 2023-08-25 04:38

Sisenemise navigeerimine

• Sissesõidu sisu
• Bibliograafia
• Akadeemilised tööriistad
• Sõprade PDF-i eelvaade
• Teave autori ja tsitaadi kohta
• Tagasi üles

Teise ja kõrgema järgu loogika

Esmakordselt avaldatud 20. detsembril 2007; sisuline redaktsioon K 4. märts 2009

Teise astme loogika on esimese järgu loogika laiendus, kus lisaks kvantitaatoritele, nagu näiteks „iga objekti jaoks (diskursuse universumis)”, on kvantitatiivid nagu „objektide iga omaduse kohta (diskursuse universumis)).” Keele selline suurendamine suurendab selle väljendusjõudu, lisamata uusi mitteloogilisi sümboleid, näiteks uusi predikaat sümboleid. Klassikalise laiendiloogika puhul (nagu ka selles sissekandes) saab atribuute tuvastada komplektide abil, nii et teise järgu loogika annab meile kvantitaatori “iga objektide komplekti jaoks”.

Teise astme loogika semantikale on kaks lähenemisviisi. Need erinevad fraasi „iga objektide komplekti” tõlgendamisel. Kas sellel on mingi kindel tähendus, millele saame viidata, või peame arvestama fraaside tähenduste mitmekesisusega? Esimesel juhul (mida hakatakse kutsuma standardsemantikaks) peame teatud matemaatilisi mõisteid iseenesestmõistetavaks. Teisel juhul (mida hakatakse nimetama üldiseks semantikaks) peetakse palju vähem enesestmõistetavaks. Sel juhul peab lause õigeks pidamiseks olema tõene fraasi „iga objektide komplekti” kõigi lubatud tähenduste korral.

• 1. Süntaks ja tõlge
• 2. Standardsemantika
• 3. Üldine semantika
• 4. Kõrgema järgu loogika
• 5. Teise järgu numbriteooria süsteemid
• Bibliograafia
• Akadeemilised tööriistad
• Muud Interneti-ressursid
• Seotud kirjed

1. Süntaks ja tõlge

Sümboolses loogikas vastab valem (Px → Px) tõele, olenemata sellest, milline objekt diskursuse universumis on määratud muutujale x. Mis tähendab, et nothing x (Px → Px) vastab tõele, olenemata sellest, millist diskursuse universumi alamhulka kasutatakse predikaatliku sümboli P tõlgendamiseks. Kuid kas pole mitte midagi öelda, vaid et valem ∀ P ∀ x (Px → Px) on tõsi, ükskõik mida?

Esimese astme keeltes on mõned asjad, mida me saame öelda, ja mõned, mida me ei saa. Oletame näiteks, et tahame avaldada fakte naturaalarvude aritmeetika kohta. See tähendab, et tahame väljendada fakte struktuuri (N; 0, S, <, +, ×) kohta, mis koosneb naturaalarvude hulgast N = {0, 1,…} koos tavaliste aritmeetiliste toimingute ja suhetega. Ja me tahame kasutada esimese astme keelt kvantitaatoritega ∀, mida tõlgendatakse kui “iga naturaalarvu jaoks” ja ∃ tõlgendatakse kui “mõne naturaalarvu jaoks”. Lisaks hõlmame keeles püsiv sümbol 0 arvu nulli jaoks, ühekohaline funktsioonisümbol S järeltöötluse jaoks (mis naturaalarvu kohaldades annab järgmise), kahekohaline predikatsioonisümbol <tellimissuhte jaoks <N pealja kahekohalised funktsioonisümbolid + ja × vastavalt liitmiseks ja korrutamiseks.

Selle keele abil saame nüüd sümboliseerida paljusid fakte, millest teame, et need vastavad tõestele naturaalarvudele. Saame moodustada lause ∀ x (x <Sx), mis väljendab asjaolu, et iga arv on väiksem kui näiteks järgmine. Kuid raskused tekivad siis, kui tahame väljendada “hästi korrastavat omadust”, et ükskõik millisel mittetühjal naturaalarvude komplektil on väikseim liige. Kui P on uus ühe koha predikaat sümbol, siis

∃ x Px → ∃ x (Px ja ∀ y (Py → (y = xvx <y)))

väljendab mõtet, et P on tõene mõne väikseima arvu korral, kui see kehtib kõigi arvude kohta. See valem vastab tõele struktuuris (N; 0, S, <, +, ×), kui tõlgendame predikaattähist P tõesena teatud kindla komplekti numbrite suhtes - sõltumata sellest, milline see komplekt on - öeldakse, et komplekt on kõige vähem liiget, kui see pole tühi. Nüüd lisage kvantifikaator ∀ P

∀ P [∃ x Px → ∃ x (Px ja ∀ y (Py → (y = xvx <y))))]

saame hästi korrastava vara vormistamise.

Teise järgu loogika keel laiendab esimese järgu loogika keelt, võimaldades predikaat- ja funktsioonisümbolite kvantifitseerimist. Nagu eelnev näide näitab, võime aritmeetika teise astme keeles öelda, et naturaalarvud on hästi järjestatud. Me teame, et hästi järjestatavat omadust ei saa ühegi esimese järgu lausega väljendada, sest (N; 0, S, <, +, ×) (esimese järgu) teooria mittestandardseid mudeleid ei tellita kunagi hästi. Nii et teise astme loogika juurde minek on ehtne laiend. See tähendab, et võime tõlkida mõned looduskeelsed laused, näiteks „Seos <on hästi korrastav” teise järgu loogika keelde, mida ei saa tõlkida esimese astme loogika keelde.

Teise näitena võime (kasutades valikut) öelda, et diskursuse universum on lõpmatu, öeldes, et universumis on olemas transitiivne suhe, nii et igal elemendil on seos millegi, kuid mitte iseendaga:

∃ R [∀ x ∀ y ∀ z (Rxy ja Ryz → Rxz) ja ∀ x [¬ Rxx ja ∃ y Rxy]

Teise astme kvantifikaator “∃ R” väljendab siin mingisugust binaarset seost universumis. Kuna selle kvantifikaatori ulatuses on ainus predikaatmärk R, pole lausel tõlgendamiseks avatud predikaattähiseid. Nagu on hästi teada, pole ühelgi esimese järgu lausel oma mudelite jaoks täpselt lõpmatuid struktuure.

Üksikasjalikumalt mõeldakse siin teise astme keele all: üks algab esimese astme keelega ja täiendab seda n-koha predikaatmuutujate lõpmatu pakkumisega iga positiivse täisarvu n jaoks ja lõpmatu pakkumisega n -funktsiooni muutujad iga positiivse täisarvu n korral. (Funktsioonimuutujaid saab vältida, kuid see on teine küsimus.) Hästi moodustatud valemite moodustamise reeglid on ilmsed; eriti universaalne ja eksistentsiaalne kvantifitseerimine on lubatud iga muutuja jaoks, olgu see siis individuaalne muutuja, predikatiivne muutuja või funktsioonimuutuja.

Naastes naturaalarvude näite juurde, võime Peano induktsiooni postulaati väljendada teise järgu lausega:

∀ X [X 0 ja ∀ y (Xy → XSy) → ∀ y Xy]

See lause väljendab mõtet, et X vastab tõele kõigi naturaalarvude puhul, kui see vastab tõele 0 ja selle tõde mingil arvul y garanteerib selle tõe y järeltulijal, sõltumata sellest, milline arvude komplekt X võib olla tõene.

Näites, mis hõlmab reaalarvude komplekti R koos tavapärase järjestamisega, saame väikseima ülaserva omaduse väljendada teise järgu lausega:

∀ X [∃ y ∀ z (Xz → z ≤ y) ja ∃ z Xz → ∃ y ∀ y '(∀ z (Xz → z ≤ y') ↔ y ≤ y ')]

Eelnevad näited on võetud matemaatilistest olukordadest. Samuti on intrigeeriv võimalus looduskeelsetes lausetes, mis näivad nende vormistamiseks vajavat teise järgu valemeid. George Boolos pakkus näite: "On mõned kriitikud, kes imetlevad ainult üksteist." Selle lausega kinnitatakse teatud vara omavate isikute kogumi olemasolu; see ei tähenda näiteks, et on kaks kriitikut, kes imetlevad üksteist ega imetle mitte ühtegi teist.

2. Standardsemantika

Eelmises jaotises on kaudselt kasutatud teise järgu lause tõe kontseptsiooni struktuuris. Mõelge struktuurile M = (A, R,…), mis koosneb mittetühjast hulgast A, mis toimib diskursuse universumina, ja mõningatest seostest ja funktsioonidest A-l, mis tõlgendab mitteloogilisi sümboleid. Siis tahame arvestada vormi ∀ P second teise astme lauset (kus P on ak-koha predikaatmuutuja) selle struktuuri tõesena, kui A-liikme iga k-komplekti Q hulga Q korral on meil that vastab tõele struktuuris, kui P-le omistatakse seos Q.

Ametlikumalt peame määrama induktiivselt, mida tähendab teise astme valemi φ rahuldamine struktuuris M = (A, R,…), kui objekt omistatakse objekti free vabadele muutujatele in, mis kirjutatakse M ⊨ φ [s]. Määratlus toimub täpselt nagu esimese astme puhul, välja arvatud teise järgu kvantifikaatorite lisaklauslid. Ak-koha predikaatmuutuja P korral

M ⊨ ∀ P φ [s] kui iga A-k-i seose Q korral on meil M ⊨ φ [s ']

kus s 'erineb s-st ainult seose Q määramisel predikaatmuutujale P. (Siin lühendab „iff“lühendit „ainult siis ja ainult siis“.) Samamoodi funktsiooni muutuja ak-ak puhul F, M ⊨ ∀ F φ [s] kui iga k-koha funktsiooni G kohta A-l on meil M ⊨ φ [s ']

kus s 'erineb s-st ainult funktsiooni G omistamisel funktsioonimuutujale F. Pange tähele, et see määratlus viitab 1-kohalise predikaatmuutuja korral A kõigile alamhulkadele, see tähendab kogu A võimsuskomplektile. Just see omadus annab teise astme keelte erakordse semantilise tugevuse.

Teisejärgulise lause σ (st vaba muutujata valemi) korral pole ülesanne s enam asjakohane ja võime struktuuris M rääkida ühemõtteliselt tõe või vale väärtusest σ (st võib öelda, et M on või ei ole σ mudel). Eelkõige võib nüüd näha § 1 näidete tõlkeid looduskeelest teise järgu loogika keelde nende kavandatud eesmärkide saavutamiseks. Lineaarse järjestamise ja lause aksioomide kooslus

∃ x Px → ∃ x (Px ja ∀ y (Py → (y = xvx <y)))

vastab tõele struktuuris (A, <), kui seos <tellib hulga A hästi. Lause

∃ R [∀ x ∀ y ∀ z (Rxy ja Ryz → Rxz) ja ∀ x (¬ Rxx ja ∃ y Rxy)]

vastab tõele struktuuris, kus diskursuse universum on lõpmatu kogum. See näide näitab, et kompaktsuse teoreem ei kehti teise astme loogika jaoks. Kui nimetame ülaltoodud lauset λ∞ ja laseme λ n-l olla esimese astme lause “universumis on vähemalt n erinevat asja”, siis komplekt

{¬λ∞, λ2, λ3, λ4, …}

pole mudelit, ehkki igal piiratud alamhulgal on mudel.

Peano postulaat seostub

∀ x (¬0 = Sx) ja ∀ x ∀ y (Sx = Sy → x = y)

ja Peano induktsiooni postulaat

∀ X [X 0 ja ∀ y (Xy → XSy) → ∀ y Xy]

vastab tõele struktuuris (A, f, e), kui see struktuur on isomorfne (N, S, 0) suhtes, järgneva operatsiooni S ja eristatud elemendi naturaalarvudega. Nende kolme lause kooslus annab näite lause, mis on kategooriline, see tähendab, et sellel on täpselt üks mudel, kuni isomorfismini. Esimese astme lause võib seevastu olla kategooriline ainult siis, kui selle üks mudel on piiratud.

Samamoodi saab reaalarvude järjestatud välja (R, 0, 1, +, ×, <) iseloomustada kuni isomorfismini järjestatud välja esimese astme aksioomide järgi koos teise järgu lausega, mis väljendab kõige vähem - ülaosaga kinnistu. On hästi teada, et nende lausete mis tahes mudel peab olema isomorfne reaalarvude järjestatud välja suhtes. See näide näitab, et Löwenheim – Skolemi teoreem ei kehti teise astme loogika osas.

Eelnevad näited näitavad, et kaks igapäevast matemaatilist struktuuri (N, S, 0) ja (R, 0, 1, +, ×, <) on teisejärgulised. See tähendab, et igal ühel on ühtne teise järgu aksioom, millest see on ainus mudel, kuni isomorfismini. Võib küsida, millised muud struktuurid võivad olla teisejärgulised. Muidugi, kuni isomorfismini võib selliseid struktuure olla vaid loendatavalt palju, sest igaüks vajab lauset.

Järgmisena oletame, et nendes näidetes kvantifitseerime eksistentsiaalselt kõik mitteloogilised sümbolid (st kõik predikaat- ja funktsioonisümbolid). Kui π (0, S,) on kolme Peano postulaadi kooslus, on lause ∃ x ∃ F π (x, F) lause võrdsuse teise astme keeles, see tähendab, et sellel puudub mitteloogiline sümbolid üldse.

Võrdõiguslikkuse keele struktuur koosneb lihtsalt tühjast diskursuse universumist; puuduvad seosed ega funktsioonid ega eristatavad elemendid. Sellise struktuuri määrab muidugi isomorfism lihtsalt selle kardinaalsuse tõttu. Lause σ kohta võrdsuse keeles olgu selle spekter kardinaliteetide klass, milles see on tõene. Näiteks kehtiva lause spekter on kõigi nullist erinevate kardinalide klass. Mitterahuldava lause spekter on tühi. ¬σ spekter on σ spektri täiendus (kõigi nullist erinevate kardinaalsete arvude klassi suhtes). Lausete konjunktsioon ja disjunktsioon annavad spektrite ristumise ja liitumise. Lause võrdsuse keeles määratakse loogilise ekvivalentsuseni selle spektri järgi.

Peano postulaatidest tehtud lause ∃ x ∃ F π (x, F) on tõeselt lõpmatus kardinaalsuses ja mitte üheski teises. Seega on selle spekter singleton. Ütle, et kardinalarv κ on teise järguga iseloomulik, kui leidub võrdsuse teise astme keele lause, mis vastab tõele kardinaalsuses κ ja ainult seal. (Nullist erinevad piiratud kardinalid on kõik esmajärgulised.) Oleme näinud, et loendamatu lõpmatu kardinal on teise järgu iseloomustus. Sarnaselt võime näidata, et kontinuumi jõud on teisejärguline. Kui ρ (0, 1, +, ×, <) on teise järgu lause, mis iseloomustab reaalarvude järjestatud välja kuni isomorfismi, siis lause

∃ x ∃ y ∃ F ∃ G ∃ R ρ (x, y, F, G, R)

on võrdõiguslikkuse teise astme keeles lause, mis vastab tõele kontinuumi võimuses ja mitte üheski teises kardinaalsuses.

Võib küsida, millised muud kardinaalsed numbrid on teisejärgulised. Selle küsimuse uurimiseks lugege S. Garlandi 1974. aasta artiklit. Selliseid kardinali võib muidugi olla vaid loendatavalt palju, sest igaüks võtab lause.

Pole raske aru saada, et kõige vähem loendamatu kardinal on teisejärguline. Me võime kasutada lauset, mis ütleb, et universum on lõpmatu, kuid mitte loendatav ja et kõik loendamatud alamhulgad on kogu universumi jaoks võrdsed. Seega on meil võrdsuse teise astme keeles laused κ ja λ, mis iseloomustavad vastavalt kõige vähem loendamatut kardinaali ja kontinuumi jõudu. Lause κ ↔ λ on kehtiv lause, kui pidevhüpotees on tõene, ja ainult siis. Võib järeldada, et ZFC-s ei lahendata tingimata kõiki teise astme loogikaga seotud probleeme.

Palju uuritud PA-i esimese astme aritmeetika teooria saadakse muidugi teise astme induktsiooniposturaadi asemel ∀ X [X 0 & ∀ y (Xy → XSy) → ∀ y Xy], kasutades vastavat esimese järjekorra skeem

φ (0) ja ∀ y (φ (y → φ (Sy)) → ∀ y φ (y)

kus φ võib olla ükskõik milline sobiv esimese järgu valem. Selle skeemi mõju on hästi teada; see tagab, et iga määratletav komplekt, mis sisaldab 0 ja on suletud järeltulija poolt, peab sisaldama kõike.

Oletame, et analoogia põhjal alustame reaalarvude järjestatud välja teist järku aksiomatizimisega ja asendame teise järku madalaima ülaosaga aksioomi vastava skeemiga. Tulemuseks on lõpmatu komplekt esimese astme aksioome, tagades, et kõigil määratlematutel komplektidel, mis pole tühjad ja piiratud, on minimaalne ülemine piir. Selle mudeleid nimetatakse reaalselt suletud järjestatud väljadeks. Huvitav on see, et selle kontseptsiooni sõnastasid kõigepealt algebraistid, mitte loogikud.

Teise astme loogika tugevuse üks mõõt on selle kehtivate lausete kompleksi keerukus. Olgu V ¹ esimese astme loogika kehtivate lausete kogum ja V ² teise astme loogika kehtivate lausete komplekt. Täpsemalt, esimese astme loogikas, milles on ainult üks kahekohaline predikaattähis P, teame, et kehtivate lausete komplekt V ¹ (P) on täielik arvutatav loetav komplekt (st täielik rekursiivselt loendatav komplekt). (Siin saame määrata Gödeli numbreid ja vaadata V ¹ (P) naturaalarvude kogumina või samaväärsena võime seda vaadata otse kui sõnade komplekt piiratud tähestiku kohal.) Ja Tarski on märkinud, et komplekt V ¹ (=) kehtivate lausete võrdsuse esimese astme keeles (millel pole üldse mitteloogilisi sümboleid) on otsustatav.

Võrdluseks - olgu V ² (=) kehtivate lausete komplekt võrdsuse teise astme keeles. Mis on selle komplekti keerukus?

Olgu π Peano postulaatide ja liitmise ja korrutamise rekursioonivõrrandite koosseis. Seega π on aritmeetika keeles teise järgu lause, mille 0, S, + ja × on. Lause π on kategooriline; selle ainus mudel on (N, 0, S, +, ×), kuni isomorfismini. Järelikult on lause σ aritmeetika keeles σ tõene aritmeetikas, kui tingimuslik (π → σ) kehtib. See näitab, et V ² (0, S, +, ×) ei saa olla aritmeetilised (st ei saa olla aritmeetikas esimese astme piiritletavad), et aritmeetikas ei oleks tõde määratletav, rikkudes Tarski teoreemi. Nüüd saame kvantifitseerida kõik mitteloogilised sümbolid; lause φ (P) on kehtiv, kui lause ∀ P φ (P) on kehtiv. Järeldus on, et V ² (=) ei ole aritmeetiline.

Nii huvitav kui see ka pole, on see lihtsalt jäämäe tipp. Alustuseks võime näidata, et V ² (=) pole analüütiline, see tähendab, et seda ei saa aritmeetikas teise astme valemi abil määratleda. Tarski teoreemi tõestus, mis näitab, et aritmeetika tõeliste esimese astme lausete komplekt ei ole aritmeetikas esmajärjekorras määratletav, näitab ka seda, et aritmeetika tegelike teise järgu lausete komplekt ei ole aritmeetikas defineeritav teise astme lause. Ülejäänud väide on muutmata. Ja hiljem näeme, et veelgi enam on tõsi.

Hoopis teises suunas on R. Fagin näidanud üllatavat seost arvutusliku keerukusega teema ja piiritletud struktuuride teise astme määratletavuse vahel. Näiteks võib piiritletud graafi pidada paariks (V, E), mis koosneb mittetühja tipu hulgast V ja sümmeetrilisest servasuhest E V-l. Väidet, et graafikut saab õigesti kolme värviga värvida, saab väljendada teise järgu lausega: on olemas alamhulgad R, G, B, et partitsioon V moodustab nii, et kaks servaga ühendatud tippu pole kunagi sama värvi. See lause on Σ-1-1, see tähendab, et sellel on vorm

[eksistentsiaalsed teise järgu kvantifikaatorid] [esimese astme valem].

On hästi teada, et kolmevärviline olemine on graafi NP omadus. See tähendab, et see on omadus, mis on polünoomi ajal äratuntav mittedeterministliku Turingi masina poolt. (Seal on mittedeterministlik Turingi masin M ja polünoom p, mis antakse alati, kui M-le antakse sobivalt kodeeritud (V, E), siis kui (V, E) on kolmevärvitav, aktsepteerib M arvutamine graafik p (n) etappides, kus n mõõdab (V, E) suurust ja kui (V, E) ei ole kolmevärvitav, siis M-i arvutamine graafikut kunagi ei aktsepteeri.)

Fagin näitas, et see pole isoleeritud näide; iga piiratud graafide NP omadus on defineeritav teise astme loogika Σ-1-1 lausega. Ja vastupidi, iga Σ-1-1 lause määratleb NP omaduse. Ja graafikute asemel võime kasutada suunatud graafikuid või muid piiratud struktuure. Fagini teoreem väidab, et piiratud struktuuride omadus on NP omadus ainult siis, kui see on defineeritav by-1-1 teise järgu lausega.

3. Üldine semantika

Eelmises jaotises käsitletud „standardsemantika” põhijooneks on see, et ühekohalisest predikaatmuutujast X kvantifikaator ∀ X ulatub diskursuse universumi kogu võimsuskomplekti ulatuses. Oleme näinud, et see funktsioon annab teise astme keeltele kõrge väljendusvõime.

Kuid kas me tõesti tahame, et kvantifikaator ∀ X ulatuks üle tegeliku seatud võimsuse? Predikativist vaidleb vastu sellele, et võimsuse määramise operatsioon pole mõttekas. Ja isegi klassikaline matemaatik tunnistab, et võimsuse seadmisel on mõned varjatud omadused. Järjepidevuse hüpoteesi sõltumatus illustreerib ühte sellist hägusust. Kui meie eesmärk on uurida matemaatika aluseid, võib olla mõistlik mitte võtta enesestmõistetavana seda, et me teame juba kõiki energiakomplekte.

Teise järgu loogika üldise semantika kontseptsioon väldib igasugust pretensiooni, et võimsuse seadistatud toiming on fikseeritud hästi mõistetav ressurss. Selle asemel tuleb vahetult täpsustada kvantifikaatori vahemik ∀ X.

Teise astme keele üldise eelstruktuuri all peame silmas tavapärases tähenduses struktuuri (diskursuse universum pluss mitteloogiliste sümbolite tõlgendused) koos täiendavate komplektidega:

• Iga positiivse täisarvu n-koha suhte universum n. See peab olema n-suhete kogum diskursuse universumis. Eelkõige peab 1-kohaline universum olema mingi universumi alamhulkade kogum. Seega on see osa (võib-olla kõik, võib-olla mitte) universumi võimasüsteemist.
• N-koha funktsiooni universum iga positiivse täisarvu n jaoks. See peab olema n-koha funktsioonide kogum diskursuse universumis.

Üldise eelstruktuuri M jaoks on loomulik viis määratleda, mida tähendab teise astme valem φ, mis peab olema täidetud struktuuris M objektide omistamisega the vabadele muutujatele, mis jälle kirjutatakse M ⊨ φ [s]. Teise järgu kvantifikaatorid on nüüd määratletud vastavas universumis ulatuma. Ak-koha predikaatmuutuja P korral

M ⊨ ∀ P φ [s] kui iga k-asendi seose Q kohta k-koha seose universumis on meil M ⊨ φ [s ']

kus s 'erineb s-st ainult seose Q määramisel predikaatmuutujale P. Samamoodi on ak-koha funktsiooni muutuja F korral

M ⊨ ∀ F φ [s] kui iga k-koha funktsiooni G korral k-koha funktsioonis universumis on meil M ⊨ φ [s ']

kus s 'erineb s-st ainult funktsiooni G omistamisel funktsioonimuutujale F. Teise järgu lause σ (st vaba muutujata valemi) korral pole ülesanne s enam asjakohane ja võime ühemõtteliselt rääkida σ tõest või vääritest üldises eelstruktuuris M (et on, võime öelda, et M on või ei ole σ mudel).

Kuid teise järgu loogika huvides ei taha me tegelikult, et 1-kohaline universum oleks universumi alamhulkade suvaline kogum. Võimalik, et me ei tea kõike energiatarbimisega seotud toimingutest, kuid teame selle kohta mõnda asja. Tegelikult tähendab üldiste eelstruktuuride kasutamine teise astme keele käsitlemist mitmekordse esimese järjekorra keelena.

On mõned universumi alamhulgad, millest me teame, sest me saame neid määratleda. See tähendab, et oletame, et φ on valem, milles ainult muutuja u on vaba. Siis hulk set, mis defineeritakse M-is, on komplekt, mis koosneb M kõigist liikmetest a, nii et φ rahuldub M-ga, kui a on määratud u-ga. Seda ideed saab laiendada. Oletame, et φ-l on ainult vabad muutujad u, v, w, x, Y ja Z (kus Y on m-koha predikaatmuutuja ja Z on n-koha funktsioonimuutuja). Oletame, et c ja d on (individuaalse) universumi liikmed | M | M-st, et E on M 'sm-koha suhte universumis ja F on M' sn-koha funktsiooni universumis. Siis defineeritakse binaarsuhe φ parameetrites c, d, E M ja F on | elementide paari <a, b> hulk | M | nii, et φ on rahul M-ga, kui selle muutujad u, v, w, x, Y,ja Z on tähistatud vastavalt a, b, c, d, E ja F. See tähendab, et see on binaarne suhe:

{<a, b> | M ⊨ φ (u, v, w, x, Y, Z) [a, b, c, d, E, F]}

Ilmselt saab seda mõistet üldistada olukorras, kus aktuaarne seos on määratletud mis tahes konkreetse parameetri hulgast.

Siis on mõistlik piirata tähelepanu üldistele eelkonstruktsioonidele, mis on määratletavuse piires suletud. Niisiis on äsja kirjeldatud olukorras mõistlik eeldada, et M 2-aaruselise seose universum sisaldab binaarset suhet, mis φ määratleb eelkonstruktsiooni parameetrite järgi. See tähendab, et me ootame lauset

∀ w ∀ x ∀ Y ∀ Z ∃ R ∀ u ∀ v [Ruv ↔ φ (u, v, w, x, Y, Z)]

et olla tõsi M-is. Nimetage sellised lausete mõistmise aksioomid.

Teise astme keele üldise ülesehituse all (nimetatakse ka Henkini struktuuriks) peetakse üldist eelstruktuuri, milles kõik arusaamise aksioomid (kõigi valemite puhul) on õiged. (Siin võivad φ sisaldada kvantitaate predikatiivsete muutujate suhtes, nii et ka impreditatiivsed mõistmise aksioomid peavad paika. 5. jaotises kaalume alternatiivide kasutamist täielikuks mõistmiseks.) Üldiste struktuuride hulgas on sellised, milles 1-kohaline universum on üksiku universumi tegelik võimsus ja nii edasi. (Nimetage sellist üldist ülesehitust absoluutseks.) Kuid neid võib olla ka teisigi.

Teise astme keele jaoks saame üldsemantika (mida nimetatakse ka Henkini semantikaks), võttes arvesse kõiki üldisi struktuure. See tähendab, et lause σ peaks kehtima üldises semantikas, peab see olema tõene kõigis üldstruktuurides. See on tugevam nõue kui öelda, et σ kehtib standardsemantikas. Standardsemantikas kehtiv lause vastab tõele nendes üldstruktuurides, mille jaoks 1-kohaline universum on individuaalse universumi täielik võimu komplekt jne. Kuid selline lause σ võib osutuda mõnes üldstruktuuris valeks (st ¬σ-l võib olla üldine mudel).

Üldise semantika põhijooneks on tüüp „miski peale”: teise järgu loogika koos üldise semantikaga pole midagi muud kui esimese järgu loogika (mitmeti sorteeritud) koos mõistmise aksioomidega. Seega kehtib lause üldises semantikas, kui seda mõistavad loogiliselt (esimese astme loogikas) mõistmise aksioomide kogumid.

Esimese astme loogika vähendamine annab järgmised tulemused korraga:

• (Loendatavus) Teise astme keeles, kus on väga palju mitteloogilisi sümboleid, on lauses üldloendis kehtivad lausekomplektid arvutatavad. See kehtib seetõttu, et arusaadavuse aksioomide kogum on arvutatav kogum (st rekursiivne kogum).
• (Kompaktsus) Lausekomplektil on üldine mudel, kui igal piiratud alamhulgal on üldmudel.
• (Löwenheim – Skolem) Kui lausekomplektil on üldmudel, siis sellel on loendatav üldmudel.

Kõigil neil kolmel juhul on terav kontrast standardsemantika olukorraga, mida on käsitletud 2. jaos. Lisaks sellele võib teise astme loogika jaoks anda deduktiivse kalkulatsiooni (kohandatud esimese järgu loogikast ja täiendatud mõistmise aksioomidega) mis on üldise semantika jaoks täielik.

Võrdluseks: aksiomaatiline kogumiteooria (ZFC öelda) on esimese järjekorra teooria; komplekteerimisteooria mudel peab andma energiatarbimise komplekti. Kuid komplektiteooria keeles on teatud kõrgema astme aspekte, kuna see võimaldab meil rääkida komplektidest, komplektide komplektidest ja nii edasi.

Äärmuslikul juhul struktuuri M korral, milles kõik seosed on määratletavad (nt ühepunktilise universumiga struktuur), langeb üldine semantika kokku tavalise semantikaga.

4. Kõrgema järgu loogika

Teise järgu loogika juures pole vaja peatuda; saab edasi minna. Keelele võib lisada sümbolid, millel on ülipredikaat, mis võtab argumentidena nii üksikute sümbolite (muutujad või konstandid) kui ka predikaatmärgid. Ja siis saame lubada kvantifitseerimist ülipregaatide sümbolite kohal. Ja siis saame edasi minna.

(Lugejat tuleb hoiatada, et kirjanduses on järjekorra loendamiseks kaks erinevat viisi. Vastavalt ühele skeemile võimaldab kolmanda astme loogika ülipredikaadi sümbolite vaba esinemist ja neljanda järgu loogika võimaldab neid kvantifitseerida. Teise skeemi kohaselt võimaldab kolmanda astme loogika juba superpredikaadi sümbolite kvantifitseerimist.)

Tüüpide teooria tasemeni jõuame pärast ω sammu. Ja jätkumine piiritletud piirkonda on mõeldav.

Me nägime, et kuigi esimese astme loogika kehtivate valemite komplekt V1 on arvutatav, on vastav teise astme loogika vastav komplekt V² (koos standardsemantikaga) tunduvalt keerukam. See nähtus ei jätku kõrgemates klassides.

Mõnes mõttes on võimsuse määramise toiming määratletav teise järgu loogikas. Vaatleme keelt, kus on ühekohaline predikaadisümbol I (üksikisikute jaoks), ühekohaline predikaadisümbol S (komplektide jaoks) ja kahekohaline predikaadisümbol E (liikmesuhte jaoks). Seejärel väljendada mõtet, et S on I jõukomplekt, saame kasutada järgmise nelja lause kooslust (nimetame seda σ):

∀ x (Ix + Sx), kus “+” tähistab eksklusiivset disjunktsiooni

∀ x ∀ y (Exy → Ix & Sy)

∀ x ∀ y (Sx & Sy & ∀ t (Etx ↔ Ety) → x = y) (laiendavus)

∀ X ∃ y (Sy & ∀ (See → (Ety ↔ Xt)))) (mõistmine).

On selge, et σ vastab mis tahes struktuurile, mille universum on komplekti A ja selle võimsuskogumi P (A) eraldunud liit ja mis määrab A punktile I, P (A) väärtusele S ja omistab liikmesuhte ∈ E-le. Ja vastupidi, olgu M suvaline σ mudel (standardses semantikas). Olgu f üks-ühele funktsioon alates M-i I tõlgendusest kogumile A, mis on lahutatud tema võimsuskomplektist (selline komplekt on alati olemas). Laiendage f kogu M-i universumiga, määratledes M-i S-i tõlgenduses iga s-i jaoks

f (s) = {f (i) | M ⊨ E [i, s]}

(see tähendab, et f (s) on A-seeria asjade kogum, mis M arvates kuulub s-i). Siis f on isomorfism M-st struktuurini, mille universum on hulga A ja selle võimsuskogumi P (A) eraldatav liit ja mis määrab A punktile I, P (A) väärtusele S ja määrab liikmesuhte ∈ E. Nii jämedalt öeldes määratleb σ võimsuse seatud toimingu “isomorfismi piires”.

Sarnaselt võime määratleda isomorfismi piires I × I võimsuskogumi, st I binaarsuhete komplekti. Ja nii edasi.

See toiteseadme teise järgu väljendatavus võimaldab simuleerida kõrgema järgu loogikat teises järjekorras. Täpsemalt öeldes on meil Hintikka (1955) järgmine tulemus: iga kõrgema järgu loogika valemi φ jaoks (keeles, kus on lõplikult palju mitteloogilisi sümboleid) leiame efektiivselt teise astme loogika lause ψ: võrdõiguslikkuse keel), nii et φ kehtib ainult siis, kui ψ kehtib. Lause ψ konstrueerimiseks laiendatakse esmalt keelt, lisades sümboleid erinevat tüüpi universumite (indiviidid, indiviidide kogumid jne) ja nendesse universumidesse kuulumise jaoks. Siis on φ kehtivus samaväärne teise järgu valemi kehtivusega

Universumid on õigesti paigutatud → φ *

kus φ * on sobiv relativisatsioon of-le. Lõpuks võime universaalsete kvantifikaatorite eesliide lisada lause ψ saamiseks võrdsuse keeles.

Seega on seitsmeteistkümnenda järgu loogika kehtivuskogum redutseeritavalt arvutatav väärtuseks V ² (=), mis on võrdsuse keeles kasutatava teise järgu kehtivuskogum. (Tegelikult on need kaks komplekti ka isomorfsed.) Nii et selles aspektis ei suurene kõrgema järgu loogika keerukus järjekorraga. Sellest järeldub, et komplekt V ² (=) on väga keerukas. Saame laiendada oma varasemat tähelepanekut, et see pole teise astme aritmeetikas määratletav; seda ei saa määratleda ka kõrgema astme aritmeetikas. Montague 1965. aastal laiendas seda piirmääratuks. Sel ajal kuuldi teda ütlemas, et kogum V ² (=) ei peitu üheski Kleene'i hierarhias „minevik, olevik ega tulevik”.

Fakt, et me võime võimsuse komplekti operatsiooni väljendada teise astme loogikas (ja saab protseduuri korrata), annab teise astme loogikale suure osa komplekti teooria ekspressiivsusest. Quine on väitnud, et teise astme loogika pole tegelikult loogika, vaid seab teooria maskeeritult. Ja Robert Vaught on kommenteerinud, et teise astme loogika uurimine oli nagu “komplekti teooria standardmudeli” uurimine.

V ² (=) keerukus ei muutu palju, kui kehtestame lausete kvantitatiivsele kujule piiranguid. Eelnev kõrgema astme loogika taandamine annab Π-1-2 lauset, seega võime järeldada, et võrdõiguslikkuse keeles kehtivate Π-1-2 lausete komplekt on isomorfne täisväärtusele V ² (=). See puudutab parimat võimalikku tulemust. Kehtivate lausete The-1-1 komplekt on täielik arvutatav loetav komplekt; kui langetame universaalsed teise järgu kvantifikaatorid, vaatame esimese järgu valemeid. Võrdõiguslikkuse keeles kehtivate lausete Σ-1-1 komplekt on täielik koekomplekt, st arvutatavalt loetava komplekti komplement. (Lause ∃ P φ (P) vastab tõele igas nullist erinevas kardinaalsuses, kui elementaarsel lausel φ (P) on iga piiratud suurusega mudeleid, kaasomadusi. Ja Turingi masinale saab tõhusalt määrata elementaarse lause, millel on igas piiratud suuruses mudelid, kui masin kunagi ei peatu.) Kehtivate Σ-1-2 lausete võrdsuse keel on võrdselt isomorfne ka täisväärtusega V ² (=), kuid see asjaolu nõuab teistsugust tõestust.

5. Teise järgu numbriteooria süsteemid

Aritmeetika keel (0, S, <, + ja ×) on oluline matemaatika aluste jaoks. Aksioomidena võime võtta tavalisi Peano postulaate, sealhulgas teise astme induktsiooni aksioomi. Tavalises semantikas on Peano postulaatide ainus mudel, kuni isomorfism, tavaline aritmeetika mudel. Niisiis on nende aksioomide poolt genereeritud teooria (standardses semantikas) lihtsalt tõelise aritmeetika teise astme teooria.

Kuid oletame, et arvestame selle asemel üldise semantikaga. Peano postulaatidel on üldised mudelid, mis võivad tavalisest mudelist erineda kahel (või mõlemal) viisil. Peano postulaatide mittestandardsete üldmudelite konstrueerimiseks, mis sisaldavad lõpmata palju numbreid, saame kasutada kompaktsusteoreemi. Samuti võime leida Peano postulaatide üldisi mudeleid, milles komplektide universum on väiksem kui üksiku universumi täisvõimsuse komplekt (st üldmudelid, mis pole absoluutsed). Tõepoolest, iga loendatav üldmudel peab olema selline.

Üldiste mudelite kontekstis lisame valiku jaoks täiendava aksioomi skeemi:

∀ n ∃ X φ (n, X) → ∃ Y ∀ n φ (n, {t | ynt})

vajaduse korral universaalsete kvantifikaatoritega. (Siin saadakse valem, mis on kirjutatud kui φ (n, {t | Ytn}) väärtusest φ (n, X), asendades iga termini Xu terminiga Ynu.)

Peano postulaadid on piisavalt tugevad, et pakkuda meile sidumisfunktsioone. Järelikult määrab üldmudeli puhul selle 1-kohaline suhte universum iga k-i jaoks täielikult tema k-koha suhte universumi.

Traditsiooniline terminoloogia on viidata teise järgu numbriteooriale analüüsina. Nimi tuleneb asjaolust, et naturaalarvude komplektide abil on võimalik tuvastada reaalarvud. Naturaalarvude komplektide teisest järku kvantifikaatorit saab seejärel vaadata reaalarvu kvantifikaatorina. Nime sobivus on kahtluse alla seatud, kuid selle kasutamine on väljakujunenud. Seetõttu peame analüüsimudeli all silmas Peano postulaatide üldmudelit koos valikuga. Üldise mudelina peab loomulikult iga analüüsimudel vastama kõigile arusaamise aksioomidele; hiljem kaalume selle nõude nõrgendamist.

Olgu A 2 teooria, mille genereerib Peano valikuga postulaate (üldises semantikas). Siis A 2 on tõelise teise järgu aritmeetika täielik arvutatav loetav alamhulk. A 2 sisaldab iga tõest Σ-0-1 lauset. See ei sisalda kõiki õigeid Π-0-1 lauseid.

Tugevama teooria saame, piirates tähelepanu analüüsimudelitele, mis erinevad tavalisest mudelist ainult kahest eespool kirjeldatud viisist. See tähendab, et määratlege ω-analüüsimudel analüüsi mudeliks, milles individuaalne universum on tegelik looduslike arvude kogum ja sümbolitel 0 ja S on tavalised tõlgendused. (Järelikult on sümbolitel <, + ja × oma tavapärased tõlgendused.) Analüüsimudeli komplekteeritud universum peab seega moodustama mingi osa (võib-olla kogu) naturaalarvude võimsuse komplektist, kuid see peab olema selline et täielik mõistmine on rahul.

Ω-mudelite kaalumise motivatsiooni võib öelda järgmiselt. Naturaalarvude komplekt on meil arusaadav või nii, nagu meile meeldib mõelda. Kuid meil pole midagi sarnast arusaama naturaalarvude komplekti võimsuskomplektist. Seega on mõistlik hoida kindel osa selles osas, milles me kindlad oleme, kuid jätta osa, milles me pole nii kindlad, tõlgendamise lahtiseks.

Analüüsi model-mudeli määrab täielikult kindlaks määratud universum. Kuna meil on sidumisfunktsioonid, mis on esimese astme piirides määratletavad, määrab komplekteeritud universum binaarsete suhete universumi jne. Löwenheimi – Skolemi argument näitab, et on olemas ω-mudelid analüüsitavate loendatava universumiga.

Mis tahes ω-analüüsimudeli puhul on tõelised esimese astme laused täpselt samad, mis tavalises mudelis. Kuid ω-mudelid võivad teise astme lausetes erineda. Olgu A ω ω-mudelite teooria, see tähendab, et lausekomplekt vastab tõele kõigis ω -mudelites. Siis laieneb A A A 2. See on täielik Π-1-1 komplekt. See sisaldab iga tõelist Π-1-1 lauset; see ei sisalda kõiki õigeid Σ-1-1 lauseid.

Reegli we all peame silmas järeldust, mis tuletab ∀ x φ (x) eeldustest φ (0), φ (1), φ (2),…. Oletame, et lisame selle reegli tavalisele loogilisele aparaadile ja vaatame, mis siis Peano postulaatidest valikuliselt järeldatav on. Dedu-reegli abil tehtud „mahaarvamine” on üldiselt lõpmatu, kuid see peab olema hästi põhjendatud. Pole raske aru saada, kas mõni sel viisil tuletatav lause on tähesuuruses. Vastupidiselt kehtib täielikkuse teoreem: A-lause igas lauses on kirjeldatud tüüpi lahus.

1961. aasta artiklis kirjeldas Andrzej Mostowski võimalust astuda samm edasi veelgi tugevama teooria poole. Oletame, et me oleme valmis pidama mitte ainult tellimustüüpi ω piisavalt arusaadavaks, vaid isegi hästi korraldavaks mõisteks. Defineerige β-analüüsimudel ω-mudeliks koos lisaomadustega, mida mudeli korraldused, mis tunduvad olevat korralikud, tegelikult on. See tähendab, et analüüsi M-mudel M on β-mudel, kui iga M-i tellimissuhe (naturaalarvudel) omadusega, et M-i mittetühjades komplektides on alati kõige vähem liikmeid, on tegelikult hästi korraldav.

Siis osutub lausete A β, mis on tõesed kõigis β-mudelites, täielik Π-1-2 komplekt. See sisaldab iga tõest Π-1-2 lauset; see ei sisalda kõiki õigeid Σ-1-2 lauseid. On selge, et meil on kaasamised

A 2 ⊆ A ω ⊆ A β ⊆ Tõeline teise astme aritmeetika.

Näiteks on ZF-i komplekti teooria transitiivse ∈-mudeli arvuteoreetiline osa alati β-analüüsimudel. Kuid me võime luua β-mudeli ilma tugevate eeldusteta. Tegelikult on kõige väiksem β-mudel ja seda saab konstrueerida viisil, mis meenutab Gödeli määratlust kokkupandavate komplektide L-klassi kohta.

Lõpuks tuleb mainida, et on kontekste, kus sobivad teise järgu aritmeetika teooriad, mille mõistmine on väiksem kui täielik. Näiteks võib võtta Peano postulaatide antud ACA teooria koos arusaamise aksioomidega ainult esimese järgu valemite jaoks. Sellised teooriad on osutunud rakendatavateks pöördtemaatika uurimisel.

Bibliograafia

• Boolos, George, 1975. “Teise järgu loogikast”, The Journal of Philosophy, 72: 509–527. Samuti filmis Logic, Logic and Logic, autor George Boolos, Cambridge, MA: Harvard University Press, 1998, lk 37–53.
• Church, Alonzo, 1956. Sissejuhatus matemaatilisse loogikasse, 1. köide. Princeton: Princeton University Press.
• –––, 1972. „Kõrgema järgu funktsionaalsete kalkulite aksioomid” loogikas ja kunstis: esseed Nelson Goodmani, Richard S. Rudneri ja Israel Scheffleri (toim) auks, Indianapolis ja New York: Bobbs-Merrill Company, lk 197–213.
• Enderton, Herbert B., 2001. Loogika matemaatiline sissejuhatus, teine trükk. San Diego: Akadeemiline ajakirjandus.
• Fagin, Ronald, 1974. “Üldistatud esimese järgu spektrid ja polünoomiajal tuvastatavad komplektid” arvutamise keerukuses, Richard M. Karp (toim), SIAM-AMS Proceedings, vol. 7, Providence: American Mathematical Society, lk 43–73.
• Garland Stephen J., 1974. „Teise järgu kardinalide iseloomustatavus” aksiomaatilise komplekti teoorias, Thomas J. Jech (toim), Proceedings of Symposia in Pure Mathematics, vol. 13, 2. osa, Providence: American Mathematical Society, lk 127–146.
• Grzegorczyk, Andrzej, A. Mostowski ja C. Ryll-Nardzewski, 1958. “Klassikaline ja ω-täielik aritmeetika”, The Journal of Symbolic Logic, 23: 188–205.
• Henkin, Leon, 1950. “Tüüpide teooria terviklikkus”, The Symbolic Logic Journal, 15: 81–91.
• Hintikka, K. Jaakko, 1955. “Reduktsioonid tüüpide teoorias” kahes sümboliloogikat käsitlevas artiklis, Acta Philosophica Fennica, nr 8, Helsingi, lk 57–115.
• Montague, Richard, 1965. “Kõrgema järgu loogika vähendamine”, Theory of Model, JW Addison, Leon Henkin ja Alfred Tarski (toim.), Amsterdam: North-Holland Publishing Co., lk 251–264.
• Mostowski, Andrzej, 1961. “Infinitistlikel tõestusreeglitel põhinev ametlik analüüsi süsteem” infinitistlikel meetoditel, Varssavi: Państwowe Wydawnictwo Naukowe ja Oxford, London, New York ja Pariis: Pergamon Press, lk 141–166.
• Orey, Steven, 1956. “ω-järjepidevusest ja sellega seotud omadustest”, The Journal of Symbolic Logic, 21: 246–252.
• Shapiro, Stewart, 1991. Sihtasutused ilma fundamentaalsuseta: teise astme loogika juhtum. Oxford: Oxford University Press.
• Simpson, Stephen, 1999. Teise järgu aritmeetika alamsüsteemid. Berliin: Springer.
• Väänänen, Jouko, 2001. “Teise järgu loogika ja matemaatika alused”, Sümboolse loogika bülletään, 7: 504–520.

Akadeemilised tööriistad

	Kuidas seda sissekannet tsiteerida.
	Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
	Vaadake seda sisestusteema Indiana filosoofia ontoloogia projekti (InPhO) alt.
	Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

[Palun võtke soovitustega ühendust autoriga.]