1. The interplay between $(-)^*$ and the power-set constructor $\mathbb P$ respectively the finite power-set constructor is at the heart of formal language theory. These constructurs ought to be seen as endo-functors on the category Set. Hence we need some basic category theory. 1.0 Categories informally A directed graph $G$ is a 2-sorted entity; it is comprised of - a class $G_0$ of objects or 0-cells - a class $G_1$ of morphisms or 1-cells or arrows - two functions dom and cod from $G_1$ to $G_0$ assigning the domain and codomain to an arrow; [Diagram!] - notation $A --f-> B$ means: $f$ has domain $A$ and codomain $B$. - Def A directed graph $G$ is called - small, if the objects form a set; - locally small, if for any two objects $A$ and $B$ the arrows with domain $X$ and codomain $Y$ form a set $\G$, called the hom-set for $X$ and $Y$; this is the standard case. - If such directed graphs have extra structure: . a sensible composition operation on ``matching'' arrows: A --f-> B --g-> C composes to A --f;g-> C; associative . units for this compositions A --id_A-> A we have a category. - The fact that certain composites of 1-cells coincide is often expressed in terms of ``commutative diagrams''. - Exas . the paradigmatic category is Set, with sets as objects and functions as morphisms; . Mon has monoids as objects and monoid homomorphisms as morphisms; . Top has topological spaces as objects and continuous functions as morphisms; . Vec(F) has vector spaces over some fixed field $F$ as objects and linear functions as morphisms; . each monoid $M$ is a category with one object $*$; here $M$ is the only hom-set . each ordered set is a category where the hom-sets are at most singletons. Transitivity of the order relation takes care of the composition, while reflexivity provides units. This includes discretely ordered sets. - So categories form a common generalization of monoids and ordered sets. - A slightly different approach starts with the hom-sets rather than a whole class of morphisms: A locally small directed graph can alternatively be specified by a class $G_0$ of objects and a set-valued $G_0\times G_0$ matrix of hom-sets. These need not be disjoint! Their disjoint union comprises $G_1$. - Def (official) A ``locally small category'' $A$ consists of a class A-Ob of ``objects'' together with a $A\times A$-matrix of ``hom-sets'' $\A$, $X,Y\in A$ of morphisms from $X$ to $Y$, together with . distinguished ``identity morphisms $1 --\id_X-> \A$ for every $X\in A-Ob$; . a family of composition operations $\A\times\A --cmp_{XYZ}-> \A$ subject to two axioms: * composition is associative * the ideintity morpjisms provide units for the composition. - Just as for directed graphs, we can reverse all the arrows and obtain the ``opposite category'' $A\op$ for any category $A$. - Exa. For a relation $R$ on a set $A$ viewed as a directed graph, the only possible hom-sets are $\emptyset$, if $\\notin R$, and a singleton $1$ for $\\in R$ - For the same class of objects one can have different classes of morphisms and hence different categories: - Exas . a given set $P$ with more than one element can carry different pre-orders, e.g., the equality and $P\times P$, the indiscrete or chaotic order. . Rel is a category with sets as objects and binary relations as morphisms. It contains Set as a (non-full) subcategory. Notation: $A --R-|> B$ for $R\inc A\times B$ Identifying each function with its graph, we recover $Set$ as (non-full) subcategory of $Rel$; the only 2-cells between functions are the trivial ones; however partial functions give rise to a non-trivial 2-category $Prt$ properly between $Set$ and $Rel$. Notice also that this category happens to be ``self-dual'': for every relation $A --R-|> B$ we have the opposite relation $B --R\op-|> A$. Hence $\Rel\op=(B\tims A)\mathbb P\equiv(A\times B)\mathbb P=\Rel$, so $Rel$ and $Rel\op$ are essentially the same category. - The last exampple illustrates a new but important phenomenon: The hom-sets themselves can have structure! In the case of Rel the hom-sets are ordererd by set-inclusion, and hence themselves are categories. In fact, Rel turns out to be a 2-category with inclusions as 2-cells. - Other very important 2-categories are Cat, the category of small categories, and CAT, the category of all locally small categories. In both cases the 1-cells are certain graph morphisms (these preserve objects and arrows as well as (co)domains). In addition, the composition of arrows and the units for this composition need to be preserved as well. Such 1-cells are called ``functors''. If the categories $A$ and $B$ are given in terms of their hom-sets, a functor $A --F-> B$, besides its object function, is specified by a family of functions $\A --\F-> \B$. Obviously, functors $A --F-> B --G-> C$ compose [exercise?] - Exa (functors) . Functors between monoids (a one-object categories) are just monoid homomorphisms. . Functors between pre-ordered sets are just order-preserving functions. - For any locally small category $A$ the assignment of hom-sets yields a functor $A\op\times A --hom-> Set$, the so-called hom-functor. Fixing the first or second component produces so-called ``representable functors'' \[A --[X,-]-> Set\] and \[A\op --[-,X]-> Set\] which play a very important role in category theory. - But there is more: Given two functors A --F,G-> B, a ``natural transformation'' $\alpha$ is a family of 1-cells $AF --A\alpha-> AG$ indexed by the objects of A and subject to an obvious commutativity condition. (Plain ``transformations'' don't have to satisfy the commutativity condition and make sense already for directed graphs; however, the do not compose). Usual notation: $F ==\alpha=> G$. There is an obvious composition of natural transformations $F ==\alpha=> G ==\beta=> H$ which together with the identity natural transformations $F ==id_F=> F$ turns the class of functors from $A$ to $B$ into a category (not neccessarily locally small). [Exercise?] - If the notion of natural transformation initially seems hard to grasp, consider two order pre-ordered sets $\$ and $\$ and two order-preserving functions $P --f,g-> Q$. One classically defines $f\le g$, if this ist pointwise the case, i.e., if $xf\sqq xg$ for every $x\in P$. Natural transformations extend this notion of pointwise comparison to general functors. Notice that the commutativity condition is automatically satisfied in the pre-ordered case. - Exa (naturality, allegedly the starting point of category theory). Consider the category $Vec(F)$ of vectorspaces over a field $F$. From linear algebra we know that any finite-dimensional vectorspace $V$ is isomorphic to F^n for suitable $n in\IN$. In particular, this applies to the dual space $V^*$ of linear functions $V --l-> F$ (not the free monoids!), and consequently to the double dual space $V^{**}$. Now the vector spaces $V$ and $V^{**}$ turn out to be ``naturally isomorphic'', while this is not the case for $V$ and $V^*$. A first indication for this is that any isomorphism between between $V$ and $V^*$ needs to be defined using bases of these space, while there is a canonical isomorphism between $V$ and $V^{**}$ given by evaluation: map a vector $v\in V$ to the function $V^* --> F$, that evaluates a function $V --l->F$ at $v$. Now consider, how other linear functions $V --f-> W$ interact with these isomorphisms. Taking dual spaces leads to a reversal of the linear function, i.e., we have $W^* --f^*-> W^*$ and then $V^{**} --f^{**}-> V^{**}$. And in the latter case we obtain a nice commuting diagram involving $f$, $f^{**}$ and the two evaluation isomorphisms, whereas in the former case we cannot even form such a diagram. - Many important categorical concepts rely on this 2-dimensional structure, most notably adjoints and monads. We consider this for the specific case of the word-functor $(-)^*$ and the (finite) power set functor $\mathbb P$ resp. $\mathbb F$.