Modellteori

Innehållsförteckning:

Modellteori
Modellteori
Anonim

Inmatningsnavigering

  • Inmatningsinnehåll
  • Bibliografi
  • Akademiska verktyg
  • Vänner PDF-förhandsvisning
  • Författare och Citation Info
  • Tillbaka till toppen

Modellteori

Först publicerad lör 10 november 2001; substantiell revidering ons 17 juli 2013

Modellteorin började med att studera formella språk och deras tolkningar, och av de typer av klassificering som ett visst formellt språk kan göra. Mainstream-modellteorin är nu en sofistikerad gren av matematik (se posten i första ordningens modellteori). Men i en bredare mening är modellteori studiet av tolkningen av alla språk, formella eller naturliga, med hjälp av setteoretiska strukturer, med Alfred Tarskis sanningsdefinition som ett paradigm. I denna bredare mening möter modellteori filosofi på flera punkter, till exempel i teorin om logisk konsekvens och i semantiken i naturliga språk.

  • 1. Grundläggande uppfattningar om modellteori
  • 2. Modellteoretisk definition
  • 3. Modellteoretisk konsekvens
  • 4. Uttrycksstyrka
  • 5. Modeller och modellering
  • Bibliografi
  • Akademiska verktyg
  • Andra internetresurser
  • Relaterade poster

1. Grundläggande uppfattningar om modellteori

Ibland skriver eller talar vi en mening (S) som uttrycker ingenting varken sant eller falskt, eftersom det saknas viktig information om vad orden betyder. Om vi fortsätter att lägga till denna information, så att (S) kommer att uttrycka ett sant eller falskt uttalande, sägs vi tolka (S), och den tillagda informationen kallas en tolkning av (S). Om tolkningen (I) råkar göra (S) tillstånd något sant, säger vi att (I) är en modell av (S), eller att (I) uppfyller (S)), i symbolerna '(I / vDash S)'. Ett annat sätt att säga att (I) är en modell av (S) är att säga att (S) är sant i (I), och så har vi uppfattningen om modellteoretisk sanning, som är sanning i en viss tolkning. Men man bör komma ihåg att uttalandet '(S) är sant i (I)' bara är en parafrase av '(S), när den tolkas som i (I), är sann'så modellteoretisk sanning är parasitisk på vanlig vanlig sanning, och vi kan alltid omformasera den bort.

Till exempel kan jag säga

Han dödar dem alla,

och erbjuder tolkningen att "han" är Alfonso Arblaster på 35 halvmånen, Beetleford, och att "dem" är duvorna på hans loft. Denna tolkning förklarar (a) vilka objekt som vissa uttryck refererar till, och (b) vilka klasser vissa kvantifierare sträcker sig över. (I det här exemplet finns det en kvantifierare: 'alla av dem'). Tolkningar som består av artiklar (a) och (b) förekommer väldigt ofta i modellteori, och de kallas strukturer. Speciella typer av modellteori använder särskilda strukturer; till exempel brukar matematisk modellteori använda så kallade förstordensstrukturer, modellteori för modal logik använder Kripke-strukturer, och så vidare.

Strukturen (I) i föregående stycke innefattar ett fast objekt och en fast klass. Eftersom vi beskrev strukturen idag är klassen klassen av duvor på Alfonsos loft idag, inte de som kommer imorgon för att ersätta dem. Om Alfonso Arblaster dödar alla duvorna på sitt loft idag, uppfyller (I) den citerade meningen idag men kommer inte att tillfredsställa den i morgon, för Alfonso kan inte döda samma duvor två gånger över. Beroende på vad du vill använda modellteori för kan du gärna utvärdera meningar idag (standardtid), eller kanske du vill registrera hur de är nöjda vid en tidpunkt och inte vid en annan. I det senare fallet kan du relativisera begreppet modell och skriva '(I / vDash_t S)' för att betyda att (I) är en modell av (S) vid tiden (t). Detsamma gäller för platser,eller till något annat som kan plockas upp av andra implicita indexindex i meningen. Om du till exempel tror på möjliga världar kan du indexera (vDash) efter den möjliga världen där meningen ska utvärderas. Förutom att använda uppsättningsteori är modellteori helt agnostisk om vilka slags saker som finns.

Observera att objekt och klasser i en struktur har etiketter som styr dem till rätt uttryck i meningen. Dessa etiketter är en väsentlig del av strukturen.

Om samma klass används för att tolka alla kvantifierare kallas klassen strukturens domän eller universum. Men ibland finns det kvantifierare som sträcker sig över olika klasser. Till exempel om jag säger

En av de dåliga sjukdomarna är att döda alla fåglarna.

du letar efter en tolkning som tilldelar en klass av sjukdomar till "dessa sakta sjukdomar" och en klass av fåglar till "fåglarna". Tolkningar som ger två eller flera klasser för olika kvantifierare att variera sägs vara många sorterade och klasserna kallas ibland sorter.

Idéerna ovan kan fortfarande vara användbara om vi börjar med en mening (S) som säger något antingen sant eller falskt utan att behöva ytterligare tolkning. (Modellteoretiker säger att en sådan mening är fullständigt tolkad.) Vi kan till exempel överväga missuppfattningar (I) av en helt tolkad mening (S). En felaktig tolkning av (S) som gör det sant kallas en icke standard eller oavsiktlig modell av (S). Matematikens gren som kallas icke-standardanalys är baserad på icke-normala modeller av matematiska påståenden om de verkliga eller komplexa talsystemen; se avsnitt 4 nedan.

Man talar också om modellteoretisk semantik för naturliga språk, vilket är ett sätt att beskriva betydelsen av naturliga språkmeningar, inte ett sätt att ge dem betydelse. Kopplingen mellan denna semantik och modellteori är lite indirekt. Det ligger i Tarskis sanningsdefinition från 1933. Se posten i Tarskis sanningsdefinitioner för mer information.

2. Modellteoretisk definition

En mening (S) delar upp alla möjliga tolkningar i två klasser, de som är modeller av det och de som inte är det. På detta sätt definierar den en klass, nämligen klassen för alla dess modeller, skriven (Mod (S)). För att ta ett rättsligt exempel är meningen

Den första personen har överfört fastigheten till den andra personen, som därmed innehar fastigheten till förmån för den tredje personen.

definierar en klass av strukturer som har formen av märkta 4-tuples, som till exempel (skriver etiketten till vänster):

  • den första personen = Alfonso Arblaster;
  • fastigheten = det förfallna landet bakom Alfonsos hus;
  • den andra personen = John Doe;
  • den tredje personen = Richard Roe.

