Logikk Og Spill

Innholdsfortegnelse:

Logikk Og Spill
Logikk Og Spill

Video: Logikk Og Spill

Video: Logikk Og Spill
Video: Karisma logikk i spill 2024, Mars
Anonim

Inngangsnavigasjon

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

Logikk og spill

Først publisert fredag 27. juli 2001; substansiell revisjon fre 16. august 2019

Spill mellom to spillere, av den typen der en spiller vinner og en taper, ble et kjent verktøy i mange grener av logikk i løpet av andre halvdel av det tjuende århundre. Viktige eksempler er semantiske spill som brukes til å definere sannhet, frem og tilbake spill som brukes til å sammenligne strukturer og dialogspill for å uttrykke (og kanskje forklare) formelle bevis.

  • 1. Spill i logikkens historie
  • 2. Logiske spill
  • 3. Semantiske spill for klassisk logikk
  • 4. Semantiske spill med ufullkommen informasjon
  • 5. Semantiske spill for annen logikk
  • 6. Back-and-Forth-spill
  • 7. Andre modellteoretiske spill

    • 7.1 Tvinge spill
    • 7.2 Klipp ut og velg spill
    • 7.3 Spill på treet til to etterfølgerfunksjoner
  • 8. Games of Dialogue, Communication and Proof
  • Bibliografi

    • Spill i logikkens historie
    • Spill for undervisningslogikk
    • Logiske spill
    • Semantiske spill for klassisk logikk
    • Semantiske spill med ufullkommen informasjon
    • Semantiske spill for annen logikk
    • Back-and-Forth-spill
    • Andre modellteoretiske spill
    • Games of Dialogue, Communication and Proof
  • Akademiske verktøy
  • Andre internettressurser
  • Relaterte oppføringer

1. Spill i logikkens historie

Koblingene mellom logikk og spill går langt igjen. Hvis man tenker på en debatt som et slags spill, hadde Aristoteles allerede opprettet forbindelsen; hans forfatterskap om syllogisme er tett sammenvevd i hans studie av målene og reglene for debatt. Aristoteles synspunkt overlevde inn i det vanlige middelaldernavnet for logikk: dialektikk. I midten av det tjuende århundre gjenopplivet Charles Hamblin koblingen mellom dialog og reglene for god resonnement, rett etter at Paul Lorenzen hadde koblet dialog til konstruktive grunnlegger av logikk.

Det er nære koblinger mellom spill og undervisning. Forfattere gjennom hele middelalderen snakker om dialoger som en måte å 'undervise' eller 'teste' bruken av lydresonnement. Vi har minst to lærebøker med logikk fra begynnelsen av det sekstende århundre som presenterer det som et spill for en individuell student, og Lewis Carrolls The Game of Logic (1887) er et annet eksempel i samme sjanger. Det er nok av moderne eksempler også, selv om det sannsynligvis ikke har vært nok kontinuitet til å rettferdiggjøre å snakke om en tradisjon for å lære logikk ved spill.

Matematisk spillteori ble grunnlagt på begynnelsen av det tjuende århundre. Selv om ingen matematiske koblinger med logikk dukket opp før på 1950-tallet, er det påfallende hvor mange av de tidlige pionerene innen spillteori også er kjent for sine bidrag til logikk: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo og andre. I 1953 skapte David Gale og Frank Stewart fruktbare forbindelser mellom settteori og spill. Like etterpå foreslo Leon Henkin en måte å bruke spill for å gi semantikk for infinitære språk.

Første halvdel av det tjuende århundre var en epoke med økende strenghet og profesjonalitet i logikken, og for de fleste logikere i den perioden ville bruk av spill i logikk antagelig virket useriøst. Intuisjonisten LEJ Brouwer uttrykte denne holdningen da han beskyldte sine motstandere for å få matematikk til å «utarte seg til et spill» (som David Hilbert siterte ham i 1927, sitert i van Heijenoort 1967). Hermann Weyl (sitert i Mancosu 1998) brukte forestillingen om spill for å forklare Hilberts metamatematikk: matematiske bevis fortsetter som skuespill i et meningsløst spill, men vi kan stå utenfor spillet og stille meningsfulle spørsmål om det. Wittgensteins språkspill vakte liten respons fra logikerne. Men i andre halvdel av århundret flyttet tyngdepunktet for logisk forskning fra fundamenter til teknikker,og fra omtrent 1960 ble spill brukt oftere og oftere i logiske papirer.

Ved begynnelsen av det tjueførste århundre hadde det blitt bred enighet om at spill og logikk går sammen. Resultatet var en enorm spredning av nye kombinasjoner av logikk og spill, spesielt i områder der logikk blir brukt. Mange av disse nye utviklingene kom opprinnelig fra arbeid i ren logikk, selv om de i dag følger sine egne agendaer. Et slikt område er argumentasjonsteori, der spill danner et verktøy for å analysere strukturen i debatter.

Nedenfor vil vi konsentrere oss om de spillene som er mest knyttet til ren logikk.

2. Logiske spill

Fra spillteoriens synspunkt er de viktigste spillene som logikere studerer ikke i det hele tatt typiske. De involverer normalt bare to spillere, de har ofte uendelig lengde, de eneste resultatene er å vinne og tape, og ingen sannsynligheter er knyttet til handlinger eller utfall. De viktigste elementene i et logisk spill er som følger.

Det er to spillere. Generelt kan vi kalle dem (forall) og (exist). Uttalene 'Abelard' og 'Eloise' går tilbake til midten av 1980-tallet og fikser spillerne som mannlige og kvinnelige, noe som gjør referansen enklere: hennes trekk, hans trekk. Andre navn er vanlig å bruke for spillerne i bestemte typer logisk spill.

Spillerne spiller ved å velge elementer i et sett (Omega), kalt spillets domene. Når de velger, bygger de opp en sekvens

[a_0, a_1, a_2, / ldots)

av elementer av (Omega). Uendelige sekvenser av elementer i (Omega) kalles skuespill. Endelige sekvenser av elementer i (Omega) kalles posisjoner; de tar opp hvor et skuespill kan ha kommet til innen en viss tid. En funksjon (tau) (turnfunksjonen eller spillerfunksjonen) tar hver posisjon (mathbf {a}) til enten (exist) eller (forall); hvis (tau (mathbf {a}) = / eksisterer), betyr dette at når spillet har nådd (mathbf {a}), spiller (exist) tar neste valg (og på samme måte med (forall)). Spillreglene definerer to sett (W _ { forall}) og (W _ { exist}) bestående av posisjoner og spill, med følgende egenskaper: hvis en posisjon (mathbf {a}) er i (W _ { forall}) så er det også alle spill eller lengre posisjoner som begynner med (mathbf {a}) (og på samme måte med (W _ { eksisterer}));og ingen spill er i både (W _ { forall}) og (W _ { exist}). Vi sier at spilleren (forall) vinner et spill (mathbf {b}), og at (mathbf {b}) er en gevinst for (forall), hvis (mathbf {b}) er i (W _ { forall}); Hvis noen posisjon (mathbf {a}) som er et innledende segment av (mathbf {b}) er i (W _ { forall}), så sier vi den spilleren (forall) vinner allerede på (mathbf {a}). (Og på samme måte med (exist) og (W _ { exist}).) Så for å oppsummere, er et logisk spill en 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { exist})) med egenskapene som nettopp er beskrevet.så sier vi at spilleren (forall) vinner allerede på (mathbf {a}). (Og på samme måte med (exist) og (W _ { exist}).) Så for å oppsummere, er et logisk spill en 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { exist})) med egenskapene som nettopp er beskrevet.så sier vi at spilleren (forall) vinner allerede på (mathbf {a}). (Og på samme måte med (exist) og (W _ { exist}).) Så for å oppsummere, er et logisk spill en 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { exist})) med egenskapene som nettopp er beskrevet.

Vi sier at et logisk spill er totalt hvis hvert spill er i enten (W _ { forall}) eller (W _ { exist}), slik at det ikke blir uavgjort. Med mindre man gjør et eksplisitt unntak, antas alltid at logiske spill er totale. (Ikke forveksle å være total med den mye sterkere egenskapen av å være bestemt - se nedenfor.)

Det er bare for matematisk bekvemmelighet at definisjonen ovenfor forventer at spillet fortsetter til uendelig selv når en spiller har vunnet i en endelig stilling; det er ingen interesse for noe som skjer etter at en spiller har vunnet. Mange logiske spill har den egenskapen at i hvert spill har en av spillerne allerede vunnet på en endelig stilling; spill av denne typen sies å være velbegrunnede. En enda sterkere betingelse er at det er et endelig antall (n) slik at en av spillerne i hvert spill allerede har vunnet den (n) - th-stillingen; i dette tilfellet sier vi at spillet har endelig lengde.

En strategi for en spiller er et sett med regler som beskriver nøyaktig hvordan den spilleren skal velge, avhengig av hvordan de to spillerne har valgt ved tidligere trekk. Matematisk består en strategi for (forall) av en funksjon som tar hver posisjon (mathbf {a}) med (tau (mathbf {a}) = / forall) til et element (b) av (Omega); vi tenker på det som en instruksjon til (forall) å velge (b) når spillet har nådd posisjonen (mathbf {a}). (På samme måte med en strategi for (eksisterer).) En strategi for en spiller sies å vinne hvis den spilleren vinner hvert spill der han eller hun bruker strategien, uavhengig av hva den andre spilleren gjør. På det meste har en av spillerne en vinnerstrategi (siden ellers kunne spillerne spille sine vinnerstrategier mot hverandre, og begge ville vinne,motsier at (W _ { forall}) og (W _ { eksisterer}) ikke har noen avspillinger til felles). Noen ganger møter man situasjoner der det ser ut til at to spillere har vinnerstrategier (for eksempel i tvangsspillene nedenfor), men nærmere inspeksjon viser at de to spillerne faktisk spiller forskjellige spill.

