---
abstract: 'We use a method from descriptive set theory to investigate the two complete clones above the unary clone on a countable set.'
address: |
    Discrete Mathematics and Geometry\
    Algebra Research GroupTU Wien\
    Wiedner Hauptstra[ß]{}e 8–10/104 1040 Wien, Austria (Europe)
author:
- Martin Goldstern
bibliography:
- 'listb.bib'
- 'listx.bib'
- 'goldstrn.bib'
- 'other.bib'
date: '2004-04-11'
title: Analytic Clones
---

Introduction. Known results
===========================

An “operation” on a set $X$ is a function $f:X^n\to X$, for some $n\in {{\mathbb N}}\setminus\{0\}$. If $f$ is such an “$n$-ary operation”, $g_1$, …, $g_n$ are $k$-ary, then the “composition” $f(g_1,\ldots, g_n)$ is defined naturally: $$f(g_1,\ldots, g_n)(\vec x) = 
f(g_1(\vec x), \ldots, g_n(\vec x)  ) \ \ \mbox{ for all $\vec x \in X^k$}$$ A clone on a set $X$ is a set ${\mathscr{C}}$ of operations which contains all the projections and is closed under composition. (Alternatively, ${\mathscr{C}}$ is a clone on $X$ [if]{} ${\mathscr{C}}$ is the set of term functions of some universal algebra over $X$.)

The family of all clones forms a complete algebraic lattice $Cl(X)$ with greatest element ${{\mathscr O}}= \bigcup_{n=1}^\infty {{{\mathscr O}}^{(n)}} $, where ${{{\mathscr O}}^{(n)}} = X^{X^n} $ is the set of all $n$-ary operations on $X$. (In this paper, the underlying set $X$ will always be the set ${{\mathbb N}}= \{0,1,2,\ldots \} $ of natural numbers.)

The coatoms of this lattice $Cl(X) $ are called “precomplete clones” or “maximal clones” on $X$.

For any set ${\mathscr{C}}\subseteq {{\mathscr O}}$ we write $\langle {\mathscr{C}}\rangle$ for the smallest clone containing ${\mathscr{C}}$. In particular, $\langle {{{\mathscr O}}^{(1)}} \rangle$ is the set of all functions $\pi\circ f$, where $f:X\to X$ is arbitrary and $\pi:X^n\to X$ is a projection to one coordinate. However, to lighten the notation we will identify ${{{\mathscr O}}^{(1)}} $ (the set of all unary functions) with $\langle {{{\mathscr O}}^{(1)}} \rangle$ (the set of all “essentially” unary functions).

For singleton sets $X$ the lattice $Cl(X)$ is trivial; for $|X|=2$ the lattice $Cl(X)$ is countable, and well understood (“Post’s lattice”). For $|X|\ge 3$, $Cl(X)$ is uncountable. For infinite $X$, $Cl(X)$ has $2^{2^{|X|}}$ elements, and there are even $2^{2^{|X|}}$ precomplete clones on $X$.

In this paper we are interested in the interval $[{{{\mathscr O}}^{(1)}}, {{\mathscr O}}]$ of the clone lattice on a countable set $X$. It will turn out that methods from descriptive set theory are useful to describe the complexity of several interesting clones in this interval, and also the overall structure of the interval.

For simplicity we concentrate on binary clones, i.e., clones generated by binary functions. Equivalently, we can define a binary clone to be a set ${\mathscr{C}}$ of functions $f:{{\mathbb N}}^2\to {{\mathbb N}}$ which contains the two projections and is closed under composition: if $f,g,h\in {\mathscr{C}}$, then also the function $f(g,h)$ (mapping $(x,y)$ to $ f(g(x,y),h(x,y))$) is in ${\mathscr{C}}$.

The set of binary clones, $Cl^{(2)}(X)$, also forms a complete algebraic lattice.

Occasionally we will remark on how to modify the definitions or theorems for the case of “full” clones, i.e., for clones that are not necessarily generated by binary functions. (In some cases this generalization is trivial, in other cases it is nontrivial but known, and in some cases it is still open.)

