Claim 2.4. There exists a sequence $(u_{\rho },\bar {f_{\rho }}, \bar {A_{\rho }} : \rho \in T)$ such that:

1. a. $\bar {f_{\rho }}=(f_{\rho ,\nu } : \nu \in T_{lg(\rho )})$ .

2. b. $f_{\rho ,\nu } \in Sym(u_{\rho })$ has no fixed points.

3. c. $\bar {A_{\rho }}=(A_{\rho ,\nu } : \nu \in T_{lg(\rho )})$ . We shall denote $\underset {\nu \in T_{lg(\rho )}}{\cup }A_{\rho ,\nu }$ by $A_{\rho }'$ .

4. d. $A_{\rho ,\nu } \subseteq u_{\rho } \subseteq H(\aleph _0)$ and $\Sigma \{|u_{\eta }| : \eta <_* \rho \} \ll |A_{\rho ,\nu }|$ .

5. e. $\nu _1 \neq \nu _2 \in T_{lg(\rho )} \rightarrow A_{\rho ,\nu _1} \cap A_{\rho ,\nu _2}=\emptyset $ .

6. f. If $\rho \in 2^n$ and $w=w(\dots ,x_{\nu },\dots )_{\nu \in 2^n}$ is a non-trivial group term of length $\leq n$ then:

   1. 1. $w(\dots ,f_{\rho ,\nu },\dots )_{\nu \in 2^n} \in Sym(u_{\rho })$ has no fixed points.

   2. 2. $(w(\dots ,f_{\rho ,\nu },\dots )_{\nu \in 2^n}(\underset {\nu \in 2^n}{\cup }A_{\rho ,\nu })) \cap \underset {\nu \in 2^n}{\cup }A_{\rho ,\nu }=\emptyset $ .

7. g. $\{f_{\rho ,\nu } : \nu \in T_{lg(\rho )}\}$ generate the group $K_{\rho }$ (whose set of elements is $u_{\rho }$ ) which is considered as a group of permutations of $u_{\rho }$ .

Proof We choose $(u_{\rho }, \bar {f_{\rho }},\bar {A_{\rho }})$ by $<_*$ -induction on $\rho $ as follows: Arriving at $\rho $ , we choose the following objects:

1. a. $n_{\rho }^1$ such that $\Sigma \{|u_{\nu }| : \nu <_* \rho \}2^{lg(\rho )+7} \ll n_{\rho }^1$ and let $n_{\rho }^0=\frac {n_{\rho }^1}{2^{lg(\rho )}}$ .

2. b. Let $H_{\rho }$ be the group generated freely by $\{x_{\rho ,\nu } : \nu \in T_{lg(\rho )}\}$ .

3. c. In $H_{\rho }$ we can find $(y_{\rho ,n} : n<\omega )$ which freely generate a subgroup (we can do it explicitly, for example, if a and b freely generate a group, then $(a^nb^n : n<\omega )$ are as required), wlog for $w_1$ and $w_2$ as in Claim 2.4(f) and $n_1<n_2$ we have $w_1y_{\rho ,n_1} \neq w_2y_{\rho ,n_2}$ .

   Now choose $A_{\rho ,\nu }^1 \subseteq \{y_{\rho ,n} : n<\omega \}$ for $\nu \in 2^{lg(\rho )}$ such that $\nu _1 \neq \nu _2 \rightarrow A_{\rho ,\nu _1}^1 \cap A_{\rho ,\nu _2}^1=\emptyset $ and $n_{\rho }^0 \leq |A_{\rho ,\nu }^1|$ .

4. d. Let $\Lambda _{\rho }=\{w : w=w(\dots ,x_{\rho ,\nu },\dots )_{\nu \in T_{lg(\rho )}}$ is a group word of length $\leq lg(\rho ) \}$ .

As $H_{\rho }$ is free, it’s residually finite, hence there is a finite group $K_{\rho }$ and an epimorphism $\phi _{\rho }: H_{\rho } \rightarrow K_{\rho }$ such that $\phi _{\rho } \restriction ((\underset {\nu \in 2^{lg(\rho )}}{\cup }A_{\rho ,\nu }^1) \cup \Lambda _{\rho } \cup \{wa : w\in \Lambda _{\rho } \wedge a\in \underset {\nu \in 2^{lg(\rho )}}{\cup }A_{\rho ,\nu }^1\})$ is injective (note that there is no use of the axiom of choice as we can argue in a model of the form $L[A]$ ). WLOG $K_{\rho } \subseteq H(\aleph _0)$ and $K_{\rho }$ is disjoint to $\cup \{u_{\nu } : \nu <_* \rho \}$ .

We now define the following objects:

1. a. $u_{\rho }=K_{\rho }$ .

2. b. $A_{\rho ,\nu }=\{\phi _{\rho }(a) : a \in A_{\rho ,\nu }^1\}$ .

3. c. For $\nu \in 2^{lg(\rho )}$ , let $f_{\rho ,\nu } : u_{\rho } \rightarrow u_{\rho }$ be multiplication by $\phi _{\rho }(x_{\rho ,\nu })$ from the left.

It’s now easy to verify that $(u_{\rho }, \bar {A_{\rho }}, \bar {f_{\rho }})$ are as required, so $U=\cup \{u_{\rho } : \rho \in T\}$ .

Proof By the proof of Ramsey’s theorem and the arguments which are implicit in the proof of Claim 2.7. Note that while the statement “there exists an infinite homogeneous set” is analytic, we can Borel-compute that homogeneous set. See the proof of Claim 6 in [Reference Horowitz and Shelah2] for more details.

Claim 2.7. If $f\in H_3$ then there exists $g\in Sym(U)$ such that for some

$(B,\eta _1,\eta _2,\bar a,\bar b,\bar {\nu })$ , g and $(B,\eta _1,\eta _2,\bar a,\bar b, \bar {\nu })$ are as required in Claim 2.6(c)(2) (and therefore, there are also $(\bar c,\bar d,\bar e)$ as required there). Moreover, g is unique once $(B,\eta _1,\eta _2,\bar a,\bar b,\bar {\nu })$ is fixed.

Proof $f\in H_3$ , so $\mathbf {B}_{1,1}(f)=0$ .

We shall first observe that if g is defined as above, then g is a permutation of U with no fixed points. It’s also easy to see that g is unique once $(B,\eta _1,\eta _2,\bar a,\bar b,\bar {\nu })$ has been chosen. Therefore, it’s enough to find $(B,\eta _1,\eta _2,\bar a,\bar b,\bar {\nu })$ as required.