Et spill sies å være bestemt om en eller annen av spillerne har en vinnende strategi. Det er mange eksempler på spill som ikke er bestemt, som Gale og Stewart viste i 1953 ved bruk av det valgte aksiomet. Denne oppdagelsen førte til viktige anvendelser av forestillingen om determinitet i grunnlaget for settteorien (se oppføring om store kardinaler og determinitet). Gale og Stewart beviste også en viktig teorem som bærer navnet sitt: Hvert velbegrunnet spill er bestemt. Det følger at hvert spill med begrenset lengde er bestemt - et faktum som allerede er kjent for Zermelo i 1913. (En mer presis uttalelse av Gale-Stewart-teoremet er dette. Et spill (G) sies å være stengt hvis (eksisterer) vinner hvert spill av (G) der hun ikke allerede har tapt på noen endelig stilling. Teoremet sier at hvert lukkede spill er bestemt. Beviset på teoremet er i utgangspunktet enkelt: La oss kalle en stilling som vinner for (forall) hvis han har en vinnerstrategi som starter fra denne posisjonen. Anta at (forall) ikke har en vinnende strategi i spillet, det vil si at i begynnelsen vinner ikke stillingen for (forall). Hvis det første trekket er et trekk fra (forall), er stillingen fortsatt ikke å vinne for ham etter hans trekk. Hvis det første trekket er et trekk fra (eksisterer), må hun ha et trekk hvor stillingen fremdeles ikke vinner for (forall), for ellers ville den forrige stillingen vunnet for (forall). Spillet foregår på denne måten uendelig mange trekk gjennom posisjoner som ikke vinner for (forall). Fordi spillet er lukket, vinner (exist).)Anta at (forall) ikke har en vinnende strategi i spillet, det vil si at i begynnelsen vinner ikke stillingen for (forall). Hvis det første trekket er et trekk fra (forall), er stillingen fortsatt ikke å vinne for ham etter hans trekk. Hvis det første trekket er et trekk fra (eksisterer), må hun ha et trekk hvor stillingen fremdeles ikke vinner for (forall), for ellers ville den forrige stillingen vunnet for (forall). Spillet foregår på denne måten uendelig mange trekk gjennom posisjoner som ikke vinner for (forall). Fordi spillet er lukket, vinner (exist).)Anta at (forall) ikke har en vinnende strategi i spillet, det vil si at i begynnelsen vinner ikke stillingen for (forall). Hvis det første trekket er et trekk fra (forall), er stillingen fortsatt ikke å vinne for ham etter hans trekk. Hvis det første trekket er et trekk fra (eksisterer), må hun ha et trekk hvor stillingen fremdeles ikke vinner for (forall), for ellers ville den forrige stillingen vunnet for (forall). Spillet foregår på denne måten uendelig mange trekk gjennom posisjoner som ikke vinner for (forall). Fordi spillet er lukket, vinner (exist).)Hvis det første trekket er et trekk fra (eksisterer), må hun ha et trekk hvor stillingen fremdeles ikke vinner for (forall), for ellers ville den forrige stillingen vunnet for (forall). Spillet foregår på denne måten uendelig mange trekk gjennom posisjoner som ikke vinner for (forall). Fordi spillet er lukket, vinner (exist).)Hvis det første trekket er et trekk fra (eksisterer), må hun ha et trekk hvor stillingen fremdeles ikke vinner for (forall), for ellers ville den forrige stillingen vunnet for (forall). Spillet foregår på denne måten uendelig mange trekk gjennom posisjoner som ikke vinner for (forall). Fordi spillet er lukket, vinner (exist).)

Akkurat som i klassisk spillteori fungerer definisjonen av logiske spill ovenfor som en kleshest som vi kan henge andre konsepter på. For eksempel er det vanlig å ha noen lover som beskriver hvilke elementer av (Omega) som er tilgjengelige for en spiller å velge i et bestemt trekk. Strengt tatt er denne avgrensningen unødvendig, fordi vinnerstrategiene ikke påvirkes hvis vi i stedet vedtar at en spiller som bryter loven, taper umiddelbart; men for mange spill virker denne måten å se på dem unaturlig. Nedenfor ser vi noen andre ekstrafunksjoner som kan legges til spill.

Definisjonene av spill og strategi ovenfor var rent matematiske. Så de la ut det som trolig er den viktigste funksjonen i spill, som er at folk spiller dem (i det minste metaforisk). Spillerne har som mål å vinne, og ved å studere strategiene som er åpne for dem, studerer vi hvilken atferd som er rasjonell for en person med et bestemt mål. I de fleste spill er det flere spillere, så vi kan studere hva som er en rasjonell respons på andres oppførsel. Ved å begrense spillernes trekk og mulige strategier, kan vi studere begrenset rasjonalitet, der en agent må ta rasjonelle beslutninger under forhold med begrenset informasjon, minne eller tid.

Kort sagt brukes spill til å modellere rasjonalitet og begrenset rasjonalitet. Dette er uavhengig av hvilken som helst forbindelse med logikk. Men noen logikker ble designet for å studere aspekter ved rasjonell oppførsel, og de siste årene har det blitt stadig mer vanlig å knytte disse logikkene til passende spill. Se avsnitt 5 ('Semantiske spill for andre logikker') og bibliografien.

Men inntil nylig var logiske spill forbundet med rasjonell oppførsel på en ganske annen måte. På overflaten hadde den aktuelle logikken ingen direkte forbindelse med atferd. Men logikere og matematikere la merke til at noen ideer kunne gjøres mer intuitive hvis de var knyttet til mulige mål. For eksempel i mange applikasjoner av logiske spill, er den sentrale forestillingen den om en vinnende strategi for spilleren (eksisterer). Ofte viser disse strategiene (eller deres eksistens) seg til å være likeverdige med noe av logisk betydning som kunne vært definert uten å bruke spill - for eksempel et bevis. Men spill føles for å gi en bedre definisjon fordi de bokstavelig talt gir litt motivasjon: (exist) prøver å vinne.

Dette reiser et spørsmål som ikke er av stor interesse matematisk, men det bør angå filosofer som bruker logiske spill. Hvis vi vil at (exist) 's motivasjon i et spill (G) skal ha noen forklarende verdi, må vi forstå hva som oppnås hvis (exist) vinner. Spesielt bør vi være i stand til å fortelle en realistisk historie om en situasjon der noen agent kalt (exist) prøver å gjøre noe forståelig, og å gjøre det er det samme som å vinne i spillet. Som Richard Dawkins sa, og reiste det tilsvarende spørsmålet for evolusjonsspillene til Maynard Smith,

Hele hensikten med søket vårt … er å oppdage en passende skuespiller som kan spille den ledende rollen i metaforene våre. Vi… vil si: 'Det er til beste for …'. Vår søken i dette kapittelet er etter den rette måten å fullføre den setningen. (The Extended Phenotype, Oxford University Press, Oxford 1982, side 91.)

For fremtidig referanse, la oss kalle dette Dawkins-spørsmålet. I mange logiske spill viser det seg å være vanskeligere å svare på enn pionerene i disse spillene. (Marion 2009 diskuterer Dawkins-spørsmålet videre.)

3. Semantiske spill for klassisk logikk

På begynnelsen av 1930-tallet foreslo Alfred Tarski en definisjon av sannhet. Hans definisjon besto av en nødvendig og tilstrekkelig betingelse for at en setning på språket til en typisk formell teori skulle være sann; hans nødvendige og tilstrekkelige betingelse brukte bare forestillinger fra syntaks og settteori, sammen med de primitive forestillingene om den aktuelle formelle teorien. Faktisk definerte Tarski den mer generelle relasjonen 'formel (phi (x_1, / ldots, x_n)) er sant for elementene (a_1, / ldots, a_n)' sannhet om en setning er det spesielle tilfellet hvor (n = 0). For eksempel spørsmålet om

'For alle (x) er det (y) slik at R ((x, y))' er sant

reduserer spørsmålet om følgende gjelder:

For hvert objekt (a) er setningen 'Det er (y) slik at R ((a, y))' er sann.

Dette reduserer igjen til:

For hvert objekt (a) er det et objekt (b) slik at setningen 'R ((a, b))' er sann.

I dette eksemplet er det så langt Tarskis sannhetsdefinisjon vil ta oss.

På slutten av 1950-tallet la Leon Henkin merke til at vi intuitivt kan forstå noen setninger som ikke kan håndteres etter Tarskis definisjon. Ta for eksempel den uendelig lange setningen

For alle (x_0) er det (y_0) slik at for alle (x_1) er det (y_1) slik at … R ((x_0, y_0, x_1, y_1, / ldots)).

Tarskis tilnærming mislykkes fordi strengen av kvantifiserere i begynnelsen er uendelig, og vi vil aldri komme til en slutt med å fjerne dem. I stedet, antydet Henkin, bør vi vurdere spillet der en person (forall) velger et objekt (a_0) for (x_0), deretter velger en annen person (exist) et objekt (b_0) for (y_0), deretter (forall) velger (a_1) for (x_1, / exist) velger (b_1) for (y_1) og så videre. Et spill av dette spillet er en gevinst for (exist) hvis og bare hvis den uendelige atomsetningen

(R (a_0, b_0, a_1, b_1, / ldots))

er sant. Den opprinnelige setningen er sann hvis og bare hvis spilleren (eksisterer) har en vinnende strategi for dette spillet. Strengt tatt brukte Henkin spillet bare som en metafor, og sannhetsbetingelsen som han foreslo var at den skolemiserte versjonen av setningen er sann, dvs. at det er funksjoner (f_0, f_1, / ldots) slik at for alle valg av (a_0, a_1, a_2) osv. vi har

(R (a_0, f_0 (a_0), a_1, f_1 (a_0, a_1), a_2, f_2 (a_0, a_1, a_2), / ldots).)

