Epsilon-beregningen

Innholdsfortegnelse:

Epsilon-beregningen
Epsilon-beregningen

Video: Epsilon-beregningen

Video: Epsilon-beregningen
Video: Lek 1 | Matematik - Komplekse Tal (Part 1/2) 2024, Mars
Anonim

Inngangsnavigasjon

  • Inngangsinnhold
  • Bibliografi
  • Akademiske verktøy
  • Venner PDF forhåndsvisning
  • Forfatter og sitatinfo
  • Tilbake til toppen

Epsilon-beregningen

Først publisert fre 3. mai 2002; substansiell revisjon man 6. mai 2019

Epsilon-kalkylen er en logisk formalisme utviklet av David Hilbert i tjeneste for sitt program i grunnlaget for matematikk. Epsilon-operatøren er en termdannende operatør som erstatter kvantifikatorer i vanlig predikatlogikk. Spesifikt, i kalkulaturen, betegner et begrep (varepsilon x A) noen (x) tilfredsstillende (A (x)), hvis det er en. I Hilberts program spiller epsilonbegrepene rollen som ideelle elementer; Målet med Hilberts finitistiske konsistensbevis er å gi en prosedyre som fjerner slike vilkår fra et formelt bevis. Prosedyrene som dette skal utføres er basert på Hilberts epsilonsubstitusjonsmetode. Epsilon-beregningen har imidlertid applikasjoner også i andre sammenhenger. Den første generelle bruken av epsilon-beregningen var i Hilberts epsilon-setninger,som igjen gir grunnlaget for det første riktige beviset på Herbrands teorem. Nyere har varianter av epsilon-operatøren blitt brukt i språkvitenskap og språklig filosofi for å håndtere anaforiske pronomen.

  • 1. Oversikt
  • 2. Epsilon-beregningen
  • 3. Epsilon-setningene
  • 4. Herbrands teorem
  • 5. Epsilon substitusjonsmetode og aritmetikk
  • 6. Nyere utvikling
  • 7. Epsilon operatører i lingvistikk, filosofi og ikke-klassisk logikk
  • Bibliografi
  • Akademiske verktøy
  • Andre internettressurser
  • Relaterte oppføringer

1. Oversikt

Ved århundreskiftet ble David Hilbert og Henri Poincaré anerkjent som de to viktigste matematikerne i deres generasjon. Hilberts utvalg av matematiske interesser var bred, og inkluderte en interesse for grunnlaget for matematikk: hans Foundations of Geometry ble publisert i 1899, og av listen over spørsmål som ble stilt til Den internasjonale matematikerkongressen i 1900, tok tre uttrykkelige grunnleggende spørsmål opp.

Etter publiseringen av Russells paradoks, presenterte Hilbert en adresse til den tredje internasjonale matematikerkongressen i 1904, der han for første gang tegnet planen sin for å gi et strengt grunnlag for matematikk via syntaktiske konsistensbeviser. Men han kom ikke tilbake til emnet for alvor før i 1917, da han begynte med en serie forelesninger om matematikkens grunnlag med hjelp av Paul Bernays. Selv om Hilbert var imponert over arbeidet til Russell og Whitehead i deres Principia Mathematica, ble han overbevist om at logikernes forsøk på å redusere matematikk til logikk ikke kunne lykkes, særlig på grunn av den ikke-logiske karakteren av deres aksiom for reduserbarhet. Samtidig bedømte han den intuisjonelle avvisningen av loven om den ekskluderte midten som uakseptabel for matematikk. Derfor,for å motvirke bekymringer som ble oppdaget av oppdagelsen av de logiske og setteoretiske paradokser, var det nødvendig med en ny tilnærming for å rettferdiggjøre moderne matematiske metoder.

Sommeren 1920 hadde Hilbert formulert en slik tilnærming. For det første skulle moderne matematiske metoder bli representert i formelle deduktive systemer. For det andre skulle disse formelle systemene bevises syntaktisk konsistente, ikke ved å vise en modell eller redusere deres konsistens til et annet system, men ved et direkte metamatematisk argument av en eksplisitt, "finitær" karakter. Tilnærmingen ble kjent som Hilberts program. Epsilon-beregningen skulle gi den første komponenten i dette programmet, mens epsilonsubstitusjonsmetoden var å gi den andre.

Epsilon-beregningen er, i sin mest grunnleggende form, en utvidelse av førsteordens predikatlogikk med en "epsilon-operasjon" som for enhver ekte eksistensiell formel velger et vitne til den eksistensielle kvantifisereren. Utvidelsen er konservativ i den forstand at den ikke gir nye konsekvenser av første orden. Men omvendt kan kvantifiserere defineres i form av epsilonene, slik at førsteordens logikk kan forstås i form av kvantifiseringsfri begrunnelse som involverer epsilon-operasjonen. Det er denne sistnevnte egenskapen som gjør beregningen praktisk for å bevise konsistens. Egnede utvidelser av epsilon-beregningen gjør det mulig å legge inn sterkere, kvantifiserende teorier om tall og sett i kvantifiseringsfrie beregninger. Hilbert forventet at det ville være mulig å demonstrere konsistensen av slike utvidelser.

2. Epsilon-beregningen

I sitt foredrag i Hamburg i 1921 (1922) presenterte Hilbert først ideen om å bruke valgfunksjoner for å håndtere prinsippet om den ekskluderte midten i et formelt system for aritmetikk. Disse ideene ble utviklet til epsilon-beregningen og epsilon-substitusjonsmetoden i en serie forelesningskurs mellom 1921 og 1923, og i Hilbert's (1923). Den endelige presentasjonen av epsilon-calculus finnes i Wilhelm Ackermanns avhandling (1924).

Dette avsnittet vil beskrive en versjon av beregningen som tilsvarer førsteordens logikk, mens utvidelser til første- og andreordens aritmetikk vil bli beskrevet nedenfor.

La (L) være et førsteordens språk, det vil si en liste over konstante, funksjons- og relasjonssymboler med spesifiserte arities. Settet med epsilon-termer og settet med formler for (L) er definert induktivt, samtidig, som følger:

  • Hver konstant av (L) er et begrep.
  • Hver variabel er et begrep.
  • Hvis (s) og (t) er termer, er (s = t) en formel.
  • Hvis (s_1, / ldots, s_k) er termer og (F) er et (k) - ary funksjonssymbol til (L, F (s_1, / ldots, s_k)) er et begrep.
  • Hvis (s_1, / ldots, s_k) er termer og (R) er et (k) - ary-relasjonssymbol for (L, R (s_1, / ldots, s_k)) er en formel.
  • Hvis (A) og (B) er formler, er det også (A / kile B, A / vee B, A / høyre mark B) og (neg A).
  • Hvis (A) er en formel og (x) er en variabel, er (varepsilon x A) et begrep.

Substitusjon og forestillingene om fri og bundet variabel er definert på vanlig måte; spesielt blir variabelen (x) bundet i begrepet (varepsilon x A). Den tiltenkte tolkningen er at (varepsilon x A) betegner noen (x) tilfredsstillende (A), hvis det er en. Dermed styres epsilonbetegnelsene av følgende aksiom (Hilberts “transfinite axiom”): [A (x) høyre mark A (varepsilon x A)) I tillegg inkluderer epsilon-beregningen et komplett sett med aksiomer som styrer klassiske proposisjonelle tilkoblinger og aksiomer som styrer likhetssymbolet. De eneste reglene i regnestykket er følgende:

  • Modus ponens
  • Bytte: fra (A (x)), konkludere (A (t)), for ethvert begrep (t.)

Tidligere former for epsilon-beregningen (som den som ble presentert i Hilbert 1923) bruker en dobbel form av epsilon-operatøren, der (varepsilon x A) returnerer en verdi som forfalsker (A (x)). Versjonen over ble brukt i Ackermanns avhandling (1924), og har blitt standard.

Vær oppmerksom på at beregningen som nettopp er beskrevet, er kvantifiseringsfri. Kvantifiserere kan defineres som følger: (start {align} eksisterer x A (x) & / equiv A (varepsilon x A) / \ forall x A (x) & / equiv A (varepsilon x (neg A)) end {align}) De vanlige kvantifiseringsaksiomene og -reglene kan avledes fra disse, så definisjonene ovenfor tjener til å legge inn førsteordens logikk i epsilon-beregningen. Samtalen er imidlertid ikke sant: ikke alle formler i epsilon-beregningen er bildet av en vanlig kvantifisert formel under denne innebygningen. Derfor er epsilonberegningen mer uttrykksfull enn predikatberegningen, ganske enkelt fordi epsilonuttrykk kan kombineres på mer komplekse måter enn kvantifiseringsmidler.

Det er verdt å merke seg at epsilonuttrykk er nondeterministisk, og dermed representerer en form for det valgte aksiomet. For eksempel, på et språk med konstante symboler (a) og (b), er (varepsilon x (x = a / vee x = b)) enten (a) eller (b), men beregningen lar den være helt åpen for hva som er tilfelle. Man kan legge til et skjema for ekstensjonalitet, [(alt x (A (x) leftrightarrow B (x)) høyre pil / varepsilon x A = / varepsilon x B) som hevder at epsilon-operatøren tildeler det samme vitne til likeverdige formler (A) og (B). For mange applikasjoner er dette ekstra skjemaet imidlertid ikke nødvendig.

3. Epsilon-setningene

Det andre bindet av Hilbert og Bernays 'Grundlagen der Mathematik (1939) gir en redegjørelse for resultatene på epsilon-regnestykket som hadde blitt bevist på den tiden. Dette inkluderer en drøfting av den første og andre epsilon-teorems med anvendelser til førsteordens logikk, epsilonsubstitusjonsmetoden for aritmetikk med åpen induksjon, og en utvikling av analyse (det vil si annenordens aritmetikk) med epsilon-kalkulaturen.

De første og andre epsilon-teoremene er som følger:

Første epsilon-teorem: Anta (Gamma / cup {A }) er et sett med kvantifiseringsfrie formler som ikke involverer epsilon-symbolet. Hvis (A) er avledelig fra (Gamma) i epsilon-kalkulaturen, er (A) deriverbar fra (Gamma) i kvantifiseringsfri predikatlogikk.

Andre epsilon-teorem: Anta (Gamma / cup {A }) er et sett med formler som ikke involverer epsilonsymbolet. Hvis (A) er avledelig fra (Gamma) i epsilon-kalkulaturen, er (A) deriverbar fra (Gamma) i predikatlogikken.

I det første epsilon-teoremet er "kvantifiseringsfri predikatlogikk" ment å inkludere substitusjonsregelen ovenfor, slik at kvantifiseringsfrie aksiomer oppfører seg som deres universelle lukkinger. Siden epsilonberegningen inkluderer førsteordens logikk, innebærer den første epsilonsteoremet at enhver omvei gjennom førsteordens predikatlogikk som brukes til å utlede et kvantifiseringsfritt teorem fra kvantifiseringsfrie aksiomer, til slutt kan unngås. Det andre epsilon-teoremet viser at enhver omkjøring gjennom epsilon-kalkylen som brukes til å utlede et teorem på språket til predikatkalkulusen fra aksiomer på språket til predikatkalkulus, også kan unngås.

Mer generelt fastslår det første epsilonsteoremet at kvantifiseringsmidler og epsiloner alltid kan elimineres fra et bevis på en kvantifiseringsfri formel fra andre kvantifiseringsfrie formler. Dette er spesielt viktig for Hilberts program, siden epsilonene spiller rollen som ideelle elementer i matematikk. Hvis kvantifiseringsfrie formler tilsvarer den "reelle" delen av den matematiske teorien, viser den første epsilon-teoremet at ideelle elementer kan elimineres fra bevis på virkelige utsagn, forutsatt at aksiomene også er reelle utsagn.

Denne ideen er presis i en viss generell konsistenssteorem som Hilbert og Bernays stammer fra den første epsilon-teoremet, som sier følgende: La (F) være et hvilket som helst formelt system som er resultatet av predikatberegningen ved tilsetning av konstant, funksjon og predikatsymboler pluss sanne aksiomer som er kvantifiserings- og epsilonfrie, og antar at sannheten om atomformler i det nye språket kan avgjøres. Da er (F) konsistent i sterk forstand at hver avledelig kvantifiserings- og epsilonfri formel er sann. Hilbert og Bernays bruker dette teoremet for å gi et finitalt konsistens bevis på elementær geometri (1939, kapittel 1.4).

Vanskeligheten med å gi konsistensbevis for aritmetikk og analyse består i å utvide dette resultatet til tilfeller der aksiomene også inneholder ideelle elementer, dvs. epsilontermer.

Videre lesning. De originale kildene på epsilon-calculus og epsilon-setningene (Ackermann 1924, Hilbert & Bernays 1939) er fortsatt bare tilgjengelige på tysk. Leisenring 1969 er en relativt moderne boklengdes introduksjon til epsilon-kalkylen på engelsk. Den første og andre epsilon-teorem er beskrevet i detalj i Zach 2017. Moser & Zach 2006 gir en detaljert analyse for saken uten likeverd. De originale bevisene er gitt for aksiomatiske presentasjoner av epsilon-regnestykket. Maehara 1955 var den første til å vurdere sekvensberegning med epsilon-termer. Han viste hvordan man kunne bevise den andre epsilonsteoremet ved bruk av kuttet eliminering, og styrket deretter teoremet til å inkludere skjemaet om ekstensjonalitet (Maehara 1957). Baaz et al. 2018 gir en forbedret versjon av det første epsilon-teoremet. Rettelser av feil i litteraturen (inkludert Leisenrings bok) finnes i Flannagan 1975; Ferrari 1987; og Yasuhara 1982. En variant av epsilon-beregningen basert på Skolem-funksjoner, og derfor kompatibel med førsteordens logikk, er omtalt i Davis & Fechter 1991.

4. Herbrands teorem

Hilbert og Bernays brukte metodene til epsilon-kalkulusen for å etablere teoremer om førsteordens logikk som ikke henviser til selve epsilonkalkulusen. Et slikt eksempel er Herbrands teorem (Herbrand 1930; se Buss 1995, Girard 1982, og avsnitt 2.5 i Buss 1998). Dette er ofte formulert som påstanden om at hvis en eksistensiell formel (eksisterer x_1 / ldots / eksisterer x_k A (x_1, / ldots, x_k)) er deriverbar i første ordens predikatlogikk (uten likeverd), hvor (A) er kvantifiseringsfritt, så er det sekvenser av termer (t_ {1} ^ 1, / ldots, t_ {k} ^ 1, / ldots, t_ {1} ^ n, / ldots, t_k ^ n), slik at [A (t_ {1} ^ 1, / ldots, t_k ^ 1) vee / ldots / vee A (t_ {1} ^ n, / ldots, t_k ^ n)) er en tautologi. Hvis man har å gjøre med førsteordens logikk med likhet,man må erstatte “tautologi” med “tautologisk konsekvens av substitusjonsforekomster av likhetsaksiomene”; vi vil bruke begrepet “kvasi-tautologi” for å beskrive en slik formel.

Versjonen av Herbrands teorem som nettopp er beskrevet følger umiddelbart fra Extended First Epsilon Theorem of Hilbert and Bernays. Ved å bruke metoder assosiert med beviset for den andre epsilonsteoremet, oppnådde Hilbert og Bernays imidlertid et sterkere resultat som, i likhet med Herbrands opprinnelige formulering, gir mer informasjon. For å forstå de to delene av teoremet nedenfor, hjelper det å vurdere et bestemt eksempel. La (A) være formelen

(eksisterer x_1 / forall x_2 / eksisterer x_3 / forall x_4 B (x_1, x_2, x_3, x_4)) der (B) er kvantifiseringsfritt. Negasjonen av (A) tilsvarer (forall x_1 / eksisterer x_2 / forall x_3 / eksisterer x_4 / neg B (x_1, x_2, x _3, x_4).) Ved å Skolemizing, dvs. ved å bruke funksjonssymboler for å være vitne til de eksistensielle kvantifisererne, får vi (eksisterer 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)). Når vi tar avstand fra dette, ser vi at den opprinnelige formelen er "ekvivalent" til (forall f_2, f_4 / eksisterer x_1, x_3 B (x_1, f_2 (x_1), x_3, f_4 (x_1, x_3)).)