Case I ( $\mathbf {B}_{1,2}(f)=1$ ). For infinitely many n, $f"(A_{\eta _1 \restriction n}') \nsubseteq \cup \{u_{\rho } : \rho \leq _* \eta _1 \restriction n\}$ . In this case, let $B_0=\{n : $ there is $a\in A_{\eta _1 \restriction n}'$ such that $f(a) \notin \cup \{u_{\rho } : \rho \leq _* \eta _1 \restriction n\}$ , and for every $n\in B_0$ , let $a_n$ be the $<_*$ -first element in $A_{\eta _1 \restriction n}'$ witnessing that $n\in B_0$ . Let $b_n=f(a_n)$ and let $\nu _n \in T$ be the sequence for which $b_n \in u_{\nu _n}$ . Apply Ramsey’s theorem (we don’t need the axiom of choice, as we can argue in some $L[A]$ ) to get an infinite set $B \subseteq B_0$ such that $c_{k,l} \restriction [B]^k$ is constant for every $(k,l) \in \{(2,1),(2,2),(2,4),(3,1),(3,3)\}$ , where for $n_1<n_2<n_3$ :

1. a) $c_{2,1}(n_1,n_2)=TV(lg(\nu _1)<lg(\nu _2))$ .

2. b) $c_{2,2}(n_1,n_2)=TV(\nu _{n_2} \in \{\nu _n : n\leq n_1\})$ .

3. c) $c_{3,1}(n_1,n_2,n_3)=TV(lg(\nu _{n_2} \cap \nu _{n_3})>\nu _{n_1})$ .

4. d) $c_{3,3}(n_1,n_2)=\nu _{n_2}(lg(\nu _{n_1} \cap \nu _{n_2})) \in \{0,1,$ undefined $\}$ .

We shall prove now that $(lg(\nu _n) : n\in B)$ has an infinite increasing subsequence: Choose an increasing sequence $n(i) \in B$ by induction on i such that $j<i \rightarrow lg(\nu _{n(j)})<lg(\nu _{n(i)})$ . Arriving at stage $i=j+1$ , suppose that there is no such $n(i)$ , then $\{f(a_n) : n\in B \setminus n(j)\} \subseteq \cup \{u_{\rho } : lg(\rho ) \leq lg(\nu _{n(j)})\}$ , hence $\{f(a_n) : n\in B\setminus n(j)\}$ is finite. Similarly, $\{\nu _n : n\in B\setminus n(j)\}$ is finite, and therefore, there are $n_1<n_2 \in B\setminus n(j)$ such that $\nu _{n_1}=\nu _{n_2}$ and $f(a_{n_1})=f(a_{n_2})$ . As f is injective, $a_{n_1}=a_{n_2}$ , and by the choice of the $a_n$ , $a_{n_1} \in u_{\eta _1 \restriction n_1}$ and $a_{n_2} \in u_{\eta _1 \restriction n_2}$ .

This is a contradiction, as $u_{\eta _1 \restriction n_1} \cap u_{\eta _1 \restriction n_2}=\emptyset $ .

Therefore, there is an infinite $B' \subseteq B$ such that $(lg(\nu _n) : n\in B')$ is increasing, and wlog $B'=B$ .

Now we shall note that if $n_1<n_2<n_3$ are from B, then $lg(\nu _{n_2} \cap \nu _{n_3})>lg(\nu _{n_1})$ :

By the choice of B, $c_{3,1}(n_1,n_2,n_3)$ is constant for $n_1<n_2<n_3$ , so it suffices to show that $c_{3,1} \restriction [B]^3=true$ . Let $n_1=min(B)$ and $k=lg(\nu _{n_1})+1$ . The sequence $(\nu _n \restriction k : n\in B\setminus \{n_1\})$ is infinite, hence there are $n_2<n_3 \in B\setminus \{n_1\}$ such that $\nu _{n_2} \restriction k=\nu _{n_3} \restriction k$ . Therefore, $lg(\nu _{n_1})<k \leq lg(\nu _{n_2} \cap \nu _{n_3})$ , and as $c_{3,1}$ is constant on $[B]^3$ , we’re done.

For $n<k \in B$ such that k is the successor of n in B, let $\eta _n=\nu _n \cap \nu _k$ . Suppose now that $n<k<l$ are successor elements in B, then $lg(\eta _k)=lg(\nu _k \cap \nu _l)>lg(\nu _n) \geq lg(\nu _n \cap \nu _k)=lg(\eta _n)$ , and $\eta _n,\eta _k \leq \nu _k$ , therefore, $\eta _n$ is a proper initial segment of $\eta _k$ and $\eta _2:=\underset {n<\omega }{\cup }\eta _n \in 2^{\omega }$ . If $n<k \in B$ are successor elements, then $lg(\eta _k)>lg(\nu _n)$ (by a previous claim), therefore, $\nu _n \cap (T\setminus \nu _k)$ is disjoint to $\eta _2$ , hence $\nu _n \cap \eta _2=\nu _n \cap \nu _k=\eta _n$ . Therefore, if $n<k \in B$ then $\nu _n \cap \eta _2$ is a proper initial segment of $\nu _k \cap \eta _2$ and $\eta _2=\underset {n<\omega }{\cup }(\nu _n \cap \eta _2)$ .

It’s now easy to verify that $(B,\eta _1,\eta _2,\bar a,\bar b,\bar {\nu })$ and g are as required.

Case II ( $\mathbf {B}_{1,2}(f)=0$ and $n_1$ stands for  $\mathbf {B}_{1,3}(f)$ ). There is $n_1$ such that for every $n_1 \leq n$ , $f"(A_{\eta _1 \restriction n}') \subseteq \cup \{u_{\rho } : \rho \leq _* \eta _1 \restriction n\}$ .

