STRUCTURE OF SUMMABLE TALL IDEALS UNDER KATĚTOV ORDER

Abstract

We show that Katětov and Rudin–Blass orders on summable tall ideals coincide. We prove that Katětov order on summable tall ideals is Galois–Tukey equivalent to $(\omega ^\omega ,\le ^*)$. It follows that Katětov order on summable tall ideals is upwards directed which answers a question of Minami and Sakai. In addition, we prove that ${l_\infty }$ is Borel bireducible to an equivalence relation induced by Katětov order on summable tall ideals.

1 Introduction

A set $\mathcal I\subseteq \mathcal P(\omega )$ is an ideal on $\omega $ if it is closed under taking subsets and finite unions. In this paper we always assume that an ideal is proper, i.e., it contains all finite subsets of $\omega $ and it does not contain $\omega $ . Given an ideal $\mathcal I$ on $\omega $ , define $\mathcal I^+=\mathcal P(\omega )\setminus \mathcal I$ . Elements of $\mathcal I^+$ are called $\mathcal I$ -positive sets. The dual filter of $\mathcal {I}$ is denoted by $\mathcal I^*=\{\omega \setminus A:A\in \mathcal I\}$ . If Y is an $\mathcal I$ -positive set, then $\mathcal I\big |Y=\{A\cap Y:A\in \mathcal I\}$ is an ideal on Y.

The set of all finite subsets of $\omega $ is denoted by $\mathbf {Fin}$ or $[\omega ]^{<\omega }$ . Note that $\mathbf {Fin}$ is an ideal on $\omega $ . The set of all infinite subsets of $\omega $ is denoted by $[\omega ]^\omega $ . We say that an ideal $\mathcal I$ on $\omega $ is tall if for any $A\in [\omega ]^\omega $ , there exists $B\in [A]^\omega $ such that $B\in \mathcal I$ . Let $X,Y$ be two countably infinite sets. Let $\mathcal I$ be an ideal on X and $\mathcal J$ be an ideal on Y. We write $\mathcal I\simeq \mathcal J$ if there exists a bijection $e:X\to Y$ such that $A\in \mathcal I\Leftrightarrow e[A]\in \mathcal J$ where $e[A]$ is the image of A under e. One may check that an ideal $\mathcal I$ is not tall if there exists an $\mathcal I$ -positive set A such that $\mathcal I\big |A\simeq \mathbf {Fin}$ .

All ideals are assumed to be tall throughout this paper.

The set of all non-negative rational numbers is denoted by $\mathbb {Q_+}$ . The set of all non-negative real numbers is denoted by $\mathbb {R_+}$ . An ideal $\mathcal I$ on $\omega $ is a summable ideal if there is a function $f:\omega \to \mathbb {R_+}$ with $\sum \limits _{n<\omega }f(n)=\infty $ such that

$$ \begin{align*} \mathcal I=\mathcal I_f:=\left\{A\subseteq\omega:\sum\limits_{n\in A}f(n)<\infty\right\}. \end{align*} $$

Every summable ideal is an $F_{\sigma }$ subset of $2^{\omega }$ via characteristic functions (see Theorem 2.1 in Section 2 or [3]). For each summable ideal $\mathcal I_f$ , if we take a function $f':\omega \to \mathbb {Q_+}$ such that

$$ \begin{align*} |f(n)-f'(n)|\le\frac{1}{2^n} \text{ for each } n\in\omega, \end{align*} $$

then we have $\mathcal I_f=\mathcal I_{f'}$ , so we assume always that $f\in \mathbb Q_+^\omega $ whenever we say that $\mathcal I_f$ is a summable ideal. One may easily check that summable ideal $\mathcal I_f$ is tall if and only if $\lim \limits _{n\to \infty }f(n)=0$ . Define

$$ \begin{align*} \boldsymbol{\textsf{summable ideals}}=\{\mathcal I_f: f\in\mathbb{Q}_+^\omega ,~\sum\limits_{n<\omega}f(n)=+\infty \text{ and } \lim\limits_{n \rightarrow \infty}f(n)=0\}. \end{align*} $$

The followings are important tools for studying ideals, we refer the readers to a survey written by Hrušák [3] for details:

1. (1) (Katětov ordering) $\mathcal I\leq _K \mathcal J$ if there is a function $p: \omega \to \omega $ such that

   $$\begin{align*}\forall A\subseteq \omega (A\in \mathcal I\Rightarrow p^{-1}(A)\in \mathcal J).\end{align*}$$

2. (2) (Katětov–Blass ordering) $\mathcal I\leq _{KB} \mathcal J$ if there is a finite-to-one function $p: \omega \to \omega $ such that

   $$\begin{align*}\forall A\subseteq \omega (A\in \mathcal I\Rightarrow p^{-1}(A)\in \mathcal J).\end{align*}$$

3. (3) (Rudin–Blass ordering) $\mathcal I\leq _{RB} \mathcal J$ if there is a finite-to-one function $p: \omega \to \omega $ such that

   $$\begin{align*}\forall A\subseteq \omega (A\in \mathcal I\Leftrightarrow p^{-1}(A)\in \mathcal J).\end{align*}$$

Obviously, $\mathcal I\le _{RB} \mathcal J \Rightarrow \mathcal I\le _{KB} \mathcal J \Rightarrow \mathcal I\le _K \mathcal J$ . Denote $\mathcal I<_K \mathcal J$ if $\mathcal I\leq _K \mathcal J$ and $\mathcal J\not \leq _K \mathcal I$ . Denote $\mathcal I\simeq _K \mathcal J$ if $\mathcal I\leq _K \mathcal J$ and $\mathcal J\leq _K \mathcal I$ . Notice that $\simeq _K$ is an equivalence relation. Similarly we define $\mathcal I<_{KB} \mathcal J$ , $\mathcal I<_{RB} \mathcal J$ , $\mathcal I\simeq _{KB} \mathcal J$ , and $\mathcal I\simeq _{RB} \mathcal J$ .

Farah [2] proved that the Rudin–Blass order on all summable ideals has neither maximal elements nor minimal elements. He also proved that it is a dense ordering which includes an isomorphic copy of $(\mathcal P(\omega )/\mathrm {Fin},\subseteq ^*)$ . Let $F_\sigma $ ideals be the family of all $F_\sigma $ -ideals. Minami and Sakai [5] proved that $(F_\sigma \boldsymbol{\textsf{ideals}},\le _K)$ and $(F_\sigma \boldsymbol{\textsf{ideals}},\le _{KB})$ are both upward directed and asked that if this is true for summable ideals [5, Question 5.1]. We will give a positive answer to this question in Section 3.

Let us consider a variation of the definition of summable ideals. Let

$$ \begin{align*} \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}=\{f \in\mathbb{Q}_+^\omega :~\sum\limits_{n<\omega}f(n)=+\infty, ~\lim\limits_{n \rightarrow \infty}f(n)=0 , \text{ and } \forall n(f(n)\ge f(n+1))\} \end{align*} $$

and

$$ \begin{align*} \boldsymbol{\textsf{ST}}=\{\mathcal I_f:f\in\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}\}. \end{align*} $$

Actually, $\boldsymbol{\textsf{ST}}$ and $\boldsymbol{\textsf{summable ideals}}$ are virtually the same class of ideals (up to isomorphism) and we will show it in Section 2 (see Propositions 2.2 and 2.3).

In Section 4, we give a characterization of $\leq _{K}$ on $\boldsymbol{\textsf{ST}}$ which is crucial for later sections. In particular, we prove that for every $\mathcal I_f, \mathcal I_g\in \boldsymbol{\textsf{ST}}$ , $\mathcal I_f\leq _{K}\mathcal I_g$ if and only if $\mathcal I_f\leq _{RB}\mathcal I_g$ (see Theorem 4.1).

Section 5 and 6 deal with Galois–Tukey connections which is introduced by Vojtáš [7]. For definition of Galois–Tukey connections, we follow the terminology in [1]. Let $\textbf {A}=(A_-,A_+,A)$ and $\textbf {B}=(B_-,B_+,B)$ be triples such that $A\subseteq A_-\times A_+$ and $B\subseteq B_-\times B_+$ . We say $\textbf {A}\le _{GT}\textbf {B}$ if there is a pair $\rho =(\rho _-,\rho _+)$ of functions such that:

1. (1) $\rho _-:A_-\to B_-$ ,

2. (2) $\rho _+:B_+\to A_+$ , and

3. (3) $\forall a\in A_-\forall b\in B_+(\rho _-(a)Bb\Rightarrow aA\rho _+(b))$ .

We write $\textbf {A}\simeq _{GT}\textbf {B}$ if $\textbf {A}\le _{GT}\textbf {B}$ and $\textbf {B}\le _{GT}\textbf {A}$ . We say that $\textbf {A}$ is Galois–Tukey equivalent to $\textbf {B}$ if $\textbf {A}\simeq _{GT}\textbf {B}$ .

Minami and Sakai [5] proved that $(F_\sigma \boldsymbol{\textsf{ideals}},\le _K)$ and $(F_\sigma \boldsymbol{\textsf{ideals}},\le _{KB})$ are both Galois–Tukey equivalent to $(\omega ^\omega ,\le ^*)$ . We prove that $(\boldsymbol{\textsf{ST}},\le _K) \simeq _{GT}(\omega ^\omega ,\le ^*)$ in Section 5 and that $(\boldsymbol{\textsf{ST}},\ge _K)\simeq _{GT}(\omega ^\omega ,\le ^*)$ in Section 6.

The last section is devoted to the study of Borel reducibility. We say that a topological space X is a Borel space if X is a Borel subset of some Polish space. Let X, Y be Borel spaces. Let E and F be equivalence relations on X and Y, respectively. We say that E is Borel reducible to F (denote $E\le _B F$ ) if there is a Borel map $\Phi :X\to Y$ such that $xEy\Leftrightarrow \Phi (x)F\Phi (y)$ for all $x,y\in X$ . We say that E is Borel bireducible to F if $E\le _B F$ and $F\le _B E$ . Let $l_\infty =\{f\in \mathbb {R}^\omega :\sup \limits _{n<\omega }|f(n)|<\infty \}$ . For each $x,y\in \mathbb {R}^\omega $ , define

$$ \begin{align*} x{l_\infty}y\Longleftrightarrow x-y\in l_\infty. \end{align*} $$

We will prove that $l_\infty $ is Borel bireducible to $\simeq _K$ on $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ . Here, $f\simeq _K g$ means $\mathcal I_f\simeq _K\mathcal I_g$ .

2 Preliminary

We make two comments in this section. One is that there is a convenient tool for studying $F_\sigma $ -ideals. The other is that $\boldsymbol{\textsf{ST}}$ and summable ideals are virtually the same class of ideals (up to isomorphism).

Every summable ideal is an $F_\sigma $ -ideal. This can be inferred by Mazur’s characterization of $F_\sigma $ -ideals using submeasures. A submeasure on $\omega $ is a function $\mu :\mathcal P(\omega ) \to [0,+\infty ]$ with the following properties for A, $B\subseteq \omega $ :

1. (1) $\mu (A)\le \mu (B)$ if $A\subseteq B$ ,

2. (2) $\mu (A\cup B)\le \mu (A)+\mu (B)$ , and

3. (3) $\mu (\emptyset )=0$ .

A submeasure $\mu $ is lower semicontinuous (lsc) if for every $A\subseteq \omega $ we have that

$$ \begin{align*} {\mu}(A)=\lim\limits_{n\to\infty}\mu(A\cap n). \end{align*} $$

We say that $\mu $ is unbounded if ${\mu }(\omega )=\infty $ . Mazur proved the following theorem.

Theorem 2.1. [4] The following are equivalent for every ideal $\mathcal I$ on $\omega :$

1. (1) $\mathcal I$ is an $F_\sigma $ -ideal.

2. (2) $\mathcal I=Fin(\mu )$ for some unbounded lsc submeasure $\mu $ on $\omega $ , where

   $$ \begin{align*} Fin(\mu)=\{A\subseteq\omega:{\mu}(A)<\infty\}. \end{align*} $$