Men denne tilstanden oversettes umiddelbart til spillets språk; Skolem-funksjonene (f_0) osv. definerer en vinnende strategi for (eksisterer), og forteller henne hvordan hun skal velge i lys av tidligere valg av (forall). (Det kom på et tidspunkt senere at CS Peirce allerede hadde foreslått å forklare forskjellen mellom 'alle' og 'noen' med tanke på hvem som velger objektet; for eksempel i sitt andre Cambridge Conference-foredrag fra 1898.)

Rett etter Henkins arbeid la Jaakko Hintikka til at den samme ideen gjelder konjunksjoner og disjunksjoner. Vi kan se på en konjunksjon '(phi / kil' / psi) 'som et universelt kvantifisert utsagn som uttrykker' Hver setning (phi, / psi) holder '), så det skal være for spilleren (forall) for å velge en av setningene. Som Hintikka sa det, for å spille spillet (G (phi / kile / psi), velger / forall) om spillet skal fortsette som (G (phi)) eller som (G (psi)). På samme måte blir disjunksjoner eksistensielt kvantifiserte utsagn om sett med setninger, og de markerer trekk der spilleren (exist) velger hvordan spillet skal gå frem. For å bringe kvantifiserere i samme stil foreslo han at spillet (G (forall x / phi (x))) fortsetter således: spiller (forall) velger et objekt og gir et navn (a) for det,og spillet fortsetter som (G (phi (a))). (Og på samme måte med eksistensielle kvantifiserere, bortsett fra at (exist) velger.) Hintikka kom også med et genialt forslag for å innføre negasjon. Hvert spill G har et dobbelt spill som er det samme som G bortsett fra at spillerne (forall) og (exist) er transponert i både spillereglene og reglene for å vinne. Spillet (G (neg / phi)) er det dobbelte av (G (phi)).

Man kan bevise at for enhver førsteordens setning (phi), tolket i en fast struktur (A), har spiller (exist) en vinnende strategi for Hintikka's spill (G (phi)) hvis og bare hvis (phi) er sant i (A) i betydningen Tarski. To trekk ved dette beviset er interessante. For det første, hvis (phi) er en førsteordens setning, så har spillet (G (phi)) endelig lengde, og derfor forteller teoremet Gale-Stewart at det er bestemt. Vi slutter oss til at (exist) har en vinnende strategi i nøyaktig en av (G (phi)) og dens doble; så hun har en vinnende strategi i (G (neg / phi)) hvis og bare hvis hun ikke har en i (G (phi)). Dette tar seg av negasjon. Og for det andre: Hvis (exist) har en vinnende strategi for hvert spill (G (phi (a))), så etter å ha valgt en slik strategi (f_a) for hvert (a),hun kan strenge dem sammen til en enkelt vinnende strategi for (G (forall x / phi (x))) (nemlig 'Vent og se hvilket element (a / forall) velger, og spill deretter (f_a) '). Dette tar vare på klausulen for universelle kvantifiserere; men argumentet bruker aksiomet til valget, og det er faktisk ikke vanskelig å se at utsagnet om at Hintikka og Tarskis definisjoner av sannhet er likeverdige i seg selv tilsvarer det aksiomet som valget er (gitt de andre aksiomene i Zermelo-Fraenkel-setteorien).og faktisk er det ikke vanskelig å se at utsagnet om at Hintikkas og Tarskis definisjoner av sannhet er likeverdige tilsvarer i seg selv det valgte aksiomet (gitt de andre aksiomene i Zermelo-Fraenkel-settteorien).og faktisk er det ikke vanskelig å se at utsagnet om at Hintikkas og Tarskis definisjoner av sannhet er likeverdige tilsvarer i seg selv det valgte aksiomet (gitt de andre aksiomene i Zermelo-Fraenkel-settteorien).

Det er rart at vi her har to teorier om når en setning er sann, og teoriene er ikke likeverdige hvis valgets aksiom mislykkes. Faktisk er grunnen ikke veldig dyp. Valgets aksiom er ikke nødvendig fordi Hintikka-definisjonen bruker spill, men fordi den forutsetter at strategier er deterministiske, dvs. at de er enkeltverdige funksjoner som gir brukeren ikke noe valg av alternativer. En mer naturlig måte å oversette Tarski-definisjonen til spilltermer på er å bruke nondeterministiske strategier, noen ganger kalt quasistrategies (se Kolaitis 1985 for detaljer). (Imidlertid insisterer Hintikka 1996 på at riktig forklaring av 'sant' er den som bruker deterministiske strategier, og at dette faktum berettiger valgets aksiom.)

Datamaskinimplementeringer av disse spillene fra Hintikka viste seg å være en veldig effektiv måte å lære betydningene av førsteordens setninger. En slik pakke ble designet av Jon Barwise og John Etchemendy på Stanford, kalt 'Tarski's World'. Uavhengig laget et annet team ved Universitetet i Omsk en russisk versjon for bruk på skoler for begavede barn.

I den publiserte versjonen av John Locke-forelesningene hans i Oxford reiste Hintikka i 1973 Dawkins-spørsmålet (se over) for disse spillene. Svaret hans var at man skulle se til Wittgensteins språkspill, og språkspillene for å forstå kvantifiserere er de som dreier seg om å søke og finne. I de tilsvarende logiske spillene bør man tenke på (exist) som meg selv og (forall) som en fiendtlig natur som aldri kan stole på å presentere det objektet jeg ønsker; så for å være sikker på å finne det, trenger jeg en vinnende strategi. Denne historien var aldri veldig overbevisende; motivasjonen til naturen er irrelevant, og ingenting i det logiske spillet tilsvarer det å søke. I ettertid er det litt skuffende at ingen tok seg bryet med å lete etter en bedre historie. Det kan være mer nyttig å tenke på en vinnende strategi for (eksisterer) i (G (phi)) som et slags bevis (i et passende infinitærsystem) at (phi) er sant.

Senere utvidet Jaakko Hintikka ideene til dette avsnittet i to retninger, nemlig til semantikk for naturlig språk og til ufullkommen informasjon (se neste avsnitt). Navnet Game-Theoretic Semantics, GTS for kort, har kommet til å brukes for å dekke begge disse utvidelsene.

Spillene som er beskrevet i dette avsnittet tilpasser seg nesten trivielt til mangesortert logikk: for eksempel kvantifisereren (forall x _ { sigma}), der (x _ { sigma}) er en variabel av sortering (sigma), er en instruksjon for spilleren (forall) om å velge et element av sortering (sigma). Dette gir oss umiddelbart de tilsvarende spillene for annenordens logikk, hvis vi tenker på elementene i en struktur som en sortering, settene med elementer som en andre sortering, de binære relasjonene som en tredje og så videre. Det følger at vi ganske rutinemessig har spilleregler for de fleste generaliserte kvantifiserere; vi kan finne dem ved først å oversette de generaliserte kvantifisererne til annenordens logikk.

4. Semantiske spill med ufullkommen informasjon

I dette og neste avsnitt ser vi på noen tilpasninger av de semantiske spillene fra forrige seksjon til andre logikker. I vårt første eksempel ble logikken (den uavhengighetsvennlige logikken til Hintikka og Sandu 1997, eller mer kort IF-logikk) opprettet for å passe til spillet. Se oppføringen om uavhengighetsvennlig logikk og Mann, Sandu og Sevenster 2011 for utfyllende beretninger om denne logikken.

Spillene her er de samme som i forrige seksjon, bortsett fra at vi dropper forutsetningen om at hver spiller kjenner forrige historie. Vi kan for eksempel kreve at en spiller tar et valg uten å vite hvilke valg den andre spilleren har gjort ved visse tidligere trekk. Den klassiske måten å håndtere dette innen spillteori er å begrense spillernes strategier. For eksempel kan vi kreve at strategifunksjonen som forteller (eksisterer) hva vi skal gjøre på et bestemt trinn, er en funksjon der domenet er familien til mulige valg av (forall) på bare hans første og andre trekk; dette er en måte å uttrykke at (exist) ikke vet hvordan (forall) valgte ved sitt tredje og senere trekk. Spill med denne typen begrensninger på strategifunksjonene sies å være av ufullkommen informasjon,i motsetning til spill med perfekt informasjon i forrige seksjon.

For å lage en logikk som passer til disse spillene, bruker vi det samme førsteordens språket som i forrige seksjon, bortsett fra at det legges til en notasjon til noen kvantifiserere (og muligens også noen tilkoblinger), for å vise at Skolem fungerer for disse kvantifisererne (eller tilkoblinger) er uavhengige av visse variabler. For eksempel setningen

[(forall x) (eksisterer y / / forall x) R (x, y))

leses som: "For hver (x) er det (y), ikke avhengig av (x), slik at (R (x, y))".

Det er tre viktige kommentarer å gjøre om skillet mellom perfekt og ufullkommen informasjon. Den første er at Gale-Stewart-teoremet kun inneholder spill for perfekt informasjon. Anta at for eksempel at (forall) og (exist) spiller følgende spill. Først velger (forall) et av tallene 0 og 1. Da velger (exist) et av disse to tallene. Spiller (eksisterer) vinner hvis de to valgte numrene er de samme, og ellers spiller (forall) vinner. Vi krever at (exist), når hun tar sitt valg, ikke vet hva (forall) valgte; så en Skolem-funksjon for henne vil være en konstant. (Dette spillet tilsvarer IF-setningen ovenfor med (R) lest som likhet, i en struktur med et domene som består av 0 og 1.) Det er tydelig at spilleren (eksisterer) ikke har en konstant vinnerstrategi,og også at spilleren (forall) ikke har en vinnende strategi i det hele tatt. Så dette spillet er ubestemt, selv om lengden bare er 2.

En følge er at Hintikkas begrunnelse for å lese negasjon som dualisering ('spillere bytter plass'), i sine spill for førsteordens logikk, ikke overføres til IF-logikk. Hintikkas svar har vært at dualisering var den riktige intuitive betydningen av negasjon selv i første-ordens saken, så ingen begrunnelse er nødvendig.

