typeteori

Typeteori er en familie av formelle systemer som gir en ramme for å representere og manipulere matematiske objekter ved hjelp av typer. I stedet for å tilordne objekter direkte til setter, kobler type-systemet hver term til en type, og operasjoner må være konsistente med den typen. Dette bidrar til å unngå visse logiske paradoxer og gir et grunnlag for konstruktiv matematikk og formell verifikasjon. Varianter inkluderer enkle typer, avhengige typer og systemer med universer.

Historisk sett startet utviklingen med det enkle typed lambda-kalkulus av Alonzo Church, som innførte typer for å begrense definisjoner. Per Martin-Löf utviklet avhengige type teorier som en mer uttrykksfull plattform for matematikk. Videre utviklet Girard og Coquand Calculus of Constructions, og senere Calculus of Inductive Constructions, som danner grunnlaget for Coq. Av andre viktige systemer er Agda og Lean, som støtter avhengige typer og universer. Homotopy Type Theory (HoTT) bringer inn ideer fra topologi og homotopi, og endrer måten likheter mellom typer oppfattes på.

Typeteori har bred anvendelse i formell verifikasjon og bevisbygging, samt i teoretisk og konstruktiv matematikk. Curry–Howard-sammenhengen beskriver en korrespondanse mellom bevis og programmer: bevis er koder, og bevisprogrammer er koder som kjøres. Avhengige typer gjør det mulig å uttrykke egenskaper som avhenger av verdier, noe som er nyttig for å sikre programvare og matematiske bevis. Verdenskjente verifikasjonsverktøy som Coq, Agda og Lean bygger på slike typerystemer, og forskningen fortsetter å utforske universer, høyere induktive typer og forholdet mellom logikk og databehandling.