By [@Gavrilov:1965] (see also [@GoSh:737]), we know that there are exactly 2 precomplete binary clones above ${{{\mathscr O}}^{(1)}} $, which we call ${{\sf T}}_1$ and ${{\sf T}}_2$ (see below). It is known that the interval $[{{{\mathscr O}}^{(1)}}, {{{\mathscr O}}^{(2)}} ] $ of binary clones is dually atomic, so it can be written $$[{{{\mathscr O}}^{(1)}}, {{{\mathscr O}}^{(2)}} ]  = [{{{\mathscr O}}^{(1)}} , {{\sf T}}_1] \cup [{{{\mathscr O}}^{(1)}} , {{\sf T}}_2]\cup \{{{{\mathscr O}}^{(2)}} \},$$ i.e., every binary clone above ${{{\mathscr O}}^{(1)}} $ other than ${{{\mathscr O}}^{(2)}} $ itself is contained in ${{\sf T}}_1$ or in ${{\sf T}}_2$.

So we will have to investigate the intervals $ [{{{\mathscr O}}^{(1)}}, {{\sf T}}_1]$ and $[{{{\mathscr O}}^{(1)}}, {{\sf T}}_2]$. We will see that these two structures are very different, and that this difference can be traced back to a difference in “complexity” of the two binary clones ${{\sf T}}_1$ and ${{\sf T}}_2$.

More precisely, ${{\sf T}}_1$ is a Borel set, while ${{\sf T}}_2$ is a complete coanalytic set. We will see that ${{\sf T}}_1$ is finitely generated over ${{{\mathscr O}}^{(1)}}$, but ${{\sf T}}_2$ is not countably generated over ${{{\mathscr O}}^{(1)}} $.

A function $f:{{\mathbb N}}\times {{\mathbb N}}$ is called “almost unary”, if at least one of the following holds:

1.  There is a function $F:{{\mathbb N}}\to {{\mathbb N}}$ such that $\forall
                 x\,\forall y: f(x,y)\le F(x)$.

2.  There is a function $F:{{\mathbb N}}\to {{\mathbb N}}$ such that $\forall
                 x\,\forall y: f(x,y)\le F(y)$.

We let ${{\sf T}}_1$ be the set of all binary functions which are almost unary. It is easy to see that ${{\sf T}}_1$ is a binary clone containing ${{{\mathscr O}}^{(1)}} $.

Let $B \subseteq {{{\mathscr O}}^{(2)}}$. The set ${{\rm Pol}}(B)$ is defined as $$\bigcup_{k=1 }^\infty \{f\in {{{\mathscr O}}^{(k)}} : \forall  g_1,\ldots, g_k\in B:
              f(g_1,\ldots, g_k)\in B\}$$

(Background and a more general definition of ${{\rm Pol}}$ can be found in [@PK:1979].)

${{\rm Pol}}(B)$ is a clone. If $B$ is a binary clone, then ${{\rm Pol}}(B) 
\cap {{{\mathscr O}}^{(2)}} = B$.

Let $\Delta:= \{(x,y)\in {{\mathbb N}}\times {{\mathbb N}}: x > y\}$, $\nabla:= \{(x,y): x < y\}$.

For $S_1,S_2\subseteq {{\mathbb N}}$ we let $\Delta_{S_1,S_2}: =\Delta\cap
(S_1\times S_2)$. We define $\nabla_{S_1,S_2}$ similarly.

If $S_1,S_2$ are infinite subsets of ${{\mathbb N}}$, and $g:
\Delta_{S_1,S_2}\to {{\mathbb N}}$ or $g:\nabla_{S_1,S_2} \to {{\mathbb N}}$, then we say that $g$ is “canonical” iff one of the following holds:

1.  $g$ is constant

2.  There is a 1-1 function $G:S_1\to {{\mathbb N}}$ such that $$\forall (x,y)\in {{\rm dom}}(g): g(x,y)  = G(x)$$

3.  There is a 1-1 function $G:S_2\to {{\mathbb N}}$ such that $$\forall (x,y)\in {{\rm dom}}(g): g(x,y)  = G(y)$$

4.  $g$ is 1-1.

The “type” of $g$ is one of the labels “constant”, “x”, “y”, or “1-1”, respectively.

Let $f:{{\mathbb N}}\times {{\mathbb N}}\to {{\mathbb N}}$. We say that $f$ is canonical on $S_1\times S_2$ iff both functions $f{{\upharpoonright}}\Delta_{S_1,S_2}$ and $f{{\upharpoonright}}\nabla_{S_1,S_2}$ are canonical (but not necessarily of the same type), and moreover:

> Either the ranges of $f{{\upharpoonright}}\Delta_{S_1,S_2}$ and $f{{\upharpoonright}}\nabla_{S_1,S_2}$ are disjoint,\
> or $S_1=S_2$, and $f(x,y)=f(y,x)$ for all $x,y\in S_1$.