Den andre kommentaren er at allerede i spill med perfekt informasjon kan det skje at vinnende strategier ikke bruker all tilgjengelig informasjon. For eksempel i et spill med perfekt informasjon, hvis spilleren (eksisterer) har en vinnende strategi, så har hun også en vinnerstrategi der strategifunksjonene bare er avhengig av de tidligere valgene til (forall). Dette fordi hun kan rekonstruere sine egne tidligere trekk ved å bruke sine tidligere strategifunksjoner.

Da Hintikka brukte Skolem-funksjoner som strategier i spillene sine for førsteordens logikk, gjorde han at strategiene for en spiller bare var avhengig av de tidligere spillerne fra den andre spilleren. (En Skolem-funksjon for (eksisterer) avhenger bare av universelt kvantifiserte variabler.) Fordi spillene var spill med perfekt informasjon, var det ikke noe tap i dette, av den andre kommentaren ovenfor. Men da han flyttet til IF-logikk, gjorde virkelig kravet om at strategier kun avhenger av trekk fra den andre spilleren. Hodges 1997 viste dette ved å revidere notasjonen, slik at for eksempel ((exist y / x)) betyr: “Det er (y) uavhengig av (x), uavhengig av hvilken spiller som valgte (x)”.

Vurder nå setningen

[(alt x) (eksisterer z) (eksisterer y / x) (x = y),)

spilles igjen på en struktur med to elementer 0 og 1. Spilleren (eksisterer) kan vinne som følger. For (z) velger hun det samme som spiller (forall) valgte for (x); deretter for (y) velger hun det samme som hun valgte for (z). Denne vinnende strategien fungerer bare fordi (eksisterer) i dette spillet kan referere til hennes egne tidligere valg. Hun ville ikke ha noen vinnerstrategi hvis den tredje kvantifisereren var ((exist y / xz)), igjen fordi enhver Skolem-funksjon for denne kvantifisereren måtte være konstant. Måten (exist) formidler informasjon til seg selv ved å henvise til hennes forrige valg er et eksempel på signaliseringsfenomenet. John von Neumann og Oskar Morgenstern illustrerte det med eksemplet Bridge, hvor en enkelt spiller består av to partnere som må dele informasjon ved å bruke sine offentlige trekk for å signalisere til hverandre.

Den tredje kommentaren er at det er en dislokasjon mellom den intuitive ideen om ufullkommen informasjon og den teoretiske definisjonen av den når det gjelder strategier. Intuitivt er ufullkommen informasjon et faktum om omstendighetene spillet spilles i, ikke om strategiene. Dette er en veldig vanskelig sak, og det fortsetter å føre til misforståelser om IF og lignende logikk. Ta for eksempel setningen

[(eksisterer x) (eksisterer y / x) (x = y),)

igjen spilt på en struktur med elementene 0 og 1. Intuitivt kan man tro at hvis (exist) ikke får lov til å huske på den andre kvantifisereren hva hun valgte ved den første, så kan hun knapt ha en vinnende strategi. Men faktisk har hun det veldig enkelt: 'Velg alltid 0'!

Sammenlignet med førsteordens logikk, mangler IF-logikk en komponent som spillsemantikken ikke vil levere. Spillets semantikk forteller oss når en setning er sann i en struktur. Men hvis vi tar en formel med (n) gratis variabler, hva uttrykker formelen om den ordnede (n) - tuplene til elementer i strukturen? I førsteordens logikk ville den definere et sett med dem, dvs. et (n) - ary forhold til strukturen; Tarski-sannhetsdefinisjonen forklarer hvordan. Er det en lignende definisjon for vilkårlige formler av IF-logikk? Det viser seg at det er en for den litt forskjellige logikken introdusert av Hodges 1997, og den fører til en Tarski-stil sannhetsdefinisjon for språket i den logikken. Med en liten justering kan denne sannhetsdefinisjonen gjøres for å passe til IF-logikk også. Men for begge disse nye logikkene er det en fangst:i stedet for å si når en tildeling av elementer til frie variabler gjør en formel sann, sier vi når et sett med tildelinger av elementer til frie variabler gjør formelen sann. Väänänen 2007 gjorde denne ideen til grunnlaget for en rekke nye logikker for å studere forestillingen om avhengighet (se oppføring om avhengighetslogikk). I disse logikkene er semantikken definert uten spill, selv om den originale inspirasjonen kommer fra arbeidet til Hintikka og Sandu.

I Väänänens logikk er det lett å se hvorfor man trenger oppdragssett. Han har en atomformel som uttrykker '(x) er avhengig av (y)'. Hvordan kan vi tolke dette i en struktur, for eksempel strukturen til naturlige tall? Det er overhode ikke noe fornuftig å spørre om 8 er avhengig av 37. Men hvis vi har et sett X med bestilte par med naturlige tall, er det fornuftig å spørre om i X det første medlemmet av hvert par er avhengig av sekund; svaret Ja vil bety at det er en funksjon (f) slik at hvert par ((a, b)) i X har formen ((f (b), b)).

5. Semantiske spill for annen logikk

Strukturer av følgende art gir opphav til interessante spill. Strukturen (A) består av et sett (S) av elementer (som vi skal kalle tilstander, og legger til at de ofte kalles verdener), en binær relasjon (R) på (S) (vi skal lese (R) som pil), og en familie (P_1, / ldots, P_n) av undergrupper av (S). De to spillerne (forall) og (exist) spiller et spill G på (A), med en tilstand (s) som får dem, ved å lese en passende logisk formel (phi) som et sett med instruksjoner for å spille og for å vinne.

Så hvis (phi) er (P_i), så vinner spilleren (exist) på en gang hvis (s) er i (P_i), og ellers spiller (forall) vinner samtidig. Formlene (psi / wedge / theta, / psi / vee / theta) og (neg / psi) oppfører seg som i Hintikka sine spill ovenfor; for eksempel (psi / wedge / theta) instruerer spilleren (forall) å velge om spillet skal fortsette som for (psi) eller for (theta). Hvis formelen (phi) er (Box / psi), velger spiller (forall) en pil fra (s) til en tilstand (t) (dvs. en tilstand (t) slik at paret ((s, t)) er i forholdet (R)), og spillet fortsetter deretter fra staten (t) i henhold til instruksjonene (psi). Regelen for (Diamond / psi) er den samme bortsett fra at spilleren (exist) gjør valget. Til slutt sier vi at formelen (phi) er sann ved s i A hvis spilleren (eksisterer) har en vinnende strategi for dette spillet basert på (phi) og starter på (s).

Disse spillene er i tråd med modal logikk på samme måte som Hintikka sine spill er førsteklasses logikk. Spesielt er de en måte å gi en semantikk for modal logikk, og de er enige i vanlig semantikk av Kripke-typen. Selvfølgelig er det mange typer og generaliseringer av modal logikk (inkludert nær beslektede logikker som tidsmessige, epistemiske og dynamiske logikker), og så de tilsvarende spillene kommer i mange forskjellige former. Et eksempel på interesse er datamaskinteoretisk logikk til Matthew Hennessy og Robin Milner, brukt for å beskrive systemers oppførsel; her kommer pilene i mer enn én farge, og å bevege seg langs en pil med en bestemt farge representerer å utføre en bestemt 'handling' for å endre tilstanden. Et annet eksempel er den kraftigere modalen (mu) - beregning av Dexter Kozen, som har faste punktoperatører;se kapittel 5 i Stirling 2001.

Et interessant trekk ved disse spillene er at hvis en spiller har en vinnende strategi fra en eller annen posisjon, trenger den strategien aldri å referere til noe som skjedde tidligere i stykket. Det er uten betydning hvilke valg som ble tatt tidligere, eller til og med hvor mange trinn som er spilt. Så vi har det dataforskerne noen ganger kaller en 'minneløs' vinnerstrategi.

I den relaterte 'logikken over spill', foreslått av Rohit Parikh, er spill som beveger oss mellom delstatene gjenstanden snarere enn en måte å gi en sann definisjon på. Disse spillene har mange interessante aspekter. I 2003 ga tidsskriftet Studia Logica et tema viet dem, redigert av Marc Pauly og Parikh.

Innflytelser fra økonomi og informatikk har ført til at en rekke logikere bruker logikk for å analysere beslutninger under forhold med delvis uvitenhet. (Se for eksempel artikkelen om epistemisk logikk.) Det er flere måter å representere kunnskapstilstander på. Den ene er å ta dem som stater eller verdener i den slags modalstruktur som vi nevnte i begynnelsen av denne delen. En annen er å bruke IF-logikk eller en variant av den. Hvordan er disse tilnærmingene relatert? Johan van Benthem 2006 presenterer noen tanker og resultater på dette veldig naturlige spørsmålet. Se også avisene av Johan van Benthem, Krister Segerberg, Eric Pacuit og K. Venkatesh og deres referanser, i del IV 'Logic, Agency and Games' av Van Benthem, Gupta og Parikh 2011 og innføringen på logikk for å analysere spill for en utvalg av nyere arbeid på dette området.

6. Back-and-Forth-spill

I 1930 formulerte Alfred Tarski forestillingen om at to strukturer (A) og (B) er elementært likeverdige, dvs. at nøyaktig de samme førsteordens setninger stemmer i (A) som er sanne i (B). På en konferanse i Princeton i 1946 beskrev han denne forestillingen og uttrykte håp om at det ville være mulig å utvikle en teori om den som ville være "så dypt som forestillinger om isomorfisme, etc. nå i bruk" (Tarski 1946).