For each summable ideal $\mathcal I_f$ , let $u_f(A)=\sum _{i\in A}f(i)$ for $A\subseteq \omega $ . It is easy to see that $u_f$ is an unbounded lsc submeasure on $\omega $ by

$$\begin{align*}{u}_f(A)=\sum_{i\in A}f(i)=\lim\limits_{n\to\infty}\sum_{i\in A\cap n}f(i)=\lim\limits_{n\to\infty}u_f(A\cap n).\end{align*}$$

Now we turn to the second comment.

Proposition 2.2. There is a Borel function $F:\boldsymbol{\textsf{F}}\to \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ such that $\mathcal I_f\simeq \mathcal I_{F(f)}$ for every $f\in \boldsymbol{\textsf{F}}$ where

$$ \begin{align*} \boldsymbol{\textsf{F}}=\left\{ f\in\mathbb{Q}_+^\omega: \sum\limits_{n\in\omega}f(n)=\infty \textrm{and} \lim\limits_{n\to\infty}f(n)=0\right\}. \end{align*} $$

Proof Let $f\in \boldsymbol{\textsf{F}}$ . For each $n\in \omega $ , let

$$ \begin{align*} X_n=\left\{k\in\omega:\frac{1}{n+2}\le f(k)<\frac{1}{n+1}\right\} \end{align*} $$

and $N_n=|X_n|$ . Since $\mathcal I_f$ is tall, we have that $N_n<\infty $ for all $n\in \omega $ . Denote $M_n=\sum \limits _{i=0}^{n}N_i$ . Let $Y_0=[0,M_0)$ and $Y_n=[M_{n-1},M_{n})$ for each $n>0$ . It follows that $|X_n|=|Y_n|$ for all n. For each $n\in \omega $ , define

$$ \begin{align*} m_1^n \text{ by } f(m_1^n)=\max f[X_n] \end{align*} $$

and

$$ \begin{align*} m_j^n \text{ by } f(m_j^n)=\max f[X_n\setminus\{m_1^n,\ldots, m_{j-1}^n\}] \text{ for each } 1<j\le N_n. \end{align*} $$

For each $n\in \omega $ , define a bijection $h_n:X_n\to Y_n$ by

$$ \begin{align*} h_n(m_j^n) = M_{n-1} + j - 1 \text{ for each } 1\le j \le N_n. \end{align*} $$

For each $n\in \omega $ , define $f^{\prime }_n:Y_n\to \mathbb {Q}_+$ by

$$ \begin{align*} f^{\prime}_n(h_n(m_j^n))=f(m_j^n) \text{ for all } 1\le j\le N_n. \end{align*} $$

Let $f'=\bigcup _{n\in \omega }f^{\prime }_n$ . Define $F(f)=f'$ . It follows that $F(f)$ is nonincreasing by the definition of $f'$ . Then $\mathcal I_f\simeq \mathcal I_{F(f)}$ is witnessed by $h=\bigcup _{n\in \omega }h_n$ .

Next we show that F is Borel. For any $n\in \omega $ and $b>a\ge 0$ , define

$$ \begin{align*} U&=\{f\in\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}:f(n)\in(a,b)\} \text{ and} \\U_q&=\{f\in\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}:f(n)=q\} \text{ for all } q\in(a,b)\cap\mathbb Q_+. \end{align*} $$

It follows that U is a basic open set in $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ and $U=\bigcup _{q\in (a,b)\cap \mathbb Q_+}U_q$ . Fix n, U, q, and $U_q$ as above. By the definition of $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ , for each $f\in U_q$ we have that

$$ \begin{align*} f(i)\ge q \text{ for all } 0\le i<n \text{ and } f(j)\le q \text{ for all } j>n. \end{align*} $$

Let $A=\{q\}$ , $B=[q,+\infty )$ , and $C=[0,q]$ . It is easy to see that the set $A\times B^n\times C^\omega $ is Borel in $\mathbb {Q}_+^{\omega }$ . For each $K\in [\omega ]^{n+1}$ , let $P_K\subseteq \omega ^{n+1}$ be the set of all permutations of K (i.e., all bijections from K to K). For each $a=(a_0,a_1,\ldots ,a_n)\in P_K$ , define $S(a)=(S_0,S_1,\ldots ,S_n,\ldots )\in \mathcal P(\omega )^\omega $ by

$$ \begin{align*} S_{a_0}=A, S_{a_1}=\cdots=S_{a_n}=B \text{ and } S_j=C \text{ for all } j\not\in\{a_0,\ldots,a_n\}. \end{align*} $$

Denote $\prod S(a)=\prod _{i\in \omega }S_i.$ Then

$$ \begin{align*} F^{-1}(U)=\bigcup_{q\in(a,b)\cap\mathbb Q_+}F^{-1}(U_q)=\bigcup_{q\in(a,b)\cap\mathbb Q_+}\bigcup_{K\in[\omega]^{n+1}}\bigcup_{a\in P_K}\prod S(a). \end{align*} $$

It follows that $F^{-1}(U)$ is a Borel set and F is Borel.

Proposition 2.3. Define a map $\Lambda :\boldsymbol{\textsf{summable ideals}} \to \boldsymbol{\textsf{ST}}$ by

$$ \begin{align*} \Lambda(\mathcal I_f)=\mathcal I_{F(f)} \text{ for all } \mathcal I_f\in\boldsymbol{\textsf{summable ideals}}, \end{align*} $$

where F is the function taken from the Proposition 2.2. Then for each pair $\mathcal I_f,\mathcal I_g\in \boldsymbol{\textsf{summable ideals}}$ we have that

$$\begin{align*}\mathcal I_f\le_K\mathcal I_g\Leftrightarrow\mathcal I_{F(f)}\le_K\mathcal I_{F(g)}.\end{align*}$$

Proof ( $\Rightarrow $ ): Let $\mathcal I_f,\mathcal I_g\in \boldsymbol{\textsf{summable ideals}}$ such that $\mathcal I_f\le _K\mathcal I_g$ . Then we have that

$$\begin{align*}\mathcal I_{F(f)}\simeq\mathcal I_f\le_K\mathcal I_g\simeq\mathcal I_{F(g)}.\end{align*}$$

It follows that $\mathcal I_{F(f)}\le _K\mathcal I_{F(g)}$ .

( $\Leftarrow $ ): Let $\mathcal I_f,\mathcal I_g\in \boldsymbol{\textsf{summable ideals}}$ such that $\mathcal I_f\not \le _K\mathcal I_g$ and $p:\omega \to \omega $ be a map. Let $e_1$ and $e_2$ be witnesses for $\mathcal I_f\simeq \mathcal I_{F(f)}$ and $\mathcal I_g\simeq \mathcal I_{F(g)}$ , respectively. By $\mathcal I_f\not \le _K\mathcal I_g$ , there exists $A\in \mathcal I_f$ such that

$$\begin{align*}(e_1^{-1}\circ p\circ e_2)^{-1}(A)\not\in\mathcal I_g.\end{align*}$$

Then we have that $e_1[A]\in \mathcal I_{F(f)}$ and

$$\begin{align*}e_2^{-1}(p^{-1}(e_1[A]))\not\in\mathcal I_g\Leftrightarrow p^{-1}(e_1[A])\not\in\mathcal I_{F(g)}.\end{align*}$$

Thus $\mathcal I_{F(f)}\not \le _K\mathcal I_{F(g)}$ .

3 An answer to Minami and Sakai’s question

In this section, we prove the following theorem which give a positive answer to a question of Minami and Sakai’s [5, Question 5.1].

Theorem 3.1. $(\boldsymbol{\textsf{Summable ideals}}, \leq _{KB})$ is countably upward directed.

Proof Suppose that $\mathcal I_f\in \boldsymbol{\textsf{summable ideals}}$ . Then $\lim \limits _{n \rightarrow \infty }f(n)=0$ and $\sum \limits _{n\in \omega }f(n)=\infty $ . Inductively take $\{k_n:n\in \omega \}$ such that for each $n\in \omega $ ,

1. (1) $k_n<k_{n+1}$ ,

2. (2) $f(m)<1/(n+1)$ for each $m\ge k_n$ , and

3. (3) $ u_f([k_n,k_{n+1}))\ge 1$ .

Suppose we have already constructed $\{k_j:j\le n\}$ such that (1)–(3) holds. Since $\lim _{n \rightarrow \infty }f(n)=0$ , we can find $k_{n+1}$ large enough such that (1) and (2) hold. By $\Sigma _{n\in \omega }f(n)=\infty $ we have $u_f([k_n,\infty ))=\infty $ , so we may find $k_{n+1}$ such that (3) holds. Denote $N_n:=u_f([k_n,k_{n+1}))\ge 1$ and $I_n:=[k_n,k_{n+1})$ for all $n\in \omega $ . Then

$$ \begin{align*} u_f(I_n)= N_n\ge 1. \end{align*} $$

Now let $\{\mathcal I_{f_m}:m\in \omega \}\subseteq \boldsymbol{\textsf{summable ideals}}$ . For each $m\in \omega $ , let $k^m_n$ , $I^m_n$ , $N^m_n$ be as above. Then for all $n,m\in \omega $ ,

$$ \begin{align*} u_{f_m}(I_n^m)= N_n^m\ge 1. \end{align*} $$

For each $n\in \omega $ , let $X_n=\prod \limits _{m<n} I^m_n\subseteq \omega ^n$ and $X=\bigcup \limits _{n\in \omega }X_n$ . Fix $n\in \omega $ . For any $(i_0,i_1,\ldots ,i_{n-1})\in X_n$ , define a function f by

$$ \begin{align*} f\big( (i_0,i_1,\ldots,i_{n-1}) \big)=\frac{\prod\limits_{m<n}f_m(i_m)}{\prod\limits_{m<n}N^m_n}. \end{align*} $$

Then

$$ \begin{align*} u_f(X_n) & =\displaystyle\sum\limits_{(i_0,\ldots,i_{n-1})\in X_n}f\big((i_0,\ldots,i_{n-1})\big)= \displaystyle\sum\limits_{i_0\in I^0_n, \ldots, i_{m}\in I^{n-1}_n}f\big((i_0,\ldots,i_{n-1})\big) \\ & =\frac{1}{\prod\limits_{m<n}N^m_n} \cdot \displaystyle\sum\limits_{i_0\in I^0_n, \cdots, i_{n-1}\in I^{n-1}_n}\left(\prod\limits_{m<n}f_m(i_m)\right)=\frac{1}{\prod\limits_{m<n}N^m_n} \cdot \prod\limits_{m<n}u_{f_m}(I^m_n) \\ & =1, \end{align*} $$

so $u_f(X)=\infty $ .

By (2), for all $n\in \omega $ we have that

$$ \begin{align*} f\big( (i_0,i_1,\ldots,i_{n-1}) \big)\le\frac{1}{(n+1)^n} \text{ for every } (i_0,i_1,\ldots,i_{n-1})\in X_n, \end{align*} $$

so $\mathcal I_f$ is tall.

We will show that for each $m\in \omega $ , $\mathcal I_{f_m}\le _{KB} \mathcal I_f$ . Fix $m\in \omega $ . Define $\pi _m:X\to \omega $ by

$$ \begin{align*} \pi_m\big((i_0,\ldots,i_{n-1})\big)=0, & n\le m, \\ \pi_m\big((i_0,\ldots,i_{n-1})\big)=i_m, & n> m, \end{align*} $$

Then $\left |\pi _m^{-1}(0)\right |<\infty $ and $u_f\left (\pi _m^{-1}(0)\right )<\infty $ . Let $i\in \omega \setminus \{0\}$ . If $i\in I^m_n$ for some $n\le m$ then $\pi _m^{-1}(i)=\emptyset $ . We assume that $i\in I^m_n$ for some $n>m$ . It follows that $\left |\pi _m^{-1}(i)\right |\le \left |X_n\right |<\infty $ and

$$ \begin{align*} u_f\left(\pi_m^{-1}(i)\right) & = u_f\Big(\big\{(i_0,\ldots,i_m,\ldots,i_{n-1})\in X:i_m=i\big\}\Big) \\ & =\frac{f_m(i)}{N^m_n}\cdot\sum\limits_{(i_{0},\ldots,i_{n-1})}\left(\frac{\prod\limits_{j< n,\ j\neq m}f_j(i_j)}{\prod\limits_{j<n,j\not=m}N^j_n}\right) = \frac{f_m(i)}{N^m_n}\le f_m(i). \end{align*} $$

Thus, for every $A\subseteq \omega \setminus \{0\}$ with $u_{f_m}(A)<\infty $ we have that $u_f\left (\pi ^{-1}_m(A)\right )\le u_{f_m}(A)<\infty $ .

4 Characterizations of Katětov order among summable ideals

In this section, we prove the following theorem which is crucial for later section.

Theorem 4.1. Let $\mathcal I_f$ , $\mathcal I_g\in \boldsymbol{\textsf{ST}}$ . Then the following are equivalent $:$

1. (1) $\mathcal I_f\le _K\mathcal I_g$ .

2. (2) There exist $p:\omega \rightarrow \omega $ and $0<C$ such that

   $$\begin{align*}A[C]=\{n:u_g(p^{-1}(n))\le C\cdot f(n)\}\in\mathcal I_f^*\end{align*}$$
   and $p^{-1}(A[C])\in \mathcal I_g^*$ .

3. (3) There exists $0<M\in \omega $ such that for all $l> M$ and $k_1>k_0\ge M$ , if $u_g([k_0,k_1])>M\cdot u_f([0,l])$ , then $g(k_1)\le M\cdot f(l)$ .

4. (4) There exist an interval-to-one map $p:\omega \rightarrow \omega $ and $0<c<C$ such that $c\cdot f(i)\le u_g(p^{-1}(i))\le C\cdot f(i)$ for all i.

5. (5) There exist an interval-to-one map $p:\omega \rightarrow \omega $ and $0<C$ such that $u_g(p^{-1}(i))\le C\cdot f(i)$ for all i.

6. (6) There exists $0<M\in \omega $ such that for all k, $l\in \omega $ , if $u_g([0,k])>M\cdot u_f([0,l])$ , then $g(k)\le M\cdot f(l)$ .

7. (7) $\mathcal I_f\le _{RB}\mathcal I_g$ .

Proof (1) $\Rightarrow $ (2): Let $p:\omega \rightarrow \omega $ be a witness for $\mathcal I_f\le _K\mathcal I_g$ . We show that there exists $C>0$ such that $A[C]=\left \{n:u_g\left (p^{-1}(n)\right )\le C\cdot f(n)\right \}\in \mathcal I_f^*$ . Otherwise, $A[C]\not \in \mathcal I_f^*$ for every $C>0$ . Thus, we can find pairwise disjoint finite sets $\{a_n:1\le n<\omega \}$ such that for each $1\le n\in \omega $ ,

1. (i) $f(j)\le \frac {1}{n^2}$ for any $j\in a_n$ ,

2. (ii) $a_n\subseteq \omega \setminus A[n]$ , and

3. (iii) $\frac {1}{n^2}\le u_f(a_n)\le \frac {2}{n^2}$ .

By (ii),

$$\begin{align*}u_g\left(p^{-1}\left(a_n\right)\right)> n\cdot u_f\left(a_n\right) \ge \frac{1}{n}.\end{align*}$$

Let $B=\bigcup \limits _{1\le n<\omega }a_n$ . Then

$$ \begin{align*} u_f(B)\le\sum\limits_{n=1}\limits^\infty\frac{2}{n^2}<\infty, \text{and}\ u_g\left(p^{-1}(B)\right)\ge\sum\limits_{n=1}\limits^{\infty}\frac{1}{n}=\infty. \end{align*} $$

This contradicts the definition of p.

(2) $\Rightarrow $ (3): Let p and C be such that $A[C]\in \mathcal I_f^*$ and $p^{-1}(A[C])\in \mathcal I_g^*$ . Then $p^{-1}\left (\omega \setminus A[C]\right )\in \mathcal I_g$ . Take $M>C+1$ such that $u_g\left (p^{-1}\left (\omega \setminus A[C]\right )\setminus M\right )<1$ and $u_f\left ([0,M]\right )>2$ . Assume $l> M$ , $k_1>k_0\ge M$ with $u_g([k_0,k_1])>Mu_f([0,l])$ . Consider $t=[k_0,k_1]\setminus p^{-1}\left ([0,l]\right )$ . The proof is divided into two cases.

Case 1: $p(t)\cap A[C]=\emptyset $ .

Then $t\cap p^{-1}(A[C])=\emptyset $ . By $k_0\ge M$ , we have that $t\subset p^{-1}(\omega \setminus A[C])\setminus M$ . By the definition of M we have $u_g(t)<1$ . On the other hand we have

$$ \begin{align*} u_g\Big([k_0,k_1]\cap p^{-1}([0,l])\cap p^{-1}(\omega\setminus A[C])\Big)\le u_g\Big(p^{-1}(\omega\setminus A[C])\setminus M\Big)<1\end{align*} $$

and

$$ \begin{align*} u_g\Big([k_0,k_1]\cap p^{-1}([0,l])\cap p^{-1}(A[C])\Big)\le C\cdot u_f\Big([0,l]\cap A[C])\Big)\le C\cdot u_f([0,l]). \end{align*} $$

Thus

$$ \begin{align*} u_g\Big([k_0,k_1]\cap p^{-1}([0,l])\Big) & \le 1+C\cdot u_f([0,l]) \\ & = 2+C\cdot u_f([0,l])-1<(C+1)\cdot u_f([0,l])-1 \end{align*} $$

and

$$ \begin{align*} u_g(t)=u_g\Big([k_0,k_1]\setminus p^{-1}\left([0,l]\right)\Big) & = u_g([k_0,k_1])-u_g\Big([k_0,k_1]\cap p^{-1}([0,l])\Big) \\ &> M\cdot u_f([0,l])-((C+1)\cdot u_f([0,l])-1)>1. \end{align*} $$

A contradiction.

Case 2: $p(t)\cap A[C]\neq \emptyset $ .

Let $m\in t$ and $p(m)\in A[C]$ . Then $m\le k_1$ , $p(m)>l$ , and $u_g\left (p^{-1}(p(m))\right )\le C\cdot f(p(m))$ . By the monotonicity of f and g, we have

$$ \begin{align*} g(k_1)\le g(m)\le u_g\left(p^{-1}(p(m))\right)\le C\cdot f(p(m))\le C\cdot f(l)<M\cdot f(l). \end{align*} $$

(3) $\Rightarrow $ (4): Choose $k_0$ such that

$$ \begin{align*} u_g([M,k_0))=u_g([M,k_0-1])>M\cdot u_f([0,M]). \end{align*} $$

We recursively choose a sequence $k_0<k_1<\cdots $ such that for each i, $k_{i+1}$ is the minimal such that $u_g([k_i,k_{i+1}))\ge M\cdot f(M+1+i).$ Then we have

$$ \begin{align*} u_g([M,k_{i+1}))>M\cdot u_f([0,M])+M\cdot\sum\limits_{j=0}\limits^{i}f(M+1+j)=M\cdot u_f([0,M+1+i]). \end{align*} $$

Thus $g(k_{i+1}-1)\le M\cdot f(M+1+i)$ by the assumption of (3). The proof is divided into two cases.

Case 1. $k_{i+1}-1=k_i$ . Clearly we have that $g(k_{i+1}-1)=u_g([k_i,k_{i+1}))= M\cdot f(M+1+i)$ .

Case 2. $k_{i+1}-1>k_i$ . By the definition of $k_{i+1}$ , we have $u_g([k_i,k_{i+1}-1))< M\cdot f(M+1+i).$ This implies that

$$\begin{align*}M\cdot f(M+1+i)\le u_g([k_i,k_{i+1}))&=u_g([k_i,k_{i+1}-1))+g(k_{i+1}-1)\\ &< 2M\cdot f(M+1+i).\end{align*}$$

Let $p:\omega \rightarrow \omega $ be an interval-to-one map such that $p^{-1}([0,M])=[0,k_0)$ and $p^{-1}(M+1+i)=[k_i,k_{i+1})$ for every i. Define

$$\begin{align*}C=\max\left\{2M,\max\left\{\frac{u_g(p^{-1}(n))}{u_f(n)}:n\le M\right\}\right\} \end{align*}$$

and

$$\begin{align*}c=\min\left\{M,\min\left\{\frac{u_g(p^{-1}(n))}{u_f(n)}:n\le M\right\}\right\}.\end{align*}$$

Then, for each $n\le M$ we have that

$$ \begin{align*} c\cdot f(n)\le\frac{u_g\left(p^{-1}(n)\right)}{f(n)}\cdot f(n)=u_g\left(p^{-1}(n)\right)=\frac{u_g\left(p^{-1}(n)\right)}{f(n)}\cdot f(n)\le C\cdot f(n). \end{align*} $$

(4) $\Rightarrow $ (7): For every $A\subseteq \omega $ , we have that

$$ \begin{align*} u_f(A)<\infty\Rightarrow u_g\left(p^{-1}(A)\right)\le C\cdot u_f(A)<\infty \end{align*} $$

and

$$ \begin{align*} u_g\left(p^{-1}(A)\right)<\infty\Rightarrow u_f(A)\le \frac{1}{c}\cdot u_g\left(p^{-1}(A)\right)<\infty. \end{align*} $$

(4) $\Rightarrow $ (5), (5) $\Rightarrow $ (1), (7) $\Rightarrow $ (1) are clear.

(5) $\Rightarrow $ (6): Let C be as in (5). Define $M=C$ . We will show that M is as desired. Let l, $k\in \omega $ with $u_g([0,k])>M\cdot u_f([0,l])$ . By the assumption of (5), $u_g\left (p^{-1}([0,l])\right )\le M\cdot u_f([0,l])$ , so $[0,k]\setminus p^{-1}([0,l])\neq \emptyset $ . Take $m\in [0,k]\setminus p^{-1}([0,l])$ . Then $m\le k$ and $p(m)>l$ . It follows that

$$ \begin{align*} g(k)\le g(m)\le u_g\left(p^{-1}(p(m))\right)\le M\cdot f(p(m))\le M\cdot f(l). \end{align*} $$

(6) $\Rightarrow $ (5): Choose $k_0$ such that

$$ \begin{align*} u_g([0,k_0))=u_g([0,k_0-1])>M\cdot f(0). \end{align*} $$

Recursively define a sequence $k_0<k_1<\cdots $ such that for each $i>0$ , $k_i$ is the minimal such that $u_g([k_{i-1},k_i))\ge M\cdot f(i).$ Then we have

$$ \begin{align*} u_g([0,k_i))>M\cdot\sum\limits_{j=0}\limits^{i}f(j)=M\cdot u_f([0,i]). \end{align*} $$

Thus $g(k_i-1)\le M\cdot f(i)$ by the assumption of (5). The proof is divided into two cases.

Case 1. $k_i-1=k_{i-1}$ . Clearly we have that $g(k_i-1)=u_g([k_{i-1},k_i))=M\cdot f(i)$ .

Case 2. $k_i-1>k_{i-1}$ . By the choice of $k_i$ , we have $u_g([k_{i-1},k_i-1))< M\cdot f(i)$ . This implies that

$$ \begin{align*} M\cdot f(i)\le u_g([k_i,k_{i+1}))=u_g([k_i,k_{i+1}-1))+g(k_{i+1}-1)< 2M\cdot f(i). \end{align*} $$

Let $p:\omega \rightarrow \omega $ be an interval-to-one map such that $p^{-1}(0)=[0,k_0)$ and $p^{-1}(i)=[k_{i-1},k_i)$ for every $i>0$ . It is easy to see that p and $C=2M$ .

Remark: It is worth to note that p in the proof of (3) $\Rightarrow $ (4) and (6) $\Rightarrow $ (5) is a surjection and $\max p^{-1}(n)<\min p^{-1}(n+1)$ for $n\in \omega $ (see Figure 1).

Figure 1 An example of interval-to-one map $p$ in Remark.

5 The structure of $(\boldsymbol{\textsf{ST}},\le _K)$ in the sense of Galois–Tukey connection

In this section we prove that $(\boldsymbol{\textsf{ST}},\le _K)\simeq _{GT}(\omega ^{\omega },\le ^*)$ (see Theorem 5.6). We first prove $(\boldsymbol{\textsf{ST}},\le _K)\le _{GT}(\omega ^{\omega },\le ^*)$ (see Lemma 5.4).

We will define an order $(\mathbb H,\leq ^\circ )$ such that $(\mathbb H,\leq ^\circ )$ is upward directed and

$$ \begin{align*} (\boldsymbol{\textsf{ST}}, \leq_K)\le_{GT}(\mathbb H,\leq^\circ)\le_{GT}(\omega^\omega,\le^*). \end{align*} $$

To define $(\mathbb H,\leq ^\circ )$ , we need the following.

First, we define a set $\Phi \subseteq \ \mathbb Q_+^{<\omega }\times \omega ^{<\omega }$ by $(s,p)\in \Phi $ if and only if ( $*$ ) there exist $l_s,k_s\in \omega $ such that $(s,p)$ satisfies the following (see Figure 2):

1. (i) $s:l_s\to \mathbb Q_+$ and $s(j)\ge s(j+1)$ for all $j<l_s -1$ ,

2. (ii) $0=p(1)< p(2)< \cdots < p(k_s)=l_s-1$ ,

3. (iii) $ u_s\big (\big [p(i),p(i+1)\big )\big )\ge 1$ for each $0<i<k_s$ , and

4. (iv) $s(j)\le \frac {1}{i}$ for each $j\ge p(i)$ and $0<i< k_s$ .

For any $(s,p)\in \Phi $ , define a subset of $\Phi $ by

$$ \begin{align*} \Phi(s,p)=\left\{(t,q)\in\Phi : s \sqsubseteq t, p \sqsubseteq q ~ \mathrm{and} \ k_t=k_s+1\right\}. \end{align*} $$

Define an order $\unlhd _{(s,p)}$ on $\Phi (s,p)$ as follows: for each $(t_1,q_1), (t_2,q_2) \in \Phi (s,p)$ , $(t_1,q_1)\unlhd _{(s,p)}(t_2,q_2)$ if and only if there exists a map

$$ \begin{align*} \pi:\big[q_2(k_s),q_2(k_s+1)\big)\to\big[q_1(k_s),q_1(k_s+1)\big) \end{align*} $$

such that

$$ \begin{align*} u_{t_2}(\pi^{-1}(i))\le t_1(i) \text{ for each } i\in \big[q_1(k_s),q_1(k_s+1)\big). \end{align*} $$

It is easy to see that $\unlhd _{(s,p)}$ is transitive.

Lemma 5.1. $(\Phi (s,p),\unlhd _{(s,p)})$ is upward directed for all $(s,p)\in \Phi $ .

Proof Fix $(t_0,q_0),(t_{1},q_{1})\in \Phi (s,p)$ . Define $(t,q)$ as follows. Define $I_0 = \big [q_0(k_s),q_0(k_s+1)\big )$ and $I_1 = \big [q_1(k_s),q_1(k_s+1)\big )$ and $I=I_0\times I_1$ .

Figure 2 An element $(s,p)$ of set $\Phi$ .

Fix $i\in \{0,1\}$ . Denote $N_i:= u_{t_i}\big (I_i)\ge 1.$ For every $(j_0,j_1)\in I$ , define t by

$$ \begin{align*} t\big((j_0,j_1)\big)=\frac{t_0(j_0)\cdot t_1(j_1)}{N_0\cdot N_1}. \end{align*} $$

Let $M=|I_1|\cdot |I_2|$ . We can find a bijection e from I to $[p(k_s)+1,p(k_s)+M]$ such that

$$ \begin{align*} t(e^{-1}(j))\ge t(e^{-1}(j+1)) \text{ for all } j\in[p(k_s)+1,p(k_s)+M]. \end{align*} $$

Let $q(k_s)=p(k_s)$ and $q(k_s+1)=p(k_s)+M + 1$ . Then

$$ \begin{align*} I=e^{-1}(\big[q(k_s),q(k_s+1)\big)). \end{align*} $$

Without loss of generality, we can regard I as $\big [q(k_s),q(k_s+1)\big )$ .

We will show that $(t,q)\in \Phi (s,p)$ and $(t_i,q_i)\unlhd _{(s,p)} (t,q)$ for $i\in \{0,1\}$ .

(1) $(t,q)\in \Phi (s,p)$ :

Use

$$ \begin{align*} u_t(I)=\displaystyle\sum\limits_{(j_0,j_1)\in I} \frac{t_0(j_0)\cdot t_1(j_1)}{N_0\cdot N_1}= 1 \end{align*} $$

and

$$ \begin{align*} t\big((j_0,j_1)\big)=\frac{t_0(j_0)\cdot t_1(j_1)}{N_0\cdot N_1} \le \frac{1}{N_0\cdot N_1}\cdot\frac{1}{k_s^2}\le\frac{1}{k_s} \text{ for all } (j_0,j_1)\in I. \end{align*} $$

(2) $(t_i,q_i)\unlhd _{(s,p)} (t,q)$ for $i\in \{0,1\}$ :

Let $\pi _0$ and $\pi _1$ be the projection map onto the first coordinate and second coordinate, respectively. For any $j\in I_0$ , we have that

$$ \begin{align*} \pi^{-1}_{0}(j)=\left\{(j,j_{1}):j_{1}\in I_1\right\} \end{align*} $$

and

$$ \begin{align*} u_t\left(\pi_{0}^{-1}(j)\right)= \frac{t_{0}(j)}{N_{0}}\cdot\displaystyle\sum\limits_{j_{1}\in I_1}\frac{t_1(j_1)}{N_1} = \frac{t_{0}(j)}{N_{0}}\le t_{0}(j). \end{align*} $$

Similarly, we have $u_t\left (\pi _{1}^{-1}(j)\right )\le t_{1}(j)$ .

For any $(s,p)\in \Phi $ , define a cofinal subset $\widetilde {\Phi }(s,p)$ of $\Phi (s,p)$ such that ( $\widetilde {\Phi }(s,p)$ , $\unlhd _{(s,p)}$ ) is an increasing chain. We define $\widetilde {\Phi }(s,p)$ as follows. Enumerate $\Phi (s,p)=\{(s_n,p_n),n\in \omega \}$ . Let $(t_0,q_0)=(s_0,p_0)$ . Suppose we have already constructed $\{(t_i,q_i):i<n\}$ . Then we take $(t_n,q_n)$ such that $(t_{n-1},q_{n-1})\unlhd _{(s,p)}(t_n,q_n)$ and $(s_n,p_n)\unlhd _{(s,p)}(t_n,q_n)$ by Lemma 5.1. Define

$$ \begin{align*} \widetilde{\Phi}(s,p)=\{(t_n,q_n):n<\omega\}. \end{align*} $$

Define

$$ \begin{align*} \mathbb H=\left\{h\in\Phi^{\Phi}: h((s,p))\in\widetilde{\Phi}(s,p)~\mathrm{for\ all}\ (s,p)\in \Phi \right\}. \end{align*} $$

Define the order $\leq ^\circ $ on $\mathbb H$ as follows: for each $h, h' \in \mathbb H$ , $h\leq ^\circ h'$ if and only if $h((s,p))\unlhd _{(s,p)} h'((s,p))$ for all but finitely many $(s,p)\in \Phi $ . It is easy to see that $(\mathbb H,\leq ^\circ )$ is upward directed by the definition of $\mathbb H$ .

Next, we prove the following:

Lemma 5.2. $(\mathbb H, \leq ^\circ )\leq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Enumerate

$$\begin{align*}\Phi=\{(s_i,p_i),i\in\omega\}.\end{align*}$$

Enumerate

$$\begin{align*}\widetilde{\Phi}(s_i,p_i)=\left\{\left(t^{(s_i,p_i)}_j,q^{(s_i,p_i)}_j\right):j\in\omega\right\}\end{align*}$$

in such way that $(t^{(s_i,p_i)}_j,q^{(s_i,p_i)}_j)\unlhd _{(s_i,p_i)}(t^{(s_i,p_i)}_k,q^{(s_i,p_i)}_k)$ for all $j<k$ .

Define $\rho _+:\omega ^\omega \to \mathbb H$ as follows. For every $g\in \omega ^\omega $ and $i\in \omega $ , let

$$ \begin{align*} \rho_+(g)((s_i,p_i))=\Big(t^{(s_i,p_i)}_{g(i)},q^{(s_i,p_i)}_{g(i)}\Big). \end{align*} $$

Define $\rho _-:\mathbb H\to \omega ^\omega $ as follows. For every $h\in \mathbb H$ and $i\in \omega $ , let

$$ \begin{align*} h((s_i,p_i))=\Big(t^{(s_i,p_i)}_{\rho_-(h)(i)},q^{(s_i,p_i)}_{\rho_-(h)(i)}\Big) \text{ for all } i\in\omega. \end{align*} $$

We claim that

$$ \begin{align*} \forall h\in \mathbb H~\forall g\in\omega^\omega(\rho_-(h)\le^* g\Rightarrow h\leq^\circ \rho_+(g)). \end{align*} $$

Suppose $h\in \mathbb H$ , $g\in \omega ^\omega $ , and $\rho _-(h)\le ^*g$ . There is $n\in \omega $ such that for each $i\ge n$ we have $\rho _-(h)(i)\le g(i)$ . Then $h((s_i,p_i))\unlhd _{(s_i,p_i)} \rho _+(g)((s_i,p_i))$ for all but finitely many $i\in \omega $ , i.e., $h\leq ^\circ \rho _+(g)$ .

Now, we prove the following:

Lemma 5.3. $(\boldsymbol{\textsf{ST}}, \leq _K) \leq _{GT} (\mathbb H, \leq ^\circ )$ .

Proof Define $\rho _+:\mathbb H\to \boldsymbol{\textsf{ST}}$ as follows. Define $q_{-1}\in \omega ^1$ by $q_{-1}(1)=0$ and $t_{-1}(0)=1$ . For each $h\in \mathbb H$ , let $(t_0^h,q_0^h)=h((t_{-1},q_{-1}))$ and $(t^h_{n+1},q^h_{n+1})=h((t^h_n,q^h_n))$ for all $n\in \omega $ . Let $g=\bigcup \limits _{n\in \omega } t^h_n$ and $\rho _+(h)=\mathcal I_g$ . Since $q_{-1}=(q_{-1}(1))$ , we have that $q_0^h=(q_0^h(1),q_0^h(2))$ , and

$$ \begin{align*} q_n^h=(q_n^h(1),q_n^h(2),\ldots,q_n^h(n+2)) \text{ for } n\in\omega \text{, i.e., } k_{t_n^h}=n+2 \end{align*} $$

(see ( $*$ ) at the beginning of Section 4 for the definition of $k_{t_n^h}$ ).

Define $\rho _-:\boldsymbol{\textsf{ST}}\to \mathbb H$ as follows. For $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ , take $0=m_1<m_2<\cdots <m_i<\cdots $ such that for each $i>0$ ,

$$ \begin{align*} u_f([m_i,m_{i+1}))\ge 1 \text{ and } f(j)\le \frac{1}{i} \text{ for every } j\ge m_i. \end{align*} $$

For each $n\ge 1$ , let $p(n)=m_n$ , $p_n=(p(1),\ldots ,p(n))$ , and $s_n=f\big |_{[0,p(n))}$ . For every $(t,q)\in \Phi $ with $q=(q(1),\ldots ,q(k_t))$ , let

$$ \begin{align*} p^{\prime}_t & =\big(q(1),\ldots,q(k_t),q(k_t)+p(k_t+1)-p(k_t)\big) \\ & =\big(p^{\prime}_t(1),\ldots,p^{\prime}_t(k_t),p^{\prime}_t(k_t+1)\big). \end{align*} $$

We have that:

• • $p^{\prime }_t(j)=q(j)$ for $1\le j\le k_t$ ,

• • $p^{\prime }_t(k_t+1)=q(k_t)+p(k_t+1)-p(k_t)$ , and

• • $s^{\prime }_t=t^\frown f\big |_{[p(k_t),p(k_t+1))}$ .

Then $(s^{\prime }_t,p^{\prime }_t)\in \Phi (t,q)$ (see Figure 3). Take $(s^*_t,p^*_t)\in \widetilde {\Phi }(t,q)$ such that $(s^{\prime }_t,p^{\prime }_t)\unlhd _{(t,q)}(s^*_t,p^*_t)$ . Define $\rho _- (\mathcal I_f)((t,q))=(s^*_t,p^*_t)$ .

Figure 3 The definition of $(s'_t, p'_t)$ in the proof of Lemma 5.3.

We claim that

$$ \begin{align*} \forall\mathcal I_f\in\boldsymbol{\textsf{ST}}~\forall h\in \mathbb H(\rho_-(\mathcal I_f)\leq^\circ h\Rightarrow\mathcal I_f\le_K \rho_+(h)). \end{align*} $$

Suppose $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ , $h\in \mathbb H$ , and $\rho _-(\mathcal I_f)\leq ^\circ h$ . Let $\{s_n:n\in \omega \}$ and p be like in the definition of $\rho _-(\mathcal I_f)$ . Then we have that

$$ \begin{align*} \rho_-(\mathcal I_f)((t,q))\unlhd_{(t,q)}h((t,q)) \end{align*} $$

for all but finitely many $(t,q)\in \Phi $ . By the definition of $\rho _+$ , there exists $\{(t_n^h,q_n^h):n\in \omega \}$ . Then there is N such that for $n>N$ , we have that

$$\begin{align*}\rho_-(\mathcal I_f)((t_n^h,q_n^h))\unlhd_{(t_n^h,q_n^h)}h((t_n^h,q_n^h))=(t_{n+1}^h,q_{n+1}^h).\end{align*}$$

Since $\rho _-(\mathcal I_f)((t_n^h,q_n^h))=(s_{t_n^h}^*,p_{t_n^h}^*)$ , we have that

$$ \begin{align*} (s^{\prime}_{t_n^h},p^{\prime}_{t_n^h})\unlhd_{(t_n^h,q_n^h)}(s_{t_n^h}^*,p_{t_n^h}^*)\unlhd_{(t_n^h,q_n^h)}(t_{n+1}^h,q_{n+1}^h). \end{align*} $$

Then for each $n>N$ , there exists a map

$$\begin{align*}{\pi'}_n:[q_{n+1}^h(n+2),q_{n+1}^h(n+3))\to[p^{\prime}_{t_n^h}(n+2),p^{\prime}_{t_n^h}(n+3))\end{align*}$$

such that

$$ \begin{align*} u_{t_{n+1}^h}({\pi'}_n^{-1}(i))\le s^{\prime}_{t_n^h}(i) \text{ for all } i\in [p^{\prime}_{t_n^h}(n+2),p^{\prime}_{t_n^h}(n+3)). \end{align*} $$

Define $\sigma _n:[p^{\prime }_{t_n^h}(n+2),p^{\prime }_{t_n^h}(n+3))\to [p(n+2),p(n+3))$ by

$$ \begin{align*} \sigma_n(j)=j-p^{\prime}_{t_n^h}(n+2)+p(n+2) \text{ for all } j \in[p^{\prime}_{t_n^h}(n+2),p^{\prime}_{t_n^h}(n+3)). \end{align*} $$

Define $\pi _n=\sigma _n\circ {\pi '}_n$ for each $n>N$ . We have that

$$ \begin{align*} u_{t_{n+1}^h}(\pi_n^{-1}(i))\le s_{n+3}(i) \text{ for each } i\in [p(n+2),p(n+3)). \end{align*} $$

There exist $\pi _{-1}:[0,q_0^h(2))\to [0,p(2))$ and $c_{-1}>0$ such that

$$ \begin{align*} u_{t_0^h}(\pi_{-1}^{-1}(i))\le c_{-1}\cdot s_2(i) \text{ for each } i \in[0,p(2)). \end{align*} $$

For every $m\le N$ , there exist $\pi _{m}:[q_m^h(m+2),q_m^h(m+3))\to [p(m+2),p(m+3))$ and $c_{m}>0$ such that

$$ \begin{align*} u_{t_{m+1}^h}(\pi_{m}^{-1}(i))\le c_{m}\cdot s_{m+3}(i) \text{ for each } i \in[p(m+2),p(m+3)). \end{align*} $$

Let $\pi =\bigcup \limits _{n\in \omega \cup \{-1\}}\pi _n$ and $C=\max \{1,c_{-1},c_{0},\ldots ,c_{N}\}$ . Then we have that

$$ \begin{align*} u_g(\pi^{-1}(i))\le C\cdot f(i) \text{ for } i\in\omega\ \mathrm{(see\ Figure\ 4)}.\end{align*} $$

Then $\pi $ witnesses $\mathcal I_f \le _K \mathcal I_g=\rho _+(h)$ by Theorem 4.1(5).

Figure 4 $\pi$ witnesses $\mathcal I_f \le_K \mathcal I_g$ in the proof of Lemma 5.3.

Combining Lemmas 5.2 and 5.3 we have:

Lemma 5.4. $(\boldsymbol{\textsf{ST}}, \leq _K)\leq _{GT}(\omega ^\omega ,\leq ^*)$ .

The proof of the other side is short.

Lemma 5.5. $(\boldsymbol{\textsf{ST}}, \leq _K)\geq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Define $\rho _+:\boldsymbol{\textsf{ST}} \to \omega ^\omega $ as follows. For each $\mathcal I_g\in \boldsymbol{\textsf{ST}}$ and $n\ge 1$ , there exists $\rho _+(\mathcal I_g)$ such that

$$ \begin{align*} u_g\big(\big[\rho_+(\mathcal I_g)(n-1), \rho_+(\mathcal I_g)(n)\big)\big)\ge n^2. \end{align*} $$

Define $\rho _-: \omega ^\omega \to \boldsymbol{\textsf{ST}}$ as follows. For each $r\in \omega ^\omega $ , take a partition $(A_n^r:n\in \omega )$ of $\omega $ into successive finite intervals such that $|A^r_0|\ge 1$ ,

$$ \begin{align*} \text{min}(A^r_n)\ge r(n) \text{, and } |A^r_n|\ge \max\{n, |A^r_{n-1}|\} \text{ for each } n\in \omega\setminus \{0\}. \end{align*} $$

Then define $f_r:\omega \to \mathbb {Q}_+ $ by

$$ \begin{align*} f_r(k)=1/|A^r_n| \text{ where } n \text{ such that } k\in A^r_n. \end{align*} $$

Let $\rho _-(r)=\mathcal I_{f_r}$ .

We claim that

$$ \begin{align*} \forall r\in\omega^\omega~\forall\mathcal I_g\in\boldsymbol{\textsf{ST}} (\rho_-(r)\leq_K \mathcal I_g\Rightarrow r\le^* \rho_+(\mathcal I_g)). \end{align*} $$

Take arbitrary $r\in \omega ^\omega $ and $\mathcal I_g\in \boldsymbol{\textsf{ST}}$ such that $\mathcal I_{f_r}=\rho _-(r)\le _K \mathcal I_g$ . By Theorem 4.1(5), there exist a map $p:\omega \to \omega $ and $C>0$ such that

$$ \begin{align*} u_g(p^{-1}(i))\le C\cdot f_r(i) \text{ for all } i\in\omega. \end{align*} $$

By the Remark (above Figure 1), we may assume that p is a nondecreasing surjection and $p(i)\le i$ . Thus $\max p^{-1}(i)\ge i$ for all $i\in \omega $ . Then for large enough n, there is $j_n$ such that

$$ \begin{align*} u_g([0,j_n]) & =u_g\Big(p^{-1}\Big(\bigcup\limits_{0\le m\le n}A^r_m\Big)\Big)\le C\cdot u_{f_r}\Big(\bigcup\limits_{0\le m\le n}A^r_m\Big)= n\cdot C \le n^2 \\ & \le u_g\left(\big[\rho_+(\mathcal I_g)(n-1), \rho_+(\mathcal I_g)(n)\big)\right)\le u_g\left(\big[0, \rho_+(\mathcal I_g)(n)\big)\right). \end{align*} $$

Thus $j_n\le \rho _+(\mathcal I_g)(n)$ for large enough n. Then for large enough n we have that

$$ \begin{align*} r(n)\le\max\Big(\bigcup\limits_{0\le m\le n}A^r_m\Big)\le\max p^{-1}\Big(\bigcup\limits_{0\le m\le n}A^r_m\Big)= j_n. \end{align*} $$

Therefore we have that $r(n)\le j_n\le \rho _+(\mathcal I_g)(n)$ for large enough n.

Theorem 5.6. $(\boldsymbol{\textsf{ST}}, \leq _K)\simeq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Combine Lemma 5.4 with Lemma 5.5.

6 The structure of $(\boldsymbol{\textsf{ST}},\ge _K)$ in the sense of Galois–Tukey connection

In this section we prove that $(\boldsymbol{\textsf{ST}}, \geq _K)\simeq _{GT}(\omega ^\omega ,\leq ^*)$ . First, we prove the following:

Lemma 6.1. $(\boldsymbol{\textsf{ST}}, \geq _K)\leq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Let $\omega ^{\uparrow \omega }$ be all strictly increasing functions from $\omega $ to $\omega \setminus \{0\}$ . It suffices to show that $(\boldsymbol{\textsf{ST}}, \geq _K)\leq _{GT}\left (\omega ^{\uparrow \omega },\leq ^*\right )$ because $\left (\omega ^{\uparrow \omega },\leq ^*\right )\leq _{GT}(\omega ^\omega ,\leq ^*)$ .

Define $\rho _-: \boldsymbol{\textsf{ST}} \to \omega ^{\uparrow \omega }$ as follows. For each $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ , define $\rho _-(\mathcal I_f)\in \omega ^{\uparrow \omega }$ by $\rho _-(\mathcal I_f)(0) = 1$ and

$$ \begin{align*} \rho_-(\mathcal I_f)(k)=\min\left\{n>\rho_-(\mathcal I_f)(k-1):\forall m\geq n \left(f(m)\leq \frac {1}{k}\right)\right\} \end{align*} $$

for all $k\ge 1$ .

Define $\rho _+: \omega ^{\uparrow \omega }\to \boldsymbol{\textsf{ST}} $ as follows. For each $x\in \omega ^{\uparrow \omega }$ , define $F:\omega ^{\uparrow \omega } \to \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ by $F(x)(k)=1$ for all $0\leq k<x(1),$ and

$$ \begin{align*} F(x)(k)=\frac {1} {n} \text{ where } n \text{ is such that } k\in [x(n),x(n+1)). \end{align*} $$

Then $\mathcal I_{F(x)}$ is tall for each $x\in \omega ^{\uparrow \omega } $ . Let $\rho _+(x)=\mathcal I_{F(x)}$ .

We claim that

$$ \begin{align*} \forall \mathcal I_f\in \boldsymbol{\textsf{ST}}~ \forall x\in \omega^{\uparrow \omega}\left(\rho_-(\mathcal I_f)\leq^* x\Rightarrow \mathcal I_f\geq_K \rho_{+}(x)\right). \end{align*} $$

Let $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ and $x\in \omega ^{\uparrow \omega }$ such that $\rho _-(\mathcal I_f)\leq ^* x$ . We will show that $f\leq ^* F(x)$ and then $\mathbf {id}: \omega \to \omega $ will be a witness for $\mathcal I_f\geq _K \mathcal I_{F(x)}$ . To see that $f\leq ^* F(x)$ , take $N>0$ such that

$$ \begin{align*} \rho_-(\mathcal I_f)(n)\leq x(n) \text{ for each } n\geq N. \end{align*} $$

Then for each $n\geq N$ and $k\in [x(n),x(n+1))$ we have $k\ge \rho _-(\mathcal I_f)(n)$ . By the definition of $\rho _-(\mathcal I_f)$ , we have $f(k)\leq \frac {1}{n}=F(x)(k)$ . It follows that $f\leq ^* F(x)$ .

Lemma 6.2. $(\boldsymbol{\textsf{ST}}, \geq _K)\geq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Define $\rho _-: \omega ^{\omega } \to \boldsymbol{\textsf{ST}}$ as follows. For each $x\in \omega ^{\omega } $ , take a partition $\{A^x_n: n\in \omega \setminus \{0\}\}$ of $\omega $ into successive finite intervals such that for all $n>0$ :

1. (1) $\min A^x_n\geq \min \{x(n), n\}$ and

2. (2) $|A^x_n|\geq n^2 (x(n)+1)$ .

Then define $g_x \in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ by

$$ \begin{align*} g_x(k)=\frac 1{n} \text{ where } n \text{ is such that } k\in A^x_n. \end{align*} $$

Let $\rho _-(x)=\mathcal I_{g_x}$ . It follows that $\rho _-(x)$ is tall for all $x\in \omega ^\omega $ .

Define $ \rho _+: \boldsymbol{\textsf{ST}}\to \omega ^{\omega }$ as follows. Suppose $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ . For each $n>0$ , define $\rho _+(\mathcal I_f)$ by $\rho _+(\mathcal I_f)(0)=0$ and $\rho _+(\mathcal I_f)(n)=$

$$ \begin{align*} \min\left\{m \ge n+1: m\geq u_f\big(\big[0,\rho_+(\mathcal I_f)(n-1)\big]\big) ~\&~ \forall k\geq m\left(f(k)\leq \frac{1}{(n+1)^2}\right) \right\}. \end{align*} $$

We claim that

$$ \begin{align*} \forall \mathcal I_f\in \boldsymbol{\textsf{ST}}~ \forall x\in \omega^{ \omega}(\rho_-(x)\geq_K \mathcal I_f\Rightarrow x\leq^* \rho_+(\mathcal I_f)). \end{align*} $$

Let $\mathcal I_f\in \boldsymbol{\textsf{ST}}$ and $x\in \omega ^{\omega }$ such that $x\not \leq ^* \rho _+(\mathcal I_f)$ . Let $\rho _-(x)=\mathcal I_{g_x}$ . We will show for each $M>0$ , there are $l>M$ , $k_1>k_0\ge M$ such that:

1. (3) $u_{g_x}([k_0,k_1])>M\cdot u_f([0,l])$ and

2. (4) $g_x(k_1)>M\cdot f(l)$ .

Then, $\rho _-(x)\not \geq _K \mathcal I_f$ follows from Theorem 4.1. To prove (3) and (4), fix $M>0$ and let $n_0>M$ be such that $x(n_0)>\rho _+(\mathcal I_f)(n_0)$ . Define $l=\rho _+(\mathcal I_f)(n_0-1)$ and $k_0<k_1$ such that $[k_0, k_1]=A^x_{n_0}$ . It follows that $l>M$ , $k_1>k_0\ge M$ and

$$ \begin{align*} u_{g_x}([k_0,k_1])\geq n_0\cdot (x(n_0)+1)>n_0 \cdot x(n_0)> M\cdot u_f([0,l]). \end{align*} $$

Thus (3) holds. By the definition of l, we have that $f(l)\leq \frac {1}{n_0^2}$ and

$$ \begin{align*} g_x(k_1)=\frac{1}{n_0}=n_0\cdot\frac{1}{n_0^2}>M\cdot f(l). \end{align*} $$

Thus (4) holds.

Theorem 6.3. $(\boldsymbol{\textsf{ST}}, \geq _K)\simeq _{GT}(\omega ^\omega ,\leq ^*)$ .

Proof Use Lemmas 6.1 and 6.2.

7 $\simeq _K$ on $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ is Borel bireducible to ${l_\infty }$

In this section we will prove that $l_\infty $ is Borel bireducible to $\simeq _K$ on $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ .

Definition 7.1.

1. (1) Let $C=\{(A_n)\in \mathcal P(\omega )^\omega :\forall n(A_n\subseteq A_{n+1})\}$ and for each $(A_n),(B_n)\in C$ ,

   $$\begin{align*}(A_n)H(B_n)\Longleftrightarrow\exists n\forall m(A_m\subseteq B_{n+m} \land B_m\subseteq A_{n+m}).\end{align*}$$

2. (2) Let $X_0=\prod \limits _{n<\omega }n$ , where $n=\{0,1,\ldots ,n-1\}$ . For each $\alpha ,\beta \in X_0$ , define

   $$\begin{align*}\alpha E_{K_\sigma}\beta\Longleftrightarrow\exists n \forall m(|\alpha(m)-\beta(m)|\le n).\end{align*}$$

It is proved in [6, Proposition 19] that $H\simeq _B l_\infty \simeq _B E_{K_\sigma }$ , so it suffices to prove that $\simeq _K\le _B H$ and $E_{K_\sigma }\le _B \simeq _K$ .

7.1 The proof of $\simeq _K\le _B H$

This will be proved in Corollary 7.10. The proof consists of two steps. We first show that the so-called decomposable equivalence relations are all Borel reducible to H (Theorem 7.5). Then we prove that $\simeq _K$ is decomposable (Theorem 7.9). Before this, we need some preparations.

Lemma 7.2. $\simeq _K$ is an $F_\sigma $ subset of $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}^2$ .

Proof Denote $\preceq _K=\{(f,g)\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}^2:\mathcal I_f\le _K\mathcal I_g\}$ . By Theorem 4.1(6), $\preceq _K=$

$$\begin{align*}\{(f,g):\kern-1pt \exists n\in\omega\kern-1pt \setminus\kern-1pt \{0\},\forall k\kern-1pt \in\kern-1pt \omega,\forall l\in\omega\big[u_g([0,k])\kern-1pt \le\kern-1pt n\cdot u_f([0,l])~\mathrm{or}\ g(k)\kern-1pt \le\kern-1pt n\cdot f(l)\big]\}\end{align*}$$

$$ \begin{align*} =\bigcup\limits_{n\in\omega\setminus\{0\}}\bigcap\limits_{k\in\omega}\bigcap\limits_{l\in\omega}\big[\{(f,g):u_g([0,k])\le n\cdot u_f([0,l])\}\cup\{(f,g):g(k)\le n\cdot f(l)\}\big].\ \end{align*} $$

For each $n>1$ , let

$$ \begin{align*} F_n=\bigcap\limits_{k\in\omega}\bigcap\limits_{l\in\omega}\big[\{(f,g):u_g([0,k])\le n\cdot u_f([0,l])\}\cup\{(f,g):g(k)\le n\cdot f(l)\}\big]. \end{align*} $$

Then $F_n$ is closed. Thus $\preceq _K$ is $F_\sigma $ .

Denote $\succeq _K=\{(f,g):\mathcal I_f\ge _K\mathcal I_g\}$ . Similarly we can prove that $\succeq _K$ is $F_\sigma $ . It follows that $\simeq _K=\preceq _K\cap \succeq _K$ is $F_\sigma $ .

We need the following characterization of $\simeq _K$ .

Lemma 7.3. Let $f,g\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ . Then $f \simeq _K g$ if and only if there exists $n>0$ such that for each $k\in \omega $ we have that

$$ \begin{align*} \frac{f(l_k)}{n}\le g(k)\le n\cdot f(l^{\prime}_k), \end{align*} $$

where $l_k,l^{\prime }_k$ are such that

$$\begin{align*}\frac{u_f([0,l_k-1]])}{n}\le u_g([0,k])< \frac{u_f([0,l_k])}{n}\end{align*}$$

and

$$\begin{align*}n\cdot u_f([0,l^{\prime}_k])<u_g([0,k])\le n\cdot u_f([0,l^{\prime}_k+1]).\end{align*}$$

Proof ( $\Rightarrow $ ): Recall that $f \simeq _K g$ means $\mathcal I_f \le _K \mathcal I_g$ and $\mathcal I_g \le _K \mathcal I_f$ . By Theorem 4.1(6), there exists $M_1$ such that for all k and $l'$ we have that

$$ \begin{align*} u_g([0,k])>M_1\cdot u_f([0,l']) \Rightarrow g(k)\le M_1\cdot f(l'). \end{align*} $$

For the same reason, there exists $M_2$ such that for all k and l we have that

$$ \begin{align*} u_f([0,l])>M_2\cdot u_g([0,k]) \Rightarrow f(l)\le M_2\cdot g(k). \end{align*} $$

Let $n=\max \{M_1, M_2\}$ . Then we have that

$$ \begin{align*} u_g([0,k])>n\cdot u_f([0,l'])\ge M_1\cdot u_f([0,l']) \Rightarrow g(k)\le M_1\cdot f(l')\le n\cdot f(l') \end{align*} $$

and

$$ \begin{align*} u_f([0,l])>n\cdot u_g([0,k])\ge M_2\cdot u_g([0,k]) \Rightarrow f(l)\le M_2\cdot g(k)\le n\cdot g(k). \end{align*} $$

Define

$$ \begin{align*} l_k=\min\left\{l\in\omega:u_g([0,k])< \frac{u_f([0,l])}{n}\right\} \end{align*} $$

and

$$ \begin{align*} l_k'=\max\left\{l'\in\omega:u_g([0,k])>n\cdot u_f([0,l'])\right\}. \end{align*} $$

We have that

$$\begin{align*}n\cdot u_f([0,l^{\prime}_k])<u_g([0,k])\le n\cdot u_f([0,l^{\prime}_k+1])\end{align*}$$

and

$$\begin{align*}\frac{u_f([0,l_k-1]])}{n}\le u_g([0,k])< \frac{u_f([0,l_k])}{n}.\end{align*}$$

It follows that

$$\begin{align*}\frac{f(l_k)}{n}\le g(k)\le n\cdot f(l^{\prime}_k).\end{align*}$$

( $\Leftarrow $ ): For each $k\in \omega $ , we have $l_k=\min \{l\in \omega :u_g([0,k])< \frac {u_f([0,l])}{n}\}$ . For each $l\in \omega $ we have that

$$ \begin{align*} u_g([0,k])< \frac{u_f([0,l])}{n} \Rightarrow l\ge l_k. \end{align*} $$

For each $l\ge l_k$ we have that

$$\begin{align*}\frac{f(l)}{n}\le \frac{f(l_k)}{n}\le g(k).\end{align*}$$

It follows that for each $k\in \omega $

$$\begin{align*}u_f([0,l])>n\cdot u_g([0,k])\Rightarrow f(l)\le n\cdot g(k).\end{align*}$$

By Theorem 4.1(6), we have $\mathcal I_g \le _K \mathcal I_f$ .

$\mathcal I_f \le _K \mathcal I_g$ can be proved in a similar way.

Now we define decomposable equivalence relations.

Definition 7.4. Let F be a $F_\sigma $ equivalence relation on Borel space X. We call F is decomposable on X if there is a sequence $\{F_n:n\in \omega \}$ of closed subsets of $X^2$ such that:

1. (1) For each $n<\omega $ , $F_n\subseteq F_{n+1}$ and $F_n\circ F_n\subseteq F_{n+1}$ (i.e., $xF_ny\land yF_nz\Rightarrow xF_{n+1}z$ ).

2. (2) $F=\bigcup _{n\in \omega } F_n$ .

3. (3) $[U]_n=\{x\in X:\exists z\in U(zF_nx)\}$ is Borel for each open subset U of X and $n\in \omega $ .

Theorem 7.5. Let F be an $F_\sigma $ equivalence relation such that F is decomposable on Borel space X. Then $F\le _B H$ .

Proof Let $\{F_n:n<\omega \}$ be a sequence which witnesses that F is decomposable. Fix a basis $\{U_n:n\in \omega \}$ of X. For each $n\in \omega $ , define a function $f_n:X\to \mathcal P(\omega )$ by

$$ \begin{align*} f_n(x)=\{k\in\omega:\exists z\in U_k (zF_nx)\}. \end{align*} $$

By (3) of Definition 7.4, for each $m\in \omega $ we have that

$$\begin{align*}f_n^{-1}(\{A\subseteq\omega:m\in A\})=[U_m]_n\end{align*}$$

is Borel. It follows that $f_n$ is a Borel function for each $n\in \omega $ . By (1) of Definition 7.4, we have that

$$ \begin{align*} f_n(x)\subseteq f_{n+1}(x) \text{ for each } n\in\omega \text{ and } x\in X. \end{align*} $$

We prove that $\Phi :x \mapsto (f_n(x))$ is a Borel reduction from F to H. $\Phi $ is a Borel map by the following: For any open subset $\prod \limits _{n\in \omega }\mathcal U_n$ of C, we have

$$ \begin{align*} \Phi^{-1}\left(\prod\limits_{n\in\omega}\mathcal U_n\right)=\bigcap\limits_{n\in\omega}f_n^{-1}(\mathcal U_n). \end{align*} $$

It follows that $\Phi $ is Borel by $f_n$ being Borel for all $n\in \omega $ .

Then we show that $\Phi $ is a reduction from F to H. Let $x,y\in X$ such that $xFy$ . Then there exists $n\in \omega $ such that $xF_ny$ . Therefore, for any $z\in X$ such that $zF_mx$ for some $m\in \omega $ , we have that

$$\begin{align*}zF_{\max\{n,m\}+1}y.\end{align*}$$

It follows that $f_m(x)\subseteq f_{n+1+m}(y)$ for all $m\in \omega $ . Similarly, there exists $n'$ such that $f_m(y)\subseteq f_{n'+1+m}(x)$ for all $m\in \omega $ . Let $N=\max \{n+1,n'+1\}$ . We have that

$$ \begin{align*} \forall m\in\omega(f_m(x)\subseteq f_{N+m}(y) ~\land~ f_m(y)\subseteq f_{N+m}(x)). \end{align*} $$

Conversely, let $x,y\in X$ such that $(f_n(x))H(f_n(y))$ . Then there exists $n\in \omega $ such that

$$ \begin{align*} f_m(x)\subseteq f_{n+m}(y) \text{ for all } m\in\omega. \end{align*} $$

Fix n as above. For each $m\in \omega $ , define $F_m^x=\{z: zF_mx\}$ . Then for each $k\in \omega $ we have that

$$ \begin{align*} U_k\cap F_m^x\neq\emptyset\Longrightarrow k\in f_m(x)\Longrightarrow k\in f_{n+m}(y)\Longrightarrow U_k\cap F_{n+m}^y\neq\emptyset. \end{align*} $$

Since $F_{n+m}^y$ is closed, we have $F_m^x\subseteq F_{n+m}^y$ . Take m large enough such that $xF_mx$ , then we have that

$$ \begin{align*} xF_mx\Rightarrow x\in F_m^x\Rightarrow x\in F_{n+m}^y\Rightarrow xF_{n+m}y. \end{align*} $$

It follows that $xFy$ .

Next, we will show that $\simeq _K$ is decomposable. We need some observations.

Definition 7.6. For each $n\in \omega $ , define $R_n$ , $S_n$ , $E_n$ , and $F_n$ on $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ as follows:

1. (1) $fR_ng$ if and only if there exists an interval-to-one map $p:\omega \to \omega $ such that $u_g\left (p^{-1}(i)\right )\le n\cdot f(i)$ for all $i\in \omega $ .

2. (2) $fS_ng$ if and only if for all $k,l\in \omega $ , $u_g([0,k])>n\cdot u_f([0,l])$ implies $g(k)\le n\cdot f(l)$ .

3. (3) $fE_ng$ if and only if $fR_ng$ and $gR_nf$ .

4. (4) $fF_ng$ if and only if $fS_ng$ and $gS_nf$ .

Lemma 7.7. Let $f,g,h\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ . For each pair $n\le m$ we have follows $:$

1. (1) $fR_ng \Rightarrow fR_mg$ ; $fS_ng \Rightarrow fS_mg$ ; $fE_ng \Rightarrow fE_mg$ ; $fF_ng \Rightarrow fF_mg$ .

2. (2) $fR_ng \Rightarrow fS_ng$ ; $fS_ng \Rightarrow fR_{2n}g$ .

3. (3) $fR_ng\land gR_nh \Rightarrow fR_{n^2}h$ ; $fE_ng\land gE_nh \Rightarrow fE_{n^2}h$ .

4. (4) $fS_ng\land gS_nh \Rightarrow fS_{4n^2}h$ ; $fF_ng\land gF_nh \Rightarrow fF_{4n^2}h$ .

Proof (1): The proof is obvious.

(2): Use the proof of Theorem 4.1 $(5)\Rightarrow (6)$ and $(6)\Rightarrow (5)$ .

(3): Let $f,g,h\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ such that $fR_ng$ and $gR_nh$ . Then there exist $p_1$ and $p_2$ such that

$$ \begin{align*} u_g(p_1^{-1}(i))\le n\cdot f(i) \text{ and } u_h(p_2^{-1}(i))\le n\cdot g(i) \text{ for all } i\in\omega. \end{align*} $$

Then

$$ \begin{align*} u_h((p_1\circ p_2)^{-1}(i))=u_h(p_2^{-1}(p_1^{-1}(i)))\le n\cdot u_g(p_1^{-1}(i))\le n^2\cdot f(i) \end{align*} $$

for all $i\in \omega $ . It follows that $fR_{n^2}h$ .

Similarly, we can prove that $fE_ng,gE_nh \Rightarrow fE_{n^2}h$ .

(4): By (2) we have that $fS_ng \Rightarrow fR_{2n}g$ and $gS_nh \Rightarrow gR_{2n}h$ . Then by (3) we have that $fR_{2n}g\land gR_{2n}h \Rightarrow fR_{4n^2}h \Rightarrow fS_{4n^2}h$ .

Lemma 7.8. $[U]_n=\{f\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}:\exists g\in U (fF_ng)\}$ is Borel for every open subset U of $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ and $n\ge 1$ .

Proof Fix $n\ge 1$ . Without loss of generality, assume U is the form of $(\prod \limits _{i<m}(p_i,q_i)\times \prod \limits _{i\ge m}\mathbb {Q_+})\cap \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ for some $m\in \omega $ , where $0\le p_i<q_i\in \mathbb {Q_+}\text { for each} i<m$ . Fix m as above. Denote

$$ \begin{align*} S=\{s\in \mathbb{Q}_+^m:\forall i<m-1 \big(s(i)\ge s(i+1)\big)\ \land\ \forall i<m \big(p_i<s(i)<q_i\big) \}. \end{align*} $$

For each $s\in S$ , let $T_s$ be the set of all $t\in \mathbb {Q}_+^{<\omega }$ such that:

1. (1) For each $l<|t|-1$ , $t(l)\ge t(l+1)$ .

2. (2) $\frac {u_t([0,|t|-2])}{n}\le u_s([0,m-1]) < \frac {u_t([0,|t|-1])}{n}$ .

3. (3) For each $l'<|t|$ and $k<m$ ,

   $$\begin{align*}u_s([0,k])>n\cdot u_t([0,l'])\Rightarrow s(k)\le n\cdot t(l') .\end{align*}$$

4. (4) For each $l<|t|$ and $k<m$ ,

   $$\begin{align*}u_s([0,k])<\frac{u_t([0,l])}{n}\Rightarrow s(k)\ge\frac{t(l)}{n} .\end{align*}$$

Claim. $[U]_n=\bigcup \limits _{s\in S}\bigcup \limits _{t\in T_s}\left \{f\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}: f\big |_{|t|}=t\right \}$ .

Proof ( $\subseteq $ ): For each $f\in [U]_n$ there exists $g\in U$ such that $fF_ng$ . Then $g\big |_m=s\in S$ . Define $l_s$ by

$$\begin{align*}l_s=\min\{l>1:u_f([0,l-1])> n\cdot u_s([0,m-1])\}.\end{align*}$$

Let $t=f\big |_{l_s}$ . It is easy to see that t satisfies (1) by $f\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ . (2) follows from the definition of $l_s$ . By $fF_ng$ we have (3) and (4). It follows that $t\in T_s$ .

( $\supseteq $ ): Let $s\in S$ and $t\in T_s$ and $f\in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ such that $f\big |_{|t|}= t$ . Let $l=|t|$ . Then we have that

$$ \begin{align*} \frac{u_f([0,l-2])}{n}\le u_s([0,m-1])< \frac{u_f([0,l-1])}{n}. \end{align*} $$

We will find g extending s such that $g\in U$ and $fF_ng$ . It suffices to construct a sequence $\{g(i)\in \mathbb {Q}_+: i<\omega \}$ such that:

1. (5) $g(i)=s(i)$ for each $i<m$ and $g(i-1)\ge g(i)$ for each $i\ge m$ .

2. (6) For each $i\ge m$ ,

   $$ \begin{align*} \frac{u_f([0,l-2+i-m])}{n}\le u_g([0,i-1])<\frac{u_f([0,l-1+i-m])}{n} \end{align*} $$
   and $g(i-1)\ge \frac {f(l-1+i-m)}{n}$ .

3. (7) For each $i\ge m$ , if

   $$\begin{align*}n\cdot u_f([0,l'])<u_g([0,i-1])\le n\cdot u_f([0,l'+1]),\end{align*}$$
   then $l'<l-1+i-m$ and $g(i-1)\le n\cdot f(l')$ .

4. (8) $\lim \limits _{n\to \infty }g(n)=0$ .

Then $(5)\Rightarrow g\in U$ , $(3)(5)(7)\Rightarrow fS_ng$ , and $(4)$ – $(6)\Rightarrow gS_nf$ .

Suppose we have already constructed $\{g(i):i<j\}$ such that (5)–(7) hold for each $i<j$ . Let

$$ \begin{align*} \epsilon_j=\frac{u_f([0,l-1+j-m])}{n}-u_g([0,j-1]). \end{align*} $$

Define

$$ \begin{align*} g(j)=\max\{\epsilon_j,\frac{f(l+j-m)}{n}\}. \end{align*} $$

By (6) for $j-1$ , we have

$$ \begin{align*} \epsilon_j\le\frac{f(l-1+j-m)}{n}\le g(j-1). \end{align*} $$

It follows that $g(j)\le g(j-1)$ and $g(j)$ satisfies (5).

By $g(j)=\max \{\epsilon _j,\frac {f(l+j-m)}{n}\}$ , i.e.,

$$ \begin{align*} \frac{f(l+j-m)}{n} \le g(j) \text{ and } \epsilon_j\le g(j)<\epsilon_j+\frac{f(l+j-m)}{n}, \end{align*} $$

we have that

$$ \begin{align*} \frac{u_f([0,l-1+j-m])}{n}&\le u_g([0,j])<\frac{u_f([0,l-1+j-m])}{n}+\frac{f(l+j-m)}{n}\\ &=\frac{u_f([0,l+j-m])}{n}. \end{align*} $$

It is follows that $g(j)$ satisfies (6).

Assume that

$$ \begin{align*} n\cdot u_f([0,l'])<u_g([0,j])\le n\cdot u_f([0,l'+1]). \end{align*} $$

By $n\ge 1$ and

$$ \begin{align*} u_g([0,j])<\frac{u_f([0,l+j-m])}{n}\le n\cdot u_f([0,l+j-m]), \end{align*} $$

we have that $l'< l+j-m$ and

$$ \begin{align*} g(j)\le \frac{f(l-1+j-m)}{n} \le n\cdot f(l-1+j-m)\le n\cdot f(l'). \end{align*} $$

It is follows that $g(j)$ satisfies (7).

(8) follows from (7) for $j\ge m$ .

By the Claim above, we have that $[U]_n$ is Borel.

Theorem 7.9. $\simeq _K$ is decomposable on a Borel space $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ .

Proof $\simeq _K$ is decomposable which is witnessed by $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ being Borel and $\{F_{4n^2}:n\in \omega \}$ from Definition 7.6. We show that $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ is a Borel subset of $\mathbb {Q}_+^\omega $ . Recall that

$$ \begin{align*} f\in\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}\Leftrightarrow(\sum\limits_{n=0}^{\infty}f(n)=+\infty)\land(\lim\limits_{n\to\infty}f(n)=0)\land(\forall n\in\omega(f(n)\ge f(n+1)). \end{align*} $$

Define

$$ \begin{align*} A&=\{f\in\mathbb{Q}_+^\omega:\sum\limits_{n=0}^{\infty}f(n)=+\infty\},\\B&=\{f\in\mathbb{Q}_+^\omega:\lim\limits_{n\to\infty}f(n)=0\} \text{, and}\\C_n&=\{f\in\mathbb{Q}_+^\omega:f(n)\ge f(n+1)\} \text{ for each } n\in\omega. \end{align*} $$

We have

$$\begin{align*}f\in A\Leftrightarrow\forall M\in\omega\ \exists N\in\omega\ \left(\sum\limits_{n=0}^{N}f(n)\ge M\right)\end{align*}$$

and

$$\begin{align*}f\in B\Leftrightarrow\forall m\in\omega\ \exists N\in\omega\ \forall n\ge N\ \left(f(n)< \frac{1}{m}\right).\end{align*}$$

Thus A and B are Borel.

Obviously, $C_n$ is Borel for each $n\in \omega $ . It follows that $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ is Borel by $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}=A\cap B\cap (\bigcap \limits _{n\in \omega }C_n).$

Corollary 7.10. $\simeq _K\le _B H$ .

Proof Use Theorems 7.5 and 7.9.

7.2 The proof of $E_{K_\sigma }\le _B\simeq _K$

Now we turn to the proof of $E_{K_\sigma }\le _B\simeq _K$ .

Theorem 7.11. $(X_0,E_{K_\sigma })\le _B(\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}},\simeq _K)$ .

Proof First, we define a map $\Phi :X_0\to \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ as follows. Take $a_0=1$ and $a_{n+1}=2^n\sum \limits _{i=0}^na_i$ for each $n<\omega $ . For $\alpha \in X_0$ , define a sequence $\{c_n^\alpha :n\ge 1\}$ and $f_\alpha \in \boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ as follows. For each $n\ge 1$ :

1. (1) $c_1^\alpha = 1$ ;

2. (2) $\big |[c_n^\alpha ,c_{n+1}^\alpha )\big |=a_n\cdot 2^{\frac {n(n-1)}{2}+\alpha (n)}$ ;

3. (3) $f_\alpha (j)=2^{-\frac {n(n-1)}{2}-\alpha (n)}$ for each $j\in [c_n^\alpha ,c_{n+1}^\alpha )$ .

Then $f_\alpha $ is constant on every $[c_{n}^\alpha , c_{n+1}^\alpha )$ and $u_{f_\alpha }([c_{n}^\alpha , c_{n+1}^\alpha ))=a_{n}$ for each $n\ge 1$ . Let $\Phi (\alpha )=f_\alpha $ . We will show that $\Phi $ is Borel. Take a basic open subset V of $\Phi [X_0]$ , i.e., there exists $\mathcal A\in [\mathbb Q_+^{<\omega }]^{\omega }$ such that $V=\bigcup _{s\in \mathcal A}V_s$ and $V_s=[s]$ ¹ for all $s\in \mathcal A$ . Fix $s\in \mathcal A$ . Then there exist $\alpha \in X_0$ and $m\in \omega $ such that $s=f_\alpha \big |_{[0,m]}$ . Let $n\ge 1$ be such that $m\in [c_n^\alpha ,c_{n+1}^\alpha )$ . Then we have that

