Logika Druhého řádu A Vyššího řádu

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Logika druhého řádu a vyššího řádu

První vydání 20. prosince 2007; věcná revize St 4. března 2009

Logika druhého řádu je rozšíření logiky prvního řádu, kde kromě kvantifikátorů, jako je „pro každý objekt (ve vesmíru diskursu),“má jeden kvantifikátory, jako „pro každou vlastnost objektů (ve vesmíru diskursu).). “Toto rozšíření jazyka zvyšuje jeho expresivní sílu, aniž by přidávalo nové nes Logické symboly, jako jsou nové predikátové symboly. U klasické rozšířené logiky (jako v této položce) lze vlastnosti identifikovat pomocí sad, takže logika druhého řádu nám poskytuje kvantifikátor „pro každou sadu objektů“.

Existují dva přístupy k sémantice logiky druhého řádu. Liší se interpretací fráze „pro každou sadu objektů“. Má to nějaký pevný význam, na který se můžeme odkazovat, nebo musíme zvážit různé významy, které by tato věta mohla mít? V prvním případě (který se bude nazývat standardní sémantika) považujeme za jisté matematické pojmy. Ve druhém případě (který se bude nazývat obecná sémantika) je mnohem méně považováno za samozřejmost. V tomto případě, aby byla věta považována za platnou, bude muset platit věta ve všech přípustných významech věty „pro každou sadu objektů“.

• 1. Syntaxe a překlady
• 2. Standardní sémantika
• 3. Obecná sémantika
• 4. Logika vyššího řádu
• 5. Systémy teorie čísel druhého řádu
• Bibliografie
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Syntaxe a překlady

V symbolické logice bude vzorec (Px → Px) pravdivý, bez ohledu na to, jaký objekt ve vesmíru diskurzu je přiřazen proměnné x. Což neznamená nic jiného než to, že ∀ x (Px → Px) bude pravdivé, bez ohledu na to, jaká podmnožina vesmíru diskursu se používá k interpretaci predikátového symbolu P. Není to však nic říct, ale že vzorec ∀ P ∀ x (Px → Px) je pravdivý, bez ohledu na to?

V jazycích prvního řádu jsou některé věci, které můžeme říci, a některé, které nemůžeme. Předpokládejme například, že chceme vyjádřit fakta o aritmetice přirozených čísel. To znamená, že chceme vyjádřit fakta o struktuře (N; 0, S, <, +, ×) sestávající z množiny N = {0, 1, …} přirozených čísel, společně se společnými aritmetickými operacemi a vztahy. A chceme použít jazyk prvního řádu s kvantifikátory ∀ interpretovanými jako „pro každé přirozené číslo“a ∃ interpretovanými jako „pro nějaké přirozené číslo“. Kromě toho do jazyka zahrneme konstantní symbol 0 pro nulu číslo, jednobodový funkční symbol S pro nástupnickou operaci (který aplikuje na přirozené číslo dává další), dvoumístný predikátový symbol <pro relační vztah <na N,a dvoumístné funkční symboly + a × pro sčítání a násobení.

S tímto jazykem můžeme nyní symbolizovat mnoho skutečností, o kterých víme, že jsou pravdivá o přirozených číslech. Můžeme vytvořit větu ∀ x (x <Sx), která například vyjadřuje skutečnost, že každé číslo je menší než následující. Potíže však vyvstanou, pokud chceme vyjádřit „dobře uspořádanou vlastnost“, že jakákoli neprázdná množina přirozených čísel má nejmenšího člena. Je-li P nový predikátový symbol na jednom místě, pak

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

vyjadřuje myšlenku, že P platí pro nejmenší číslo, pokud platí pro všechna čísla. Tento vzorec je pravdivý ve struktuře (N; 0, S, <, +, ×), když interpretujeme predikátový symbol P jako pravdivý z čísel v nějaké konkrétní sadě - bez ohledu na to, co je sada - říká, že množina má nejméně člena, pokud není prázdný. Nyní přidáte kvantifikátor ∀ P

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

získáme formalizaci dobře uspořádané nemovitosti.

Jazyk logiky druhého řádu rozšiřuje jazyk logiky prvního řádu tím, že umožňuje kvantifikaci predikátových symbolů a funkčních symbolů. Jak ukazuje předchozí příklad, v aritmetickém jazyce druhého řádu můžeme říci, že přirozená čísla jsou dobře uspořádána. Víme, že dobře uspořádaná vlastnost není vyjádřitelná větou prvního řádu, protože nestandardní modely teorie (prvního řádu) (N; 0, S, <, +, ×) nejsou nikdy dobře uspořádány. Logika druhého řádu je tedy opravdovým rozšířením. To znamená, že můžeme přeložit některé věty přirozeného jazyka, například „Vztah <je řádný řád“, do jazyka logiky druhého řádu, které nelze přeložit do jazyka logiky prvního řádu.

Pro jiný příklad můžeme (pomocí volby) říci, že vesmír diskursu je nekonečný tím, že říkáme, že existuje vesmírný tranzitivní vztah, takže každý prvek nese vztah k něčemu, ale ne k sobě:

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

Kvantifikátor druhého řádu „∃ R“zde vyjadřuje existenci nějakého binárního vztahu ve vesmíru. Protože jediný predikátový symbol R je v rozsahu tohoto kvantifikátoru, věta nemá žádné predikátové symboly otevřené pro interpretaci. Jak je známo, žádná věta prvního řádu nemá pro své modely přesně nekonečné struktury.

