Skip to main content

Lists and finite trees are E3

In order to prove the fgoagog thing we need to be able to do computations on trees at a low level of the Grzegorczyk hierarchy, so it doesn’t mess up the complexity of the whole group computation. I will give a model of finite trees that lies in E3, the same level as Cannonito/Gatterdam’s standard index for the free group. (( this post has been sitting as a draft since the beginning of May because I wanted to make some nice tree pictures, but I’d rather just publish it now. So, the trees section is copied out of my notes and might not make sense ))


First of all, I’ll show how to encode sequences of numbers so that they can be manipulated and read by E3 functions. Let (x1,,xn) be a sequence of n non-negative numbers.

First encode the list as a Gödel number:


where pi is the ith prime. (( it’s just occurred to me that I haven’t shown that things such as finding primes and divisiblity tests and so on are E3 computable. I’ll do another post after this one with suitable definitions for all that stuff ))

In order to actually do anything with this encoded list, we need to be able to find out its length and the value of the entry at any given position. plog(x,p) return the exponent of the prime p in x:


I’m using (x)i instead of xi to denote the ith element of an encoded list, just so it’s clear that’s what’s happening later on.

lh(x) finds the length of an encoded list:


Note that μixP(i)=x+1 if there is no ix such that P(i) holds. The ix bit in the minimisation is so that the function is bounded – it doesn’t matter what upper bound I pick as long as it’s “enough”.

find(x,n) returns the first occurence of n in an encoded list x:


Make use of find to determine whether an encoded list contains a given value:


This function to find the largest element of a list x, biggest(x), is defined by using a helper function biggest(x,n), which gives the biggest element up to (x)n:


slice(x,s,e), which I will also write x[se], gives you the sublist of x starting at position s and ending at position e. The max/min stuff is to make sure this function works sensibly even when given wrong inputs:

\[ slice(x,s,e)=i=se(pi+1s)(x)i+1e=max(1,min(e,lh(x)))s=max(1,min(s,e))

splice(x,n), also written x:n, appends a value n to the end of an encoded list x:



A tree consists of a set of vertices V and a set of edges E connecting pairs of vertices, with no loops.

A rooted tree has a unique vertex v0 said to be at the ‘top’. In an ordered tree, the set of children of each vertex is ordered, so there is a leftmost child, and so on. A plane recursive tree is a rooted, ordered tree constructed by a process which begins with the root node and recursively adds vertices below existing ones.

We can assign a labelling to a plane recursive tree by giving vertices labels corresponding to the order in which they were added to the tree, beginning with 0 for the root. This way, the sequence of labels encountered heading outwards from the root is always increasing. Every edge can also be given a unique labelling by saying that the edge eij, connecting vertex vi to vj, has label max(i,j).

Suppose we have a tree T=(V,E) with root vertex v0. T is En computable if there is an En-decidable labelling i:VN (we can assume i(v0)=0) and an En-computable “parent function” pT:i(V)i(V) which gives the label of the parent of a vertex. We also require that pT(v0)=0.

A finite plane recursive tree can be entirely described in a canonical way by a depth-first walk. Note that every node has a single parent and a finite ordered set of children. The process on ‘visiting’ a vertex vi goes as follows: for each child node vj, travel along eij and visit vj, then travel backwards along eij. The sequence of labelled edges travelled along by beginning this process at v0 is the depth-first walk of the tree. Note that each edge is visited exactly twice – once heading outwards, and again heading back towards the root.

This sequence can then be encoded as a Gödel number by the method in Section 1. We will define a function ϕ(x,n) which takes an encoded tree x and gives the parent of the vertex with label n. Note that the root vertex’s label will not appear in this sequence because it has no associated edge.

Some functions to work with encoded trees:

To find the first and second occurrences of the edge with label n in the walk:


To get the label of the nth child of the root:


To find the subtree descended from the nth child node:


The number of children of the root node:


Whether the root has a child with label n:


Finally, the parent function. The idea is to basically do the depth-first walk, remembering which vertex you just came from. If you reach a subtree which doesn’t contain n then turn back, or if you reach the required vertex then return the label of the vertex you just came from.


where z:=μi<numchildren(x)contains(subtree(x,i),n).

We will also need to know if the tree contains an edge eij:



A finite ordered tree is E3 computable.


As the tree is finite, of course its labelling is E3-decidable, and pbfx(n) as defined above is E3-computable.