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


*

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

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

*Show that $\text{Sym}(T)$ is uncountable.
If anyone can offer  any assistance on this problem, it would be greatly appreciated.
 A: 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.

*

*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$.

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


*

*Verify that $\sigma_\varphi$ really is a symmetry of $T$.

*Show that if $\varphi$ and $\psi$ are distinct functions from $\omega$ to $\{0,1\}$, $\sigma_\varphi\ne\sigma_\psi$.

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