Logika Druhého A Vyššieho Poriadku

2023 Autor: Noah Black | [email protected]. Naposledy zmenené: 2023-11-26 16:14

Vstupná navigácia

• Obsah vstupu
• Bibliografia
• Akademické nástroje
• Náhľad priateľov PDF
• Informácie o autorovi a citácii
• Späť na začiatok

Logika druhého a vyššieho poriadku

Prvýkrát publikované 20. decembra 2007; podstatná revízia St 4. marca 2009

Logika druhého poriadku je rozšírenie logiky prvého poriadku, kde okrem kvantifikátorov, ako napríklad „pre každý objekt (vo vesmíre diskurzu)“, má človek kvantifikátory, ako napríklad „pre každú vlastnosť objektov (vo vesmíre diskurzu).). Toto rozšírenie jazyka zvyšuje jeho výraznú silu bez pridávania nových neslogických symbolov, ako sú nové predikátové symboly. V prípade klasickej rozšírenej logiky (ako v tejto položke) je možné vlastnosti identifikovať pomocou množín, takže logika druhého poriadku nám poskytuje kvantifikátor „pre každú množinu objektov“.

Existujú dva prístupy k sémantike logiky druhého poriadku. Líšia sa interpretáciou vety „pre každú skupinu objektov“. Má to nejaký pevný význam, na ktorý sa môžeme odvolávať, alebo musíme brať do úvahy rôzne významy, ktoré môže mať táto veta? V prvom prípade (ktorý sa bude nazývať štandardná sémantika) považujeme za samozrejmé určité matematické pojmy. V druhom prípade (ktorý sa bude nazývať všeobecná sémantika) sa oveľa menej považuje za samozrejmosť. V tomto prípade, aby bola veta považovaná za platnú, bude musieť platiť za všetkých prípustných významov vety „pre každú skupinu objektov“.

• 1. Syntax a preklad
• 2. Štandardná sémantika
• 3. Všeobecná sémantika
• 4. Logika vyššieho poriadku
• 5. Systémy teórie čísel druhého rádu
• Bibliografia
• Akademické nástroje
• Ďalšie internetové zdroje
• Súvisiace záznamy

1. Syntax a preklad

V symbolickej logike bude vzorec (Px → Px) pravdivý, bez ohľadu na to, ktorý objekt vo vesmíre diskurzu je priradený premennej x. To znamená, že ∀ x (Px → Px) bude pravdivé, bez ohľadu na to, ktorá podskupina vesmíru diskurzu sa používa na interpretáciu predikátového symbolu P. Nie je to však nič iné ako to, že vzorec ∀ P ∀ x (Px → Px) je pravdivý, bez ohľadu na to?

V jazykoch prvého poriadku sú niektoré veci, ktoré môžeme povedať, a iné, ktoré nemôžeme. Predpokladajme napríklad, že chceme vyjadriť fakty o aritmetike prirodzených čísel. To znamená, že chceme vyjadriť fakty o štruktúre (N; 0, S, <, +, ×) pozostávajúcej zo súboru N = {0, 1, …} prirodzených čísel spolu so spoločnými aritmetickými operáciami a vzťahmi. A chceme používať jazyk prvého poriadku s kvantifikátormi ∀ interpretovanými ako „pre každé prirodzené číslo“a ∃ interpretovanými ako „pre nejaké prirodzené číslo“. Ďalej do jazyka zahrnujeme konštantný symbol 0 pre číslo nula, funkčný symbol S na jedno miesto pre následnú operáciu (ktorá aplikuje na prirodzené číslo dáva nasledujúce), dvojmiestny predikátový symbol <pre objednávací vzťah <na N,a dvojmiestne funkčné symboly + a × pre sčítanie a násobenie.

Týmto jazykom môžeme teraz symbolizovať mnohé skutočnosti, o ktorých vieme, že sú o prirodzených číslach pravdivé. Môžeme vytvoriť vetu ∀ x (x <Sx), ktorá napríklad vyjadruje, že každé číslo je menšie ako nasledujúce. Problém však nastáva, ak chceme vyjadriť „vlastnosť s dobrým usporiadaním“, že akákoľvek neprázdna množina prirodzených čísel má najmenšieho člena. Ak P je nový predikátový symbol na jednom mieste, potom

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

vyjadruje myšlienku, že P platí pre najmenšie číslo, ak pre všetky čísla platí vôbec. Tento vzorec platí v štruktúre (N; 0, S, <, +, ×), keď interpretujeme predikátový symbol P ako pravdivý z čísel v určitej konkrétnej množine - bez ohľadu na to, čo táto množina je - hovorí, že množina má najmenej člena, ak nie je prázdny. Teraz pridaním kvantifikátora ∀ P

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

dostaneme formalizáciu dobre usporiadaného majetku.

Jazyk logiky druhého poriadku rozširuje jazyk logiky prvého poriadku tým, že umožňuje kvantifikáciu predikátových symbolov a funkčných symbolov. Ako ukazuje predchádzajúci príklad, v aritmetickom jazyku druhého poriadku môžeme povedať, že prirodzené čísla sú dobre usporiadané. Vieme, že dobre usporiadaná vlastnosť nie je vyjadriteľná žiadnou vetou prvého poriadku, pretože neštandardné modely teórie (prvého poriadku) (N; 0, S, <, +, ×) nie sú nikdy dobre usporiadané, Logika druhého poriadku je teda skutočným rozšírením. To znamená, že môžeme preložiť niektoré vety v prirodzenom jazyku, ako napríklad „Vzťah <je dobre usporiadaný“, do jazyka logiky druhého poriadku, ktoré sa nedajú preložiť do jazyka logiky prvého poriadku.

Ako ďalší príklad môžeme (pomocou výberu) povedať, že vesmír diskurzu je nekonečný tým, že hovoríme, že existuje vesmírny tranzitívny vzťah tak, že každý prvok nesie vzťah k niečomu, ale nie k sebe samému:

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

