Post-Doctoral Research Visit F/M Symmetric foundations of type theory

Type de contrat : CDD

Contrat renouvelable : Oui

Niveau de diplôme exigé : Thèse ou équivalent

Fonction : Post-Doctorant

The job is within the framework of the Malinca project (http://malinca.org). It will be located at the IRIF lab in Paris.

Travel expenses are covered within the limits of the scale in force.

Dependent type theory, which is at the heart of several proof assistants, such as Agda, Lean, Rocq, is traditionally based on the "natural deduction" formalism, equipped with universes and dependent elimination of positive connectives. In the absence of those last two features, it is known that natural deduction is only one formal approach among others, besides e.g. sequent calculus and axiomatic systems. Among these last two approaches, sequent calculus has the particularity to spontaneously exhibit symmetries.

There is a three-way "Curry-Howard-Lambek" correspondence between proofs of natural deduction, programs of lambda-calculus and morphisms of cartesian closed categories. On its side, the symmetry of sequent calculus echo the value/stack symmetry of abstract machines in programming. An associated three-way correspondence with category theory is currently emerging, adding the symmetry of adjunctions to the picture.

The symmetry of sequent calculus directly leads to a smooth integration of classical logic into the realm of computation. Classical logic features are also at work in choice axioms: a standard way to express the axiom of choice in type theory is as a commutation of quantification with propositional truncation, which directly relates to the subclassical "double negation shift" principle.

The objective of the post-doc is to explore how to combine the above observations into a more general picture. In particular, it intends:

• to clarify the emerging three-way Curry-Howard-Lambek-style correspondence between sequent calculus, abstract machines and adjunctions
• to explore type theory in forms different than natural deduction, namely sequent calculus or axiomatic style, paving the way to more symmetries between hypotheses and conclusions in the presentation of type theory and a tighter connection to category theory
• to eventually add classical logic as a dualisation principle and choice principles as shift principles to the picture
• to explore the impact of the results on the design of type-theoretic proof assistants

Expertise expected in type theory, structural proof theory and category theory.

Familiarity with the question of computing with the axiom of choice welcomed.

Familiarity with proof assistants also welcomed.

Fluency in French or English recommended.

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
• Possibility of teleworking and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

Attention: Les candidatures doivent être déposées en ligne sur le site Inria. Le traitement des candidatures adressées par d'autres canaux n'est pas garanti.