Robinsonova aritmetika - Robinson arithmetic

v matematika, Robinsonova aritmetika je konečně axiomatizovaný fragment prvního řádu Peano aritmetika (PA), nejprve stanoveno R. M. Robinson v roce 1950. Obvykle se označuje Q. Q je téměř PA bez schéma axiomu z matematická indukce. Q je slabší než PA, ale má stejný jazyk a obě teorie jsou neúplný. Q je důležité a zajímavé, protože se jedná o konečně axiomatizovaný fragment PA, který je rekurzivně nekompletní a v podstatě nerozhodnutelné.

Axiomy

The logika pozadí z Q je logika prvního řádu s identita, označeno infix '='. Jednotlivci, volal přirozená čísla, jsou členy a soubor volala N s významným členem 0, volala nula. Tam jsou tři operace přes N:

• A unární provoz volala nástupce a označeno předpona  S;
• Dva binární operace, přidání a násobení, označeno infix + a tím zřetězení, resp.

Následující axiomy pro Q jsou Q1 – Q7 v Burgessovi (2005: 42) (viz také axiomy z aritmetika prvního řádu ). Proměnné není vázán existenční kvantifikátor jsou vázány implicitně univerzální kvantifikátor.

1. Sx ≠ 0
   • 0 není nástupcem žádného čísla.
2. (Sx = Sy) → X = y
   • Pokud nástupce X je totožný s nástupcem y, pak X a y jsou identické. (1) a (2) přinášejí minimum faktů o N (je to nekonečná sada ohraničen 0) a S (je to injekční funkce jehož doména je N) potřebné pro nepodstatnost. The konverzovat z (2) vyplývá z vlastností identity.
3. y=0 ∨ ∃X (Sx = y)
   • Každé číslo je buď 0 nebo nástupce nějakého čísla. The schéma axiomu z matematická indukce přítomný v aritmetice silnější než Q promění tento axiom v teorém.
4. X + 0 = X
5. X + Sy = S(X + y)
   • (4) a (5) jsou rekurzivní definice z přidání.
6. X·0 = 0
7. x · Sy = (x · y) + X
   • (6) a (7) jsou rekurzivní definice z násobení.

Varianty axiomatizací

Axiomy v Robinsonovi (1950) jsou (1) - (13) v Mendelsonu (1997: 201). Prvních 6 z Robinsonových 13 axiomů je požadováno pouze tehdy, když na rozdíl od zde logika pozadí nezahrnuje identitu.

Obvyklý přísný celková objednávka na N, „méně než“ (označeno „<“), lze definovat z hlediska přidání prostřednictvím pravidla X < y ↔ ∃z (Sz + X = y). Ekvivalentně získáme definitivní konzervativní rozšíření Q tím, že vezmeme „<“ jako primitivní a přidáme toto pravidlo jako osmý axiom; tento systém se nazývá „Robinsonova aritmetika R"in Boolos et al. (2002: Sec 16.4).

Jiné rozšíření Q, kterému dočasně říkáme Q +, se získá, pokud vezmeme "<" jako primitivní a přidáme (místo posledního definičního axiomu) následující tři axiomy k axiómům (1) - (7) z Q:

• ¬(X < 0)
• X < Sy ↔ (X < y ∨ X = y)
• X < y ∨ X = y ∨ y < X

Q + je stále konzervativní příponou Q, v tom smyslu, že jakýkoli vzorec prokazatelný v Q + neobsahující symbol "<" je již prokazatelné v Q. (Přidání pouze prvních dvou z výše uvedených tří axiomů do Q dává konzervativní rozšíření Q to je ekvivalent toho, co Burgess 2005: 56 volá Q *. Viz také Burgess 2005: 230 fn. 24, ale všimněte si, že druhý z výše uvedených tří axiomů nelze odvodit z „čistého definičního rozšíření“ z Q získáno přidáním pouze axiomu X < y ↔ ∃z (Sz + X = y).)