Den første leddet i teoremet nedenfor, i dette spesielle tilfellet, sier at formelen (A) ovenfor er avledelig i førsteordens logikk hvis og bare hvis det er en rekke ordene (t_ {1} ^ 1, t_ {3} ^ 1, / ldots, t_ {1} ^ n, t_ {3} ^ n) på det utvidede språket med (f_2) og (f_4) slik at [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))) er en kvasitatologi.

Den andre leddet i teoremet nedenfor, i dette spesielle tilfellet, sier at formelen (A) ovenfor er avledbar i førsteordens logikk hvis og bare hvis det er sekvenser med variabler (x_ {2} ^ 1, x_ { 4} ^ 1, / ldots, x_2 ^ n, x_4 ^ n) og termer (s_ {1} ^ 1, s_ {3} ^ 1, / ldots, s_1 ^ n, s_3 ^ n) i originalen språk slik at [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)) er en kvasi-tautologi, og slik at (A) er avledet fra denne formelen ved å bruke bare kvantifiserings- og idempotensitetsreglene beskrevet nedenfor.

Mer generelt, antar at (A) er en hvilken som helst prenexformel, av formen (mathbf {Q} _1 x_1 / ldots / mathbf {Q} _n x_n B (x_1, / ldots, x_n),) hvor (B) er kvantifiseringsfritt. Da sies (B) å være matrisen til (A), og en forekomst av (B) oppnås ved å erstatte termer på språket til (B) for noen av dens variabler. Herbrands normale form (A ^ H) av (A) oppnås av

  • slette hver universell kvantifiserer, og
  • erstatte hver universelt kvantifiserte variabel (x_i) med (f_i (x_ {i} ^ 1, / ldots, x_ {i} ^ {k (i)})), hvor (x_ {i} ^ 1, / ldots, x_ {i} ^ {k (i)}) er variablene som tilsvarer de eksistensielle kvantifiseringene som går foran (mathbf {Q} _i) i (A) (i rekkefølge), og (f_i) er et nytt funksjonssymbol som er utpekt for denne rollen.

Når vi refererer til en forekomst av matrisen til (A ^ H), mener vi en formel som oppnås ved å erstatte termer i det utvidede språket i matrisen til (A ^ H). Vi kan nå oppgi Hilbert og Bernays formulering av

Herbrands teorem. (1) En preneksformel (A) er deriverbar i predikatberegningen hvis og bare hvis det er en disjunksjon av forekomster av matrisen til (A ^ H) som er en kvasi-tautologi.

(2) En preneksformel (A) er deriverbar i predikatberegningen hvis og bare hvis det er en disjunksjon (bigvee_j B_j) forekomster av matrisen til (A), slik at (bigvee_j B_j) er en kvasi-tautologi, og (A) er avledelig fra (bigvee_j B_j) ved å bruke følgende regler:

  • fra (C_1 / vee / ldots / vee C_i (t) vee / ldots / vee C_m)

    konkludere (C_1 / vee / ldots / vee / eksisterer x C_i (x) vee / ldots / vee C_m) og

  • fra (C_1 / vee / ldots / vee C_i (x) vee / ldots / vee C_m)

    konkludere (C_1 / vee / ldots / vee / forall xC_i (x) vee / ldots / vee C_m) (hvis (x) ikke i (C_j) for (j / ne i)),

samt idempotensen til (vee) (fra (C / vee C / vee D) konkludere (C / vee D)).

Herbrands teorem kan også oppnås ved å bruke kuttet eliminering, via Gentzens "midlertidige teorem." Imidlertid har beviset ved bruk av det andre epsilon-teoremet skillet mellom å være det første fullstendige og riktige beviset på Herbrands teorem. Videre, og dette er sjelden anerkjent, mens beviset basert på kutteliminering gir en begrensning på lengden av Herbrand-disjunksjonen bare som en funksjon av kuttens rangering og kompleksitet av kuttformlene i beviset, lengden oppnådd fra beviset basert på epsilon-beregningen gir en bundet som en funksjon av antall applikasjoner av det transfinite aksiomet, og rangen og graden av epsilon-begrepene som forekommer der. Med andre ord, lengden på Herbrand-disjunksjonen avhenger bare av den kvantifiserende kompleksiteten til de involverte substitusjonene, og f.eks.ikke i det hele tatt på proposisjonsstrukturen eller bevisets lengde.

Versjonen av Herbrands teorem uttalt i begynnelsen av dette avsnittet er i det vesentlige det spesielle tilfellet til (2) der formelen (A) er eksistensiell. I lys av dette spesielle tilfellet tilsvarer (1) påstanden om at en formel (A) er avledbar i førsteordens predikatlogikk hvis og bare hvis (A ^ H) er. Fremover for denne ekvivalensen er mye lettere å bevise; faktisk for enhver formel (A, A / høyre mark A ^ H) er deriverbar i predikatlogikken. Å bevise omvendt retning innebærer å fjerne tilleggsfunksjonssymbolene i (A ^ H), og er mye vanskeligere, spesielt i nærvær av likhet. Det er her epsilonmetoder spiller en sentral rolle.

Gitt en prenexformel, er Skolem normalform (A ^ S) definert dobbelt til (A ^ H), dvs. ved å erstatte eksistensielt kvantifiserte variabler med å vitne til funksjoner. Hvis (Gamma) er et sett med prenexsetninger, la (Gamma ^ S) betegne settet med sine Skolem-normale former. Ved bruk av deduksjonssteoremet og Herbrands teorem er det ikke vanskelig å vise at følgende tilsvarer parvis: (begin {align} Gamma & / text {proves} A \\ / Gamma & / text {proves} A ^ H \\ / Gamma ^ S & / text {proves} A \\ / Gamma ^ S & / text {proves} A ^ H / end {align})

En påfallende anvendelse av Herbrands teorem og relaterte metoder finnes i Luckhardts (1989) analyse av Roths teorem. For en diskusjon om nyttige utvidelser av Herbrands metoder, se Sieg 1991. En modellteoretisk versjon av dette er omtalt i Avigad 2002a.

5. Epsilon substitusjonsmetode og aritmetikk

