\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{tree}

\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{graph_theory}{}\paragraph*{{Graph theory}}\label{graph_theory}

[[!include graph theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak
\noindent\hyperlink{as_undirected_graphs}{As undirected graphs}\dotfill \pageref*{as_undirected_graphs} \linebreak
\noindent\hyperlink{as_spaces}{As spaces}\dotfill \pageref*{as_spaces} \linebreak
\noindent\hyperlink{as_digraphs}{As digraphs}\dotfill \pageref*{as_digraphs} \linebreak
\noindent\hyperlink{as_ordered_sets}{As ordered sets}\dotfill \pageref*{as_ordered_sets} \linebreak
\noindent\hyperlink{as_functors}{As functors}\dotfill \pageref*{as_functors} \linebreak
\noindent\hyperlink{as_terminal_coalgebra}{As terminal coalgebra}\dotfill \pageref*{as_terminal_coalgebra} \linebreak
\noindent\hyperlink{as_operations}{As operations}\dotfill \pageref*{as_operations} \linebreak
\noindent\hyperlink{as_relational_structures}{As relational structures}\dotfill \pageref*{as_relational_structures} \linebreak
\noindent\hyperlink{as_polynomial_endofunctors_after_kock}{As polynomial endofunctors (after Kock)}\dotfill \pageref*{as_polynomial_endofunctors_after_kock} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

A \textbf{tree} is a connected [[graph]] without cycles. Some notions of tree (such as planar tree) consider extra structure or properties as well, but the baseline notion is tree as acyclic connected graph.

Trees are fundamental combinatorial objects which appear in a wide variety of guises. Some are given below.

\hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions}

\hypertarget{as_undirected_graphs}{}\subsubsection*{{As undirected graphs}}\label{as_undirected_graphs}

Recall that an [[undirected graph]] $G$ consists of a set $V$ of \emph{vertices} and a set $E$ of unordered pairs of vertices. A \textbf{path} in $G$ is a finite sequence of vertices $x_0, \ldots, x_n$ such that each pair $x_i x_{i+1}$ belongs to $E$. If $x_n = x_0$, then the path is called a \textbf{cycle}. A graph is \textbf{connected} if it is nonempty and if for every distinct pair of vertices $x, y$, there is a path for which $x_0 = x$ and $x_n = y$. A graph is \textbf{acyclic} if the only cycles are paths

\begin{displaymath}
x_0, \ldots, x_{n-1}, x_n, x_{n-1}, \ldots, x_0
\end{displaymath}
where steps are retraced; an acyclic graph is also called a \emph{forest}. A \textbf{tree} is a connected forest.

Each forest is a [[disjoint union|disjoint sum]] (a [[coproduct]] in the category of graphs) of trees. Removal of a vertex of a tree (and any edges incident to it) results in a forest.

Not all authors include nonemptiness as part of the notion of connectedness. See [[connected space]] for commentary on this. Forests on the other hand may be empty.

\hypertarget{as_spaces}{}\subsubsection*{{As spaces}}\label{as_spaces}

A \emph{topological tree} is a 1-dimensional [[CW-complex]] which is contractible, i.e., homotopy equivalent to a point.

In this language, a topological graph is simply a 1-dimensional CW-complex; more precisely, we mean a \emph{CW-presentation} and not merely a space that can be so presented. A topological forest is then a 1-dimensional CW-complex with vanishing first [[homology group]] with integral coefficients, and a tree is a connected forest.

For finite graphs $G$ as CW-complexes, one has the useful [[Euler characteristic|Euler formula]]:

\begin{displaymath}
h_0 - h_1 = c_0 - c_1
\end{displaymath}
where $c_i$ is the number of $i$-cells and $h_i$ is the rank of the homology group $H_i(G; \mathbb{Z})$. This gives a useful criterion for a graph to be a tree: that it be connected ($h_0 = 1$) and that the number of vertices $c_0$ be 1 greater than the number of edges $c_1$.

\hypertarget{as_digraphs}{}\subsubsection*{{As digraphs}}\label{as_digraphs}

A \textbf{rooted tree} is a [[directed graph]] (or [[quiver]]) $G$ such that the [[free category on a quiver|free category]] generated by $G$ has a [[terminal object]], called the \textbf{root} of $G$. (Thus for every vertex $x$ in $G$ there is exactly one directed path from $x$ to the root. It follows easily that the free category is a poset. There is no significant change in content if ``terminal'' here is replaced by ``initial''; we can distinguish the conventions by a tree directed \emph{towards} the root rather than \emph{away from} the root.)

A \textbf{rooted forest} is a coproduct of rooted trees, and again we have the fundamental fact that there is a natural [[equivalence of categories]]

\begin{displaymath}
Tree \overset{\to}{\leftarrow} Forest
\end{displaymath}
which in one direction is the functor which sends a tree to the forest which results by excising the root and all edges incident to it, and in the other sends a forest to the tree gotten by adjoining a new root and joining the roots of the forest to that new root by new edges.

This equivalence can be exploited to relate the [[exponential generating function]] for finite rooted trees to the [[Lambert W-function]] (q.v.).

A tree in the form of an \emph{undirected} graph together with a chosen vertex can be regarded as a rooted tree in digraph form (with root the chosen vertex), by orienting all edges in the direction of paths going to the root. The category of rooted trees has very nice categorical properties not shared by the category of unrooted trees; see the following section.

\hypertarget{as_ordered_sets}{}\subsubsection*{{As ordered sets}}\label{as_ordered_sets}

In [[order theory]], a tree is described by a [[partial order]] with the added property that it is downward [[well ordering|well ordered]]. Let $S$ be a [[partially ordered set]], then $S$ is a tree when for each $x \in S$ the downward closure or history $x^- = \{ y \mid y \leq x \}$ is a [[well ordered]] subset of $S$. If instead of a well-order we find that $x^-$ is only totally ordered (meaning that points in the tree do not have a distinguished successor) we say that $S$ is [[prefix ordered]].

\hypertarget{as_functors}{}\subsubsection*{{As functors}}\label{as_functors}

Let $\mathbb{N}$ be the [[totally ordered set]] of natural numbers $0 \leq 1 \leq 2 \leq \ldots$, viewed as a [[category]]. A \textbf{rooted forest} is a [[presheaf]] on $\mathbb{N}$, i.e., a functor

\begin{displaymath}
F: \mathbb{N}^{op} \to Set
\end{displaymath}
to ``the'' [[category of sets]]. A \textbf{rooted tree} is a forest for which $F(0)$ is terminal (a [[point]]).

In this case, we get from a tree as functor $F$ to a tree as digraph by passing to the [[category of elements]] $El(F)$. The vertices of the digraph are the elements, and the edges are those morphisms of $El(F)$ which map to morphisms $i + 1 \to i$ in $\mathbb{N}^{op}$. Notice that $\mathbb{N}^{op}$ is itself (the free category on) a tree as digraph, one that is terminal in the category of forests.

In the other direction, starting with a tree as digraph, we define a functor $F \colon \mathbb{N}^{op} \to Set$ by letting $F(n)$ be the set of vertices $v$ such that the path from $v$ to the root has $n$ edges. The map $F(n+1) \to F(n)$ moves a vertex $v \in F(n+1)$ to the vertex that is one step closer to the root (along the unique path from $v$ to the root).

The functor description makes it clear that the category of forests is a (presheaf) [[topos]], indeed a [[Grothendieck topos]]; therefore the [[category of trees]], which is equivalent, is also a [[topos]].

If we replace $Set$ here by the category of [[totally ordered set]]s $Tos$, then we may define a \textbf{planar forest} as a functor

\begin{displaymath}
F: \mathbb{N}^{op} \to Tos
\end{displaymath}
\hypertarget{as_terminal_coalgebra}{}\subsubsection*{{As terminal coalgebra}}\label{as_terminal_coalgebra}

The category of trees as described in the section immediately above can be described universally in 2-universal terms, as the 2-terminal coalgebra for the endofunctor on $Cat$ (locally small categories) which takes a category to its small-coproduct cocompletion. See [[terminal coalgebra]] for an extended discussion.

\hypertarget{as_operations}{}\subsubsection*{{As operations}}\label{as_operations}

Let $\mathbf{F}$ denote the free (strict) monoidal category generated by $n$-ary operations $\theta_n: x^n \to x$, one for each arity $n \geq 0$. A (finite) \textbf{planar forest with ($n$) live leaves} is a morphism $\phi: x^n \to x^m$ in $\mathbf{F}$; a (finite) \textbf{planar tree with ($n$) live leaves} is a morphism $\phi: x^n \to x$.

The previous description is more a theorem than definition, but it points to the recursive construction of trees based on the fundamental equivalence between forests and trees:

\begin{itemize}%
\item The identity $x \to x$ corresponds to a root considered as a live leaf;


\item Given trees with live leaves $f_j \colon x^{n_j} \to x$, where $j \in \{1 \ldots, k\}$, there is a forest

\begin{displaymath}
f_1 \otimes \ldots \otimes f_k \colon x^{n_1 + \ldots + n_k} = x^{n_1} \otimes \ldots \otimes x^{n_k} \to x \otimes \ldots \otimes x = x^k
\end{displaymath}
whose set of live leaves is the disjoint union of sets of live leaves of the $f_j$.


\item Given a forest with live leaves

\begin{displaymath}
f_1 \otimes \ldots \otimes f_k \colon x^{n_1 + \ldots + n_k} = x^{n_1} \otimes \ldots \otimes x^{n_k} \to x \otimes \ldots \otimes x = x^k
\end{displaymath}
there is a tree

\begin{displaymath}
\theta_n \circ (f_1 \otimes \ldots \otimes f_k) \colon x^{n_1 + \ldots + n_k} \to x
\end{displaymath}
with the same set of live leaves.



\end{itemize}
In more straightforward combinatorial language: if a finite planar tree is a functor $F \colon [n]^{op} \to \Delta_a$ from a finite ordinal to the augmented [[simplex category]], and a \textbf{leaf} is an element without predecessors in the poset of elements of $F$, then we can consider as extra structure some subset of the leaves whose elements are designated as \textbf{live}. The principle is that one is permitted to graft roots of trees onto live leaves, but not onto dead ones. (Dead leaves arise by plugging in the constant = $0$-ary operation $\theta_0 \colon I = x^0 \to x$.)

Fancier versions of this basic recursive construction may involve ``colored trees'', ``cherry trees'', and so on, and figure prominently in the theory of [[operads]], especially in the construction of [[free operads]].

In fact, this type of recursivity is at the root (pun perhaps intended) of the [[cumulative hierarchy]] conception of sets in a material set theory like [[ZFC|ZFC set theory]]: all sets are collections of sets $\{x_1, \ldots, x_n\}$, and all sets are formed in this way. In order to found this conception on trees in a way that accepts the [[axiom of foundation]], one must restrict to \emph{well-founded} trees. A tree (pictured as a free category on a digraph, i.e., as a certain poset $P$) is \textbf{well-founded} if every object of $P^{op}$ is bounded above by a maximal element, or equivalently if there are no infinite chains $x_0 \lt x_1 \lt \ldots$ in $P^{op}$ starting from the root $x_0$. (Chains starting from the root are also called \textbf{branches}.) See [[well-founded relation]] for other formulations of this definition (including those suitable for [[constructive mathematics]]; see [[pure set]] for details on this construction of the cumulative hierarchy, including using arbitrary trees for \emph{ill-founded} sets.

The category of well-founded trees admits a (2-)universal description, as an [[initial algebra]] for a certain endofunctor on [[Cat]]. See [[well-founded forest]] for details.

To be continued\ldots{}

Very nice! Is there a similar story worth telling for possibly infinite trees, corecursion, etc.

\emph{Toby}: Well-founded trees (and pure sets) may be defined recursively; ill-founded trees (and pure sets) may be defined corecursively; there is stuff about this at [[pure set]]. (Note that even a well-founded tree may be infinite, as long as some vertex has infinitely many branches out of it.)

\hypertarget{as_relational_structures}{}\subsubsection*{{As relational structures}}\label{as_relational_structures}

A \emph{rooted tree} can be defined as a [[relational structure]] and as such serves as a useful [[geometric models for modal logics|model]] in the context of [[modal logics]]. In this form it consists of a set of \emph{nodes}, \emph{vertices} or whatever your preferred terminology is, and a binary relation, $S$, on $T$. These are to satisfy the following:

\begin{itemize}%
\item the set $T$ contains a unique element $r$ called the \textbf{root}, such that, for all $t\in T$, $S^*r t$ holds, where $S^*$ is the reflexive-[[transitive closure]] of $S$;


\item if $t\in T$, and $t\neq r$, then there is a unique $t'\in T$ such that $S t' t$;


\item $S$ is \textbf{acyclic}, so for all $t\in T$, $\neg S^+ t t$, where $S^+$ is the [[transitive closure]] of $S$.



\end{itemize}
This last property, of course, implies that $S$ is irreflexive.

\hypertarget{as_polynomial_endofunctors_after_kock}{}\subsubsection*{{As polynomial endofunctors (after Kock)}}\label{as_polynomial_endofunctors_after_kock}

A new way of thinking about (rooted, usually assumed finite) trees has been introduced by \hyperlink{Kock}{Joachim Kock}.

\begin{defn}
\label{}\hypertarget{}{}
A \emph{tree} $T$ consists of a set $T_0$ of edges, a set $T_1$ of nodes, and a set $T_2$ of \emph{input flags}, all assumed finite, together with functions

\begin{displaymath}
T_0 \stackrel{s}{\leftarrow} T_2 \stackrel{p}{\to} T_1 \stackrel{t}{\to} T_0
\end{displaymath}
such that

\begin{itemize}%
\item $t$ is injective,
\item $s$ is injective and its image is complementary to a singleton $\{r\}$ (called the \emph{root}), and
\item for all $e \in T_0$ there exists a natural number $k$ such that $\sigma^k(e) = r$, where $\sigma : T_0 \to T_0$ is the ``walk-to-root'' function defined by $e \mapsto t(p(s^{-1}(e)))$ if $e \neq r$, else $r \mapsto r$.

\end{itemize}
\end{defn}
Some commentary is in order. The subscript $0$ for edges and $1$ for nodes is consonant with standard usage in [[string diagrams]], where edges are labeled by $0$-cells in a monoidal category and nodes by $1$-cells. Each node is pictured as having a multiplicity of (and possibly zero) input edges and exactly one outgoing edge; the map $t: T_1 \to T_0$ maps a node to its outgoing edge. Only the root edge is not an input edge of any node, i.e., the unique inhabitant of the complement of $im(s)$ is what we call the root $r$. Now: the input ``function'' $T_1 \to T_0$ is actually a multivalued function, taking a node to the set of its input edges, and is therefore represented as a [[relation]] or [[span]] from $T_0$ to $T_1$. The domain of this relation $T_2$ is the set of ordered pairs $(e, v)$ where $e \in T_0$ is an input edge of $v \in T_1$; this may be called a ``flag'' (thinking of a general flag as a chain of incidence relations, here a 1-step chain with $e$ input-incident to $v$).

To each tree $T$ described in this form, there is an associated [[polynomial endofunctor]] $p_T: Set/T_0 \to Set/T_0$ controlled by the data

\begin{displaymath}
T_0 \stackrel{s}{\leftarrow} T_2 \stackrel{p}{\to} T_1 \stackrel{t}{\to} T_0
\end{displaymath}
and defined by the composition

\begin{displaymath}
Set/T_0 \stackrel{s^\ast}{\to} Set/T_2 \stackrel{\Pi_p}{\to} Set/T_1 \stackrel{\Sigma_t}{\to} Set/T_0
\end{displaymath}
where as usual $\Sigma_f \dashv f^\ast \dashv \Pi_f$. Notice that the functors on display preserve pullbacks, so $p_T$ preserves pullbacks.

There is a [[double category]] whose $0$-cells are sets $I$, whose horizontal $1$-cells are polynomial endofunctors $p: Set/I \to Set/J$, whose vertical $1$-cells are pullback functors $f^\ast: Set/I \to Set/I'$ induced by functions $f: I' \to I$, and whose $2$-cells are [[cartesian natural transformations]] of the form

\begin{displaymath}
\itexarray{
Set/I & \stackrel{p}{\to} & Set/J \\ 
\mathllap{f^\ast} \downarrow & \swArrow & \downarrow \mathrlap{g^\ast} \\ 
Set/I' & \underset{p'}{\to} & Set/J'
}
\end{displaymath}
The category consisting of horizontal arrows and 2-cells between them is called the \emph{category of polynomial endofunctors}, $PolyEnd$. Kock defines a category of trees where objects are trees $T$ and whose morphisms are morphisms between the corresponding endofunctors $p_T$ as objects in $PolyEnd$.

As Kock shows, this description of trees is well-adapted to the usual sorts of combinatorics that emerge in the study of [[operads]], such as free operads.

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[category of trees]]


\item in [[perturbative quantum field theory]] [[Feynman graphs]] of vanishing ``[[loop order]]'' are trees, and their contribution to the [[Feynman perturbation series]] is hence called the \emph{tree level} contribution


\item [[shuffle of trees]]



\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item [[Joachim Kock]], \emph{Polynomial functors and trees}, arXiv:\href{http://arxiv.org/abs/0807.2874}{0807.2874}

\end{itemize}
[[!redirects tree]] [[!redirects trees]]

[[!redirects planar tree]] [[!redirects planar trees]]

[[!redirects rooted tree]] [[!redirects rooted trees]]



\end{document}