patternMinor
Category theory and graphs
Viewed 0 times
theorygraphscategoryand
Problem
Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be written for such graphs?
Solution
A category consists of:
-
Objects.
-
Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.
-
A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.
-
Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).
The composition map has to satisfy the following axioms:
-
Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.
-
Identity: if $f\colon x \to y$ and $1_x\colon x \to x$ and $1_y\colon y \to y$ are the distinguished self loops then $f1_x = 1_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1_x\colon x\to x$ and $1_y\colon y\to y$ such that $f1_x = 1_yf = f$.)
You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.
-
Objects.
-
Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.
-
A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.
-
Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).
The composition map has to satisfy the following axioms:
-
Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.
-
Identity: if $f\colon x \to y$ and $1_x\colon x \to x$ and $1_y\colon y \to y$ are the distinguished self loops then $f1_x = 1_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1_x\colon x\to x$ and $1_y\colon y\to y$ such that $f1_x = 1_yf = f$.)
You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.
Context
StackExchange Computer Science Q#23875, answer score: 3
Revisions (0)
No revisions yet.