August 2008

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

My goals for this part of the course

At this point, we have seen examples of circularly-defined sets such as the set of streams the set of infinite trees One of the main goals of the course is to present a theory of how these “solution spaces” work. The theory is based on the concept of a coalgebra for a functor and on similar notions from category theory. This part of the course is a quick introduction to a few of the concepts which we’ll need. It is not a systematic presentation of the subject.

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

Categories A category C consists of 1

objects c, d, . . .

2

morphisms f , g , . . .. Each morphism has a domain and codomain. f : c → d means that c is the domain of f , and d is the codomain.

3

identity morphisms id a for all objects.

4

a composition operation: if f : a → b and g : b → c, then g · f : a → c.

subject to the requirements that Composition is associative. If f : a → b, then id b · f = f = f · id a .

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

Examples of Categories

We continue with several examples of categories including the category Set of sets. the category CMS of complete metric spaces. Of course, we’ll see constructions of “new categories from old” at several places as well.

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

The category Set

The objects of Set are the sets, and the morphisms are triples hx, y , f i where f : x → y . The domain of hx, y , f i is x, and the codomain is y . The identity morphism id a for a set a is ha, a, f i, where f is the identity function on a. The composition operation of morphisms is given by: hy , z, g i · hx, y , f i = hx, z, g · f i

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

The category Set

The objects of Set are the sets, and the morphisms are triples hx, y , f i where f : x → y . The domain of hx, y , f i is x, and the codomain is y . The identity morphism id a for a set a is ha, a, f i, where f is the identity function on a. The composition operation of morphisms is given by: hy , z, g i · hx, y , f i = hx, z, g · f i An alternative presentation of the category of sets would take as morphism the pairs hy , f i with y ⊇ {a : (∃b)hb, ai ∈ f }.

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

The category CMS

This is the category of complete metric spaces, with distances measured in [0, 1], and with non-expanding functions as morphisms: d(x, y ) ≥ d(fx, fy ). One reason for the use of [0, 1] is that this way the homsets CMS(X , Y )

=

{f : f is a continuous function from X to Y }

are again objects in the category, with d(f , g )

=

sup dY (f (x), g (x)). x∈X

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

Functors

Let C and D be categories. A functor from C to D consists of An object mapping a 7→ Fa, taking objects of C to objects of D. A morphism mapping f 7→ Ff , taking morphisms of C to morphisms of D. such that If f : a → b, then Ff : Fa → Fb. F id a = id Fa . F (f · g ) = Ff · Fg . A functor from C to itself is an endofunctor.

MATHLOGAPS 2008: Coalgebra and Circularity

Category Theory Background

The easiest examples

Let d be an object of D. We get F : C → D, the constant functor d by: Fc = d, Ff = id d .

The composition