En naturlig del av en slik teori ville være en rent strukturell nødvendig og tilstrekkelig betingelse for at to strukturer er elementært likeverdige. Roland Fraïssé, en fransk-Algerier, var den første som fant en brukbar nødvendig og tilstrekkelig betingelse. Den ble oppdaget noen år senere av den kasakhiske logikeren AD Taimanov, og den ble omformulert med tanke på spill av den polske logikeren Andrzej Ehrenfeucht. Spillene er nå kjent som Ehrenfeucht-Fraïssé-spill, eller noen ganger som frem-og-tilbake-spill. De har vist seg å være en av de mest allsidige ideene i det tjuende århundrets logikk. De tilpasser seg fruktbart til et bredt spekter av logikker og strukturer.

I et frem og tilbake spill er det to strukturer (A) og (B), og to spillere som ofte kalles Spoiler and Duplicator. (Navnene skyldes Joel Spencer på begynnelsen av 1990-tallet. Nylig foreslo Neil Immerman Samson og Delilah, ved å bruke de samme initialene; dette plasserer Spoiler som den mannlige spilleren (forall) og Duplicator som den kvinnelige (eksisterer).) Hvert trinn i spillet består av et trekk med Spoiler, etterfulgt av et trekk av Duplicator. Spoiler velger et element i en av de to strukturene, og Duplicator må deretter velge et element i den andre strukturen. Så etter (n) trinn, er to sekvenser valgt, en fra (A) og en fra (B):

[(a_0, / ldots, a_ {n-1}; b_0, / ldots, b_ {n-1}).)

Denne posisjonen er en gevinst for Spoiler hvis og bare hvis noen atomformel (av en av formene '(R (v_0, / ldots, v_ {k-1}))' eller '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'eller' (v_0 = v_1) ', eller en av disse med forskjellige variabler) er tilfreds med ((a_0, / ldots, a_ { n-1})) i (A) men ikke av ((b_0, / ldots, b_ {n-1})) i (B), eller omvendt. Betingelsen for at Duplicator skal vinne er forskjellig i forskjellige former for spillet. I den enkleste formen, (EF (A, B)), er et skuespill en gevinst for Duplicator hvis og bare hvis ingen første del av det er en seier for Spoiler (dvs. hun vinner hvis hun ikke har tapt med noen finitt stadium). For hvert naturlig tall (m) er det et spill (EF_m (A, B)); i dette spillet vinner Duplicator etter (m) trinn forutsatt at hun ikke har tapt ennå. Alle disse spillene blir bestemt av Gale-Stewart-setningen. De to strukturene (A) og (B) sies å være frem og tilbake ekvivalent hvis Duplicator har en vinnende strategi for (EF (A, B)), og m-ekvivalent hvis hun har en vinnende strategi for (EF_m (A, B)).

Man kan bevise at hvis (A) og (B) er (m) - ekvivalent for hvert naturlig tall (m), så er de i utgangspunktet likeverdige. Faktisk, hvis Eloise har en vinnende strategi (tau) i Hintikka-spillet G ((phi)) på (A), der hekkingen av kvantifiseringsomfang av (phi) har de fleste m nivåer og Duplicator har en vinnende strategi (varrho) i spillet (EF_m (A, B)), de to strategiene (tau) og (varrho) kan settes sammen til en vinnende strategi fra Eloise i G ((phi)) på (B). På den annen side kan en vinnende strategi for Spoiler i (EF_m (A, B)) konverteres til en førsteordens setning som stemmer nøyaktig i en av (A) og (B), og der hekkingen av kvantifiseringsomfang har de fleste (m) nivåer. Så vi har vår nødvendige og tilstrekkelige forutsetning for elementær ekvivalens, og litt til.

Hvis (A) og (B) tilsvarer frem og tilbake, er de absolutt likeverdige; men faktisk frem og tilbake ekvivalens viser seg å være det samme som elementær ekvivalens i en infinitær logikk som er mye mer uttrykksfull enn førsteordens logikk. Det er mange justeringer av spillet som gir andre typer ekvivalens. For eksempel beskrev Barwise, Immerman og Bruno Poizat uavhengig et spill der de to spillerne har nøyaktig (p) nummererte småstein hver; hver spiller må merke sine valg med en rullestein, og de to valgene i samme trinn må merkes med småstein som har samme antall. Etter hvert som spillet fortsetter, vil spillerne gå tom for småstein, og derfor må de gjenbruke småstein som allerede var brukt. Betingelsen for at Spoiler skal vinne i en posisjon (og alle påfølgende posisjoner) er den samme som før, bortsett fra at bare elementene som bærer etiketter i den posisjonen teller. Eksistensen av en vinnende strategi for Duplicator i dette spillet betyr at de to strukturene er enige om setninger som bruker mest (p) variabler (slik at disse variablene kan forekomme et antall ganger).

Teorien bak frem og tilbake spill bruker svært få antagelser om den aktuelle logikken. Som et resultat er disse spillene en av få modellteoretiske teknikker som også gjelder finite strukturer som for uendelige, og dette gjør dem til en av hjørnesteinene i teoretisk informatikk. Man kan bruke dem til å måle uttrykksstyrken til formelle språk, for eksempel språk for databasesøk. Et typisk resultat kan for eksempel si at et visst språk ikke kan skille mellom "jevn" og "merkelig"; Vi vil bevise dette ved å finne for hvert nivå (n) av kompleksiteten i formler på språket, et par begrensede strukturer som Duplicator har en vinnende strategi i det frem og tilbake spillet av nivå (n), men den ene strukturen har et jevnt antall elementer, og den andre har et oddetall. Semantikere av naturlige språk har funnet frem og tilbake spill som er nyttige for å sammenligne uttrykksmaktene til generaliserte kvantifiserere. (Se for eksempel Peters og Westerståhl 2006 avsnitt IV.)

Det er også et slags frem-og-tilbake-spill som tilsvarer vår modale semantikk ovenfor på samme måte som Ehrenfeucht-Fraïssé-spill tilsvarer Hintikkas spillsemantikk for førsteordens logikk. Spillerne starter med en tilstand (s) i strukturen (A) og en tilstand (t) i strukturen (B). Spoiler og duplikator beveger seg vekselvis, som før. Hver gang han flytter, velger Spoiler om han vil flytte inn (A) eller i (B), og deretter må Duplicator bevege seg i den andre strukturen. Et trekk gjøres alltid ved å gå fremover med en pil fra gjeldende tilstand. Hvis mellom de to spillerne nettopp har flyttet til en tilstand (s) ´ i (A) og en tilstand (t) ´ i (B), og noe predikat (P_i) holder på bare en av (s) ´ og (t) ´, så taper Duplicator på en gang. Hun mister også hvis det ikke er tilgjengelige piler for henne å bevege seg;men hvis Spoiler finner at det ikke er tilgjengelige piler for ham å bevege seg i en av strukturer, vinner Duplicator. Hvis de to spillerne spiller dette spillet med gitte starttilstander (s) i (A) og (t) i (B), og begge strukturer har bare mange andre stater, kan man vise at Duplicator har en vinnende strategi hvis og bare hvis de samme modale setningene er sanne ved (s) i (A) som er sanne ved (t) i (B).

Det er mange generaliseringer av dette resultatet, noen av dem involverer følgende forestilling. La (Z) være en binær relasjon som knytter tilstander til (A) til tilstander av (B). Så kaller vi (Z) en bisimulering mellom (A) og (B) hvis Duplicator kan bruke (Z) som en ikke-bestemmende vinnerstrategi i det frem og tilbake spillet mellom (A) og (B) der det første trekkparet til de to spillerne er å velge starttilstander. I informatikk er forestillingen om en bisimulering avgjørende for forståelsen av (A) og (B) som systemer; det uttrykker at de to systemene samhandler med omgivelsene sine på samme måte som hverandre, trinn for trinn. Men litt før dataforskerne introduserte forestillingen, dukket i hovedsak det samme konseptet opp i Johan van Benthems doktorgradsavhandling om modal logikkens semantikk (1976).

7. Andre modellteoretiske spill

De logiske spillene i dette avsnittet er matematikernes verktøy, men de har noen konseptuelt interessante funksjoner.

7.1 Tvinge spill

Å tvinge spill er også kjent for beskrivende settteoretikere som Banach-Mazur-spill; se referansene fra Kechris eller Oxtoby nedenfor for mer informasjon om den matematiske bakgrunnen. Modellteoretikere bruker dem som en måte å bygge uendelige strukturer med kontrollerte egenskaper. I det enkleste tilfellet spiller (forall) og (exist) et såkalt Model Existence Game, der (exist) hevder at en fast setning (phi) har en modell mens (forall) hevder at han kan utlede en motsetning fra (phi). I begynnelsen er et tallfritt uendelig sett (C) med nye konstante symboler (a_0, a_1, a_2) osv. Rettet. (exist) forsvarer en disjunksjon ved å velge en disjunct, og en eksistensiell uttalelse ved å velge en konstant fra (C) som vitne. (forall) kan utfordre en konjunksjon ved å velge en av konjunktene,og en universell uttalelse ved å velge et vilkårlig vitne fra (C). (exist) vinner hvis ingen motstridende atomsetninger spilles. (exist) har en vinnende strategi (en konsistensseiendom er en måte å beskrive en vinnende strategi) hvis og bare hvis (phi) har en modell. På den annen side, hvis (forall) har en vinnende strategi, er treet (som kan gjøres begrenset) av alle skuespill mot hans vinnerstrategi relatert til et gentzen stilbevis for negering av (phi). Denne metoden for å analysere setninger er nært knyttet til Bet's metode for semantiske tabluer og det dialogiske spillet (se avsnitt 8). Hvis (forall) har en vinnerstrategi, er treet (som kan gjøres begrenset) av alle skuespill mot hans vinnerstrategi relatert til et Gentzen-stil bevis på negering av (phi). Denne metoden for å analysere setninger er nært knyttet til Bet's metode for semantiske tabluer og det dialogiske spillet (se avsnitt 8). Hvis (forall) har en vinnerstrategi, er treet (som kan gjøres begrenset) av alle skuespill mot hans vinnerstrategi relatert til et Gentzen-stil bevis på negering av (phi). Denne metoden for å analysere setninger er nært relatert til Bet's metode for semantiske tabluer og det dialogiske spillet (se avsnitt 8).

