Representable Functor

A set-valued functor

Q: A –> S

is called representable if there is an object A in the domain category A and an element q in the set Q(A) such that, for any object B of the category A, the function

A(A, B) –> Q(B)

(from the set A(A, B) of functions from A to B to the set Q(B), which is the value of the functor Q at B) assigning to each map

b: A –> B

(in the set A(A, B)) the element

Q(b) (q)

(where

Q(b): Q(A) –> Q(B)

is the function to which the map b is assigned to by the functor Q) is an isomorphism of sets (Sets for Mathematics, p. 248).

Consider a set

W = {you, me}

There are two elements in W.   Next consider another set

1 = {·}

There are two functions from 1 to W.  They are

you: 1 –> W

with you(·) = you

and

me: 1 –> W

with me(·) = me

Let

W¹ = {you, me}

be the map set of functions from 1 to W.  Note that both sets W and W¹ have the same number of elements i.e.

|W| = |W¹| = 2

which means that there is an isomorphism

W = W¹

which is an opposed-pair of functions

f: W –> W¹

with

f(you) = you: 1 –> W

f(me) = me: 1 –> W

and

g: W¹ –> W

with

g(you: 1 –> W) = you(·)

g(me: 1 –> W) = me(·)

satisfying

gf = 1_W

fg = 1_W^I

All of this may seem like an excessively elaborate discourse on a rather trivial matter: the number of elements of a set W is equal to the number of functions from the singleton set 1 to the set W.

I have two folders in my head

1. profound

2. all else

I put everything that looks trivial such as functions from the terminal set

1 –> W

in the profound folder.  Of course, I didn’t recognize either DISCRETE SUBCATEGORY or REPRESENTABLE FUNCTOR in

W = W¹