Podrobněji je zde uvedeno, co se rozumí jazykem druhého řádu: Jeden začíná jazykem prvního řádu a rozšiřuje jej nekonečným zásobováním n -place predikátových proměnných pro každé kladné celé číslo n a nekonečným doplňováním n -place funkční proměnné pro každé kladné celé číslo n. (Funkčním proměnným se lze vyhnout, ale to je další věc.) Pravidla formace dobře vytvořených vzorců jsou zřejmá; zejména jakákoli univerzální a existenciální kvantifikace je povolena pro jakoukoli proměnnou, ať už jde o individuální proměnnou, predikátovou proměnnou nebo funkční proměnnou.

Abychom se vrátili k příkladu přirozených čísel, můžeme vyjádřit postulát indukce Peano větou druhého řádu:

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

Tato věta vyjadřuje myšlenku, že X platí o všech přirozených číslech, pokud platí o 0 a jeho pravda u nějakého čísla y zaručuje jeho pravdivost nástupci y, bez ohledu na to, z čeho může být množina X pravdivá.

Pro příklad zahrnující množinu reálných čísel R s jejím obvyklým uspořádáním můžeme vyjádřit vlastnost s nejnižší horní mezí větou druhého řádu:

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

Předchozí příklady jsou čerpány z matematických situací. Existuje také zajímavá možnost vět přirozeného jazyka, které zřejmě vyžadují formalizaci druhého řádu. George Boolos navrhl příklad: „Jsou někteří kritici, kteří obdivují pouze jeden druhého.“Tato věta potvrzuje existenci souboru jednotlivců majících určitý majetek; Neznamená to například, že existují dva kritici, kteří obdivují jeden druhého a nikoho jiného.

2. Standardní sémantika

V předchozí části je implicitní pojem pravdy věty druhého řádu ve struktuře. Uvažujme strukturu M = (A, R,…) skládající se z neprázdné množiny A sloužící jako vesmír diskurzu a některých vztahů a funkcí na A interpretujících neslogické symboly. Pak chceme počítat větu druhého řádu ve tvaru ∀ P φ (kde P je ak -place predikátová proměnná) jako pravdivou v této struktuře, pokud pro každou množinu Q k-násobků členů A máme tuto φ je ve struktuře pravdivé, když P je přiřazen vztah Q.

Více formálně musíme definovat induktivně, co to znamená, aby byl vzorec druhého řádu φ uspokojen ve struktuře M = (A, R,…) pod přiřazením objektů volným proměnným v φ, které budou zapsány M ⊨ φ [s]. Definice probíhá přesně jako v případě prvního řádu, s výjimkou dalších ustanovení pro kvantifikátory druhého řádu. U ak -place predikátové proměnné P

M ⊨ ∀ P φ [s] iff pro každý k -ary vztah Q na A, máme M ⊨ φ [s ']

kde s 'se liší od s pouze v přiřazení vztahu Q k predikátové proměnné P. (Zde „iff“zkracuje zkratku „if and only if.“) Podobně pro proměnnou funkce ak -place F, M ⊨ ∀ F φ [s] iff pro každou k -place funkci G na A, máme M ⊨ φ [s ']

kde s 'se liší od s pouze přiřazením funkce G funkční proměnné F. Všimněte si, že tato definice se vztahuje, v případě 1-predikátové predikční proměnné, na všechny podmnožiny A, tj. Na celou energetickou sadu A. Je to tato vlastnost, která odpovídá za mimořádnou sémantickou sílu jazyků druhého řádu.

V případě věty druhého řádu σ (tj. Vzorec bez volné proměnné) již přiřazení s není relevantní a můžeme jednoznačně mluvit o pravdě nebo nepravdivosti σ ve struktuře M (tj. lze říci, že M je nebo není modelem σ). Zejména příklady § 1 překladů z přirozeného jazyka do jazyka logiky druhého řádu lze nyní vidět, aby splňovaly zamýšlené účely. Spojení axiomů pro lineární uspořádání a věty

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

je pravdivý ve struktuře (A, <) iff vztah <studna objedná množinu A. Věta

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

je ve struktuře pravdivý, pokud je vesmír diskurzu nekonečnou sadou. Tento příklad ukazuje, že věta o kompaktnosti neplatí pro logiku druhého řádu. Pokud nazveme výše uvedenou větu λ∞ a necháme λ n větu prvního řádu „ve vesmíru je alespoň n různých věcí“, pak množina

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

nemá žádný model, ačkoli každá konečná podmnožina má model.

Spojení 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]

je pravdivý ve struktuře (A, f, e) jestliže tato struktura je izomorfní k (N, S, 0), přirozená čísla s nástupnickou operací S a rozlišujícím prvkem 0. Spojení těchto tří vět poskytuje příklad věta, která je kategorická, to znamená, že má přesně jeden model, až po izomorfismus. Naproti tomu věta prvního řádu může být kategorická, pouze pokud je její jeden model konečný.

Podobně lze uspořádané pole reálných čísel (R, 0, 1, +, ×, <) charakterizovat až k izomorfismu axiomy prvního řádu pro uspořádané pole, spolu s větou druhého řádu vyjadřující nejméně -upper vázaná vlastnost. Je dobře známo, že jakýkoli model těchto vět musí být izomorfní k uspořádanému poli reálných čísel. Tento příklad ukazuje, že Löwenheimova-Skolemova věta neplatí pro logiku druhého řádu.

