Epsilono Kalkulis

Turinys:

Epsilono Kalkulis
Epsilono Kalkulis

Video: Epsilono Kalkulis

Video: Epsilono Kalkulis
Video: Epsilon-delta limit definition 1 | Limits | Differential Calculus | Khan Academy 2024, Kovo
Anonim

Įėjimas Navigacija

  • Įstojimo turinys
  • Bibliografija
  • Akademinės priemonės
  • Draugai PDF peržiūra
  • Informacija apie autorius ir citata
  • Atgal į viršų

Epsilono kalkulis

Pirmą kartą paskelbta 2002 m. Gegužės 3 d. esminė peržiūra 2019 m. gegužės 6 d., pirmadienis

„Epsilon“skaičiavimas yra loginis formalizmas, kurį sukūrė Davidas Hilbertas, naudodamas savo programą matematikos pagrindais. „Epsilon“operatorius yra terminus formuojantis operatorius, kuris keičia įprasto predikato logikos kiekybinius parametrus. Tiksliau, skaičiavime terminas (varepsilon x A) žymi kai kuriuos (x) tenkinančius (A (x)), jei jų yra. Hilberto programoje epsilono terminai vaidina idealių elementų vaidmenį; finbertinių nuoseklumo įrodymų tikslas yra pateikti procedūrą, kuri pašalintų tokias sąvokas nuo oficialaus įrodymo. Procedūros, kuriomis tai turi būti atlikta, yra pagrįstos Hilbert'o epsilono pakeitimo metodu. Tačiau „epsilon“skaičiavimas taip pat gali būti naudojamas ir kituose kontekstuose. Pirmasis bendras epsilono skaičiavimo taikymas buvo Hilberto epsilono teoremose,o tai savo ruožtu sudaro pagrindą pirmajam teisingam Herbrando teoremos įrodymui. Pastaruoju metu kalbotyroje ir lingvistinėje filosofijoje buvo pritaikyti epsilono operatoriaus variantai sprendžiant anaforinius įvardžius.

  • 1. Apžvalga
  • 2. Epsilono kalkulis
  • 3. Epsilono teoremos
  • 4. Herbrando teorema
  • 5. Epsilono pakaitalo metodas ir aritmetika
  • 6. Naujausi pokyčiai
  • 7. „Epsilon“kalbotyros, filosofijos ir neklasikinės logikos operatoriai
  • Bibliografija
  • Akademinės priemonės
  • Kiti interneto šaltiniai
  • Susiję įrašai

1. Apžvalga

Amžiaus pabaigoje Davidas Hilbertas ir Henri Poincaré buvo pripažinti dviem svarbiausiais savo kartos matematikais. Hilberto matematinių interesų diapazonas buvo platus ir apėmė susidomėjimą matematikos pagrindais: jo „Geometrijos pagrindai“buvo paskelbti 1899 m. Ir iš klausimų, pateiktų 1900 m. Tarptautiniam matematikų kongresui, sąrašo, trys nagrinėjo aiškiai pagrindinius klausimus.

Po Russello paradokso paskelbimo, Hilbertas 1904 m. Pateikė pranešimą trečiajam tarptautiniam matematikų kongresui, kuriame pirmą kartą pateikė eskizą savo ketinime pateikti griežtą matematikos pagrindą per sintaksinės konsistencijos įrodymus. Bet jis negrįžo į šį dalyką nuoširdžiai iki 1917 m., Kai, pasitelkęs Pauliaus Bernayso pagalbą, pradėjo paskaitas apie matematikos pagrindus. Nors Hilbertą sužavėjo Russello ir Whiteheado darbai jų „Principia Mathematica“, jis įsitikino, kad logistų bandymas redukuoti matematiką į logiką negali būti sėkmingas, visų pirma dėl jų neperspektyvaus supratimo aksiomos pobūdžio. Tuo pat metu jis intuityvią atskirties vidurio įstatymo atmetimą įvertino kaip nepriimtiną matematikai. Todėl,siekiant išspręsti problemas, iškilusias dėl loginių ir aibių teorinių paradoksų atradimo, reikėjo naujo požiūrio, pagrindžiančio šiuolaikinius matematinius metodus.

Iki 1920 m. Vasaros Hilbertas suformulavo tokį požiūrį. Pirmiausia, šiuolaikiniai matematiniai metodai turėjo būti pateikiami formaliose dedukcinėse sistemose. Antra, šios formalios sistemos turėjo būti įrodomos sintaksiniu požiūriu nuoseklios, ne pateikiant modelį ar sumažinant jų nuoseklumą kitai sistemai, bet remiantis tiesioginiu metamatematiniu aiškaus, „baigtinio“pobūdžio argumentu. Šis požiūris tapo žinomas kaip Hilberto programa. „Epsilon“skaičiavimas turėjo pateikti pirmąjį šios programos komponentą, o jo „epsilon“pakeitimo metodas turėjo pateikti antrąjį.

Pagrindinė epsilono skaičiavimo forma yra pirmosios eilės predikatinės logikos pratęsimas naudojant „epsilono operaciją“, kuri pasirenka bet kurią tikrąją egzistencinę formulę egzistencinio kiekybinio rodiklio liudytoju. Pratęsimas yra konservatyvus ta prasme, kad neprideda jokių naujų pirmosios eilės padarinių. Bet, atvirkščiai, kiekybinius rodiklius galima apibrėžti pagal epsilonus, taigi pirmosios eilės logika gali būti suprantama kaip samprotavimai be kiekybinių veiksnių, susijusių su epsilono operacija. Būtent pastaroji savybė daro skaičiavimą patogų įrodant nuoseklumą. Tinkami „epsilon“skaičiavimų išplėtimai leidžia įterpti stipresnes kiekybines skaičių ir aibių teorijas į skaičiavimus be kiekybinių parametrų. Hilbertas tikėjosi, kad bus galima parodyti tokių pratęsimų nuoseklumą.

2. Epsilono kalkulis

1921 m. (1922 m.) Hamburge vykusioje paskaitoje Hilbertas pirmą kartą pristatė pasirinkimo funkcijų panaudojimo idėją, kad būtų galima išspręsti atskirto vidurio principą formalioje aritmetikos sistemoje. Šios idėjos buvo išplėstos epsilon skaičiavimais ir epsilon pakeitimo metodais per paskaitų kursus 1921–1923 m. Ir Hilbert (1923). Galutinį epsilon-calculus pristatymą galima rasti Wilhelmo Ackermanno disertacijoje (1924).

Šiame skyriuje bus aprašyta skaičiavimo versija, atitinkanti pirmosios eilės logiką, o pirmosios ir antrosios eilės aritmetikos plėtiniai bus aprašyti žemiau.

Tegul (L) yra pirmosios eilės kalba, tai yra konstantos, funkcijos ir santykio simbolių su nurodytomis arijomis sąrašas. Epsilono terminų aibė ir (L) formulių rinkinys yra induktyviai apibrėžti vienu metu, taip:

  • Kiekviena (L) konstanta yra terminas.
  • Kiekvienas kintamasis yra terminas.
  • Jei (s) ir (t) yra terminai, tada (s = t) yra formulė.
  • Jei (s_1, / ldot, s_k) yra terminai ir (F) yra (k) - funkcijos funkcijos simbolis (L, F (s_1, / ldots, s_k)) yra terminas.
  • Jei (s_1, / ldot, s_k) yra terminai ir (R) yra (k) - ary santykio simbolis (L, R (s_1, / ldots, s_k)) yra formulė.
  • Jei (A) ir (B) yra formulės, tai yra ir (A / pleištas B, A / vee B, A / dešinė rodyklė B) ir (neg A).
  • Jei (A) yra formulė, o (x) yra kintamasis, (varepsilon x A) yra terminas.

Pakeitimas ir laisvo bei surišto kintamojo sąvokos apibrėžiami įprastu būdu; visų pirma kintamasis (x) tampa įpareigotas terminu (varepsilon x A). Numatomas aiškinimas, kad (varepsilon x A) žymi kai kuriuos ((x)) tenkinančius (A), jei jų yra. Taigi, epsilono terminus valdo ši aksioma (Hilberto „neribota aksioma“): [A (x) dešinė rodyklė A (varepsilon x A)) Be to, epsilono skaičiavimuose yra visas aksiomų rinkinys, reguliuojantis klasikiniai teiginiai ir lygybės simbolį valdančios aksiomos. Vienintelės skaičiavimo taisyklės yra šios:

  • Modus ponens
  • Pakaitalas: iš (A (x)), užbaigia (A (t)), bet kuriam terminui (t.)