Mezi axiomy (1) - (7) z Q, axiom (3) potřebuje vnitřní existenční kvantifikátor. Shoenfield (1967: 22) dává axiomatizaci, která má pouze (implicitní) vnější univerzální kvantifikátory, tím, že upustí od axiomu (3) Q ale přidání výše uvedených tří axiomů s Q + minus axiom (3) a je přísně slabší než Q +, protože axiom (3) je nezávislý na ostatních axiomech (například ordinály menší než ${ displaystyle omega ^ { omega}}$ tvoří model pro všechny axiomy kromě (3), když Sv je interpretován jako proti + 1). Shoenfieldův systém se objevuje také v Boolos et al. (2002: Sec 16.2), kde se tomu říká „minimální aritmetika"(také označeno Q). Úzce související axiomatizace, která používá „≤“ místo „<“, lze nalézt v Machover (1996: 256–57).

Metamatematika

Na metamatematice Q, viz Boolos et al. (2002: kapitola 16), Tarski, Mostowski a Robinson (1953), Smullyan (1991), Mendelson (1997: 201–03) a Burgess (2005: §§1.5a, 2.2). The zamýšlený výklad z Q je přirozená čísla a jejich obvyklá aritmetika, ve které přidání a násobení mají svůj obvyklý význam, identita je rovnost, Sx = X + 1, a 0 je přirozené číslo nula.

Libovolný model (struktura), který splňuje všechny axiomy Q až na to, že axiom (3) pravděpodobně má jedinečný submodel („standardní část“) izomorfní se standardními přirozenými čísly (N, +, ·, S, 0). (Axiom (3) nemusí být splněn; například polynomy s nezápornými celočíselnými koeficienty tvoří model, který splňuje všechny axiomy kromě (3).)

Q, jako Peano aritmetika, má nestandardní modely všeho nekonečného kardinality. Na rozdíl od aritmetiky Peano však Tennenbaumova věta neplatí pro Qa má vypočítatelné nestandardní modely. Například existuje vypočítatelný model Q sestávající z polynomů s celočíselnými koeficienty s kladným vedoucím koeficientem plus nulového polynomu s jejich obvyklou aritmetikou.

Pozoruhodná charakteristika Q je absence schématu axiomu indukce. Proto je často možné prokázat se v Q každá konkrétní instance skutečnosti o přirozených číslech, ale ne související obecná věta. Například 5 + 7 = 7 + 5 je prokazatelný v Q, ale obecné tvrzení X + y = y + X není. Podobně to nelze dokázat Sx ≠ X (Burgess 2005: 56). Model Q že selže mnoho standardních faktů se získá spojením dvou odlišných nových prvků a a b se standardním modelem přirozených čísel a definováním Sa = a, Sb = b, x + a = b a x + b = a pro všechna x, a + n = a a b + n = b, pokud n je standardní přirozené číslo, x · 0 = 0 pro všechna x, a · n = b a b · n = a, pokud n je nenulové standardní přirozené číslo, x · a = a pro všechna x kromě x = a, x · b = b pro všechna x s výjimkou x = b, a · a = b a b · b = a (Boolos et al, 2002 Sec 16.4).

Q je interpretovatelný ve fragmentu Zermelo axiomatická teorie množin, skládající se z extenzionalita, existence prázdná sada a axiom adjunkce. Tato teorie je S 'v Tarski et al. (1953: 34) a ST in Burgess (2005: 90–91; 223). Vidět obecná teorie množin Více podrobností.