Předchozí příklady ukazují, že dvě každodenní matematické struktury (N, S, 0) a (R, 0, 1, +, ×, <) jsou charakterizovatelné ve druhém řádu. To znamená, že každý má jediný axiom druhého řádu, který je jediným modelem, až po izomorfismus. Jeden by se mohl zeptat, jaké další struktury by mohly být charakterizovatelné druhého řádu. Samozřejmě, existuje tolik takových struktur, až po izomorfismus, protože každá potřebuje větu.

Dále předpokládejme, že v těchto příkladech existenciálně kvantifikujeme všechny logické symboly (tj. Všechny predikátové symboly a funkční symboly). Kde π (0, S,) je spojení tří Peano postulátů, věta ∃ x ∃ F π (x, F) je věta v jazyce druhého řádu rovnosti, to znamená, že nemá logickou logiku symboly vůbec.

Struktura pro jazyk rovnosti sestává jednoduše z neprázdného vesmíru diskursu; neexistují žádné vztahy nebo funkce nebo rozlišující prvky. Taková struktura je samozřejmě určována izomorfismem jednoduše její mohutností. Pro větu σ v jazyce rovnosti nechť je její spektrum třídou kardinálů, ve které je pravda. Například spektrum platné věty je třída všech nenulových kardinálních čísel. Spektrum nevyhovující věty je prázdné. Spektrum ¬σ je komplement (ve vztahu ke třídě všech nenulových kardinálních čísel) spektra σ. Spojení a odpojení vět vede k průniku a sjednocení spektra. Věta v jazyce rovnosti je dána logickou ekvivalencí svým spektrem.

Věta ∃ x ∃ F π (x, F), kterou jsme vytvořili z postulátů Peano, je pravdivá v nespočetně nekonečné mohutnosti a nikdo jiný. Jeho spektrum je tedy singleton. Řekněme, že kardinální číslo κ je charakterizovatelné v druhém řádu, pokud existuje věta jazyka rovného řádu druhého řádu, která platí pro kardinálnost κ a pouze tam. (Nenulové konečné kardinály jsou všechny charakterizovatelné prvního řádu.) Viděli jsme, že spočítatelný nekonečný kardinál je charakterizovatelný druhého řádu. Podobně můžeme ukázat, že síla kontinua je charakterizovatelná druhého řádu. Kde ρ (0, 1, +, ×, <) je věta druhého řádu, která charakterizuje uspořádané pole reálných čísel až po izomorfismus, věta

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

je věta v jazyce druhého řádu rovnosti, která je pravdivá v síle kontinua a v žádném jiném kardinálu.

Člověk by se mohl zeptat, jaká další kardinální čísla jsou charakterizovatelná v druhém řádu. Pro zkoumání této otázky viz dokument S. Garlanda z roku 1974. Samozřejmě může být jen tolik takových kardinálů, protože každý z nich má větu.

Není těžké vidět, že nejméně nespočetný kardinál je charakterizovatelný druhého řádu. Můžeme použít větu, která říká, že vesmír je nekonečný, ale nečíslitelný a že jakákoli nespočetná podmnožina je stejná jako celý vesmír. Máme tedy věty κ a λ v jazyce druhého řádu rovnosti, které charakterizují nejméně nespočetného kardinála a sílu kontinua. Věta κ ↔ λ je platná věta, pokud je hypotéza kontinua pravdivá, a teprve poté. Můžeme dojít k závěru, že ne všechny problémy týkající se logiky druhého řádu jsou nutně vyřešeny v ZFC.

Hodně studovaná teorie PA, alometika Peano prvního řádu, je samozřejmě získána použitím indukčního postulátu druhého řádu ∀ X [X 0 a ∀ y (Xy → XSy) → ∀ y Xy], odpovídající schéma prvního řádu

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

kde φ může být jakýkoli vhodný vzorec prvního řádu. Účinek tohoto schématu je dobře znám; zajišťuje, že každá definovatelná množina, která obsahuje 0 a je uzavřena pod nástupcem, musí obsahovat vše.

Předpokládejme, že analogicky začneme s naší axiomatizací uspořádaného pole reálných čísel druhého řádu a nahradíme axiomat s nejnižší horní hranicí druhého řádu odpovídajícím schématem. Výsledkem je nekonečná množina axiomů prvního řádu, což zajišťuje, že každá definovatelná množina, která není prázdná a ohraničená, má nejméně horní hranici. Jejich modely se nazývají skutečně uzavřená uspořádaná pole. Je zajímavé, že tento koncept byl poprvé formulován algebraisty, nikoli logiky.

Jedním z měření síly logiky druhého řádu je složitost jeho sady platných vět. Nechť V ¹ je množina platných vět logiky prvního řádu a nechť V ² je sada platných vět logiky druhého řádu. Přesněji řečeno, v logice prvního řádu s jediným jednoduchým 2-místným predikátovým symbolem P víme, že množina V1 (P) platných vět je úplná vypočítatelná množina (tj. Úplná rekurzivně spočetná množina). (Zde můžeme přiřadit Gödel čísla a zobrazit V ¹ (P) jako množinu přirozených čísel, nebo rovnocenně je můžeme zobrazit přímo jako množinu slov nad konečnou abecedou.) A Tarski poukázal na to, že množina V ¹ (=) platných vět v jazyce prvního řádu rovnosti (bez logických symbolů vůbec) je rozhodnutelné.