Ankstesnėse epsilon skaičiavimo formose (tokiose, kaip aprašytos Hilbert 1923 m.) Naudojama dviguba epsilon operatoriaus forma, kurioje (varepsilon x A) grąžina klastojančią reikšmę (A (x)). Aukščiau pateikta versija buvo naudojama Ackermanno disertacijoje (1924) ir tapo standartine.

Atminkite, kad ką tik aprašytas skaičiavimas neturi skaičiavimų. Kiekybinius rodiklius galima apibrėžti taip: (pradėti {lygiuoti} egzistuoja x A (x) & / equiv A (varepsilon x A) / \ forall x A (x) & / equiv A (varepsilon x (neg A)) end {lygiuoti}) Iš jų galima išvesti įprastas kiekybinių parametrų aksiomas ir taisykles, todėl aukščiau pateiktos apibrėžtys naudojamos norint įterpti pirmosios eilės logiką į „epsilon“skaičiavimus. Tačiau atvirkščiai, netiesa: ne kiekviena „epsilon“skaičiavimo formulė yra įprastos kiekybiškai išreikštos formulės vaizdas pagal šį įdėjimą. Taigi epsilono skaičiavimas yra išraiškingesnis nei pirminis skaičiavimas vien todėl, kad epsilono terminai gali būti derinami sudėtingesniais būdais nei kiekybiniai.

Verta paminėti, kad epsilono terminai yra nedeterminiški, taigi parodo pasirinktos aksiomos formą. Pvz., Kalboje su pastoviais simboliais (a) ir (b) (varepsilon x (x = a / vee x = b)) yra (a) arba (b), tačiau skaičiavimai palieka visiškai atvirus atvejus. Prie skaičiavimo galima pridėti išplėtimo schemą: (forall x (A (x) leftrightarrow B (x)) rightarrow / varepsilon x A = / varepsilon x B), kurie tvirtina, kad „epsilon“operatorius priskiria tą patį liudykite lygiavertes formules (A) ir (B). Tačiau daugeliui programų ši papildoma schema nėra būtina.

3. Epsilono teoremos

Antrame Hilberto ir Bernayso „Grundlagen der Mathematik“(1939) tome aprašomi to laiko epsilon-calculus rezultatai. Tai apima pirmosios ir antrosios epsilono teoremų, taikomų pirmosios eilės logikai, aptarimą, epsilono pakaitų metodą aritmetikai su atvira indukcija, ir analizės (tai yra antros eilės aritmetinės) su epsilon skaičiavimu sukūrimą.

Pirmoji ir antroji epsilono teoremos yra šios:

Pirmoji epsilono teorema: Tarkime, kad (gama / taurė {A }) yra kiekybinių formulių, neturinčių epsilono simbolio, rinkinys. Jei (A) yra išvestinis iš (Gamma) epsilon skaičiavime, tada (A) yra išvestinis iš (Gamma), naudojant predikto logiką be kiekybinių parametrų.

Antroji epsilono teorema: Tarkime, kad (gama / taurė {A }) yra formulių rinkinys, kuriame nėra epsilono simbolio. Jei (A) yra išvestinis iš (Gamma) epsilon skaičiavime, tada (A) yra išvestinis iš (Gamma) predikatinėje logikoje.

Pirmojoje epsilono teoremoje „predikato logika be kvantifikatoriaus“ketinama įtraukti aukščiau pateiktą pakeitimo taisyklę, todėl aksionai be kvantifikatorių elgiasi taip, kaip jų universalūs uždarymai. Kadangi epsilono skaičiavimai apima pirmosios eilės logiką, pirmoji epsilono teorema reiškia, kad bet kokio apvažiavimo per pirmosios eilės predikatinę logiką, naudojamą norint gauti kvantifikatoriaus teoremą iš aksiomų be kvantifikatoriaus, galima išvengti. Antroji epsilono teorema parodo, kad taip pat galima išvengti bet kokio apvažiavimo per epsilon skaičiavimą, naudojamą teoremos apskaičiavimui predikato skaičiavimo kalba iš aksiomų predikato skaičiavimo kalba.

Apskritai, pirmojoje epsilono teoremoje nustatyta, kad kiekybinius rodiklius ir epsilonus visada galima pašalinti iš formulės, kurioje nėra kiekybinio įvertinimo, įrodymų, susijusių su kitomis formulėmis, kuriose nėra kiekybinio vertiklio. Tai ypač svarbu Hilberto programai, nes epsilonai matematikoje vaidina idealių elementų vaidmenį. Jei formulės be kiekybinio įvertinimo neatitinka „tikrosios“matematinės teorijos dalies, pirmoji epsilono teorema parodo, kad idealiųjų elementų galima pašalinti iš realių teiginių įrodymų, jei aksiomos taip pat yra tikrosios.

Ši idėja yra tiksliai apibrėžta tam tikroje bendrojo nuoseklumo teoremoje, kurią Hilbertas ir Bernaysas kildina iš pirmosios epsilono teoremos, kuri sako: „Tegul (F) yra bet kokia oficiali sistema, atsirandanti dėl predikato skaičiavimo, pridedant pastovią, funkciją., ir predikatiniai simboliai bei tikrosios aksiomos, neturinčios kvantifikatorių ir epsilono, ir tarkime, kad atominių formulių tiesa naujojoje kalboje yra priimtina. Tada (F) yra nuoseklus stipria prasme, kad kiekviena išmatuojama formulė be skaitmenų ir be epsilono yra teisinga. Hilbertas ir Bernaysas naudoja šią teoremą, kad pateiktų elementarios geometrijos nuoseklų nuoseklumą (1939, 1.4 skyrius).

Pateikti aritmetikos ir analizės nuoseklumo įrodymus sudėtinga šį rezultatą išplėsti tais atvejais, kai aksiomose taip pat yra idealiųjų elementų, ty epsilono terminai.

Papildoma literatūra. Originalūs šaltiniai apie epsilon-calculus ir epsilon teoremas (Ackermann 1924, Hilbert & Bernays 1939) tebėra prieinami tik vokiečių kalba. 1969 m. Leisenring yra palyginti šiuolaikiška knygos „epsilon calculus“įvadas anglų kalba. Pirmoji ir antroji epsilono teorema išsamiai aprašytos Zach 2017. Moser & Zach 2006 pateikia išsamią bylos analizę be lygybės. Originalūs įrodymai pateikiami už aksiomatines „epsilon-calculus“formas. 1955 m. Maehara buvo pirmoji, kuri svarstė nuoseklųjį skaičiavimą su epsilono terminais. Jis parodė, kaip įrodyti antrąją epsilono teoremą, naudojant pjūvio eliminaciją, ir tada sustiprino teoremą įtraukdamas išplėtimo schemą (Maehara 1957). Baaz ir kt. 2018 m. Pateiks patobulintą pirmosios epsilono teoremos versiją. Klaidų pataisymus literatūroje (įskaitant Leisenringo knygą) galima rasti Flannagan 1975; „Ferrari 1987“; ir Yasuhara 1982. Epsilon skaičiavimo variacija, pagrįsta Skolem funkcijomis ir todėl suderinama su pirmosios eilės logika, aptariama Davis & Fechter 1991.

4. Herbrando teorema

Hilbertas ir Bernays naudojo epsilono skaičiavimo metodus, kad sudarytų pirmosios eilės logikos teoremas, kuriose nėra jokios nuorodos į patį epsilon skaičiavimą. Vienas iš tokių pavyzdžių yra Herbrando teorema (Herbrand 1930; žr. Buss 1995, Girard 1982 ir Buss 1998, 2.5 skirsnis). Tai dažnai formuluojama kaip teiginys, kad jei egzistencinė formulė (egzistuoja x_1 / ldots / egzistuoja x_k A (x_1, / ldots, x_k)) yra išvedama pirmosios eilės predikatinėje logikoje (be lygybės), kur (A) nėra kiekybinių parametrų, tada yra terminų sekos (t_ {1} ^ 1, / ldot, t_ {k} ^ 1, / ldots, t_ {1} ^ n, / ldots, t_k ^ n), toks, kad [A (t_ {1} ^ 1, / ldots, t_k ^ 1) vee / ldots / vee A (t_ {1} ^ n, / ldots, t_k ^ n)) yra tautologija. Jei su lygybe susiduriame su pirmos eilės logika,„tautologiją“reikia pakeisti „lygybės aksiomų pakeitimo atvejų tautologinėmis pasekmėmis“; tokiai formulei apibūdinti naudosime terminą „kvazi-tautologija“.