For å tegne ideen om det generelle tvangsspillet, kan du tenke deg at et utallig uendelig team med utbyggere bygger et hus (A). Hver byggherre har sin egen oppgave å utføre: for eksempel å installere et badekar eller å tapetsere inngangshallen. Hver byggherre har uendelig mange sjanser til å komme inn på stedet og legge til en viss mengde materiale til huset; disse sporene for byggherrene er sammenflettet slik at hele prosessen foregår i en sekvens av trinn som er talt av de naturlige tallene.

For å vise at huset kan bygges etter ordre, må vi vise at hver byggherre hver for seg kan utføre sin valgte oppgave, uavhengig av hva de andre byggherrene gjør. Så vi forestiller oss hver byggherre som spiller (eksisterer) i et spill der alle de andre spillerne er samlet sammen som (forall), og vi tar sikte på å bevise at (exist) har en vinnende strategi for dette spill. Når vi har bevist dette for hver byggherre hver for seg, kan vi tenke oss at de kommer til å jobbe, hver med sin egen vinnerstrategi. De vinner alle sine respektive kamper, og resultatet er ett vakkert hus.

Mer teknisk sett er elementene i strukturen (A) faste på forhånd, si som (a_0, a_1, a_2) osv., Men egenskapene til disse elementene må avgjøres av stykket. Hver spiller beveger seg ved å kaste inn et sett atom- eller negerte atomuttalelser om elementene, bare under forutsetning av at settet som består av alle utsagnene som er kastet inn så langt, må være i samsvar med et fast sett med aksiomer skrevet ned før spillet. (Så å kaste inn en negert atomsetning (neg / phi) har effekten av å forhindre at enhver spiller legger til (phi) på et senere tidspunkt.) På slutten av samspillet, settet med atomsetninger kastet inn har en kanonisk modell, og dette er strukturen (A); det er måter å sikre at det er en modell av det faste settet av aksiomer. En mulig egenskap P av (A) sies å kunne håndheves hvis en byggherre som får oppgaven å gjøre P sann av (A) har en vinnende strategi. Et sentralt poeng (hovedsakelig på grunn av Ehrenfeucht) er at sammenhengen av et utallig uendelig sett med rettskraftige egenskaper igjen er rettskraftig.

Ulike Löwenheim-Skolem-teorier fra modellteori kan bevises ved å bruke varianter av tvangsspillet. I disse variantene konstruerer vi ikke en modell, men en submodel av en gitt modell. Vi starter med en stor modell (M) for en setning (eller et tellende sett med setninger) (phi). Så lister vi opp underformlene til (phi), og hver spiller har en underformel med en gratis variabel å delta på. Spillerens oppgave er å sørge for at så snart parametrene til underformelen oppstår i spillet, og det er et vitne til sannheten om formelen i den store modellen, blir et slikt vitne spilt. Når spillet er over, er en tellbar submodel av (M) blitt bygget på en slik måte at det tilfredsstiller (phi).

Navnet 'tvang' kommer fra en anvendelse av relaterte ideer fra Paul Cohen for å konstruere modeller for settteori på begynnelsen av 1960-tallet. Abraham Robinson tilpasset den til å lage en generell metode for å bygge tellbare strukturer, og Martin Ziegler introduserte spillinnstillingen. Senere brukte Robin Hirsch og Ian Hodkinson beslektede spill for å avgjøre noen gamle spørsmål om relasjonsalgebras.

Å tvinge spill er et sunt eksempel du må huske på når du tenker på Dawkins-spørsmålet. De minner oss om at i logiske spill trenger det ikke være nyttig å tenke på spillerne som motsetter hverandre.

7.2 Klipp ut og velg spill

I det tradisjonelle kutt-og-velg-spillet tar du et kakestykke og kutter det i to mindre biter; så velger jeg en av bitene og spiser den, og etterlater den andre til deg. Denne prosedyren er ment å legge press på deg å kutte kaken rettferdig. Matematikere, som ikke helt forstår formålet med øvelsen, insisterer på å iterere den. Dermed får jeg deg til å kutte stykket jeg valgte i to, så velger jeg et av disse to; så klipper du dette stykket igjen, og så videre på ubestemt tid. Noen enda mer verdslige matematikere får deg til å skjære kaken i utallige mange biter i stedet for to.

Disse spillene er viktige i definisjonsteorien. Anta at vi har en samling (A) av objekter og en familie (S) av egenskaper; hver eiendom kutter (A) i settet med objektene som har egenskapen og settet med de som ikke har det. La (exist) kutte, starte med hele settet (A) og bruke en egenskap i (S) som kniv; la (forall) velge en av brikkene (som er undergrupper av (A)) og gi den tilbake til (exist) for å klippe ut igjen, ved å bruke en egenskap i (S); og så videre. La (eksisterer) tape så snart (forall) velger et tomt stykke. Vi sier at ((A, S)) har rangering på det meste (m) hvis (forall) har en strategi som sikrer at (exist) vil tape før henne (m) - flytte. Rangeringen til ((A, S)) gir verdifull informasjon om familien av undergrupper av (A) som kan defineres etter egenskaper i (S).

Variasjoner av dette spillet, slik at et stykke kan kuttes i uendelig mange mindre stykker, er grunnleggende i grenen av modellteorien kalt stabilitetsteori. Grovt sett er en teori 'god' i betydningen stabilitetsteori hvis, når vi tar en modell (A) av teorien og (S) settet med førsteordens formler i en gratis variabel med parametere fra (A), strukturen ((A, S)) har 'liten' rang. En annen variant er å kreve at (exist) på hvert trinn deler seg i to hver av brikkene som har overlevd fra tidligere trinn, og igjen mister hun så snart et av de kuttede fragmentene er tomme. (I denne versjonen er (forall) overflødig.) Med denne variasjonen kalles rangen til ((A), S) dens Vapnik-Chervonenkis-dimensjon; denne oppfatningen brukes i beregningslæringsteori.

7.3 Spill på treet til to etterfølgerfunksjoner

Se for deg et tre som er bygget opp i nivåer. På bunnnivå er det en enkelt rotnode, men en venstre gren og en høyre gren kommer opp fra den. På neste nivå opp er det to noder, en på hver gren, og fra hver av disse nodene vokser en venstre gren og en høyre gren opp. Så på neste nivå oppover er det fire noder, og igjen grener treet inn til venstre og høyre ved hver av disse nodene. Fortsatt til uendelig, kalles dette treet tre av to etterfølgerfunksjoner (nemlig venstre etterfølger og høyre etterfølger). Tar knutepunktene som elementer og introduserer to funksjonssymboler for venstre og høyre etterfølger, har vi en struktur. Et kraftig teorem fra Michael Rabin uttaler at det er en algoritme som vil fortelle oss, for hver monadisk annenordens setning (phi) på språket som er passende for denne strukturen,hvorvidt (phi) stemmer i strukturen eller ikke. ('Monadic second-order' betyr at logikken er som første-orden, bortsett fra at vi også kan kvantifisere over sett med elementer, men ikke over binære relasjoner til elementer, for eksempel.)

Rabins teorem har en rekke nyttige konsekvenser. For eksempel brukte Dov Gabbay det for å bevise avgjørbarheten til noen modale logikker. Men Rabins bevis, ved bruk av automata, var notorisk vanskelig å følge. Yuri Gurevich og Leo Harrington, og uavhengig Andrei Muchnik, fant mye enklere bevis der automaten er en spiller i et spill.

Dette resultatet av Rabin er en av flere innflytelsesrike resuls som forbinder spill med automata. Et annet eksempel er paritetsspillene som brukes til å verifisere egenskapene til modalsystemer. Se for eksempel Stirling (2001) kapittel 6; Bradfield og Stirling (2006) diskuterer paritetsspill for modal (mu) - calculus.

8. Spill om dialog, kommunikasjon og bevis

