Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What do you mean by "express"? You can just say that $\mathcal{T}$ is a category with objects being trees and morphisms being homomorphisms of trees (graphs -- it's a full subcategory of the category $\mathcal{G}$ of graphs). – Damian Sobota Feb 12 '12 at 13:27
"define" is better than "express" – tyranitar Feb 12 '12 at 13:41
So I wrote you an answer. What do you need more? – Damian Sobota Feb 12 '12 at 13:55
up vote 6 down vote accepted

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."

share|cite|improve this answer
That's exactly what I said in a comment. – Damian Sobota Feb 12 '12 at 21:14
@DamianSobota: you could make that a full answer rather than a comment. – Mitch Feb 13 '12 at 2:34

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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.