Pro srovnání, nechť V ((=) je množina platných vět v jazyce druhého řádu rovnosti. Jaká je složitost této sady?

Nechť π je spojením Peano postulátů a rekurzních rovnic pro sčítání a násobení. Π je tedy věta druhého řádu v jazyce aritmetiky s 0, S, + a ×. Věta π je kategorická; jeho jediný model je (N, 0, S, +, ×), až po izomorfismus. V důsledku toho je věta σ v jazyce aritmetiky pravdivá σ v aritmetice, pokud je podmínka (π → σ) platná. Toto ukazuje, že V ² (0, S, +, ×) nemůže být aritmetický (tj. Nemůže být aritmeticky definovatelný v prvním řádu), aby v pravdě v aritmetice nebylo možné definovat pravdu, a to v rozporu s Tarského větou. Nyní můžeme vyčíslit všechny neslogické symboly; věta φ (P) platí, pokud je věta ∀ P φ (P) platná. Závěr je, že V ² (=) není aritmetický.

Je zajímavé, že se jedná pouze o špičku ledovce. Začneme tím, že můžeme ukázat, že V ² (=) není analytické, to znamená, že není aritmeticky definováno vzorcem druhého řádu. Důkaz Tarského věty, ukazující, že množina pravých vět prvního řádu aritmetiky není v aritmetice definovatelná v prvním řádu, také ukazuje, že množina skutečných vět vět aritmetiky druhého řádu není v aritmetice definovatelná v druhém řádu. Zbytek argumentu se nezmění. A později uvidíme, že ještě více je pravda.

Ve velmi odlišném směru ukázal R. Fagin překvapivé spojení mezi tématem ve výpočetní složitosti a definovatelností druhého řádu nad konečnými strukturami. Například konečný graf lze považovat za pár (V, E) sestávající z neprázdné vrcholové sady V a symetrické okrajové relace E na V. Výrok, že graf lze správně obarvit třemi barvami, lze vyjádřit větou druhého řádu: existují podmnožiny R, G, B, které rozdělují V tak, že dva vrcholy spojené hranou nejsou nikdy stejné barvy. Tato věta je Σ-1-1, to znamená, že má tvar

[existenciální kvantifikátory druhého řádu] [vzorec prvního řádu].

Je dobře známo, že být tříbarevný je vlastnost NP grafu. To znamená, že jde o vlastnost rozpoznatelnou v polynomickém čase nedeterministickým Turingovým strojem. (Existuje nedeterministický Turingův stroj M a polynom p takový, že kdykoli (V, E), vhodně kódovaný, je dán M, pak pokud (V, E) je tříbarevný, pak nějaký výpočet M přijme graf v krocích p (n), kde n měří velikost (V, E), a pokud (V, E) není tříbarevný, žádné výpočty M nikdy nepřijmou graf.)

Fagin ukázal, že to není izolovaný příklad; každá NP vlastnost konečných grafů je definovatelná Σ-1-1 větou logiky druhého řádu. A naopak každá věta Σ-1-1 definuje vlastnost NP. A místo grafů můžeme použít směrované grafy nebo jiné konečné struktury. Faginova věta říká, že vlastnost konečných struktur je vlastnost NP, a to pouze tehdy, pokud je definovatelná větou second-1-1 druhého řádu.

3. Obecná sémantika

Klíčovým rysem „standardní sémantiky“diskutované v předchozí části je to, že v případě predikátové proměnné X na jednom místě se kvantifikátor ∀ X rozprostírá přes celou mocninu diskursu. Viděli jsme, že tato funkce dává jazykům druhého řádu vysokou míru výrazné síly.

Opravdu však chceme, aby se kvantifikátor ∀ X pohyboval v rozsahu skutečného výkonu? Prediktivista bude namítat, že operace nastavení napájení nemá smysl. A dokonce i klasický matematik připouští, že existují určité nejasné rysy operace s elektrickým pohonem. Nezávislost hypotézy kontinua ilustruje jednu takovou nejasnost. Pokud je naším cílem studovat základy matematiky, mohlo by být rozumné nepovažovat za samozřejmost, že už víme vše o mocenských sadách.

Koncept obecné sémantiky pro logiku druhého řádu se vyhýbá jakémukoli předstírání, že operace nastavení energie je stálým dobře srozumitelným zdrojem. Místo toho musí být přímo stanoven rozsah kvantifikátoru ∀ X.

Obecnou předstrukturou pro jazyk druhého řádu máme na mysli strukturu v obvyklém slova smyslu (vesmír diskurzu plus interpretace pro logické symboly) spolu s dalšími množinami:

• Vesmír n-místa vztahu pro každé kladné celé číslo n. Musí to být sbírka n -árních vztahů ve vesmíru diskursu. Zejména musí být vesmírem s jedním vztahem určitá kolekce podmnožin vesmíru. Je tedy součástí (možná všechny, možná ne) mocenské sady vesmíru.
• Vesmír funkce n-místa pro každé kladné celé číslo n. Musí to být sbírka n -place funkcí ve vesmíru diskursu.

Pro obecnou předstrukturu M existuje přirozený způsob, jak definovat, co to znamená pro vzorec druhého řádu φ, který má být splněn ve struktuře M pod přiřazením objektů volným proměnným v φ, které budou znovu zapsány M ⊨ φ [s]. Kvantifikátory druhého řádu jsou nyní definovány tak, aby se pohybovaly v odpovídajícím vesmíru. U ak -place predikátové proměnné P

M ⊨ ∀ P φ [s] iff pro každý k -ary vztah Q ve vesmíru k -place relace, máme M ⊨ φ [s ']

kde s 'se liší od s pouze v přiřazení vztahu Q k predikátové proměnné P. Podobně pro ak -place funkční proměnnou F, M ⊨ ∀ F φ [s] iff pro každou funkci k -place G ve vesmíru funkce k -place, máme M ⊨ φ [s ']

kde s 'se liší od s pouze přiřazením funkce G funkční proměnné F. V případě věty druhého řádu σ (tj. Vzorec bez volné proměnné) již přiřazení již není relevantní a můžeme jednoznačně hovořit o pravdě nebo nepravdivosti σ v obecné předstruktuře M (že je, můžeme říci, že M je nebo není modelem σ).

Ale pro logiku druhého řádu opravdu nechceme, aby byl 1-místo vztahový vesmír libovolnou sbírkou podmnožin vesmíru. Možná nebudeme vědět všechno o operaci s napájením, ale víme o tom něco. Použití obecných předběžných struktur ve skutečnosti znamená, že se s jazykem druhého řádu bude zacházet jako s mnohořadovým jazykem prvního řádu.

Existuje několik podmnožin vesmíru, o kterých víme, protože je můžeme definovat. To znamená, že φ je vzorec, ve kterém se vyskytuje pouze proměnná u zdarma. Pak množina φ definuje v M je množina, která se skládá ze všech členů a z M tak, že φ je splněna v M, když a je přiřazeno k u. Tento nápad lze rozšířit. Předpokládejme, že φ má pouze volné proměnné u, v, w, x, Y a Z (kde Y je predikátová proměnná m -place a Z je n -place funkční proměnná). Předpokládejme, že c a d jsou členy (individuálního) vesmíru M | z M, že E je v M 'sm -place relačním vesmíru, a že F je v M' sn -place funkčním vesmíru. Pak binární relace φ definuje v M z parametrů c, d, E a F množinu párů <a, b> prvků | M | takový, že φ je splněn v M, když jeho proměnné u, v, w, x, Y,a Z jsou přiřazeny a, b, c, d, E a F. To znamená, že se jedná o binární vztah:

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

Tento koncept lze samozřejmě zobecnit na situaci, kdy je ak -ary vztah definován z jakéhokoli konkrétního počtu parametrů.

Pak je rozumné omezit pozornost na obecné předstruktury, které jsou uzavřeny podle definovatelnosti. Tudíž v právě popsané situaci je rozumné očekávat, že M 2-ary relační vesmír bude obsahovat binární vztah, který φ definuje z parametrů v předstruktuře. To znamená, že očekáváme větu

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

být pravdivý v M. Nazvěte takové věty pochopení axiomů.

Obecnou strukturou pro jazyk druhého řádu (také nazývanou Henkinova struktura) se míní obecná předstruktura, ve které jsou všechny axiomy porozumění (pro všechny vzorce) pravdivé. (Zde φ může obsahovat kvantifikátory nad predikátovými proměnnými, takže i pravdivé axiomy porozumění mají být pravdivé. V části 5 zvažujeme alternativy k „úplnému porozumění“.) Mezi obecnými strukturami jsou ty, ve kterých je 1-místo vztahový vesmír skutečná mocenská sada jednotlivého vesmíru atd. (Takovou obecnou strukturu nazývejte absolutní.) Ale mohou existovat i další.

Obecnou sémantiku (nazývanou také Henkinova sémantika) získáme pro jazyk druhého řádu tím, že vezmeme v úvahu všechny obecné struktury. To znamená, aby věta σ byla platná v obecné sémantice, musí to platit ve všech obecných strukturách. To je silnější požadavek, než říkat, že σ platí ve standardní sémantice. Věta, která je platná ve standardní sémantice, platí v těch obecných strukturách, pro které je vesmírný vztah na jednom místě úplnou mocenskou sadou jednotlivého vesmíru atd. Ale taková věta σ by se mohla v některé obecné struktuře ukázat jako nepravdivá (tj. ¬σ může mít obecný model).

Hlavní rys obecné sémantiky je výsledkem typu „nic než“: Logika druhého řádu s obecnou sémantikou není nic jiného než logika prvního řádu (mnohočetná) spolu s axiomy porozumění. Věta je tedy platná v obecné sémantice, pokud je logicky implikována (v logice prvního řádu) množinou axiomů porozumění.

Toto snížení na logiku prvního řádu přináší okamžitě následující výsledky:

• (Enumerability) V jazyce druhého řádu s konečně mnoha neslogickými symboly je množina vět, které jsou platné v obecné sémantice, vyčíslitelná. Platí to proto, že množina axiomů porozumění je vypočítatelná množina (tj. Rekurzivní množina).
• (Kompaktnost) Sada vět má obecný model, má-li každá konečná podmnožina obecný model.
• (Löwenheim – Skolem) Pokud má množina vět obecný model, má počítatelný obecný model.

V každém z těchto tří případů existuje ostrý kontrast k situaci standardní sémantiky zvažované v oddíle 2. Kromě toho lze pro logiku druhého řádu dát deduktivní počet (přizpůsobený z logiky prvního řádu a rozšířený o axiomy porozumění). to bude kompletní pro obecnou sémantiku.

Pro srovnání, axiomatická teorie množin (ZFC říká) je teorie prvního řádu; model teorie množin musí dodávat operaci elektrického napájení. Jazyk teorie množin má však určité aspekty vyššího řádu, protože nám umožňuje mluvit o množinách, sadách množin atd.

V extrémním případě struktury M, ve které jsou všechny vztahy definovatelné (např. Struktura s jednobodovým vesmírem), se obecná sémantika shoduje se standardní sémantikou.

4. Logika vyššího řádu

Není třeba se zastavovat u logiky druhého řádu; jeden může pokračovat. Můžeme přidat do jazyka „super predikátové“symboly, které berou jako argumenty jednotlivé symboly (proměnné nebo konstanty) i predikátové symboly. A pak můžeme dovolit kvantifikaci nad super predikátními symboly. A pak můžeme pokračovat dál.

(Čtenáři je třeba upozornit, že v literatuře existují dva různé způsoby, jak počítat pořadí. Podle jednoho schématu logika třetího řádu umožňuje, aby se vyskytly super predikátové symboly, a logika čtvrtého řádu umožňuje jejich kvantifikaci. Podle druhého schématu logika třetího řádu již umožňuje kvantifikaci super predikátových symbolů.)

Teprve po krocích dosáhneme úrovně teorie typů. Představitelné je pokračování v transfinitu.

Viděli jsme, že ačkoli množina V1 platných vzorců logiky prvního řádu je počítatelně vyčíslitelná, odpovídající sada V2 pro logiku druhého řádu (se standardní sémantikou) je mnohem složitější. Tento jev nepokračuje ve vyšších řádech.

Existuje smysl, ve kterém je operace s nastavením výkonu definovatelná v logice druhého řádu. Vezměme si jazyk s jedním místem predikátového symbolu I (pro jednotlivce), s jedním místem predikátového symbolu S (pro sady) a se dvěma místy predikátového symbolu E (pro členský vztah). Pak, abychom vyjádřili myšlenku, že S je mocninná soustava I, můžeme použít konjunkci (nazvanou σ) následujících čtyř vět:

∀ x (Ix + Sx), kde „+“označuje exkluzivní disjunkci

∀ x ∀ y (Exy → Ix a Sy)

∀ x ∀ y (Sx a Sy & ∀ t (Etx ↔ Ety) → x = y) (prodlužování)

∀ X ∃ y (Sy & ∀ t (It → (Ety ↔ Xt))) (porozumění).

Je zřejmé, že σ platí v jakékoli struktuře, jejíž vesmír je disjunktním sdružením množiny A a její mocenské sady P (A) a která přiřadí A k I, přiřadí P (A) k S a přiřadí členskou relaci ∈ k E. A naopak, nechť M je jakýkoli model σ (ve standardní sémantice). Nechť f je individuální funkce od M interpretace I na množinu A, která je disjunktní od její mocenské sady (vždy existuje taková množina). Rozšiřte f do celého M vesmíru definováním pro každou s v M interpretaci S

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

(to je, f (s) je soubor věcí v A že M myslí, že patří k s). Pak f je izomorfismus z M na strukturu, jejíž vesmír je nespojité spojení množiny A a její mocenské sady P (A) a která přiřadí A k I, přiřadí P (A) k S a přiřadí členskou relaci ∈ k E. Zhruba řečeno, σ definuje operaci nastavení síly „uvnitř izomorfismu“.

V podobném duchu můžeme v rámci izomorfismu definovat mocenskou sadu I × I, tj. Množinu binárních vztahů na I. A tak dále.

Tato vyjádřitelnost operace elektrického souboru druhého řádu umožňuje simulaci logiky vyššího řádu v rámci druhého řádu. Konkrétněji, máme následující výsledek Hintikky (1955): Pro každý vzorec φ logiky vyššího řádu (v jazyce s konečně mnoha nes Logickými symboly) můžeme efektivně najít větu ψ logiky druhého řádu (v jazyk rovnosti), takže φ platí, pouze pokud je ψ platné. Věta ψ je konstruována tak, že se nejprve rozšíří jazyk přidáním symbolů pro vesmíry různých typů (jednotlivci, sady jednotlivců,…) a pro členství v těchto vesmírech. Pak je platnost φ ekvivalentní platnosti vzorce druhého řádu

Vesmír je správně uspořádán → φ *

kde φ * je vhodná relativizace φ. Nakonec můžeme předponu univerzálních kvantifikátorů získat větu ψ v jazyce rovnosti.

Tak je sada validit logiky sedmnáctého řádu vypočítatelně redukovatelná na V² (=), sada validit druhého řádu v jazyce rovnosti. (Ve skutečnosti jsou tyto dvě množiny výpočetně izomorfní.) Takže v tomto aspektu se složitost logiky vyššího řádu s řádem nezvyšuje. Z toho vyplývá, že množina V ² (=) má vysoký stupeň složitosti. Můžeme rozšířit naše dřívější pozorování, že to není definovatelné v aritmetice druhého řádu; není ani definovatelný v aritmetice vyššího řádu. Montague v roce 1965 rozšířil toto na transfinite. V té době slyšel říkat, že množina V ² (=) nespočívá v žádné Kleene hierarchii, „minulosti, současnosti ani budoucnosti“.

Skutečnost, že můžeme operaci s mocninami vyjádřit v logice druhého řádu (a může iterovat postup), dává logice druhého řádu nějakou velkou část expresivity teorie množin. Quine prohlašoval, že logika druhého řádu není ve skutečnosti logikou, ale spíše zakrývající teorii. A Robert Vaught poznamenal, že studium logiky druhého řádu bylo jako studium „standardního modelu teorie množin“.

Složitost V ² (=) se příliš nemění, pokud uvalíme omezení na kvantifikovatelnou formu vět. Předchozí redukce logiky vyššího řádu dává Π-1-2 věty, takže můžeme dojít k závěru, že sada platných Π-1-2 vět v jazyce rovnosti je vypočítatelně izomorfní s plným V ² (=). Jedná se o nejlepší možný výsledek. Sada Π-1-1 platných vět je úplná vypočítatelná množina; jakmile upustíme univerzální kvantifikátory druhého řádu, podíváme se na vzorce prvního řádu. Sada Σ-1-1 platných vět v jazyce rovnosti je kompletní množina co-ce, tj. Doplněk spočítatelné množiny. (Věta ∃ P φ (P) platí pro každou nenulovou kardinálnost, pokud elementární věta φ (P) obsahuje modely každé konečné velikosti, co-ce vlastnost. A k Turingovu stroji můžeme efektivně přiřadit elementární větu s modely všech konečných velikostí, pokud se stroj nikdy nezastaví.) Sada platných Σ-1-2 vět v jazyce rovnosti je také vypočítatelně izomorfní s plným V ² (=), ale tato skutečnost vyžaduje jiný druh důkazu.

5. Systémy teorie čísel druhého řádu

Jazyk aritmetiky (s 0, S, <, + a ×) je důležitý pro základy matematiky. Jako axiomy můžeme vzít obvyklé Peano postuláty, včetně indukčního axiomu druhého řádu. Ve standardní sémantice je jediným modelem Peano postulátů, až po izomorfismus, obvyklý model aritmetiky. Teorie generovaná těmito axiomy (ve standardní sémantice) je tedy jednoduše teorií druhého řádu skutečné aritmetiky.

Předpokládejme však místo toho obecnou sémantiku. Peano postuláty mají obecné modely, které se mohou lišit od obvyklého modelu dvěma způsoby. Můžeme použít teorém kompaktnosti pro konstrukci nestandardních obecných modelů Peano postulátů obsahujících nekonečně velká čísla. Můžeme také najít obecné modely Peano postulátů, ve kterých je vesmír množin menší než plný výkon jednotlivého vesmíru (tj. Obecné modely, které nejsou absolutní). Ve skutečnosti musí být jakýkoli obecný model, který lze spočítat, tohoto druhu.

V kontextu obecných modelů přidáváme další schéma axiomu pro výběr:

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

podle potřeby předponou univerzálními kvantifikátory. (Zde je vzorec, který byl zapsán jako φ (n, {t | Ytn}), získán z φ (n, X) nahrazením každého termínu Xu termínem Ynu.)

Postuláty Peano jsou dostatečně silné, aby nám poskytly párovací funkce. V důsledku toho pro obecný model jeho 1-vesmírný vztahový vesmír zcela určuje svůj vesmírný vztah k-místo pro každý k.

Tradiční terminologie je odkazovat na teorii čísel druhého řádu jako analýzu. Název je odvozen od skutečnosti, že je možné identifikovat reálná čísla pomocí množin přirozených čísel. Kvantifikátory druhého řádu nad množinami přirozených čísel mohou být potom považovány za kvantifikátory nad skutečnými čísly. Vhodnost jména je otevřená otázce, ale její použití je dobře zavedeno. V souladu s tím budeme pomocí modelu analýzy myslet obecný model Peano postulátů s výběrem. Jako obecný model musí každý model analýzy samozřejmě splňovat všechny axiomy porozumění; později budeme uvažovat o oslabení tohoto požadavku.

Nechť A 2 je teorie generovaná Peano postuláty s výběrem (v obecné sémantice). Pak A2 je úplná vypočítatelná výčet podmnožiny skutečné aritmetiky druhého řádu. A 2 obsahuje každou pravou Σ-0-1 větu. Neobsahuje každou pravou Π-0-1 větu.

Silnější teorii můžeme získat omezením pozornosti na modely analýzy, které se liší od obvyklého modelu pouze ve druhém ze dvou výše popsaných způsobů. To znamená, že definujeme ω- model analýzy jako model analýzy, ve kterém je jednotlivý vesmír skutečnou sadou přirozených čísel a symboly 0 a S mají své obvyklé interpretace. (V důsledku toho symboly <, + a × mají své obvyklé interpretace.) Nastavený vesmír ω-modelu analýzy proto musí být nějakou částí (možná všechny) mocninové sady přirozených čísel, ale musí to být takový že plné porozumění je uspokojeno.

Motivaci k uvažování ω-modelů lze uvést následovně. Máme jasné porozumění - nebo tak rádi přemýšlíme - o souboru přirozených čísel. Nemáme však nic jako stejné chápání mocninové sady přirozených čísel. Je tedy rozumné držet opravenou část, o které jsme si jisti, ale nechat otevřenou interpretaci části, o které si nejsme tak jistí.

Ω-model analýzy je zcela určen jeho stanoveným vesmírem. Protože máme párovací funkce, které jsou definovatelné v prvním řádu, bude určovaný vesmír určovat vesmír binárních relací atd. Argument Löwenheim – Skolem ukáže, že existují ω-modely analýzy s počítatelným množstvím vesmíru.

V každém ω-modelu analýzy jsou skutečné věty prvního řádu přesně ty, které platí v obvyklém modelu. Ω-modely se však mohou lišit ve větách druhého řádu. Nechť ω je teorie ω-modelů, tj. Množina vět pravdivá ve všech ω-modelech analýzy. Pak A co rozšiřuje A 2. Je to kompletní sada Π-1-1. Obsahuje každou pravou Π-1-1 větu; neobsahuje žádnou pravou true-1-1 větu.

Pod pojmem ω- se rozumí infinitární pravidlo inference, které vyvozuje ∀ x φ (x) z předpokladů φ (0), φ (1), φ (2),…. Předpokládejme, že přidáme toto pravidlo k obvyklému logickému aparátu a uvidíme, co je pak možné odvodit z Peano postulátů s výběrem. „Odpočet“pomocí pravidla ω bude obecně nekonečný, ale musí být opodstatněný. Není těžké vidět, že jakákoli věta, kterou lze takto odvodit, je v Aω. Naopak platí věta o úplnosti: Každá věta v A má odečtení popsaného druhu.

Andrzej Mostowski v dokumentu z roku 1961 popsal způsob, jak jít o krok dále, směrem k silnější teorii. Předpokládejme, že jsme ochotni považovat nejen řádový typ ω za dostatečně pochopený, ale i za koncept řádného uspořádání. Definujte β-model analýzy jako ω-model s dodatečnou vlastností, kterou jsou uspořádání v modelu, která se zdají být dobře uspořádaná, skutečně. To znamená, že ω-model M analýzy je β-model, pokud každý relační vztah (na přirozených číslech) v M s vlastností, že neprázdné množiny v M mají vždy nejméně členů, je ve skutečnosti dobře uspořádaný.

Pak se souprava A of vět, která platí ve všech β-modelech, ukáže jako kompletní sada Π-1-2. Obsahuje každou pravou Π-1-2 větu; neobsahuje žádnou pravou Σ-1-2 větu. Je zřejmé, že máme inkluze

A 2 ⊆ A ω ⊆ A β ⊆ Pravdivá aritmetika druhého řádu.

Například, teoretická část tranzitivního ∈ modelu teorie množin ZF bude vždy β-model analýzy. Můžeme však vytvořit β-model bez silných předpokladů. Ve skutečnosti existuje nejmenší β-model a lze jej konstruovat způsobem, který připomíná Gödelovu definici třídy L konstrukčních sad.

Nakonec je třeba zmínit, že existují kontexty, ve kterých jsou vhodné teorie aritmetiky druhého řádu s méně než plným porozuměním. Například, jeden může vzít teorii ACA daný Peano postuláty spolu s axiomy pochopení pro rovnice prvního řádu. Ukázalo se, že takové teorie jsou použitelné pro studium „reverzní matematiky“.

Bibliografie

• Boolos, George, 1975. „Logika druhého řádu“, The Journal of Philosophy, 72: 509–527. Také v Logic, Logic a Logic, George Boolos, Cambridge, MA: Harvard University Press, 1998, s. 37–53.
• Church, Alonzo, 1956. Úvod do matematické logiky, svazek 1. Princeton: Princeton University Press.
• –––, 1972. „Axiomy pro funkční kalkulky vyššího řádu“v logice a umění: Eseje na počest Nelsona Goodmana, Richarda S. Rudnera a Israel Schefflera (ed.), Indianapolis a New York: Bobbs-Merrill Company, str. 197–213.
• Enderton, Herbert B., 2001. Matematický úvod do logiky, druhé vydání. San Diego: Academic Press.
• Fagin, Ronald, 1974. „Generalized Spectra First-Order Spectra and Polynomial-Time Rozpoznatelné množiny,“v Complexity of Computation, Richard M. Karp (ed.), SIAM-AMS Proceedings, sv. 7, Providence: American Mathematical Society, s. 43–73.
• Garland Stephen J., 1974. „Kardinální charakterizace druhého řádu“, v Axiomatické teorii množin, Thomas J. Jech (ed.), Sborník Symposia in Pure Mathematics, sv. 13, část 2, Providence: American Mathematical Society, pp. 127–146.
• Grzegorczyk, Andrzej, A. Mostowski a C. Ryll-Nardzewski, 1958. „Klasická a ω-úplná aritmetika,“Žurnál symbolické logiky, 23: 188–205.
• Henkin, Leon, 1950. „Úplnost v teorii typů,“Žurnál symbolické logiky, 15: 81–91.
• Hintikka, K. Jaakko, 1955. „Redukce v teorii typů“, ve dvou dokumentech o symbolické logice, Acta Philosophica Fennica, č. 8, Helsinky, s. 57–115.
• Montague, Richard, 1965. „Redukce logiky vyššího řádu“v Teorie modelů, JW Addison, Leon Henkin a Alfred Tarski (eds.), Amsterdam: North-Holland Publishing Co., str. 251–264.
• Mostowski, Andrzej, 1961. „Formální systém analýzy založený na infinitistickém důkazu“, v Infinitistických metodách, Varšava: Państwowe Wydawnictwo Naukowe a Oxford, Londýn, New York a Paříž: Pergamon Press, str. 141–166.
• Orey, Steven, 1956. „Co se týče konzistence a souvisejících vlastností“, The Journal of Symbolic Logic, 21: 246–252.
• Shapiro, Stewart, 1991. Nadace bez zakladatelství: Případ logiky druhého řádu. Oxford: Oxford University Press.
• Simpson, Stephen, 1999. Podsystémy aritmetiky druhého řádu. Berlín: Springer.
• Väänänen, Jouko, 2001. „Logika druhého řádu a základy matematiky,“Bulletin symbolické logiky, 7: 504–520.

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Indiana Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

[Obraťte se na autora s návrhy.]