Detta är en typisk modellteoretisk definition som definierar en klass av strukturer (i detta fall den klass som advokaterna känner till som förtroende).

Vi kan utöka idén om modellteoretisk definition från en enda mening (S) till en uppsättning (T) av meningar; (Mod (T)) är klassen för alla tolkningar som samtidigt är modeller av alla meningar i (T). När en uppsättning (T) av meningar används för att definiera en klass på detta sätt, säger matematiker att (T) är en teori eller en uppsättning axiomer, och att (T) axiomatiserar klassen (mod (T)).

Ta till exempel följande uppsättning första ordningsmeningar:

(börja {align *} & / forall x / forall y / forall z (x + (y + z) = (x + y) + z). \& / för alla x (x + 0 = x). \& / för alla x (x + (-x) = 0). \& / forall x / forall y (x + y = y + x). / End {align *})

Här är etiketterna tilläggssymbolen '+', minussymbolen '(-)' och den ständiga symbolen '0'. En tolkning måste också ange en domän för kvantifierarna. Med ett förbehåll är modellerna för denna uppsättning meningar exakt de strukturer som matematiker känner som abeliska grupper. Förbehållet är att domänen i en abelisk grupp (A) ska innehålla tolkningen av symbolen 0 och den ska stängas under tolkningarna av symbolerna + och (-). I matematisk modellteori bygger man detta villkor (eller motsvarande villkor för annan funktion och konstanta symboler) i definitionen av en struktur.

Varje matematisk struktur är knuten till ett visst första ordningsspråk. En struktur innehåller tolkningar av vissa symboler för predikat, funktion och konstant; varje predikat eller funktionssymbol har en fast arity. Samlingen (K) av dessa symboler kallas strukturen för signatur. Symboler i signaturen kallas ofta icke-logiska konstanter, och ett äldre namn för dem är primitiva. Det första ordningsspråket för signatur (K) är det första ordningsspråket som byggs upp med symbolerna i (K), tillsammans med jämställdhetstecknet =, för att bygga upp sina atomformler. (Se posten om klassisk logik.) Om (K) är en signatur, är (S) en mening i signaturspråket (K) och (A) är en struktur vars signatur är (K), därför att symbolerna matchar, vi vet att (A) gör (S) antingen sant eller falskt. Så man definierar klassen abeliska grupper som klass för alla de strukturerna för signatur (+), (-), (0) som är modeller för meningarna ovan. Bortsett från det faktum att det använder ett formellt första ordningsspråk, är detta exakt algebraisternas vanliga definition av klassen abeliska grupper; modellteori formaliserar en typ av definition som är extremt vanligt i matematik.

Nu har de definierande axiomerna för abeliska grupper tre slags symboler (bortsett från skiljetecken). Först finns det den logiska symbolen = med en fast betydelse. För det andra finns det icke-logiska konstanter som får sin tolkning genom att tillämpas på en viss struktur; man bör gruppera kvantifieringssymbolerna med dem, eftersom strukturen också bestämmer domänen som kvantifierarna sträcker sig över. Och för det tredje finns variablerna (x, y) osv. Detta tre nivåers symbolmönster låter oss definiera klasser på ett andra sätt. I stället för att leta efter tolkningarna av de icke-logiska konstanterna som kommer att göra en mening sann, fixar vi tolkningarna av de icke-logiska konstanterna genom att välja en viss struktur (A), och vi letar efter uppdrag av element av (A) till variabler som gör en given formel sann i (A).

Låt till exempel (mathbb {Z}) vara den additiva gruppen med heltal. Dess element är heltal (positiva, negativa och 0), och symbolerna (+), (-), (0) har sina vanliga betydelser. Tänk på formeln

[v_1 + v_1 = v_2.)

Om vi tilldelar numret (- 3) till (v_1) och antalet (- 6) till (v_2) fungerar formeln som sant i (mathbb {Z}). Vi uttrycker detta genom att säga att paret ((- 3, -6)) uppfyller denna formel i (mathbf {Z}). Likaså uppfyller (15,30) och (0,0) det, men ((2, -4)) och (3,3) gör det inte. Således definierar formeln en binär relation på heltal, nämligen uppsättningen parpar med heltal som tillfredsställer det. En relation definierad på detta sätt i en struktur (A) kallas en första ordnings definierbar relation i (A). En användbar generalisering är att låta den definierande formeln använda tillagda namn för vissa specifika element i (A); dessa element kallas parametrar och relationen kan sedan definieras med parametrar.

Denna andra typ av definition, som definierar relationer i en struktur snarare än klasser av struktur, formaliserar också en vanlig matematisk praxis. Men den här gången tillhör praxis geometri snarare än algebra. Du kanske känner igen relationen i fältet för verkliga nummer som definieras av formeln

[v_1 ^ 2 + v_2 ^ 2 = 1.)

Det är cirkeln med radie 1 runt ursprunget i det verkliga planet. Algebraisk geometri är full av definitioner av denna typ.