The following fact is a consequence of Ramsey’s theorem, see [@GoSh:737]. It was originally proved in a slightly different formulation already in [@Gavrilov:1965].

\[ramsey\] Let $f:{{\mathbb N}}\times {{\mathbb N}}\to {{\mathbb N}}$. Then there are infinite sets $S_1$, $S_2$ such that $f$ is canonical on $S_1\times S_2$.

Moreover, for any infinite sets $S_1, S_2$ we can find infinite $S'_1\subseteq S_1 $, $S'_2\subseteq S_2$ such that $f$ is canonical on $S'_1\times S'_2$.

Let $f:{{\mathbb N}}\times {{\mathbb N}}\to {{\mathbb N}}$. We say that $f$ is “nowhere injective”, if:

> whenever $f$ is canonical on $S_1\times S_2$, then neither $f{{\upharpoonright}}\Delta_{S_1,S_2}$ nor $f{{\upharpoonright}}\nabla_{S_1,S_2}$ is 1-1.

We let ${{\sf T}}_2$ be the set of all nowhere injective functions. Using fact \[ramsey\], it is easy to check that ${{\sf T}}_2$ is a binary clone; clearly ${{\sf T}}_2$ contains ${{{\mathscr O}}^{(1)}}$. (More precisely, ${{\sf T}}_2$ contains $\langle {{{\mathscr O}}^{(1)}} \rangle\cap {{{\mathscr O}}^{(2)}}$.)

${{\sf T}}_1$ and ${{\sf T}}_2$ are precomplete binary clones, and every binary clone containing ${{{\mathscr O}}^{(1)}}$ is either contained in one of ${{\sf T}}_1$, ${{\sf T}}_2$, or equal to the clone of all binary functions.

\[For the non-binary case: ${{\rm Pol}}({{\sf T}}_1)$ and ${{\rm Pol}}({{\sf T}}_2)$ are precomplete clones, and every clone $\supseteq {{{\mathscr O}}^{(1)}}$ is either $={{\mathscr O}}$, or $\subseteq {{\rm Pol}}({{\sf T}}_1)$, or $\subseteq {{\rm Pol}}({{\sf T}}_2)$.\]

We will prove the following:

-   (Section \[t1\]) ${{\sf T}}_1$ is finitely generated over ${{{\mathscr O}}^{(1)}} $, so the interval $[{{{\mathscr O}}^{(1)}}, {{\sf T}}_1]$ in the lattice of binary clones is dually atomic.\
    In fact, the interval contains a unique coatom: ${{\sf T}}_1\cap {{\sf T}}_2$.

-   (Section \[t2\]) ${{\sf T}}_2$ is neither finitely nor countably generated over ${{{\mathscr O}}^{(1)}} $.\
    ${{\sf T}}_1\cap {{\sf T}}_2$ is a coatom in the interval $[{{{\mathscr O}}^{(1)}}, {{\sf T}}_2]$. (Easy)\
    Any clone which is a Borel set (or even an analytic set) cannot be a coatom in this interval.

I am grateful to J. Jezek, K. Kearnes, R. Pöschel, A. Romanowska, A. Szendrei and R. Willard for inviting me to Bela Csakany’s birthday conference (Szeged, 2002), at which I first presented the main ideas from this paper.