Ką tik aprašyta Herbrando teoremos versija iš karto išplaukia iš išplėstinės pirmosios Epsilono teoremos, kurią sukūrė Hilbertas ir Bernaysas. Taikydami metodus, susijusius su antrosios epsilono teoremos įrodymu, tačiau Hilbertas ir Bernaysas pasiekė stipresnį rezultatą, kuris, kaip ir Herbrando originali formuluotė, suteikia daugiau informacijos. Norėdami suprasti dvi žemiau pateiktos teoremos dalis, padeda apsvarstyti tam tikrą pavyzdį. Tegul (A) yra formulė

(egzistuoja x_1 / forall x_2 / egzistuoja x_3 / forall x_4 B (x_1, x_2, x_3, x_4)), kur (B) nėra kiekybinių parametrų. Neigimas (A) yra lygus (forall x_1 / egzistuoja x_2 / forall x_3 / egzistuoja x_4 / neg B (x_1, x_2, x _3, x_4).) Skolemizuodami, ty naudodamiesi funkcijos simboliais egzistenciniams kiekybiniams rodikliams gauti gauname (egzistuoja f_2, f_4 / forall x_1, x_3 / neg B (x_1, f_2 (x_1), x_3, f_4 (x_1, x_3))..) Neigdami to, pamatome, kad pradinė formulė yra „lygiavertė“(forall f_2, f_4 / egzistuoja x_1, x_3 B (x_1, f_2 (x_1), x_3, f_4 (x_1, x_3)).)

Pirmasis žemiau pateiktos teoremos sakinys šiuo konkrečiu atveju sako, kad aukščiau pateikta formulė (A) yra išvedama pirmosios eilės logika tada ir tik tada, kai yra terminų seka (t_ {1} ^ 1, t_ {3} ^ 1, / ldots, t_ {1} ^ n, t_ {3} ^ n) išplėstine kalba su (f_2) ir (f_4) tokia, kad [B (t_ {1} ^ 1, f_2 (t_ {1} ^ 1), t_ {3} ^ 1, f_4 (t_ {1} ^ 1, t_ {3} ^ 1)) vee / ldots / vee B (t_ {1} ^ n, f_2 (t_ {1} ^ n), t_ {3} ^ n, f_4 (t_ {1} ^ n, t_ {3} ^ n))] yra kvazi-tautologija.

Antroji teoremos sąlyga, šiuo konkrečiu atveju, sako, kad aukščiau pateikta formulė (A) yra išvedama pirmosios eilės logika tada ir tik tada, kai yra kintamųjų sekos (x_ {2} ^ 1, x_ { 4} ^ 1, / ldot, x_2 ^ n, x_4 ^ n) ir terminai (s_ {1} ^ 1, s_ {3} ^ 1, / ldots, s_1 ^ n, s_3 ^ n) originale kalba tokia, kad [B (s_ {1} ^ 1, x_ {2} ^ 1, s_ {3} ^ 1, x_4 ^ 1) vee / ldots / vee B (s_1 ^ n, x_2 ^ n, s_3 ^ n, x_4 ^ n)) yra kvazi-tautologija ir tokia, kad (A) išvedama iš šios formulės, naudojant tik žemiau aprašytas kiekybinio koeficiento ir idempotencijos taisykles.

Paprastai tariant, (A) yra bet kokia prenexo formulė, kurios forma yra [(mathbf {Q} _1 x_1 / ldots / mathbf {Q} _n x_n B (x_1, / ldots, x_n),) kur (B) be kiekybinių parametrų. Tada sakoma, kad (B) yra (A) matrica, ir (B) egzempliorius gaunamas pakeičiant kai kurių jo kintamųjų terminus (B) kalba. Herbrando normalioji forma (A ^ H) (A) gaunama

  • išbraukiant kiekvieną universalųjį kiekybinį rodiklį, ir
  • pakeičiant kiekvieną visuotinai apskaičiuotą kintamąjį (x_i) į (f_i (x_ {i} ^ 1, / ldots, x_ {i} ^ {k (i)})), kur (x_ {i} ^ 1, / taškai, x_ {i} ^ {k (i)}) yra kintamieji, atitinkantys egzistencinius kiekybinius rodiklius prieš (mathbf {Q} _i), esančius (A) (eilės tvarka), ir (f_i)) yra naujas funkcijos simbolis, paskirtas šiam vaidmeniui.

Kai mes kalbame apie ((A ^ H)) matricos egzempliorių, turime omenyje formulę, gaunamą pakeičiant terminus išplėstine kalba (A ^ H) matricoje. Dabar galime pasakyti Hilberto ir Bernayso formuluotę

Herbrando teorema. (1) Prenexo formulę (A) galima apskaičiuoti predikatiniame skaičiavime, jei ir tik tada, kai yra ((A ^ H)) matricos, kuri yra kvazi-tautologija, pavyzdžių atskyrimas.

(2) Prenexo formulę (A) galima apskaičiuoti predikatiniame skaičiavime tada ir tik tada, kai yra (A) matricos egzempliorių disjunkcija (bigvee_j B_j), kad (bigvee_j B_j) yra kvazi-tautologija, o (A) išvedama iš (bigvee_j B_j), naudojant šias taisykles:

  • iš (C_1 / vee / ldots / vee C_i (t) vee / ldots / vee C_m)

    sudaryti (C_1 / vee / ldots / vee / egzistuoja x C_i (x) vee / ldots / vee C_m) ir

  • iš (C_1 / vee / ldots / vee C_i (x) vee / ldots / vee C_m)

    sudaryti (C_1 / vee / ldots / vee / forall xC_i (x) vee / ldots / vee C_m) (jei (x) ne (C_j), skirtoje (j / ne i)),

taip pat (vee) idempotencija (iš (C / vee C / vee D) sudaryti (C / vee D)).

Herbrando teoremą taip pat galima gauti naudojant pjūvio eliminaciją per Gentzeno „vidurinę teoremą“. Tačiau įrodymas naudojant antrąją epsilono teoremą skiriasi tuo, kad yra pirmasis išsamus ir teisingas Herbrando teoremos įrodymas. Be to, ir tai retai pripažįstama, o įrodymas, paremtas išpjaustymu, Herbrand'o disjunkcijos ilgį riboja tik kaip įrodyme supjaustytų formų pjaustymo laipsnio ir sudėtingumo funkciją, o ilgis, gaunamas iš įrodymo Remiantis epsilono skaičiavimais, gaunamas ryšys kaip transfinito aksiomos taikymo skaičiaus funkcija ir jame esančių epsilono terminų rangas bei laipsnis. Kitaip tariant, Herbrando disjunkcijos trukmė priklauso tik nuo dalyvaujančių pakaitų kiekybinio sudėtingumo ir, pvz.visai ne dėl pasiūlymo struktūros ar įrodymų ilgio.

Šio skyriaus pradžioje pateikta Herbrando teoremos versija iš esmės yra ypatingas atvejis (2), kai formulė (A) egzistuoja. Atsižvelgiant į šį ypatingą atvejį, (1) yra lygus teiginiui, kad formulė (A) yra išvestinė pirmosios eilės predikatinėje logikoje, jei ir tik tada, kai (A ^ H) yra. Šios lygiavertiškumo pirmyn kryptį yra daug lengviau įrodyti; iš tikrųjų bet kuri formulė (A, A / dešinė rodyklė A ^ H) yra išvedama predikatinėje logikoje. Įrodžius atvirkštinę kryptį, reikia pašalinti papildomų funkcijų simbolius, esančius (A ^ H), ir tai yra daug sunkiau, ypač esant lygybei. Būtent čia epsilono metodai vaidina pagrindinį vaidmenį.

Atsižvelgiant į papildomą formulę, Skolemo normalioji forma (A ^ S) apibrėžiama du kartus į ((A ^ H)), ty pakeičiant egzistenciškai kiekybinius kintamuosius stebint funkcijas. Jei (Gamma) yra priešakinių sakinių rinkinys, tegul (Gamma ^ S) žymi jų Skolem normalių formų aibę. Naudojant dedukcijos teoremą ir Herbrando teoremą, nėra sunku parodyti, kad šios poros yra lygiavertės: (pradėti {lygiuoti} gama ir / tekstas {įrodo} A \\ / gama & / tekstas {įrodo} A ^ H \\ / Gama ^ S & / tekstas {įrodo} A \\ / Gama ^ S & / tekstas {įrodo} A ^ H / pabaiga {lygiuoti})

Ryškus Herbrando teoremos ir susijusių metodų taikymas randamas Luckhardto (1989) Roth'o teoremos analizėje. Apie naudingus Herbrando metodų plėtinius skaitykite Sieg 1991. Modelio teorinė šio varianto versija yra aptariama Avigad 2002a.

5. Epsilono pakaitalo metodas ir aritmetika