Under 1940-talet hände det till flera människor (främst Anatolii Mal'tsev i Ryssland, Alfred Tarski i USA och Abraham Robinson i Storbritannien) att metatorierna i klassisk logik skulle kunna användas för att bevisa matematiska teorier om klasser definierade på de två sätten vi har precis beskrivet. År 1950 bjöds både Robinson och Tarski in till den internationella kongressen för matematiker i Cambridge Mass. Om denna nya disciplin (som hittills inte hade något namn - Tarski föreslog namnet 'modellerteori' 1954). Slutsatsen på Robinsons adress till den kongressen är värt att citera:

[De] konkreta exemplen som framställts i detta dokument kommer att ha visat att samtida symbolisk logik kan producera användbara verktyg - men inte på något sätt allmänt - för utvecklingen av faktisk matematik, mer specifikt för utvecklingen av algebra och, verkar det, av algebraisk geometri. Detta är förverkligandet av en ambition som Leibniz uttryckte i ett brev till Huyghens så länge sedan 1679.

I själva verket hade Mal'tsev redan använt ganska djupa tillämpningar av modellteori i gruppteori flera år tidigare, men under de tidens politiska förhållanden var hans arbete i Ryssland ännu inte känt i väst. I slutet av det tjugonde århundradet hade Robinsons förhoppningar fullständigt uppfyllts; se posten i första ordningens modellteori.

Det finns minst två andra typer av definitioner i modellteori förutom dessa två ovan. Den tredje är känd som tolkning (ett speciellt fall av tolkningarna som vi började med). Här börjar vi med en struktur (A), och vi bygger en annan struktur (B) vars signatur inte behöver vara relaterad till (A) genom att definiera domänen (X) för (B) och alla märkta relationer och funktioner för (B) för att vara de relationer som kan definieras i (A) med vissa formler med parametrar. En ytterligare förfining är att hitta ett definierbart ekvivalensförhållande på (X) och ta domänen till (B) att inte vara själva (X) utan uppsättningen av ekvivalensklasser för denna relation. Strukturen (B) byggd på detta sätt sägs vara tolkad i strukturen (A).

Ett enkelt exempel, återigen från standardmatematik, är tolkningen av gruppen (mathbb {Z}) av heltal i strukturen (mathbb {N}) som består av de naturliga siffrorna 0, 1, 2 etc. med etiketter för 0, 1 och +. För att konstruera domänen för (mathbb {Z}) tar vi först uppsättningen (X) för alla ordnade par med naturliga nummer (helt klart en definierbar relation i (mathbb {N})), och på denna uppsättning (X) definierar vi ekvivalensrelationen (sim) med

[(a, b) sim (c, d) text {om och bara om} a + d = b + c)

(återigen definierbar). Domänen för (mathbb {Z}) består av ekvivalensklasserna för denna relation. Vi definierar tillägg på (mathbb {Z}) av

[(a, b) + (c, d) = (e, f) text {om och bara om} a + c + f = b + d + e.)

Ekvivalensklassen för ((a, b)) blir heltalet (a - b).

När en struktur (B) tolkas i en struktur (A) kan varje första ordning om (B) översättas till en första ordning om (A), och i detta sätt vi kan läsa av hela teorin om (B) från den av (A). I själva verket om vi utför denna konstruktion inte bara för en enda struktur (A) utan för en familj av modeller av en teori (T), alltid med samma definierande formler, kommer de resulterande strukturerna alla att vara modeller av en teori (T ') som kan avläsas från (T) och de definierande formlerna. Detta ger en exakt mening till påståendet att teorin (T ') är tolkad i teorin (T). Vetenskapsfilosofer har ibland experimenterat med denna uppfattning om tolkning som ett sätt att göra exakt vad det betyder för en teori att kunna reduceras till en annan. Men realistiska exempel på minskningar mellan vetenskapliga teorier verkar i allmänhet vara mycket subtilare än denna enkla sinnesmodell-teoretiska idé kommer att tillåta. Se posten om interteoriska relationer i fysik.

Den fjärde typen av definierbarhet är ett par begrepp, implicit definierbarhet och uttrycklig definierbarhet av en viss relation i en teori. Se avsnitt 3.3 i posten om första ordens modellteori.

Tyvärr brukade det finnas en mycket förvirrad teori om modellteoretiska axiomer, som också gick under namnet implicit definition. I slutet av 1800-talet hade matematisk geometri i allmänhet upphört att vara en studie av rymden, och det hade blivit studiet av klasser av strukturer som tillfredsställer vissa 'geometriska' axiomer. Geometriska termer som 'punkt', 'linje' och 'mellan' överlevde, men endast som de primitiva symbolerna i axiomer; de hade inte längre någon betydelse förknippad med dem. Så den gamla frågan, om Euclids parallella postulat (som ett uttalande om rymden) kunde dras från Euclids andra antaganden om rymden, var inte längre intressant för geometrar. Istället visade geometrar att om man skrev ner en aktuell version av Euclids andra antaganden, i form av en teori (T),då var det möjligt att hitta modeller av (T) som inte uppfyller det parallella postulatet. (Se posten om geometri på 1800-talet för bidrag från Lobachevski och Klein till denna prestation.) 1899 publicerade David Hilbert en bok där han konstruerade sådana modeller med exakt den tolkningsmetod som vi just beskrev.

Problem uppstod på grund av hur Hilbert och andra beskrev vad de gjorde. Historiken är komplicerad, men ungefär hände följande. Runt mitten av 1800-talet märkte människor till exempel att i en abelisk grupp är minfunktionen definierbar i termer av 0 och + (nämligen: (- a) är elementet (b) så att (a + b = 0)). Eftersom denna beskrivning av minus i själva verket är en av de axiomer som definierar abeliska grupper, kan vi säga (med ett uttryck taget från JD Gergonne, som inte bör hållas ansvarigt för den senare användningen av det) att axiomerna för abeliska grupper implicit definierar minus. I tidens jargong sa man inte att axiomerna definierar funktionen minus, utan att de definierar begreppet minus. Anta nu att vi växlar om och försöker definiera plus i termer av minus och 0. På så sätt kan det inte göras, eftersom man kan ha två abeliska grupper med samma 0 och minus men olika plusfunktioner. I stället för att säga detta, drog matematikarna från det nittonde århundradet att axiomerna endast delvis definierar plus i termer av minus och 0. Efter att ha svalt så mycket fortsatte de att säga att axiomerna tillsammans bildar en implicit definition av begreppen plus, minus och 0 tillsammans, och att denna implicita definition endast är delvis men den säger om dessa begrepp exakt så mycket som vi behöver veta.de fortsatte med att säga att axiomerna tillsammans bildar en implicit definition av begreppen plus, minus och 0 tillsammans, och att denna implicita definition endast är partiell men den säger om dessa begrepp exakt så mycket som vi behöver veta.de fortsatte med att säga att axiomerna tillsammans bildar en implicit definition av begreppen plus, minus och 0 tillsammans, och att denna implicita definition endast är partiell men den säger om dessa begrepp exakt så mycket som vi behöver veta.

Man undrar hur det kunde hända att i femtio år ingen utmanade denna nonsens. I själva verket utmanade vissa människor det, i synnerhet geometern Moritz Pasch som i avsnitt 12 i hans Vorlesungen über Neuere Geometrie (1882) insisterade på att geometriska axiomer berättar oss ingenting om betydelsen av "punkt", "linje" etc. I stället han sagt, axiomerna ger oss relationer mellan begreppen. Om man tänker på en struktur som ett slags ordnat (n) - tupel av uppsättningar etc., då blir en klass (Mod (T)) en (n) - ary-relation, och Paschs konto instämmer med vår. Men han kunde inte ställa upp detaljerna, och det finns vissa bevis för att hans samtida (och några nyare kommentatorer) trodde att han sa att axiomen kanske inte bestämmer betydelsen av "punkt" och "linje",men de bestämmer de av relationella termer som "mellan" och "incident med"! Freges rivning av den implicita definitionsdoktrinen var mästerligt, men det kom för sent för att rädda Hilbert från att säga, i början av sin Grundlagen der Geometrie, att hans axiomer ger "den exakta och matematiskt adekvata beskrivningen" av relationerna "lögn", " mellan 'och' kongruent '. Lyckligtvis talar Hilberts matematik för sig själv, och man kan helt enkelt kringgå dessa filosofiska faux pas. Den modellteoretiska redogörelsen som vi nu tar som en korrekt beskrivning av detta arbete verkar ha dykt upp först i gruppen kring Giuseppe Peano på 1890-talet, och den nådde den engelsktalande världen genom Bertrand Russells matematiska principer 1903.men det kom för sent för att rädda Hilbert från att säga, i början av sin Grundlagen der Geometrie, att hans axiomer ger 'den exakta och matematiskt adekvata beskrivningen' av relationerna 'lögn', 'mellan' och 'kongruent'. Lyckligtvis talar Hilberts matematik för sig själv, och man kan helt enkelt kringgå dessa filosofiska faux pas. Den modellteoretiska redogörelsen som vi nu tar som en korrekt beskrivning av detta arbete verkar ha dykt upp först i gruppen kring Giuseppe Peano på 1890-talet, och den nådde den engelsktalande världen genom Bertrand Russells matematiska principer 1903.men det kom för sent för att rädda Hilbert från att säga, i början av sin Grundlagen der Geometrie, att hans axiomer ger 'den exakta och matematiskt adekvata beskrivningen' av relationerna 'lögn', 'mellan' och 'kongruent'. Lyckligtvis talar Hilberts matematik för sig själv, och man kan helt enkelt kringgå dessa filosofiska faux pas. Den modellteoretiska redogörelsen som vi nu tar som en korrekt beskrivning av detta arbete verkar ha dykt upp först i gruppen kring Giuseppe Peano på 1890-talet, och den nådde den engelsktalande världen genom Bertrand Russells matematiska principer 1903. Lyckligtvis talar Hilberts matematik för sig själv, och man kan helt enkelt kringgå dessa filosofiska faux pas. Den modellteoretiska redogörelsen som vi nu tar som en korrekt beskrivning av detta arbete verkar ha dykt upp först i gruppen kring Giuseppe Peano på 1890-talet, och den nådde den engelsktalande världen genom Bertrand Russells matematiska principer 1903. Lyckligtvis talar Hilberts matematik för sig själv, och man kan helt enkelt kringgå dessa filosofiska faux pas. Den modellteoretiska redogörelsen som vi nu tar som en korrekt beskrivning av detta arbete verkar ha dykt upp först i gruppen kring Giuseppe Peano på 1890-talet, och den nådde den engelsktalande världen genom Bertrand Russells matematiska principer 1903.

3. Modellteoretisk konsekvens

Anta (L) är ett signaturspråk (K, T) är en uppsättning meningar av (L) och (phi) är en mening av (L). Sedan relationen

(Mod (T) subseteq / Mod (phi))

uttrycker att varje struktur av signatur (K) som är en modell av (T) också är en modell av (phi). Detta kallas modell-teoretisk konsekvensförhållande, och det är skrivet för kort

[T / vDash / phi)

Dubbel användning av (vDash) är en olycka. Men i det specifika fallet där (L) är första ordningen, berättar fullständighetsteoremet (se posten på klassisk logik) att '(T / vDash / phi)' gäller om och bara om det finns ett bevis av (phi) från (T), en relation som vanligtvis är skriven

[T / vdash / phi)

Eftersom (vDash) och (vdash) uttrycker exakt samma samband i detta fall, undviker modellteoriker ofta dubbel användning av (vDash) genom att använda (vdash) för modellteoretisk konsekvens. Men eftersom det följande inte är begränsat till första ordens språk, tyder säkerheten på att vi håller oss med (vDash) här.

Före mitten av 1800-talet lärde studentböcker med logik vanligtvis eleven att kontrollera giltigheten för ett argument (säga på engelska) genom att visa att den har en av ett antal standardformer eller genom att parafrasera det till en sådan form. Standardformerna var syntaktiska och / eller semantiska argument på engelska. Processen var farlig: semantiska former är nästan per definition inte synliga på ytan, och det finns ingen rent syntaktisk form som garanterar giltigheten av ett argument. Av denna anledning hade de flesta av de gamla läroböckerna ett långt avsnitt om "missförstånd" - sätt som ett ogiltigt argument kan tyckas vara giltigt.

1847 bytte George Boole detta arrangemang. Till exempel för att validera argumentet

Alla monarker är människor. Inga människor är ofelbara. Därför är inga ofelbara varelser monarker.

Boole skulle tolka symbolerna (P, Q, R) som namn på klasser:

(P) är klass för alla monarker.

(Q) är klassen för alla människor.

(R) är klassen för alla ofelbara varelser.

Sedan påpekade han att det ursprungliga argumentet omformas till en set-teoretisk konsekvens:

[(P / subseteq Q), (Q / cap R = 0) vDash (R / cap P = 0))

(Detta exempel kommer från Stanley Jevons, 1869. Booles eget konto är idiosynkratisk, men jag tror att Jevons exempel representerar Booles avsikter exakt.) Idag skulle vi skriva (allall x (Px / högermark Qx)) snarare än (P / subseteq Q), men detta är i huvudsak standarddefinitionen av (P / subseteq Q), så skillnaden mellan oss och Boole är liten.

I den mån de följer Boole konstaterar moderna logböcker med logik att engelska argument är giltiga genom att reducera dem till modellteoretiska konsekvenser. Eftersom klassen av modellteoretiska konsekvenser, åtminstone i första ordningens logik, inte har någon av vaguenheterna i de gamla argumentformerna, har läroböcker med logik i denna stil för länge sedan upphört att ha ett kapitel om missförstånd.

Men det finns en varning som överlever från de gamla läroböckerna: Om du formaliserar ditt argument på ett sätt som inte är en modellteoretisk konsekvens, betyder det inte att argumentet inte är giltigt. Det kan bara betyda att du misslyckades med att analysera begreppen i argumentet tillräckligt djupt innan du formaliserade. De gamla läroböckerna som används för att diskutera detta i ett trasskyddsavsnitt som kallas 'ämnen' (dvs. tips för att hitta argument som du kanske har missat). Här är ett exempel från Peter av Spaniens 1300-talets Summulae Logicales:

Det finns en far. Därför finns det ett barn. ' … Var kommer detta argument från giltighet? Från relationen. Maximumet är: När ett av ett korrelerat par ställs, så är det andra också.

Hilbert och Ackermann, möjligen den lärobok som gjorde mest för att etablera den moderna stilen, diskuterar i deras avsnitt III.3 ett mycket liknande exempel: "Om det finns en son, finns det en far". De påpekar att varje försök att motivera detta med hjälp av symboliken

(existerar xSx / högermark / existerar xFx)

är dömd till misslyckande.”Ett bevis på detta uttalande är bara möjligt om vi konceptuellt analyserar betydelsen av de två predikaten som förekommer”, som de fortsätter att illustrera. Och naturligtvis finner analysen exakt den relation som Peter av Spanien hänvisade till.

Å andra sidan, om ditt engelska argument översätter till en ogiltig modellteoretisk konsekvens, kan ett motexempel på konsekvensen ge ledtrådar om hur du kan beskriva en situation som skulle göra grunden för ditt argument sanna och slutsatsen falsk. Men detta är inte garanterat.

Man kan ta upp ett antal frågor om huruvida den moderna läroboksproceduren verkligen fångar en förnuftig uppfattning om logisk konsekvens. Till exempel i Booles fall kan de setteoretiska konsekvenserna som han förlitar sig lätt bevisas med formella bevis i första ordningens logik, inte ens med några setteoretiska axiomer; och genom fullständighetsteoremet (se posten på klassisk logik) är det samma för första ordningens logik. Men för vissa andra logiker är det verkligen inte sant. Till exempel förutsätter modell-teoretisk konsekvensförhållande för vissa tidslogiker vissa fakta om tidens fysiska struktur. Som Boole själv påpekade kräver dess översättning från ett engelskt argument till dess setteoretiska form att vi tror att för varje egenskap som används i argumentet,det finns en motsvarande klass med alla saker som har egenskapen. Detta kommer farligt nära Freges inkonsekventa förståelsexiom!

1936 föreslog Alfred Tarski en definition av logisk konsekvens för argument på ett fullständigt tolkat formellt språk. Hans förslag var att ett argument är giltigt om och bara om: under någon tillåten omtolkning av dess icke-logiska symboler, om lokalerna är sanna, så är slutsatsen. Tarski antog att klassen av tillåtna omtolkningar kunde avläsas från semantiken i språket, vilket anges i hans sanningsdefinition. Han lämnade det obestämt vilka symboler som räknas som icke-logiska; i själva verket hoppades han att denna frihet skulle göra det möjligt för en att definiera olika typer av nödvändighet, kanske separera "logiskt" från "analytiskt". En sak som gör Tarskis förslag svårt att utvärdera är att han helt ignorerar frågan vi diskuterade ovan, att analysera begreppen för att nå alla logiska kopplingar mellan dem. Den enda rimliga förklaringen jag kan se för detta ligger i hans parentetiska kommentar om

nödvändigheten av att eliminera alla definierade tecken som eventuellt kan uppstå i de berörda meningarna, dvs att ersätta dem med primitiva tecken.

Detta antyder för mig att han vill att hans primitiva tecken ska vara oanalyserbara genom bestämmelse. Men då kommer det att vara rent oavsiktligt om hans föreställning om logisk konsekvens fångar allt man normalt skulle räkna som en logisk konsekvens.

Historiker noterar en likhet mellan Tarskis förslag och ett i avsnitt 147 i Bernard Bolzanos Wissenschaftslehre från 1837. I likhet med Tarski definierar Bolzano giltigheten av ett förslag i fråga om sanningen i en familj av relaterade förslag. Till skillnad från Tarski gör Bolzano sitt förslag till förslag i det språkliga, inte för meningar av ett formellt språk med en exakt definierad semantik.

I hela detta avsnitt, se även posten om logisk konsekvens.

4. Uttrycksstyrka

En mening (S) definierar sin klass (Mod (S)) av modeller. Med tanke på två språk (L) och (L ') kan vi jämföra dem genom att fråga om varje klass (Mod (S)), med (S) en mening med (L), är också en klass med formen (Mod (S ')) där (S') är en mening med (L '). Om svaret är Ja, säger vi att (L) kan reduceras till (L '), eller att (L') är minst lika uttrycksfullt som (L).

