Aritmetika druhého řádu - Second-order arithmetic

v matematická logika, aritmetika druhého řádu je sbírka axiomatický systémy, které formalizují přirozená čísla a jejich podmnožiny. Je to alternativa k axiomatická teorie množin jako nadace pro hodně, ale ne pro všechny, matematiku.

Předchůdce aritmetiky druhého řádu, která zahrnuje parametry třetího řádu, byl zaveden David Hilbert a Paul Bernays ve své knize Grundlagen der Mathematik. Standardní axiomatizace aritmetiky druhého řádu je označena Z₂.

Aritmetika druhého řádu zahrnuje, ale je výrazně silnější než její první objednávka protějšek Peano aritmetika. Na rozdíl od Peano aritmetiky, aritmetika druhého řádu umožňuje kvantifikace nad množinami přirozených čísel i samotných čísel. Protože reálná čísla lze reprezentovat jako (nekonečný ) množiny přirozených čísel známými způsoby, a protože aritmetika druhého řádu umožňuje kvantifikaci nad těmito množinami, je možné formalizovat reálná čísla v aritmetice druhého řádu. Z tohoto důvodu se aritmetika druhého řádu někdy nazývá „analýza “(Sieg 2013, s. 291).

Aritmetiku druhého řádu lze také považovat za slabou verzi teorie množin ve kterém je každý prvek buď přirozeným číslem, nebo množinou přirozených čísel. I když je mnohem slabší než Teorie množin Zermelo – Fraenkel, aritmetika druhého řádu může dokázat v podstatě všechny výsledky z klasická matematika vyjádřitelný v jeho jazyce.

A subsystém aritmetiky druhého řádu je teorie v jazyce aritmetiky druhého řádu, z nichž každý axiom je teorémem úplné aritmetiky druhého řádu (Z₂). Takové subsystémy jsou nezbytné reverzní matematika, výzkumný program zkoumající, kolik klasické matematiky lze odvodit v určitých slabých subsystémech různé síly. V těchto slabých subsystémech lze formalizovat velkou část základní matematiky, z nichž některé jsou definovány níže. Reverzní matematika také objasňuje rozsah a způsob, jakým je klasická matematika nekonstruktivní.

Definice

Syntax

Jazyk aritmetiky druhého řádu je dva tříděné. První druh podmínky a zejména proměnné, obvykle označované malými písmeny, se skládá z Jednotlivci, jehož zamýšlená interpretace je jako přirozená čísla. Jiný druh proměnných, různě nazývaný „proměnné sady“, „proměnné třídy“ nebo dokonce „predikáty“, jsou obvykle označeny velkými písmeny. Vztahují se k třídám / predikátům / vlastnostem jednotlivců, takže je lze považovat za množiny přirozených čísel. Jednotlivci i množinu proměnných lze kvantifikovat univerzálně nebo existenciálně. Vzorec s ne vázaný jsou nastaveny proměnné sady (tj. žádné kvantifikátory nad nastavenými proměnnými) aritmetický. Aritmetický vzorec může mít volně nastavené proměnné a vázané jednotlivé proměnné.

Jednotlivé členy jsou tvořeny z konstanty 0, unární funkce S (dále jen nástupnická funkce ) a binární operace + a ${displaystyle cdot}$ (sčítání a násobení). Funkce nástupce přidá 1 ke svému vstupu. Vztahy = (rovnost) a <(srovnání přirozených čísel) se týkají dvou jedinců, zatímco vztah ∈ (členství) se týká jednotlivce a množiny (nebo třídy). V zápisu je tedy jazyk aritmetiky druhého řádu dán podpisem ${displaystyle {mathcal {L}} = {0, S, +, cdot, =, <, v}}$.

