Definition: A tree is a triple $(T,\sigma,\pi)$ where $T$ is a set and $\sigma$ is a so-called successor function from $T$ to the set $T^*$ of all nonempty subsets of $T$, together with a surjective map $\pi:T\rightarrow \mathbb{N}$ such that the following diagram commutes

$$ \newcommand{\ra}[1]{\!\!\xrightarrow{\quad#1\quad}\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{ll} T & \ra{\sigma} & T^* \\ \da{\pi} & & \da{\pi^*} \\ \mathbb{N} & \ra{\sigma^*}&\mathbb{N}^*\\ \end{array} $$

where $\sigma^*$ is the composition of the successor function on $\mathbb{N}$ followed by inclusion into the set $\mathbb{N}$ of all nonempty subsets of $\mathbb{N}$ and $\pi^*:T^*\rightarrow \mathbb{N}^*$ is the map induced by $\pi$ on nonempty subsets of $T$.

I am wanting to understand how the intervals used in the construction of the Cantor middle-third set could be described using the language is this definition. What seems clear to me is that the set $T$ would be subintervals of [0,1] in the construction of the Cantor set, and $\sigma$ would be a relation relating each parent intervals to their two children, which accounts for $T^*$. What I am not clear about is how the rest of the diagram applies. I have had a few ideas about enumerating the sets, but none seem to sync up with the diagram in a sensible way. Additionally I think the fact that the branches in the Cantor construction are nested should be reflected somehow throughout the map. I am imagining some sort of map that takes a word in $\mathbb{N}$ to a "nested word" in $\mathbb{N}^*$, but I am struggling to make this explicit.


The map $\pi$ assigns to each node of the tree $T$ its level. In the specific case of the binary tree of intervals used in the construction of the middle-thirds Cantor set, $\pi([0,1])=0$,


and so on: if $\pi(I)=n$, and $I_0$ and $I_1$ are the two children of $I$, then $\pi(I_0)=\pi(I_1)=n+1$. The map $\sigma^*$ takes $n\in\Bbb N$ to $\{n+1\}$, the singleton of the successor of $n$.

Saying that the diagram commutes is just saying that if $I$ is an interval on level $n$ of the tree, so that $\pi(I)=n$, then the set of children of $I$ is a subset of level $n+1$ of the tree: every child $J$ of $I$ will satisfy $\pi(J)=n+1$.

This is really not a definition of trees in general: it’s a definition of trees of height $\omega$.

  • $\begingroup$ But isn't the set containment $\supset$ implied in the Cantor construction via $\sigma$ is lost via $\sigma^*$? Given a particular interval on level $n$ it does not necessarily contain a child on level $n+1$. I'm looking for a way to preserve this containment via $\sigma^*$. $\endgroup$ – Earl Nov 20 '15 at 19:38
  • $\begingroup$ @hammy: Every interval on level $n$ has (and contains as subsets) exactly two children on level $n+1$. And you have no control over $\sigma^*$: it’s given, and is simply the map $\sigma^*(n)=\{n+1\}$. The containment relation among subsets of $T$ has nothing to do with the containment relation among subsets of $\Bbb R$ in the construction of the Cantor set. $\endgroup$ – Brian M. Scott Nov 20 '15 at 19:49
  • $\begingroup$ I understand the map you suggest, and thank you for the clear explanation. But what I am looking for is a map that preserves this containment. That is, shouldn't we be able to find a map that indicates when $\sigma^*(n)\in\mathbb{N}^*$ is 'contained' in $n\in\mathbb{N}$ instead of just knowing that $\sigma^*(n)$ is on the $n+1$ level. $\endgroup$ – Earl Nov 20 '15 at 20:46
  • $\begingroup$ @hammy: I can’t make any sense out of that, I’m afraid: $\sigma^*(n)$ isn’t even in the tree, let alone in the $(n+1)$-st level. The definition that you’ve given in your question is simply a fancy way of defining the levels of a tree of height $\omega$. If you want something more than or otherwise different from that, you should toss that definition and explain exactly what it is that you’re trying to do. $\endgroup$ – Brian M. Scott Nov 20 '15 at 20:51
  • $\begingroup$ @ Brian M. Scott- Got it. I was hoping that I could say more with the diagram. I see now that $\sigma^*$ is not a choice. I did not realize that successor function implied that it must be a "+1". $\endgroup$ – Earl Nov 22 '15 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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