(Conceptual Mathematics, p. 314) on my own :(

Saving discrete subcategory for later, let’s return to our representable functor.  A simple example is, as you guessed, our “you, me” story, little generalized.  More specifically, the identity functor

1: S –> S

(from the category S of sets to the category S) is a representable functor.  What do I need to do in order to convince you that

1: S –> S

is indeed a representable functor?

We need an object

A

of the domain category S of sets and an element

q

of the value of the set-valued functor 1: S –> S at A i.e. of the set

1(A)

Simply put, we need a set

A

and an element

q: 1 –> A

What do these duo i.e. this set

A

and this element

q: 1 –> A

have to do with representable functor?

For any set

B

the function

S(A, B) –> 1(B)

from the set of functions (from A to B)

S(A, B) = B^A

(to the value of our identity functor at the set B i.e.) to the set

1(B) = B

assigning to each function

b: A –> B

(in the set B^A of functions from A to B) the element

1(b) (q)

i.e. (since 1(b: A –> B) = b: A –> B) the element

b(q)

is an isomorphism of sets.

Thanks to our “you, me” story, we take a guess and take a singleton set

1 = {·}

as our A which has only one element ‘·’ which is our element ‘q’ both of which will make the assignment to each function

b: 1 –> B

in the set

S(1, B) = B¹

the element

1(b)(q) = b(q) = b(·) = b

in the set

1(B) = B

an isomorphism

B¹ = B

Next, let’s see if the set-valued functor on the category of dynamical systems, which assigns to each dynamical system its set of states, is a representable functor.

Exercise 5.17c (Sets for Mathematics, p. 109)

The assignments (-)^T(A) = A^T for any set A and (-)^T(f) = f ^T for any function f: A –> B define a functor (-)^T: S –> S.

 

First, S is the category of sets, whose objects and morphisms are sets and functions, respectively.  Next, a functor

P: V –> W

is an assignment of objects and morphisms of the codomain category W to objects and morphisms, respectively, of the domain category V in a way respectful of the domain, codomain, identity, and composition structure of the category.

Let’s look at the case of the functor of our present concern, which has the category S of sets as both domain and codomain category i.e. a functor

P: S –> S

The functor P assigns sets to sets, which we denote as

P_Ob: S_Ob –> S_Ob

and functions to functions, which we denote as

P_Mp: S_Mp –> S_Mp

These two functions

P_Ob: S_Ob –> S_Ob

P_Mp: S_Mp –> S_Mp

together are required to satisfy, in order to constitute a functor

P: S –> S

the following four conditions corresponding to preserving (i) domain, (ii) codomain, (iii) identity, and (iv) composition.

(i) Preserving Domain

S_Ob       –P_Ob–>            S_Ob

^                                  ^

|                                   |

domain                        domain

|                                   |

S_Mp      –P_Mp–>           S_Mp

The commutativity of the above diagram stated as

domain o P_Mp = P_Ob o domain

guarantees the preserving of domain (where ‘o’ denotes composition).  This commutativity equation is read as: the domain set (in top-right S_Ob) of the function (in bottom-right S_Mp) to which a function (in bottom-left S_Mp) is assigned to by P_Mp is same as the set (in top-right S_Ob) to which the domain set (in top-left S_Ob), of the function (in bottom-left S_Mp), is assigned to by P_Ob.

(ii) Preserving Codomain

S_Ob       –P_Ob–>            S_Ob

^                                  ^

|                                   |

codomain                    codomain

|                                   |

S_Mp      –P_Mp–>           S_Mp

The commutativity of the above diagram stated as

codomain o P_Mp = P_Ob o codomain

guarantees the preserving of codomain.  This commutativity equation is read as: the codomain set (in top-right S_Ob) of the function (in bottom-right S_Mp) to which a function (in bottom-left S_Mp) is assigned to by P_Mp is same as the set (in top-right S_Ob) to which the codomain set (in top-left S_Ob), of the function (in bottom-left S_Mp), is assigned to by P_Ob.

(iii) Preserving Identity

S_Mp      –P_Mp–>           S_Mp

^                                  ^

|                                   |

identity                         identity

|                                   |

S_Ob       –P_Ob–>            S_Ob

The commutativity of the above diagram stated as

identity o P_Ob = P_Mp o identity

guarantees the preserving of identity.  This commutativity equation is read as: the identity function (in top-right S_Mp) of the set (in bottom-right S_Ob) to which a set (in bottom-left S_Ob) is assigned to by P_Ob is same as the function (in top-right S_Mp) to which the identity function (in top-left S_Mp), of the set (in bottom-left S_Ob), is assigned to by P_Mp.

(iv) Preserving Composition

P_Mp (g o f) = P_Mp (g) o P_Mp (f)

The function (P_Mp (g o f)) to which the composite function (g o f) is assigned to by P_Mp is same as the composite of the functions (P_Mp(g) and P_Mp(f)) to which the functions (g and f, respectively) are assigned to by P_Mp.

Now that we know what it takes to be a functor, let’s see if what we are given i.e. the functions

(-)^T(A) = A^T

(-)^T(f) = f ^T

together constitute a functor

(-)^T: S –> S

The function

(-)^T_Ob: S_Ob –> S_Ob

assigns to each set

A

(in the domain set S_Ob) the map set

A^T

of T-shaped figures in A i.e. the functions

a: T –> A

from [a fixed set] T to A.

The function

(-)^T_Mp: S_Mp –> S_Mp

assigns to each function

f: A –> B

(in the domain set S_Mp) the induced function

f ^T: A^T –> B^T

where A^T and B^T are map sets whose elements are T-shaped figures in A and B, respectively.

The function

f ^T: A^T –> B^T

assigns to each element (a T-shaped figure in A)

a: T –> A

in the domain map set

A^T

the element

T —a–> A —f–> B

i.e. a T-shaped figure in B

fa: T –> B

in the codomain set

B^T

Thus

f ^T(a) = fa

for all

a: T –> A

in the domain map set

A^T

of the function

f ^T: A^T –> B^T

Now we have to check to see if the object function

(-)^T_Ob (A) = A^T

and the morphism function

(-)^T_Mp (f: A –> B) = f ^T: A^T –> B^T

together constitute a functor

(-)^T: S –> S

i.e. preserve (i) domain, (ii) codomain, (iii) identity, and (iv) composition.

(i) Preserving Domain

S_Ob       –(-)^T_Ob–>         S_Ob

^                                  ^

|                                   |

domain                        domain

|                                   |

S_Mp      –(-)^T_Mp–>        S_Mp

domain o (-)^T_Mp = (-)^T_Ob o domain

LHS

domain o (-)^T_Mp (f: A –> B) = domain (f ^T: A^T –> B^T) = A^T

RHS

(-)^T_Ob o domain (f: A –> B) = (-)^T_Ob (A) = A^T

(ii) Preserving Codomain

S_Ob       –(-)^T_Ob–>         S_Ob

^                                  ^

|                                   |

codomain                    codomain

|                                   |

S_Mp      –(-)^T_Mp–>        S_Mp

codomain o (-)^T_Mp = (-)^T_Ob o codomain

LHS

codomain o (-)^T_Mp (f: A –> B) = codomain (f ^T: A^T –> B^T) = B^T

RHS

(-)^T_Ob o codomain (f: A –> B) = (-)^T_Ob (B) = B^T

(iii) Preserving Identity

S_Mp      –(-)^T_Mp–>        S_Mp

^                                  ^

|                                   |

identity                         identity

|                                   |

S_Ob       –(-)^T_Ob–>         S_Ob

identity o (-)^T_Ob = (-)^T_Mp o identity

LHS

identity o (-)^T_Ob (A) = identity (A^T) = 1_AT: A^T –> A^T

RHS

(-)^T_Mp o identity (A) = (-)^T_Mp (1_A: A –> A) = 1_A^T: A^T –> A^T

where

1_A^T (a: T –> A) = T —a–> A –1_A–> A = 1_A o a = a: T –> A

(iv) Preserving Composition

(-)^T_Mp (g o f) = (-)^T_Mp (g) o (-)^T_Mp (f)

where

f: A –> B, g: B –> C, and g o f: A –> C

LHS

(-)^T_Mp (g o f: A –> C) = (gf)^T: A^T –> C^T

where

(gf)^T(a: T –> A) = T —a–> A —gf–> C = (gf)a: T –> C

RHS

(-)^T_Mp (g) o (-)^T_Mp (f)

= g^T: B^T –> C^T o f ^T: A^T –> B^T

= A^T —f ^T–> B^T —g^T–> C^T

= g^T o f ^T: A^T –> C^T

where

g^T o f ^T (a: T –> A) = g^T (fa: T –> B) = g(fa): T –> C

Thanks to the associative law

(gf)a = g(fa)

of composition

T —a–> A —f–> B —g–> C

the morphism component

(-)^T_Mp: S_Mp –> S_Mp

of the functor

(-)^T: S –> S

preserves composition.  Thus with (i) domain, (ii) codomain, (iii) identity, and (iv) composition preserved by the assignments

(-)^T(A) = A^T

(-)^T(f) = f ^T

we do have a functor

(-)^T: S –> S

Exercise 29 (Conceptual Mathematics, p. 150)

Every morphism f: X –> Y in a category C gives rise to a morphism in the category of Z-structures, by the associative law.

Let’s start with what we are given: associative law.  This seemingly simple law from elementary school

(1 + 2) + 3 = 1 + (2 + 3)

is all that we need to do the exercise (all exercises, for that matter; see Conceptual Mathematics, p. 136 and p. 371).

The composite of three composable morphisms such as

A – p –> B – x –> X – f –> Y

can be calculated in two ways:

1. first calculate the composite of morphisms p and x, and then the composite of xp and f

2. first calculate the composite of morphisms x and f, and then the composite of p and fx

The associative law states that these two calculations give the same result, which is expressed as

f (xp) = (fx) p

All we have to do, in order to do the exercise, is turn the associate law

f (xp) = (fx) p

into the commutative diagram

xp        –>            fxp

^                                ^

|                                |

x            –>            fx

Let’s start at the bottom-left corner

x: B –> X

which when pre-composed with

p: A –> B

takes us to the top-left corner

xp: A –> X

which when post-composed with

f: X –> Y

takes us to the top-right corner

fxp: A –> Y

Of course, we could have taken the other route i.e. start (as earlier) at the bottom-left corner

x: B –> X

which when post-composed with

f: X –> Y

takes us to the bottom-right corner

fx: B –> Y

which when pre-composed with

p: A –> B

takes us to the top-right corner

fxp: A –> Y

So, to sum up, reading the commutative diagram

xp        –post–>            fxp

^                                         ^

|                                         |

pre                                pre

|                                         |

x            –post–>            fx

satisfying

post o pre = pre o post

(where ‘o’ denotes composition) into the associative law

f (xp) = (fx) p

satisfied by

A – p –> B – x –> X – f –> Y

is all that’s needed to do the exercise.

YOU: Just do it!

OK.  What we need to deliver is a category of Z-structures, and that’s starters.  But, what on wordpress is Z-structure?  First, let’s make explicit something that’s implicit.  Z is a small family of objects and morphisms of the category C.  The only condition on the small family Z is that if a morphism of C is in the small family, then both domain and codomain of the morphism are in the family.  Let’s take

A – p –> B

as our small family Z i.e. our family Z consists of two objects (A, B) and one morphism (p).  Every object X of the category C gives rise to a Z-structure, which has as many component sets as the number of objects in Z and as many structural functions (between these component sets) as the number of morphisms in Z.  Since there are two objects (A, B) in our family Z, we have two component sets:

1. A-th component set A(X) is the set of all A-shaped figures in X (i.e. A –> X)

2. B-th component set B(X) is the set of all B-shaped figures in X (i.e. B –> X)

corresponding to the two objects (A, B).  Since there is one morphism

p: A –> B

in Z, we have one structural function

p(X): A(X) <– B(X)

(note the opposite direction of p(X) compared to p) assigning to each element

x: B –> X

in the domain set B(X) an element in the codomain set A(X).  But, which one?

p(X)(x) = xp

Summing up, what we have so far is the following diagram

A(X)

^

|

p(X)

|

B(X)

of two component sets and one structural function constituting a Z-structure denoted Z(X), which the object X (of the category C) gave rise to.  Along similar lines, object Y (of C) gives rise to another Z-structure Z(Y) i.e.

A(Y)

^

|

p(Y)

|

B(Y)

Now we have to show that a morphism

f: X –> Y

in the category C gives rise to a morphism

Z(f): Z(X) –> Z(Y)

in the category of Z-structures i.e. a morphism from the object Z(X)

A(X)

^

|

p(X)

|

B(X)

to the object Z(Y)

A(Y)

^

|

p(Y)

|

B(Y)

Putting it all together, we need a pair of functions

f(A): A(X) –> A(Y)

f(B): B(X) –> B(Y)

making the diagram

A(X)        –f(A)–>            A(Y)

^                                              ^

|                                              |

p(X)                                              p(Y)

|                                              |

B(X)            –f(B)–>            B(Y)

commute i.e. satisfy

p(Y) o f(B) = f(A) o p(X)

If that’s not enough headache we need to show that the morphism

f: A –> B

gives rise to these functions

f(A): A(X) –> A(Y)

f(B): B(X) –> B(Y)

This added headache turns out to be the solution in the following sense.  Take the case of

f(A): A(X) –> A(Y)

which has to assign to each element

xp: A –> X

of the domain set A(X) an element of the codomain set A(Y), but which one?  The solution is to post-compose with

f: A –> B

i.e. define the function

f(A): A(X) –> A(Y)

as

f(A)(xp) = f (xp)

Similarly, we define the function

f(B): B(X) –> B(Y)

as

f(B)(x) = fx

With

f(A): A(X) –> A(Y)

f(B): B(X) –> B(Y)

defined as above, the diagram

A(X)        –f(A)–>            A(Y)

^                                              ^

|                                              |

p(X)                                              p(Y)

|                                              |

B(X)            –f(B)–>            B(Y)

does commute i.e. satisfies

p(Y) o f(B) = f(A) o p(X)

To be more explicit, let’s start at the bottom-left corner with a B-shaped figure in X

x: B –> X

i.e. an element of B(X).

LHS: p(Y) o f(B)

p(Y) o f(B) (x) = p(Y) (fx) = (fx) p

RHS: f(A) o p(X)

f(A) o p(X) (x) = f(A) (xp) = f (xp)

If

(fx) p = f (xp)

then the above diagram commutes.  Fortunately the associative law

(fx) p = f (xp)

says just that.  In other words the commutativity of the diagram (morphism of Z-structures)

A(X)        –f(A)–>            A(Y)

^                                              ^

|                                              |

p(X)                                              p(Y)

|                                              |

B(X)            –f(B)–>            B(Y)

induced by the morphism

f: X –> Y

(of the category C) follows from the associativity of composition of morphisms

A – p –> B – x –> X – f –> Y

YOU: What if the family Z has more (or less) than the one morphism

p: A –> B

that we considered?

In general the Z-structure has a component set for each object and a structural function for each morphism in Z.  These component sets and structural functions (that an object X of C gave rise to) together constitute an object of the category of Z-structures.  A morphism in the category of Z-structures has as many component functions as the number of component sets (which is same as the number of objects in Z).  All these component functions together are required to satisfy, in order to constitute a morphism, as many equations as the number of structural functions (which is same as the number of morphisms in Z).  Morphisms (in so satisfying the commutativity equations) preserve, while transforming, all the structure of objects of the category of Z-structures.

Cutting to confession: we did not do the exercise at the level of abstraction that the exercise called for.  However, I hope, working out the case of a particular small family of two objects and one morphism gave a feel for the calculations involved in general.

YOU: But, what does STRUCTURE and SMALL FAMILY have to do with cognition?

Where to begin…

abstraction: Particulars –> Generals

to be continued…