Kaip minėta aukščiau, istoriškai pagrindinis susidomėjimas epsilono skaičiavimu buvo priemonė nuoseklumo įrodymams gauti. Hilberto 1917–1918 m. Paskaitose jau pažymima, kad galima lengvai įrodyti teiginio logikos nuoseklumą, imant pasiūlytinius kintamuosius ir formules, kad jie atitiktų 0 ir 1 tiesos reikšmes, ir aiškindami loginius jungtukus kaip atitinkamas aritmetines operacijas. Panašiai galima įrodyti predikatinės logikos (arba grynojo epsilono skaičiavimo) nuoseklumą, pasitelkiant interpretacijas, kai diskurso visata turi vieną elementą. Šie samprotavimai rodo šią bendresnę nuoseklumo įrodymo programą:

  • Išskleiskite „epsilon“skaičiavimą taip, kad būtų parodyta didesnė matematikos dalis.
  • Taikant baigtinius metodus, parodykite, kad kiekvienas išplėstinės sistemos įrodymas turi aiškumą.

Pvz., Apsvarstykite aritmetikos kalbą su simboliais (0), (1), (+), (kartų), (lt). Kartu su pagrindinius simbolius apibrėžiančiomis be kiekybinio apibrėžimo aksiomomis galima nurodyti, kad epsilono terminai (varepsilon x A (x)) pasirenka mažiausią reikšmę, tenkinančią (A), jei yra, su šia aksioma.: (tag {*} A (x) dešinė rodyklė A (varepsilon x A (x)) pleištas / varepsilon x A (x) le x) Rezultatas yra sistema, pakankamai stipri, kad pirmiausia galėtų ją išaiškinti. -užsakymo (Peano) aritmetika. Kaip alternatyva, epsilono simboliu galima patenkinti šią aksiomą: [A (y) dešinė rodyklė A (varepsilon x A (x)) pleištas / varepsilon x A (x) ne y + 1.]

Kitaip tariant, jei yra koks nors liudytojas (y), tenkinantis (A (y)), epsilono terminas grąžina vertę, kurios pirmtakas neturi tos pačios savybės. Akivaizdu, kad (*) apibūdintas epsilono terminas patenkina alternatyvią aksiomą; atvirkščiai, galima patikrinti, ar duotame ((A)) (varepsilon x (egzistuoja z / le x A (x))), tenkinanti alternatyvią aksiomą, reikšmė gali būti naudojama aiškinant (varepsilon x A (x)) (*). Galima dar labiau patikslinti epsilono termino reikšmę aksioma (varepsilon x A (x) ne 0 / dešinė rodyklė A (varepsilon x A (x))), reikalaujanti, kad jei nėra liudytojo (A), epsilono terminas grįžta 0. Tačiau toliau aptariant, patogiausia sutelkti dėmesį tik į (*).

Tarkime, mes norime parodyti, kad aukščiau pateikta sistema yra nuosekli; kitaip tariant, mes norime parodyti, kad nėra formulės (0 = 1) įrodymų. Stumiant visus aksiomų pakeitimus ir keičiant laisvuosius kintamuosius konstanta 0, pakanka parodyti, kad iš pasiūlyto uždarojo aksiomų egzempliorių rinkinio nėra pasiūlymo (0 = 1) įrodymų. Tam pakanka parodyti, kad, atsižvelgiant į bet kokį baigtinį uždarojo tipo aksiomų egzempliorių rinkinį, galima susieti skaitines reikšmes terminais taip, kad aiškinant visos aksiomos būtų teisingos. Kadangi aritmetines operacijas (+) ir (times) galima interpretuoti įprastu būdu, vienintelis sunkumas yra rasti tinkamas vertes, kurias būtų galima priskirti epsilono terminams.

Apytiksliai galima apibūdinti Hilberto epsilono pakeitimo metodą:

  • Atsižvelgiant į baigtinį aksiomų rinkinį, pradėkite aiškinti visus epsilono terminus kaip 0.
  • Aukščiau raskite aksiomos (*) pavyzdį, kuris aiškinant yra klaidingas. Tai gali įvykti tik tuo atveju, jei vienas terminas t yra toks, kad interpretacijoje teisinga yra (A (t)), bet arba (A (varepsilon x A (x))) yra klaidinga, arba (t) yra mažesnė už (varepsilon x A (x)) reikšmę.
  • „Pataisykite“užduotį, priskirdami (varepsilon x A (x)) (t) reikšmę ir pakartokite procesą.

Gaunamas baigtinio konsistencijos įrodymas, kai baigtinai priimtinu būdu parodoma, kad šis paskesnio „remonto“procesas pasibaigia. Jei taip, visos kritinės formulės yra tikrosios formulės be epsilon terminų.

Šią pagrindinę idėją („Hilbertsche Ansatz“) pirmiausia iškėlė Hilbertas savo 1922 m. Pokalbyje (1923 m.) Ir išplėtotas paskaitose 1922–23 m. Tačiau ten pateiktuose pavyzdžiuose nagrinėjami tik įrodymai, kai visi transfinitetinės aksiomos atvejai atitinka vieną epsilono terminą (varepsilon x A (x)). Iššūkis buvo išplėsti požiūrį į daugiau nei vieną epsilono terminą, įterptus epsilono terminus ir galiausiai į antrosios eilės epsilonus (siekiant gauti ne tik aritmetinės, bet ir analizės nuoseklumo įrodymą).

Sunkumų, susijusių su įdėtais epsilono terminais, galima apibūdinti taip. Tarkime, viena iš įrodymų aksiomų yra begalinė aksioma [B (y) dešinė rodyklė B (varepsilon y B (y))) (varepsilon y B (y)), žinoma, gali atsirasti kitos įrodymų formulės, ypač kitose neribotose aksiomose, pvz., [A (x, / varepsilon y B (y)) dešinė rodyklė A (varepsilon x A (x, / varepsilon y B (y)), / varepsilon y B (y))) Taigi pirmiausia reikia rasti teisingą (varepsilon y B (y)) interpretaciją, prieš bandydami surasti (varepsilon x A (x, / varepsilon) y B (y))). Tačiau yra ir sudėtingesnių pavyzdžių, kai epsilono terminai gali atsirasti įrodyme. Aksiomos pavyzdys, atliekantis teisingą (varepsilon y B (y)) interpretaciją, gali būti [B (varepsilon x A (x,\ varepsilon y B (y))) dešinė rodyklė B (varepsilon y B (y))) Jei (B) (0) yra klaidinga, tada pirmame procedūros etape (varepsilon y B (y)) bus aiškinamas 0. Vėliau pakeitus (varepsilon x A (x, 0)) aiškinimą nuo 0 iki, tarkime, (n), bus aiškinamas šis atvejis. kaip (B (n) dešinė rodyklė B) (0), kuri bus klaidinga, jei (B (n)) yra tiesa. Taigi aiškinimas (varepsilon y B (y)) turės būti pataisytas į (n), o tai, savo ruožtu, gali lemti interpretaciją (varepsilon x A (x, / varepsilon y) B (y))) nebėra tikra formulė.rezultatas bus interpretuojamas kaip (B (n) dešinė rodyklė B) (0), kuris bus klaidingas, jei (B (n)) yra tiesa. Taigi aiškinimas (varepsilon y B (y)) turės būti pataisytas į (n), o tai, savo ruožtu, gali lemti interpretaciją (varepsilon x A (x, / varepsilon y) B (y))) nebėra tikra formulė.rezultatas bus interpretuojamas kaip (B (n) dešinė rodyklė B) (0), kuris bus klaidingas, jei (B (n)) yra tiesa. Taigi aiškinimas (varepsilon y B (y)) turės būti pataisytas į (n), o tai, savo ruožtu, gali lemti interpretaciją (varepsilon x A (x, / varepsilon y) B (y))) nebėra tikra formulė.

Tai yra tik sunkumų, susijusių su Hilbert'o idėjos išplėtimu, eskizas. Ackermannas (1924) pateikė tokį apibendrinimą, naudodamas procedūrą, kuri „atsitraukia“, kai nauja interpretacija tam tikrame etape lemia poreikį pataisyti ankstesniame etape rastą interpretaciją.

