Maths - Category Theory - Universal Constructions

Here we look at properties of categories that are common across all concrete categories from different branches of mathematics. As discussed earlier we are trying to find the properties of a category from its external interactions and universal properties give us a way to do this. In particular we may be looking for unique arrows (morphisms) that have some particular property.

In universal properties there is a unique isomorphism somewhere, this gives the 'best' of such a property.

Universal constructions happen in dual pairs:

Limits and Colimits

This is a generalisation that includes:

  • initial/terminal objects
  • (co)products
  • (co)equalizers
  • pullbacks/pushout.
heirchy

Linked to the ideas of universal properties and adjoint functions

(Co)Limits add two vertices to a given diagram:

So this arrow must be unique together with the condition that the various triangles formed with the pre-existing diagram must commute and any requirements of the existing diagram must be met.

  universal cone over diagram:
Initial/terminal

empty diagram

empty diagram

product/sum ab diagram
pullback/pushout abc diagram
(co)equaliser parallel diagram

Cone and Cocone

This is also called a wedge. For a given pair there may be many wedges. We look for a 'best possible' wedge .

example: highest common factor.

A cone/cocone can be added on to an existing diagram.

cone diagram

  Cone Cocone
A cone/cocone is defined by the tuple: (X,f,g). cone cocone
We can give this a universal property if, for other tuples (Xi,fi,gi), there is an arrow m known as the mediating arrow. This makes (X,f,g), in some way, the 'best' for that construction. cone 2 cocone 2
Example in set

union

cone set

intersection

cocone set

     

Initial and Terminal Objects

These are related to the identity elements of an algebra.

In some cases (group, vectors) an object is both initial and terminal, in this case it is called a zero object or null object.

Terminal objects give a category theory version of the concept of 'element' in set theory. 1 -> A allows us to pick out an arbitrary element of the set.

  Terminal Initial
  terminal arrow category initial arrow category
Notation 1 0
generalisation a kind of limit a kind of colimit
universal cone over diagram

empty diagram empty diagram

examples: set:

{1}or {a} ...

set with one element (singleton)

Ø = {}

empty set

group (null object) trivial group (just identity element) trivial group (just identity element)
topological space single point empty space
poset greatest element (if exists) least element (if exists)
monoid trivial monoid (consisting of only the identity element) trivial monoid
semigroup singleton semigroup empty semigroup
Rng trivial ring consisting only of a single element 0=1 ring of integers Z
fields does not have terminal object does not have initial object
Vec zero object zero object
Top one-point space empty space
Grf graph with a single vertex and a single loop the null graph (without vertices and edges)
Ω-Alg
algebra with signature Ω
  initial (term) algebra whose carrier consists of all finite trees.
Cat category 1 (with a single object and morphism) empty category

Equaliser and Coequaliser

every subset of a set occurs as an equaliser.

  Equaliser Coequaliser
universal cone over diagram

parallel diagram

 

equaliser

An equaliser is an arrow 'h' which makes 'f' and 'g' equal.

coequaliser

A Coequaliser is an arrow 'h' which makes 'f' and 'g' equal.

Universal Property:

'k' is a unique arrow known as the mediator.

this is equivalent to the following diagrams commuting

equaliser 2

that is:
j = f•h = g•h

 
  equaliser is monic (injective) coequaliser is epic
     
     
     
     

Product and Sum

 

Product
(pullback)

More on this page

Sum
(Coproduct)
(pushout)

More on this page

universal cone over diagram

ab diagram

  product arrow category sum arrow category
generalisation a kind of limit a kind of colimit
set example

cartesian product

product set

{a,b,c}*{x,y}=
{{a,x},{b,x},{c,x},{a,y},{b,y},{c,y}}

disjoint union

sum of set

{a,b,c}+{x,y}=
{a,b,c,x,y}

group the product is given by the cartesian product with multiplication defined componentwise. free product
the free product for groups is generated by the set of all letters from a similar "almost disjoint" union where no two elements from different sets are allowed to commute.
Grp (abelian) direct sum

direct sum
consists of the elements of the direct product which have only finitely many nonzero terms (this therefore coincides exactly with the direct product, in the case of finitely many factors)

the group generated by the "almost" disjoint union (disjoint union of all nonzero elements, together with a common zero)

vector space direct sum direct sum
poset greatest lower bound
meet
least upper bound
join
base topological space   wedge
POS

greatest lower bounds (meets)

least upper bounds (joins)

Rng    
Top the space whose underlying set is the cartesian product and which carries the product topology disjoint unions with their disjoint union topologies
Grf    
category objects: (a,b)
morphism: (a,b)->(a',b')
 

tensor products are not categorial products.

In the category of pointed spaces, fundamental in homotopy theory, the coproduct is the wedge sum (which amounts to joining a collection of spaces with base points at a common base point).

Sum

When generating a sum for objects with structure then the structure associated with the link can be added to the sum object.

group sum category

Product

product category construction

Products for groups are discussed on this page.

Pullbacks and Pushout

Pullback:

In programming terms it is related to the concept of indexing.

The pullback is like a type of division for function composition, in other words if multiplication is function composition then what is division? This comes in left and right flavors that is:

if h = g o f

More about pullbacks on page here.

Completeness and Cocompleteness

  Competeness

Cocompeteness

     
     
set example

 

 

Set    
Grp    
Rng    
Vec    
Top    
Grf    
Cat    

Exponential

This is a universal structure but not a limit.

more here.

Example of a Limit

Lets look at a Category of Subsets (could also be looked at as a poset, which forms a lattice, but the diagrams seem more instructive if we show it as subsets) where the objects are subsets and the arrows preserve these subsets:

subset example

So, as an example, we take these three subsets:

  • {a,b,c}
  • {a,b,d}
  • {a,b,e}
subset example

There are various other subsets which have arrows to our original diagram:

  • {a}
  • {b}
  • {a,b}

(on this diagram I have shown an internal representation of the arrows rather than just the arrows themselves)

subset example But only one of these has arrows from all the others.

We can see that this limit represents the biggest subset which is common to our original diagram. In some ways limits like this represent a more sophisticated form of 'type', so all the objects in the first diagram are a 'type' which contain {a,b}.


metadata block
see also:

http://stackoverflow.com/questions/13352205/what-are-free-monads

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.

 

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.