Q je fascinující, protože je definitivně axiomatizovaný teorie prvního řádu to je podstatně slabší než Peano aritmetika (PA) a jejichž axiomy obsahují pouze jeden existenční kvantifikátor, přesto jako PA je neúplný a neúplný ve smyslu Gödelovy věty o neúplnosti a v zásadě nerozhodnutelné. Robinson (1950) odvodil Q axiomy (1) - (7) výše uvedením toho, jaké PA axiomy jsou požadovány k prokázání (Mendelson 1997: Th. 3.24), že každý vypočítatelná funkce je reprezentativní^{[je zapotřebí objasnění ]} v PA. Jediné použití, které tento důkaz dělá ze schématu PA axiomu z indukce je dokázat tvrzení, které je axiomem (3) výše, a tak jsou všechny vypočítatelné funkce reprezentovatelné v Q (Mendelson 1997: Th. 3,33, Rautenberg 2010: 246). Závěr druhé Gödelovy věty o neúplnosti také platí Q: žádné konzistentní rekurzivně axiomatizované prodloužení Q může prokázat svou vlastní konzistenci, i když navíc omezíme Gödelovy počty důkazů na definovatelný řez (Bezboruah a Shepherdson 1976; Pudlák 1985; Hájek & Pudlák 1993: 387).

První teorém o neúplnosti platí pouze pro axiomatické systémy definující dostatečnou aritmetiku pro provedení nezbytných kódovacích konstrukcí (z nichž Gödelovo číslování tvoří součást). Axiomy Q byly vybrány konkrétně, aby se zajistilo, že jsou pro tento účel dostatečně silné. K prokázání toho lze tedy použít obvyklý důkaz první věty o neúplnosti Q je neúplný a nerozhodnutelný. To naznačuje, že neúplnost a nerozhodnost PA nelze vinit z jediného aspektu PA, který ji odlišuje od Q, jmenovitě schéma axiomu z indukce.

Gödelovy věty neplatí, když je vynechán některý ze sedmi výše uvedených axiomů. Tyto fragmenty Q zůstávají nerozhodnutelní, ale již nejsou v zásadě nerozhodnutelní: mají konzistentní rozhodovatelná rozšíření i nezajímavé modely (tj. modely, které nejsou koncovými rozšířeními standardních přirozených čísel).

Viz také

• Gentzenův důkaz konzistence
• Gödelova věta o neúplnosti
• Seznam teorií prvního řádu
• Peanoovy axiomy
• Presburgerova aritmetika
• Skolemská aritmetika
• Aritmetika druhého řádu
• Set-teoretická definice přirozených čísel
• Obecná teorie množin

Reference

• A. Bezboruah a John C. Shepherdson, 1976. „Gödelova druhá věta o neúplnosti pro Q“. Journal of Symbolic Logic v. 41 n. 2, str. 503–512.
• George Boolos John P. Burgess a Richard Jeffrey, 2002. Vyčíslitelnost a logika, 4. vyd. Cambridge University Press.
• Burgess, John P., 2005. Stanovení Frege. Princeton University Press.
• Petr Hájek a Pavel Pudlák (1998) [1993]. Metamathematika aritmetiky prvního řádu, 2. vyd. Springer-Verlag.
• Lucas, J. R., 1999. Konceptuální kořeny matematiky. Routledge.
• Machover, Moshe, 1996. Teorie množin, logika a jejich omezení. Cambridge University Press.
• Mendelson, Elliott, 1997. Úvod do matematické logiky, 4. vyd. Chapman & Hall.
• Pavel Pudlák, 1985. „Střihy, prohlášení o shodě a interpretace“. Journal of Symbolic Logic v. 50 n. 2, s. 423–441.
• W. Rautenberg (2010), Stručný úvod do matematické logiky (3. vyd.), New York: Springer Science + Business Media, doi:10.1007/978-1-4419-1221-3, ISBN  978-1-4419-1220-6.
• R. M. Robinson, 1950, "Zásadně nerozhodnutelný systém axiomu" v Sborník z mezinárodního kongresu matematiky 1950, s. 729–730.
• Joseph R. Shoenfield, 1967. Matematická logika. Addison Wesley. (Přetištěno Asociací pro symbolickou logiku a A K Petersem v roce 2000.)
• Raymond Smullyan, 1991. Gödelovy věty o neúplnosti. Oxford University Press.
• Alfred Tarski, A. Mostowski, a R. M. Robinson, 1953. Nerozhodnutelné teorie. Severní Holandsko.