You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Jacob Zelko (Apr 21 2024 at 19:17):Hi folks!
I've been tinkering a bit with putting some pen to paper as well as thought to code and have been trying to read and understand some of the blog posts from the AlgebraicJulia blog. Evan Patterson wrote a really nice blog post, "What Is a Graph?", in a series of posts on that blog discussing Catlab's approach to understanding graphs.
I understood the majority of the blog when it was discussing graphs but got lost a bit in the nuance when we started discussing graphs as C-Sets. I had a few questions in the blog post that I have extracted below (the sections I am most curious about are the ones: Graphs as C-Sets and Symmetric Graphs)
Here are the questions I had:
In this context, the category C is interpreted as a schema
~ Graphs as C-Sets
What is a schema in this context here? Where can I read more about it? I wasn't sure if this was relating to a programming schema or a mathematical idea of a schema.
parts in the structure and the subpart relations between them
~ Graphs as C-Sets
What are parts and subparts? This is what was making me think that a schema is a sort of mathematical object.
there are two kinds of parts, of type V and E
~ Graphs as C-Sets
What are types in this context?
schema for graphs is the category Sch(Graph) [...] In particular, when C=Sch(Graph), a C-set is exactly a graph as previously defined.
~ Graphs as C-Sets
How are these two things isomorphic to one another? Does this encode some sort of functor or natural transformation? Struggling a bit to parse this out fully.
Unpacking this, a symmetric graph is a graph G together with an orientation-reversing involution on edges
Symmetric Graphs
What is an involution in this situation? I realized I may not be very familiar with this idea and even after trying to read about it, I am struggling to understand it from a category theoretic perspective -- an involution switches out arrows? Or switches the direction of errors?
Thanks folks and looking forward to discussing further if folks can help me parsing out these ideas! Additionally, I am happy to provide more clarification or thoughts as needed. Thank you!!!
Spencer Breiner (Apr 21 2024 at 20:07):Jacob Zelko said:
In this context, the category C is interpreted as a schema
~ Graphs as C-SetsWhat is a schema in this context here? Where can I read more about it? I wasn't sure if this was relating to a programming schema or a mathematical idea of a schema.
The "schema" terminology comes (I think) from databases, where it specifies the tables and their columns. This is pretty close to the categorical version, except that foreign keys (columns representing functional relations between tables) are sometimes implicit, whereas in the categorical story they are strongly distinguished from "attributes" that represent actual data (i.e. strings, numbers, etc.)
Formally, the difference is that the unique identifier (key) marking a row in a table has no semantic meaning. You would get an equivalent DB if you changed the keys to a different format, as long as you changed the let values stored in other tables at the same time. This is very different from names, birth dates, etc., which can't be modified without changing the meaning of the data.
Spencer Breiner (Apr 21 2024 at 20:12):Jacob Zelko said:
parts in the structure and the subpart relations between them
~ Graphs as C-SetsWhat are parts and subparts? This is what was making me think that a schema is a sort of mathematical object.
"Parts" and "subparts" are the AlgebraicJulia lingo for the rows in the tables and the values in the columns, respectively. (Not my favorite terminology). In categorical terms, an instance is a set-valued functor, the parts are the elements of the sets in the image, and the subparts are the values of the functions in the image.
For example, an edge or a vertex is a part, and the source vertex of an edge is a subpart.
Spencer Breiner (Apr 21 2024 at 20:31):Jacob Zelko said:
there are two kinds of parts, of type V and E
~ Graphs as C-SetsWhat are types in this context?
The types are the objects in the schema category, or the tables in the database schema.
Jacob Zelko (Apr 21 2024 at 20:34):Ah thanks @Spencer Breiner ! I thought "schema" was some sort of other mathematical terminology but being as it is mostly from database terminology, I'll take more of a look at Spivak's _Relational Foundations For Functorial Data Migration_.
But since you mentioned it, is there a categorical notion of a schema separate from databases? It seems like there is based on what you are saying -- where can I read more about that categorical treatment of schemas?
Jacob Zelko (Apr 21 2024 at 20:36):Ah thanks for clarifying on types -- sometimes it can be hard to disentangle the software/implementation terminology from the mathematical nomenclature. I was wondering if type was being used in the sense that you can have a of a type "whatever" within category theory.
Spencer Breiner (Apr 21 2024 at 20:41):Jacob Zelko said:
schema for graphs is the category Sch(Graph) [...] In particular, when C=Sch(Graph), a C-set is exactly a graph as previously defined.
~ Graphs as C-SetsHow are these two things isomorphic to one another? Does this encode some sort of functor or natural transformation? Struggling a bit to parse this out fully.
To make this a formal statement, you would need to spell out a different definition of (directed, multi-)graph (and graph homomorphism). Then you could define functors back and forth, and natural transformations establishing an equivalence of categories.
However, it's probably more convincing to just draw a directed graph on paper and then figure out how to represent it as a C-set. Ditto on graph homomorphisms and natural transformations between C-set functors.
Evan Patterson (Apr 21 2024 at 20:47):Jacob Zelko said:
But since you mentioned it, is there a categorical notion of a schema separate from databases? It seems like there is based on what you are saying -- where can I read more about that categorical treatment of schemas?
David's book Category theory for the sciences, a draft of which is also available online, explains in detail how to think about schemas as categories. (Attributes are not treated specially in this simple picture, but the simplicity is what makes it the best place to start to get the general idea. Then you can start putting bells and whistles on it.)
Spencer Breiner (Apr 21 2024 at 20:47):Jacob Zelko said:
Unpacking this, a symmetric graph is a graph G together with an orientation-reversing involution on edges
Symmetric GraphsWhat is an involution in this situation? I realized I may not be very familiar with this idea and even after trying to read about it, I am struggling to understand it from a category theoretic perspective -- an involution switches out arrows? Or switches the direction of errors?
This one is easy to Google. An involution is a function that is it's own inverse (so necessarily an endomorphism).
In this case, categorical schemas don't have a good way of not distinguishing the source and target of an edge (the usual way would be a two element subset, but subsets require power objects, and that is a big step up in logical strength), so instead we just put in two edges pointing either way, and regard the undirected edges as orbits of the involution.
Spencer Breiner (Apr 21 2024 at 20:48):PS. If you ask each question in a different post, that makes it easier to quote and reply.
Ryan Wisnesky (Apr 22 2024 at 04:01):the study of generic 'categories of schemas' from a data migration POV using institutional model theory is here, it foreshadows much of functorial data migration etc: https://www.semanticscholar.org/paper/A-Model-Theory-for-Generic-Schema-Management-Alagic-Bernstein/8ca873192a72bdd1148d04f7850befa1f45d9535
John Baez (Apr 22 2024 at 12:23):Jacob Zelko said:
In this context, the category C is interpreted as a schema
What is a schema in this context here? Where can I read more about it? I wasn't sure if this was relating to a programming schema or a mathematical idea of a schema.
To be really precise, though perhaps not very helpful, I think schema here is defined to mean exactly 'category'!
You can read a lot more about this use of the term schema here:
They refer to an earlier paper:
In [Spi12], Spivak puts emphasis on the ability to move data from one format, or database schema, to another. To enable that, he proposes defining schemas to be mere categories [....]