4.3 Modellteori — tolkningsfunksjon, ordnede par og evaluering

$$M = \langle D, F\rangle$$

Her er $D$ domenet — tingene som finnes i situasjonen — og $F$ er tolkningsfunksjonen, som sier hva hvert symbol i språket viser til i denne situasjonen.

Hvorfor dette er nødvendig. I kap. 4.1 skrev vi formler, men vi kunne ikke regne ut sannhetsverdien deres. En formel er sann eller usann i forhold til en situasjon, og for å regne på den trenger vi situasjonen beskrevet like presist som formelen. Modellen er den beskrivelsen.

Merk at vinkelparentesene $\langle\ \rangle$ er reservert i denne boka: de brukes om ordnede par, og modellen er nettopp et ordnet par av domene og tolkningsfunksjon. Rekkefølgen er fast — domenet først, tolkningsfunksjonen sist.

Et domene kan være hva som helst, og det er som regel lite i en oppgave:

$$D = \{\text{Arne}, \text{Bea}, \text{Cato}\}$$

Domenet er det kvantorene løper over. Dette er svaret på spørsmålet som ble stående åpent i kap. 4.1: når $\forall x$ sier «for alt», er det alt i $D$ som menes — ikke alt i universet. Utenfor domenet finnes ingenting, sett fra modellens synspunkt.

Praktisk konsekvens: et domene med tre elementer betyr at enhver kvantorpåstand kan avgjøres ved å prøve tre ting. Det er derfor modelloppgaver er mekaniske — de er alltid endelige.

Den delen av modellen som sier hva hvert symbol viser til. Den engelske termen er ‘interpretation function’, og symbolet er $F$.

Tolkningsfunksjonen gjør tre slags jobber:

- Konstanter får hvert sitt individ i domenet: $F(a) = \text{Arne}$.
- Ettplasspredikater får en mengde av individer: $F(S) = \{\text{Arne}, \text{Cato}\}$.
- Toplasspredikater får en mengde av ordnede par: $F(K) = \{\langle \text{Arne}, \text{Bea}\rangle\}$.

Uten tolkningsfunksjonen er formelen bare tegn. $S(a)$ sier ingenting før noen har sagt hvem $a$ er og hva $S$ omfatter. Tolkningsfunksjonen er det som knytter språket til situasjonen — og det er nettopp den knytningen semantikken handler om, helt tilbake til referansebegrepet i kap. 1.2.

Merk at $F$ er en funksjon, ikke en liste. Hvert symbol får nøyaktig én verdi. Det er denne egenskapen Zimmermann & Sternefeld bygger videre på, og som behandles i løkke 4.

Verdien tolkningsfunksjonen gir en individkonstant: ett bestemt individ i domenet.

$F(a) = \text{Arne}$ leses «$a$ viser til Arne».

To ting er verdt å merke seg. For det første må hver konstant få en verdi — en konstant uten tolkning gjør formelen uavgjørbar. For det andre kan to konstanter godt vise til det samme individet: en modell der $F(a) = F(b) = \text{Arne}$ er helt lovlig, og da er $a = b$ sann i den modellen.

Det siste er ikke en spissfindighet. Det er nettopp hva som gjør identitetspåstander informative, og det er bakgrunnen for Freges problem med sense og reference i kap. 1.2: to uttrykk kan vise til det samme uten at det er opplagt at de gjør det.

En samling av ting, skrevet mellom krøllparenteser: $\{\text{Arne}, \text{Cato}\}$. Den engelske termen er ‘set’.

Tre egenskaper er verdt å ha friskt fra kap. 3.4:

- Rekkefølgen inni betyr ingenting. $\{\text{Arne}, \text{Cato}\}$ og $\{\text{Cato}, \text{Arne}\}$ er samme mengde.
- Gjentakelser teller ikke. Et individ er enten med eller ikke med.
- En mengde er fullstendig bestemt av medlemmene sine.

Merk kontrasten som kommer i løkke 2: i en mengde er rekkefølgen likegyldig, men i et ordnet par er den avgjørende. Det er nettopp derfor relasjoner tolkes med par og ikke med mengder.

Relasjonen mellom en ting og en mengde den hører til i. Symbolet er $\in$, og den engelske termen er ‘membership’.

$\text{Arne} \in \{\text{Arne}, \text{Cato}\}$ er sann. $\text{Bea} \in \{\text{Arne}, \text{Cato}\}$ er usann.

Dette er hele avlesningsmekanismen i kapitlet. Enhver atomær formel avgjøres av ett medlemskapsspørsmål, og alt annet bygges opp av det. Kan du svare på «ligger denne tingen i denne mengden», kan du evaluere enhver formel i en endelig modell.

Skrivemåten i et svar: skriv medlemskapet ut, ikke bare konklusjonen. «$F(a) = \text{Arne}$, og $\text{Arne} \in F(S)$, altså er $S(a)$ sann» er et fullstendig oppslag. «$S(a)$ er sann» alene er et gjettet svar med riktig fasit.

Mengden av alle individene i domenet som predikatet er sant om. Den engelske termen er ‘extension’.

$F(S) = \{\text{Arne}, \text{Cato}\}$ betyr at Arne og Cato synger, og at Bea ikke gjør det.

Legg merke til at mengden sier alt. Det som ikke står i $F(S)$, er ikke $S$. Modellen er fullstendig: den lar ingenting stå åpent. Det er en av grunnene til at modell-evalueringer alltid har fasit.

Ekstensjonsbegrepet er ikke nytt. Du møtte det i kap. 1.2: ekstensjonen er mengden uttrykket gjelder for, intensjonen er betingelsen som avgjør ekstensjonen. Modellteorien her arbeider utelukkende med ekstensjoner — den oppgir hvem som faktisk synger, ikke hva det vil si å synge.

Regelen om at alt som ikke står i en ekstensjon, er usant i modellen. Modellen lar ingenting stå åpent.

Står $F(S) = \{\text{Arne}, \text{Cato}\}$, så synger ikke Bea. Ikke «vi vet ikke om hun synger» — hun synger ikke.

Dette er grunnen til at modell-evalueringer alltid har fasit. Du kan lese negative svar rett ut av modellen uten å lete videre og uten å ta forbehold. En modell er ikke en ufullstendig rapport om verden; den er situasjonen, ferdig beskrevet.

Praktisk konsekvens: når du har slått opp og ikke funnet det du lette etter, er du ferdig. Svaret er usann, og det trenger ingen tilleggsbegrunnelse ut over oppslaget.

Mengden uten medlemmer, skrevet $\{\ \}$ eller $\emptyset$.

Et predikat kan godt ha tom ekstensjon: $F(S) = \{\ \}$ betyr at ingen synger i denne modellen.

Dette er verdt å øve på, for det er der de fleste hopper over et oppslag. Er $F(S)$ tom, er:

- $\exists x\,S(x)$ usann — det finnes ingenting å finne.
- $\forall x\,S(x)$ usann, forutsatt at domenet ikke er tomt.
- $\forall x\,(S(x) \rightarrow \varphi)$ derimot sann, uansett hva $\varphi$ er. Hver eneste implikasjon har usann antesedent og er sann av tom sannhet, akkurat som i kap. 3.1.

Det siste punktet er den enkeltraden som overrasker flest, og det er derfor det er verdt å ha sett den skrevet ut på forhånd.

To ting satt sammen i en bestemt rekkefølge, skrevet med vinkelparenteser: $\langle a, b\rangle$. Den engelske termen er ‘ordered pair’.

Forskjellen fra en mengde er hele poenget:

- $\{a, b\}$ og $\{b, a\}$ er samme mengde.
- $\langle a, b\rangle$ og $\langle b, a\rangle$ er ulike par.

Ordnede par finnes fordi relasjoner har retning. «Arne kjenner Bea» og «Bea kjenner Arne» er to forskjellige påstander, og en tolkning av kjenner må kunne skille dem. En mengde kan ikke; et par kan.

Dette er den samme innsikten som argumentrekkefølgen i kap. 4.1, sett fra tolkningssiden. Der handlet den om formelen; her handler den om hva formelen viser til.

$$\langle a, b\rangle \neq \langle b, a\rangle$$

At $\langle \text{Arne}, \text{Bea}\rangle \in F(K)$, sier ingenting om hvorvidt $\langle \text{Bea}, \text{Arne}\rangle$ også er der. De to må sjekkes hver for seg.

Bildet som hjelper: tegn relasjonen som piler. Et par er en pil fra det første til det andre elementet. En pil peker én vei, og at det går en pil fra Arne til Bea, betyr ikke at det går en tilbake.

Kontrollen i en besvarelse: når du evaluerer $K(b,a)$, skriv eksplisitt hvilket par du leter etter — «jeg spør om $\langle \text{Bea}, \text{Arne}\rangle \in F(K)$» — før du slår opp. Skriver du paret ned i riktig rekkefølge, har du allerede gjort det vanskeligste.

$$F(K) = \{\langle \text{Arne}, \text{Bea}\rangle, \langle \text{Bea}, \text{Cato}\rangle\}$$

Dette betyr: Arne kjenner Bea, og Bea kjenner Cato. Alt annet er usant. Arne kjenner ikke Cato, Cato kjenner ingen, og ingen kjenner seg selv.

Merk hvor mye modellen sier ved å tie. To par er oppgitt; i et domene med tre individer finnes det ni mulige par. De sju som ikke står der, er dermed usanne. Modellen er fullstendig, og det er derfor du kan lese negative svar rett ut av den.

Praktisk telling: med $n$ individer i domenet finnes det $n^2$ mulige ordnede par, siden hvert individ kan stå i begge plasser, også sammen med seg selv. For $n = 3$ blir det ni.

Prosessen der en formels sannhetsverdi regnes ut mot en modell. Den engelske termen er ‘evaluation’.

Ordet er verdt å ha presist, for det navngir nettopp den ferdigheten oppgavetypen prøver. Du tolker ikke formelen og vurderer den ikke — du regner den ut, med faste regler, i en bestemt rekkefølge.

Evalueringen har alltid tre bestanddeler: en formel, en modell, og et resultat som er sann eller usann. Mangler én av dem, er spørsmålet ikke velformet. «Er $S(a)$ sann?» er ikke et spørsmål før noen har oppgitt modellen.

$$\llbracket \alpha \rrbracket$$

Den engelske termen er ‘denotation’, og $\alpha$ er en plassholder for et vilkårlig uttrykk.

For en konstant er denotasjonen et individ: $\llbracket a \rrbracket = \text{Arne}$. For en hel formel er den en sannhetsverdi: $\llbracket S(a) \rrbracket = \text{sann}$.

Denotasjonsklammene er reservert for nettopp dette i hele boka. De skal ikke brukes om noe annet, og de skal ikke forveksles med vinkelparentesene $\langle\ \rangle$, som er ordnede par, eller med krøllparentesene $\{\ \}$, som er mengder. Tre klammetyper, tre jobber.

Praktisk merknad: i en besvarelse holder det som regel å skrive «$S(a)$ er sann i $M$». Klammene er nyttige når du vil snakke om verdien som en ting — «denotasjonen til $a$ er Arne» — og du bør kjenne dem igjen, siden pensumlitteraturen bruker dem gjennomgående.

En formel er sann i en modell når evalueringsreglene gir den verdien sann i akkurat den modellen. Den engelske termen er ‘true in a model’.

Dette er en relativ egenskap, og det er selve poenget. Ingen formel er sann uten videre; den er sann i noen modeller og usann i andre. $S(a)$ er sann i vår modell og usann i en modell der Arne ikke synger.

Merk skillet til entailment fra kap. 3.2. Entailment er en påstand om alle modeller: $p \vDash q$ betyr at $q$ er sann i hver eneste modell der $p$ er sann. Sannhet i en modell er en påstand om én. Boka bruker derfor $\vDash$ bare om entailment, aldri om sannhet i en enkelt modell — de to er ulike ting, og kap. 3.2 handlet nettopp om å ikke blande dem.

Framgangsmåten for sammensatte formler: regn ut de minste delene først, og sett dem sammen utover.

Slik gjør du det:

- Finn hovedkonnektivet — det som binder formelen sammen på øverste nivå. Framgangsmåten er den samme som i kap. 3.1: se bort fra alt i parentes, og se hva som blir stående igjen.
- Regn ut hver atomær delformel med et fullstendig oppslag.
- Sett sammen med sannhetstabellen for hovedkonnektivet.

Mellomtrinnene skal stå i svaret. De er ikke rot — de er dokumentasjon på framgangsmåten, og de er nøyaktig det samme som mellomkolonnene i en sannhetstabell. Et svar uten dem kan ikke kontrolleres, og et ukontrollerbart svar er et gjettet svar.

Denne oppbyggingen har et navn i faget: den er en anvendelse av kompositsjonalitetsprinsippet, som sier at betydningen til en helhet bestemmes av betydningen til delene og måten de er satt sammen på. Prinsippet behandles for seg i kap. 7.1.

Regelen som knytter kvantorene til modellen: $\forall x$ og $\exists x$ løper over domenet $D$, og ingenting annet.

$\forall x\,S(x)$ spør ikke om alt i universet synger. Den spør om alt i denne modellens domene gjør det — her: om Arne, Bea og Cato alle synger.

Dette er svaret på spørsmålet kap. 4.1 lot stå åpent. Der sa vi at kvantorene alltid løper over noe, og at det noe er gitt av sammenhengen. Nå er sammenhengen gjort presis: den er domenet i modellen.

Praktisk konsekvens: et endelig domene gjør enhver kvantorpåstand avgjørbar ved å prøve hvert individ. Med tre individer er en $\forall$-påstand tre oppslag, og en $\exists$-påstand er høyst tre.

Framgangsmåten for å evaluere en kvantorformel i en endelig modell: prøv hvert individ i domenet etter tur.

Slik gjør du det:

- For $\forall x\,\varphi$: sett inn hvert individ i domenet for $x$, evaluer $\varphi$ hver gang, og krev at alle går igjennom.
- For $\exists x\,\varphi$: gjør det samme, men stopp så snart ett individ går igjennom.

Metoden virker fordi domenet er endelig og hvert individ har et navn i oppgaven. Det er alltid tilfellet i eksamensoppgaver, og det er derfor denne enkle framgangsmåten holder. En helt generell definisjon av kvantorer trenger et mer omstendelig apparat, men det er langt utenfor det et innføringsemne krever.

Skrivemåten i et svar: før opp hvert individ på egen linje med utfallet. En kvantorevaluering uten den listen er et gjettet svar, og listen er samtidig det som gjør svaret ditt kontrollerbart.

Framgangsmåten når en formel har to kvantorer inni hverandre, som $\forall x\,\exists y\,K(x,y)$.

Regelen er: den ytterste kvantoren velger først, og den innerste prøves på nytt for hvert valg den ytterste gjør.

Konkret, med tre individer i domenet:

- Velg det første individet for $x$. Prøv deretter alle tre for $y$, og se om minst én går igjennom.
- Gjenta for det andre individet, og for det tredje.
- Samle opp: allkvantoren ytterst krever at alle de tre rundene går igjennom.

Dette er scope-mekanikken fra kap. 4.2 gjort til en utregning. Der forklarte vi hvorfor $\forall x\,\exists y$ og $\exists y\,\forall x$ betyr ulike ting; her ser du forskjellen i praksis, som to ulike gjennomganger av det samme domenet.

Skrivemåten i et svar: før den ytterste gjennomgangen som en liste, og skriv utfallet av den innerste på hver linje. Da ser leseren begge lagene.

En funksjon er en regel som gir nøyaktig én verdi for hvert argument den får inn. De engelske termene er ‘function’, ‘argument’ og ‘value’.

Tolkningsfunksjonen $F$ er et eksempel: gir du den symbolet $a$, får du individet Arne. Argumentet er $a$, verdien er Arne.

Ordet «argument» brukes i to betydninger i dette emnet, og de må holdes fra hverandre.

- I predikatlogikken er et argument det som fyller en plass i et predikat: i $K(a,b)$ er $a$ og $b$ argumenter.
- I funksjonsteorien er et argument det en funksjon får inn.

De to henger sammen — et predikat kan oppfattes som en funksjon som tar sine argumenter inn — men ordet brukes altså på to nivåer. Zimmermann & Sternefeld bygger hele framstillingen sin på funksjonsbegrepet, og dette apparatet er prøvd i 1 av de 12 settene, høsten 2018.

Zimmermann & Sternefelds måte å beskrive det samme apparatet på: et ettplasspredikat er en funksjon fra individer til sannhetsverdier.

I stedet for å si at $F(S)$ er mengden $\{\text{Arne}, \text{Cato}\}$, kan man si at $S$ er en funksjon som gir sann for Arne, usann for Bea og sann for Cato.

De to beskrivelsene sier nøyaktig det samme. Å oppgi hvilke individer en funksjon gir sann for, er å oppgi en mengde; å oppgi en mengde, er å si hvilke individer funksjonen gir sann for. Mengdeversjonen er lettere å regne med for hånd; funksjonsversjonen er lettere å bygge videre på når betydninger skal settes sammen.

Tilsvarende for toplasspredikater: en relasjon kan oppfattes som en funksjon fra ordnede par til sannhetsverdier, eller som en funksjon som tar ett argument om gangen og gir en ny funksjon tilbake.

Hvorfor dette er verdt å kjenne: funksjonsversjonen er det som gjør kompositsjonalitetsprinsippet i kap. 7.1 presist. Der er spørsmålet hvordan betydningen til en helhet bygges av delene, og funksjoner er svaret: en del er en funksjon som tar en annen del som argument.

En modell der en formel får motsatt verdi av den den hadde i modellen du startet med. Å kunne konstruere en, er trinn tre i den formelle føringen.

Framgangsmåten er enkel: finn ut hvilket oppslag som avgjorde svaret, og endre nettopp det.

- Var formelen usann fordi ett individ veltet en $\forall$-påstand, legg det individet inn i den mengden som manglet.
- Var den sann fordi ett individ reddet en $\exists$-påstand, ta det individet ut.

Å oppgi en motmodell er den mest overbevisende måten å vise at du har forstått hva du regnet. Det viser at du vet hvilket oppslag som bar hele svaret, og ikke bare at du fikk riktig verdi ut.

Merk sammenhengen med entailment fra kap. 3.2: et moteksempel mot en entailment-påstand er nettopp en modell der premisset er sant og konklusjonen usann. Det er samme grep, brukt på en påstand om alle modeller i stedet for på én formel.