# Infinite rooted binary tree

Let $T$ be a rooted infinite binary tree and let $\text{Sym}(T)$ be the group of all symmetries of $T$.

1. Show that any $\alpha \in \text{Sym}(T)$ sends the root to the root, even if you just view $T$ as an unrooted tree.

2. Show that $\text{Sym}(T)$ contains an index 2 subgroup isomorphic to $\text{Sym}(T)\times\text{Sym}(T)$.

3. Show that $\text{Sym}(T)$ is uncountable.

If anyone can offer any assistance on this problem, it would be greatly appreciated.

-

I am assuming that by rooted infinite binary tree you actually mean the rooted complete binary tree of height $\omega$.

HINT for (2): For each vertex $v$ of $T$ let $v^L$ be the left child of $v$, and let $v^R$ be the right child of $v$. Let $T_L$ and $T_R$ be the subtrees of $T$ with roots $r^L$ and $r^R$, respectively.

1. Show that if $\sigma\in\operatorname{Sym}(T)$, then either $\sigma(r^L)=r^L$ and $\sigma(r^R)=r^R$, or $\sigma(r^L)=r^R$ and $\sigma(r^R)=r^L$.
2. Let $S_0=\{\sigma\in\operatorname{Sym}(T):\sigma(r^L)=r^L\text{ and }\sigma(r^R)=r^R\}$; show that $S_0$ is a subgroup of $\operatorname{Sym}(T)$, and find an isomorphism between $S_0$ and $\operatorname{Sym}(T_L)\times\operatorname{Sym}(T_R)$.

HINT for (3): For $n\in\omega$ let $L_n$ be the set of vertices of $T$ of height $n$ (equivalently, those whose distance from the root $r$ is $n$). Thus, $L_0=\{r\}$, and $L_1=\{r^L,r^R\}$. For each function $\varphi:\omega\to\{0,1\}$ we’ll define a different $\sigma_\varphi\in\operatorname{Sym}(T)$; that will certainly provide uncountably many symmetries.

The idea is to start at the root and work up through the levels of $T$. At some levels we’ll interchange siblings, and at others we won’t; the function $\varphi$ will determine which levels are which. Specifically, when $\varphi(n)=1$, we’ll swap the children of each vertex in $L_n$. Thus, if $\varphi(0)=1$, $\sigma_\varphi$ will swap $r^L$ and $r^R$: $\sigma_\varphi(r^L)=r^R$ and $\sigma_\varphi(r^R)=r^L$; otherwise, if $\varphi(0)=0$, $\sigma_\varphi(r^L)=r^L$ and $\sigma_\varphi(r^R)=r^R$. Now we want to work our way up through the tree, doing the same thing at each level.

Specifically, suppose that we’ve already defined $\sigma_\varphi(v)$ for each $v\in L_n$. Each vertex in $L_{n+1}$ is of the form $v^L$ or $v^R$ for some $v\in L_n$, so we can define $\sigma_\varphi\upharpoonright L_{n+1}$ as follows:

If $\varphi(n)=0$, let $\sigma_\varphi(v^L)=\big(\sigma_\varphi(v)\big)^L$ and $\sigma_\varphi(v^R)=\big(\sigma_\varphi(v)\big)^R$ for each $v\in L_n$; this sends the left child of $v$ to the left child of $\sigma_\varphi(v)$ and the right child of $v$ to the right child of $\sigma_\varphi(v)$, so it doesn’t swap $v$’s children.

If $\varphi(n)=1$, let $\sigma_\varphi(v^L)=\big(\sigma_\varphi(v)\big)^R$ and $\sigma_\varphi(v^R)=\big(\sigma_\varphi(v)\big)^L$ for each $v\in L_n$; this sends the left child of $v$ to the right child of $\sigma_\varphi(v)$ and the right child of $v$ to the left child of $\sigma_\varphi(v)$, so it does swap $v$’s children.

1. Verify that $\sigma_\varphi$ really is a symmetry of $T$.
2. Show that if $\varphi$ and $\psi$ are distinct functions from $\omega$ to $\{0,1\}$, $\sigma_\varphi\ne\sigma_\psi$.
-
Your hint for (3) doesn't quite work out. If, e.g., $\varphi(1)=1$ and $\varphi(2)=0$, then $\sigma_\varphi (\langle 0 \rangle)=\langle 1 \rangle$ but $\sigma_\varphi (\langle 00 \rangle)=\langle 00 \rangle$ (not a child of $\sigma_\varphi (\langle 0 \rangle$)! You will probably have to define the function $\sigma_\varphi$ on the coordinates of the finite binary sequences. Something like $\sigma_\varphi (\langle b_0 \cdots b_{n-1} \rangle ) = \langle (\varphi(0)\oplus b_0 )\cdots (\varphi(n-1)\oplus b_{n-1} ) \rangle$ where $a\oplus b$ is the modulo-2 sum of $a$ and $b$. – arjafi Mar 5 '12 at 8:55
@Arthur: You’re right, though I think that instead I’ll define $\sigma_\varphi\upharpoonright L_n$ recursively. (I’ll see how it looks when I actually write it down.) – Brian M. Scott Mar 5 '12 at 8:59
Looking good! (The recursive definition is probably better from a pedagogical standpoint.) – arjafi Mar 5 '12 at 11:59

To get you started, consider the degree of each vertex.

-
Ok. I understand that every degree of a vertex can only be send to other vertices with the same degree. How do I start to show that and $\alpha$ sends the root to root if I am considering $T$ as an unrooted tree? – Metena Mar 4 '12 at 18:05
For convenience, name your root vertex $r$, but then consider your tree as if it were unrooted. The vertex $r$ is still the only vertex of degree two in the entire tree, so $r$ maps to $r$ under any symmetry. – Austin Mohr Mar 4 '12 at 18:33
Right. I figured out for the first part that r is always fixed. Thanks! Now onto part 2 with the subgroup of index 2. But doesn't an infinite group by definition always contain a subroup that is normal, so that would be the subgroup of index 2? – Metena Mar 4 '12 at 18:39
@Metena: Which definition are you referring to? The definition of an infinite group doesn't refer to normal subgroups; a group is infinite if and only if it has infinitely many elements. For question 2, you could classify the symmetries according to whether they swap the two subtrees attached to the root or not. – joriki Mar 5 '12 at 7:01