For each n, recall that $v_n=\{a\in A_{\eta _1 \restriction n}' \subseteq u_{\eta _1 \restriction n} : f(a)\in u_{\eta _1 \restriction n}\}$ . $v_n$ satisfies $|A_{\eta _1 \restriction n}' \setminus v_n| \leq \Sigma \{|u_{\nu }| : \nu <_*\ \eta _1 \restriction n\}$ , and as $\Sigma \{|u_{\nu }| : \nu <_* \eta _1 \restriction n\} \ll |A_{\eta _1 \restriction n}'|$ , it follows that $\Sigma \{|u_{\nu }| : \nu <_* \eta _1 \restriction n\} \ll |v_n|$ . Recall also that for $a\in v_n$ , as $f(a) \in u_{\eta _1 \restriction n}$ , by Definition 2.5(e), $y_{a,f(a)}$ is well-defined.

We now consider three subcases:

Case IIA ( $\mathbf {B}_{1,4}(f)=1$ ). The set of $l_{a,f(a),n}$ for $a\in v_n$ and $n_1 \leq n$ is unbounded. In this case, we find an infinite $B\subseteq [n_1,\omega )$ and $a_n \in v_n$ for each $n\in B$ such that $(l_{a_n,f(a_n),n} : n\in B)$ is increasing. Now let $\eta _2:=\eta _1$ and define $\bar b$ , $\bar {\nu }$ and g as described in Definition 2.6. It’s easy to verify that $(B,\eta _1,\eta _2,\bar a,\bar b, \bar {\nu })$ are as required.

Case IIB ( $\mathbf {B}_{1,4}(f)=0$ and $\mathbf {B}_{1,6}(f)=1$ ). Case IIA doesn’t hold, but $\mathbf {B}_{1,6}(f)=1$ and there is an infinite $B\subseteq [n_1,\omega )$ , $l_{**}<l_*$ (see below) and $(a_n \in v_n : n\in B)$ (given by $\mathbf {B}_{1,8}(f)$ , $\mathbf {B}_{2,0}(f)$ and $\mathbf {B}_{1,7}(f)$ , respectively) such that:

1. a. $l_{a_n,f(a_n)}=l_*$ and $l_{**}=\mathbf {B}_{2,0}(f)<l_*$ .

2. b. $i_{a_n,f(a_n),l}=i_l^*$ for $l<l_*$ .

3. c. If $n\in B$ and $m\in B\cap n$ , then $\rho _{a_m,f(a_m),l_{**}} \nsubseteq \rho _{a_n,f(a_n),l_{**}}$ .

In this case we define $\bar b$ , $\bar {\nu }$ and g as in Definition 2.6 and we let $\eta _2:=\eta _1$ . It’s easy to see that $(B,\eta _1,\eta _2,\bar a,\bar b \bar {\nu })$ are as required.

Remark: By a routine Ramsey-type argument, it’s easy to prove that if $\mathbf {B}_{1,6}(f)=1$ then the values of $\mathbf {B}_{1,7}(f),\mathbf {B}_{2,0}(f)$ are well-defined and Borel-computable so the above conditions hold.

Case IIC ( $\mathbf {B}_{1,4}(f)=\mathbf {B}_{1,6}(f)=0$ ). $\neg IIA \wedge \neg IIB$ . We shall first prove that $\mathbf {B}_{2,1}(f)$ , $\mathbf {B}_{2,2}(f)$ , $\mathbf {B}_{2,3}(f)$ , $(\mathbf {B}_{2,4,n}(f) : n\in \mathbf {B}_{2,2}(f))$ and $(\mathbf {B}_{2,5,l}(f) : l<\mathbf {B}_{2,3}(f))$ are well-define and Borel computable.

Let $l(*)$ be the supremum of the $l(a,f(a))$ where $n_1 \leq n$ and $a\in v_n$ ( $l(*)<\omega $ by $\neg 2A$ ). We can find $l(**) \leq l(*)$ such that $B_1:=\{ n\in B : v_{n,1}=\{a\in v_n : l(a,f(a))=l(**)\}$ has at least $\frac {v_n}{l(*)}$ elements $\}$ is infinite. Next, we can find $i_*(l) \in \{1,-1\}$ for $l<l(**)$ such that $B_2:\{n \in B_1 : v_{n,2}=\{a\in v_{n,1} : \underset {l<l(**)}{\wedge }i_{a,f(a),l}=i_*(l)\}$ has at least $\frac {|v_n|}{2^{l(**)}l(*)}$ elements $\}$ is infinite. For each $n\in B_2$ , there are $\rho _{n,0},\dots ,\rho _{n,l(**)-1} \in T_n$ such that $v_{n,3}=\{a\in v_{n,2} : \underset {l<l(**)}{\wedge }\rho _{a,f(a),l}=\rho _{n,l} \}$ has at least $\frac {|v_n|}{l(**)2^{l(**)}2^{nl(**)}}$ elements. By Ramsey’s theorem, there is an infinite subset $B_3 \subseteq B_2$ such that for each $l<l(**)$ , the sequence $(TV(\rho _{m,l} \leq \rho _{n,l}) : m<n \in B_3)$ is constant. Therefore, we’re done showing that the above Borel functions are well-defined.

Now if $\mathbf {B}_{2,6}'(f)=1$ then we finish as in the previous case (this time we’re in the situation of Definition 2.6(b)(2)(K)(c)). If $\mathbf {B}_{2,6}'(f)=0$ , then we get a contradiction to the assumption that $f\in H_3$ , therefore we’re done.

Claim 2.8. If $w(x_0,\dots ,x_{k_*-1})$ is a reduced non-trivial group word, $f_0,\dots ,f_{k_{**}-1} \in H_3$ are pairwise distinct, $g_l \in G_{f_l}\ (l\in \{0,\dots ,k_{**}-1\})$ , $g_l=g_{\nu _l}^*$ where $\nu _l \in 2^{\omega } \setminus \{\mathbf {B}(f) : f\in H_3\}$ , $l=k_{**},\dots ,k_*-1$ and $(\nu _l : k_{**} \leq l<k_* )$ is without repetition, then $w(g_0, k_{*-1}) \in Sym(U)$ has a finite number of fixed points.

Proof Assume towards contradiction that $w(x_0,\dots ,x_{k_*-1})=x_{k(m-1)}^{i(m-1)} \cdot \ldots \cdot x_{k(0)}^{i(0)}$ , $\{f_0,\dots ,f_{k_*-1}\}$ and $\{g_0,\dots ,g_{k_*-1}\}$ form a counterexample, where $i(l) \in \{-1,1\}$ , $k(l)<k_*$ and $k(l)=k(l+1) \rightarrow \neg (i(l)=-i(l+1))$ for every $l<m$ . WLOG $m=lg(w)$ is minimal among the various counterexamples. Let $C=\{a\in U : w(g_0,\dots ,g_{k_*-1})(a)=a\}$ , this set is infinite by our present assumption. For $c\in C$ , define $b_{c,l}$ by induction on $l<m$ as follows:

1. 1. $b_{c,0}=c$ .

2. 2. $b_{c,l+1}=g_{k(l)}^{i(l)}(b_{c,l})$ .

Notational warning: The letter c with additional indices will be used to denote the elements of sequences of the form $\bar c$ from Definition 2.6(b)(2).

For all but finitely many $c\in C$ , $(b_{c,l} : l<m)$ is without repetition by the minimality of m, so wlog this is true for every $c\in C$ .

For every $c\in C$ , let $\rho _{c,l} \in T$ be such that $b_{c,l} \in u_{\rho _{c,l}}$ , and let $l_1[c]$ be such that $\rho _{c,l_1[c]} \leq _* \rho _{c,l}$ for every $l<m$ . We can choose $l_1[c]$ such that one of the following holds:

1. 1. $l_1[c]>0$ and $\rho _{c,l_1[c]-1} \neq \rho _{c,l_1[c]}$ .

2. 2. $l_1[c]=0$ and $\rho _{c,m-1} \neq \rho _{c,0}$ .

3. 3. $\rho _{c,0}=\dots =\rho _{c,m-1}$ .

We may assume wlog that $(l_1[c] : c\in C)$ is constant and that actually $l_1[c]=0$ for every $c\in C$ . In order to see that we can assume the second part, for $j<m$ let $w_j(x_0,\dots ,x_{k_*-1})=x_{k(j-1)}^{i(j-1)} \ldots x_{k(0)}^{i(0)}x_{k(m-1)}^{i(m-1)} \ldots x_{k(j)}^{i(j)}$ , then $w_j(g_0,\dots ,g_{k_*-1}) \in Sym(U)$ is a conjugate of $w(g_0,\dots ,g_{k_*-1})$ . The set of fixed points of $w_j(g_0,\dots ,g_{k_*-1})$ includes $\{b_{c,j} : c\in C\}$ , and therefore it’s infinite.

For $c\in C$ , $(b_{c,j},b_{c,j+1},\dots ,b_{c,m-1},b_{c,0},\dots ,b_{c,j-1})$ and $w_j(g_0,\dots ,g_{k_*-1})$ satisfy the same properties that $(b_{c,0},\dots ,b_{c,m-1})$ and $w(g_0,\dots ,g_{k_*-1})$ satisfy. Therefore, if $(l_1[c] : c\in C)$ is constantly $j>0$ , then by conjugating and moving to $w_j(g_0,\dots ,g_{k_*-1})$ , we may assume that $(l_1[c] : c\in C)$ is constantly $0$ .

Let $l_2[c]<m$ be the maximal such that $\rho _{c,0}=\dots =\rho _{c,l_2[c]}$ , so wlog $l_2[c]=l_*$ for every $c\in C$ . For $l<k_*$ let $\eta _{1,l}$ be $\mathbf {B}(f_l)$ if $l<k_{**}$ and $\nu _l$ if $l\in [k_{**},k_*)$ (we might also denote it by $\rho _l$ in this case). As $f_l \in H_3$ for $l<_{k_**}$ , and $\rho _l \notin \{\mathbf {B}(f) : f\in H_3\}$ for $l\in [k_{**},k_*)$ , it follows that $l_1<k_{**} \leq l_2<k_* \rightarrow \eta _{1,l_1} \neq \eta _{1,l_2}$ . Therefore, $(\eta _{1,l} : l<k_*)$ is without repetition.

Now let $\eta _{2,l}$ be defined as follows:

1. 1. If $l<k_{**}$ , let $\eta _{2,l}$ be $\eta _2$ from Definition 2.6(b)(2) for $f_l$ and $g_l$ .

2. 2. If $l\in [k_{**},k_*)$ , let $\eta _{2,l}=\eta _{1,l}$ .

Let $j(*)<\omega $ be such that:

1. a. $(\eta _{1,l} \restriction j(*) : l<k_*)$ is without repetition.

2. b. If $\eta _{1,l_1} \neq \eta _{2,l_2}$ then $\eta _{1,l_1} \restriction j(*) \neq \eta _{2,l_2} \restriction j(*)\ (l_1,l_2<k_*)$ .

3. c. If $\eta _{2,l_1} \neq \eta _{2,l_2}$ then $\eta _{2,l_1} \restriction j(*) \neq \eta _{2,l_2} \restriction j(*)\ (l_1,l_2<k_*)$ .

4. d. $j(*)>3m,k_*$ .

5. e. $j(*)>n(l_1,l_2)$ for every $l_1<l_2<k_*$ , where $n(l_1,l_2)$ is defined as follows:

   1. 1. If $k_{**} \leq l_1,l_2$ , let $n(l_1,l_2)=0$ .

   2. 2. If $l_1<k_{**}$ or $l_2<k_{**}$ , let $(\nu _n^1 : n \in B_1)$ and $(\nu _n^2 : n\in B_2)$ be as in Definition 2.6(b)(2) for $(f_{l_1},\eta _{1,l_1})$ and $(f_{l_2},\eta _{1,l_2})$ , respectively. If there is no $\nu _n^1$ such that $\nu _n^1 \nleq \eta _{1,l_1}$ and no $\nu _n^2$ such that $\nu _n^2 \nleq \eta _{1,l_2}$ , let $n(l_1,l_2)=0$ . Otherwise, there is at most one $n\in B_1$ such that $\nu _n^1 \nleq \eta _{1,l_1}$ and $\nu _n^1 \leq \eta _{1,l_2}$ and there is at most one $m\in B_2$ such that $\nu _m^2 \nleq \eta _{1,l_2}$ and $\nu _m^2 \leq \eta _{1,l_1}$ . If there are $\nu _n^1$ and $\nu _m^2$ as above, let $n(l_1,l_2)=lg(\nu _n^1)+lg(\nu _m^2)+1$ . If there is $\nu _n^1$ as above but no $\nu _m^2$ as above, let $n(l_1,l_2)=lg(\nu _n^1)+1$ , and similarly for the dual case.

6. f. $j(*)>m(l_1,l_2)$ for every $l_1<l_2<k_{**}$ where $m(l_1,l_2)$ is defined as follows: Let $(\nu _n^1 : n\in B_1)$ and $(\nu _m^2 : m\in B_2)$ be as in Definition 2.6(b)(2) for $(f_{l_1},\eta _{1,l_1})$ and $(f_{l_2},\eta _{1,l_2})$ , respectively. As $\eta _{1,l_1} \neq \eta _{1,l_2}$ , $|\{\nu _n^1 : n\in B_1\} \cap \{\nu _m^2 : m\in B_2\}| <\aleph _0$ , let $s(l_1,l_2)$ be the supremum of the length of members in this intersection and let $m(l_1,l_2):=s(l_1,l_2)+1$ .

We may assume wlog that $lg(\rho _{c,l_1[c]})>j(*)$ for every $c\in C$ . We now consider two possible cases (wlog $TV((\rho _{c,l} : l<m)$ is constant) is the same for all $c\in C$ ):

Case I. For every $c\in C$ , $(\rho _{c,l} : l<m)$ is not constant.

In this case, for each such $c\in C$ , $l_2[c]<m-1$ and $b_{c,l_2[c]} \in u_{\rho _{c,0}}=\dots =u_{\rho _{c,l_2[c]}}$ . Now $(b_{c,l_2[c]},b_{c,l_2[c]+1}) \in g_{k(l_2[c])}^{i(l_2[c])}$ , and as $\rho _{c,l_2[c]} \neq \rho _{c,l_2[c]+1}$ , necessarily $k(l_2[c])<k_{**}$ . By the definition of $l_1[c]$ and the fact that $\rho _{c,l_1[c]}=\rho _{c,l_2[c]}$ , necessarily $\rho _{c,l_2[c]}<_* \rho _{c,l_2[c]+1}$ .

For each $l<m-1$ , if $lg(\rho _{c,l})<lg(\rho _{c,l+1})$ , then either $g_{k(l)}$ or $g_{k(l)}^{-1}$ is as in Definition 2.5(2)(b), so letting $n=lg(\rho _{c,l})$ , $(\rho _{c,l},\rho _{c,l+1})$ here correspond to $(\eta _1 \restriction n,\nu _n)$ there, and there are $(a^l,b^l,c^l,d^l,e^l)=(a_c^l,b_c^l,c_c^l,d_c^l,e_c^l)$ in our case that correspond to $(a_n,b_n,c_n,d_n,e_n)$ in Definition 2.6(2)(b). In the rest of the proof we shall denote those sequences by $(a^l,b^l,c^l,d^l,e^l)$ , as the identity of the relevant $c\in C$ should be clear. In addition, one of the following holds:

1. 1. $i(l)=1$ and $g_{k(l)}^{i(l)}(a^l)=b^l$ .

2. 2. $i(l)=-1$ and $g_{k(l)}^{i(l)}(b^l)=a^l$ .

Similarly, for $l<m-1$ , if $lg(\rho _{c,l})>lg(\rho _{c,l+1})$ then the above is true modulo the fact that now $(\rho _{c,l},\rho _{c,l+1})$ correspond to $(\nu _n,\eta _1 \restriction n)$ and one of the following holds:

1. 1. $i(l)=1$ and $g_{k(l)}^{i(l)}(b^l)=e^l$ .

2. 2. $i(l)=-1$ and $g_{k(l)}^{i(l)}(b^l)=a^l$ .

Therefore, if $l=l_2[c]$ then $lg(\rho _{c,l})<lg(\rho _{c,l+1})$ , so the first option above holds, and therefore $\rho _{c,l}$ is an initial segment of $\eta _{1,k(l)}$ .

If $l=m-1$ , then $lg(\rho _{c,m-1})>lg(\rho _{c,0})=lg(\rho _{c,m})$ and therefore $\rho _{c,0}$ is an initial segment of $\eta _{1,k(m-1)}$ . It follows that $\rho _{c,0}=\rho _{c,l_2[c]}$ is an initial segment of $\eta _{1,k(l_2[c])} \cap \eta _{1,k(m-1)}$ . Recalling that $lg(\rho _{c,0})=lg(\rho _{c,l_1[c]})>j(*)$ and that $(\eta _{1,l} \restriction j(*) : l<k_*)$ is without repetition, it follows that $k(m-1)=k(l_2[c])$ .

We shall now prove that if $l_2[c]<m-1$ then $l_2[c]=m-2$ . Let $(a^{l_2[c]},b^{l_2[c]},\dots )$ be as above for $l=l_2[c]$ , so $b_{c,l_2[c]+1}=b^{l_2[c]}$ , and as $k(l_2[c])=k(m-1)$ , we get $b_{c,l_2[c]+1}=b^{l_2[c]}=b^{m-1}$ . In order to show that $l_2[c]=m-2$ , it suffices to show that $b^{m-1}=b_{c,m-1}$ (as the sequence of the $b_{c,l}$ s is without repetition), which follows from the fact that $\rho _{c,0}<_*\rho _{c,m-1}$ .

As we assume that the word w is reduced, and as $k(m-2)=k(l_2[c])=k(m-1)$ , necessarily $i(m-2)=i(m-1)$ . We may assume wlog that $i(m-2)=i(m-1)=1$ (the proof for $i(m-2)=i(m-1)\,{=}\,{-}1$ is similar, as we can replace w by a conjugate of its inverse).

Let $w'=w'(g_0,\dots ,g_{k_*-1}):=g_{k(m-3)}^{i(m-3)} \ldots g_{k(0)}^{i(0)}$ , by the above considerations and as $b^{m-1}=b_{c,m-1}$ , it follows that $e^{m-1}=g_{k(m-1)}(b^{m-1})=g_{k(m-1)}^{i(m-1)}(b^{m-1})=g_{k(m-1)}^{i(m-1)}(b_{c,m-1})=b_{c,0}$ . We also know that $g_{k(m-2)}^{i(m-2)}(w'(b_{c,0}))=g_{k(m-2)}(w'(b_{c,0}))$ is “higher” than $w'(b_{c,0})$ . Therefore, $g_{k(m-2)}^{i(m-2)}(w'(b_{c,0}))=g_{k(m-2)}(w'(b_{c,0}))=b^{m-2}=b^{m-1}$ . It also follows that $w'(b_{c,0})=a^{m-2}=a^{m-1}$ . Therefore, $w'(e^{m-1})=a^{m-1}$ .

We shall now prove that if $l<m-2$ then $b_{c,l+1}=(g_{\nu _{k(l)}}^*)^{i(l)}(b_{c,l})$ . Assume that for some $l<m-2$ , $g_{k(l)}(b_{c,l}) \neq g_{\nu _{k(l)}}^*(b_{c,l})$ and we shall derive a contradiction. Let $(a^{m-2},b^{m-2},\dots )$ be as before for $g_{k(m-2)}$ , so $(b_{c,m-2},b_{c,0})=(a^{m-2},e^{m-2})$ .

Case I(a). $k(l)=k(m-2)=k(m-1)$ . As the $b_{c,i}$ s are without repetition, if $0<l<m-2$ , then $b_{c,l} \notin \{b_{c,m-2},b_{c,0}\}=\{a^{m-2},e^{m-2}\}=\{a^l,e^l\}$ , and of course, $b_{c,l} \notin \{b^l,c^l,d^l\}$ (as it is a “lower” element). Therefore, $g_{k(l)}(b_{c,l})=g_{\nu _{k(l)}}^*(b_{c,l})$ , a contradiction. If $l=0$ , then $g_{k(m-1)}^{i(m-1)}(b_{c,m-1})=b_{c,0}$ and $(b_{c,m-1},b_{c,0})=(b^{m-1},e^{m-1})$ . If $i(0)=-i(m-1)$ , then by conjugating $g_{k(0)}$ , we get a shorter word with infinitely many fixed points, contradicting our assumption on the minimality of m.

If $i(0)=i(m-1)=1$ , then we derive a contradiction as in the case of $0<l$ .

Case I(b): $k(l) \neq k(m-2)=k(m-1)$ . In this case, we know that $g_{k(l)}$ almost coincides with $g_{\nu _{k(l)}}^*$ , with the exception of at most $\{a^l,b^l,c^l,d^l,e^l\}$ . Let $\rho _c:=\rho _{c,0}=\dots =\rho _{c,m-2}$ , then necessarily $\rho _c \leq \nu _{k(m-1)}=\eta _{1,k(m-1)}$ (as $g_{k(m-1)}$ moves $b_{c,m-1}$ to a lower $u_{\rho }$ (namely $u_{\rho _c}$ ), $\rho _c$ plays the role of $\eta _1 \restriction n$ in Definition 2.6 for $g_{k(m-1)}$ ). By our assumption, $lg(\rho _c)>j(*)$ and $(\eta _{1,l} \restriction j(*) : l<k(*))$ is without repetition, therefore $\eta _{1,k(l)} \restriction lg(\rho _c) \neq \rho _c$ , so $\rho _c \nleq \eta _{1,k(l)}$ . Therefore, when we consider $f_{k(l)}$ and $\eta _{1,k(l)}$ in Definition 2.6(b)(2), then $\rho _c$ has the form $\nu _n$ for some n. By the choice of $j(*)$ , it’s then impossible to have $\rho _c \leq \eta _{1,k(m-1)}$ , a contradiction.

Therefore, $a^{m-2}=w'(g_0,\dots ,g_{k_*-1})(e^{m-2})=w'(g_0,\dots ,g_{k_*-1})(b_{c,0})=w'(g_{\nu _0}^*,\dots , g_{\nu _{k_*-1}}^*)(b_{c,0})=w'(g_{\nu _0}^*,\dots ,g_{\nu _{k_*-1}}^*)(e^{m-2})$ . In the notation of the Claim and Definition 6(b)(2),

$F_1(f_{k(m-2)})(a^{m-2})=e^{m-2}$ , therefore, by composing with $w'$ , we obtain a word composed of permutation of $u_{\rho _{c,m-2}}$ (in the sense of Claim 2.4(f)) that fixes $e^{m-2} \in u_{\rho _{c,m-2}}$ , therefore, $m-3=0$ (or else we get a contradiction by Claim 2.4(f)).

It follows that $w(g_0,\dots ,g_{k_*-1})=g_{k(m-2)}g_{k(m-2)}g_{k(0)}^{i(0)}$ and $g_{k(0)}^{i(0)}(e^{m-2})=a^{m-2}$ . Now, obviously $\rho _{c,m-2} \leq \eta _{1,k(m-2)}$ , so $\rho _{c,m-2} \nleq \eta _{1,k(0)}=\nu _{k(0)}$ . By the definition, $g_{\nu _{k(0)}}^* \restriction u_{\rho _{c,m-2}}=f_{\rho _{c,m-2},\nu _{k(0)} \restriction lg(\rho _{c,m-2})} \neq f_{\rho _{c,m-2},\rho _{c,m-2}}$ . Also $F_1(f_{k(m-2)}) \restriction u_{\rho _{c,m-2}}=g^*_{\nu _{k(m-2)}} \restriction u_{\rho _{c,m-2}}=f_{\rho _{c,m-2},\rho _{c,m-2}}$ . Therefore, we get the following: $a^{m-2}=g_{k(0)}^{i(0)}(e^{m-2})=(g_{\nu _{k(0)}}^*)^{i(0)}(e^{m-2})=(f_{\rho _{c,m-2},\nu _{k(0)} \restriction lg(\rho _{c,m-2})})^{i(0)}(e^{m-2})$ and $e^{m-2}=F_1(f_{k(m-2)})(a^{m-2})=f_{\rho _{c,m-2},\rho _{c,m-2}}(a^{m-2})$ . In conclusion, we get a contradiction to Claim 2.4(f), as we have a short non-trivial word that fixes $e^{m-2}$ .

Case II. $(\rho _{c,l} : l<m)$ is constant for every $c\in C$ (so $l_2[c]=m-1$ ). Let $\rho _c:=\rho _{c,0}=\dots =\rho _{c,m-1}$ . If $g_{k(l)}^{i(l)}(b_{c,l})=(g_{\nu _{k(l)}}^*)^{i(l)}(b_{c,l})$ for every $l<m$ , then we get a contradiction to Claim 2.4(f). Therefore, for every $c\in C$ , the set $v_c=\{l<m : g_{k(l)}^{i(l)}(b_{c,l}) \neq (g_{\nu _{k(l)}}^*)^{i(l)}(b_{c,l})\}$ is nonempty. Without loss of generality, $v_c$ doesn’t depend on c, and we shall denote it by v. For every $l\in v$ , if $i(l)=1$ then $(b_{c,l},b_{c,l+1}) \in \{(a^l,b^l),(b^l,e^l),(c^l,d^l)\}$ , if $i(l)=-1$ then $(b_{c,l},b_{c,l+1}) \in \{(b^l,a^l),(e^l,b^l),(d^l,c^l)\}$ .

We shall now prove that for some $k<k_{**}$ , $k(l)=k$ for every $l\in v$ . Suppose not, then for some $l_1<l_2 \in v$ , $k(l_1) \neq k(l_2)$ . By the choice of $j(*)$ , each of the following options in impossible: $\rho _{c,l_1} \leq \eta _{1,l_1} \wedge \rho _{c,l_2} \leq \eta _{1,l_2}$ , $\rho _{c,l_1} \leq \eta _{1,l_1} \wedge \rho _{c,l_2} \nleq \eta _{1,l_2}$ , $\rho _{c,l_1} \nleq \eta _{1,l_1} \wedge \rho _{c,l_2} \leq \eta _{1,l_2}$ or $\rho _{c,l_1} \nleq \eta _{1,l_1} \wedge \rho _{c,l_2} \nleq \eta _{1,l_2}$ . Therefore we get a contradiction. It follows that $\{k(l) : l\in v\}$ is singleton, and we shall denote its only member by $k<k_{**}$ .

Note that if $l_1 \in v$ , $l_2 \in v$ is the successor of $l_1$ in v, $l_1+1<l_2$ and $c\in C$ then $b_{c,l_1+1} \neq b_{c,l_2}$ (recall that $(b_{c,l} : l<m)$ is without repetition). We shall now arrive at a contradiction by examining the following three possible cases (in the rest of the proof, we refer to $l(*)$ from Definition 2.5(A)(e) as “the distance between a and b”, and similarly for any pair of members from some $u_{\eta }$ ):

Case II (a). $g_k$ is as in Definition 6(b)(2)(K)(a). In this case, for every $l\in v$ , the only possibilities for $(b_{c,l},b_{c,l+1})$ are either of the form $(c,d)$ or $(d,c)$ (and not both, as we don’t allow repetition). As the distance between c and d is at most $2$ , we get a word made of $f_{\rho ,\nu }$ s of length $\leq m+1$ that fixes c, contradicting Claim 2.4(f).

Case II (b). $g_k$ is as in Definition 6(b)(2)(K)(c). Pick $c\in C$ such that $lg(\rho _c)$ is also greater than $m+l_*$ where $l_*$ is as in Definition 2.6(b)(2)(K)(c) for $g_k$ . As the sequence $(b_{c,l} : l<m)$ is without repetition, necessarily $1\leq |v| \leq 3$ .

If $|v|=3$ , then necessarily the sequences $(a,b,e)$ or $(e,b,a)$ occur in $(b_{c,l} : l<m)$ , as well as $(c,d)$ or $(d,c)$ . As the distance between a and e is $1$ and the distance between c and d is $\leq 2$ , we get a contradiction as before.

Suppose that $|v|=2$ . If the sequence $(a,b,e)$ appears in $(b_{c,l} : l<m)$ , we get a contradiction as above. If $(a,e)$ (or $(e,a)$ ) and $(c,d)$ (or $(d,c)$ ) appear, we also get a contradiction as above. If $(a,b)/(b,a)$ and $(c,d)/(d,c)$ appear, as the distance between a and b is $l_*$ , we get a word made of $f_{\rho ,\nu }$ s of length $\leq m+l(*)$ fixing c, a contradiction to Claim 2.4(f). Finally, if $|v|=1$ we get a contradiction similarly.

Case II (c). $g_k$ is as in Definition 2.6(b)(2)(K)(b). As in the previous case, where the only non-trivial difference is when either $|v| \in \{1,2\}$ and the sequence $(a,b)/(b,a)$ appears in $(b_{c,l} : l<m)$ , but not as a subsequence of $(a,b,e)/(e,b,a)$ . If for some c this is not the case, then we finish as before, so suppose that it’s the case for every $c\in C$ . As the distance between c and d is $\leq 2$ , suppose wlog that $|v|=1$ , $k=k(m-1)$ (by conjugating) and the sequence $(b_{c,l} : l<m)$ ends with a and starts with b or vice versa. Therefore, every $c\in C$ is of the form $a^n$ or $b^n$ (where $n\in B$ and B is as in Definition 2.6(b)(2) for $g_k$ ) and either $g_{k(0)}^{i(0)} \ldots g_{k_{m-2}}^{i(m-2)}(a^n)=b^n$ or $g_{k(0)}^{i(0)} \ldots g_{k_{m-2}}^{i(m-2)}(b^n)=a^n$ , so the distance between $a^n$ and $b^n$ is $\leq m-1$ . As C is infinite, the distance between $a^n$ and $b^n$ is $\leq m-1$ for infinitely many $n \in B$ . This is a contradiction to the assumption from Definition 2.6(b)(2)(K)(b) that the distance between $a^n$ and $b^n$ is increasing.

This completes the proof of Claim 2.8.

Claim 2.9. There exists a Borel function $\mathbf {B}_4: U^U \rightarrow U^U$ such that for every $f\in \mathbf {B}_1$ , $\mathbf {B}_4(f) \in G_f$ .

Proof As in [Reference Horowitz and Shelah2], and we comment on the main point in the proof of Claim 2.7.

Claim 2.11. G is a maximal cofinitary group.

Proof G is cofinitary by Claim 2.8, so it’s enough to prove maximality. Assume towards contradiction that H is a counterexample and let $f_* \in H\setminus G$ , so $\mathbf {B}_4(f_*) \in G$ , and we shall denote $f^*=\mathbf {B}_4(f_*)$ .

Case I. $f_* \in H_3$ . In this case, by Definition 2.6, $\{a_n : n\in B\} \subseteq eq(f_*,f^*):=X$ (see thee relevant notation in Definition 2.6), hence it’s infinite. Therefore, $f_*^{-1}f^* \restriction X$ is the identity, but $f_*^{-1}f^* \in H$ and H is cofinitary, therefore $f_*^{-1}f^*=Id$ so $f_*=f^* \in G$ , a contradiction.

Case II. $f_* \notin H_3$ . By the definition of $H_3$ , $\mathbf {B}_{2,6}'(f_*)=0$ , so the sequences $\mathbf {B}_{2,1}(f_*)=(A_n=A_n(f_*) : n\in \mathbf {B}_{2,2}(f_*))$ , $\bar {\rho _*^n}=(\rho _{n,i} : i<l_*)=(\rho _{a,f_*(a),i} : i<l_*)$ and $\bar {i}=(i_{l} : l<l_*)=(i_{a,f(a),l} : l<l_*)\ (n\in \mathbf {B}_{2,2}(f_*), a\in A_n)$ are well-defined, and for every $l<l_*$ , $(\rho _{n,l} : n\in \mathbf {B}_{2,2}(f_*))$ is $\leq $ -increasing, so $\nu _l:=\underset {n\in \mathbf {B}_{2,2}(f_*)}{\cup } \rho _{n,l} \in 2^{\omega }$ is well-defined. Let $g=(g_{\nu _0}^*)^{i_0} \cdot \cdot \cdot (g_{\nu _{l_*-1}}^*)^{i_{l_*-1}} \in G_1$ (we may assume that it’s a reduced product). Let $w_1=\{l<l_* : (\exists f_l \in H_3)(\nu _l=\mathbf {B}(f_l))\}$ and $w_2=l_* \setminus w_1$ . For $l<l_*$ , define $g_l$ as follows:

1. 1. If $l\in w_1$ , let $g_l=\mathbf {B}_4(f_l)$ .

2. 2. If $l\in w_2$ , let $g_l=g_{\nu _l}^*$ .

Let $g'=g_0^{i(0)} \cdot \cdot \cdot g_{l_*-1}^{i(l_*-1)}$ . By the definition of G, $g_0,\dots ,g_{l_*-1} \in G$ , hence $g' \in G$ .

Again by Definition 2.6, if $l\in w_1$ then $g_l=F_1(f_l)\ mod\ I_1$ and $g_l^{-1}=F_1(f_l)^{-1}\ mod\ I_1$ . Now suppose that $g(a) \neq g'(a)$ , then there is a minimal $l<l_*$ such that $(g_{\nu _0}^*)^{i(0)} \ldots (g_{\nu _l}^*)^{i(l)}(a) \neq (g_0)^{i(0)} \ldots (g_l)^{i(l)}(a)$ . Let $v_l=dif(g_{\nu _l}^*,g_l)$ , then $a\in (g_0^{i{0}} \ldots g_{l-1}^{i(l-1)})^{-1}(v_l)$ . In order to show that $(g_0^{i{0}} \ldots g_{l-1}^{i(l-1)})^{-1}(v_l) \in I_1$ it suffices to observe that for $i\in w_1$ , functions of the form $g_i,g_i^{-1}$ map elements of $I_1$ to elements of $I_1$ , therefore it follow that $g=g'\ mod\ I_1$ . It suffices to show that $eq(f_*,g) \notin I_1$ , as it will then follow that $eq(f_*,g') \notin I_1$ , so $f_*^{-1}g'=Id$ on an $I_1-$ positive set, hence on an infinite set. As $f_*^{-1}g' \in H$ and H is cofinitary, $f_*^{-1}g'=Id$ , an therefore $f_*=g' \in G$ , a contradiction.

So let $n\in \mathbf {B}_{2,2}(f_*)$ and $a\in A_n=A_n(f_*)$ , and observe that $f_*(a)=g(a)$ . Indeed, by the definition of $\mathbf {B}_{2,1}(f_*)$ , for every such a, $f_*(a)=((f_{\eta _1 \restriction n \rho _{n,0}}^{i_0}) \cdot \cdot \cdot (f_{\eta _ \restriction n \rho _{n,l_*-1}}^{i_{l_*-1}}))(a)$ (where $\eta _1$ is as in the definition of $\mathbf {B}_{2,1}(f_*)$ ). It’s now easy to verify that the last expression equals $g(a)$ . It’s also easy to verify that $\underset { n\in \mathbf {B}_{2,2}(f_*)}{\cup }A_n \notin I_1$ , therefore we’re done.

Claim 2.12. G is Borel.

Proof It suffices to prove the following subclaim:

Subclaim: There exists a Borel function $\mathbf {B}_5$ with domain $Sym(U)$ such that if $g\in G$ then $\mathbf {B}_5(g)=(g_0,g_1,\dots ,g_m)$ such that $G\models "g=g_0^{i_0}g_1^{i_1} \ldots g_m^{i_m}"$ for some $(i_0,\dots ,i_m) \in \{-1,1\}^{m+1}$ .

Proof: By the definition of G, if $g\in G$ then there are m, $f_0,\dots ,f_m \in \mathbf {A}_1$ (possibly with repetition) and $i_0,\dots ,i_m \in \{-1,1\}$ such that $g=g_0^{i_0} \ldots g_m^{i_m}$ where each $g_i$ is either of the form $\mathbf {B}_4(f_i)$ for $f_i \in H_3$ (in this case, let $\nu _i:=\mathbf {B}(f_i)$ ) or $g_{\nu _i}^*$ for $\nu _i \in 2^{\omega } \setminus \{\mathbf {B}(f) : f\in H_3\}$ .

Now if n is greater than $m!$ , then for some $u\subseteq 2^n$ such that $|u|\leq m!<\frac {2^n}{2}$ , for every $\rho \in 2^n \setminus u$ we have:

1. a. For every $l\leq m$ , $g_l \restriction u_{\rho }=f_{\rho ,\nu _l \restriction lg(\rho )}$ .

2. b. $g\restriction u_{\rho }$ can be represented as $f_{\rho ,\nu _0 \restriction lg(\rho )}^{i_0} \ldots f_{\rho ,\nu _m \restriction lg(\rho )}^{i_m} \in Sym(u_{\rho })$ .

3. d. By Claim 2.4(f), the above representation of $g\restriction u_{\rho }$ is unique.

Therefore, from g we can Borel-compute $((\nu _i \restriction n : n<\omega ) : i<m)$ hence $(\nu _i : i<m)$ .

As $H_3$ is Borel and $\mathbf {B}$ is injective, the sets $\{\mathbf {B}(f) : f\in H_3\}$ and $2^{\omega } \setminus \{\mathbf {B}(f) : f\in H_3\}$ are Borel. Now if $\nu _i \in 2^{\omega } \setminus \{\mathbf {B}(f) : f\in H_3\}$ , we can Borel compute $g_i=g_{\nu _i}^*$ . If $\nu _i \in \{\mathbf {B}(f) : f\in H_3\}$ , then $\nu _i=\mathbf {B}(f_i)$ and we can Borel-compute $f_i$ (by applying $\mathbf {B}_{-1}$ from Definition 2.3(e)) hence $\mathbf {B}_4(f_i)$ .