IFIP WG2.2 40th Anniversary Meeting (3): Utility of categories
This comment arises from a question: at one of the coffee breaks a participant asked Furio Honsell what results can be proved more easily using categories.
I think it is a question category theorists should be able to respond to with easily understood examples.
I make an analogy with ring theory. Perhaps the first useful thing about rings is Gauss's observation that there is a homomorphism from Z to Z mod m. Of course you don't need to mention rings in talking of this homomorphism but only by avoiding the word, not the concept. This homomorphism (reducing modulo m) immediately gives results.
Example 0: x*x-3*y*y = 19 has no solutions in integers (an infinite problem).
Proof: consider modulo 4. The left had side can be 0,1 or 2 modulo 4 but never 3.
The right hand side is 3 mod 4. Contradiction.
There should be results almost as simple for categories. I intend to make a list.
Example 1: (but too complicated for what I would like) The fundamental group pi_1 is a functor from (pointed) Top to Groups. Futher pi_1(circle)=Z, pi_1(disk)=0, so there cannot be a continuous map Disk->Circle such that
Circle->Disk->Circle = identity, because there are no functions Z->0->Z which compose to be the identity.
Example 2: (discussion with Aurelio Carboni) Consider the category D of open intervals of R, and differentiable functions, and the category L whose objects are of the form RxU (U an open interval) and whose arrows from RxU to RxV are pairs s:RxU->R, f:U->V where s(-,u) is linear, and f:U->V is differentiable; composition is usual composition of functions. Then differentiation is a functor from D to L. This is just the chain rule.
Application: The extrema of exp(cos(x*x)) occur at the points sqrt(n*pi) and their negatives. Proof: differentiate using the chain rule, and look for zeros.
Everyone knows this from a first course in calculus, but just as modular arithmetic uses rings, these calculations use composition of functions and the functoriality of differentiation.
(Comment by Aurelio: I would phrase the content as follows:
The graphs D and L are categories such that the obvious graphs morphism is a functor iff differentiable maps compose, iff chain rule holds. Obviously D and L can be applied to any choosen class of composable differentiable maps.)
Perhaps a simpler version of this example would be to take D to have objects R^n (n=0,1,2,3,..) and L could even be the same as D. Then diff takes R^n to R^(2n), and
f:R^n->R^m to a polynomial g:R^(2n)->R^(2m) such that if u, v are in R^n then
g(u,v)=(f'(v)(u),f(v)), where f'(v) is the linear function approximating f at v.
The fact that diff is a functor is the chain rule for polynomial functions of
several variables.
Example 3: (Burnside Lemma) Consider a finite groupoid H. It is obvious that in a connected component C of H the homs between any pair of objects have the same number of elements, k_C say. So the number e_C of endomorphisms in the component C = k_C x number of objects in C. But the number n_C of arrows out of an object in C is also k_C x number of objects in C. Hence e_C=n_C.
Hence e_H, the total number of endomorphisms in H, = sum over the components C of n_C.
Application: (from Wikipedia - counting the number of distict cubes painted with 3 colours) Consider the rotation group of the cube - it has 24 elements. Consider the groupoid whose objects are the 3^6 cubes coloured with three colours, and whose arrows are the rotations transforming one coloured cube into another.
The connected components of this groupoid are the distinct 3-coloured cubes.
The number of arrows out of any object is always 24.
Hence the total number of endomorphisms in the groupoid = 24 x number of components.
That is,
number of distinct 3-coloured cubes = 1/24 x number of 3-coloured cubes fixed under rotations.
There are 3^6 cubes fixed uner the identity.
There are 6 x 3^3 cubes fixed under the six 90-degree face rotations.
There are 3 x 3^4 cubes fixed under the three 180-degree face rotations.
There are 8 x 3^2 cubes fixed under the eight 120-degree vertex rotations.
There are 6 x 3^3 cubes fixed under the six 180-degree edge rotations.
Hence the number of distict 3-coloured cubes is
1/24 x (3^6+6x3^3+3x3^4+8x3^2+6x3^3) = 57.
---
This is usually considered an application of group theory (and hence of categories). But in my view, as above, there is a groupoid involved.
Example 4. to develop In close analogy to the example above regarding congruences, facts about systems may be deduced using instead various compositional simulations.
Example 5. to develop The free strict symmetric monoidal category on one object is the category P with objects natural numbers and arrows permutations. The category S with objects natural numbers and for each object n two arrows + and - from n to n, is a strict symmetric monoidal category with symmetry -:1+1->1+1. The induced functor sign:P->S is very useful in proving that various games have impossible reachable states - ex Rubik's cube etc.
Example 6. to develop Metric spaces and enriched categories
Example 7. to develop Kleene theorem and enriched categories
I think it is a question category theorists should be able to respond to with easily understood examples.
I make an analogy with ring theory. Perhaps the first useful thing about rings is Gauss's observation that there is a homomorphism from Z to Z mod m. Of course you don't need to mention rings in talking of this homomorphism but only by avoiding the word, not the concept. This homomorphism (reducing modulo m) immediately gives results.
Example 0: x*x-3*y*y = 19 has no solutions in integers (an infinite problem).
Proof: consider modulo 4. The left had side can be 0,1 or 2 modulo 4 but never 3.
The right hand side is 3 mod 4. Contradiction.
There should be results almost as simple for categories. I intend to make a list.
Example 1: (but too complicated for what I would like) The fundamental group pi_1 is a functor from (pointed) Top to Groups. Futher pi_1(circle)=Z, pi_1(disk)=0, so there cannot be a continuous map Disk->Circle such that
Circle->Disk->Circle = identity, because there are no functions Z->0->Z which compose to be the identity.
Example 2: (discussion with Aurelio Carboni) Consider the category D of open intervals of R, and differentiable functions, and the category L whose objects are of the form RxU (U an open interval) and whose arrows from RxU to RxV are pairs s:RxU->R, f:U->V where s(-,u) is linear, and f:U->V is differentiable; composition is usual composition of functions. Then differentiation is a functor from D to L. This is just the chain rule.
Application: The extrema of exp(cos(x*x)) occur at the points sqrt(n*pi) and their negatives. Proof: differentiate using the chain rule, and look for zeros.
Everyone knows this from a first course in calculus, but just as modular arithmetic uses rings, these calculations use composition of functions and the functoriality of differentiation.
(Comment by Aurelio: I would phrase the content as follows:
The graphs D and L are categories such that the obvious graphs morphism is a functor iff differentiable maps compose, iff chain rule holds. Obviously D and L can be applied to any choosen class of composable differentiable maps.)
Perhaps a simpler version of this example would be to take D to have objects R^n (n=0,1,2,3,..) and L could even be the same as D. Then diff takes R^n to R^(2n), and
f:R^n->R^m to a polynomial g:R^(2n)->R^(2m) such that if u, v are in R^n then
g(u,v)=(f'(v)(u),f(v)), where f'(v) is the linear function approximating f at v.
The fact that diff is a functor is the chain rule for polynomial functions of
several variables.
Example 3: (Burnside Lemma) Consider a finite groupoid H. It is obvious that in a connected component C of H the homs between any pair of objects have the same number of elements, k_C say. So the number e_C of endomorphisms in the component C = k_C x number of objects in C. But the number n_C of arrows out of an object in C is also k_C x number of objects in C. Hence e_C=n_C.
Hence e_H, the total number of endomorphisms in H, = sum over the components C of n_C.
Application: (from Wikipedia - counting the number of distict cubes painted with 3 colours) Consider the rotation group of the cube - it has 24 elements. Consider the groupoid whose objects are the 3^6 cubes coloured with three colours, and whose arrows are the rotations transforming one coloured cube into another.
The connected components of this groupoid are the distinct 3-coloured cubes.
The number of arrows out of any object is always 24.
Hence the total number of endomorphisms in the groupoid = 24 x number of components.
That is,
number of distinct 3-coloured cubes = 1/24 x number of 3-coloured cubes fixed under rotations.
There are 3^6 cubes fixed uner the identity.
There are 6 x 3^3 cubes fixed under the six 90-degree face rotations.
There are 3 x 3^4 cubes fixed under the three 180-degree face rotations.
There are 8 x 3^2 cubes fixed under the eight 120-degree vertex rotations.
There are 6 x 3^3 cubes fixed under the six 180-degree edge rotations.
Hence the number of distict 3-coloured cubes is
1/24 x (3^6+6x3^3+3x3^4+8x3^2+6x3^3) = 57.
---
This is usually considered an application of group theory (and hence of categories). But in my view, as above, there is a groupoid involved.
Example 4. to develop In close analogy to the example above regarding congruences, facts about systems may be deduced using instead various compositional simulations.
Example 5. to develop The free strict symmetric monoidal category on one object is the category P with objects natural numbers and arrows permutations. The category S with objects natural numbers and for each object n two arrows + and - from n to n, is a strict symmetric monoidal category with symmetry -:1+1->1+1. The induced functor sign:P->S is very useful in proving that various games have impossible reachable states - ex Rubik's cube etc.
Example 6. to develop Metric spaces and enriched categories
Example 7. to develop Kleene theorem and enriched categories
Labels: category theory, mathematics
posted by Unknown at 2:24 AM
0 Comments:
Post a Comment
<< Home