Let $T$ be the set of full binary trees. In what way $T^7 \cong T$?

246 Views Asked by At

I was reading the slides of a talk by Tom Leinster. I have trouble understanding the last line of page 17 (pages 1-15 are irrelevant and can be skipped). Could someone please explain it to me?

If I translate the images correctly, $T$ is defined to be the set of all full binary trees. A full binary tree is either:

  • a single vertex, $\bullet$

  • a graph formed by taking two full binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree.

Then $T \cong \{ \bullet \} \sqcup (T \times T)$. Thus $$|T| = 1 + |T|^2.$$ (Note: I think the last equation also holds if we defined $T$ to be the set of all (not necessarily full, and possibly empty) binary trees since then $T \cong \{\emptyset\} \sqcup (T \times T)$.)

Forgetting what $|T|$ stands for, we could solve the above equation for $|T|$ and find that $|T|=e^{\pm i\pi/3}$. Hence $|T|^7 = |T|$. This suggests that $T^7 \cong T$. Tom Leinster writes "This really is true!". Why is that?

1

There are 1 best solutions below

2
On BEST ANSWER

The paper Seven Trees in One exhibits a "very explicit bijection" $T^7\cong T$. It is perhaps a bit cumbersome because it requires separating into five cases based on how the seven trees look in the first four levels of depth. A proof is present too. Disclaimer: I haven't read it.

Another paper Objects of Categories as Complex Numbers discusses the relationship between algebra (in particular, manipulating elements of polynomial semirings modulo relations) and natural isomorphisms. Indeed, if we consider an initial set of relations satisfied by an object to be a class of prototypical isomorphisms, then we can "do algebra" utilizing the relations and translate that into a sequence of isomorphisms. For example the authors write that one can do

$$\begin{array}{ll} T & \cong 1+T^2 \\ & \cong 1+T+T^3 \\ & \cong 1+T+T^2+T^4 \\ & \cong 2T+T^4 \\ & \cdots \\ & \cong T^7 \end{array} $$

with $18$ isomorphisms in total. (This is not the bijection exhibited in 7 trees in 1.)