Descriptive Set Theory {#dst}
======================

We collect a few facts and notions from descriptive set theory. (For motivation, history, details and proofs see the textbooks by Moschovakis [@Moschovakis:1980] or Kechris [@Kechris:1995].)

Let $X$ be a countable set (usually $X={{\mathbb N}}$, or $X={{\mathbb N}}^k$), and $Y$ a finite or countable set, $|Y|\ge
2$ (usually $Y={{\mathbb N}}$, or $Y= 2:= \{0,1\}$). $Y^X$ is the space of all functions from $X$ to $Y$.

We equip $Y$ with the discrete topology, $Y^X$ and $Y^{X^n}$ with the product topology, and $\bigcup_{n=1}^\infty  Y^{X^n}$ with the sum topology. All these spaces are “Polish spaces”, i.e., they are separable and carry a (natural) complete metric.

The family of Borel sets is the smallest family $B$ that contains all open sets and is closed under complements and countable unions (equivalently: contains all open sets and all closed sets, and is closed under countable unions and countable intersections).

A function $f$ between two topological spaces is called a Borel function iff the preimage of any Borel set under $f$ is again a Borel set.

A [*finite sequence on $Y$*]{} is a tuple $(a_0,\ldots, a_{n-1})\in
Y^n$. If $s\in Y^k$ and $t\in Y^n$ are finite sequences, $k<n$, then we write $s\vartriangleleft t$ iff $s$ is an initial segment of $t$.

We write $Y^{<\omega} := \bigcup_{n\in {{\mathbb N}}} Y^n$ for the set of all finite sequences on $Y$. If $Y$ is countable, then also $Y^{<\omega}$ is countable.

We can identify ${{\mathscr P}}(Y^{<\omega})$, the power set of $Y^{<\omega}$, with the set $2^{Y^{<\omega}}$ of all characteristic functions, so also ${{\mathscr P}}(Y^{<\omega})$ carries a natural topology.

A “tree on $Y$” is a set $T  \subseteq \bigcup_{n\in {{\mathbb N}}}  Y^n$ of finite sequences which is downward closed, i.e.,

> whenever $t\in T$, $s\vartriangleleft t$, then also $s\in T$

The set of all trees is easily seen to be a closed subset of ${{\mathscr P}}(Y^{<\omega})$.

For any tree $T$ on $Y$ we call $f\in Y^{{\mathbb N}}$ a [*branch*]{} of $T$ iff $\forall n: f{{\upharpoonright}}n \in T$. (Here we write $f{{\upharpoonright}}n$ for $(f(0), \ldots, f(n-1))$.)

We write $[T]$ for the set of all branches of $T$.

It is easy to see that $[T]$ is always a closed set in $Y^{{\mathbb N}}$, and that every closed set $\subseteq Y^{{\mathbb N}}$ is of the form $[T]$ for some tree $T$.

We call a tree $Y$ [*well-founded*]{} if $[T] = \emptyset$, i.e., if there is no sequence $s_0 \vartriangleleft s_1 \vartriangleleft
\cdots$ of elements of $T$.

We write ${{{\bf WF}}}$ for the set of all well-founded trees.

The class of [*analytic sets*]{} is a proper extension of the class of Borel sets. There are several possible equivalent definitions of “analytic”, for example one could choose the equivalence (1)$\Leftrightarrow$(3) in fact \[def.ana\] as the definition of “analytic”.

\[def.ana\] Let ${{\mathscr X}}$ be a Polish (=complete metric separable) topological space, $A \subseteq {{\mathscr X}}$, $C:= {{\mathscr X}}\setminus A$. Then the following are equivalent:

1.  $A$ is analytic

2.  $C$ is coanalytic

3.  $A=\emptyset$, or there is a continuous function $f:{{\mathbb N}}^{{\mathbb N}}\to {{\mathscr X}}$ with $A=f[{{\mathbb N}}^{{\mathbb N}}]$

4.  There is a Borel set $B \subseteq {{\mathbb N}}^{{\mathbb N}}$ and a continuous function $f:{{\mathbb N}}^{{\mathbb N}}\to{{\mathscr X}}$ with $A=f[B]$

5.  There is a continuous function $f:{{\mathscr X}}\to {{\mathscr P}}({{\mathbb N}}^{<\omega})$ such that $C = f^{-1}[ {{{\bf WF}}}] $.

6.  (Assuming ${{\mathscr X}}= Y^{{\mathbb N}}$.) There is a set $R \subseteq Y^{<\omega}\times {{\mathbb N}}^{<\omega}$ such that $$A  = \{ f\in Y^{{\mathbb N}}:  \ \exists g\in {{\mathbb N}}^{{\mathbb N}}\,\forall n\,\,
        (f{{\upharpoonright}}n, g{{\upharpoonright}}n) \in R \}$$

The coanalytic sets are just the sets whose complement is analytic. Borel sets are of course both analytic and coanalytic, and the “Separation theorem” states that the converse is true:

Let $A\subseteq {{\mathscr X}}$ be both analytic and coanalytic. Then $A$ is a Borel set.

Analytic sets have the following closure properties:

\[closure\]

1.  All Borel sets are analytic (and coanalytic).

2.  The countable union or intersection of analytic sets is again analytic. Similarly, the countable union or intersection of coanalytic sets is again analytic.

3.  The continuous preimage of an analytic set is analytic. The continuous preimage of a coanalytic set is coanalytic.

4.  The continuous image of an analytic set is analytic. (Note that the continuous image of a Borel set is in general not Borel.)

5.  In particular, if $C \subseteq {{\mathbb N}}^{{\mathbb N}}\times {{\mathbb N}}^{{\mathbb N}}$ is a Borel set, then the set $\{f\in {{\mathbb N}}^{{\mathbb N}}: \exists g\in {{\mathbb N}}^{{\mathbb N}}\,
         (f,g)\in C\}$ is analytic, and the set $\{f\in {{\mathbb N}}^{{\mathbb N}}: \forall g\in {{\mathbb N}}^{{\mathbb N}}\, (f,g)\in C\}$ is coanalytic.

However, while the Borel sets are closed under complements, the analytic sets are not. There are coanalytic sets which are not analytic, for example the set ${{{\bf WF}}}$.

We call a set $D \subseteq Y^X$ “complete coanalytic” iff

1.  $D$ is coanalytic

2.  For any coanalytic set $C\subseteq Y^X$ there is a continuous function $F:Y^X\to Y^X$ with $C= F^{-1}[D]$.

It is known that the set ${{\bf WF}}$ is complete coanalytic. In fact, ${{\bf WF}}$ is the “typical” coanalytic set:

Let $D$ be coanalytic. Then $D$ is complete coanalytic iff there is a continous function $F:{{\mathscr P}}({{\mathbb N}}^{<\omega})\to Y^X$ with ${{\bf WF}}= F^{-1}[D]$.

Equivalently, $D$ is complete coanalytic iff there is a function as above which is defined only on the set of trees.

The existence of coanalytic sets which are not analytic easily implies that a complete coanalytic set can never be analytic.

The following theorem should be read as “analytic sets can never reach $ \omega_1$.”

\[bound\]

1.  Every coanalytic set is the union of an increasing $\omega_1$-chain of Borel sets.

2.  Let ${{\bf WF}}= \bigcup_{\alpha \in \omega_1} {{\bf WF}}_\alpha$ be an increasing union of Borel sets, and let $A \subseteq {{\bf WF}}$ be Borel (or even analytic).\
    Then there is $\alpha\in \omega_1 $ such that $A\subseteq {{\bf WF}}_\alpha$.

Clones below ${{\sf T}}_1$ {#t1}
==========================

We fix a 1-1 function $p$ from ${{\mathbb N}}\times {{\mathbb N}}$ onto $ {{\mathbb N}}\setminus \{0\}$. Let $\chi_\Delta$ and $\chi_\nabla $ be the characteristic functions of $\Delta$ and $\nabla$, and let $p_\Delta:= p \cdot \chi_\Delta$, i.e., $p_\Delta(x,y) = p(x,y)$ for $x>y$, and $=0$ otherwise.

Similarly, let $p_\nabla:= p\cdot \chi_\nabla$.

The following is clear:

-   $\chi_\nabla$ and $\chi_\Delta$ are canonical, and in ${{\sf T}}_1\cap {{\sf T}}_2$.

-   $p_\Delta $ and $p_\nabla$ are in ${{\sf T}}_1\setminus {{\sf T}}_2$, and are canonical.

-   $p\notin {{\sf T}}_1\cup {{\sf T}}_2$. In fact, the only clone containing ${{{\mathscr O}}^{(1)}} \cup \{p\}$ is ${{\mathscr O}}$ itself.

${{\sf T}}_1$ is generated by $\{p_\Delta\}\cup {{{\mathscr O}}^{(1)}}$.

Let ${\mathscr{C}}$ be the binary clone generated by $\{p_\Delta\}\cup {{{\mathscr O}}^{(1)}}$. We will first find a function $q\in {\mathscr{C}}$ satisfying

1.  $q$ is 1-1 on $\Delta$

2.  $q(x,y) = Q(x)$ on $\nabla$, for some 1-1 function $Q$

3.  $q[\Delta]\cap q[\nabla] = \emptyset$.

Note that any two functions $q$, $q'$ satisfying these properties will be equivalent, in the sense that there is a unary function $u$ with $q(x,y)=u(q'(x,y))$ for all $(x,y)\in \Delta\cup \nabla$.)

\#1\#2\#3\#4\#5[ @font ]{}

(5037,3264)(0,-10) (1575,3237)(1575,12)(5025,12) (1575,12)(4725,3162) (3750,1062)[(0,0)\[lb\][$p(x,y)$]{}]{} (2475,2412)[(0,0)\[lb\][$x$]{}]{}

Properties of $q$ (simplified)

Let $P(x) = \max \{p(x,y): y\le x\}+1$, and let $$q(x,y):= p_\Delta(P(x), p_\Delta(x,y)).$$ Note that this actually means $q(x,y) = 
    p(P(x), p_\Delta(x,y))$, as $P(x)>p_\Delta(x,y)$ for all $x,y$. So, $$q(x,y) = \KNUTHcases{ p(P(x), p(x,y)) & for  $x>y$\cr
        p(P(x),0)   & for  $x \le y$,\cr}$$

So $  q$ satisfies (1)–(3), and $q\in {\mathscr{C}}$.

We now consider an arbitrary almost unary function $f$, say $f(x,y) < F(x)$ for all $x,y$. Wlog we assume $f(x,y)>0$ for all $(x,y)$.

Let $p':{{\mathbb N}}\times {{\mathbb N}}\to {{\mathbb N}}$ be a 1-1 function satisfying $p'(x,y)>x$ for all $x,y$.

Define $$\begin{aligned}
    f_1(x,y) &= \KNUTHcases{
        p'(F(x), f(x,y)) 
            & for $x> y$\cr
            F(x)     & for $x\le y$\cr
    }\\
f_2(x,y) &= \KNUTHcases{\rlap{0}
    \hphantom{   p'(F(x), f(x,y)) }
    & for $x> y$\cr
        f(x,y)    & for $x\le y$\cr
}
\end{aligned}$$

\#1\#2\#3\#4\#5[ @font ]{}

(9037,3264)(0,-10) (0075,3237)(0075,12)(3525,12) (0075,12)(3225,3162) (0975,2412)[(0,0)\[lb\][$F(x)$]{}]{} (1750,562)[(0,0)\[lb\][$f(x,y)$ (but $>x$)]{}]{}

(5575,3237)(5575,12)(8925,12) (5575,12)(8725,3162) (6475,2412)[(0,0)\[lb\][$f(x,y)$]{}]{} (7250,562)[(0,0)\[lb\][$0$]{}]{}

Definitions of $f_1$ and $f_2$ (simplified)

Then $f_1(x,y) = u_1(q(x,y))$ for some unary $u_1$, and $f_2(x,y) = u_2(p_\Delta(y+1, x)$ for some unary $u_2$. So $f_1,f_2\in {\mathscr{C}}$.

Let $f'(x,y):= p_\Delta(f_1(x,y),f_2(x,y))$. Now $f_2(x,y)<   F(x) \le f_1(x,y)$ for all $x,y$, so $f'(x,y) = p(f_1(x,y),f_2(x,y))$.

As $f(x,y)$ can be recovered from the pair $(f_1(x,y), f_2(x,y))$, and hence also from $f'(x,y)$, we conclude that $f(x,y) = v(f'(x,y))$ for some unary $v$. Hence $f\in
        {\mathscr{C}}$.

If ${\mathscr{C}}\subseteq {{\sf T}}_1$ is a binary clone containing ${{{\mathscr O}}^{(1)}}$, then either ${\mathscr{C}}= {{\sf T}}_1$, or ${\mathscr{C}}\subseteq {{\sf T}}_2$.

Hence: ${{\sf T}}_1\cap {{\sf T}}_2$ is the unique coatom in the interval $[{{{\mathscr O}}^{(1)}},
        {{\sf T}}_1]$ of binary clones, and every binary clone in this interval (except for ${{\sf T}}_1$ itself) is included in $ {{\sf T}}_1\cap {{\sf T}}_2$.

Assume $ {{{\mathscr O}}^{(1)}} \subseteq {\mathscr{C}}\subseteq {{\sf T}}_1$, but ${\mathscr{C}}\not \subseteq
{{\sf T}}_2$. So let $f\in {\mathscr{C}}\setminus {{\sf T}}_2$. So there are 1-1 unary functions $u$ and $v$ such that $f(u(x), v(y))$ is canonical and 1-1 on $\Delta$ (or on $\nabla$). So wlog $f$ is canonical and 1-1 on $\Delta$.

Moreover, either $f$ is symmetric, or ${{\rm ran}}(f{{\upharpoonright}}\nabla)\cap {{\rm ran}}(f{{\upharpoonright}}\Delta)= \emptyset$.

In the first case, the function $f'(x,y):=f(2x, 2y+1)$ is 1-1 on all of ${{\mathbb N}}\times {{\mathbb N}}$, so $\langle \{f'\}\cup {{{\mathscr O}}^{(1)}}\rangle = {{\mathscr O}}$, which contradicts our assumption ${\mathscr{C}}\subseteq {{\sf T}}_1$.

In the second case, we can find a unary function $u$ such that $$\forall x,y: \ u(f(2x,2y+1)) =
p_\Delta(x,y),$$ so $p_\Delta\in{\mathscr{C}}$, i.e., $C={{\sf T}}_1$.