Ackermanno procedūra buvo taikoma antros eilės aritmetikos sistemai, kurioje antros eilės terminai buvo apriboti taip, kad būtų išvengta kryžminio antrosios eilės epsilonų jungimosi. Apytiksliai tai reiškia aritmetinio supratimo, kaip turimo rinkinio formavimo principo, apribojimą (žr. Diskusiją šio skyriaus pabaigoje). Kiti sunkumai, susiję su antrosios eilės epsilono terminais, iškilo, ir greitai paaiškėjo, kad toks įrodymas buvo klaidingas. Tačiau niekas Hilberto mokykloje nesuvokė sunkumų masto iki 1930 m., Kai Gedelis paskelbė apie savo neišsamumo rezultatus. Iki tol buvo manoma, kad įrodymas (bent jau su kai kuriais „Ackermann“padarytais pakeitimais,kai kurios iš jų buvo susijusios su idėjomis iš von Neumanno (1927 m. epsilon pakeitimo metodo) versijos), bent jau pirmosios eilės. Hilbert ir Bernays (1939) teigia, kad naudojami metodai suteikia tik pirmosios eilės aritmetikos nuoseklumo įrodymą su atvirąja indukcija. 1936 m. Gerhardui Gentzenui pavyko įrodyti pirmosios eilės aritmetikos nuoseklumą formuluojant remiantis predikatine logika be epsilono simbolio. Šis įrodymas naudoja neribotą indukciją iki (varepsilon_0). Ackermannas (1940 m.) Vėliau sugebėjo pritaikyti Gentzeno idėjas ir pateikti teisingą pirmosios eilės aritmetikos nuoseklumo įrodymą, naudojant epsilono pakeitimo metodą. Gerhardui Gentzenui pavyko įrodyti pirmosios eilės aritmetikos nuoseklumą formuluotėje, paremtoje predikatine logika, be epsilono simbolio. Šis įrodymas naudoja neribotą indukciją iki (varepsilon_0). Ackermannas (1940 m.) Vėliau sugebėjo pritaikyti Gentzeno idėjas ir pateikti teisingą pirmosios eilės aritmetikos nuoseklumo įrodymą, naudojant epsilono pakeitimo metodą. Gerhardui Gentzenui pavyko įrodyti pirmosios eilės aritmetikos nuoseklumą formuluotėje, paremtoje predikatine logika, be epsilono simbolio. Šis įrodymas naudoja neribotą indukciją iki (varepsilon_0). Ackermannas (1940 m.) Vėliau sugebėjo pritaikyti Gentzeno idėjas ir pateikti teisingą pirmosios eilės aritmetikos nuoseklumo įrodymą, naudojant epsilono pakeitimo metodą.

Nors Ackermanno bandymai įrodyti antrosios eilės aritmetikos nuoseklumą buvo nesėkmingi, jie leido aiškiau suprasti antrosios eilės epsilono terminų naudojimą įforminant matematiką. Ackermannas vartojo antros eilės epsilono terminus (varepsilon f / A (f)), kur (f) yra funkcijos kintamasis. Analogiškai pirmosios eilės atveju, (varepsilon f / A (f)) yra funkcija, kuriai (A (f)) yra tiesa, pvz., (Varepsilon f (x + f (x)) = 2x)) yra tapatybės funkcija (f (x) = x). Panašiai kaip pirmosios eilės atvejis, antrosios eilės kiekybinius rodiklius interpretuoti galima naudoti antrosios eilės epsilonus. Visų pirma, bet kuriai antros eilės formulei (A (x)) galima rasti tokį terminą (t (x)), kad [A (x) kairioji dešinė rodyklė t (x) = 1) yra išvestinė. skaičiavime (formulė (A) gali turėti kitų laisvų kintamųjų,tokiu atveju jie taip pat pateikiami termina (t). Tada šį faktą galima panaudoti aiškinimo principams aiškinti. Kalba su funkcijų simboliais pasireiškia tokia forma: [egzistuoja f / forall x (A (x) leftrightarrow f (x) = 1))) savavališkos formulės (A (x)) atžvilgiu. Supratimas dažniausiai išreiškiamas išreikštais kintamaisiais; tokiu atveju jis pasireiškia tokia forma: [egzistuoja Y / forall x (A (x) leftrightarrow x / Y),) tvirtinant, kad kas antra eilės formulė su parametrais, nusako rinkinį.tokiu atveju ji yra tokia forma: [egzistuoja Y / forall x (A (x) leftrightarrow x / Y),) tvirtinant, kad kiekviena antra eilės formulė su parametrais apibrėžia aibę.tokiu atveju ji yra tokia forma: [egzistuoja Y / forall x (A (x) leftrightarrow x / Y),) tvirtinant, kad kiekviena antra eilės formulė su parametrais apibrėžia aibę.

Analizė, arba antros eilės aritmetika, yra pirmosios eilės aritmetikos pratęsimas savavališkos antrosios eilės formulių supratimo schema. Teorija yra netiksli tuo, kad ji leidžia apibrėžti natūraliųjų skaičių aibes, naudojant kiekybinius rodiklius, kurie svyruoja per visą aibių visatą, įskaitant netiesiogiai apibrėžiamą aibę. Apgaulingus šios teorijos fragmentus galima gauti ribojant supratimo aksiomoje leidžiamų formulių tipus. Pavyzdžiui, aukščiau aptartas apribojimas, susijęs su „Ackermann“, atitinka aritmetinę supratimo schemą, kurioje formulės neapima antros eilės kiekybinių rodiklių. Yra įvairių būdų gauti stipresnius analizės fragmentus, kurie vis dėlto yra pateisinami. Pavyzdžiui, gaunama rafinuota analizė, susiejant eilinį rangą su kintamaisiais;Apytiksliai, apibrėžiant duoto rango aibę, kiekybiniai rodikliai svyruoja tik per žemesnio rango aibes, ty tuos, kurių apibrėžimai logiškai yra ankstesni.

Papildoma literatūra. Ankstyvieji Hilberto ir Ackermanno įrodymai aptariami Zach 2003; 2004. Von Neumanno įrodymas yra „Bellotti 2016“tema. 1940 m. Ackermanno įrodymas aptariamas Hilbert & Bernays 1970 ir Wang 1963. Šiuolaikinį pranešimą pateikia Moser 2006. Ankstyvasis epsilono pakaitalas yra nekontroliuojamas pavyzdys (Kreisel). 1951 m.).

6. Naujausi pokyčiai

Šiame skyriuje aptariame epsilono pakeitimo metodo, skirto gauti stiprių sistemų nuoseklumo rezultatus, kūrimą; šie rezultatai yra matematinio pobūdžio. Deja, čia negalime aptarti išsamios įrodymų detalės, tačiau norėtume nurodyti, kad epsilono pakeitimo metodas mirė su Hilberto programa ir kad nemažai dabartinių tyrimų atliekama epsilono formalizmuose.

Gentzeno aritmetinės konsistencijos įrodymas pradėjo tyrimų sritį, žinomą kaip ordinalinė analizė, o matematinių teorijų stiprumo matavimo programa, naudojant ordinarinius žymėjimus, tebevykdoma ir šiandien. Tai ypač aktualu išplėstinėje Hilberto programoje, kurios tikslas yra pagrįsti klasikinę matematiką konstruktyvių ar pusiau konstruktyvių sistemų atžvilgiu. „Gentzen“metodai, skirti išnaikinti vaistą (ir Pauliaus Lorentzeno, Petro Novikovo ir Kurto Schütte'io sukurti neinitarinės logikos pratęsimai), iš esmės, atmetė epsilono pakeitimo metodus šiuose užsiėmimuose. Tačiau epsilon skaičiavimo metodai suteikia alternatyvų požiūrį, ir vis dar aktyviai tiriami būdai, kaip išplėsti Hilbert-Ackermann metodus į stipresnes teorijas. Bendras modelis išlieka tas pats:

  1. Įdėkite tiriamą teoriją į atitinkamą epsilon skaičiavimą.
  2. Apibūdinkite epsilon terminų priskyrimų atnaujinimo procesą.
  3. Parodykite, kad procedūra normalizuojasi, ty atsižvelgiant į bet kurį terminų rinkinį yra atnaujinimų seka, kurios rezultatas yra užduotis, tenkinanti aksiomas.

Kadangi paskutinis žingsnis garantuoja originalios teorijos nuoseklumą, pagrindiniu požiūriu domimasi metodais, naudojamais normalizavimui įrodyti. Pvz., Gaunamas eilinis tyrimas, priskiriant eilinius žymėjimus procedūros žingsniams taip, kad žymėjimo reikšmė mažėtų kiekvienu žingsniu.

Septintajame dešimtmetyje Taitas (1960, 1965, 2010) išplėtė Ackermanno metodus, norėdamas gauti įprastinę aritmetikos pratęsimų analizę pagal transfinito indukcijos principus. Tobulesnes ir modernesnes šio požiūrio versijas galima rasti „Mints 2001“ir „Avigad 2002b“. Pastaruoju metu Mintsas, Tupailo ir Buchholzas laikė stipresnius, tačiau vis dar prediktyviai pagrįstus analizės fragmentus, įskaitant aritmetinio supratimo teorijas ir (Delta ^ {1} _1) - supratimo taisyklę (Mints, Tupailo ir Buchholz 1996).; Mints & Tupailo 1999; dar žr. Mints 2016). „Arai 2002“išplėtė epsilono pakeitimo metodą teorijoms, leidžiančioms pakartoti aritmetinį supratimą pagal primityvius rekursinius šulinių išdėstymus. Visų pirma,jo darbas pateikia įprastas analizės prediktyvias analizės fragmentų, apimančių peržengiančias hierarchijas ir perribotas indukcijas, analizę.