Flere middelalderske tekster beskriver en form for debatt kalt obligasjoner. Det var to disputanter, Opponens og Respondens. I begynnelsen av en samling ville disputantene enes om en 'positum', typisk en falsk uttalelse. Respondentenes jobb var å gi rasjonelle svar på spørsmål fra Opponens, under forutsetning av sannheten om positumet; fremfor alt måtte han unngå å motsi seg unødvendig. Opponens jobb var å prøve å tvinge Respondens til motsetninger. Så vi vet stort sett svaret på Dawkins-spørsmålet, men vi kjenner ikke spillereglene! De middelalderske lærebøkene beskriver riktignok flere regler som disputantene bør følge. Men disse reglene er ikke bestemte spilleregler; de er retningslinjer som lærebøkene stammer fra prinsipper for forsvarlig resonnement ved hjelp av eksempler.(Paul of Venice rettferdiggjør en regel ved å utføre "store logikere, filosofer, geometre og teologer." Spesielt var det åpent for en lærer med plikter å oppdage nye regler. Denne åpenheten innebærer at forpliktelser ikke er logiske spill i vår forstand.

Ikke alle er enige i forrige setning. For eksempel gir Catarina Dutilh Novaes (2007, 6) et detaljert forsvar av synspunktet som forpliktelser presenterer "et bemerkelsesverdig tilfelle av konseptuell likhet mellom et middelalderlig og moderne teoretisk rammeverk". Men uansett hva vi ser på dette spørsmålet, har disse debattene inspirert til en viktig linje med moderne forskning innen logiske spill.

Se for deg (eksisterer) som tar en muntlig eksamen i bevisteori. Sensoren gir henne en dom og inviterer henne til å begynne å bevise den. Hvis setningen har form

(phi / vee / psi)

så har hun rett til å velge en av setningene og si 'OK, jeg skal bevise denne'. (Faktisk hvis sensoren er en intuisjonist, kan han insistere på at hun velger en av setningene som skal bevises.) På den annen side hvis dommen er

(phi / kile / psi)

da kan sensoren, som er en sensor, godt velge en av konjunktene selv og invitere henne til å bevise den. Hvis hun vet hvordan man kan bevise konjunksjonen, så vet hun absolutt hvordan man kan bevise konjunkten.

Tilfellet med (phi / rightarrow / psi) er litt subtilere. Hun vil sannsynligvis starte med å anta (phi) for å trekke fra (psi); men det er en viss risiko for forvirring fordi setningene hun har skrevet ned så langt er alle ting som skal bevises, og (phi) er ikke noe å bevise. Sensoren kan hjelpe henne ved å si 'Jeg antar (phi), og la oss se om du kan komme til (psi) derfra.' På dette tidspunktet er det en sjanse for at hun ser en måte å komme seg til (psi) ved å trekke en motsetning fra (phi); slik at hun kan snu bordene på sensoren og invitere ham til å vise at hans antagelse er konsistent, med sikte på å bevise at det ikke er det. Symmetrien er ikke perfekt: han ba henne vise at en setning er sann overalt, mens hun inviterer ham til å vise at en setning er sann et eller annet sted. Likevel kan vi se en slags dualitet.

Ideer av denne typen ligger bak de dialektiske spillene til Paul Lorenzen. Han viste at med en viss skyving og skyving kan man skrive regler for spillet som har den egenskapen som (exist) har en vinnende strategi hvis og bare hvis setningen som hun blir presentert i begynnelsen er en teorem om intuisjonistisk logikk. I en gest mot middelalderske debatter kalte han (eksisterer) Proponenten og den andre spilleren motstanderen. Nesten som i middelalderens forpliktelser, vinner motstanderen ved å føre Talsmannen til et punkt der de eneste trekkene som er tilgjengelige for henne, er åpenbare selvmotsigelser.

Lorenzen hevdet at hans spill ga begrunnelse for både intuisjonistisk og klassisk logikk (eller med hans ord gjorde dem til 'gerechtfertigt', Lorenzen (1961, 196)). Dessverre innebærer enhver "begrunnelse" et overbevisende svar på Dawkins-spørsmålet, og dette Lorenzen ga aldri. For eksempel snakket han om trekk som 'angrep', selv når de (som sensorens valg på (phi / kil / psi) ovenfor) ser mer ut som hjelp enn fiendtlighet.

Inngangsdialogisk logikk gir en mer fullstendig redegjørelse for Lorenzens spill og en rekke nyere varianter. I sin nåværende form (januar 2013) sidestiller den Lorenzens påstander om rettferdiggjøring av logikk. I stedet beskriver den spillene som å gi semantikk for logikkene (et poeng som Lorenzen sikkert ville vært enig i), og legger til at for å forstå forskjellene mellom logikk kan det være nyttig å sammenligne semantikken deres.

Fra dette synspunktet er Lorenzens spill et viktig paradigme for det nyere bevisteoretikere har kalt semantikk av bevis. En semantikk av bevis gir en 'mening' ikke bare forestillingen om å være beviselig, men for hvert enkelt trinn i et bevis. Det svarer på spørsmålet "Hva oppnår vi ved å gjøre dette trekket i beviset?" I løpet av 1990-årene lette en rekke arbeidere ved den logiske enden av informatikk etter spill som ville stå i tråd med lineær logikk, og noen andre bevissystemer på samme måte som Lorenzens spill sto for intuisjonistisk logikk. Andreas Blass, og deretter senere Samson Abramsky og kolleger, ga spill som tilsvarte deler av lineær logikk, men i skrivende stund har vi ennå ikke en perfekt korrespondanse mellom spill og logikk. Dette eksemplet er spesielt interessant fordi svaret på Dawkins-spørsmålet skulle gi en intuitiv tolkning av lovene om lineær logikk, noe som denne logikken har sårt behov for. Spillene til Abramsky et al. fortelle en historie om to interaktive systemer. Men mens han begynte med spill der spillerne høflig svinger, tillot Abramsky senere spillerne å opptre 'på en distribuert, asynkron måte' og bare merke hverandre når de valgte å gjøre det. Disse spillene er ikke lenger i det normale formatet for logiske spill, og deres virkelighetsnære tolkning reiser mange nye spørsmål. Men mens han begynte med spill der spillerne høflig svinger, tillot Abramsky senere spillerne å opptre 'på en distribuert, asynkron måte' og bare merke hverandre når de valgte å gjøre det. Disse spillene er ikke lenger i det normale formatet for logiske spill, og deres virkelighetsnære tolkning reiser mange nye spørsmål. Men mens han begynte med spill der spillerne høflig svinger, tillot Abramsky senere spillerne å opptre 'på en distribuert, asynkron måte' og bare merke hverandre når de valgte å gjøre det. Disse spillene er ikke lenger i det normale formatet for logiske spill, og deres virkelighetsnære tolkning reiser mange nye spørsmål.

Giorgi Japaridze har foreslått en 'beregbarhetslogikk' for å studere beregning. Syntaks er førsteordens logikk med noen ekstra elementer som minner om lineær logikk. Semantikken er i form av semantiske spill med noen uvanlige funksjoner. For eksempel er det ikke alltid bestemt hvilken spiller som gjør neste trekk. Forestillingen om strategifunksjoner er ikke lenger tilstrekkelig for å beskrive spillerne; i stedet beskriver Japaridze måter å lese den andre spilleren (spilleren (eksisterer) i notasjonen vår) som en slags datamaskin. Ytterligere informasjon er på hjemmesiden hans.

En annen gruppe spill av samme generelle familie som Lorenzen er bevisspillene til Pavel Pudlak 2000. Her er motstanderen (kalt Prover) i rollen som advokat i en domstol, som vet at talsmannen (kalt motstander) er skyldig i noe lovbrudd. Talsmannen vil insistere på at han er uskyldig, og er villig til å fortelle løgner for å forsvare seg. Motstander har som mål å tvinge Proponent til å motsi noe som Proponent er på posten som tidligere sagt; men motstander holder posten, og (som i rullesteinspillene ovenfor) må han noen ganger slippe elementer fra posten på grunn av mangel på plass eller minne. Det viktige spørsmålet er ikke om motstander har en vinnende strategi (det antas fra begynnelsen at han har en), men hvor mye minne han trenger for platen sin. Disse spillene er et nyttig apparat for å vise øvre og nedre grense på lengden på prøvene i forskjellige korrektursystemer.

En annen type logisk spill som tillater løgn, er Ulams Game with Lies. Her tenker en spiller på et tall i et gitt område. Den andre spillerens mål er å finne ut hva nummeret er, ved å stille den første spilleren ja / nei spørsmål; men den første spilleren har lov til å fortelle noen faste løgner i svarene. Som i Pudlak sine spill, er det absolutt en vinnende strategi for den andre spilleren, men spørsmålet er hvor hardt denne spilleren må jobbe for å vinne. Tiltaket denne gangen er ikke plass eller minne, men tid: hvor mange spørsmål må han stille? Cignoli et al. 2000 kapittel 5 relaterer dette spillet til mange verdsatte logikker.

For å komme tilbake et øyeblikk til Lorenzen: han klarte ikke å skille mellom forskjellige holdninger som en person kan innta i et argument: å uttale, anta, inngi, spørre, angripe, begå seg selv. Hvorvidt det virkelig er mulig å definere alle disse forestillingene uten å anta noen logikk, er et viktig poeng. Men husk det; en foredling av Lorenzens spill i disse linjene kan tjene som en tilnærming til uformell logikk, og spesielt til forskningen som tar sikte på å systematisere de mulige strukturer for lyd uformell argumentasjon. På denne fronten kan du se Walton og Krabbe 1995. Avisene i Bench-Capon og Dunne 2007 er også relevante.

Bibliografi

Noen av referansepapirene av Henkin og Lorenzen, og noen av oppgavene som er sitert nedenfor, vises i samlingen Infinitistic Methods (Proceedings of the Symposium on Foundations of Mathematics, Warszawa 2. september 9. september 1959), Oxford: Pergamon Press, 1961 Redaksjonen er ikke navngitt.

Spill i logikkens historie

  • Dutilh Novaes, Catarina, 2007, Formalizing Medieval Logical Theories: Suppositio, Consequentiae and Obligationes, New York: Springer-Verlag.
  • Hamblin, Charles, 1970, Fallacies, London: Methuen.
  • Hilbert, David, 1967, “Die Grundlagen der Mathematik”, oversatt som “Grunnlaget for matematikk,” i Jean van Heijenoort (red.), Fra Frege til Gödel, Cambridge Mass.: Harvard University Press, s. 464–479.
  • Paul of Venice, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (red.), New York: British Academy og Oxford University Press, 1988.
  • Weyl, Hermann, 1925–7, “Die heutige Erkenntnislage in der Mathematik,”, oversatt som “Den nåværende epistemologiske situasjonen i matematikk” i Paolo Mancosu, Fra Brouwer til Hilbert: Debatten om grunnlaget for matematikk på 1920-tallet, New York: Oxford University Press, 1988, s. 123–142.
  • Zermelo, Ernst, 1913, “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels,” i EW Hobson og AEH Love (red.), Proceedings of the Fifth International Congress of Mathematicians, Volum II, Cambridge: Cambridge University Press.

Spill for undervisningslogikk

  • Barwise, Jon og John Etchemendy, 1995, The Language of First-Order Logic, inkludert Tarski's World 3.0, Cambridge: Cambridge University Press.
  • Carroll, Lewis, 1887, The Game of Logic, London: Macmillan.
  • Dienes, Zoltan P., og EW Golding, 1966, Learning Logic, Logical Games, Harlow: Educational Supply Association.
  • Havas, Katalin, 1999, “Lære å tenke: logikk for barn,” i Proceedings of the Twentieth World Congress of Philosophy (bind 3: Philosophy of Education), David M. Steiner (red.), Bowling Green Ohio: Bowling Green State Universitetsfilosofi, s. 11–19.
  • Nifo, Agostino, 1521, Dialectica Ludicra (Logic as a game), Florence: Bindonis.
  • Weng, Jui-Feng, med Shian-Shyong Tseng og Tsung-Ju Lee, 2010, “Lære boolsk logikk gjennom tuning av spillregler,” IEEE Transactions, Learning Technologies, 3 (4): 319–328. [Bruker Pac-Man-spill for å lære boolsk logikk til ungdomsskoleelever.]

Logiske spill

  • Gale, David og FM Stewart, 1953, "Uendelig spill med perfekt informasjon," i Bidrag til teorien om spill II (Annals of Mathematics Studies 28), HW Kuhn og AW Tucker (red.), Princeton: Princeton University Press, pp. 245–266.
  • Kechris, Alexander S., 1995, Classical Descriptive Set Theory, New York: Springer-Verlag.
  • Marion, Mathieu, 2009, "Hvorfor spille logiske spill?".
  • Osbourne, Martin J. og Ariel Rubinstein, 1994, A Course in Game Theory, Cambridge: MIT Press.
  • Väänänen, Jouko, 2011, Models and Games, Cambridge: Cambridge University Press.
  • van Benthem, Johan, 2011, Logisk dynamikk i informasjon og samhandling, Cambridge: Cambridge University Press, 2011.
  • –––, 2014, Logic in games, Cambridge, MA: MIT Press.

Semantiske spill for klassisk logikk

  • Henkin, Leon, 1961, "Noen kommentarer til uendelig lange formler," i Infinitistic Methods, op. cit., s. 167–183.
  • Hintikka, Jaakko, 1973, Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic, Oxford: Clarendon Press.
  • Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, New York: Cambridge University Press. [Se for eksempel side 40, 82 om ønsket aksiom.]
  • Hodges, Wilfrid, 2001, “Elementary Predicate Logic 25: Skolem Functions,” i Dov Gabbay, og Franz Guenthner (red.), Handbook of Philosophical Logic I, 2. utgave, Dordrecht: Kluwer, s. 86–91. [Bevis for ekvivalens av spill og Tarski semantikk.]
  • Kolaitis, Ph. G., 1985, "Game quantification", i J. Barwise og S. Feferman (red.), Model-Theoretic Logics, New York: Springer-Verlag, s. 365-421.
  • Peirce, Charles Sanders, 1898, Reasoning and the Logic of Things: The Cambridge Conferences Lectures of 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Semantiske spill med ufullkommen informasjon

  • Hintikka, Jaakko og Gabriel Sandu, 1997, “Spillteoretisk semantikk,” i Johan van Benthem og Alice ter Meulen (red.), Handbook of Logic and Language, Amsterdam: Elsevier, s. 361–410.
  • Hodges, Wilfrid, 1997, "Kompositorisk semantikk for et språk med ufullkommen informasjon," Logic Journal of IGPL, 5: 539–563.
  • Janssen, Theo MV og Francien Dechesne, 2006, “Signaling: a tricky business,” i J. van Benthem et al. (red.), The Age of Alternative Logics: Assessing the Philosophy of Logic and Mathematics Today, Dordrecht: Kluwer, s. 223–242.
  • Mann, Allen L., Gabriel Sandu og Merlin Sevenster, 2011, Independence-Friendly Logic: A Game-Theoretic Approach (London Mathematical Society Lecture Note Series 386), Cambridge: Cambridge University Press.
  • von Neumann, John og Oskar Morgenstern, 1944, Theory of Games and Economic Behaviour, Princeton: Princeton University Press.
  • Väänänen, Jouko, 2007, Dependence Logic: A New Approach to Independence Friendly Logic, Cambridge: Cambridge University Press.

Semantiske spill for annen logikk

  • Bradfield, Julian og Colin Stirling, 2006, “Modal mu-calculi,” i P. Blackburn et al. (red.), Handbook of Modal Logic, Amsterdam: Elsevier, s. 721–756.
  • Dekker, Paul og Marc Pauly (red.), 2002, Journal of Logic, Language and Information, 11 (3): 287–387. [Spesialutgave om logikk og spill.]
  • Hennessy, Matthew og Robin Milner, 1985, “Algebraiske lover for ubestemmelse og samtidighet,” Journal of the ACM, 32: 137–162.
  • Parikh, Rohit, 1985, “Logikken i spill og dens anvendelser,” i Marek Karpinski og Jan van Leeuwen (red.), “Emner i teorien om beregning,” Annals of Discrete Mathematics, 24: 111-140.
  • Pauly, Marc og Rohit Parikh (red.), 2003, Studia Logica, 72 (2): 163–256 [Spesialutgave om spilllogikk.]
  • Stirling, Colin, 2001, Modal and Temporal Properties of Processes, New York: Springer-Verlag.
  • van Benthem, Johan, 2006, “The epistemic logic of IF games,” i Randall Auxier og Lewis Hahn (red.), The Philosophy of Jaakko Hintikka, Chicago: Open Court s. 481–513.
  • van Benthem, Johan med Amitabha Gupta og Rohit Parikh, 2011, Proof, Computation and Agency, Dordrecht: Springer-Verlag.

Back-and-Forth-spill

  • Blackburn, Patrick med Maarten de Rijke og Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
  • Doets, Kees, 1996, Basic Model Theory, Stanford: CSLI Publications and FoLLI.
  • Ebbinghaus, Heinz-Dieter og Jörg Flum, 1999, Finite Model Theory, 2. utgave, New York: Springer.
  • Ehrenfeucht, Andrzej, 1961, "En anvendelse av spill på fullstendighetsproblemet for formaliserte teorier," Fundamenta Mathematicae, 49: 129–141.
  • Grädel, Erich med Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, og Scott Weinstein, 2007, Finite Model Theory, Berlin: Springer-Verlag.
  • Libkin, Leonid, 2004, Elements of Finite Model Theory, Berlin, Springer-Verlag.
  • Otto, Martin, 1997, Bounded Variable Logics and Counting-A Study in Finite Models (Lecture Notes in Logic, 9), Berlin: Springer-Verlag.
  • Peters, Stanley og Dag Westerståhl, 2006, Quantifiers in Language and Logic, Oxford: Clarendon Press.
  • Tarski, Alfred, 1946, “Adresse på Princeton University Bicentennial Conference on Problems of Mathematics (17–19 desember 1946),” Hourya Sinaceur (red.), Bulletin of Symbolic Logic, 6 (2000): 1–44.
  • van Benthem, Johan, 2001, “Correspondence Theory,” i Dov Gabbay og Franz Guenthner (red.), Handbook of Philosophical Logic III, 2. utgave, Dordrecht: Kluwer.

Andre modellteoretiske spill

  • Anthony, Martin og Norman Biggs, 1992, Computational Learning Theory, Cambridge: Cambridge University Press. [For Vapnik-Chervonenkis-dimensjonen.]
  • Gurevich, Yuri og Leo Harrington, 1984, “Trees, automata and games,” i HR Lewis (red.), Proceedings of ACM Symposium on the Theory of Computing, San Francisco: ACM, s. 171–182.
  • Hirsch, Robin og Ian Hodkinson, 2002, Relation Algebras by Games, New York: Nord-Holland.
  • Hodges, Wilfrid, 1985, Building Models by Games, Cambridge: Cambridge University Press.
  • Hodges, Wilfrid, 1993, Model Theory, Cambridge: Cambridge University Press.
  • Oxtoby, JC, 1971, Mål og kategori, New York: Springer-Verlag.
  • Ziegler, Martin, 1980, “Algebraisch abgeschlossene Gruppen,” i SI Adian et al. (red.), Ordproblemer II: Oxford Book, Amsterdam: Nord-Holland, s. 449–576.

Games of Dialogue, Communication and Proof

  • Abramsky, Samson og Radha Jagadeesan, 1994, "Spill og fullstendighet for multiplikativ lineær logikk," Journal of Symbolic Logic, 59: 543–574.
  • Abramsky, Samson og Paul-André Melliès, 1999, "Samtidige spill og fullstendighet," i Proceedings of the Fourteenth International Symposium on Logic in Computer Science, Computer Science Press of the IEEE, s. 431–442.
  • Bench-Capon, TJM og Paul E. Dunne, 2007, “Argumentasjon innen kunstig intelligens,” Kunstig intelligens, 171: 619–641. [Innledningen til en rik samling av artikler om samme tema på side 642–937.]
  • Blass, Andreas, 1992, “En spillsemantikk for lineær logikk,” Annals of Pure and Applied Logic, 56: 183–220.
  • Cignoli, Roberto LO, Itala ML D'Ottaviano, og Daniele Mundici, 2000, Algebraic Foundations of Many-Valued Reasoning, Dordrecht: Kluwer.
  • Felscher, Walter, 2001, “Dialogues as a foundation for intuitionistic logic,” i Dov Gabbay og Franz Guenthner (red.), Handbook of Philosophical Logic V, 2. utgave, Dordrecht: Kluwer.
  • Hodges, Wilfrid og Erik CW Krabbe, 2001, “Dialogstiftelser,” Proceedings of the Aristotelian Society (Supplementary Volume), 75: 17–49.
  • Japaridze, Giorgi, 2003, "Introduksjon til beregbarhetslogikk", Annals of Pure and Applied Logic, 123: 1–99.
  • Lorenzen, Paul, 1961 “Ein dialogisches Konstruktivitätskriterium,” i Infinitistic Methods, op. cit., 1961, s. 193–200.
  • Pudlak, Pavel, 2000, “Bevis som spill,” American Mathematical Monthly, 107 (6): 541–550.
  • Walton, Douglas N. og Erik CW Krabbe, 1995, Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning, Albany: State University of New York Press.

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

Anbefalt: