Proof Fix a strictly increasing function $h:\omega \rightarrow \omega \setminus \{0\}$ . We begin by describing representatives ${\mathcal B}$ of the strong types and a group G that acts faithfully and transitively on ${\mathcal B}$ . As notation, for each n, let $[h(n)]$ denote the $h(n)$ -element set $\{1,\dots ,h(n)\}$ and let $\textit{Sym}([h(n])$ be the (finite) group of permutations of $[h(n)]$ . Let

$$ \begin{align*} {\mathcal B}=\{f:\omega\rightarrow\omega:f(n)\in[h(n)] \ \text{for all } n\in\omega\}, \end{align*} $$

and let $G=\Pi _{n\in \omega } \textit{Sym}([h(n)])$ be the direct product. As notation, for each $n\in \omega $ , let $\pi _n:G\rightarrow \textit{Sym}([h(n)])$ be the natural projection map. Note that G acts coordinate-wise on ${\mathcal B}$ by: For $g\in G$ and $f\in {\mathcal B}$ , $g\cdot f$ is the element of ${\mathcal B}$ satisfying $g\cdot f(n)=\pi _n(g)(f(n))$ .

Define an equivalence relation $\sim $ on ${\mathcal B}$ by:

$$ \begin{align*} f\sim f'\quad \text{if and only if} \quad \{n\in\omega:f(n)\neq f'(n)\}\ \text{is finite.} \end{align*} $$

For $f\in {\mathcal B}$ , let $[f]$ denote the $\sim $ -class of f and, abusing notation somewhat, for $W\subseteq {\mathcal B}$

$$ \begin{align*} [W]:=\bigcup\{[f]:f\in W\}. \end{align*} $$

Observe that for every $g\in G$ , the permutation of ${\mathcal B}$ induced by the action of g maps $\sim $ -classes onto $\sim $ -classes, i.e., G also acts transitively on ${\mathcal B}/{\sim}$ .

We first identify a countable family of $\sim $ -classes that are ‘sufficiently indiscernible’. Our first lemma is where we use the fact that the function h defining $T_h$ is strictly increasing.

Fix an enumeration $\langle f_i:i\in \omega \rangle $ of Y for the whole of the argument. The ‘indiscernibility’ of Y alluded to above is formalized by the following definition and lemma.

Proof Note that since h is increasing, $h(n)\ge n$ for every $n\in \omega $ . Fix a permutation $\sigma \in \textit{Sym}(\omega )$ and we will define some $g\in G$ respecting $\sigma $ coordinate-wise. Using Lemma 2.2, choose a sequence

$$ \begin{align*} 0=N_0\ll N_1\ll N_2\ll \cdots \end{align*} $$

of integers such that for all $i\in \omega $ , both $f_i(n)\neq f_j(n)$ and $f_{\sigma (i)}(n)\neq f_{\sigma (j)}(n)$ hold for all $n\ge N_i$ and all $j<i$ .

Since $\{N_i\}$ are increasing, it follows that for each $i\in \omega $ and all $n\ge N_i$ , the subsets $\{f_j(n):j\le i\}$ and $\{f_{\sigma (j)}(n):j\le i\}$ of $[h(n)]$ each have precisely $(i+1)$ elements. Thus, for each $i<\omega $ and for each $n\ge N_i$ , there is a permutation $\delta _n\in \textit{Sym}([h(n)])$ satisfying

$$ \begin{align*} \bigwedge_{j\le i} \delta_n(f_j(n))=f_{\sigma(j)}(n). \end{align*} $$

(Simply begin defining $\delta _n$ to meet these constraints, and then complete $\delta _n$ to a permutation of $[h(n)]$ arbitrarily.) Using this, define $g:=\langle \delta _n:n\in \omega \rangle $ , where each $\delta _n\in \textit{Sym}([h(n)])$ is constructed as above. To see that g respects $\sigma $ , note that for every $i\in \omega $ , $(g\cdot f_i)(n)=f_{\sigma (i)}(n)$ for all $n\ge N_{i}$ , so $(g\cdot f_i)\sim f_{\sigma (i)}$ .

Definition 2.5. For distinct integers $i\neq j$ , let $d_{i,j}\in {\mathcal B}$ be defined by:

$$ \begin{align*} d_{i,j}(n):=\begin{cases} f_i(n) & \text{if } n \text{ even;} \\ f_j(n) & \text{if } n \text{ odd.}\end{cases} \end{align*} $$

Let $Z:=\{d_{i,j}:i\neq j\}$ .

Note that $d_{i,j}\not \sim f_k$ for all distinct $i,j$ and all $k\in \omega $ , hence $\{[f_i]:i\in \omega \}$ and $\{[d_{i,j}]:i\neq j\}$ are disjoint.

Proof Choose $\sigma \in \textit{Sym}(\omega )$ , g respecting $\sigma $ , and $i\neq j$ . Choose N such that $(g\cdot [f_i])(n)=[f_{\sigma (i)}](n)$ and $(g\cdot [f_j])(n)=[f_{\sigma (j)}](n)$ for every $n\ge N$ . Since $d_{i,j}(n)=f_i(n)$ for $n\ge N$ even,

$$ \begin{align*} (g\cdot d_{i,j})(n)=\pi_n(g)(d_{i,j}(n))=\pi_n(g)(f_i(n))=(g\cdot f_i)(n)=f_{\sigma(i)}(n). \end{align*} $$

Dually, $(g\cdot d_{i,j})(n)=f_{\sigma (j)}(n)$ when $n\ge N$ is odd, so $(g\cdot d_{i,j})\sim d_{\sigma (i),\sigma (j)}$ .

With the combinatorial preliminaries out of the way, we now prove that $T_h$ is Borel complete. We form a highly homogeneous model $M^*\models T_h$ and thereafter, all models we consider will be countable, elementary substructures of $M^*$ . Let $A=\{a_f:f\in {\mathcal B}\}$ and $B=\{b_f:f\in {\mathcal B}\}$ be disjoint sets and let $M^*$ be the L-structure with universe $A\cup B$ and each $E_n$ interpreted by the rules:

• • For all $f\in {\mathcal B}$ and $n\in \omega $ , $E_n(a_f,b_f)$ ; and

• • For all $f,f'\in {\mathcal B}$ and $n\in \omega $ , $E_n(a_f,a_{f'})$ iff $f(n)=f'(n)$ ,

with the other instances of $E_n$ following by symmetry and transitivity. For any finite $F\subseteq \omega $ , $\{f\mathord \restriction _{F}:f\in {\mathcal B}\}$ has exactly $\Pi _{n\in F} h(n)$ elements, hence $E_F(x,y):=\bigwedge _{n\in F} E_n(x,y)$ has $\Pi _{n\in F} h(n)$ classes in $M^*$ . Thus, the $\{E_n:n\in \omega \}$ cross cut and $M^*\models T_h$ .

Let $E_{\infty }(x,y)$ denote the (type definable) equivalence relation $\bigwedge _{n\in \omega } E_n(x,y)$ . Then, in $M^*$ , $E_{\infty }$ partitions $M^*$ into two-element classes $\{a_f,b_f\}$ , indexed by $f\in {\mathcal B}$ . Note also that every $g\in G$ induces an L-automorphism $g^*\in Aut(M^*)$ by

$$ \begin{align*} g^*(x):=\begin{cases} a_{(g\cdot f)} & \text{if } x=a_f \text{ for some } f\in{\mathcal B};\\ b_{(g\cdot f)} & \text{if } x=b_f \text{ for some } f\in{\mathcal B}. \end{cases} \end{align*} $$

Recall the set $Y=\{f_i:i\in {\mathcal B}\}$ from Lemma 2.2, so $[Y]=\{[f_i]:i\in \omega \}$ . Let $M_0\subseteq M^*$ be the substructure with universe $\{a_f:f\in [Y]\}$ . As $T_h$ admits elimination of quantifiers and as $[Y]$ is dense in ${\mathcal B}$ , $M_0\preceq M^*$ . Moreover, every substructure M of $M^*$ with universe containing $M_0$ will also be an elementary substructure of $M^*$ , hence a model of $T_h$ .

To show that $Mod(T_h)$ is Borel complete, we define a Borel mapping from $\{$ irreflexive graphs ${\mathcal G}=(\omega ,R)\}$ to $Mod(T_h)$ as follows: Given ${\mathcal G}$ , let $Z(R):=\{d_{i,j}\in Z:{\mathcal G}\models R(i,j)\}$ , so $[Z(R)]=\bigcup \{[d_{i,j}]:d_{i,j}\in Z(R)\}$ . Let $M_G\preceq M^*$ be the substructure with universe

$$ \begin{align*} M_0\cup\{a_d,b_d:d\in [Z(R)]\}. \end{align*} $$

That the map ${\mathcal G}\mapsto M_G$ is Borel is routine, given that Y and Z are fixed throughout.

Note that in $M_G$ , every $E_{\infty }$ -class has either one or two elements. Specifically, for each $d\in [Z(R)]$ , the $E_{\infty }$ -class $[a_d]_{\infty }=\{a_d,b_d\}$ , while the $E_{\infty }$ -class $[a_f]_{\infty }=\{a_f\}$ for every $f\in [Y]$ .

We must show that for any two graphs ${\mathcal G}=(\omega ,R)$ and ${\mathcal H}=(\omega ,S)$ , ${\mathcal G}$ and ${\mathcal H}$ are isomorphic if and only if the L-structures $M_G$ and $M_H$ are isomorphic.

To verify this, first choose a graph isomorphism $\sigma :(\omega ,R)\rightarrow (\omega ,S)$ . Then $\sigma \in \textit{Sym}(\omega )$ and, for distinct integers $i\neq j$ , $d_{i,j}\in Z(R)$ if and only if $d_{\sigma (i),\sigma (j)}\in Z(S)$ . Apply Lemma 2.4 to get $g\in G$ respecting $\sigma $ and let $g^*\in Aut(M^*)$ be the L-automorphism induced by g. By Lemma 2.6 and Definition 2.3, it is easily checked that the restriction of $g^*$ to $M_G$ is an L-isomorphism between $M_G$ and $M_H$ .

Conversely, assume that $\Psi :M_G\rightarrow M_H$ is an L-isomorphism. Clearly, $\Psi $ maps $E_{\infty }$ -classes in $M_G$ to $E_{\infty }$ -classes in $M_H$ . In particular, $\Psi $ permutes the one-element $E_{\infty }$ -classes $\{\{a_f\}:f\in [Y]\}$ of both $M_G$ and $M_H$ , and maps the two-element $E_{\infty }$ -classes $\{\{a_d,b_d\}:d\in [Z(R)]\}$ of $M_G$ onto the two-element $E_{\infty }$ -classes $\{\{a_d,b_d\}:d\in [Z(S)]\}$ of $M_H$ . That is, $\Psi $ induces a bijection $F:[Y\sqcup Z(R)]\rightarrow [Y\sqcup Z(S)]$ that permutes $[Y]$ .

As well, by the interpretations of the $E_n$ ’s, for $f,f'\in [Y\sqcup Z(R)]$ and $n\in \omega $ ,

$$ \begin{align*} f(n)=f'(n)\quad\text{if and only if}\quad F(f)(n)=F(f')(n). \end{align*} $$

From this it follows that F maps $\sim $ -classes onto $\sim $ -classes. As F permutes $[Y]$ and as $[Y]=\bigcup \{[f_i]:i\in \omega \}$ , F induces a permutation $\sigma \in \textit{Sym}(\omega )$ given by $\sigma (i)$ is the unique $i^*\in \omega $ such that $F([f_i])=[f_{i^*}]$ .

We claim that this $\sigma $ induces a graph isomorphism between ${\mathcal G}=(\omega ,R)$ and ${\mathcal H}=(\omega ,S)$ . Indeed, choose any $(i,j)\in R$ . Thus, $d_{i,j}\in Z(R)$ . As F is $\sim $ -preserving, choose N large enough so that $F(f_i)(n)\hspace{-2pt}=\hspace{-2pt}F(f_{\sigma (i)})(n)$ and $F(f_j)(n)\hspace{-2pt}=\hspace{-2pt}F(f_{\sigma (j)})(n)$ for every $n\ge N$ . By definition of $d_{i,j}$ , $d_{i,j}(n)\hspace{-2pt}=\hspace{-2pt}f_i(n)$ for $n\ge N$ even, so $F(d_{i,j})(n)=F(f_i)(n)=f_{\sigma (i)}(n)$ for such n. Dually, for $n\ge N$ odd, $F(d_{i,j})(n)=F(f_j)(n)=f_{\sigma (j)}(n)$ . Hence, $F(d_{i,j})\sim d_{\sigma (i),\sigma (j)}\in [Z(S)]$ . Thus, $(\sigma (i),\sigma (j))\in S$ . The converse direction is symmetric (i.e., use $\Psi ^{-1}$ in place of $\Psi $ and run the same argument).

Proof Given any function $f:\omega \rightarrow \omega \setminus \{0,1\}$ , choose a partition $\omega =\bigsqcup \{F_n:n\in \omega \}$ into non-empty finite sets for which $\Pi _{k\in F_n} f(k)< \Pi _{k\in F_m} f(k)$ whenever $n<m<\omega $ . For each n, let $h(n):=\Pi _{k\in F_n} f(k)$ and let $E^*_n(x,y):=\bigwedge _{k\in F_n} E_k(x,y)$ . Then, as h is strictly increasing and $\{E^*_n\}$ is a cross-cutting set of equivalence relations with each $E_n^*$ having $h(n)$ classes.