Pinsker [@Pinsker:2004a] has analyzed the interval $({{\sf T}}_1,{{\rm Pol}}({{\sf T}}_1))$ of (full) clones, and shown the following:

Let ${\min^+}_n(x_1,\ldots, x_n):= x_{\pi (2)}$, where $\pi$ is any permutation such that $x_{\pi(1)}\le x_{\pi(2)}\le \cdots \le
x_{\pi(n)}$.\
(So ${\min^+}_2(x,y)=\max(x,y)$, and ${\min^+}_3(x,y,z)$ is the median of $x,y,z$.)

Then the clones ${{\mathscr M}}_n:=\langle {{\sf T}}_1\cup \{{\min^+}_n\}\rangle$ are all distinct, $${{\sf T}}_1 \subseteq \cdots \subsetneq {{\mathscr M}}_5 
    \subsetneq {{\mathscr M}}_4 
\subsetneq {{\mathscr M}}_3 = {{\rm Pol}}({{\sf T}}_2)
    \subsetneq {{\mathscr M}}_2 = {{\mathscr O}},$$ and every clone in the interval $[{{\sf T}}_1,{{\rm Pol}}({{\sf T}}_1)]$ is equal to some ${{\mathscr M}}_n$.

So ${{\mathscr M}}_4$ is a coatom in the interval $[{{{\mathscr O}}^{(1)}} , {{\rm Pol}}({{\sf T}}_1)]$ in the lattice of all clones. It is also easy to see that $
{{\rm Pol}}({{\sf T}}_1)\cap {{\rm Pol}}({{\sf T}}_2) = {{\rm Pol}}({{\sf T}}_1\cap {{\sf T}}_2) $ is another coatom.

${{\sf T}}_1$ is a Borel set.

The set ${{\sf T}}_1^{\rm x}:= \{f\in{{{\mathscr O}}^{(2)}}:  \exists F \, \forall
        x,y:f(x,y)\le F(x)\}$ is apparently only $\Sigma_1^1$, but we can rewrite it as $$\begin{split}
        {{\sf T}}_1^{\rm x} &= \{
            f\in{{{\mathscr O}}^{(2)}}: \forall x\,\exists z\, \forall y: f(x,y)\le z \} \\
            &= 
            \bigcap_{x\in {{\mathbb N}}}   \, 
            \bigcup_{z\in {{\mathbb N}}} \, 
            \bigcap_{y\in {{\mathbb N}}}  \, 
            \bigcup_{t\le z} \, 
            \{f\in {{{\mathscr O}}^{(2)}}: f(x,y) = t \},
            \end{split}$$ which is $F_{\sigma\delta}$.

${{\sf T}}_1^{\rm y}$ can be defined similarly, and ${{\sf T}}_1 = {{\sf T}}_1^{\rm x}\cup 
            {{\sf T}}_1^{\rm y}$.

Clearly, ${{\rm Pol}}({{\sf T}}_1)$ is coanalytic. (See \[closure\](5).) By Pinsker’s theorem, ${{\rm Pol}}({{\sf T}}_1) = \langle {{\sf T}}_1\cup
            \{{\min^+}_3\}\rangle$ is finitely generated over ${{\sf T}}_1$, hence analytic and therefore even Borel. An explicit Borel description can be found in [@Pinsker:2004a].

