Monadic and Higher-Order Structure

Simple type theories, ubiquitous in the study of programming language theory, augment algebraic theories with higher-order, variable-binding structure. This motivates the definition of higher-order algebraic theories to capture this structure, permitting the study of simple type theories in a categorical setting analogous to that of algebraic theories. The theory of higher-order algebraic theories is in one sense much richer than that of algebraic theories, as we may stratify the former according to their order: for instance, the first-order algebraic theories are precisely the classical algebraic theories, the second-order algebraic theories permit operators to abstract over operators, the third-order algebraic theories permit operators to abstract over operators that themselves abstract over operators, and so on. We study the structure of the category of (n + 1)th-order algebraic theories, demonstrating that it may be viewed as a construction on the category of nth-order algebraic theories, facilitating an inductive construction of the category of higher-order algebraic theories. In turn, this description leads naturally to a monad–theory correspondence for higher-order algebraic theories, subsuming the classical monad–theory correspondence, and providing a new, monadic understanding of higher-order structure. In proving the monad–theory correspondence for higher-order algebraic theories, we are led to reconsider the traditional perspective on the classical monad–theory correspondence. In doing so, we reveal a new understanding of the relationship between algebraic theories and monads that clarifies the nature of the correspondence. The crucial insight follows from the consideration of relative monads, which are shown to act as an intermediary in the correspondence. To support our proposal that this be viewed as the correct perspective of the monad–theory correspondence, we show how the same proof may be carried out in a formal 2-categorical setting. The classical monad–theory correspondence, as well as those in the literature for enriched and internal categories, then follow as corollaries of a general theory.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2022

Author dc:creator

• Arkor, Nathanael

Advisor dc:contributor.advisor

• Fiore, Marcelo

• category theory
• algebraic theories
• monads
• relative monads
• type theory
• 2-categories

Licence

• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.86347

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/338940