Now let $M\models T_f$ be arbitrary and let $L'=\{E^*_n:n\in \omega \}$ . As each $E_n^*$ described above is 0-definable in M, there is an $L'$ -reduct $M'$ of M. It follows from Theorem 2.1 that $T'=Th(M')$ is Borel complete, so $T_f$ has a Borel complete reduct.

Proof Let $M\models T$ be arbitrary. As usual, by the Cantor–Bendixon analysis of the compact, Hausdorff–Stone space $S_1(T)$ of complete one-types, choose a set $\{\varphi _{\eta }(x):\eta \in 2^{<\omega }\}$ of 0-definable formulas, indexed by the tree $(2^{<\omega },\trianglelefteq )$ ordered by initial segment, satisfying:

1. 1. $M\models \exists x\varphi _{\eta }(x)$ for each $\eta \in 2^{<\omega }$ ;

2. 2. For $\nu \trianglelefteq \eta $ , $M\models \forall x(\varphi _{\eta }(x)\rightarrow \varphi _{\nu }(x))$ ;

3. 3. For each $n\in \omega $ , $\{\varphi _{\eta }(x):\eta \in 2^n\}$ are pairwise contradictory.

By increasing these formulas slightly, we can additionally require

1. 4. For each $n\in \omega $ , $M\models \forall x( \bigvee _{\eta \in 2^n} \varphi _{\eta }(x))$ .

Given such a tree of formulas, for each $n\in \omega $ , define

Because of (4) above, $M\models \forall x(\delta ^0_n(x)\vee \delta ^1_n(x))$ for each n. Also, for each n, let

$$ \begin{align*} E_n(x,y):=[\delta_n^0(x)\leftrightarrow \delta_n^0(y)]. \end{align*} $$

From the above, each $E_n$ is a 0-definable equivalence relation with precisely two classes.

Claim: The equivalence relations $\{E_n:n\in \omega \}$ are cross-cutting.

Thus, taking the 0-definable relations $\{E_n\}$ , M has a reduct that is a model of $T_f$ (where f is the constant function 2). As reducts of reducts are reducts, it follows from Lemma 3.1 and Theorem 2.1 that M has a Borel complete reduct.

Proof Let M be any model of T and choose k least such that T has uncountably many complete k-types consistent with it. In the language $L^{eq}\kern-1.5pt$ , there is a sort $U_k$ and a definable bijection $f:M^k\rightarrow U_k$ . Hence $Th(M^{eq})$ has uncountably many one-types consistent with it, each extending $U_k$ . Thus, $M^{eq}$ has a Borel complete reduct by Theorem 3.2.

Proof Choose a countable M so that $S_1(M)$ is uncountable. Then, in the language $L(M)$ , the theory of the expanded structure $M_M$ in the language $L(M)$ has uncountably many one-types, hence it has a Borel complete reduct by Theorem 3.2.

Proof We show that every model M has an $(\infty ,\omega )$ -elementary substructure of size $2^{\aleph _0}$ , which suffices. So, fix M and choose an arbitrary countable $M_0\preceq M$ . By Proposition 4.4 of [Reference Laskowski4], $M\setminus M_0$ can be decomposed into countable components, and any permutation of isomorphic components induces an automorphism of M fixing $M_0$ pointwise. As there are at most $2^{\aleph _0}$ non-isomorphic components over $M_0$ , choose a substructure $N\subseteq M$ containing $M_0$ and, for each isomorphism type of a component, N contains either all of copies in M (if there are only finitely many) or else precisely $\aleph _0$ copies if M contains infinitely many copies. It is easily checked that $N\preceq _{\infty ,\omega } M$ .

Proof Fix $\lambda \ge \beth _2$ . It is readily checked that there is a family of $2^{\lambda }$ graphs that are pairwise not back and forth equivalent. As there are fewer than $2^{\lambda } \ \equiv _{\infty ,\omega }$ -classes of models of T, there cannot be a $\lambda $ -Borel reduction of graphs into $\mathrm {Mod}_{\lambda }(T)$ .

Proof Let $\kappa $ denote the number of $\equiv _{\infty ,\omega }$ -classes of models of T. If T were grounded, then $\kappa $ would also bound the number of potential canonical Scott sentences. As the class of graphs has a proper class of potential canonical Scott sentences, it would follow from Theorem 3.10 of [Reference Ulrich, Rast and Laskowski7] that T could not be Borel complete.