Clones below ${{\sf T}}_2$ {#t2}
==========================

In the previous section we have seen:

${{\sf T}}_1 = \langle {{{\mathscr O}}^{(1)}} \cup \{p_\Delta\}\rangle$. Thus, ${{\sf T}}_1$ is finitely generated over ${{{\mathscr O}}^{(1)}} $.

The next theorem and its corollaries show that ${{\sf T}}_2$ is not finitely generated over ${{{\mathscr O}}^{(1)}} $.

Let $B \subseteq {{\mathscr O}}$ be a Borel or analytic set. Then $\langle B\rangle$ is analytic.

Similarly, if $B \subseteq {{{\mathscr O}}^{(2)}} $ is a Borel or analytic set, then $\langle B\rangle_{{{{\mathscr O}}^{(2)}}}$ (the binary clone generated by $B$) is analytic.

Is there a Borel set $B$ (perhaps even a closed set? a countable set? a set of the form ${{{\mathscr O}}^{(1)}} \cup \{f_1,\ldots, f_n\}$?) such that $\langle B\rangle$ is not Borel?

${{\sf T}}_2$, ${{\rm Pol}}({{\sf T}}_2)$, ${{\sf T}}_1\cap {{\sf T}}_2$ and ${{\rm Pol}}({{\sf T}}_1\cap {{\sf T}}_2)$ are complete coanalytic sets.

We will define a continuous map $F$ from the set of all trees $T
      \subseteq {{\mathbb N}}^{<{{\mathbb N}}}$ into ${{\sf T}}_1$ such that

> for all $T $: $T$ is wellfounded iff $F(T)\in {{\sf T}}_2$.

Let $\{s_n:n\in {{\mathbb N}}\}$ enumerate all finite sequences of natural numbers, with $ s_k\vartriangleleft s_n \Rightarrow k<n$.

For any tree $T \subseteq \{s_n:n\in {{\mathbb N}}\}$ let $F(T)$ be defined as follows: $$F(T)(k,n) = \KNUTHcases { p(k,n) & if $k<n$ and $s_k,s_n\in T$,
      $s_k\vartriangleleft s_n$\cr
            0   & otherwise\cr
}$$

Now if $A:=\{s_{n_1}, s_{n_2},\ldots \,\}$ is an infinite branch in $T$, then $F(T){{\upharpoonright}}\nabla_{A,A} $ is 1-1.

Conversely: Assume $A = \{n_1<n_2< \cdots \}$, $B= \{m_1<m_2<\cdots \}$, and $F(T){{\upharpoonright}}\nabla_{A,B}$ is 1-1.\
We claim that $s_{n_1}\vartriangleleft s_{n_2}$. Indeed, for any large enough $k$ we have $F(T)(n_1,m_k)\not=0$, so $s_{n_1}\vartriangleleft s_{m_k}$, and similarly $s_{n_2}\vartriangleleft s_{m_k}$. So $s_{n_1}\vartriangleleft s_{n_2}$.\
Similarly we get $s_{n_1}\vartriangleleft s_{n_2} \vartriangleleft 
s_{n_3}\vartriangleleft \cdots $.

${{\rm Pol}}({{\sf T}}_2)$, ${{\sf T}}_2$, ${{\sf T}}_2\cap {{\sf T}}_1$ are not countably generated over ${{{\mathscr O}}^{(1)}}$.

If $C$ is a countable set, then $C\cup {{{\mathscr O}}^{(1)}} $ is Borel, so $\langle C\cup {{{\mathscr O}}^{(1)}} \rangle$ is analytic, hence not complete coanalytic.

The well-known analysis of coanalytic sets now gives the following:

There is a sequence $(C_i:i\in \omega_1)$ of Borel clones such that:

$i<j$ implies $C_i\subsetneq  C_j$, $\bigcup_{i\in \omega_1} C_i =
      {{\sf T}}_2$, and:\
For every analytic clone $C\subseteq {{\sf T}}_2$ there is $i< \omega_1$ such that $C\subseteq C_i$.

In other words: There is an increasing family of $\aleph_1$ many analytic clones below ${{\sf T}}_2$ such that every analytic clone below ${{\sf T}}_2$ is covered by a clone from the family.

A similar representation can be found for ${{\rm Pol}}({{\sf T}}_2)$, ${{\sf T}}_1\cap {{\sf T}}_2$, etc.

By \[bound\](1), we can find an increasing family of Borel sets $(B_i:i<\omega_1)$ such that ${{\sf T}}_2=\bigcup_i B_i$. Clearly each clone $\langle B_i\rangle$ is analytic. By the boundedness theorem (\[bound\](2)) we know that for all $i$ there is $j$ with $\langle B_i\rangle \subseteq B_j$. Let $h:\omega_1\to \omega_1$ be continuous and strictly increasing such that $\forall i: \langle
B_i\rangle \subseteq B_{f(i)}$. Now the family $\{B_i: f(i)=i\}$ is as desired.

Find a nice cofinal family in $\{{\mathscr{C}}: {\mathscr{C}}\subsetneq
{{\sf T}}_2\}$. I.e., a nice family ${\mathscr{F}}$ such that $\forall {\mathscr{C}}\subsetneq {{\sf T}}_2$ there is ${\mathscr{C}}'\in {\mathscr{F}}$ with ${\mathscr{C}}\subseteq {\mathscr{C}}'$.

Since we already have a family that covers all analytic clone, this question asks really: which nonanalytic clones are there below ${{\sf T}}_2$?

Can we get a family $B_i$ as in the theorem where each $B_i$ is generated by a single function?

Analyze the interval $[ {{\sf T}}_2, {{\rm Pol}}({{\sf T}}_2)]$.
