Back to search

University of Strathclyde

Induction and coinduction schemes in category theory

Abstract

dc:description.abstract

This thesis studies induction and coinduction schemes from the point of view of category theory. We start from the account of inductive and coinductive types given by initial algebra semantics and final coalgebra semantics, respectively. We then use fibrations as a generic setting describing a logic for a type theory to study induction and coinduction. As our starting point we consider the seminal work of Hermida and Jacobs [Her93, HJ98], who pioneered the fibrational approach. We extend their induction and coinduction schemes to give provably sound generic induction and coinduction schemes for arbitrary inductive and coinductive types. To achieve this we introduce the notion of a quotient category with equality (QCE) which i) abstracts the standard notion of a fibration of relations constructed from a given fibration and ii) gives us the correct structure to compare induction and coinduction from a categorical perspective. This allows us to broaden the applications of the coinduction scheme, as well as present the duality between coinduction and induction in a systematic way. Finally, we consider induction and coinduction schemes in the more general setting of fibred fibrations which is used to give sound, generic indexed induction and coinduction schemes for indexed inductive and coinductive types.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral-pg
Grantor dc:publisher.institution
University of Strathclyde
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fumex, Cle?ment

Rights

Identifiers

dc:identifier.*
Identifier
T13203

Chain of custody

source
Harvested from
University of Strathclyde
Base URL
stax.strath.ac.uk/catalog/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Fumex, Cle?ment. Induction and coinduction schemes in category theory. doctoral-pg thesis, University of Strathclyde, 2012. https://stax.strath.ac.uk/concern/theses/1c18df83h