A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure the term "sub-category" is correct.
Category of Trees as sub-category of Category of Graphs
-
0So I wrote you $a$n answer. What do you need more? – 2012-02-12
2 Answers
I think the term you're looking for is "full subcategory". If you have a category $C$, and a set $d$ of objects in $C$, then the full subcategory of $C$ defined by $d$ is the category $D$ whose objects are the elements of $d$, and whose morphisms are all the morphisms of $C$ whose domain and codomain are in $d$. Thus, you can simply say:
"Define the category Tree as the full subcategory of Gph whose objects are trees."
-
1@DamianSobota: you could make that a full answer rather than a comment. – 2012-02-13
Defining what a tree is is a subtle thing and depends on what you want to use the trees for. Let us assume that you are interested in the notion of an "undirected, rooted, finite non-planar tree". The definition 'a connected undirected graph with no cycles, and with a chosen leaf as root' captures that notion and gives rise to a category of trees as the full subcategory of the category of undirected graphs spanned by these trees. However, the definition 'a contractible 1-dimensional compact connected and simply connected space with a chosen boundary point' also captures the the same notion and thus gives rise to another category of trees, the full subcategory of the category of topological spaces spanned by those trees.
Another possibile definition is 'a finite poset with a smallest element and such that for every element the down-set determined by it is linearly ordered'. It too captures the same notion of "tree" as above and yields yet another category of trees, the full subcategory of the category of posets spanned by those trees. There is also the dendroidal category $\Omega$ whose objects are trees and can be defined in at least three different ways.
More possible definitions can be found in http://ncatlab.org/nlab/show/tree.
The point is that all of these categories are radically different. In particular the notion of subtree is highly sensitive to which of these categories you consider.
All this just goes to show that much care is needed with such formulations, even if you wish your trees form a subcategory of graphs, depending on your choice of axiomatization of the tree concept you might get very different categories.