Till exempel om (L) är ett första ordens språk med identitet, vars signatur består av 1-ary predikatsymboler, och (L ') är det språk vars meningar består av de fyra syllogistiska formerna (Alla (A)) är (B), några (A) är (B), Nej (A) är (B), några (A) är inte (B)) med samma predikatsymboler, då är (L ') reducerbar till (L), eftersom de syllogistiska formerna är uttryckliga i första ordningens logik. (Det finns några grälar om vilket är det rätta sättet att uttrycka dem; se posten på det traditionella torget av oppositionen.) Men första ordningsspråket (L) är verkligen inte reducerbart till språket (L ') av syllogismer, eftersom vi i (L) kan skriva ner en mening som säger att exakt tre element uppfyller (Px), och det finns inget sätt att säga detta med bara de syllogistiska formerna. Eller flytta åt andra hållet,om vi bildar ett tredje språk (L '') genom att lägga till (L) kvantifieraren (Qx) med betydelsen "Det finns otaligt många element (x) så att …", då trivialt (L) är reducerbar till (L ''), men den nedåtgående Loewenheim-Skolem-teoremet visar på en gång att (L '') inte är reducerbar till (L).

Dessa idéer är användbara för att analysera styrkan hos databasfrågespråken. Vi kan tänka på de möjliga tillstånden i en databas som strukturer, och en enkel fråga om Ja / Nej blir en mening som framkallar svaret Ja om databasen är en modell av den och Nej annars. Om ett databasfrågespråk inte kan reduceras till ett annat kan den första uttrycka en fråga som inte kan uttryckas i den andra.

Så vi behöver tekniker för att jämföra språkens uttrycksfulla styrkor. En av de mest kraftfulla teknikerna som finns tillgängliga består av fram-och-tillbaka-spel från Ehrenfeucht och Fraïssé mellan de två spelarna Spoiler och Duplicator; se posten i logik och spel för mer information. Föreställ dig till exempel att vi spelar det vanliga första ordning fram och tillbaka spelet (G) mellan två strukturer (A) och (B). Teorin för dessa spel fastställer att om någon första ordningssats (phi) är sant i exakt en av (A) och (B), så finns det ett nummer (n) som kan beräknas från (phi), med egenskapen som Spoiler har en strategi för (G) som garanterar att han vinner i de flesta (n) steg. Omvänt, för att visa att första ordningens logik inte kan skilja mellan (A) och (B) räcker det att visa att för varje ändlig (n),Duplicator har en strategi som garanterar att hon inte tappar (G) i de första (n) stegen. Om vi lyckas visa detta följer det att alla språk som skiljer mellan (A) och (B) inte kan reduceras till strukturen i första ordningen i strukturerna (A) och (B).

Dessa fram och tillbaka-spel är oerhört flexibla. Till att börja med ger de lika mycket mening om ändliga strukturer som på oändliga; många andra tekniker i klassisk modellteori antar att strukturerna är oändliga. De kan också anpassas smidigt till många språk som inte är första ordningen.

1969 använde Per Lindström fram-och-tillbaka-spel för att ge några abstrakta karakteriseringar av första ordningens logik när det gäller dess uttrycksfulla kraft. En av hans teorem säger att om (L) är ett språk med en signatur (K, L) är stängd under alla första ordningens syntaktiska operationer, och (L) adderar den nedåtgående Loewenheim-Skolem-satset för enstaka meningar, och kompaktitetsteoremet, då (L) är reducerbar till första ordningsspråk för signatur (K). Dessa satser är mycket attraktiva; se kapitel XII i Ebbinghaus, Flum och Thomas för en bra redogörelse. Men de har aldrig helt uppfyllt sitt löfte. Det har varit svårt att hitta liknande karakteriseringar av andra logiker. Även för första ordningens logik är det lite svårt att se exakt vad karakteriseringarna berättar för oss. Men mycket grovt settde säger att första ordningens logik är den unika logiken med två egenskaper: (1) vi kan använda den för att uttrycka godtyckligt komplicerade saker om ändliga mönster, och (2) det är hopplöst att skilja mellan en oändlig kardinal och en annan.

Dessa två egenskaper (1) och (2) är bara egenskaperna i första ordningens logik som gjorde det möjligt för Abraham Robinson att bygga sin icke-standardiserade analys. Bakgrunden är att Leibniz, när han uppfann differentiell och integrerad kalkyl, använde oändliga siffror, dvs siffror som är större än 0 och mindre än alla 1/2, 1/3, 1/4 etc. Tyvärr finns det inga sådana verkliga siffror. Under 1800-talet omskrivs alla definitioner och bevis i Leibniz-stilen för att prata om gränser istället för oändliga mål. Låt nu (mathbb {R}) vara strukturen som består av fältet med verkliga siffror tillsammans med alla strukturella funktioner som vi vill ge namn på: säkert plus och tider, kanske beställningen, uppsättningen heltal, funktionerna syndar och logg osv. Låt (L) vara det första ordningsspråket vars signatur är (mathbb {R}). På grund av den uttrycksfulla styrkan hos (L) kan vi skriva ner valfritt antal ordsättningar som meningar av (L). På grund av den uttrycksfulla svagheten hos (L) finns det inget sätt att vi kan uttrycka i (L) att (mathbb {R}) inte har några oändliga mål. I själva verket använde Robinson kompaktitetsteoremet för att bygga en struktur (mathbb {R} ') som är en modell av exakt samma meningar av (L) som (mathbb {R}), men som har infinitesimals. Som Robinson visade kan vi kopiera Leibnizs argument med infinitesimalen i (mathbb {R} '), och så bevisa att olika teorier om beräkningen är sanna i (mathbb {R}'). Men dessa teorem är uttryckliga i (L), så de måste också vara sanna i (mathbb {R}).det finns inget sätt som vi kan uttrycka i (L) att (mathbb {R}) inte har några oändliga mål. I själva verket använde Robinson kompaktitetsteoremet för att bygga en struktur (mathbb {R} ') som är en modell av exakt samma meningar av (L) som (mathbb {R}), men som har infinitesimals. Som Robinson visade kan vi kopiera Leibnizs argument med infinitesimalen i (mathbb {R} '), och så bevisa att olika teorier om beräkningen är sanna i (mathbb {R}'). Men dessa teorem är uttryckliga i (L), så de måste också vara sanna i (mathbb {R}).det finns inget sätt som vi kan uttrycka i (L) att (mathbb {R}) inte har några oändliga mål. I själva verket använde Robinson kompaktitetsteoremet för att bygga en struktur (mathbb {R} ') som är en modell av exakt samma meningar av (L) som (mathbb {R}), men som har infinitesimals. Som Robinson visade kan vi kopiera Leibnizs argument med infinitesimalen i (mathbb {R} '), och så bevisa att olika teorier om beräkningen är sanna i (mathbb {R}'). Men dessa teorem är uttryckliga i (L), så de måste också vara sanna i (mathbb {R}).vi kan kopiera Leibnizs argument med infinitesimalen i (mathbb {R} '), och på så sätt bevisa att olika teorier om beräkningen är sanna i (mathbb {R}'). Men dessa teorem är uttryckliga i (L), så de måste också vara sanna i (mathbb {R}).vi kan kopiera Leibnizs argument med infinitesimalen i (mathbb {R} '), och på så sätt bevisa att olika teorier om beräkningen är sanna i (mathbb {R}'). Men dessa teorem är uttryckliga i (L), så de måste också vara sanna i (mathbb {R}).

Eftersom argument som använder infinitesimal vanligtvis är lättare att visualisera än argument som använder gränser är icke-standardanalys ett användbart verktyg för matematiska analytiker. Jacques Fleuriot i sin doktorsexamen avhandlingen (2001) automatiserade bevisteorin för icke-standardanalys och använde den för att mekanisera några av bevisen i Newtons Principia.

5. Modeller och modellering

Att modellera ett fenomen är att konstruera en formell teori som beskriver och förklarar det. I en nära besläktad betydelse modellerar du ett system eller en struktur som du planerar att bygga genom att skriva en beskrivning av det. Dessa är väldigt olika sinnen av 'modell' än den i modellteorin: fenomenets eller systemets 'modell' är inte en struktur utan en teori, ofta på ett formellt språk. Universellt modelleringsspråk, UML i korthet, är ett formellt språk utformat för just detta ändamål. Det rapporteras att den australiska marinen en gång anlitade en modellteoretiker för ett jobb "modellering av hydrodynamiska fenomen". (Snälla upplysa dem inte!)

Lite historia kommer att visa hur ordet 'modell' fick dessa två olika användningsområden. På sent latin var en "modellus" en mätanordning, till exempel för att mäta vatten eller mjölk. Genom språkens vagarier genererade ordet tre olika ord på engelska: mögel, modul, modell. Ofta ger en enhet som mäter en mängd av ett ämne också en form på ämnet. Vi ser detta med en ostform och även med metallbokstäverna (kallade 'moduli' i början av 1600-talet) som bär bläck till papper i tryck. Så "modell" avser ett objekt i handen som uttrycker utformningen av vissa andra föremål i världen: konstnärens modell bär den form som konstnären skildrar, och Christopher Wren "modul" i St Paul's Cathedral tjänar som vägledare för byggare.

Redan i slutet av 1600-talet kunde ordet "modell" betyda ett objekt som visar formen, inte av verkliga föremål, utan av matematiska konstruktioner. Leibniz skröt att han inte behövde modeller för att göra matematik. Andra matematiker använde gärna gips- eller metallmodeller av intressanta ytor. Modellerna av teorin framträdde först som abstrakta versioner av denna typ av modell, med teorier i stället för den definierande ekvationen för en yta. Å andra sidan kunde man stanna kvar med verkliga föremål men visa sin form genom en teori snarare än en fysisk kopia i handen; "modellering" bygger en sådan teori.

Vi har en förvirrande halvvägs situation när en forskare beskriver ett fenomen i världen med en ekvation, till exempel en differentiell ekvation med exponentiella funktioner som lösningar. Är modellen teorin som består av ekvationen, eller är dessa exponentiella funktioner själva modeller av fenomenet? Exempel av detta slag, där teori och strukturer väsentligen ger samma information, ger lite stöd för Patrick Suppes påstående att "innebörden av begreppet modell är densamma i matematik och empiriska vetenskaper" (sid 12 i hans citerade bok från 1969) Nedan). Flera vetenskapsfilosofer har drivit tanken på att använda en informell version av modellteoretiska modeller för vetenskaplig modellering. Ibland beskrivs modellerna som icke-språkliga - detta kan vara svårt att förena med vår definition av modeller i avsnitt 1 ovan.

Kognitiv vetenskap är ett område där skillnaden mellan modeller och modellering tenderar att bli suddig. En central fråga om kognitiv vetenskap är hur vi representerar fakta eller möjligheter i våra sinnen. Om man formaliserar dessa mentala representationer, blir de något som "modeller av fenomen". Men det är en allvarlig hypotes att våra mentala representationer faktiskt har en hel del gemensamt med enkla setteoretiska strukturer, så att de också är "modeller" i modellteoretisk mening. 1983 publicerades två påverkande verk av kognitiv vetenskap, båda under titeln Mental Models. Den första, redigerad av Dedre Gentner och Albert Stevens, handlade om människors "konceptualiseringar" av fysiska elementära fakta; det tillhör kvadratiskt i världen av "modellering av fenomen". Den andra, av Philip Johnson-Laird, handlar till stor del om resonemang,och gör flera överklaganden till 'modellteoretisk semantik' i vår mening. Forskare i Johnson-Laird-traditionen brukar hänvisa till deras tillvägagångssätt som 'modellteori' och se det som i någon mening förbundet med vad vi har kallat modellteori.

Bilder och diagram verkar först sväva i mellangrunden mellan teorier och modeller. I praktiken tar teoretiker ofta bilder av strukturer och använder bilderna för att tänka på strukturerna. Å andra sidan har bilder i allmänhet inte märkningen som är ett väsentligt inslag i modellteoretiska strukturer. Det finns ett snabbt växande arbete med resonemang med diagram, och den överväldigande tendensen med detta arbete är att se bilder och diagram som en form av språk snarare än som en form av struktur. Till exempel beskriver Eric Hammer och Norman Danner (i boken redigerad av Allwein och Barwise, se bibliografin) en "modellteori för Venn-diagram"; själva Venn-diagrammen är syntaxen, och modellteorin är en setteoretisk förklaring av deras betydelse.

Modellteoretikern Yuri Gurevich introducerade abstrakta tillståndsmaskiner (ASM) som ett sätt att använda modellteoretiska idéer för specifikation inom datavetenskap. Enligt webbplatsen Abstract State Machine (se andra internetresurser nedan),

vilken algoritm som helst kan modelleras på sin naturliga abstraktionsnivå av en lämplig ASM. … ASM: er använder klassiska matematiska strukturer för att beskriva tillstånden för en beräkning; strukturer är väl förståda, exakta modeller.

Börger och Stärks bok citerade nedan är en auktoritativ redogörelse för ASM: er och deras användning.

Idag kan du göra ditt namn och förmögenhet genom att hitta ett bra representationssystem. Det finns ingen anledning att förvänta sig att varje sådant system kommer att passa snyggt in i syntax / semantikramen i modellteori, men det kommer att vara förvånande om modellteoretiska idéer inte fortsätter att ge ett stort bidrag på detta område.

Bibliografi

Inledande texter

  • Doets, K., 1996, Basic Model Theory, Stanford: CSLI Publications.
  • Hodges, W., 1997, A Shorter Model Theory, Cambridge: Cambridge University Press.
  • Manzano, M., 1999, Model Theory, Oxford: Oxford University Press.
  • Rothmaler, P., 2000, Introduction to Model Theory, Amsterdam: Gordon and Breach.

Modellteoretisk definition

  • Frege, G., 1906, “Grundlagen der Geometrie”, Jahresbericht der deutschen Mathematikervereinigung, 15: 293–309, 377–403, 423–430.
  • Gergonne, J., 1818, “Essai sur la théorie de la définition”, Annales de Mathématiques Pures et Appliquées, 9: 1–35.
  • Hilbert, D., 1899, Grundlagen der Geometrie, Leipzig: Teubner.
  • Hodges, W., 2008, "Tarskis definitionsteori", i Patterson, D. New Essays on Tarski and Philosophy, Oxford: Oxford University Press, s. 94–132.
  • Lascar, D., 1998, “Perspective historique sur les rapports entre la théorie des modèles et l'algèbre”, Revue d'histoire des mathématiques, 4: 237–260.
  • Mancosu, P., Zach, R. och Badesa, C., 2009, "Utvecklingen av matematisk logik från Russell till Tarski", i L. Haaparanta (red.), The Development of Modern Logic, Oxford: Oxford University Press, s. 318–470.
  • Pasch, M., 1882, Vorlesungen über Neuere Geometrie, Berlin: Springer-Verlag.
  • Robinson, A., 1952, "Om tillämpning av symbolisk logik på algebra", Proceedings of the International Congress of Mathematicians (Cambridge, MA, 1950, bind 1), Providence, RI: American Mathematical Society, s. 686–694.
  • Suppes, P., 1957, "Theory of definition" i Introduction to Logic (kapitel 8), Princeton, NJ: Van Nostrand.
  • Tarski, A., 1954, "Bidrag till teorin om modeller, I", Indagationes Mathematicae, 16: 572–581.

Modellteoretisk konsekvens

  • Blanchette, P., 1996, "Frege och Hilbert om konsistens", The Journal of Philosophy, 93: 317–336.
  • Blanchette, P., 2012, Freges Conception of Logic, New York: Oxford University Press.
  • Boole, G., 1847, The Mathematical Analysis of Logic, Cambridge: Macmillan, Barclay och Macmillan.
  • Etchemendy, J., 1990, The Concept of Logical Consequence, Cambridge, MA: Harvard University Press.
  • Frege, G., 1971, On the Foundations of Geometry and Formal Theories of Arithmetic, E. Kluge (trans.), New Haven: Yale University Press.
  • Gómez-Torrente, M., 1996, "Tarski om logisk konsekvens", Notre Dame Journal of Formal Logic, 37: 125–151.
  • Hodges, W. 2004, "Betydelsen och försummelsen av begreppsanalys: Hilbert-Ackermann iii.3", i V. Hendricks et al. (red.), First Order Logic Revisited, Berlin: Logos, s. 129–153.
  • Kreisel, G., 1969, "Informell rigor och fullständighetsbevis", i J. Hintikka (red.), The Philosophy of Mathematics, London: Oxford University Press, s. 78–94.
  • Tarski, A., 1983, "On the concept of logical consequence", översatt i A. Tarski, Logic, Semantics, Metamathematics, J. Corcoran (red.), Indianapolis: Hackett, s. 409–420.
  • Van Benthem, J., 1991 [1983], The Logic of Time: A Model-Theoretetic Investigation into the Variants of Temporal Ontology and Temporal Discourse, Dordrecht: Reidel, 1983; andra upplagan, Springer, 1991.

Uttrycksfull styrka

  • Cutland, N., 2009, Nonstandard Analysis and its Applications, Cambridge: Cambridge University Press.
  • Ebbinghaus, H.-D. och Flum, J., 1999, Finite Model Theory, Berlin: Springer-Verlag.
  • Ebbinghaus, H.-D., Flum, J. och Thomas, W., 1984, Mathematical Logic, New York: Springer-Verlag.
  • Fleuriot, J., 2001, A Combination of Geometry Theorem Proving and Nonstandard Analysis, med tillämpning på Newtons Principia, New York: Springer-Verlag.
  • Immerman, N., 1999, Descriptive Complexity, New York: Springer-Verlag.
  • Libkin, L., 2004, Elements of Finite Model Theory, Berlin: Springer-Verlag.
  • Loeb, P. och Wolff, M. (red.), 2000, Icke-standardanalys för arbetsmatematikern, Dordrecht: Kluwer.
  • Robinson, A., 1967, "The metaphysics of the calculus", i Problem in the Philosophy of Mathematics, I. Lakatos (red.), Amsterdam: Nord-Holland, s. 28–40.

Modeller och modellering

  • Allwein, G. och Barwise, J. (red.), 1996, Logical Reasoning with Diagrams, New York: Oxford University Press.
  • Börger, E. och Stärk, R., 2003, Abstract State Machines: A Method for High-Level System Design and Analysis, Berlin: Springer-Verlag.
  • Fowler, M., 2000, UML Distilled, Boston: Addison-Wesley.
  • Garnham, A., 2001, Mental Models and the Interpretation of Anaphora, Philadelphia: Taylor and Francis.
  • Gentner, D. och Stevens, A. (red.), 1983, Mental Models, Hillsdale, NJ: Lawrence Erlbaum.
  • Johnson-Laird, P., 1983, Mental Models: Mot en kognitiv vetenskap om språk, inferens och medvetande, Cambridge: Cambridge University Press.
  • Meijers, A. (red.), 2009, Philosophy of Technology and Engineering Sciences, Amsterdam: Elsevier; se kapitel W. Hodges, "Funktionell modellering och matematiska modeller"; R. Müller, "Begreppet en modell, teorier om modeller och historia"; och N. Nersessian, "Modellbaserad resonemang inom tvärvetenskaplig teknik".
  • Moktefi, A. och Shin, S.-J. (red.), 2013, Visual Reasoning with Diagrams, Basel: Birkhäuser.
  • Morgan, MS och Morrison, M. (red.), 1999, Models as Mediators, Cambridge: Cambridge University Press.
  • Pullum, GK och Scholz, BC, 2001, "Om skillnaden mellan modellteoretiska och generativa-talräkningssyntaktiska ramverk", i Logical Aspects of Computational Linguistics (Lecture Notes in Computer Science: Volume 2099), P. De Groote et al. (red.), Berlin: Springer-Verlag, s. 17–43.
  • Stenning, K., 2002, Seeing Reason, Oxford: Oxford University Press.
  • Suppes, P., 1969, Studies in the Methodology and Foundations of Science, Dordrecht: Reidel.

Akademiska verktyg

sep man ikon
sep man ikon
Hur man citerar det här inlägget.
sep man ikon
sep man ikon
Förhandsgranska PDF-versionen av det här inlägget på SEP-samhällets vänner.
ino-ikon
ino-ikon
Slå upp det här ämnet vid Internet Philosophy Ontology Project (InPhO).
phil papper ikon
phil papper ikon
Förbättrad bibliografi för detta inlägg på PhilPapers, med länkar till dess databas.

Andra internetresurser

  • mentalmodelsblog: Mental Models in Human Thinking and Reasoning, av Ruth Byrne.
  • Algoritmisk modellteori, av E. Graedel, D. Berwanger och M. Hoelzel (Mathematische Grundlagen der Informatik, RWTH Aachen)
  • Abstract State Machines, av Jim Huggins