Kai kurie pirmi žingsniai buvo žengti naudojant epsilono pakaitalo metodą imperatyvių teorijų analizėje (žr. Arai 2003, 2006 ir Mints 2015).

Aukščiau aprašytas 3 žingsnio variantas reiškia, kad normalizavimo procedūra nėra jautri atnaujinimų pasirinkimui, tai yra, bet kuri atnaujinimų seka pasibaigia. Tai vadinama stipriu normalizavimu. 1996 m. „Mints“parodė, kad daugelis nagrinėjamų procedūrų turi šią stipresnę savybę.

Be tradicinės, pagrindinės įrodinėjimo teorijos šakos, šiandien daug kas domimasi struktūros įrodymo teorija - dalyko šaka, kurioje pagrindinis dėmesys skiriamas loginiams dedukciniams skaičiavimams ir jų savybėms. Šis tyrimas yra glaudžiai susijęs su kompiuterių mokslui aktualiomis problemomis, susijusiomis su automatizuotu atskaitymu, funkciniu programavimu ir kompiuteriu. Čia taip pat vyrauja Gentzen stiliaus metodai (dar kartą skaitykite įrašą apie įrodymų teoriją). Tačiau „epsilon“skaičiavimas taip pat gali suteikti vertingų įžvalgų; plg. pavyzdžiui, „Aguilera & Baaz 2019“arba aukščiau aptarta Herbrando teorema.

Be epsilon skaičiavimo įrodymų teorijoje, reikėtų paminėti dvi taikymo sritis. Viena iš jų yra epsilono žymėjimo naudojimas Bourbaki „Theorie des“ansambliuose (1958). Antrasis, galimas dabartinis susidomėjimas, yra epsilono operatoriaus naudojimas teorijų įrodymo sistemose HOL ir Isabelle, kur išraiškinga epsilono terminų galia suteikia reikšmingų praktinių pranašumų.

7. „Epsilon“kalbotyros, filosofijos ir neklasikinės logikos operatoriai

„Epsilon“operatoriaus skaitymas kaip neriboto pasirinkimo operatorius („an (x) toks, kad (A (x))“) rodo, kad jis gali būti naudingas įrankis analizuojant neapibrėžtas ir apibrėžtas daiktavardžių frazes formalioje semantikoje. „Epsilon“žymėjimas iš tikrųjų buvo toks naudojamas, ir ši programa pasirodė esanti naudinga visų pirma nagrinėjant anaforinę atskaitą.

Apsvarstykite pažįstamą pavyzdį

Kiekvienas ūkininkas, kuriam priklauso asilas, jį muša

Visuotinai priimtą šio sakinio analizę pateikia universalus sakinys

(forall x / forall y (mathrm {Ūkininkas} (x) pleištas / mathrm {asilas} (y) pleištas / mathrm {Owns} (x, y)) rightarrow / mathrm {Beats} (x, y)))

Trūkumas yra tas, kad „asilas“siūlo egzistencinį kiekybinį rodiklį, todėl analizė kažkokiu būdu turėtų būti lygiagreti 3 sakinio, kurį suteikia 4, analizei:

  1. Kiekvienas ūkininkas, kuriam priklauso asilas, yra laimingas,
  2. (forall x (mathrm {Farmer} (x) pleištas / egzistuoja y (mathrm {Donkey} (y) pleišas / mathrm {Owns} (x, y)) rightarrow / mathrm {Happy} (x))),

bet kuo arčiau įforminimo,