Kvantifikátor druhého rádu „∃ R“tu vyjadruje existenciu nejakého binárneho vzťahu vo vesmíre. Pretože jediný predikátový symbol R je v rozsahu tohto kvantifikátora, veta nemá žiadne predikátové symboly otvorené pre interpretáciu. Ako je dobre známe, žiadna veta prvého poriadku nemá pre svoje modely presne nekonečné štruktúry.

Podrobnejšie je to, čo sa myslí jazykom druhého rádu: Jeden začína jazykom prvého poriadku a rozširuje ho nekonečným zásobovaním n-miestnych predikátových premenných pre každé kladné celé číslo n a nekonečným zásobovaním n - funkčné premenné pre každé kladné celé číslo n. (Funkčným premenným sa dá vyhnúť, ale to je iná záležitosť.) Pravidlá formovania dobre tvarovaných vzorcov sú zrejmé; predovšetkým je povolená univerzálna a existenciálna kvantifikácia pre každú premennú, či už ide o jednotlivú premennú, predikátovú premennú alebo funkčnú premennú.

Aby sme sa vrátili k príkladu prirodzených čísel, môžeme vyjadriť postuláciu indukcie Peano vetou druhého poriadku:

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

Táto veta vyjadruje myšlienku, že X platí pre všetky prirodzené čísla, ak platí pre 0 a jeho pravda v určitom počte y zaručuje jeho pravdivosť nástupcovi y, bez ohľadu na to, z ktorej množiny X môže platiť.

Napríklad v prípade množiny R reálnych čísel s obvyklým usporiadaním môžeme najmenšiu hornú hranicu vyjadriť vetou druhého poriadku:

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

Predchádzajúce príklady sú čerpané z matematických situácií. Existuje tiež zaujímavá možnosť viet v prirodzenom jazyku, pri ktorých sa zdá, že na ich formalizáciu potrebujú vzorce druhého rádu. George Boolos navrhol príklad: „Sú niektorí kritici, ktorí obdivujú iba jeden druhého.“Táto veta potvrdzuje existenciu skupiny jednotlivcov, ktorí majú určitý majetok; neznamená to napríklad, že existujú dvaja kritici, ktorí obdivujú jeden druhého a nikoho iného.

2. Štandardná sémantika

V predchádzajúcej časti je implicitný pojem pravdy vety druhého poriadku v štruktúre. Zoberme si štruktúru M = (A, R, …) pozostávajúcu z neprázdnej množiny A, ktorá slúži ako vesmír diskurzu, a niektorých vzťahov a funkcií na A interpretujúcich neslogické symboly. Potom chceme počítať vetu druhého rádu tvaru ∀ P φ (kde P je ak -place predikátová premenná) ako pravdivý v tejto štruktúre, ak pre každú množinu Q k-násobkov členov A máme toto φ platí v štruktúre, keď P je priradený vzťah Q.

Formálnejšie musíme definovať induktívne, čo to znamená, aby sa vzorec druhého poriadku φ uspokojil v štruktúre M = (A, R, …) pod priradením objektov voľným premenným v φ, ktoré sa zapíšu. M ⊨ φ [s]. Definícia pokračuje presne ako v prípade prvého poriadku, s výnimkou ďalších ustanovení pre kvantifikátory druhého poriadku. Pre ak -place predikátovú premennú P

M ⊨ ∀ P φ [s] iff pre každý k -ary vzťah Q na A máme M ⊨ φ [s ']

kde s 'sa líši od s iba priraďovaním vzťahu Q predikátovej premennej P. (Tu skratka „iff“označuje skratku „iba vtedy, ak len“.) Podobne pre premennú funkcie ak -place F, M ⊨ ∀ F φ [s] iff pre každú k-funkciu G na A, máme M ⊨ φ [s ']

kde s 'sa líši od s iba priraďovaním funkcie G funkčnej premennej F. Všimnite si, že táto definícia sa vzťahuje, v prípade 1-predikátovej predikčnej premennej, na všetky podmnožiny A, tj na celú množinu výkonu A. Je to práve táto vlastnosť, ktorá zodpovedá za mimoriadnu sémantickú silu jazykov druhého poriadku.

V prípade vety σ druhého poriadku (tj vzorec bez voľnej premennej) už priradenia nie sú relevantné a môžeme jednoznačne hovoriť o pravde alebo nepravdivosti σ v štruktúre M (to znamená, že môže povedať, že M je alebo nie je modelom σ). Teraz je možné vidieť najmä príklady z §1 prekladov z prirodzeného jazyka do jazyka logiky druhého poriadku, aby splnili svoje zamýšľané účely. Spojenie axiómov pre lineárne usporiadanie a vety

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

je pravda v štruktúre (A, <), ak vzťah <dobre objednáva množinu A. Veta

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

je pravdou v štruktúre, ak vesmír diskurzu je nekonečný súbor. Tento príklad ukazuje, že veta kompaktnosti neplatí pre logiku druhého poriadku. Ak nazveme vyššie uvedenú vetu λ∞ a necháme λ n vetu prvého poriadku „vo vesmíre je najmenej n rôznych vecí“, potom množina

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

nemá model, hoci každá konečná podmnožina má model.

Spojenie Peano postuluje

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

a Peano indukčný postulát

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

platí v štruktúre (A, f, e), ak je táto štruktúra izomorfná k (N, S, 0), prirodzené čísla s nástupníckou operáciou S a rozlišovacím prvkom 0. Spojenie týchto troch viet poskytuje príklad veta, ktorá je kategorická, to znamená, že má presne jeden model, až po izomorfizmus. Naproti tomu veta prvého poriadku môže byť kategorická, iba ak je jej jeden model konečný.

Podobne možno zoradené pole reálnych čísel (R, 0, 1, +, ×, <) charakterizovať až do izomorfizmu axiómami prvého poriadku pre usporiadané pole spolu s vetou druhého poriadku vyjadrujúcou najmenšie -viazaná vlastnosť. Je dobre známe, že každý model týchto viet musí byť izomorfný k usporiadanému poľu reálnych čísel. Tento príklad ukazuje, že Löwenheimova-Skolemova veta neplatí pre logiku druhého poriadku.

Predchádzajúce príklady ukazujú, že dve každodenné matematické štruktúry (N, S, 0) a (R, 0, 1, +, ×, <) sú charakterizovateľné v druhom poradí. To znamená, že každý má jednu axiómu druhého poriadku, ktorá je jediným modelom až po izomorfizmus. Jeden by sa mohol opýtať, aké ďalšie štruktúry by mohli byť charakterizovateľné v druhom poriadku. Samozrejme, existuje len nespočetne veľa takýchto štruktúr, až po izomorfizmus, pretože každá z nich potrebuje vetu.

Ďalej predpokladajme, že v týchto príkladoch existenciálne kvantifikujeme všetky nonlogické symboly (tj všetky predikátové symboly a funkčné symboly). Ak π (0, S,) je spojenie troch Peano postulátov, veta ∃ x ∃ F π (x, F) je veta v jazyku druhého poriadku rovnosti, to znamená, že nemá logickú logiku symboly vôbec.

Štruktúra pre jazyk rovnosti pozostáva jednoducho z neprázdneho vesmíru diskurzu; nejestvujú žiadne vzťahy alebo funkcie alebo rozlišujúce prvky. Takáto štruktúra je samozrejme determinovaná izomorfizmom jednoducho podľa jej mohutnosti. Vetu σ v jazyku rovnosti nech je jej spektrum triedou kardinálov, v ktorej je pravdou. Napríklad spektrum platnej vety je trieda všetkých nenulových kardinálnych čísel. Spektrum nevyhovujúcej vety je prázdne. Spektrum σ je doplnkom (relatívne k triede všetkých nenulových kardinálnych čísel) spektra σ. Spojenie a prerušenie viet vedie k priesečníku a zjednoteniu spektier. Vetu v jazyku rovnosti určuje podľa logického ekvivalentu jej spektrum.

Veta ∃ x ∃ F π (x, F), ktorú sme vytvorili z postulátov Peano, platí v nespočetne nekonečnej mohutnosti a nikto iný. Jeho spektrum je teda singletón. Povedzme, že kardinálne číslo κ je charakterizovateľné v druhom poriadku, ak existuje veta jazyka druhého poriadku rovnosti, ktorá platí pre kardinálnosť κ a len tam. (Nenulové konečné kardinály sú všetky charakterizovateľné v prvom poriadku.) Videli sme, že spočítateľný nekonečný kardinál je charakterizovateľný v druhom poriadku. Podobne môžeme ukázať, že sila kontinua je charakterizovateľná v druhom poriadku. Ak ρ (0, 1, +, ×, <) je veta druhého poriadku, ktorá charakterizuje zoradené pole reálnych čísel až po izomorfizmus, veta

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

je veta v jazyku druhého poriadku rovnosti, ktorá je pravdou v sile kontinua av žiadnej inej mohutnosti.

Jeden by sa mohol opýtať, aké ďalšie kardinálne čísla sú charakterizovateľné druhého rádu. Na skúmanie tejto otázky pozri dokument S. Garlanda z roku 1974. Takých kardinálov môže byť samozrejme len nespočetne veľa, pretože každý z nich má vetu.

Nie je ťažké pochopiť, že najmenej nespočetný kardinál je charakterizovateľný v druhom poriadku. Môžeme použiť vetu, ktorá hovorí, že vesmír je nekonečný, ale nedá sa spočítať a že akákoľvek nespočetná podmnožina je rovnaká ako celý vesmír. Máme teda vety κ a λ v jazyku druhého poriadku rovnosti, ktoré charakterizujú najmenej nespočetného kardinála a silu kontinua. Veta κ ↔ λ je platná veta, ak je hypotéza kontinua pravdivá, a iba vtedy. Môžeme konštatovať, že nie všetky problémy týkajúce sa logiky druhého poriadku sa nevyhnutne riešia v ZFC.

Preštudovaná teória PA, aritmetika Peano prvého rádu, sa samozrejme získa tým, že namiesto indukčného postulátu druhého rádu ∀ X [X 0 a ∀ y (Xy → XSy) → ∀ y Xy] sa použije zodpovedajúci schéma prvého poriadku

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

kde φ môže byť akýkoľvek vhodný vzorec prvého poriadku. Účinok tejto schémy je dobre známy; zabezpečuje, že každá definovateľná množina, ktorá obsahuje 0 a je uzavretá pod nástupcom, musí obsahovať všetko.

Predpokladajme, že analogicky začneme s našou axiomatizáciou usporiadaného poľa reálnych čísel druhého rádu a nahradíme axiomu s najmenšou hornou hranicou druhého rádu zodpovedajúcou schémou. Výsledkom je nekonečná množina axiómov prvého poriadku, ktorá zaručuje, že každá definovateľná množina, ktorá nie je prázdna a ohraničená, má najmenej hornú hranicu. Ich modely sa nazývajú skutočne uzavreté zoradené polia. Je zaujímavé, že tento koncept bol prvýkrát formulovaný algebraistami, nie logikmi.

Jedným z meraní sily logiky druhého poriadku je zložitosť súboru platných viet. Nech V ¹ je množina platných viet logiky prvého poriadku a nech V ² je sada platných viet druhej logiky. Presnejšie povedané, v logike prvého poriadku s jediným jednoduchým dvojmiestnym predikátovým symbolom P vieme, že množina V1 (P) platných viet je úplná vypočítateľná množina (tj úplná rekurzívne vymenovateľná množina). (Tu môžeme priradiť Gödelho čísla a zobraziť V ¹ (P) ako množinu prirodzených čísel, alebo rovnocenne ich môžeme zobraziť priamo ako množinu slov nad konečnou abecedou.) A Tarski zdôraznil, že množina V ¹ (=) platných viet v jazyku prvého poriadku rovnosti (bez logických symbolov vôbec) je rozhodnuteľné.

Pre porovnanie, nech V ² (=) je množina platných viet v jazyku rovnosti druhého poriadku. Aká je zložitosť tohto súboru?

Nech π je spojenie Peano postulátov a rekurzných rovníc na sčítanie a násobenie. Π je teda veta aritmetiky druhého rádu s 0, S, + a ×. Veta π je kategorická; jeho jediný model je (N, 0, S, +, ×), až po izomorfizmus. V dôsledku toho platí pre vetu σ v aritmetickom jazyku σ pravdivé v aritmetike, ak je podmienená (π → σ) platná. To ukazuje, že V ² (0, S, +, ×) nemôže byť aritmetický (tj nemôže byť aritmeticky definovateľný v prvom poriadku), aby sa neurčitá pravda v aritmetike nedala definovať v rozpore s Tarského teorémom. Teraz môžeme vyčísliť všetky logické symboly; veta φ (P) platí, ak je veta ∀ P φ (P) platná. Záver je, že V² (=) nie je aritmetický.

Je zaujímavé, že je to iba špička ľadovca. Na úvod môžeme ukázať, že V ² (=) nie je analytické, to znamená, že v aritmetike nie je možné definovať pomocou vzorca druhého poriadku. Dôkaz Tarského vety, ktorý ukazuje, že množina pravých viet prvého rádu aritmetiky nie je v aritmetike definovateľná v prvom poriadku, tiež ukazuje, že množina pravých viet druhého rádu v aritmetike nie je v aritmetike definovateľná v druhom poriadku. Zvyšok argumentu sa nemení. A neskôr uvidíme, že ešte viac je pravda.

Vo veľmi odlišnom smere R. Fagin preukázal prekvapujúce spojenie medzi témou vo výpočtovej zložitosti a definovateľnosťou druhého poriadku v konečných štruktúrach. Napríklad, konečný graf sa môže považovať za pár (V, E) pozostávajúci z neprázdnej vrcholovej sady V a symetrickej okrajovej závislosti E na V. Výrok, že graf môže byť správne zafarbený tromi farbami, môže byť vyjadrený vetou druhého poriadku: existujú podskupiny R, G, B, ktoré delia V tak, že dva vrcholy spojené hranou nie sú nikdy rovnakej farby. Táto veta je Σ-1-1, to znamená, že má tvar

[existenciálne kvantifikátory druhého poriadku] [vzorec prvého poriadku].

Je dobre známe, že byť trojfarebný je vlastnosťou NP grafu. To znamená, že je to vlastnosť, ktorú rozoznáva v polynomiálnom čase neurčitý Turingov stroj. (Existuje nedeterministický Turingov stroj M a polynóm p taký, že kedykoľvek (V, E), je vhodne kódovaný, je daný M, potom ak (V, E) je trojfarebný, potom nejaký výpočet M akceptuje graf v krokoch p (n), kde n meria veľkosť (V, E) a ak (V, E) nie je trojfarebný, potom výpočet M nikdy neakceptuje výpočet.)

Fagin ukázal, že to nie je izolovaný príklad; každá vlastnosť NP konečných grafov je definovaná Σ-1-1 vetou logiky druhého poriadku. A naopak, akákoľvek veta Σ-1-1 definuje vlastnosť NP. A namiesto grafov môžeme použiť riadené grafy alebo iné konečné štruktúry. Faginova veta uvádza, že vlastnosť konečných štruktúr je vlastnosťou NP iba vtedy, ak je definovateľná vetou druhého rádu Σ-1-1.

3. Všeobecná sémantika

Kľúčovou črtou „štandardnej sémantiky“diskutovanej v predchádzajúcej časti je to, že v prípade predikčnej premennej X na jednom mieste sa kvantifikátor ∀ X pohybuje v celej množine moci vesmíru diskurzu. Videli sme, že táto funkcia dáva jazykom druhého rádu vysokú mieru výraznosti.

Naozaj chceme, aby sa kvantifikátor ∀ X pohyboval v rozsahu skutočného výkonu? Prediktivista bude namietať, že operácia nastavenia sily nemá zmysel. A dokonca aj klasický matematik pripúšťa, že existujú určité nejasné vlastnosti operácie s elektrickým pohonom. Nezávislosť hypotézy kontinua ilustruje jednu takúto nejasnosť. Ak je naším cieľom študovať základy matematiky, mohlo by byť rozumné nepovažovať za samozrejmé, že už vieme všetko o energetických súboroch.

Koncepcia všeobecnej sémantiky pre logiku druhého poriadku vylučuje akékoľvek predstieranie, že operácia s nastaveným výkonom je pevne známym zdrojom. Namiesto toho sa musí priamo určiť rozsah kvantifikátora ∀ X.

Všeobecnou predštruktúrou pre jazyk druhého poriadku sa rozumie štruktúra v obvyklom zmysle (vesmír diskurzu plus interpretácie pre logické symboly) spolu s ďalšími množinami:

• N-miesto vzťahu vesmír pre každé kladné celé číslo n. Musí to byť zbierka národných vzťahov o vesmíre diskurzu. Obzvlášť musí byť 1-bodový vzťahový vesmír nejakou zbierkou podmnožín vesmíru. Je teda súčasťou (možno všetky, možno nie) súboru moci vesmíru.
• Vesmír funkcie n-miesta pre každé kladné celé číslo n. Musí to byť zbierka n-miestnych funkcií vo vesmíre diskurzu.

Pre všeobecnú predštruktúru M existuje prirodzený spôsob, ako definovať, čo znamená, že vzorec structure druhého poriadku φ sa uspokojí v štruktúre M pod priradením objektov voľným premenným v φ, ktoré sa znova zapíšu. M ⊨ φ [s]. Kvantifikátory druhého poriadku sú teraz definované tak, aby sa pohybovali v zodpovedajúcom vesmíre. Pre ak -place predikátovú premennú P

M ⊨ ∀ P φ [s] iff pre každý k -ary vzťah Q vo vesmíre k -place, máme M ⊨ φ [s ']

kde s 'sa líši od s iba priraďovaním vzťahu Q predikátovej premennej P. Podobne pre funkčnú premennú ak -place F, M ⊨ ∀ F φ [s] iff pre každú funkciu k -place G vo vesmíre funkcie k -place, máme M ⊨ φ [s ']

kde s 'sa líši od s iba priraďovaním funkcie G funkčnej premennej F. V prípade vety σ druhého poriadku (tj vzorec bez voľnej premennej) už priradenia nie sú relevantné a vo všeobecnej predštruktúre M môžeme jednoznačne hovoriť o pravde alebo nepravdivosti σ (je, môžeme povedať, že M je alebo nie je modelom σ).

Ale pre logiku druhého poriadku v skutočnosti nechceme, aby 1-miestny vzťahový vesmír bol svojvoľnou zbierkou podskupín vesmíru. Možno nebudeme vedieť všetko o operácii s napájaním, ale vieme o tom niečo. Použitie všeobecných predštruktúr v skutočnosti predstavuje zaobchádzanie s jazykom druhého poriadku ako s mnohými triedenými jazykmi prvého poriadku.

Existuje niekoľko podmnožín vesmíru, o ktorých vieme, pretože ich môžeme definovať. To znamená, že φ je vzorec, v ktorom sa vyskytuje iba premenná u zadarmo. Potom množina φ definuje v M množinu pozostávajúcu zo všetkých členov a z M tak, že φ je uspokojená v M, keď a je priradené k u. Túto myšlienku možno rozšíriť. Predpokladajme, že φ má iba voľné premenné u, v, w, x, Y a Z (kde Y je premenná predikátu m-miesto a Z je premenná funkcie n-miesta). Predpokladajme, že ca sú členmi (individuálneho) vesmíru M | z M, že E je v M 'sm -place vzťahu vesmíru, a že F je v M' sn -place funkcie vesmíru. Potom binárny vzťah φ definuje v M z parametrov c, d, E a F množinu párov <a, b> prvkov | M | taký, že φ je spokojný v M, keď jeho premenné u, v, w, x, Y,a Z sú priradené a, b, c, d, E a F. To znamená, že ide o binárny vzťah:

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

Tento koncept sa samozrejme dá zovšeobecniť na situáciu, keď je akárny vzťah definovaný z ktoréhokoľvek konkrétneho počtu parametrov.

Potom je rozumné obmedziť pozornosť na všeobecné predštruktúry, ktoré sú uzatvorené podľa vymedzenia. Preto je v práve opísanej situácii rozumné očakávať, že M 2-aryčný vzťahový vesmír bude obsahovať binárny vzťah, ktorý φ definuje z parametrov v predštruktúre. To znamená, že očakávame vetu

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

v M. Nazvite také axiómy s porozumením vety.

Všeobecnou štruktúrou pre jazyk druhého poriadku (tiež nazývaný Henkinova štruktúra) sa myslí všeobecná predštruktúra, v ktorej sú všetky axiómy porozumenia (pre všetky vzorce) pravdivé. (Tu φ môže obsahovať kvantifikátory nad predikátovými premennými, aby aj pravdivé implikatívne axiómy porozumenia boli pravdivé. V časti 5 zvažujeme alternatívy k „úplnému porozumeniu“.) Medzi všeobecné štruktúry patria tie, v ktorých je 1-bodový vzťahový vesmír skutočná sada moci jednotlivého vesmíru atď. (Nazvi takúto všeobecnú štruktúru ako absolútnu.) Ale môžu existovať aj iné.

Získame všeobecnú sémantiku (tiež nazývanú Henkinova sémantika) pre jazyk druhého poriadku zvážením všetkých všeobecných štruktúr. To znamená, že veta σ je platná vo všeobecnej sémantike, musí to platiť vo všetkých všeobecných štruktúrach. Toto je silnejšia požiadavka ako tvrdenie, že σ platí v štandardnej sémantike. Veta platná v štandardnej sémantike je pravdou v tých všeobecných štruktúrach, pre ktoré je 1-miestny vzťahový vesmír kompletnou silou jednotlivého vesmíru atď. Ale takáto veta σ sa môže v niektorých všeobecných štruktúrach ukázať ako nepravdivá (tj ¬σ môže mať všeobecný model).

Hlavnou črtou všeobecnej sémantiky je výsledok typu „nič okrem“: Logika druhého poriadku so všeobecnou sémantikou nie je nič iné ako logika prvého rádu (mnohoraké) spolu s axiomami porozumenia. Teda veta je platná vo všeobecnej sémantike, ak je logicky implikovaná (v logike prvého poriadku) množinou axiómov porozumenia.

Toto zníženie na logiku prvého poriadku prinesie naraz tieto výsledky:

• (Vyčísliteľnosť) V jazyku druhého poriadku s konečne mnohými neslogickými symbolmi je množina viet, ktoré sú platné vo všeobecnej sémantike, spočítateľná. Platí to preto, že množina axiómov porozumenia je kompabilná množina (tj rekurzívna množina).
• (Kompaktnosť) Súbor viet má všeobecný model, ak má každá konečná podmnožina všeobecný model.
• (Löwenheim – Skolem) Ak má množina viet všeobecný model, potom má spočítateľný všeobecný model.

V každom z týchto troch prípadov existuje výrazný kontrast k situácii štandardnej sémantiky, ktorá sa zvažuje v oddiele 2. Okrem toho je možné pre logiku druhého poriadku odvodiť deduktívny počet (upravený z logiky prvého poriadku a rozšírený o axiómy porozumenia). to bude úplné pre všeobecnú sémantiku.

Pre porovnanie, axiomatická teória množín (ZFC povedať) je teória prvého poriadku; model teórie množín musí poskytovať operáciu s energetickými súbormi. Jazyk teórie množín má však určité aspekty vyššieho poriadku, pretože nám umožňuje hovoriť o množinách, množinách množín atď.

V extrémnom prípade štruktúry M, v ktorej sú definované všetky vzťahy (napr. Štruktúra s jednobodovým vesmírom), sa všeobecná sémantika zhoduje so štandardnou sémantikou.

4. Logika vyššieho poriadku

Nie je potrebné sa zastavovať pri logike druhého poriadku; jeden môže pokračovať. Môžeme do jazyka pridať „super predikátové“symboly, ktoré berú ako argumenty jednotlivé symboly (buď premenné alebo konštanty), ako aj predikátové symboly. A potom môžeme povoliť kvantifikáciu nad super predikátnymi symbolmi. A potom môžeme pokračovať ďalej.

(Čitateľovi je potrebné dať pozor, aby v literatúre boli dva rôzne spôsoby počítania rádu. Podľa jednej schémy logika tretieho poriadku umožňuje, aby sa vyskytli super predikátové symboly, a logika štvrtého poriadku umožňuje ich kvantifikáciu. Podľa druhej schémy už logika tretieho poriadku umožňuje kvantifikáciu super predikátnych symbolov.)

Teóriu typov sme dosiahli po ω krokoch. Je mysliteľné pokračovanie v transfinite.

Videli sme, že hoci množina V1 platných vzorcov logiky prvého poriadku je počítateľne spočítateľná, zodpovedajúca množina V2 pre logiku druhého poriadku (so štandardnou sémantikou) je oveľa zložitejšia. Tento fenomén nepokračuje vo vyšších rádoch.

Existuje zmysel, v ktorom je operácia s nastaviteľnou silou definovateľná v logike druhého poriadku. Zvážte jazyk so symbolom I na jednom mieste predikátu I (pre jednotlivcov), na jednom mieste predikátnym symbolom S (pre množiny) a dvojmiestnym predikátnym symbolom E (pre členský vzťah). Potom, aby sme vyjadrili myšlienku, že S je mocnina I, môžeme použiť spojku (nazvanú σ) nasledujúcich štyroch viet:

∀ x (Ix + Sx), kde „+“označuje exkluzívne

disjunkčné spojenie ∀ x ∀ y (Exy → Ix a Sy)

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

∀ X ∃ y (Sy & ∀ t (It → (Ety ↔ Xt))) (porozumenie).

Je zrejmé, že σ platí v každej štruktúre, ktorej vesmír je disjunktívnym spojením množiny A a jej výkonovej sady P (A) a ktorá priraďuje A k I, priraďuje P (A) k S a priraďuje členský vzťah ∈ k E. A naopak, nech M je akýkoľvek model σ (v štandardnej sémantike). Dovoliť f je individuálna funkcia z M interpretácie I na množinu A, ktorá je disjunktná od jej množiny moci (vždy existuje taká množina). Rozšírte f na celý M vesmír tým, že pre každú s definujete M interpretáciu S

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

(to znamená, že f (s) je súbor vecí v A, ktoré M považuje za patriace do). Potom f je izomorfizmus z M na štruktúru, ktorej vesmír je disjunktívnym spojením množiny A a jej mocenskej sady P (A) a ktorá priraďuje A k I, priraďuje P (A) k S a priraďuje k nej členský vzťah ∈ E. Zjednodušene povedané, σ definuje postup nastavenia sily „v rámci izomorfizmu“.

V podobnom duchu môžeme v rámci izomorfizmu definovať množinu moci I × I, tj množinu binárnych vzťahov na I. A tak ďalej.

Táto expresibilita operácie množiny výkonov druhého poriadku umožňuje simulovať logiku vyššieho poriadku v rámci druhého poriadku. Konkrétnejšie, máme nasledujúci výsledok Hintikky (1955): Pre každý vzorec φ logiky vyššieho poriadku (v jazyku s konečne mnohými neslogickými symbolmi) môžeme efektívne nájsť vetu ψ logiky druhého poriadku (v jazyk rovnosti) taký, že φ platí, iba ak je platné ψ. Veta ψ je vytvorená tak, že sa jazyk najskôr rozšíri pridaním symbolov pre vesmír rôznych typov (jednotlivci, skupiny jednotlivcov, …) a pre členstvo v týchto vesmíroch. Potom je platnosť φ rovnocenná s platnosťou vzorca druhého poriadku

Vesmír je správne usporiadaný → φ *

kde φ * je vhodná relativizácia φ. Nakoniec môžeme prefix univerzálnych kvantifikátorov získať vetu obtain v jazyku rovnosti.

Takto je sada validít logiky siedmeho poriadku vypočítateľne zredukovateľná na V ² (=), sada validít druhého rádu v jazyku rovnosti. (V skutočnosti sú tieto dve skupiny vypočítateľne izomorfné.) Z tohto hľadiska sa zložitosť logiky vyššieho poriadku s týmto poradím nezvyšuje. Z toho vyplýva, že množina V ² (=) má vysoký stupeň zložitosti. Môžeme rozšíriť naše predchádzajúce pozorovanie, že nie je definovateľné v aritmetike druhého poriadku; nie je ani definovateľný v aritmetike vyššieho poriadku. Montague ju v roku 1965 rozšíril na transfinit. V tom čase bolo počuť, že množina V ² (=) neleží v Kleeneho hierarchii, „minulosti, súčasnosti alebo budúcnosti“.

Skutočnosť, že operáciu množiny môžeme vyjadriť v logike druhého poriadku (a môže opakovať postup), dáva logike druhého poriadku určitú veľkú časť expresivity teórie množín. Quine tvrdil, že logika druhého poriadku nie je v skutočnosti logikou, ale skôr zakrivenou teóriou. A Robert Vaught poznamenal, že štúdium logiky druhého poriadku bolo ako štúdium „štandardného modelu teórie množín“.

Zložitosť V ² (=) sa príliš nemení, ak stanovíme obmedzenia na kvantifikovateľnú formu viet. Predchádzajúce zníženie logiky vyššieho poriadku poskytuje Π-1-2 vety, takže môžeme dospieť k záveru, že množina platných valid-1-2 viet v jazyku rovnosti je vypočítateľne izomorfná s plným V ² (=). Ide o najlepší možný výsledok. Sada Π-1-1 platných viet je kompletná vypočítateľná množina; akonáhle upustíme univerzálne kvantifikátory druhého poriadku, pozeráme sa na vzorce prvého poriadku. Sada Σ-1-1 platných viet v jazyku rovnosti je úplnou množinou co-ce, tj doplnkom vypočítateľnej množiny. (Veta ∃ P φ (P) platí pre každú nenulovú kardinálnosť, ak má elementárna veta φ (P) modely každej konečnej veľkosti, čo je vlastnosť co-ce. A k Turingovmu stroju môžeme efektívne priradiť elementárnu vetu s modelmi každej konečnej veľkosti, ak sa stroj nikdy nezastaví.) Sada platných Σ-1-2 viet v jazyku rovnosti je tiež vypočítateľne izomorfná s plným V ² (=), ale táto skutočnosť si vyžaduje iný druh dôkazu.

5. Systémy teórie čísel druhého rádu

Jazyk aritmetiky (s 0, S, <, + a ×) je dôležitý pre základy matematiky. Ako axiómy môžeme brať obvyklé Peano postuláty, vrátane indukčného axiómu druhého poriadku. V štandardnej sémantike je jediným modelom Peano postulátov až po izomorfizmus zvyčajný model aritmetiky. Teória generovaná týmito axiómami (v štandardnej sémantike) je teda jednoducho teóriou druhého rádu aritmetiky.

Ale predpokladajme namiesto toho všeobecnú sémantiku. Peano postuláty majú všeobecné modely, ktoré sa môžu líšiť od zvyčajného modelu dvoma spôsobmi. Vetu o kompaktnosti môžeme použiť na zostavenie neštandardných všeobecných modelov postulátov Peano obsahujúcich nekonečne veľké množstvo. Môžeme tiež nájsť všeobecné modely postulátov Peano, v ktorých je vesmír množín menší ako plný výkon jednotlivého vesmíru (tj všeobecné modely, ktoré nie sú absolútne). Akýkoľvek všeobecný model, ktorý je možné spočítať, musí byť skutočne tohto druhu.

V kontexte všeobecných modelov pridávame ďalšiu schému axiómov na výber:

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

podľa potreby vopred určené univerzálnymi kvantifikátormi. (Tu vzorec, ktorý bol napísaný ako φ (n, {t | Ytn}), sa získa z φ (n, X) nahradením každého pojmu Xu termínom Ynu.)

Postuláty Peano sú dostatočne silné, aby nám poskytli párovacie funkcie. V dôsledku toho pre všeobecný model jeho 1-miestny vzťahový vesmír úplne určuje svoj vzťahový vesmír k-miesto pre každé k.

Tradičná terminológia sa odvoláva na teóriu čísel druhého rádu ako analýzu. Názov je odvodený od skutočnosti, že je možné identifikovať skutočné čísla pomocou množín prírodných čísel. Kvantifikátory druhého rádu nad množinami prirodzených čísel sa potom môžu považovať za kvantifikátory nad skutočnými číslami. Vhodnosť mena je otvorená otázkam, ale jeho používanie je dobre zavedené. Podľa modelu analýzy budeme teda myslieť všeobecný model postulátov Peano s výberom. Ako všeobecný model musí každý model analýzy samozrejme spĺňať všetky axiómy porozumenia; neskôr zvážime oslabenie tejto požiadavky.

Nech A 2 je teória generovaná Peanovými postuláciami s výberom (vo všeobecnej sémantike). Potom A2 je úplná vypočítateľne spočítateľná podmnožina aritmetiky druhého rádu. A 2 obsahuje každú skutočnú Σ-0-1 vetu. Neobsahuje každú skutočnú Π-0-1 vetu.

Silnejšiu teóriu môžeme získať obmedzením pozornosti na modely analýzy, ktoré sa líšia od zvyčajného modelu iba v druhom z dvoch vyššie opísaných spôsobov. To znamená, že definujeme ω-model analýzy ako model analýzy, v ktorom je jednotlivý vesmír skutočným súborom prirodzených čísel a symboly 0 a S majú svoje obvyklé interpretácie. (V dôsledku toho symboly <, + a × majú svoje obvyklé interpretácie.) Nastavený vesmír ω-modelu analýzy musí preto byť nejakou časťou (možno všetky) mocninnej sústavy prirodzených čísel, ale musí to byť taký toto plné porozumenie je uspokojené.

Motiváciu pre zváženie ω-modelov možno uviesť nasledovne. Máme jasné porozumenie - alebo tak radi myslíme - na súbor prírodných čísel. Nemáme však nič ako rovnaké chápanie množiny moci množiny prirodzených čísel. Je preto rozumné držať opravenú časť, o ktorej sme si istí, ale nechať otvorenú interpretáciu tej časti, o ktorej nie sme si istí.

Ω-model analýzy je úplne určený jeho stanoveným vesmírom. Pretože máme párovacie funkcie, ktoré sú definovateľné v prvom poriadku, nastavený vesmír určí vesmír binárnych vzťahov a tak ďalej. Argument Löwenheim – Skolem ukáže, že existujú ω-modely analýzy s počitateľným súborom vesmíru.

V každom ω-modeli analýzy sú skutočné vety prvého rádu presne také, aké platia pre obvyklý model. Ω-modely sa však môžu líšiť podľa viet druhého rádu. Nech ω je teória ω-modelov, tj množina viet pravdivá vo všetkých ω-modeloch analýzy. Potom A co rozširuje A 2. Je to kompletný súbor Π-1-1. Obsahuje každú pravú Π-1-1 vetu; Neobsahuje každú pravú Σ-1-1 vetu.

