KNAW

Research

Categorical logic and proof theory: realizability for constructive theories

Pagina-navigatie:


Update Research data


Title Categorical logic and proof theory: realizability for constructive theories
Period 05 / 2003 - 05 / 2006
Status Completed
Research number OND1297331
Data Supplier Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)

Abstract

Realizability is one of the most important methods of proof theory. It plays a particularly relevant role in the study of constructive theories. A number of proof theoretic results about constructive theories have been obtained indeed by direct application of realizability. One of the key events in the development of realizability has been the connection between categorical logic for toposes and realizability interpretations for constructive analysis. At present, such a fruitful connection is not available for many important constructive theories. The proposed research aims to extend and to apply the categorical approach to realizability to a wide class of constructive theories for which realizability has not yet been investigated. The considered class of theories spans across the settings of set theory and type theory and includes some of the most important constructive theories, such as Aczel-Myhill set theories. The first main goal of the proposed research is to obtain a categorical account of realizability interpretations for this class of theories. This will initially involve obtaining realizability interpretations for constructive set theories and type theories. The second main goal of the proposed research is to obtain a number of proof theoretic results by direct applications of realizability. These include relative consistency and independence results. One example of the former is to prove that the consistency of constructive set theory implies the consistency of its extension with Markov's principle. Examples of the latter are open problems on notions of real number in constructive set theory.

Abstract (NL)

In het kader van dit project wordt onderzoek gedaan naar bepaalde zogenaamde constructieve logische systemen, met name de typentheorie van de Zweedse logicus en wiskundige Martin-Loef. Een belangrijk kenmerk van deze logische systemen is dat een wiskundig bewijs dat binnen zo n systeem is geformaliseerd ook meteen een expliciet algoritme levert voor de constructie van de in zo n bewijs voorkomende objecten. De logische eigenschappen van Martin-Loef typentheorie verschillen nogal van die van de -klassieke- logica waarmee een wiskundige gewoonlijk werkt. Om deze speciale eigenschappen, en de verbanden met andere logische systemen, beter te begrijpen maken wij -modellen- van universa van wiskundige objecten die zich gedragen volgens de beschrijving van de typentheorie. Hiertoe worden technieken gebruikt uit de theorie van categorieën, uit de theorie van schoven en uit de recursietheorie. Het project besteedt speciaal aandacht aan het construeren van inductieve en co-inductieve typen

Related organisations

Related people

Researcher Drs. F. de Marchi
Project leader Prof.dr. I. Moerdijk

Classification

A90000 Fundamental research
D11100 Logic, set theory and arithmetic

Go to page top
Go back to contents
Go back to site navigation