[under construction] In this document we will be working with simple finite categories in J. I hope this will be helpful for anyone interested in studying category theory in mathematics or functional programming languages as categories, but this is not a real introduction to those subjects.

## Definition

A category is a collection of objects together with a collection of morphisms which each have an assigned domain and codomain in and a partial binary (dyadic) operation (defined when the domain of its left argument matches the codomain of its right argument) which is associative and has a unique identity on each object, usually written for .

## Category Theory

Categories are an abstraction of the composition structure of functions. Most branches of mathematics can be reduced to a study of certain objects and morphisms that act between them. Category Theory has proven very useful in providing a unified language for the many branches of Mathematics. For this reason it is often called "the mathematics of mathematics" or "generalized abstract nonsense". Category Theory has also been applied to functional programming, where the language itself is a category whose objects are types and whose morphisms are functions. The best example is perhaps Haskell, which even incorporates the categorical ideas of Functor and Monad.

## Examples in J

#### Example 1

First, let's consider a very simple category which has 3 objects and one unique morphism between each pair of objects.

   ]OBJ=. 'ABC'
ABC
]MOR=. > , { ;~ OBJ
AA
AB
AC
BA
BB
BC
CA
CB
CC
]MOR_DOM=. {."1 MOR
AAABBBCCC
]MOR_COD=. {:"1 MOR
ABCABCABC
compose=. ( ({.@],{:@[) [ assert@({.@[={:@]) )
'BC' compose 'AB'
AC
(a:, <<"1 MOR) ,: (,.<"1 MOR) ; < ( <@compose :: (a:"_) )"1/~ MOR
┌────┬────────────────────────────┐
│    │┌──┬──┬──┬──┬──┬──┬──┬──┬──┐│
│    ││AA│AB│AC│BA│BB│BC│CA│CB│CC││
│    │└──┴──┴──┴──┴──┴──┴──┴──┴──┘│
├────┼────────────────────────────┤
│┌──┐│┌──┬──┬──┬──┬──┬──┬──┬──┬──┐│
││AA│││AA│  │  │BA│  │  │CA│  │  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││AB│││AB│  │  │BB│  │  │CB│  │  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││AC│││AC│  │  │BC│  │  │CC│  │  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││BA│││  │AA│  │  │BA│  │  │CA│  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││BB│││  │AB│  │  │BB│  │  │CB│  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││BC│││  │AC│  │  │BC│  │  │CC│  ││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││CA│││  │  │AA│  │  │BA│  │  │CA││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││CB│││  │  │AB│  │  │BB│  │  │CB││
│├──┤│├──┼──┼──┼──┼──┼──┼──┼──┼──┤│
││CC│││  │  │AC│  │  │BC│  │  │CC││
│└──┘│└──┴──┴──┴──┴──┴──┴──┴──┴──┘│
└────┴────────────────────────────┘

#### Example 2

Rather than having a unique morphism between every pair of objects, we could have morphisms only between pairs of objects that satisfy a certain relation. The subset and superset relations satisfy the properties of a category when interpreted this way. In this example we consider the category on subsets of with morphisms representing the subset relation.

   ]OBJ=. (<@#~"1#:@i.@(2^#)) 'abc'
┌┬─┬─┬──┬─┬──┬──┬───┐
││c│b│bc│a│ac│ab│abc│
└┴─┴─┴──┴─┴──┴──┴───┘
\$MOR=. ( #~ ([:*./{.e.&>{:)"1 ) > , { ,&<~ OBJ
27 2
]MOR_DOM=. {."1 MOR
┌┬┬┬┬┬┬┬┬─┬─┬─┬─┬─┬─┬─┬─┬──┬──┬─┬─┬─┬─┬──┬──┬──┬──┬───┐
│││││││││c│c│c│c│b│b│b│b│bc│bc│a│a│a│a│ac│ac│ab│ab│abc│
└┴┴┴┴┴┴┴┴─┴─┴─┴─┴─┴─┴─┴─┴──┴──┴─┴─┴─┴─┴──┴──┴──┴──┴───┘
]MOR_COD=. {:"1 MOR
┌┬─┬─┬──┬─┬──┬──┬───┬─┬──┬──┬───┬─┬──┬──┬───┬──┬───┬─┬──┬──┬───┬──┬───┬──┬───┬───┐
││c│b│bc│a│ac│ab│abc│c│bc│ac│abc│b│bc│ab│abc│bc│abc│a│ac│ab│abc│ac│abc│ab│abc│abc│
└┴─┴─┴──┴─┴──┴──┴───┴─┴──┴──┴───┴─┴──┴──┴───┴──┴───┴─┴──┴──┴───┴──┴───┴──┴───┴───┘
compose=. ( ({.@],{:@[) [ assert@({.@[={:@]) )
('a';'abc') compose '';'a'
┌┬───┐
││abc│
└┴───┘

Rather than look at the full 27x27 boxed composition table, I prefer to relabel our morphisms with their indices in the list MOR.

   ( (MOR i. compose) :: _: )"1/~ MOR
0 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
1 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
2 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
3 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
4 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
5 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
6 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
7 _ _ _ _ _ _ _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ 1 _ _ _ _ _ _  8  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ 3 _ _ _ _ _ _  9  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ 5 _ _ _ _ _ _ 10  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ 7 _ _ _ _ _ _ 11  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ _ 2 _ _ _ _ _  _  _  _  _ 12  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ _ 3 _ _ _ _ _  _  _  _  _ 13  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ _ 6 _ _ _ _ _  _  _  _  _ 14  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ _ 7 _ _ _ _ _  _  _  _  _ 15  _  _  _  _  _  _  _  _  _  _  _  _  _  _
_ _ _ 3 _ _ _ _  _  9  _  _  _ 13  _  _ 16  _  _  _  _  _  _  _  _  _  _
_ _ _ 7 _ _ _ _  _ 11  _  _  _ 15  _  _ 17  _  _  _  _  _  _  _  _  _  _
_ _ _ _ 4 _ _ _  _  _  _  _  _  _  _  _  _  _ 18  _  _  _  _  _  _  _  _
_ _ _ _ 5 _ _ _  _  _  _  _  _  _  _  _  _  _ 19  _  _  _  _  _  _  _  _
_ _ _ _ 6 _ _ _  _  _  _  _  _  _  _  _  _  _ 20  _  _  _  _  _  _  _  _
_ _ _ _ 7 _ _ _  _  _  _  _  _  _  _  _  _  _ 21  _  _  _  _  _  _  _  _
_ _ _ _ _ 5 _ _  _  _ 10  _  _  _  _  _  _  _  _ 19  _  _ 22  _  _  _  _
_ _ _ _ _ 7 _ _  _  _ 11  _  _  _  _  _  _  _  _ 21  _  _ 23  _  _  _  _
_ _ _ _ _ _ 6 _  _  _  _  _  _  _ 14  _  _  _  _  _ 20  _  _  _ 24  _  _
_ _ _ _ _ _ 7 _  _  _  _  _  _  _ 15  _  _  _  _  _ 21  _  _  _ 25  _  _
_ _ _ _ _ _ _ 7  _  _  _ 11  _  _  _ 15  _ 17  _  _  _ 21  _ 23  _ 25 26

#### Example 3

Categories do not require multiple objects. Here is an example of a category with a single object whose morphisms are the integers mod 5 with addition.

   ]OBJ=. ,:'A'
A
]MOR=. i. N=.5
0 1 2 3 4
]MOR_DOM=. MOR_COD=. (#MOR)#OBJ
AAAAA
compose=. N&|@+
compose/~ MOR
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

#### Example 4

One common example in category theory, denoted , is the category of all sets and all functions between them. While this is infinite, we can work with a category on some finite collection of sets and all functions between them. Since we could have different sets with the same elements, the functions will have to be represented in a way that specifies their domain and codomain. We write them as triples domain/codomain/map where map is a list of indices into the codomain corresponding to elements of the domain.

   OBJ=. 'a';'bc'
setpairtofunctions=. >@,@{@({.#<@i.@{:)@:(#@>)
MOR=. ; <@(,"1 0<"_1@setpairtofunctions)"1 > , { ,&<~ SETS
]MOR_DOM=. 0{"1 MOR
┌─┬─┬─┬──┬──┬──┬──┬──┐
│a│a│a│bc│bc│bc│bc│bc│
└─┴─┴─┴──┴──┴──┴──┴──┘
]MOR_COD=. 1{"1 MOR
┌─┬──┬──┬─┬──┬──┬──┬──┐
│a│bc│bc│a│bc│bc│bc│bc│
└─┴──┴──┴─┴──┴──┴──┴──┘
compose=. ( ({~&.>&{:,~{.@],1{[) [ assert@({.@[-:1{]) )
( (MOR i. compose) :: _: )"1/~ MOR
0 _ _ 3 _ _ _ _
1 _ _ 4 _ _ _ _
2 _ _ 7 _ _ _ _
_ 0 0 _ 3 3 3 3
_ 1 1 _ 4 4 4 4
_ 1 2 _ 4 5 6 7
_ 2 1 _ 7 6 5 4
_ 2 2 _ 7 7 7 7

## Indexed composition tables

As you may have already noticed, the composition table contains all of the important information about the category. If you relabel the morphisms with their indices and then relabel the objects with their identity morphisms (sometimes this is used as an alternative definition of category, so domain and codomain are the left and right inverses), then every aspect of the category is described in the indexed composition table.

   C=. ".&> LF&cut (0 : 0)
0 0 0 0 _ _ _ _  8  8  8  8  _  _  _  _
0 1 2 3 _ _ _ _  8  9 10 11  _  _  _  _
3 2 1 0 _ _ _ _ 11 10  9  8  _  _  _  _
3 3 3 3 _ _ _ _ 11 11 11 11  _  _  _  _
4 4 4 4 _ _ _ _ 12 12 12 12  _  _  _  _
4 5 6 7 _ _ _ _ 12 13 14 15  _  _  _  _
7 6 5 4 _ _ _ _ 15 14 13 12  _  _  _  _
7 7 7 7 _ _ _ _ 15 15 15 15  _  _  _  _
_ _ _ _ 0 0 0 0  _  _  _  _  8  8  8  8
_ _ _ _ 0 1 2 3  _  _  _  _  8  9 10 11
_ _ _ _ 3 2 1 0  _  _  _  _ 11 10  9  8
_ _ _ _ 3 3 3 3  _  _  _  _ 11 11 11 11
_ _ _ _ 4 4 4 4  _  _  _  _ 12 12 12 12
_ _ _ _ 4 5 6 7  _  _  _  _ 12 13 14 15
_ _ _ _ 7 6 5 4  _  _  _  _ 15 14 13 12
_ _ _ _ 7 7 7 7  _  _  _  _ 15 15 15 15
)
assert iscategory C
]MOR=. i. # C NB. Morphisms are indices into the rows/columns
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
]OBJ=. leftidentities C NB. Objects are the identity morphisms
1 13
]MOR_DOM=. domains C NB. The unique left identity of each morphism
1 1 1 1 13 13 13 13 1 1 1 1 13 13 13 13
]MOR_COD=. codomains C NB. The unique right identity of each morphism
1 1 1 1 1 1 1 1 13 13 13 13 13 13 13 13

JordanTirrell/FiniteCategories (last edited 2012-04-18 22:25:29 by JordanTirrell)