Pod pojmom ω- sa rozumie infinitárne pravidlo inferencie, ktoré vyvodzuje ∀ x φ (x) z predpokladov φ (0), φ (1), φ (2),…. Predpokladajme, že pridáme toto pravidlo do zvyčajného logického aparátu a uvidíme, čo je potom možné odvodiť z postulátov Peano s výberom. „Odpočet“pomocou pravidla ω bude vo všeobecnosti nekonečný, ale musí byť opodstatnený. Nie je ťažké vidieť, že akákoľvek veta, ktorú je možné takto odpočítať, je v Aω. Naopak, veta o úplnosti platí: Každá veta v A má odpočet opísaného druhu.

Andrzej Mostowski v roku 1961 opísal spôsob, ako ísť o krok ďalej, smerom k silnejšej teórii. Predpokladajme, že sme ochotní považovať nielen typ objednávky ω za dostatočne pochopený, ale aj za koncepciu správneho objednávania. Definujte β-model analýzy ako ω-model s dodatočnou vlastnosťou, ktorú sú usporiadania v modeli, ktoré sa javia ako správne usporiadania. To znamená, že ω-model M analýzy je β-model, ak každý vzťah usporiadania (na prirodzených číslach) v M s vlastnosťou, že neprázdne množiny v M majú vždy najmenej členov, je v skutočnosti dobre usporiadaný.

Potom sa množina viet ß, ktoré sú pravdivé vo všetkých modeloch β, ukáže ako kompletná množina Π-1-2. Obsahuje každú pravú Π-1-2 vetu; Neobsahuje každú pravú Σ-1-2 vetu. Je zrejmé, že máme inklúzie

A 2 ⊆ A ω ⊆ A β ⊆ Aritmetika pravého druhého poriadku.

Napríklad, teoretická časť tranzitívneho modelu of teórie množín ZF bude vždy p-modelom analýzy. Môžeme však skonštruovať β-model bez silných predpokladov. V skutočnosti existuje najmenší p-model a môže sa skonštruovať spôsobom, ktorý pripomína Gödelovu definíciu triedy L konštruktov.

Nakoniec treba uviesť, že existujú kontexty, v ktorých sú vhodné teórie aritmetiky druhého rádu s menej ako úplným porozumením. Napríklad je možné brať teóriu ACA danú Peanovými postuláciami spolu s axiomami porozumenia iba pre vzorce prvého poriadku. Ukázalo sa, že takéto teórie sú použiteľné pri štúdiu „reverznej matematiky“.

Bibliografia

• Boolos, George, 1975. „Logika druhého rádu“, The Journal of Philosophy, 72: 509–527. Tiež v Logic, Logic a Logic, George Boolos, Cambridge, MA: Harvard University Press, 1998, s. 37–53.
• Church, Alonzo, 1956. Úvod do matematickej logiky, zväzok 1. Princeton: Princeton University Press.
• –––, 1972. „Axiómy pre funkčné kalkulácie vyššieho poriadku“v odbore Logika a umenie: Eseje na počesť Nelsona Goodmana, Richarda S. Rudnera a Israel Schefflera (ed.), Indianapolis a New York: Bobbs-Merrill Company, 197–213.
• Enderton, Herbert B., 2001. Matematický úvod do logiky, druhé vydanie. San Diego: Academic Press.
• Fagin, Ronald, 1974. „Zovšeobecnené spektrá prvého rádu a rozoznateľné množiny polynomu,“v zložitosti výpočtov, Richard M. Karp (ed.), SIAM-AMS Proceedings, zv. 7, Providence: American Mathematical Society, s. 43 - 73.
• Garland Stephen J., 1974. „Kardínová charakterizácia druhého rádu“, v Axioatic Theory Theory, Thomas J. Jech (ed.), Proceedings of Symposia in Pure Mathematics, roč. 13, časť 2, Providence: American Mathematical Society, s. 127–146.
• Grzegorczyk, Andrzej, A. Mostowski a C. Ryll-Nardzewski, 1958. „Klasická a ω-úplná aritmetika“, The Journal of Symbolic Logic, 23: 188–205.
• Henkin, Leon, 1950. „Úplnosť v teórii typov“, Journal of Symbolic Logic, 15: 81–91.
• Hintikka, K. Jaakko, 1955. „Redukcie v teórii typov“, v dvoch dokumentoch o symbolickej logike, Acta Philosophica Fennica, č. 8, Helsinki, s. 57–115.
• Montague, Richard, 1965. „Reductions of High-Order Logic“, Theory of Modules, JW Addison, Leon Henkin a Alfred Tarski (eds.), Amsterdam: North-Holland Publishing Co., s. 251–264.
• Mostowski, Andrzej, 1961. „Formálny systém analýzy založený na infinitistickom pravidle dôkazu“, v Infinitistických metódach, Varšava: Państwowe Wydawnictwo Naukowe a Oxford, Londýn, New York a Paríž: Pergamon Press, s. 141–166.
• Orey, Steven, 1956. „Čo sa týka konzistencie a súvisiacich vlastností“, The Journal of Symbolic Logic, 21: 246–252.
• Shapiro, Stewart, 1991. Nadácie bez fundamentalizmu: prípad logiky druhého poriadku. Oxford: Oxford University Press.
• Simpson, Stephen, 1999. Podsystémy aritmetiky druhého poriadku. Berlín: Springer.
• Väänänen, Jouko, 2001. „Logika druhého poriadku a základy matematiky,“Bulletin symbolickej logiky, 7: 504–520.

Akademické nástroje

	Ako citovať tento záznam.
	Ukážku verzie tohto príspevku vo formáte PDF si môžete pozrieť na stránke Friends of the SEP Society.
	Vyhľadajte túto vstupnú tému v projekte Indiana Philosophy Ontology Project (InPhO).
	Vylepšená bibliografia tohto záznamu vo PhilPapers s odkazmi na jeho databázu.

Ďalšie internetové zdroje

[Obráťte sa na autora s návrhmi.]