01whole.pdf (585.04 kB)
Catalan objects in categories
thesisposted on 2022-03-28, 09:22 authored by Geoff Edington-Cheater
The Catalan numbers 1, 2, 5, 14, 42, 132, . . . count all sorts of interesting objects: for example, thenth Catalan number enumerates both the set of Tn of rooted finitely branching trees with n + 1 vertices, and the set Bn of rooted binary trees with n + 1 leaves. In fact for each n, the sets Tn and Bn are in bijection in a natural way. The objective of this thesis is to study these bijections, and similar ones, through the lens of category theory. The set of rooted finitely branching trees can be characterised as an initial motor; where a motor is a monoid endowed with a endofunction (not preserving the monoid structure). The set of rooted binary trees can be characterised as an initial pointed magma; where a pointed magma is a set endowed with a constant and a binary operation. We first give an account of the bijection between rooted trees and binary trees which uses only the universal properties of the initial motor and the initial pointed magma. We then generalise this in various directions; our most general result identifies the initial T -motor with the initial pointed T -magma, when T is an arbitrary endofunctor of a closed monoidal category C ; here, a T -motor is a monoid X endowed with a mapping T X X , while a pointed T -magma is an object with a map I + TX ⊗ X X. We will also give numerous examples and applications.