Som nevnt ovenfor, historisk sett var den primære interessen for epsilon-beregningen som et middel til å oppnå konsistensbevis. Hilberts forelesninger fra 1917–1918 bemerker allerede at man enkelt kan bevise konsistensen av proposisjonell logikk, ved å ta proposisjonsvariabler og formler for å strekke seg over sannhetsverdiene 0 og 1, og tolke de logiske forbindelsene som de tilsvarende aritmetiske operasjoner. Tilsvarende kan man bevise konsistensen av predikatlogikk (eller den rene epsilonberegningen), ved å spesialisere seg til tolkninger der diskursuniverset har et enkelt element. Disse hensynene antyder følgende mer generelle program for å bevise konsistens:

  • Utvid epsilonberegningen på en slik måte at den representerer større deler av matematikken.
  • Vis med finitære metoder at hvert bevis i det utvidede systemet har en jevn tolkning.

Tenk for eksempel på aritmetisk språk, med symboler for (0), (1), (+), (ganger), (lt). Sammen med kvantifiseringsfrie aksiomer som definerer de grunnleggende symbolene, kan man spesifisere at epsilonuttrykkene (varepsilon x A (x)) plukker ut minst mulig verdi tilfredsstillende (A), hvis det er ett, med følgende aksiom: (tag {*} A (x) høyre mark A (varepsilon x A (x)) kile / varepsilon x A (x) le x) Resultatet er et system som er sterkt nok til å tolke først -ordning (Peano) aritmetikk. Alternativt kan man ta epsilonsymbolet for å tilfredsstille følgende aksiom: [A (y) høyre pil A (varepsilon x A (x)) kile / varepsilon x A (x) ne y + 1.)

Med andre ord, hvis det er noe vitne (y) som tilfredsstiller (A (y)), returnerer epsilon-uttrykket en verdi hvis forgjenger ikke har den samme egenskapen. Det er tydelig at epsilon-betegnelsen beskrevet av (*) tilfredsstiller det alternative aksiomet; omvendt kan man sjekke at gitt (A), en verdi av (varepsilon x (eksisterer z / le x A (x))) som tilfredsstiller det alternative aksiomet, kan brukes til å tolke (varepsilon x A (x)) i (*). Man kan videre fikse betydningen av epsilon-betegnelsen med aksiomen (varepsilon x A (x) ne 0 / høyre pil A (varepsilon x A (x))) som krever at hvis det ikke er noe vitne til (A), epsilon term return 0. For diskusjonen nedenfor er det imidlertid mest praktisk å fokusere på (*) alene.

Anta at vi ønsker å vise at systemet over er konsekvent; med andre ord, vi ønsker å vise at det ikke er noe bevis på formelen (0 = 1). Ved å skyve alle substitusjoner til aksiomene og erstatte frie variabler med konstanten 0, er det nok å vise at det ikke er noe proposisjonelt bevis på (0 = 1) fra et endelig sett med lukkede forekomster av aksiomene. For det er det nok å vise at man, gitt ethvert begrenset sett med lukkede forekomster av aksiomer, kan tildele tallverdier til uttrykk på en slik måte at alle aksiomene er sanne under tolkningen. Siden de aritmetiske operasjonene (+) og (times) kan tolkes på vanlig måte, ligger den eneste vanskeligheten i å finne passende verdier å tildele epsilon-begrepene.

Hilberts epsilonsubstitusjonsmetode kan omtrent beskrives som følger:

  • Gitt et begrenset sett med aksiomer, begynn med å tolke alle epsilon-termer som 0.
  • Finn en forekomst av aksiomet (*) ovenfor som er usant under tolkningen. Dette kan bare skje hvis man har et begrep t slik at (A (t)) stemmer i tolkningen, men enten (A (varepsilon x A (x))) er falsk eller verdien av (t) er mindre enn verdien til (varepsilon x A (x)).
  • “Reparer” oppgaven ved å tilordne (varepsilon x A (x)) verdien til (t), og gjenta prosessen.

Et finitært konsistens bevis oppnås når det er vist på en finitalt akseptabel måte at denne prosessen med påfølgende "reparasjoner" avsluttes. Hvis den gjør det, er alle kritiske formler ekte formler uten epsilon-termer.

Denne grunnideen ("Hilbertsche Ansatz") ble først satt ut av Hilbert i hans foredrag i 1922 (1923), og utdypet i forelesninger 1922–23. Eksemplene som gis der, omhandler imidlertid bare bevis der alle forekomster av det transfinite aksiom tilsvarer et enkelt epsilon-begrep (varepsilon x A (x)). Utfordringen var å utvide tilnærmingen til mer enn ett epsilon-begrep, til nestede epsilon-termer, og til slutt til andreordens-epsiloner (for å oppnå et konsistensbevis ikke bare av aritmetikk, men av analyse).

Vanskeligheten med å håndtere nestede epsilonbetegnelser kan beskrives som følger. Anta at en av aksiomene i beviset er den transfinite aksiom [B (y) høyre pil B (varepsilon y B (y))) (varepsilon y B (y)) kan selvfølgelig forekomme i andre formler i beviset, spesielt i andre transfinite aksiomer, f.eks. [A (x, / varepsilon y B (y)) høyre pil A (varepsilon x A (x, / varepsilon y B (y)), / varepsilon y B (y))) Så først virker det som nødvendig å finne en riktig tolkning for (varepsilon y B (y)) før vi prøver å finne en for (varepsilon x A (x, / varepsilon y B (y))). Imidlertid er det mer kompliserte mønstre som epsilontermer kan forekomme i et bevis. Et eksempel på aksiomet, som spiller en rolle i å bestemme riktig tolkning for (varepsilon y B (y)) kan være [B (varepsilon x A (x,\ varepsilon y B (y))) høyre pil B (varepsilon y B (y))) Hvis (B) (0) er usant, så i første runde av prosedyren (varepsilon y B (y)) vil bli tolket av 0. En påfølgende endring av tolkningen av (varepsilon x A (x, 0)) fra 0 til, si (n), vil resultere i en tolkning av denne forekomsten som (B (n) høyre mark B) (0) som vil være falsk hvis (B (n)) er sant. Så tolkningen av (varepsilon y B (y)) vil måtte korrigeres til (n), noe som igjen kan resultere i tolkningen av (varepsilon x A (x, / varepsilon y B (y))) for ikke lenger å være en ekte formel.vil resultere i en tolkning av denne forekomsten som (B (n) høyre mark B) (0) som vil være falsk hvis (B (n)) er sant. Så tolkningen av (varepsilon y B (y)) vil måtte korrigeres til (n), noe som igjen kan resultere i tolkningen av (varepsilon x A (x, / varepsilon y B (y))) for ikke lenger å være en ekte formel.vil resultere i en tolkning av denne forekomsten som (B (n) høyre mark B) (0) som vil være falsk hvis (B (n)) er sant. Så tolkningen av (varepsilon y B (y)) vil måtte korrigeres til (n), noe som igjen kan resultere i tolkningen av (varepsilon x A (x, / varepsilon y B (y))) for ikke lenger å være en ekte formel.

Dette er bare en skisse av vanskene med å utvide Hilberts idé til den generelle saken. Ackermann (1924) ga en slik generalisering ved å bruke en prosedyre som “backtracks” når en ny tolkning på et gitt stadium resulterer i behovet for å rette en tolkning som allerede er funnet på et tidligere stadium.