Například, ${displaystyle forall n (nin Xightarrow Snin X)}$, je dobře formulovaný vzorec aritmetiky druhého řádu, která je aritmetická, má jednu volnou množinu proměnné X a jednu vázanou individuální proměnnou n (ale žádné vázané proměnné sady, jak je požadováno u aritmetického vzorce) - přestože ${displaystyle existuje Xforall n (nin Xleftrightarrow n$ je dobře vytvořený vzorec, který není aritmetický a má jednu vázanou proměnnou množiny X a jednu vázanou individuální proměnnou n.

Sémantika

Je možné několik různých interpretací kvantifikátorů. Pokud je aritmetika druhého řádu studována pomocí plné sémantiky logika druhého řádu pak se množiny kvantifikátorů pohybují ve všech podskupinách rozsahu číselných proměnných. Pokud je aritmetika druhého řádu formována pomocí sémantiky logika prvního řádu (Henkinova sémantika) pak jakýkoli model obsahuje doménu pro set proměnných, které se mohou rozšířit, a tato doména může být řádnou podmnožinou plné sady sil domény doménových proměnných (Shapiro 1991, s. 74–75).

Axiomy

Základní

Následující axiomy jsou známé jako základní axiomy, nebo někdy Robinsonovy axiomy. Výsledný teorie prvního řádu, známý jako Robinsonova aritmetika, je v zásadě Peano aritmetika bez indukce. The doména diskurzu pro kvantifikované proměnné je přirozená čísla, souhrnně označeno N, včetně významného člena ${displaystyle 0}$, volala "nula."

Primitivní funkce jsou unární nástupnická funkce, označeno předpona ${displaystyle S}$a dva binární operace, přidání a násobení, označeno infix „+“ a „${displaystyle cdot}$", respektive. Existuje také primitiv binární relace volala objednat, označeno příponou „<“.

Axiomy řídící nástupnická funkce a nula:

1. ${displaystyle forall m [Sm = 0ightarrow ot].}$ („Nástupce přirozeného čísla není nikdy nula“)

2. ${displaystyle forall mforall n [Sm = Snightarrow m = n].}$ („Nástupnická funkce je injekční ”)

3. ${displaystyle forall n [0 = nlor existuje m [Sm = n]].}$ („Každé přirozené číslo je nula nebo nástupce“)

Přidání definovaný rekurzivně:

4. ${displaystyle forall m [m + 0 = m].}$

5. ${displaystyle forall mforall n [m + Sn = S (m + n)].}$

Násobení definováno rekurzivně:

6. ${displaystyle forall m [mcdot 0 = 0].}$

7. ${displaystyle forall mforall n [mcdot Sn = (mcdot n) + m].}$

Axiomy řídící objednávkový vztah "<":

8. ${displaystyle forall m [m <0ightarrow ot].}$ („Žádné přirozené číslo není menší než nula“)

9. ${displaystyle forall nforall m [m$

10. ${displaystyle forall n [0 = nlor 0$ („Každé přirozené číslo je nula nebo větší než nula“)

11. ${displaystyle forall mforall n [(Sm$

Tyto axiomy jsou všechny výpisy prvního řádu. To znamená, že všechny proměnné jsou v rozsahu přirozená čísla a ne sady to je fakt ještě silnější než jejich aritmetika. Kromě toho existuje jen jeden existenční kvantifikátor, v axiomu 3. Axiomy 1 a 2, spolu s an axiomové schéma indukce tvoří obvyklé Peano-Dedekind definice N. Přidání těchto axiomů jakéhokoli druhu axiomové schéma indukce dělá nadbytečné axiomy 3, 10 a 11.

Schéma indukce a porozumění

Pokud φ (n) je vzorec aritmetiky druhého řádu s proměnnou volného čísla n a možné další volné číslo nebo nastavené proměnné (zapsané m_• a X_•), indukční axiom pro φ je axiom:

${displaystyle forall mforall X ((varphi (0) land forall n (varphi (n) ightarrow varphi (Sn))) ightarrow forall nvarphi (n))}$

(úplný) indukční schéma druhého řádu se skládá ze všech instancí tohoto axiomu, přes všechny vzorce druhého řádu.

Jeden zvláště důležitý příklad indukčního schématu je, když φ je vzorec „${displaystyle nin X}$“Vyjadřující skutečnost, že n je členem X (X je proměnná volné množiny): v tomto případě je indukční axiom pro φ

${displaystyle forall X ((0in Xland forall n (nin Xightarrow Snin X)) ightarrow forall n (nin X))}$

Tato věta se nazývá indukční axiom druhého řádu.

Pokud φ (n) je vzorec s volnou proměnnou n a případně další volné proměnné, ale ne proměnnou Z, axiom porozumění pro φ je vzorec

${displaystyle existuje Zforall n (nin Zleftrightarrow varphi (n))}$

Tento axiom umožňuje sestavit množinu ${displaystyle Z = {n | varphi (n)}}$ přirozených čísel vyhovujících φ (n). Existuje technické omezení, že vzorec φ nemusí proměnnou obsahovat Z, jinak vzorec ${displaystyle není v Z}$ by vedlo k axiomu porozumění

${displaystyle existuje Zforall n (nin Zleftrightarrow není v Z)}$,

což je nekonzistentní. Tato konvence se předpokládá ve zbývající části tohoto článku.

Celý systém

Formální teorie aritmetika druhého řádu (v jazyce aritmetiky druhého řádu) se skládá ze základních axiomů, axiomu porozumění pro každý vzorec φ (aritmetický nebo jiný) a indukčního axiomu druhého řádu. Tato teorie se někdy nazývá úplná aritmetika druhého řádu odlišit ji od jejích subsystémů definovaných níže. Protože plná sémantika druhého řádu naznačuje, že existuje každá možná množina, lze při použití této sémantiky považovat axiomy chápání za součást deduktivního systému (Shapiro 1991, s. 66).

Modely

Tato část popisuje aritmetiku druhého řádu se sémantikou prvního řádu. Tak a Modelka ${displaystyle {mathcal {M}}}$ jazyka aritmetiky druhého řádu se skládá ze sady M (který tvoří rozsah jednotlivých proměnných) spolu s konstantou 0 (prvek M), funkce S z M na M, dvě binární operace + a · on M, binární relace Ma sbírku D podskupin M, což je rozsah nastavených proměnných. Vynechávání D vytvoří model jazyka aritmetiky prvního řádu.

Když D je plná sada M, model ${displaystyle {mathcal {M}}}$ se nazývá a plný model. Použití úplné sémantiky druhého řádu je ekvivalentní omezení modelů aritmetiky druhého řádu na plné modely. Ve skutečnosti mají axiomy aritmetiky druhého řádu pouze jeden úplný model. To vyplývá ze skutečnosti, že axiomy Peano aritmetika s indukčním axiomem druhého řádu mají pouze jeden model v rámci sémantiky druhého řádu.

Když M je obvyklá množina přirozených čísel s obvyklými operacemi, ${displaystyle {mathcal {M}}}$ se nazývá ω-model. V takovém případě lze model identifikovat pomocí D, jeho sbírka sad přirozených, protože tato sada stačí k úplnému určení modelu ω.

Jedinečný plný ${displaystyle omega}$-model, což je obvyklá množina přirozených čísel se svou obvyklou strukturou a všemi svými podmnožinami, se nazývá zamýšlený nebo Standard model aritmetiky druhého řádu.

Definovatelné funkce

Funkce prvního řádu, které jsou prokazatelně celkové v aritmetice druhého řádu, jsou přesně stejné jako ty, které jsou reprezentovatelné v systém F (Girard a Taylor 1987, s. 122–123). Systém F je téměř ekvivalentní teorií funkcionálů odpovídající aritmetice druhého řádu způsobem, který je paralelní s Gödelovým systém T odpovídá aritmetice prvního řádu v Výklad dialektiky.

Subsystémy

Existuje mnoho pojmenovaných subsystémů aritmetiky druhého řádu.

Dolní index 0 v názvu subsystému naznačuje, že obsahuje pouze omezenou část celého indukčního schématu druhého řádu (Friedman 1976). Takové omezení snižuje důkazní teoretická síla systému výrazně. Například systém ACA₀ popsáno níže je ekvikonzistentní s Peano aritmetika. Odpovídající teorie ACA, skládající se z ACA₀ plus celé schéma indukce druhého řádu je silnější než Peanoova aritmetika.

Aritmetické porozumění

Mnoho dobře prozkoumaných subsystémů souvisí s uzavíracími vlastnostmi modelů. Například lze ukázat, že každý ω-model úplné aritmetiky druhého řádu je uzavřen pod Turingův skok, ale ne každý model ω uzavřený pod Turingovým skokem je modelem plné aritmetiky druhého řádu. Subsystém ACA₀ zahrnuje jen dost axiomů k zachycení pojmu uzavření pod Turingovým skokem.

ACA₀ je definována jako teorie skládající se ze základních axiomů, aritmetické porozumění axiomu schéma (jinými slovy axiom porozumění pro každého aritmetický vzorec φ) a běžný indukční axiom druhého řádu. Bylo by ekvivalentní zahrnout celé aritmetické schéma indukčního axiomu, jinými slovy zahrnout indukční axiom pro každý aritmetický vzorec φ.

Je možné ukázat, že kolekce S podmnožin ω určuje ω-model ACA₀ kdyby a jen kdyby S je uzavřen pod Turingovým skokem, Turingovou redukovatelností a Turingovým spojením (Simpson 2009, s. 311–313).

Dolní index 0 v ACA₀ značí, že ne každá instance schématu indukční axiomy je součástí tohoto subsystému. To neznamená žádný rozdíl pro modely ω, které automaticky uspokojí každou instanci indukčního axiomu. Je to však důležité při studiu non-ω-modelů. Systém sestávající z ACA₀ plus indukce pro všechny vzorce se někdy nazývá ACA bez dolního indexu.

Systém ACA₀ je konzervativní rozšíření aritmetika prvního řádu (nebo Peanoovy axiomy prvního řádu), definované jako základní axiomy plus schéma indukčního axiomu prvního řádu (pro všechny vzorce φ, které neobsahují vůbec žádné proměnné třídy, vázané nebo jiné), v jazyce aritmetiky prvního řádu (který vůbec neumožňuje proměnné třídy). Zejména má to samé ordinální důkaz ε₀ jako aritmetika prvního řádu z důvodu omezeného indukčního schématu.

Aritmetická hierarchie vzorců

Vzorec se nazývá omezená aritmetikanebo Δ⁰₀, když jsou všechny jeho kvantifikátory ve tvaru ∀n<t nebo ∃n<t (kde n je kvantifikovaná jednotlivá proměnná a t je individuální pojem), kde

${displaystyle forall n$

znamená

${displaystyle forall n (n$

a

${displaystyle existuje n$

znamená

${displaystyle existuje n (n$.

Vzorec se nazývá Σ⁰₁ (nebo někdy Σ₁), respektive Π⁰₁ (nebo někdy Π₁) když má formu ∃m_•(φ), respektive ∀m_•(φ) kde φ je omezený aritmetický vzorec a m je individuální proměnná (která je v φ zdarma). Obecněji se vzorec nazývá Σ⁰_n, respektive Π⁰_n když se získá přidáním existujících, respektive univerzálních, jednotlivých kvantifikátorů k Π⁰_n−1, respektive Σ⁰_n−1 vzorec (a Σ⁰₀ a Π⁰₀ jsou ekvivalentní Δ⁰₀). Podle konstrukce jsou všechny tyto vzorce aritmetické (nikdy nejsou vázány žádné proměnné třídy) a ve skutečnosti vložením vzorce Skolem prenex forma je vidět, že každý aritmetický vzorec je ekvivalentní Σ⁰_n nebo Π⁰_n vzorec pro všechny dostatečně velké n.

Rekurzivní porozumění

Subsystém RCA₀ je slabší systém než ACA₀ a je často používán jako základní systém v reverzní matematika. Skládá se z: základních axiomů, Σ⁰₁ indukční schéma a Δ⁰₁ schéma porozumění. První termín je jasný: Σ⁰₁ indukční schéma je indukční axiom pro každé Σ⁰₁ vzorec φ. Výraz „Δ⁰₁ porozumění “je složitější, protože neexistuje nic jako Δ⁰₁ vzorec. Δ⁰₁ schéma porozumění místo toho uplatňuje axiom porozumění pro každé Σ⁰₁ vzorec, který je ekvivalentní Π⁰₁ vzorec. Toto schéma zahrnuje pro každé Σ⁰₁ vzorec φ a každé Π⁰₁ vzorec ψ, axiom:

${displaystyle forall mforall X ((forall n (varphi (n) leftrightarrow psi (n))) ightarrow existuje Zforall n (nin Zleftrightarrow varphi (n)))}$

Sada důsledků RCA prvního řádu₀ je stejný jako u subsystému IΣ₁ Peanovy aritmetiky, ve které je indukce omezena na Σ⁰₁ vzorce. Já zase₁ je konzervativní primitivní rekurzivní aritmetika (PRA) pro ${displaystyle Pi _ {2} ^ {0}}$ věty. Navíc, důkaz-teoretický řadový z ${displaystyle mathrm {RCA} _ {0}}$ je ω^ω, stejné jako u PRA.

Je vidět, že kolekce S podmnožin ω určuje ω-model RCA₀ kdyby a jen kdyby S je uzavřen pod Turingovou redukovatelností a Turingovým spojením. Zejména kolekce všech vypočítatelných podmnožin ω dává ω-model RCA₀. To je motivace názvu tohoto systému - pokud lze pomocí RCA dokázat existenci sady₀, pak je sada rekurzivní (tj. vypočítatelná).

Slabší systémy

Někdy ještě slabší systém než RCA₀ je žádoucí. Jeden takový systém je definován takto: je třeba nejprve rozšířit jazyk aritmetiky o exponenciální funkci (ve silnějších systémech lze exponenciál definovat z hlediska sčítání a násobení obvyklým trikem, ale když je systém příliš slabý, není to delší možné) a základní axiomy zjevnými axiomy definujícími umocňování indukčně z násobení; pak se systém skládá z (obohacených) základních axiomů plus Δ⁰₁ porozumění plus Δ⁰₀ indukce.

Silnější systémy

Přes ACA₀, každý vzorec aritmetiky druhého řádu je ekvivalentní Σ¹_n nebo Π¹_n vzorec pro všechny dostatečně velké n. Systém Π¹₁-pochopení je systém skládající se ze základních axiomů, plus obyčejný indukční axiom druhého řádu a axiom porozumění pro každý Π¹₁ vzorec φ. To odpovídá to¹₁-pochopení (na druhou stranu Δ¹₁-pochopení, definované analogicky k Δ⁰₁-pochopení, je slabší).

Projektivní rozhodnost

Projektivní rozhodnost je tvrzení, že každá dokonalá informační hra pro dva hráče s tahy, které jsou celá čísla, délka hry ω a sada projektivních výplat, je určena, což je jeden z hráčů, který má vítěznou strategii. (První hráč vyhrává hru, pokud hra patří do výplatní sady; v opačném případě vyhrává druhý hráč.) Sada je projektivní, pokud (jako predikát) je vyjádřitelná vzorcem v jazyce aritmetiky druhého řádu, což umožňuje reálná čísla jako parametry, takže projektivní determinace je vyjádřitelná jako schéma v jazyce Z₂.

Mnoho přirozených výroků vyjádřitelných v jazyce aritmetiky druhého řádu je nezávislých na Z₂ a dokonce ZFC ale jsou prokazatelné z projektivní rozhodnosti. Mezi příklady patří coanalytic dokonalá vlastnost podmnožiny, měřitelnost a majetek Baire pro ${displaystyle Sigma _ {2} ^ {1}}$ sady, ${displaystyle Pi _ {3} ^ {1}}$ uniformizace atd. Přes teorii slabé báze (například RCA₀), projektivní determinace implikuje porozumění a poskytuje v podstatě úplnou teorii aritmetiky druhého řádu - přirozené výroky v jazyce Z₂ které jsou nezávislé na Z₂ s projektivní determinancí je těžké najít (Woodin 2001).

ZFC + {existují n Woodin kardinálové: n je přirozené číslo} je konzervativní vůči Z₂ s projektivní determinancí, tj. výrok v jazyce aritmetiky druhého řádu je prokazatelný v Z₂ s projektivní determinancí, pokud je jeho překlad do jazyka teorie množin v ZFC + prokazatelný {existují n Woodin kardinálové: n∈N}.

Kódovací matematika

Aritmetika druhého řádu přímo formalizuje přirozená čísla a množiny přirozených čísel. Je však schopen nepřímo formalizovat další matematické objekty pomocí technik kódování, což si poprvé všiml Weyl (Simpson 2009, s. 16). Celá čísla, racionální čísla a reálná čísla lze formalizovat v subsystému RCA₀, spolu s úplnými oddělitelnými metrickými prostory a spojitými funkcemi mezi nimi (Simpson 2009, kapitola II).

Výzkumný program Reverzní matematika používá tyto formalizace matematiky v aritmetice druhého řádu ke studiu axiomů množinové existence potřebných k prokázání matematických vět (Simpson 2009, s. 32). Například věta o střední hodnotě pro funkce od reálných do reálných je v RCA prokazatelné₀ (Simpson 2009, s. 87), zatímco Bolzano–Weierstrassova věta je ekvivalentní ACA₀ přes RCA₀ (Simpson 2009, s. 34).

Viz také

• Paříž – Harringtonova věta
• Presburgerova aritmetika

Reference

• Burgess, J. P. (2005), Stanovení Frege, Princeton University Press.
• Buss, S. R. (1998), Příručka teorie důkazů, Elsevier. ISBN  0-444-89840-9
• Friedman, H. (1976), „Systémy aritmetiky druhého řádu s omezenou indukcí“, I, II (Abstrakty). Journal of Symbolic Logic, v. 41, s. 557–559. JStor
• Girard, L. a Taylor (1987), Důkazy a typy, Cambridge University Press.
• Hilbert, D. a Bernays, P. (1934), Grundlagen der Mathematik, Springer-Verlag. PAN0237246
• Sieg, W. (2013), Hilbertovy programy a další, Oxford University Press.
• Shapiro, S. (1991), Nadace bez nacionalismu, Oxford University Press. ISBN  0-19-825029-0
• Simpson, S. G. (2009), Podsystémy aritmetiky druhého řádu, 2. vydání, Perspectives in Logic, Cambridge University Press. ISBN  978-0-521-88439-6 PAN2517689
• Takeuti, G. (1975) Teorie důkazů ISBN  0-444-10492-5
• Woodin, W. H. (2001), „Hypotéza kontinua, část I“, Oznámení Americké matematické společnosti, v. 48 n. 6.