# dirty-haskell.org: Exercises in Category Theory — 1.2

## It's not crazy — it's having fun with types.

Let be the category of objects where is a set, is a unary function, and is a nominated element and morphisms which are functions preserving the structure such that and .

1. Verify that is a category

1. For every there exists

on is indeed a function which preserves the structure (, ) and thus a morphism

2. There exists an associative partial binary operation on the arrows of

Given three objects and two functions and the function is an arrow in , that is to say, it preserves structure: and

2. Show that is a -object

is indeed a Set, is indeed an unary function and is indeed an element of .

3. Show that for each -object there is an unique arrow and describe the behaviour of the carrying function.

We construct a carrying function recursively: is indeed a morphism and thus an arrow.

Given two morphisms and we show that they are pointwise identical by induction over :
• Given :

The morphism maps to the transitive closure of under .

Consider objects of form where is a set and . For two such objects a morphism is a function that respects the selected subsets:

Show that such objects and morphisms form a category

1. For every there exists

on is indeed a function which respects the distinguished subset () and thus a morphism

2. There exists an associative partial binary operation on the arrows of

Given three objects and two functions and the function is an arrow in , that is to say, :

Consider pairs where is a set and is a binary relation on .

Show that these pairs are objects of a category finding a sensible notion of morphism.

For two such objects a morphism shall be a function that respects the binary relation: We call the category comprised of such objects and arrows .

1. For every there exists

on is indeed a function which respects the binary relation () and thus a morphism

2. There exists an associative partial binary operation on the arrows of

Given three objects and two functions and the function is an arrow in , that is to say, :

Topological spaces , where is a Set and , and continuous maps , that is , form a Category .

1. For every there exists

on is indeed a continuous map and thus a morphism

2. There exists an associative partial binary operation on the arrows of

Given three spaces and two continuous maps and the map is an arrow in , that is to say, it is contiuous:

Show that is a monoid under composition, where is an object of a category .

is associative and total on by the definition of category and is obviously closed under .

is required to exist by the definition of category and indeed an identity of on .

Each monoid is a category (again).

We construct a category with exactly one object and associate to every element an arrow . We further define .

Show that in is associative.

Consider the composition of two partial functions and : where all restricted versions of , , and are total.

Extending the above to three partial functions , , and :

Consider the category of pointed sets.

Show that and are “essentially the same” category.

The idea is to identify the undefined parts of a partial functions image with : where is total.

Verify that for every monoid both and are categories of structured sets.

Since the two proofs are perfectly analogous we cover only the case .

1. For every -Set there exists

on is indeed a structure preserving function ().

2. There exists an associative partial binary operation on the arrows of

Given three R-Sets , , and and two continuous maps and the map is an arrow in , that is to say :

The format of the proof was chosen to demonstrate that is indeed a structured set.