Ackermanns prosedyre gjaldt et system med andre orden aritmetikk, der imidlertid andre ordens vilkår ble begrenset for å utelukke kryssbinding av andre ordens epsiloner. Dette tilsvarer omtrent en begrensning til aritmetisk forståelse som det tilgjengelige settformingsprinsippet (se diskusjonen på slutten av denne delen). Ytterligere vanskeligheter med andre ordens epsilonbetegnelser dukket opp, og det viste seg raskt at beviset mens det sto var feilaktig. Ingen på Hilberts skole skjønte imidlertid omfanget av vanskeligheten før i 1930, da Gödel kunngjorde sine ufullstendige resultater. Inntil da ble det antatt at beviset (i det minste med noen modifikasjoner introdusert av Ackermann,noen av dem involverte ideer fra von Neumanns (1927) versjon av epsilonsubstitusjonsmetoden) ville gjennomgå i det minste for den første ordens delen. Hilbert og Bernays (1939) antyder at metodene som brukes bare gir et konsistensbevis for første-ordens aritmetikk med åpen induksjon. I 1936 lyktes Gerhard Gentzen å gi et bevis på konsistensen av førsteordens aritmetikk i en formulering basert på predikatlogikk uten epsilonsymbolet. Dette beviset bruker transfinitt induksjon opp til (varepsilon_0). Ackermann (1940) var senere i stand til å tilpasse Gentzens ideer for å gi et korrekt konsistensbevis for førsteordens aritmetikk ved bruk av epsilon-substitusjonsmetoden. Gerhard Gentzen lyktes i å gi et bevis på konsistensen av førsteordens aritmetikk i en formulering basert på predikatlogikk uten epsilonsymbolet. Dette beviset bruker transfinitt induksjon opp til (varepsilon_0). Ackermann (1940) var senere i stand til å tilpasse Gentzens ideer for å gi et korrekt konsistensbevis for førsteordens aritmetikk ved bruk av epsilon-substitusjonsmetoden. Gerhard Gentzen lyktes i å gi et bevis på konsistensen av førsteordens aritmetikk i en formulering basert på predikatlogikk uten epsilonsymbolet. Dette beviset bruker transfinitt induksjon opp til (varepsilon_0). Ackermann (1940) var senere i stand til å tilpasse Gentzens ideer for å gi et korrekt konsistensbevis for førsteordens aritmetikk ved bruk av epsilon-substitusjonsmetoden.