$$ \begin{align*} \Phi^{-1}(V_s)=\{\beta\in X_0:\beta(j)=\alpha(j),j\le n\} \text{ is open}. \end{align*} $$

It follows that $\Phi ^{-1}(V)=\bigcup _{s\in \mathcal A}\Phi ^{-1}(V_s)$ is open. Therefore $\Phi $ is continuous, hence Borel.

We claim that

$$ \begin{align*} \forall\alpha,\beta\in X_0(\alpha E_{K_\sigma}\beta\Leftrightarrow\Phi(\alpha)\simeq_K\Phi(\beta)). \end{align*} $$

( $\Rightarrow $ ): We will find $n\in \omega $ such that for each $k\in \omega $ ,

$$ \begin{align*} \frac{\Phi(\beta)(l_k)}{n}\le \Phi(\alpha)(k)\le n\cdot \Phi(\beta)(l^{\prime}_k), \end{align*} $$

where $l_k$ is such that

$$ \begin{align*} \frac{u_{\Phi(\beta)}([0,l_k-1]])}{n}\le u_{\Phi(\alpha)}([0,k])< \frac{u_{\Phi(\beta)}([0,l_k])}{n}, \end{align*} $$

and $l^{\prime }_k$ is such that

$$\begin{align*}n\cdot u_{\Phi(\beta)}([0,l^{\prime}_k])<u_{\Phi(\alpha)}([0,k])\le n\cdot u_{\Phi(\beta)}([0,l^{\prime}_k+1]).\end{align*}$$

Then $\Phi (\alpha )\simeq _K\Phi (\beta )$ by Lemma 7.3.

By $\alpha E_{K_\sigma }\beta $ , there exists N such that $|\alpha (m)-\beta (m)|\le N$ for $m\ge 1$ . Let $n = 2^N$ . For each $k\in \omega $ , take $l_k$ such that

$$ \begin{align*} \frac{u_{\Phi(\beta)}([0,l_k-1]])}{n}\le u_{\Phi(\alpha)}([0,k])< \frac{u_{\Phi(\beta)}([0,l_k])}{n}. \end{align*} $$

Take $n_k$ such that $k\in [c_{n_k}^\alpha ,c_{n_k+1}^\alpha )$ . We have that

$$ \begin{align*} u_{\Phi(\alpha)}([0,c_{n_k}^\alpha))=u_{\Phi(\beta)}([0,c_{n_k}^\beta))=\sum\limits_{i=1}^{n_k-1}a_i. \end{align*} $$

Then we have that

$$ \begin{align*} \frac{u_{\Phi(\beta)}([0,c_{n_k}^\beta))}{n}=\frac{u_{\Phi(\alpha)}([0,c_{n_k}^\alpha))}{n}< u_{\Phi(\alpha)}([0,k)) < \frac{u_{\Phi(\beta)}([0,l_k])}{n}. \end{align*} $$

It follows that

$$ \begin{align*} {l_k> c_{n_k}^\beta} \text{ and } \Phi(\beta)(l_k)\le2^{-\frac{n_k(n_k-1)}{2}-\beta(n_k)}. \end{align*} $$

By

$$ \begin{align*} \Phi(\alpha)(k)=2^{-\frac{n_k(n_k-1)}{2}-\alpha(n_k)} \end{align*} $$

and $\alpha (n_k)\le \beta (n_k) + N$ , we have that

$$ \begin{align*} \Phi(\alpha)(k)\ge 2^{-\frac{n_k(n_k-1)}{2}-\beta(n_k)-N}\ge\frac{\Phi(\beta)(l_k)}{2^N}. \end{align*} $$

Take $l^{\prime }_k$ such that

$$\begin{align*}n\cdot u_{\Phi(\beta)}([0,l^{\prime}_k])<u_{\Phi(\alpha)}([0,k])\le n\cdot u_{\Phi(\beta)}([0,l^{\prime}_k+1]).\end{align*}$$

Then we have that

$$\begin{align*}n\cdot u_{\Phi(\beta)}([0,l^{\prime}_k])<u_{\Phi(\alpha)}([0,k])\le n\cdot u_{\Phi(\alpha)}([0,c_{n_k+1}^\alpha))=n\cdot u_{\Phi(\beta)}([0,c_{n_k+1}^\beta)).\end{align*}$$

It follows that

$$ \begin{align*} {l^{\prime}_k<c_{n_k+1}^\beta} \text{ and } \Phi(\beta)(l^{\prime}_k)\ge2^{-\frac{n_k(n_k-1)}{2}-\beta(n_k)}. \end{align*} $$

By

$$ \begin{align*} \Phi(\alpha)(k)=2^{-\frac{n_k(n_k-1)}{2}-\alpha(n_k)} \end{align*} $$

and $-\alpha (n_k)\le -\beta (n_k) + N$ , we have that

$$ \begin{align*} \Phi(\alpha)(k)\le 2^{-\frac{n_k(n_k-1)}{2}-\beta(n_k) + N}\le2^N\cdot\Phi(\beta)(l^{\prime}_k). \end{align*} $$

Then by $n=2^N$ we have that

$$\begin{align*}\frac{\Phi(\beta)(l_k)}{n}\le \Phi(\alpha)(k)\le n\cdot\Phi(\beta)(l^{\prime}_k).\end{align*}$$

( $\Leftarrow $ ): Let $\alpha ,\beta \in X_0$ such that $(\alpha ,\beta )\not \in E_{K_\sigma }$ . We will show $\Phi (\alpha )\not \simeq _K\Phi (\beta )$ .

By $(\alpha ,\beta )\not \in E_{K_\sigma }$ , for each $N>0$ there exists $m_N>N$ such that

$$\begin{align*}|\alpha(m_N)-\beta(m_N)|>N.\end{align*}$$

Fix N. Take $k_N=c_{m_N+1}^\alpha -1$ and $l_N=c_{m_N}^\beta $ . Then

$$\begin{align*}\Phi(\alpha)(k_N)=2^{-\frac{m_N(m_N-1)}{2}-\alpha(m_N)}\end{align*}$$

and

$$\begin{align*}\Phi(\beta)(l_N)=2^{-\frac{m_N(m_N-1)}{2}-\beta(m_N)}.\end{align*}$$

Assume $\beta (m_N)>\alpha (m_N)+N$ . Thus

$$\begin{align*}\Phi(\alpha)(k_N)>2^N\cdot\Phi(\beta)(l_N).\end{align*}$$

By

$$\begin{align*}u_{\Phi(\alpha)}([0,k_N])=\sum\limits_{i=1}^{m_N}a_i\ge2^{m_N}\cdot\sum\limits_{i=1}^{m_N-1}a_i+\sum\limits_{i=1}^{m_N-1}a_i\end{align*}$$

and

$$\begin{align*}u_{\Phi(\beta)}([0,l_N])=\sum\limits_{i=1}^{m_N-1}a_i+\Phi(\beta)(l_N)\le \sum\limits_{i=1}^{m_N-1}a_i+2^{-N},\end{align*}$$

we have that

$$\begin{align*}u_{\Phi(\alpha)}([0,k_N])>2^{N}\cdot u_{\Phi(\beta)}([0,l_N]).\end{align*}$$

Without loss of generality, we can assume that there exists an infinite set $\{N_i:i\in \omega \}$ such that for each i, $\beta (m_{N_i})>\alpha (m_{N_i})+N_i$ . Then for all $0<M<\omega $ , there exists $i\in \omega $ such that $M\le 2^{N_i}$ . It follows that there exist $k_{N_i}$ and $l_{N_i}$ such that

$$ \begin{align*} u_{\Phi(\alpha)}([0,k_{N_i}])>2^{N_i}\cdot u_{\Phi(\beta)}([0,l_{N_i}]) \text{ and } \Phi(\alpha)(k_{N_i})>2^{N_i}\cdot \Phi(\beta)(l_{N_i}). \end{align*} $$

By $M\le 2^{N_i}$ ,

$$ \begin{align*} u_{\Phi(\alpha)}([0,k_{N_i}])>M\cdot u_{\Phi(\beta)}([0,l_{N_i}]) \text{ and } \Phi(\alpha)(k_{N_i})>M\Phi(\beta)(l_{N_i}). \end{align*} $$

It follows that $\Phi (\alpha )\not \simeq _K\Phi (\beta )$ by Theorem 4.1(6).

Theorem 7.12. $\simeq _K$ on $\boldsymbol{\textsf{F}}_{\boldsymbol{\textsf{DST}}}$ is Borel bireducible to ${l_\infty }$ .

Proof Use Corollary 7.10, Theorem 7.11, and $H\le _B l_\infty \le _B E_{K_\sigma }$ .