Den Calculus av Constructions är en högre ordning formalism för att skriva konstruktiva bevis i en naturlig slutledning stil, inspirerad av arbete av de Bruijn [2, 3], Girard [12], och Scott [18]. Analysen och dess syntaktiska teori presenterades i Coquands avhandling [7], och ett genomförande av författaren användes för att mekaniskt verifiera ett stort antal bevis som visar kraften i uttryck av formalismen [9]. Konstruktionskalkylen föreslås som en grund för utformningen av programmeringsmiljöer där program utvecklas konsekvent med formella specifikationer. Det aktuella dokumentet visar hur man definierar induktiva begrepp i kalkylen. En mycket allmän induktion schema erhålls genom att postulera alla delar av den typ av intresse att tillhöra standardtolkningen i samband med en predikat karta. Detta liknar behandlingen av D. Park [16], men kraften att uttrycka formalismen tillåter en mycket direkt behandling, på ett språk som formaliseras tillräckligt för att faktiskt genomföras på datorn. Särskilda fall av induktionsschema specialiserat på noeterisk induktion och strukturell induktion över någon algebraisk typ. Beräkningsinduktion behandlas i en axiomatisering av domänteorin i konstruktioner. Det hävdas att den resulterande principen är mer kraftfull än LCF:s [13], eftersom begränsningen av tillåtlighet är uttrycklig på objektspråket. Vi antar att läsaren är bekant med analys av konstruktioner, som presenteras i [7, 9, 10, 11]. Närmare bestämt ska vi i detta dokument använda det utvidgade system som definieras i avsnitt 11 i [8]. Notationen [x : A]B står för algoritmen med formell parameter x av typ A och kropp B, medan (x : A)B står för produkten av typ B indexerad av x sträcker sig över A. Därför används hakparenteser för λ-abstraktion, medan parenteser står för produktbildning. Atomen P rop är den typ av logiska förslag. Atomen T ype står för den första nivån i den predikativa hierarkin av typer (och därmed har vi P rop : T ype). Vi förkortar (x : A)B till A → B när x inte förekommer i B. När B : P rop, vi tänker på (x : A)B som den universellt kvantifierade proposition x : A·B. När x inte förekommer i B och A: P rop,
I tidig version av analysen av konstruktioner, formaliseringar av Tarskis minsta fixpunkt teorem användes också för att visa hur induktiva definitioner kunde kodas direkt i den rena (impredikativa) analysen av konstruktioner REF.
Induction principles formalized in the Calculus of Constructions
{'venue': 'Programming of Future Generation Computers. Elsevier Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}