Selv om Ackermanns forsøk på et konsistensbevis for annenordens aritmetikk var mislykket, ga de en klarere forståelse av bruken av andre ordens epsilon-termer i formaliseringen av matematikk. Ackermann brukte andreordens epsilon-termer (varepsilon f / A (f)), der (f) er en funksjonsvariabel. I analogi med den første ordens saken, er (varepsilon f / A (f)) en funksjon som (A (f)) er sant, f.eks. (Varepsilon f (x + f (x)) = 2x)) er identitetsfunksjonen (f (x) = x). Igjen, i analogi med førsteordens sak, kan man bruke andreordens epsiloner for å tolke andreordens kvantifiserere. Spesielt for enhver annenordens formel (A (x)) kan man finne et begrep (t (x)) slik at [A (x) leftrightarrow t (x) = 1) er deriverbar i beregningen (formelen (A) kan ha andre gratis variabler,i så fall vises disse også i begrepet (t)). Man kan da bruke dette faktum til å tolke forståelsesprinsipper. På et språk med funksjonssymboler har disse formen (eksisterer f / forall x (A (x) leftrightarrow f (x) = 1)) for en vilkårlig formel (A (x)). Forståelse uttrykkes mer ofte i form av angitte variabler, i så fall har den formen [(eksisterer Y / forall x (A (x) leftrightarrow / \ i Y),) og hevder at hver annen ordens formel, med parametere, definerer et sett.i så fall har den formen [(eksisterer Y / forall x (A (x) leftrightarrow x / in Y),) og hevder at hver andre ordensformel, med parametere, definerer et sett.i så fall har den formen [(eksisterer Y / forall x (A (x) leftrightarrow x / in Y),) og hevder at hver andre ordensformel, med parametere, definerer et sett.

Analyse, eller andreordens aritmetikk, er utvidelsen av førsteordens aritmetikk med forståelsesskjemaet for vilkårlige andreordens formler. Teorien er imponerende ved at den lar en definere sett med naturlige tall ved å bruke kvantifiserere som spenner over hele universet av sett, inkludert implisitt, settet som blir definert. Man kan oppnå predikative fragmenter av denne teorien ved å begrense typen formler som er tillatt i forståelsesaksiomet. For eksempel tilsvarer begrensningen diskutert i forbindelse med Ackermann ovenfor det aritmetiske forståelsesskjemaet, der formler ikke involverer andreordens kvantifiserere. Det er forskjellige måter å oppnå sterkere analysefragmenter som likevel er predikativt begrunnet. For eksempel oppnår man forsterket analyse ved å knytte en ordinær rang til å sette variabler;omtrent, i definisjonen av et sett med en gitt rang, varierer kvantifiserere bare over sett med lavere rangering, dvs. de hvis definisjoner er logisk tidligere.

Videre lesning. Hilberts og Ackermanns tidlige bevis er omtalt i Zach 2003; 2004. Von Neumanns bevis er temaet for Bellotti 2016. Ackermanns bevis fra 1940 er omtalt i Hilbert & Bernays 1970, og Wang 1963. En moderne presentasjon er gitt av Moser 2006. En tidlig anvendelse av epsilonsubstitusjon er den uten moteksemple-tolkningen (Kreisel 1951).

6. Nyere utvikling

I dette avsnittet diskuterer vi utviklingen av epsilonsubstitusjonsmetoden for å oppnå konsistensresultater for sterke systemer; disse resultatene er av matematisk art. Vi kan dessverre ikke diskutere detaljene i bevisene her, men vil gjerne indikere at epsilon-substitusjonsmetoden ikke døde med Hilberts program, og at en betydelig mengde aktuell forskning utføres i epsilon-formalismer.

Gentzens konsistensbevis for aritmetikk lanserte et forskningsfelt som kalles ordinal analyse, og programmet for å måle styrken til matematiske teorier ved bruk av ordinære notasjoner forfølges fortsatt i dag. Dette er spesielt relevant for det utvidede programmet til Hilbert, der målet er å rettferdiggjøre klassisk matematikk i forhold til konstruktive, eller kvasi-konstruktive systemer. Gentzens metoder for kutteliminering (og utvidelser til infinitær logikk utviklet av Paul Lorentzen, Petr Novikov og Kurt Schütte) har i stor grad erstattet epsilonsubstitusjonsmetoder i disse målene. Men epsilonberegningsmetoder gir en alternativ tilnærming, og det er fortsatt aktiv forskning på måter å utvide Hilbert-Ackermann-metodene til sterkere teorier. Det generelle mønsteret forblir det samme:

  1. Integrer teorien som er undersøkt i en passende epsilon-kalkyle.
  2. Beskriv en prosess for oppdatering av oppgaver til epsilon-vilkårene.
  3. Vis at prosedyren normaliseres, dvs. gitt et sett med vilkår, er det en sekvens med oppdateringer som resulterer i en oppgave som tilfredsstiller aksiomene.

Siden det siste trinnet garanterer konsistensen i den opprinnelige teorien, er man fra et grunnleggende synspunkt interessert i metodene som er brukt for å bevise normalisering. For eksempel oppnår man en ordinær analyse ved å tilordne ordinære notasjoner til trinn i prosedyren, på en slik måte at verdien av en notasjon synker med hvert trinn.

På 1960-tallet utvidet Tait (1960, 1965, 2010) Ackermanns metoder for å få en ordinær analyse av utvidelser av aritmetikk med prinsipper for transfinittinduksjon. Mer strømlinjeformede og moderne versjoner av denne tilnærmingen finner du i Mints 2001 og Avigad 2002b. Mer nylig har Mints, Tupailo og Buchholz vurdert sterkere, men likevel predikativt forsvarlige, fragmenter av analyse, inkludert teorier om aritmetisk forståelse og en (Delta ^ {1} _1) - forståelsesregel (Mints, Tupailo & Buchholz 1996; Mints & Tupailo 1999; se også Mints 2016). Arai 2002 har utvidet epsilonsubstitusjonsmetoden til å omfatte teorier som lar en iterere aritmetisk forståelse langs primitive rekursive brønnbestillinger. Spesielt,hans arbeid gir ordinære analyser for predikative fragmenter av analyse som involverer transfinite hierarkier og transfinite induksjon.

Noen første skritt er tatt for å bruke epsilonsubstitusjonsmetoden i analysen av impedikative teorier (se Arai 2003, 2006 og Mints 2015).

En variasjon på trinn 3 ovenfor innebærer å vise at normaliseringsprosedyren ikke er følsom for valg av oppdateringer, det vil si at enhver sekvens med oppdateringer avsluttes. Dette kalles sterk normalisering. Mints 1996 har vist at mange av prosedyrene som vurderes har denne sterkere egenskapen.

I tillegg til den tradisjonelle, grunnleggende grenen av bevisteori, er det i dag en god del interesse for strukturell bevisteori, en gren av faget som fokuserer på logiske deduktive beregninger og deres egenskaper. Denne forskningen er nært knyttet til problemstillinger som er relevante for informatikk, og har å gjøre med automatisk deduksjon, funksjonell programmering og datastyrt verifisering. Også her har metoder i gentzen stil en tendens til å dominere (se igjen oppføringen om bevisteori). Men epsilonberegningen kan også gi verdifull innsikt; jfr for eksempel Aguilera & Baaz 2019, eller omtalen av Herbrands teorem ovenfor.

Bortsett fra undersøkelsene av epsilon-beregningen i bevisteori, skal to anvendelser nevnes. Den ene er bruken av epsilonnotasjon i Bourbakis Theorie des ensembles (1958). Det andre, av kanskje større gjeldende interesse, er bruken av epsilon-operatøren i teorem-bevisende systemene HOL og Isabelle, der den ekspressive kraften til epsilon-termer gir betydelige praktiske fordeler.

7. Epsilon operatører i lingvistikk, filosofi og ikke-klassisk logikk

Å lese epsilon-operatøren som en ubestemt valgoperator (“en (x) slik at (A (x))”) antyder at det kan være et nyttig verktøy i analysen av ubestemte og bestemte substantivfraser i formell semantikk. Epsilon-notasjonen har faktisk blitt brukt på en slik måte, og denne applikasjonen har vist seg å være nyttig i forbindelse med anaforisk referanse.

Tenk på det kjente eksemplet

Hver bonde som eier et esel slår det

Den allment aksepterte analysen av denne setningen er gitt av den universelle setningen

(forall x / forall y (mathrm {Farmer} (x) kil / mathrm {Donkey} (y) kil / mathrm {Owns} (x, y)) høyre pil / mathrm {Beats} (x, y)))

Ulempen er at "et esel" antyder en eksistensiell kvantifiserer, og analysen bør på en eller annen måte parallelle i form av analysen av setning 3 gitt av 4:

  1. Hver bonde som eier et esel er fornøyd,
  2. (forall x (mathrm {Farmer} (x) kilen / eksisterer y (mathrm {Donkey} (y) kilen / mathrm {Owns} (x, y)) høyre pil / mathrm {Happy} (x))),

men den nærmeste mulige formaliseringen,

(forall x ((mathrm {Farmer} (x) kilen / eksisterer y (mathrm {Donkey} (y) kilen / mathrm {Owns} (x, y)) høyre pil / mathrm {Beats} (x, y)))

inneholder en gratis forekomst av (y). Evans 1980 antyder at siden pronomen refererer til uttrykk, bør de analyseres som klare beskrivelser; og hvis pronomenet forekommer som følge av en betinget, bestemmes de beskrivende forholdene av den forutgående. Dette fører til følgende E-type analyse av (1): (start {multline *} forall x ((mathrm {Farmer} (x) wedge / exist y (mathrm {Donkey} (y) kil / mathrm {Owns} (x, y)) høyre pil \(mathrm {Beats} (x, / iota y (mathrm {Donkey} (y) kil / mathrm {Owns} (x, y))) end {multline *}) Her er (iota x) den definitive beskrivelsesoperatøren, så (iota y (mathrm {Donkey} (y) kil / mathrm {Owns} (x, y))) er "eselet som eies av (x);". Problemet med dette er at den definitive beskrivelsen på standardanalysen har en unik tilstand,og så (5) vil være usant hvis det er en bonde som eier mer enn ett esel. En vei ut av dette er å introdusere en ny operatør, hvem (hvem som helst) som fungerer som en generaliserende kvantifiserer (Neale, 1990): (begin {multline *} forall x ((mathrm {Farmer} (x) kile / eksisterer y (mathrm {esel} (y) kile / mathrm {eier) (x, y)) høyre pil \(mathrm {Beats} (x, / mathrm {whe}, y (mathrm {Donkey} (y) wedge / mathrm {Owns} (x, y))) end {multline *})

Som påpekt av von Heusinger (1994) antyder dette at Neale er opptatt av at pronomen er tvetydige mellom bestemte beskrivelser ((iota) - uttrykk) og whe-uttrykk. Heusinger foreslår i stedet å bruke epsilon-operatører indeksert av valgfunksjoner (som avhenger av konteksten). I henhold til denne tilnærmingen er analysen av (1)

For hver valgfunksjon (i): (begynne {multline *} forall x ((mathrm {Farmer} (x) kile / mathrm {Owns} (x, / varepsilon_i y / mathrm {Donkey} (y)) høyre mark \\\ mathrm {Beats} (x, / varepsilon_ {a ^ *} y / mathrm {Donkey} (y)) slutt {multline *})

Her (a ^ *) er en valgfunksjon som avhenger av (i) og den forutgående for betinget: Hvis (i) er en valgfunksjon som velger (varepsilon_i y / mathrm {Donkey} (y)) fra settet med alle esler, deretter velger (varepsilon_ {a ^ *} y / mathrm {Donkey} (y)) fra settet med esler som eies av (x).

Denne tilnærmingen til å håndtere pronomen ved bruk av epsilon-operatører indeksert av valgfunksjoner gjør von Heusinger i stand til å håndtere en lang rekke omstendigheter (se Egli og von Heusinger, 1995; von Heusinger, 2000).

Anvendelser fra epsilon-operatøren i formell semantikk, og valgfunksjoner generelt, har fått betydelig interesse de siste årene. Von Heusinger og Egli (2000a) lister blant annet opp følgende: representasjoner av spørsmål (Reinhart, 1992), spesifikke ubestemmelser (Reinhart 1992; 1997; Winter 1997), pronomen fra E-typen (Hintikka og Kulas 1985; Slater 1986; Chierchia 1992, Egli og von Heusinger 1995) og bestemte substantivfraser (von Heusinger 1997, 2004).

For diskusjon om problemene og anvendelsene til epsilon-operatøren i språkvitenskap og språkfilosofi, se BH Slaters artikkel om epsilon calculi (sitert i delen Andre ressurser nedenfor), og samlingene von Heusinger og Egli 2000 og von Heusinger og Kempson 2004.

En annen anvendelse av epsilon-beregningen er som en generell logikk for resonnement om vilkårlige objekter. Meyer Viol (1995a) gir en sammenligning av epsilon-beregningen med Fine's (1985) teori om vilkårlige objekter. Forbindelsen er faktisk ikke vanskelig å se. Gitt ekvivalensen (forall x A (x) ekvivalent) A ((varepsilon x (neg A))), er uttrykket (varepsilon x (neg A)) et vilkårlig objekt i den forstand at det er et objekt som (A) er sant iff (A) generelt er sant.

Meyer Viol (1995a, 1995b) inneholder ytterligere bevis- og modellteoretiske studier av epsilon-beregningen; spesielt intuisjonistisk epsilon calculi. Her holder ikke epsilon-teoremene lenger, dvs. introduksjon av epsilon-termer gir ikke-konservative utvidelser av intuisjonistisk logikk. Andre undersøkelser av epsilonoperatører i intuisjonistisk logikk finnes i Shirai (1971), Bell (1993a, 1993b) og DeVidi (1995). For epsilon-operatører i mange verdsatte logikker, se Mostowski (1963), for modal epsilon calculus, Fitting (1975).

Videre lesning. Følgende er en liste over noen publikasjoner innen språk og språkvitenskap som er relevant for epsilon-beregningen og dens anvendelser. Leseren rettes spesielt mot samlingene von Heusinger & Egli (red.) 2000 og von Heusinger & Kempson (red.) 2004 for nærmere omtale og referanser: Bell 1993a, 1993b; Chierchia 1992; DeVidi 1995; Egli & von Heusinger 1995; Fin 1985; Tilpasset 1975; von Heusinger 1994, 1997, 2000, 2004; von Heusinger & Egli (red.) 2000; von Heusinger & Kempson (red.) 2004; Hintikka & Kulas 1985; Kempson, Meyer Viol, & Gabbay 2001; Meyer Viol 1995a, 1995b, Neale 1990; Mostowski 1963; Reinhart 1992, 1997; Slater 1986, 1988, 1994, 2000; og vinteren 1997.

Bibliografi

  • Aguilera, JP, Baaz, M., 2019, 'Uhørlige slutninger gjør bevisene kortere'. Journal of Symbolic Logic 84: 102–122.
  • Ackermann, W., 1924, 'Begründung des' 'tertium non datur' 'mittels der Hilbertschen Theorie der Widerspruchsfreiheit', Mathematische Annalen, 93: 1–36.
  • –––, 1937–38, 'Mengentheoretische Begründung der Logik', Mathematische Annalen, 115: 1–22.
  • ––– 1940, 'Zur Widerspruchsfreiheit der Zahlentheorie', Mathematische Annalen, 117: 162–194.
  • Arai, T., 2002, 'Epsilon substitusjonsmetode for teorier om hopphierarkier', Archive for Mathematical Logic, 2: 123–153.
  • –––, 2003, 'Epsilon substitusjonsmetode for ID (_ 1 (Pi ^ {0} _1 / vee / Sigma ^ {0} _1))', Annals of Pure and Applied Logic, 121: 163–208.
  • –––, 2006, 'Epsilon substitusjonsmetode for (Pi ^ {0} _2) - FIX. Journal of Symbolic Logic 71: 1155–1188
  • Avigad, J., 2002a, 'Saturated models of universal theory', Annals of Pure and Applied Logic, 118: 219–234.
  • –––, 2002b, 'Oppdater prosedyrer og 1-konsistensen av aritmetikk', Matematisk logikk kvartalsvis, 48: 3–13.
  • Baaz, M., Leitsch, A., Lolic, A., 2018, 'En sequent-calculus-basert formulering av den utvidede første epsilon-teorem', i: Artemov, S., Nerode, A. (red.), Logical Foundations of Computer Science, Berlin: Springer, 55–71.
  • Bell, JL, 1993a. 'Hilberts epsilon-operatør og klassisk logikk', Journal of Philosophical Logic, 22: 1–18.
  • –––, 1993b. 'Hilberts epsilonoperatør i intuisjonistiske teorier', Mathematical Logic Quarterly, 39: 323–337.
  • Bellotti, L., 2016, 'Von Neumanns konsistenssikkerhet', Review of Symbolic Logic, 9: 429–455.
  • Bourbaki, N., 1958, Theorie des ensembles, Paris: Hermann.
  • Buss, S., 1995, 'On Herbrand's theorem', Logic and Computational Complexity (Lecture Notes in Computer Science 960), Berlin: Springer, 195–209.
  • ––– 1998, 'Introduction to proof theory', i: Buss (red.), The Handbook of Proof Theory, Amsterdam: North-Holland, 1–78.
  • Chierchia, G., 1992. 'Anaphora og dynamisk logikk'. Lingvistikk og filosofi, 15: 111–183.
  • Davis, M. og R. Fechter, 1991, 'En gratis variabel versjon av den første ordens predikatberegning', Journal of Logic and Computation, 1: 431–451.
  • DeVidi, D., 1995. 'Intuitionistic (varepsilon) - and (tau) - calculi', Mathematical Logic Quarterly 41: 523–546.
  • Egli, U., von Heusinger, K., 1995, 'Epsilon operator and E-type pronomen', i U. Egli et al. (red.), Lexical Knowledge in the Organization of Language, Amsterdam: Benjamins, 121–141 (Current Issues in Linguistic Theory 114).
  • Evans, G., 1980, 'Pronouns', Linguistic Enquiry, 11: 337–362.
  • Ewald, WB (red.), 1996, Fra Kant til Hilbert. En kildebok i grunnlaget for matematikk, vol. 2, Oxford: Oxford University Press.
  • Ferrari, PL, 1987, 'Et notat om et bevis på Hilberts andre (varepsilon) - teorem', Journal of Symbolic Logic, 52: 214–215.
  • Fine, K., 1985. Reasoning with Arbitetary Objects, Oxford: Blackwell.
  • Fitting, M., 1975. 'A modal logic epsilon-calculus', Notre Dame Journal of Formal Logic, 16: 1–16.
  • Flannagan, TB, 1975, 'Om en utvidelse av Hilberts andre (varepsilon) - teorem', Journal of Symbolic Logic, 40: 393–397.
  • Girard, J.-Y., 1982, 'Herbrands teorem og bevisteori', Proceedings of Herbrand Symposium, Amsterdam: Nord-Holland, 29-38.
  • Herbrand, J., 1930, Recherches sur la thèorie de la dèmonstration, Dissertation, University of Paris. Engelsk oversettelse i Herbrand 1971, s. 44–202.
  • –––, 1971, Logical Writings, W. Goldfarb (red.), Cambridge, Mass.: Harvard University Press.
  • Hilbert, D., 1922, 'Neubegründung der Mathematik: Erste Mitteilung', Abhandlungen aus dem Seminar der Hamburgischen Universität, 1: 157–177, engelsk oversettelse i Mancosu, 1998, 198–214 og Ewald, 1996, 1115–1134.
  • –––, 1923, 'Die logischen Grundlagen der Mathematik', Mathematische Annalen, 88: 151–165, engelsk oversettelse i Ewald, 1996, 1134–1148.
  • Hilbert, D., Bernays, P., 1934, Grundlagen der Mathematik, Vol. 1, Berlin: Springer.
  • ––– 1939, Grundlagen der Mathematik, Vol. 2, Berlin: Springer.
  • –––, 1970, 'Grundlagen der Mathematik', Vol. 2, 2. utgave, Berlin: Springer, supplement V.
  • Hintikka, J., Kulas, J., 1985. Anaphora and Definite Describes: Two Applications of Game-Theoretical Semantics, Dordrecht: Reidel.
  • Kempson, R., Meyer Viol, W. og Gabbay, D., 2001. Dynamic Syntax: The Flow of Language Understanding, Oxford: Blackwell.
  • Kreisel, G, 1951, 'Om tolkningen av ikke-finitistiske bevis - del I', Journal of Symbolic Logic, 16: 241–267.
  • Leisenring, AC, 1969, Mathematical Logic og Hilberts Epsilon-Symbol, London: Macdonald.
  • Luckhardt, H., 1989, 'Herbrand-Analysen zweier Beweise des Satzes von Roth: Polynomiale Anzahlschranken', Journal of Symbolic Logic, 54: 234–263.
  • Maehara, S., 1955, 'Predikatberegningen med (varepsilon) - symbol', Journal of the Mathematical Society of Japan, 7: 323–344.
  • –––, 1957, 'Equality axiom on Hilbert's (varepsilon) - symbol', Journal of the Science of Science, University of Tokyo, Seksjon 1, 7: 419–435.
  • Mancosu, P. (red.), 1998, Fra Brouwer til Hilbert. Debatten om grunnlaget for matematikk på 1920-tallet, Oxford: Oxford University Press.
  • Meyer Viol, WPM, 1995a, Instantial Logic. En undersøkelse om resonnement med forekomster, Ph. D. avhandling, University of Utrecht. ILLC Dissertation Series 1995–11.
  • –––, 1995b. 'En bevisteoretisk behandling av oppgaver', Bulletin of IGPL, 3: 223–243.
  • Mints, G., 1994, 'Gentzen-type systems and Hilbert's epsilon substitution method. I ', Logic, Methodology and Philosophy of Science, IX (Uppsala, 1991), Amsterdam: Nord-Holland, 91-122.
  • –––, 1996, 'Sterk avslutning for epsilonsubstitusjonsmetoden', Journal of Symbolic Logic, 61: 1193–1205.
  • –––, 2001, 'Epsilonsubstitusjonsmetoden og kontinuiteten', i W. Sieg et al. (red.), Reflections on the Foundations of Mathematics: Essays to Honour of Solomon Feferman, Lecture Notes in Logic 15, Association for Symbolic Logic.
  • –––, 2008, 'Cut Elimination for a simple formulering of epsilon calculus', Annals of Pure and Applied Logic, 152 (1–3): 148–160.
  • –––, 2013. 'Epsilon substitution for first- and second-order predicate logic', Annals of Pure and Applied Logic, 164: 733–739.
  • –––, 2015. 'Ikke-deterministisk epsilonsubstitusjonsmetode for PA og ID (_ 1)', i: Kahle, R., Rathjen, M. (Eds.), Gentzen's Centenary: The Quest for Consistency. Berlin: Springer, s. 479–500.
  • Mints, G., Tupailo, S., 1999, 'Epsilon-substitusjonsmetode for det forsterkede språket og (Delta ^ {1} _1) - forståelsesregel', i A. Cantini et al. (red.), Logic and Foundations of Mathematics (Florence, 1995), Dordrecht: Kluwer, 107–130.
  • Mints, G., Tupailo, S., Buchholz, W., 1996, 'Epsilon substitution method for elementary analysis', Archive for Mathematical Logic, 35: 103–130.
  • Moser, G., 2006, 'Ackermanns substitusjonsmetode (remikset)', Annals of Pure and Applied Logic, 142 (1–3): 1–18.
  • Moser, G. og R. Zach, 2006, 'The epsilon calculus and Herbrand complexity', Studia Logica, 82 (1): 133–155.
  • Mostowski, A., 1963. 'Hilbert-epsilon-funksjonen i mange verdsatte logikker', Acta Philosophica Fennica, 16: 169–188.
  • Neale, S., 1990, Beskrivelser, Cambridge, MA: MIT Press.
  • Reinhart, T., 1992. 'Wh-in-situ: Et tilsynelatende paradoks'. I: P. Dekker og M. Stokhof (red.). Fortsettelser av det åttende Amsterdam-kollokviet, 17. til 20. desember 1991. ILLC. University of Amsterdam, 483–491.
  • –––, 1997. 'Kvantifiseringsomfang: Hvordan arbeidskraft er delt mellom QR og valgfunksjoner'. Lingvistikk og filosofi, 20: 335–397.
  • Shirai, K., 1971, 'Intuitionistic predicate calculus with (varepsilon) - symbol', Annals of the Japan Association for Philosophy of Science 4: 49–67.
  • Sieg, W., 1991, 'Herbrand analyser', Archive for Mathematical Logic, 30: 409–441.
  • Slater, BH, 1986, 'Pronomen av e-type og (varepsilon) - termer', Canadian Journal of Philosophy, 16: 27–38.
  • –––, 1988, 'Hilbertian reference', Noûs, 22: 283–97.
  • –––, 1994, 'The epsilon calculus' problematic ', Philosophical Papers, 23: 217–42.
  • –––, 2000, 'Kvantifiserer / variabel-bindende', Linguistics and Philosophy, 23: 309–21.
  • Tait, WW, 1960, 'Substitusjonsmetoden.' Journal of Symbolic Logic, 30: 175–192.
  • –––, 1965, 'Funksjoner definert av transfinite rekursjon,' Journal of Symbolic Logic, 30: 155–174.
  • –––, 2010. 'Substitusjonsmetoden revidert.' i: S. Feferman og W. Sieg (red.), Bevis, kategorier og beregninger: Essays til ære for Grigori Mints, London: College Publications, s. 131–14.
  • von Heusinger, K., 1994, Review of Neale (1990). Lingvistikk 32: 378–385.
  • –––, 1997. 'Definite beskrivelser og valgfunksjoner'. I: S. Akama (red.). Logic, Language and Computation, Dordrecht: Kluwer, 61–91.
  • –––, 2000, 'The Reference of Indefinites', i von Heusinger og Egli, (2000), 265–284.
  • –––, 2004, 'Choice features and the anafhoric semantics of definite NPs', Research in Language and Computation, 2: 309–329.
  • von Heusinger, K., Egli, U., (red.), 2000. Reference and Anafhoric Relations, Dordrecht: Kluwer.
  • –––, 2000a. 'Introduction: Reference and the Semantics of Anaphora', i von Heusinger og Egli (2000), 1–13.
  • von Heusinger, K., Kempson, R., (red.), 2004. Choice Functions in Semantics, Special Issue of Research on Language and Computation 2 (3).
  • von Neumann, J., 1927, 'Zur Hilbertschen Beweistheorie', Mathematische Zeitschrift, 26: 1–46.
  • Wang, H., 1963, A Survey of Mathematical Logic, Peking: Science Press.
  • Winter, Y., 1997. 'Choice features and the scopal semantics of indefinites'. Lingvistikk og filosofi, 20: 399–467.
  • Yasuhara, M., 1982, 'Cut elimination in (varepsilon) - calculi', Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 28: 311–316.
  • Zach, R., 2003, 'Utøvelsen av finitisme. Epsilon-beregning og konsistensbevis i Hilbert's Program ', Synthese, 137: 211–259.
  • –––, 2004. 'Hilberts “Verunglückter Beweis”, den første epsilonsteoremet, og konsistensbevis. Logikkens historie og filosofi, 25, 79–94.
  • –––, 2017. 'Semantics and proof theory of the epsilon calculus', i: Ghosh, S., Prasad, S. (Eds.), Logic and Its Applications. ICLA 2017, LNCS. Springer, Berlin, Heidelberg, s. 27–47.

Akademiske verktøy

september mann ikon
september mann ikon
Hvordan sitere denne oppføringen.
september mann ikon
september mann ikon
Forhåndsvis PDF-versjonen av denne oppføringen hos Friends of the SEP Society.
inpho-ikonet
inpho-ikonet
Slå opp dette emnet på Internet Philosophy Ontology Project (InPhO).
phil papirer ikon
phil papirer ikon
Forbedret bibliografi for denne oppføringen på PhilPapers, med lenker til databasen.

Andre internettressurser

Epsilon Calculi av B. Hartley Slater (Internet Encyclopedia of Philosophy)

Kontakt forfatterne for ytterligere forslag.