(forall x ((mathrm {Farmer} (x) pleištas / egzistuoja y (mathrm {Donkey} (y) pleišas / mathrm {Owns} (x, y)) rightarrow / mathrm {Beats} (x, y)))

yra laisvas (y) atvejis. Evansas 1980 siūlo, kad įvardžiai nurodo posakius, jie turėtų būti analizuojami kaip aiškūs apibūdinimai; o jei įvardis įvyksta sąlyginiojo pasekmėje, aprašomąsias sąlygas nustato priešakinis. Tai lemia tokią (1) E tipo analizę: (pradėti {daugialypė linija *} forall x ((mathrm {Farmer} (x) pleištas / egzistuoja y (mathrm {Donkey} (y)) pleištas / mathrm {Nuosavybės} (x, y)) dešinėn rodyklė \(mathrm {Beats} (x, / iota y (mathrm {asilas} (y) pleištas / mathrm {omonai (x, y))) pabaiga {daugialypė linija *}) Čia (iota x) yra apibrėžtas aprašymo operatorius, taigi (iota y (mathrm {Donkey} (y) pleišas / mathrm {Owns} (x, y)))) yra „asilas, priklausantis (x);“. Problema ta, kad atliekant standartinę analizę, aiškus aprašymas turi unikalumo sąlygą,taigi (5) bus klaidinga, jei yra ūkininkas, kuriam priklauso daugiau nei vienas asilas. Išeitis yra pristatyti naują operatorių, kuris (bet kas, kas bebūtų), kuris veikia kaip apibendrinamasis kiekybinis rodiklis (Neale, 1990): (pradėti {multline *} forall x ((mathrm {Farmer}) (x) pleištas / egzistuoja y (mathrm {Donkey} (y) pleišas / mathrm {Owns} (x, y)) rightarrow \(mathrm {Beats}) (x, / mathrm {whe}, y (mathrm {asilas} (y) pleištas / mathrm {nuosavybės} (x, y))) pabaiga {daugialypė linija *})

Kaip pažymėjo von Heusingeris (1994), tai rodo, kad Neale įsipareigoja įvardžiams būti dviprasmiškais tarp apibrėžtųjų apibūdinimų ((iota) - posakių) ir whe-išraiškų. Heusingeris siūlo naudoti „epsilon“operatorius, indeksuotus pagal pasirinkimo funkcijas (kurios priklauso nuo konteksto). Remiantis šiuo požiūriu, analizuojama (1):

Kiekvienai pasirinktai funkcijai (i): (pradėti {daugialypė linija *} forall x ((mathrm {Farmer} (x) pleišas / mathrm {Owns} (x, / varepsilon_i y / mathrm {Donkey}) y)) dešinėn rodyklė \\\ mathrm {Beats} (x, / varepsilon_ {a ^ *} y / mathrm {Donkey} (y)) end {multline *})

Čia (a ^ *) yra pasirinkimo funkcija, priklausanti nuo (i) ir sąlyginio ankstesnio: Jei (i) yra pasirinkimo funkcija, kuri pasirenka (varepsilon_i y / mathrm {Donkey} (y)) iš visų asilų rinkinio, tada (varepsilon_ {a ^ *} y / mathrm {Donkey} (y)) pasirenka iš asilų, priklausančių (x), rinkinio.

Šis požiūris į įvardžius, naudojant „epsilon“operacijas, indeksuojamas pasirinkimo funkcijomis, suteikia von Heusingeriui galimybę spręsti įvairiausias aplinkybes (žr. Egli ir von Heusinger, 1995; von Heusinger, 2000).

Pastaraisiais metais epsilono operatoriaus taikymas formaliojoje semantikoje ir pasirinkimo funkcijos apskritai sulaukė didelio susidomėjimo. Von Heusingeris ir Egli (2000a), be kita ko, išvardija: klausimų atvaizdus (Reinhart, 1992), konkrečius neribotus terminus (Reinhart 1992; 1997; 1997 m. Žiema), E tipo įvardžius (Hintikka ir Kulas, 1985; Slater, 1986; Chierchia). 1992, Egli ir von Heusinger 1995) ir apibrėžtos daiktavardžių frazės (von Heusinger 1997, 2004).

Apie „epsilon“operatoriaus problemas ir taikymo kalbotyroje ir kalbos filosofijoje klausimus skaitykite BH Slater straipsnyje apie epsilon skaičiavimus (cituojamas žemiau esančiame skyrelyje „Kiti interneto šaltiniai“) ir von Heusinger bei Egli 2000 bei von Heusinger ir Kempson rinkiniuose 2004 m..

Kitas „epsilon“skaičiavimo būdas yra bendro pobūdžio samprotavimų apie savavališkus objektus logika. Meyer Viol (1995a) pateikia epsilon skaičiavimo palyginimą su Fine (1985) savavališkų objektų teorija. Iš tiesų ryšį nėra sunku įžvelgti. Atsižvelgiant į lygiavertiškumą (forall x A (x) equiv) A ((varepsilon x (neg A))), terminas (varepsilon x (neg A)) yra savavališkas objektas ta prasme, kad tai objektas, kurio (A) yra tiesa, jei (A) yra tiesa iš tikrųjų.

Meyer Viol (1995a, 1995b) pateikia tolesnius įrodymų ir modelio teorinius epsilon skaičiavimo tyrimus; konkrečiai intuicionistiniai epsilono skaičiavimai. Čia epsilono teoremos nebeturi galios, ty įvedus epsilono terminus gaunami ne konservatyvūs intuicionistinės logikos pratęsimai. Kitus intuicinės logikos epsilono operatorių tyrimus galima rasti Shirai (1971), Bell (1993a, 1993b) ir DeVidi (1995). Apie daugelio vertinamų logikos „epsilon“operatorius skaitykite „Mostowski“(1963), apie modalinį „epsilon“skaičiavimą - „Fiting“(1975).

Papildoma literatūra. Toliau pateikiamas kai kurių kalbų ir kalbotyros leidinių, susijusių su epsilon skaičiavimu ir jo taikymu, sąrašas. Skaitytojas visų pirma nukreiptas į von Heusinger & Egli (red.) 2000 ir von Heusinger & Kempson (red.) 2004 kolekcijas, kad būtų galima toliau diskutuoti ir pateikti nuorodas: Bell 1993a, 1993b; Chierchia 1992; DeVidi 1995; Egli & von Heusinger 1995; Bauda 1985; Tinka 1975 m.; von Heusingeris 1994, 1997, 2000, 2004; von Heusingeris ir Egli (red.) 2000; von Heusingeris ir Kempsonas (red.) 2004; Hintikka & Kulas 1985; Kempsonas, „Meyer Viol“ir „Gabbay 2001“; „Meyer“smuikas 1995a, 1995b, Neale 1990; Mostowski 1963; Reinhartas 1992, 1997; Slater 1986, 1988, 1994, 2000; ir 1997 m. žiema.

Bibliografija

  • Aguilera, JP, Baaz, M., 2019, „Dėl nepagrįstų išvadų įrodymai sutrumpėja“. Žurnalas „Symbolic Logic“84: 102–122.
  • Ackermannas, W., 1924 m., „Begründung des“- „mittels der Hilbertschen Theorie der Widerspruchsfreiheit“, Mathematische Annalen, 93: 1–36.
  • ––– 1937–38 m., „Mengentheoretische Begründung der Logik“, „Mathematische Annalen“, 115: 1–22.
  • ––– 1940 m., „Zur Widerspruchsfreiheit der Zahlentheorie“, „Mathematische Annalen“, 117: 162–194.
  • Arai, T., 2002, „Epsilono pakaitalų metodas šuolių hierarchijų teorijoms“, Matematinės logikos archyvas, 2: 123–153.
  • ––– 2003 m., „Epsilono pakaitalas ID (_ 1 (Pi ^ {0} _1 / vee / Sigma ^ {0} _1))“, Annals of Pure and Applied Logic, 121: 163–208.
  • ––– 2006 m., „Epsilon pakeitimo metodas, naudojant (Pi ^ {0} _2) - FIX. Žurnalas „Symbolic Logic“71: 1155–1188
  • Avigad, J., 2002a, „Sotieji universaliųjų teorijų modeliai“, Annals of Pure and Applied Logic, 118: 219–234.
  • –––, 2002b, „Atnaujinimo procedūros ir 1 aritmetikos nuoseklumas“, Matematinė logika, ketvirtis, 48: 3–13.
  • Baaz, M., Leitsch, A., Lolic, A., 2018, 'Eilėraščio pagrindu apskaičiuota išplėstinės pirmosios epsilono teoremos formulė', in: Artemov, S., Nerode, A. (red.), Logical Foundations kompiuterių mokslas, Berlynas: Springeris, 55–71 metai.
  • Bell, JL, 1993a. „Hilberto epsilono operatorius ir klasikinė logika“, žurnalas „Philosophical Logic“, 22: 1–18.
  • –––, 1993b. „Hilberto epsilono operatorius intuicionizmo tipo teorijose“, Matematinės logikos ketvirtinis leidinys, 39: 323–337.
  • Bellotti, L., 2016 m., „Von Neumanno nuoseklumas“, „Symbolic Logic“apžvalga, 9: 429–455.
  • Bourbaki, N., 1958 m., Theorie des ansambbles, Paryžius: Hermann.
  • Buss, S., 1995, „Dėl Herbrando teoremos“, logika ir skaičiavimo sudėtingumas (Paskaitų užrašai kompiuterių moksle 960), Berlynas: Springeris, 195–209.
  • ––– 1998 m., „Įvadas į įrodinėjimo teoriją“, in: Buss (ed.), Proof Theory Handbook, Amsterdamas: Šiaurės Olandija, 1–78.
  • Chierchia, G., 1992. „Anaphora ir dinaminė logika“. Kalbotyra ir filosofija, 15: 111–183.
  • Davis, M. ir R. Fechter, 1991 m., „Pirmos eilės predikatinių skaičiavimų nemokama kintama versija“, žurnalas „Logic and Computation“, 1: 431–451.
  • DeVidi, D., 1995. „Intuicionistiniai (varepsilon) - ir (tau) - skaičiavimai“, Matematinės logikos ketvirčio 41: 523–546.
  • Egli, U., von Heusinger, K., 1995, „Epsilon operatorius ir E tipo įvardžiai“, U. Egli et al. (red.), Leksinės žinios kalbų organizavime, Amsterdamas: Benjamins, 121–141 (Kalbų teorijos aktualijos 114).
  • Evans, G., 1980, „Pronouns“, Linguistic Enquiry, 11: 337–362.
  • Ewald, WB (red.), 1996 m., Nuo Kanto iki Hilberto. Šaltinių knyga „Matematikos pagrindai“, t. 2, Oksfordas: Oxford University Press.
  • „Ferrari“, PL, 1987 m., „Pastaba apie Hilberto antrosios (varepsilon) teoremos įrodymą“, Journal of Symbolic Logic, 52: 214–215.
  • Fine, K., 1985. Priežastis savavališkais objektais, Oksfordas: Blackwell.
  • Fiting, M., 1975 m. „Modalinė loginė epsilon-calculus“, „Notre Dame Journal of Formal Logic“, 16: 1–16.
  • Flannaganas, TB, 1975 m., „Dėl antrosios Hilberto (varepsilon) teoremos pratęsimo“, Journal of Symbolic Logic, 40: 393–397.
  • Girard, J.-Y., 1982, „Herbrando teorema ir įrodymo teorija“, Herbrando simpoziumo leidiniai, Amsterdamas: Šiaurės Olandija, 29–38.
  • Herbrand, J., 1930, Paryžiaus universiteto disertacija „Recherches sur la thèorie de la dèmonstration“. Vertimas į anglų kalbą Herbrand 1971, 44–202 psl.
  • –––, 1971 m., „Logical Writings“, W. Goldfarbas (red.), Kembridžas, Mišios: Harvard University Press.
  • Hilbert, D., 1922 m., „Neubegründung der Mathematik: Erste Mitteilung“, Abhandlungen aus dem Seminar der Hamburgischen Universität, 1: 157–177, vertimas į anglų kalbą Mancosu, 1998, 198–214 ir Ewald, 1996, 1115–1134.
  • ––– 1923 m., „Die logischen Grundlagen der Mathematik“, „Mathematische Annalen“, 88: 151–165, vertimas į anglų kalbą Ewald, 1996, 1134–1148.
  • Hilbert, D., Bernays, P., 1934, Grundlagen der Mathematik, Vol. 1, Berlynas: „Springer“.
  • –––, 1939 m., Grundlagen der Mathematik, t. 2, Berlynas: „Springer“.
  • ––– 1970 m., „Grundlagen der Mathematik“, t. 2, 2, leidimas, Berlynas: „Springer“, V priedas.
  • Hintikka, J., Kulas, J., 1985. Anaphora ir apibrėžti aprašymai: du žaidimų teorinės semantikos pritaikymai, Dordrecht: Reidel.
  • Kempson, R., Meyer Viol, W., ir Gabbay, D., 2001. Dinaminė sintaksė: kalbos supratimo srautas, Oksfordas: Blackwellas.
  • Kreisel, G, 1951 m., „Dėl ne finitistinių įrodymų aiškinimo - I dalis“, „Symbolic Logic“žurnalas, 16: 241–267.
  • Leisenring, AC, 1969 m., „Matematinė logika“ir Hilberto Epsilono simbolis, Londonas: Macdonaldas.
  • Luckhardt, H., 1989, „Herbrand-Analysen zweier Beweise des Satzes von Roth: Polynomiale Anzahlschranken“, žurnalas „Symbolic Logic“, 54: 234–263.
  • Maehara, S., 1955 m., „Predikatinis skaičiavimas su (varepsilon) - simboliu“, Japonijos matematikos draugijos žurnalas, 7: 323–344.
  • ––– 1957 m., „Lygybės aksioma ant Hilberto (varepsilon) - simbolio“, Tokijo universiteto Mokslo fakulteto žurnalas, 1 skyrius, 7: 419–435.
  • Mancosu, P. (red.), 1998 m., Nuo Brouwer iki Hilbert. Diskusija apie matematikos pagrindus 1920 m., Oksfordas: Oxford University Press.
  • Meyer Viol, WPM, 1995a, „Instantial Logic“. Institucijų samprotavimo tyrimas, Ph. D. disertacija, Utrechto universitetas. ILLC disertacijų serija 1995–11.
  • –––, 1995b. „Įrodytas teorinis užduočių traktavimas“, IGPL biuletenis, 3: 223–243.
  • Mints, G., 1994, 'Gentzen tipo sistemos ir Hilberto epsilono pakeitimo metodas. Aš ', logika, metodologija ir mokslo filosofija, IX (Uppsala, 1991), Amsterdamas: Šiaurės Olandija, 91–122.
  • ––– 1996 m., „Stiprus epsilono pakeitimo metodo nutraukimas“, Journal of Symbolic Logic, 61: 1193–1205.
  • –––, 2001 m., „Epsilono pakeitimo metodas ir tęstinumas“, W. Sieg et al. (red.), Apmąstymai apie matematikos pagrindus: esė Saliamono Fefermano garbei, Paskaitų užrašai logikoje 15, Simbolinės logikos asociacija.
  • ––– 2008 m., „Iškirpta pašalinimas paprastam epsilono skaičiavimui“, Grynos ir taikomosios logikos metraščiai, 152 (1–3): 148–160.
  • –––, 2013. „Epsilono pakaitalas pirmos ir antros eilės predikatų logikai“, Annals of Pure and Applied Logic, 164: 733–739.
  • –––, 2015 m. „Neadeteinistinis PA ir ID (_ 1) epsilono pakeitimo metodas“, in: Kahle, R., Rathjen, M. (Eds.), Gentzen Centenary: The Consisten of Quest of Consistence. Berlynas: „Springer“, 479–500 psl.
  • Mints, G., Tupailo, S., 1999, A. Cantini ir kt., „Epsilono pakaitalo metodas supykusiai kalbai ir (Delta ^ {1} _1 / - supratimo taisyklė““. (red.), Matematikos logika ir pagrindai (Florencija, 1995), Dordrecht: Kluwer, 107–130.
  • Mints, G., Tupailo, S., Buchholz, W., 1996, „Epsilon pakaitinis metodas pradinei analizei“, Matematinės logikos archyvas, 35: 103–130.
  • Moser, G., 2006, „Ackermanno pakeitimo metodas (permaišytas)“, Annals of Pure and Applied Logic, 142 (1–3): 1–18.
  • Moser, G. ir R. Zach, 2006, „Epsilon calculus ir Herbrand sudėtingumas“, „Studia Logica“, 82 (1): 133–155.
  • Mostowski, A., 1963. „Hilberto epsilono funkcija daugelio vertinamoje logikoje“, Acta Philosophica Fennica, 16: 169–188.
  • Neale, S., 1990, Aprašymai, Cambridge, MA: MIT Press.
  • Reinhart, T., 1992 m. „Wh-in-situ: akivaizdus paradoksas“. In: P. Dekkeris ir M. Stokhof (red.). Aštuntojo Amsterdamo kolokviumo, 1991 m. Gruodžio 17–20 d., Leidiniai. ILLC. Amsterdamo universitetas, 483–491.
  • –––, 1997. „Kiekybinis rodiklis: kaip darbas pasiskirsto tarp QR ir pasirinkimo funkcijų“. Kalbotyra ir filosofija, 20: 335–397.
  • Shirai, K., 1971 m., „Intuicionistinis predikatinis skaičiavimas su (varepsilon) - simboliu“, Japonijos mokslo filosofijos asociacijos metraštis 4: 49–67.
  • Sieg, W., 1991, „Herbrand analizės“, Matematinės logikos archyvas, 30: 409–441.
  • Slater, BH, 1986, „E tipo įvardžiai ir (varepsilon) - terminai“, Canadian Philosophy Journal, 16: 27–38.
  • ––– 1988 m., „Hilbertian nuoroda“, Noûs, 22: 283–97.
  • ––– 1994 m., „Epsilon calculus“problematiškas “, Philosophical Papers, 23: 217–42.
  • ––– 2000 m., „Kiekybinis / kintamasis įrišimas“, Lingvistika ir filosofija, 23: 309–21.
  • Tait, WW, 1960 m., „Pakeitimo metodas“. Žurnalas „Symbolic Logic“, 30: 175–192.
  • ––– 1965 m., „Funkcijos, apibrėžtos begaline rekursija“, „Journal of Symbolic Logic“, 30: 155–174.
  • –––, 2010 m. „Pakeistas pakaitalo metodas“. in: S. Feferman ir W. Sieg (red. past.), Įrodymai, kategorijos ir skaičiavimai: Esė Garbės Grigori Mints garbei, Londonas: „College Publications“, p. 131–14.
  • von Heusinger, K., 1994, Neale apžvalga (1990). Kalbotyra 32: 378–385.
  • –––, 1997. „Neapibrėžti aprašymai ir pasirinkimo funkcijos“. In: S. Akama (red.). Logika, kalba ir skaičiavimas, Dordrecht: Kluwer, 61–91.
  • ––– 2000 m., „Neribotų asmenų nuoroda“, von Heusinger ir Egli, (2000), 265–284.
  • ––– 2004 m., „Pasirinkimo funkcijos ir apibrėžtųjų NP neforminė semantika“, Kalbos ir skaičiavimo tyrimai, 2: 309–329.
  • von Heusinger, K., Egli, U., (red.), 2000. Reference and Anaphoric Relations, Dordrecht: Kluwer.
  • –––, 2000a. „Įvadas: Anaphoros nuoroda ir semantika“, von Heusinger ir Egli (2000), 1–13.
  • von Heusinger, K., Kempson, R., (ed.), 2004. Pasirinktos semantikos funkcijos, specialioji kalbos ir skaičiavimo tyrimų problema 2 (3).
  • von Neumann, J., 1927 m., „Zur Hilbertschen Beweistheorie“, Mathematische Zeitschrift, 26: 1–46.
  • Wang, H., 1963, Matematinės logikos apžvalga, Pekinas: Science Press.
  • Y., 1997 m. Žiema. „Pasirinkimo funkcijos ir neapibrėžtumų skopalinė semantika“. Kalbotyra ir filosofija, 20: 399–467.
  • Yasuhara, M., 1982, „Iškirpimo pašalinimas iš (varepsilon) - skaičiavimų“, Zeitschrift fürhematische Logik und Grundlagen der Mathematik, 28: 311–316.
  • Zach, R., 2003, „Finitizmo praktika. Epsilono skaičiavimai ir nuoseklumo įrodymai Hilberto programoje “, Synthese, 137: 211–259.
  • –––, 2004 m. “Hilberto„ Verunglückter Beweis “, pirmoji epsilono teorema ir nuoseklumo įrodymas“. Logikos istorija ir filosofija, 25, 79–94.
  • –––, 2017. „Epsilono skaičiavimo semantika ir įrodymo teorija“, publikacijose: Ghosh, S., Prasad, S. (Eds.), Logic and Its Applications. ICLA 2017, LNCS. „Springer“, Berlynas, Heidelbergas, p. 27–47.

Akademinės priemonės

sep vyro ikona
sep vyro ikona
Kaip pacituoti šį įrašą.
sep vyro ikona
sep vyro ikona
Peržiūrėkite šio įrašo PDF versiją „Friends of the SEP“draugijoje.
info piktograma
info piktograma
Ieškokite šios įrašo temos interneto filosofijos ontologijos projekte (InPhO).
„Phil Papers“piktograma
„Phil Papers“piktograma
Patobulinta šio įrašo „PhilPapers“bibliografija su nuorodomis į jo duomenų bazę.

Kiti interneto šaltiniai

„Epsilon Calculi“, autorius B. Hartley Slater (Filosofijos interneto enciklopedija)

Kreipkitės į autorius ir pateikite daugiau pasiūlymų.