1
$\begingroup$

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.

2 Answers 2

3

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$.
  • 0
    If we make an isomorphism to $\{-1,+1\}\times\Bbb{Z}(2^{\infty})$ then the group identity is the root of the graph. Do these results follow more simply from that construction?2018-04-24
0

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

  • 0
    @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.2012-03-05