text:
# Borel and countably determined reducibility in nonstandard domain

## 1 Notation

$`{}_{}{}^{Y}X`$ is the set of all functions $`f:YX,`$ while $`x^y`$ will denote only the arithmetical power operation in standard and nonstandard domains.

$`{}_{}{}^{<\omega }2=_n{}_{}{}^{n}2`$ is the set of all finite binary sequences.

$`sa`$ is the extension of a finite sequence $`s`$ by a new rightmost term $`a.`$

$`𝚕𝚑s`$ is the length of a finite sequence $`s.`$

$`f\text{}X=\{f(x):xX𝚍𝚘𝚖\vartheta \},`$ the $`f`$-image of a set $`X.`$

If $`P`$ is a set of pairs then $`x𝑃y`$ and $`P(x,y)`$ mean that $`x,yP.`$

Nonstandard setup. Some degree of the reader’s acquaintance with basic notions of “hyperfinite” descriptive set theory is assumed; we give  as the basic reference. All “nonstandard” notions below, for instance $`^{},`$ are related to a fixed countably saturated nonstandard universe $`𝖀,`$ whose elements will be referred to as nonstandard (internal or external) sets.

In the remainder, we typically use letters like $`i,j,k,m,n`$ (with indices) for elements of $`,`$ and letters like $`a,b,c,h,x,y,z`$ for elements of $`^{}.`$

$`𝒫_{\mathrm{𝚒𝚗𝚝}}(X)`$ is the set of all internal subsets of a nonstandard set $`X.`$

If $`X,Y`$ are internal sets then $`({}_{}{}^{Y}X)_{\text{int}}`$ is the set of all internal $`f:YX.`$

Numbers $`c^{}`$ (standard or nonstandard) will be systematically identified with the sets $`[0,c)=\{x:x<c\}`$ of all smaller numbers. We shall often use $`{}_{}{}^{c}2,`$ instead of the more pedantical $`({}_{}{}^{[0,c)}2)_{\text{int}}`$ to denote the (internal) set of all internal functions $`\xi :c=[0,c)2`$.

$`\mathrm{\#}X^{}`$ is the number of elements of a hyperfinite set $`X.`$

Let $`rq`$ mean that the difference $`rq`$ is infinitesimal. For any bounded hyperrational $`\alpha `$ (i.e., $`\alpha <c`$ for some $`c`$) there is a unique standard real number $`r,`$ denoted by $`𝚜𝚝\alpha ,`$ the standard part of $`\alpha ,`$ such that $`\alpha r.`$ If $`\alpha `$ is unbounded then put $`𝚜𝚝\alpha =+\mathrm{}`$.

Borel and countably determined sets. Classes $`\mathrm{\Sigma }_1^0,\mathrm{\Pi }_1^0`$ consist of countable unions, resp., intersections of internal sets. Borel sets form the least $`\sigma `$-algebra which contains all internal sets; for instance, all sets in $`\mathrm{\Sigma }_1^0\mathrm{\Pi }_1^0`$ are Borel.

Following Henson , sets of the form

X=bB(mBXmmBX¯m),

where all sets Xm are internal,
BP(N), and =¯XmnXnXm,
𝑋subscript𝑏𝐵subscript𝑚𝐵subscript𝑋𝑚subscript𝑚𝐵subscript¯𝑋𝑚

where all sets Xm are internal,
BP(N), and =¯XmnXnXm,
\textstyle X=\bigcup_{b\in B}\hbox{\large$($}\bigcap_{m\in B}X_{m}\,\cap\,\bigcap_{m\not\in B}\overline{X}_{m}\hbox{\large$)$}\,,\,\text{ \ \parbox[t]{178.61191pt}{\hfill where all sets $X_{m}$ are internal,\\
\hfill$B\subseteq{\skr P}({{\hskip 0.1pt{\mathbb{N}}\hskip 0.1pt}}),$ and $\overline{X}_{m}=\bigcup_{n}X_{n}\setminus X_{m}$,}} (†)
are called countably determined, in brief CD. (Any reasonable version of this concept for Polish spaces yields the collection of all sets of the space.) There are several slightly different ways to define this class of sets, for instance,

X=fFmXfm,

where all Xs,s2<ω, are internal,
F2N,
and XtXs whenever st.
𝑋subscript𝑓𝐹subscript𝑚subscript𝑋𝑓𝑚

where all Xs,s2<ω, are internal,
F2N,
and XtXs whenever st.
\textstyle X=\bigcup_{f\in F}\bigcap_{m\in{{\hskip 0.1pt{\mathbb{N}}\hskip 0.1pt}}}X_{f{\hskip 0.1507pt\restriction\hskip 0.1507pt}m}\,,\,\ \text{ \ \parbox[t]{245.5965pt}{where all $X_{s},\linebreak[0]\;s\in\mathord{{}^{<\omega}{2}},$ are internal, \\
$F\subseteq\mathord{{}^{{{\hskip 0.1pt{\mathbb{N}}\hskip 0.1pt}}}{2}},$
and $X_{t}\subseteq X_{s}$ whenever $s\subset t$.}} (‡)
(See, e.g., . To convert () to (1), let $`B`$ consist of all sets $`b{}_{}{}^{<\omega }2`$ containing a subset of the form $`\{fm:m\},fF,`$ and apply any bijection $`{}_{}{}^{<\omega }2`$ onto $`.`$ To convert (1) to (), put $`X_s=_{k<m}X_k^{}`$ for any $`s=i_0,\mathrm{},i_{m1}{}_{}{}^{<\omega }2,`$ where $`X_k^{}=X_k`$ whenever $`i_k=1`$ and $`X_k^{}=^{}X_k`$ otherwise, then let $`F{}_{}{}^{}2`$ be the set of all characteristic functions of sets in $`B.`$)

All Borel sets are countably determined, but not conversely.

A map is Borel, countably determined if it has a Borel, resp., CD graph.

Cuts. Initial segments of $`^{}`$ (including $`\mathrm{},,^{}`$) are called cuts. A cut $`U`$ is additive if $`x+yU`$ whenever $`x,yU.`$ Given a CD cut $`U,`$ the sets

$$U=_{n,xU}[0,xn]\text{ and }U/=_{n,xU}[0,\frac{x}{n}]$$

are additive CD cuts, $`U/UU,`$ $`U/`$ is the largest additive cut included in $`U`$ while $`U`$ is the smallest additive cut including $`U.`$ In particular, let $`c/=[0,c)/`$ and $`c=[0,c)`$ for any $`c^{}`$.

If $`U`$ is an additive cut then $`\mathrm{log}U=\{h:2^hU\}`$ is also a cut (not necessarily additive) and $`U=2^{\mathrm{log}U}=_{h\mathrm{log}U}[0,2^h)`$.

Internal cuts are $`\mathrm{},^{},`$ and those of the form $`c=[0,c),c^{}.`$ Non-internal cuts can be obtained with the following general procedure. If $`\{a_n\}_n`$ is a strictly increasing, resp., decreasing sequence in $`^{}`$ then we define a countably cofinal cut $`\mathbf{}\{a_n\}=_n[0,a_n),`$ resp., countably coinitial cut $`\mathbf{}\{a_n\}=_n[0,a_n).`$ Both types consist of Borel sets of classes resp. $`\mathrm{\Sigma }_1^0`$ and $`\mathrm{\Pi }_1^0.`$

Cuts of the form $`c+=\{c+n:n\}`$ and $`c=\{cn:n\}(c)`$ are countably cofinal, resp., coinitial, but not additive (unless $`c`$ in $`c+`$).

###### Lemma 1.1.

Any CD cut $`\mathrm{}U^{}`$ it either countably cofinal or countably coinitial or contains a maximal element (and then is internal).

###### Proof.

Let $`U=_{fF}_mX_{fm},`$ where $`F`$ and the sets $`X_s`$ are as in (). Put $`\text{cut}X=_{xX}[0,x]`$ for any set $`X^{},`$ the least cut which includes $`X.`$ By Saturation, $`U=\text{cut}U=_{fF}_mU_{fm},`$ where $`U_s=\text{cut}X_s,`$ hence, $`U_s=[0,\mu _s],`$ where $`\mu _s=\mathrm{max}X_s^{}`$ for all $`s{}_{}{}^{<\omega }2.`$ If there is $`fF`$ with $`U=_mU_{fm}`$ then the sequence $`\{h_{fm}\}_m`$ witnesses that $`U`$ is countably coinitial, or contains a maximal element if the sequence is eventually constant. Otherwise, by Saturation, for any $`fF`$ there is $`m_f`$ such that $`h_{fm_f}U.`$ Let $`S=\{fm_f:fF\};`$ this is a countable set and easily $`U=_{sS}[0,\mu _s],`$ so that $`U`$ is either countably cofinal or contains a maximal element.

## 2 Equivalence relations and reducibility: preliminaries

Suppose that $`𝖤,𝖥`$ are countably determined equivalence relations (ERs, for brevity) on (also countably determined) sets $`X,Y.`$ We write $`𝖤_{𝙲𝙳}𝖥,`$ in words: $`𝖤`$ is CD-reducible to $`𝖥,`$ iff there is a CD map (called: reduction) $`\vartheta :XY`$ 111 To apply $`_{𝙲𝙳}`$ to non-CD relations, we should have used the existence of a CD map $`\vartheta `$ with $`X𝚍𝚘𝚖\vartheta `$ and $`\vartheta \text{}XY,`$ but we’ll not consider anything more complicated than CD below, in fact, mainly Borel ERs will be considered. such that we have $`x𝖤x^{}\vartheta (x)𝖥\vartheta (y)`$ for all $`x,x^{}X.`$ 222 It would be not less reasonable, but obviously longer, to write $`X/𝖤_{𝙲𝙳}Y/𝖥.`$ We write $`𝖤_{𝙲𝙳}𝖥`$ if both $`𝖤_{𝙲𝙳}𝖥`$ and $`𝖥_{𝙲𝙳}𝖤,`$ and $`𝖤<_{𝙲𝙳}𝖥`$ iff $`𝖤_{𝙲𝙳}𝖥`$ but not $`𝖥_{𝙲𝙳}𝖤.`$ Changing “countably determined” and “CD” to “Borel” in these definitions, we obtain the relations $`_𝙱,_𝙱,<_𝙱`$ of Borel reducibility.

Informal meaning of $`𝖤_{𝙲𝙳}𝖥`$ and $`𝖤_𝙱𝖥`$ is that $`𝖥`$ has at least as many equivalence classes as $`𝖤,`$ and this is witnessed by a CD, resp., Borel map.

Equalities, smooth ERs, transversals. For any set $`A,`$ the equality relation $`\text{D}(A)`$ (D from “diagonal”) is defined on $`A`$ by $`x\text{D}(A)y`$ iff $`x=y.`$ These are the simplest of ERs; in many aspects $`\text{D}(A)`$ can be identified with $`A.`$

Similarly to the “Polish” descriptive set theory, say that an ER $`𝖤`$ on a set $`X`$ is CD-smooth, resp., B-smooth, if $`𝖤_{𝙲𝙳}\text{D}(^{}),`$ resp., $`𝖤_𝙱\text{D}(^{}),`$ i.e., there is a countably determined, resp., Borel map $`\vartheta ,`$ with $`X𝚍𝚘𝚖\vartheta `$ and $`𝚛𝚊𝚗\vartheta ^{}`$ such that $`x𝖤x^{}`$ iff $`\vartheta (x)=\vartheta (x^{}):`$ this means that $`𝖤`$-classes admit a CD enumeration by hyperintegers.

A transversal of an equivalence relation $`𝖤`$ is a set which has exactly one common element with each $`𝖤`$-equivalence class. Easily any Borel ER $`𝖤`$ on a set $`X^{},`$ having a Borel transversal $`WX,`$ is B-smooth: let $`\vartheta (x)`$ be the only element of $`W`$ equivalent to $`x.`$ Similarly any CD equivalence relation $`𝖤`$ having a CD transversal is CD-smooth.

Borel and CD cardinalities. For any Borel sets $`X,Y,`$ let $`X_𝙱Y`$ mean that there is a Borel injection $`\vartheta :XY.`$ Accordingly, let $`X_𝙱Y`$ mean that both $`X_𝙱Y`$ and $`Y_𝙱X,`$ and $`X<_𝙱Y`$ will mean that $`X_𝙱Y`$ but not $`Y_𝙱X.`$ Changing “Borel” to “CD”, we obtain $`_{𝙲𝙳},_{𝙲𝙳},<_{𝙲𝙳},`$ stronger relations between countably determined sets.

Obviously $`X_𝙱Y`$ iff $`\text{D}(X)_𝙱\text{D}(Y),`$ thus, the $`_𝙱`$-structure of Borel sets is in a sense equal to the $`_𝙱`$-structure of B-smooth equivalence relations, and the same for the CD case.

###### Lemma 2.1.

Let $`X,Y`$ be Borel sets. Then $`X_𝙱Y`$ iff there is a Borel bijection of $`X`$ onto $`Y.`$ Similarly, if $`X,Y`$ are CD sets then $`X_{𝙲𝙳}Y`$ iff there is a CD bijection of $`X`$ onto $`Y.`$

###### Proof.

Apply the Cantor – Bernstein argument. To see that it yields a bijection of necessary type, recall that the image $`𝚛𝚊𝚗\vartheta `$ of a CD, resp., Borel injection $`\vartheta `$ is equal to $`𝚍𝚘𝚖(\vartheta ^1),`$ hence, is still a CD, resp., Borel set \[8, 2.10\].

Thus, $`X_{𝙲𝙳}Y`$ can be interpreted as saying that the sets $`X,Y`$ have the same CD-cardinality; the latter then can be defined as the $`_{𝙲𝙳}`$-class of $`X.`$ Similarly, $`X_𝙱Y`$ means that $`X,Y`$ have the same Borel cardinality.

The following result presents an alternative description of the relations $`_{𝙲𝙳},_𝙱`$ restricted to $`^{}`$ (i.e., acting only on hyperfinite sets; recall that any $`x^{}`$ is identified with the set $`[0,x)`$).

###### Proposition 2.2 (\[8, § 2\]).

Suppose that $`x,y^{}.`$ Then $`x_𝙱y`$ iff $`𝚜𝚝\frac{x}{y}=1,`$ and $`x_{𝙲𝙳}y`$ iff $`0<𝚜𝚝\frac{x}{y}<+\mathrm{}`$.

It follows that the relations $`x_𝙱y`$ and $`x_{𝙲𝙳}y`$ on $`^{}`$ are Borel. We show below that the first of them is not CD-smooth while the other one is CD-smooth but not B-smooth.

Exponential equalities. Let $`X,Y`$ be nonstandard sets. A function $`f:YX`$ is internally extendable if $`f=gY`$ for an internal function $`g`$ with $`Y𝚍𝚘𝚖g.`$ (If $`X`$ is internal then this is the same as an internal function.)

How many there are internally extendable functions $`X2`$? Equivalence relations allow to approach this quention in terms of Borel and CD reducibility. For any nonstandard set $`X,`$ let $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ be the equivalence relation defined on $`({}_{}{}^{H}2)_{\text{int}}`$ for some internal $`HX`$ so that $`\xi \text{D}_{\text{ext}}({}_{}{}^{X}2)\eta `$ iff $`\xi X=\eta X.`$ This definition formally depends on $`H,`$ but easily all ERs obtained this way (for a fixed $`X`$) are $`_𝙱`$-equivalent to each other, hence, $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ manifests this $`_𝙱`$-type. If $`X=H`$ is itself internal then so is $`\mathrm{\Xi }=({}_{}{}^{X}2){}_{\text{int}}{}^{},`$ and the definitions of $`\text{D}(\mathrm{\Xi })`$ and $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ give obviously one and the same (modulo $`_𝙱`$). If $`X`$ is not internal then $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ simulates the equality of internally extendable maps $`X2,`$ so that, for instance, the inequality $`\text{D}_{\text{ext}}({}_{}{}^{X}2)_𝙱\text{D}(Y)`$ ($`Y`$ internal) means that, the number of all internally extendable maps $`X2`$ is, in a sense, smaller-or-equal to $`\mathrm{\#}Y`$.

## 3 Borel cardinalities

Our first goal is to study the $`_𝙱`$-structure of Borel sets in $`^{}.`$ The following theorem shows that any infinite Borel subset of $`^{}`$ is $`_𝙱`$-equivalent to a unique Borel cut of some kind.

###### Theorem A.

For any Borel set $`X^{}`$ there is a Borel cut $`U^{}`$ with $`X_𝙱U,`$ actually, there is a minimal Borel cut $`U`$ satisfying $`X_𝙱U`$.

We precede the proof of the theorem by two auxiliary lemmas. The first of them says that $`_𝙱`$ is sometimes preserved under unions and intersections.

###### Lemma 3.1 (Essentially from Zivaljevic ).

Suppose that $`A_n,B_n`$ are hyperfinite sets, and $`b_n=\mathrm{\#}B_na_n=\mathrm{\#}A_n`$ for each $`n.`$ Then

1. if $`A_{n+1}A_n`$ and $`B_{n+1}B_n`$ for each $`n`$ then $`_nB_n_𝙱_nA_n;`$
2. if $`A_nA_{n+1}`$ and $`B_nB_{n+1}`$ for each $`n`$ then $`_nB_n_𝙱_nA_n`$.

###### Proof.

(i) For any $`n`$ there is an internal bijection $`f:A_0\text{ onto }[0,a_0)`$ such that $`f\text{}A_k=[0,a_k)`$ for all $`kn.`$ By Saturation, there is an internal bijection $`f:A_0\text{ onto }[0,a_0)`$ with $`f\text{}A_n=[0,a_n)`$ for all $`n.`$ We conclude that $`_nA_n_𝙱U=_n[0,a_n).`$ Also, $`_nB_n_𝙱D=_n[0,b_n).`$ However $`DU.`$

(ii) Arguing the same way, we prove that $`_nA_n_𝙱U=_n[0,a_n)`$ and $`_nB_n_𝙱D=_n[0,b_n),`$ but again $`DU`$.

If $`UV^{}`$ are cuts then we write $`UV`$ iff $`\frac{x}{y}1`$ for all $`x,yVU.`$ (For instance, if $`U=[0,a)`$ and $`V=[0,b)`$ then $`UV`$ iff $`\frac{a}{b}1.`$) This turns out to be a necessary and sufficient condition for $`U_𝙱V.`$

###### Lemma 3.2.

(i) If $`U,V`$ are Borel cuts then $`U_𝙱V`$ iff $`UV.`$

(ii) Any $``$-class of Borel cuts contains a $``$-minimal cut, in particular, any additive Borel cut is $``$-isolated, i.e., $`UV`$ for any cut $`VU`$.

###### Proof.

(i) Let, say, $`UV.`$ Suppose that $`U_𝙱V.`$ Take any $`x<y`$ in $`VU.`$ Then $`x_𝙱y,`$ hence, $`\frac{x}{y}1`$ by Proposition 2.2. Suppose, conversely, that $`UV.`$ Take any $`xVU.`$ Let $`c`$ be the entire part of $`x/2;`$ then easily $`cU.`$ Let $`A=\{a^{}:\frac{a}{c}0\}.`$ We observe that $`AU`$ and the difference $`D=VU`$ satisfies $`DX^+X^{},`$ where $`X^+=\{x+a:aA\}`$ and $`X^{}=\{xa:aA\}.`$ Define $`f(z)`$ for any $`zV`$ as follows. If $`zUA`$ then $`f(z)=z.`$ If $`zDX^+`$ then $`z=x+a,aA,`$ and we define $`f(z)=3a`$ (a number in $`A`$). If $`zDX^{},`$ but $`zx,`$ then $`z=xa,aA\{0\},`$ and we define $`f(z)=3a+1`$ (still a number in $`A`$). Finally, if $`xA`$ then let $`f(x)=3x+2.`$ Easily $`f`$ is a Borel injection $`VU.`$

(ii) Let $`\stackrel{~}{U}`$ be the set of all $`xU`$ such that there is $`yU,y>x`$ with $`\frac{x}{y}\simeq ̸1.`$ This is a cut, moreover, a projective set, hence, countably determined, which implies that $`\stackrel{~}{U}`$ is actually Borel by Lemma 1.1. Easily $`\stackrel{~}{U}U.`$ Finally, note that for any $`x\stackrel{~}{U}`$ there exists $`x^{}\stackrel{~}{U},x^{}>x,`$ with $`\frac{x^{}}{x}\simeq ̸1:`$ indeed, let $`x^{}=\frac{x+y}{2},`$ where $`yU,y>x,\frac{y}{x}\simeq ̸1.`$ This suffices to infer that $`V\stackrel{~}{U}`$ for any cut $`V\stackrel{~}{U}.`$ In other words, $`\stackrel{~}{U}`$ is the $``$-least cut $`_𝙱`$-equivalent to $`U,`$ as required. That $`\stackrel{~}{U}=U`$ for any additive cut $`U`$ is a simple exercise.

###### Proof (Theorem A).

Lemma 3.2 allows us to concentrate on the first assertion of the theorem. Since all Borel sets are countably determined, we can present a given Borel set $`X^{}`$ in the form $`X=_{fF}_nX_{fn},`$ where $`F`$ and the sets $`X_s^{}`$ are as in () of Section 1. If there is $`fF`$ such that all sets $`X_{fn}`$ are unbounded in $`^{}`$ then, by Saturation, there is an internal unbounded set $`YX_f=_nX_{fn}.`$ Then obviously $`Y_𝙱^{},`$ hence, $`X_𝙱^{}`$.

We assume henceforth that $`X`$ is bounded in $`^{}`$ — then it can be assumed that all sets $`X_s`$ are also bounded, hence, hyperfinite. Let $`\nu _s=\mathrm{\#}X_s`$.

Let $`C`$ be the set of all $`c^{}`$ such that there is $`fF`$ and an internal injection $`\phi :[0,c)X_f=_nX_{fn}.`$ Easily $`C`$ is a cut, and a countably determined set. (By Saturation, for any internal $`Y`$ to be internally embeddable in $`X_f`$ it suffices that $`\mathrm{\#}Y\nu _{fm}`$ for any $`m.`$)

We claim that $`C_𝙱X.`$ Indeed if there is $`fF`$ such that $`C[0,\nu _{fn})`$ for all $`n`$ then immediately $`C_𝙱X_f`$ by Lemma 3.1(i). Otherwise for any $`fF`$ there is $`n_f`$ such that $`\nu _{fn_f}C.`$ As $`X_{fn_f}`$ is an internal set with $`\mathrm{\#}X_{fn_f}=\nu _{fn_f},`$ no internal set $`Y`$ with $`\mathrm{\#}Y>\nu _{fn_f}`$ admits an internal injection in $`X_f,`$ hence, the countable set $`\{\nu _{fn_f}:fF\}`$ is cofinal in $`C,`$ so that $`C=_k[0,z_k),`$ where all $`z_k`$ belong to $`C.`$ However for any $`k`$ there is an internal $`R_kX`$ with $`\mathrm{\#}R_k=z_k.`$ Lemma 3.1(ii) implies $`C_𝙱_kR_k`$.

In continuation of the proof of the theorem, we have the following cases.

Case 1: $`C`$ is not additive. Then there is $`cC`$ such that $`c=U`$ and $`2cC.`$ Prove that $`X_𝙱c.`$ By Lemma 3.1(ii), it suffices to cover $`X`$ by a countable union $`_jY_j`$ of internal sets $`Y_j`$ with $`\mathrm{\#}Y_j2c`$ for all $`j.`$ For this it suffices to prove that for any $`fF`$ there is $`m`$ such that $`\nu _{fm}=\mathrm{\#}X_{fm}2c.`$ To prove this, assume, on the contrary, that $`fF`$ and $`\nu _{fm}2c`$ for all $`m;`$ we obtain, by Saturation, an internal subset $`YX_f`$ with $`\mathrm{\#}Y=2cC,`$ contradiction. We return to this case below.

In the remainder, we assume that $`C`$ is additive.

Case 2: $`C`$ is countably cofinal. Arguing as in Case 1, we find that for any $`fF`$ there is $`m`$ such that $`\nu _{fm}=\mathrm{\#}X_{fm}C.`$ (Otherwise, using Saturation and the assumption of countable cofinality, we obtain an internal subset $`YX_f`$ with $`\mathrm{\#}YC,`$ contradiction.) Thus, $`X`$ can be covered by a countable union $`_jY_j`$ of internal sets $`Y_j`$ with $`\mathrm{\#}Y_jC`$ for all $`j.`$ It follows, by Lemma 3.1(ii), that $`X_𝙱C.`$ Since $`C_𝙱X`$ has been established, we have $`X_𝙱C,`$ so that $`U=C`$ proves the theorem.

Case 3: $`C`$ is countably coinitial, and there exists a decreasing sequence $`\{h_k\}_k,`$ coinitial in $`^{}U,`$ such that $`\frac{h_k}{h_{k1}}`$ is infinitesimal for all $`k.`$ For any $`k,`$ if $`fF`$ then there is $`m`$ with $`\nu _{fm}h_{k+1}`$ (otherwise, by Saturation, $`X_f`$ contains an internal subset $`Y`$ with $`\mathrm{\#}Y>h_{k+1},`$ contradiction), so that $`X`$ is covered by a countable union of internal sets $`Y_j`$ with $`\mathrm{\#}Y_jh_{k+1}`$ for all $`j.`$ It follows, by Saturation and because $`\frac{h_k}{h_{k1}}`$ is infinitesimal, that, for any $`k,`$ $`X`$ can be covered by an internal set $`R_k`$ with $`\mathrm{\#}R_kh_k.`$ Now $`X_𝙱C`$ by Lemma 3.1(i), hence, $`U=C`$ proves the theorem.

Case 4: finally, $`C=c/`$ for some $`cU.`$ We have $`c/_𝙱X_𝙱c`$ (similarly to Case 2).

To conclude, cases 2 and 3 led us directly to the result required, while cases 1 and 4 can be summarized as follows: there is a number $`c^{}`$ such that $`c/_𝙱X_𝙱c.`$ We can assume that $`Xc.`$

Let $`\mu (Y)=\frac{\mathrm{\#}Y}{c}`$ be the counting measure on $`c.`$ The set $`X`$ is Borel, hence, Loeb-measurable. If its Loeb measure is $`\mathrm{}`$ then there is a sequence $`\{X_n\}`$ of internal subsets of $`X`$ with $`\mathrm{\#}X_n=nc,n.`$ It follows that $`c_𝙱X`$ by Lemma 3.1, hence, $`X_𝙱U=c,`$ as required.

Suppose that the Loeb measure of $`X`$ is a (standard) real $`r0.`$ There is an increasing sequence $`\{A_n\}_n`$ of internal subsets of $`X`$ and a decreasing sequence $`\{B_n\}_n`$ of supersets of $`X`$ such that $`\mu (B_n)\mu (A_n)0`$ as $`n\mathrm{}`$ (i.e., the difference is eventually less than any fixed standard $`\epsilon >0`$). If $`r=0`$ then $`\frac{\mathrm{\#}B_n}{c}0,`$ therefore, $`_nB_n_𝙱c/`$ by Lemma 3.1, which implies $`X_𝙱c/`$ since $`c/_𝙱X,`$ therefore, $`U=c/`$ proves the theorem.

Finally, assume that $`r>0.`$ Prove that then $`X_𝙱[0,(cr)).`$ We have $`\frac{\mathrm{\#}A_n}{c}r`$ from below and $`\frac{\mathrm{\#}B_n}{c}r`$ from above. Let $`U=_n[0,\mathrm{\#}A_n)`$ and $`V=_n[0,\mathrm{\#}B_n);`$ then $`_nA_n_𝙱U`$ and $`_nB_n_𝙱V`$ by Lemma 3.1, while $`(cr)VU,`$ hence, in remains to prove that $`U_𝙱V.`$ It suffices, by Lemma 3.2, to show that $`UV.`$ Let $`x<y`$ belong to $`VU.`$ If $`\frac{y}{x}\simeq ̸1`$ then $`\frac{y}{c}\frac{x}{c}`$ is not infinitesimal, which contradicts the fact that $`\mu (B_n)\mu (A_n)0`$ because $`\mu (A_n)\frac{x}{c}`$ and $`\frac{y}{c}\mu (B_n)`$ for all $`n`$.

(Theorem A)

###### Corollary 3.3.

Any two Borel sets $`X,Y^{}`$ are $`_𝙱`$-comparable.

###### Corollary 3.4 (originally Zivaljevic ).

If $`c^{},`$ $`\mu `$ is a finite counting measure on $`[0,c),`$ and sets $`X,Yc`$ are Borel and of non-0 Loeb measure $`L(\mu )`$ then $`X_𝙱Y`$ iff $`L(\mu )(X)=L(\mu )(Y)`$.

###### Proof.

See the last paragraph of the proof of the theorem.

Complete classification of Borel cardinalities. Call a Borel cut $`U^{}`$ minimal if $`V_𝙱U`$ for any cut $`VU.`$ It follows from Theorem A that any $`_𝙱`$-class of Borel subsets of $`^{}`$ contains a unique minimal Borel cut, so that minimal Borel cuts can be viewed as Borel cardinals (of Borel subsets of $`^{}`$).

For instance, any additive Borel cut is minimal by Lemma 3.2, hence, a Borel cardinal. But if $`U`$ is a non-additive minimal Borel cut, then there is a number $`cU`$ with $`2cU,`$ so that $`c/Uc,`$ and, accordingly, $`c/<_𝙱U<_𝙱c,`$ because $`c/`$ and $`c`$ are minimal cuts themselves. (Easily $`c`$ is the least attitive cut bigger than $`c/.`$)

To study the structure of minimal Borel cuts between $`c/`$ and $`c`$ for a fixed nonstandard $`c^{},`$ put $`y_{cr}=(cr)`$ for any real $`r,z>0,`$ where, we recall, $`(`$) is the entire part in the internal universe. Let $`U_{cr}=[0,y_{cr}].`$ Easily any minimal Borel cut $`U`$ satisfying $`c/<_𝙱U<_𝙱c`$ is equal to $`\stackrel{~}{U}_{cr}`$ for some positive real $`r,`$ and $`\stackrel{~}{U}_{cr}\stackrel{~}{U}_{cr^{}}`$ for different $`r,r^{}`$ (and one and the same $`c`$). Thus, Borel cardinals of Borel subsets of $`^{}`$ are either additive Borel initial segments or those of the form $`\stackrel{~}{U}_{cr},`$ or, finally, (finite) natural numbers.

## 4 CD cardinalities

It can be expected that different Borel cardinalities are “glued” by countably determined maps. Lemma 4.1 below reveals the exact measure of this phenomenon. The other side of the CD cardinalities vs. the Borel ones is that this notion is addressed to a much bigger class of sets, the countably determined sets, which are not necessarily Loeb measurable and, generally, have more vague nature. In particular, the $`_{𝙲𝙳}`$-structure of countably determined sets is known only partially.

###### Theorem B.

If $`X^{}`$ is an infinite countably determined set then either there is a unique additive Borel cut $`U_{𝙲𝙳}X`$ or there is an infinitely large $`c^{}`$ such that $`c/<_{𝙲𝙳}X<_{𝙲𝙳}c`$.

Thus, any infinite countably determined subset of $`^{}`$ either is $`_{𝙲𝙳}`$-equivalent to a unique additive CD cut, or at least can be placed between two adjacent additive CD cuts. While the “either” case is realized on simple examples (for instance, additive Borel cuts themselves), the “or” case remains enigmatic.

The next lemma comprises several facts involved in the proof.

###### Lemma 4.1.

If $`U^{}`$ is an infinite Borel cut then $`U_{𝙲𝙳}\times U`$ (the Cartesian product) and $`U_{𝙲𝙳}U`$ (a cut).

On the other hand, if $`UV`$ are Borel cuts, and $`U`$ is additive, then there is no CD map $`\phi :U\text{ onto }V.`$

It follows that, for $`x,y^{},`$ $`[0,x)_{𝙲𝙳}[0,y)`$ iff $`0<𝚜𝚝\frac{x}{y}<\mathrm{}`$.

###### Proof.

Theorem D below implies that there exists a CD set $`WU`$ such that for any $`xU`$ there is a unique $`w_xW`$ with $`|xw_x|.`$ Let $`az_a,n_a`$ be a recursive bijection of $``$ (the integers) onto $`\times .`$ Now, if $`xU`$ then put $`a=xw_x`$ and $`\vartheta (x)=w_x+z_a,n_a.`$ If $`x=m`$ then let $`\mathrm{\Phi }(x)=i_m,j_m,`$ where $`mi_m,j_m`$ is a fixed bijection of $``$ onto $`\times .`$ Also, if $`U`$ has a maximal element $`\mu `$ and $`x=\mu m,m,`$ then let $`\vartheta (x)=\mu j_m,i_m.`$ Easily $`\vartheta `$ is a CD bijection of $`U`$ onto $`U\times `$.

In the second equivalence, if $`U`$ is additive then $`U=U`$ and there is nothing to prove. Otherwise there is $`cU`$ such that $`U=_n[0,cn).`$ Note that $`U=_nU_n,`$ where $`U_n=cn+U,`$ hence, there is a Borel bijection of $`U\times `$ onto $`U.`$

To prove the second assertion, let, on the contrary, $`P=_{fF}_mP_{fm}`$ be such a map ($`P_s^{}\times ^{}`$ are internal sets and $`P_sP_t`$ whenever $`ts.`$) Then any $`P_f=_mP_{fm}`$ is still a function, hence, by Saturation, there is a number $`m_f`$ such that $`P_{fm_f}`$ is a function. Thus, there is a countable family of internal functions $`\mathrm{\Phi }_i,i,`$ with $`U𝚍𝚘𝚖\mathrm{\Phi }_i,`$ such that $`V_i\mathrm{\Phi }_i\text{}U.`$ We can assume that $`V=[0,c),`$ where $`c^{}U.`$ Put $`c_0=c`$ and, by induction, let $`c_{n+1}`$ be the entire part of $`c_n/2.`$ Then still $`c_nU`$ for any $`n`$ as $`U`$ is an additive cut, therefore, $`V_i\mathrm{\Phi }_i\text{}[0,c_{i+2}].`$ Yet every $`V_i=\mathrm{\Phi }_i\text{}[0,c_{i+2})`$ is an internal set with $`\mathrm{\#}V_ic/2^{i+2},`$ hence, by Saturation, $`_iV_i`$ can be covered by an internal set with $`c/2`$ elements, and cannot cover $`V.`$

###### Remark 4.2.

Thus, for any infinitely large $`c^{},`$ all Borel cardinals (as defined in the end of Section 3) between $`c/`$ and $`c`$ are $`_{𝙲𝙳}`$-equivalent to each other and to $`c.`$ It follows that for any Borel set $`X^{}`$ there is a unique additive Borel cut $`U`$ with $`X_{𝙲𝙳}U,`$ so that we can define CD-cardinals of Borel sets to be just additive Borel cuts in $`^{}.`$ What about CD-cardinalities of countably determined sets ? Unfortunately, this question remains open.

###### Proof (Theorem B).

We leave it as an easy exercise for the reader to verify that the arguments in the proof of Theorem A are partially applicable to any countably determined, not necessarily Borel, set $`X^{}.`$ More exactly. If $`X`$ is unbounded in $`^{}`$ then $`X_{𝙲𝙳}^{}.`$ If $`X`$ is bounded in $`^{}`$ then either $`X`$ is $`_{𝙲𝙳}`$-equivalent to an additive Borel cut (cases 2 and 3) or there is an infinitely large number $`c`$ with $`c/<_{𝙲𝙳}X<_{𝙲𝙳}c`$ (cases 1 and 4). The Loeb measurability of Borel sets allowed us to further study the “or” case provided $`X`$ is a Borel set, but the method does not seem to apply for CD sets in general.

(Theorem B)

## 5 On “singular” CD sets

Recall that the CD-cardinality of a countably determined set $`X`$ is the $`_{𝙲𝙳}`$-class of $`X.`$ For the moment, let us consider only the case of bounded CD sets $`X^{}.`$ Natural (finite) numbers and CD-cardinalities of additive countably determined cuts $`U^{}`$ can be called regular, other singular. For instance, any $`c=[0,c)^{}`$ has regular CD-cardinality because, by the above, if $`c`$ then $`[0,c)_{𝙲𝙳}c.`$

###### Problem 5.1.

Do there exist singular CD-cardinalities ? In other words (we refer to Theorem B), given $`c^{},`$ does there exist a countably determined set $`X`$ of type “or” of Theorem B, i.e., satisfying $`c/<_{𝙲𝙳}X<_{𝙲𝙳}c`$? If yes then are there $`_{𝙲𝙳}`$-incomparable sets of this sort ?

If the first question answers in the negative then the structure of CD cardinalities of (countably determined) subsets of $`^{}`$ turns out to be rather well organized: any infinite CD set $`X^{}`$ is $`_{𝙲𝙳}`$-equivalent to an additive CD cut in $`^{}.`$ But we would rather conjecture the existence of “singular” countably determined sets, i.e., those of type “or” of Theorem B. The goal of this Section is to prove that CD subsets of $`Xc`$ satisfying $`c/_{𝙲𝙳}X`$ (including possible examples for the problem) are $`_{𝙲𝙳}`$-equivalent to sets of rather simple form, which may lead to more fruitful further studies.

Since any $`c^{}`$ belongs to an interval of the form $`[2^d,2^{d+1}),d^{},`$ and then $`c=2^d`$ and $`c/=2^d/,`$ we can assume that already $`c=2^d.`$ In this case, the domain $`c=[0,c)`$ can be identified with the set $`\mathrm{\Xi }={}_{}{}^{d}2`$ of all interhal $`\xi :d2:`$ the map $`\xi x(\xi )=_{k=0}^{d1}2^{dk1}\xi (k)`$ is an internal bijection of $`\mathrm{\Xi }`$ onto $`[0,c).`$ For any $`s{}_{}{}^{<\omega }2`$ put $`M_s^d=\{\xi \mathrm{\Xi }:s\xi \}.`$ For any $`g{}_{}{}^{}2,`$ put $`M_g^d=_mM_{gm}^d=\{\xi \mathrm{\Xi }:\xi =g\}.`$ Call sets $`M_g^d`$ $`d`$-monads. In different terms, the monads $`M_g^d`$ are equivalence classes of the equivalence relation $`\text{D}_{\text{ext}}({}_{}{}^{}2)`$ on $`\mathrm{\Xi }={}_{}{}^{d}2,`$ see Section 2333 In the notation of , $`\xi `$ is denoted by $`𝚜𝚝\xi ,`$ the standard part, hence, we have $`M_g^d=𝚜𝚝^1(\{g\})`$ and $`M_G^d=𝚜𝚝^1(G).`$

For instance, $`M_\mathrm{𝟎}^d,`$ where $`\mathrm{𝟎}{}_{}{}^{}2`$ is the constant $`0,`$ is a $`d`$-monad. Easily $`\{x(\xi ):\xi M_\mathrm{𝟎}^d\}=c/,`$ hence, $`c/_{𝙲𝙳}M_\mathrm{𝟎}^d_{𝙲𝙳}M_g^d`$ for each $`g{}_{}{}^{}2.`$

Any union $`M_G^d=_{gG}M_g^d`$ of $`d`$-monads ($`G{}_{}{}^{}2`$) is clearly a CD set.

###### Theorem C.

Suppose that $`c=2^d^{}.`$ If $`Xc`$ is a countably determined set then either $`X<_{𝙲𝙳}c/`$ or $`X_{𝙲𝙳}M_G^d`$ for some $`G{}_{}{}^{}2`$.

###### Proof.

As $`c=[0,c)_{𝙲𝙳}c`$ by Lemma 4.1, we can assume that $`Xc,`$ moreover, $`X=_{fF}_mX_{fm},`$ where $`F{}_{}{}^{}2`$ while $`X_sc`$ are internal sets. We claim that the following can be w. l. o. g. assumed:

1. $`X_tX_s`$ whenever $`st`$ (otherwise put $`X_s^{}=_{k<𝚕𝚑u}X_{sk}`$);
2. $`X_{s0}X_{s1}=\mathrm{}`$ for any $`s{}_{}{}^{<\omega }2;`$
3. for any $`s{}_{}{}^{<\omega }2,`$ either $`\mathrm{\#}X_s=c2^k`$ for some $`k=k_s`$ or $`\mathrm{\#}X_sc/`$;
4. for any $`si{}_{}{}^{<\omega }2,`$ $`\mathrm{\#}X_{si}\frac{1}{2}\mathrm{\#}X_s`$ ($`si`$ is the extension of $`s`$ by $`i`$).

Justification of (2). Sets $`X_s`$ admit partitions $`X_s=𝒳_s,`$ where $`𝒳_s`$ is a finite collection of pairwise disjoint internal subsets of $`X_s`$ such that

1. if $`st`$ then for any $`A𝒳_t`$ there is (unique) $`B𝒳_s`$ with $`AB`$;
2. if $`s,t{}_{}{}^{<\omega }2`$ have the same length then any $`A𝒳_s`$ and $`B𝒳_t`$ are either equal or disjoint.

Now, let $`\mathrm{\Phi }`$ be the set of all functions $`\phi ,𝚍𝚘𝚖\phi =,`$ such that there is $`fF`$ satisfying $`\phi (m)𝒳_{fm}`$ and $`\phi (m+1)\phi (m)`$ for any $`m.`$ Obviously $`X=_{\phi \mathrm{\Phi }}_m\phi (m),`$ which justifies the claim by a modification of the argument used to derive () from (1) in Section 1.

Justification of (3). Partitions $`X_s=𝒳_s^{}`$ can be defined, such that $`𝒳_s^{}`$ is an at most countable collection of subsets of $`X_s,`$ of which at most one, say $`P_s,`$ is a $`\mathrm{\Pi }_1^0`$ set with $`P_s_{𝙲𝙳}c/`$ while all others are (pairwise disjoint) internal sets of hyperfinite cardinalities of the form $`c2^k,k,`$ and still both (a) and (b) hold (for the collections $`𝒳_s^{}`$). We can drop all sets $`P_s`$ because this amounts to a total set of $`_{𝙲𝙳}c/`$ elements by Lemma 4.1, which is not essential in the context of the theorem. Then proceed as above.

Justification of (4): a similar argument.

Coming back to the proof of the theorem, let $`S=\{fm:fFm\}`$ (a subset of $`{}_{}{}^{<\omega }2`$). In the assumptions (1)(4), one can define $`\sigma _s{}_{}{}^{<\omega }2`$ for any $`sS`$ so that (A) if $`siS`$ ($`i=0\text{ or }1`$) then $`\sigma _si\sigma _{si},`$ and (B) if $`\mathrm{\#}X_s=c2^m`$ then $`𝚕𝚑\sigma _s=m.`$ For any $`fF,`$ let $`g(f)=_m\sigma _{fm}{}_{}{}^{}2.`$ Let $`G=\{g(f):fF\}.`$ Note that (in our assumptions) the sets $`X_f=_mX_{fm}`$ and $`M_{g(f)}^d=_nM_{g(f)n}^d=_mM_{\sigma _{fm}}^d`$ are $`_{𝙲𝙳}`$ by Lemma 3.1(i), moreover, by a suitable modification of the proof of Lemma 3.1(i), we find an internal map $`\vartheta `$ such that $`\vartheta \text{}X_f=M_{g(f)}^d`$ for any $`fF,`$ hence, $`\vartheta X`$ is a bijection of $`X`$ onto $`M_G^d.`$

Thus, if Problem 5.1 answers in the positive then, by the theorem, there exist corresponding examples of the form $`M_G^d,G{}_{}{}^{}2.`$ The following rather elementary consideration focuses on $`_{𝙲𝙳}`$-properties of sets of this form.

Let a number $`c=2^d^{}`$ be fixed.

First of all note that $`M_g^d_{𝙲𝙳}c/`$ for any $`g{}_{}{}^{}2,`$ see above, therefore, we have $`c/_{𝙲𝙳}M_G^d`$ whenever $`\mathrm{}G{}_{}{}^{}2`$.

For $`c/<_{𝙲𝙳}M_G^d`$ (strictly), it is necessary and sufficient that $`\overline{\text{mes}}G>0,`$ where $`\overline{\text{mes}}`$ is the upper Lebesque measure on $`{}_{}{}^{}2.`$ (Indeed, if $`\overline{\text{mes}}G=0`$ then, by Saturation, for any $`m`$ the set $`M_G^d`$ can be covered by an internal set $`X`$ with $`\mathrm{\#}Xc/m,`$ hence, $`c/<_{𝙲𝙳}M_G^d`$ by Lemma 3.1(i). Conversely, if $`M_G^d`$ is covered by an internal set $`X`$ with $`\mathrm{\#}Xc/m,`$ then, for any $`gG,`$ there is a number $`m_g`$ such that $`M_g^{}^dX`$ whenever $`g^{}D_{gm_g},`$ where $`D_s=\{g^{}{}_{}{}^{}2:sg^{}\}`$ for any $`s{}_{}{}^{<\omega }2.`$ But the union $`D=_{gG}D_{gm_g}`$ easily has measure $`m^1`$ in $`{}_{}{}^{}2.`$)

If $`\underset{¯}{\text{mes}}G>0`$ (the inner Lebesgue measure) then $`M_G^d_{𝙲𝙳}[0,c)_{𝙲𝙳}c.`$ Indeed, we can assume, by Cantor – Bernstein, that $`G`$ is a closed subset of $`{}_{}{}^{}2`$ of positive measure, say, of measure $`2^m,m.`$ Then $`M_G^d`$ is equal to a decreasing union $`_nX_n,`$ where each $`X_n`$ is an internal set with $`\mathrm{\#}X_nc2^m.`$ It follows, by Lemma 3.1, that $`[0,c2^m)_{𝙲𝙳}M_G^d,`$ and so on.

But $`\underset{¯}{\text{mes}}G>0`$ is not a necessary condition for $`M_G^d_{𝙲𝙳}c.`$ Indeed, let $`G`$ be a transversal for the equivalence relation $`f𝖤_0g`$ iff $`f(n)=g(n)`$ for all but finite $`n`$ ($`f,g{}_{}{}^{}2`$), an example of a set with $`\underset{¯}{\text{mes}}G=0`$ and $`\overline{\text{mes}}G=1.`$ There is a sequence of internal functions $`\vartheta _n`$ such that $`[0,c)=_n\vartheta _n\text{}M_G^d,`$ so that, by an argument similar to Lemma 4.1, we have $`M_G^d_{𝙲𝙳}[0,c)_{𝙲𝙳}c.`$

Thus, to obtain an anticipated example for Problem 5.1 in the form $`M_G^d,`$ we have to employ nonmeasurable sets $`G{}_{}{}^{}2`$ with $`\underset{¯}{\text{mes}}G=0<\overline{\text{mes}}G`$ but less “dense” than transversals of $`𝖤_0.`$ It remains to be seen whether such an approach may lead to a solution of the problem.

###### Problem 5.2.

Which “standard” property of $`G,G^{}{}_{}{}^{}2`$ is necessary and sufficient for $`M_G^d_{𝙲𝙳}M_G^{}^d`$?

## 6 Countable ERs have transversals

An equivalence relation $`𝖤`$ is “countable” if any its equivalence class, i.e., a set of the form $`[x]_𝖤=\{y:x𝖤y\},x𝚍𝚘𝚖𝖤,`$ is at most countable. In “Polish” descriptive set theory, “countable” Borel ERs form a rather rich class whose full structure in terms of Borel reducibility is a topic of deep investigations (see Kechris ). In nonstandard setting, the picture is different.

###### Theorem D.

Any “countable” countably determined equivalence relation $`𝖤`$ on $`^{}`$ admits a countably determined transversal, hence, is CD-smooth.

Jin  proved the result for the ER $`x𝖬_{}y`$ iff $`|xy|.`$ Our proof of the general result employs a somewhat different idea, although some affinities with Jin’s arguments can be traced. Note also that $`𝖬_{},`$ a typical countable equivalence relation, is not B-smooth (see Lemma 12.1 below), this is the most transparent case when the Borel reducibility is really stronger.

###### Proof.

The CD-smoothness easily follows from the existence of a transversal: just let $`\vartheta (x)`$ to be the only element of a transversal equivalelent to $`x`$.

To define a transversal, suppose, as usual, that $`𝖤=_{fF}_mP_{fm},`$ where all sets $`P_s,s{}_{}{}^{<\omega }2,`$ are internal subsets of $`^{}\times ^{}`$ with $`P_tP_s`$ whenever $`st,`$ and $`F{}_{}{}^{}2.`$ An ordinary Saturation argument shows that, because all $`𝖤`$-classes are countable and a countable set cannot contain an infinite internal subset, for any $`fF`$ there is a number $`m_f`$ such that all cross-sections $`P_{fm_f}(x)=\{y:xP_{fm_f}y\}`$ are finite. Let $`S=\{fm_f:fF\};`$ this is a subset of $`{}_{}{}^{<\omega }2.`$ Then, for any $`sS,k,`$ and $`x^{},`$ we can define $`f_{sk}(x)`$ to be the $`k`$-th element (the counting begins with $`0`$) of $`P_s(x),`$ in the natural order of $`^{},`$ whenever $`\mathrm{\#}P_s(x)k,`$ so that $`f_{sk}`$ is an internal partial function $`^{}^{}`$.

Let $`sS`$ and $`k,k1.`$ For any $`x^{}`$ define an internal decreasing sequence $`\{x_{(a)}\}_{aa(x)}`$ of length $`a(x)+1^{}`$ as follows. Put $`x_{(0)}=x.`$ Suppose that $`x_{(a)}`$ is defined. If $`z=f_{sk}(x_{(a)})`$ is defined and $`z<x_{(a)}`$ then put $`x_{(a+1)}=z,`$ otherwise put $`a(x)=a`$ and end the construction. (Note that eventually the construction stops simply because $`x_{(a+1)}<x_{(a)}.`$) Put $`\nu _{sk}(x)=0`$ if $`a(x)`$ is even and $`\nu _{sk}(x)=1`$ otherwise.

Put $`𝚙𝚛𝚏𝚕x=\{s,kS\times :\nu _{sk}(x)=0\},`$ the “profile” of any $`x^{}`$.

###### Lemma 6.1.

If $`xy^{}`$ and $`x𝖤y`$ then $`𝚙𝚛𝚏𝚕x𝚙𝚛𝚏𝚕y`$.

Thus, while it is, generally speaking, possible that different nonstandard numbers have equal “profiles”, this cannot happen if they are $`𝖤`$-equivalent.

###### Proof.

We can assume that $`y<x.`$ There is $`fF`$ such that $`x,yP_f=_mP_{fm}.`$ let $`s=fm_f,`$ an element of $`S.`$ Then $`y`$ belongs to $`P_s(x),`$ a finite set, say, $`y`$ is $`k`$-th element of $`P_s(x),`$ in the natural order of $`^{}.`$ In other words, $`y=x_{(1)},`$ in the sense of the construction above, therefore, $`y(1)=x_{(2)},`$ etc.; we conclude that $`\nu _{sk}(x)\nu _{sk}(y)`$.  (Lemma )

Coming back to the theorem, choose an element $`r_AA`$ in any set $`\mathrm{}A𝒫(S\times ).`$ For any $`x^{},`$ the set $`A(x)=\{𝚙𝚛𝚏𝚕y:y[x]_𝖤\}`$ is a non-empty countable subset of $`𝒫({}_{}{}^{<\omega }2\times ).`$ Then $`X=\{x^{}:𝚙𝚛𝚏𝚕x=r_{A(x)}\}`$ is a transversal for $`𝖤`$ by Lemma 6.1. To prove that $`X`$ is countably determined consider the family $`S`$ which consists of all sets

$$D_{sk}=𝚍𝚘𝚖f_{sk},X_{sk}=\{x^{}:\nu _{sk}(x)=0\},$$

and $`X_{sks^{}k^{}}=\{xD_{sk}:\nu _{s^{}k^{}}(f_{sk}(x))=0\},`$ along with their complements. Let $`𝒜`$ be the set of all at most countable sets $`A𝒫(S\times ).`$ Obviously $`X=_{A𝒜}X(A),`$ where

$$X(A)=\{xX:A(x)=A\}=\{x^{}:A(x)=A𝚙𝚛𝚏𝚕x=r_A\},$$

###### Lemma 6.2.

Any set $`X(A),A𝒜,`$ is countably determined in $`S,`$ in the sense that it can be obtained by (1) of Section 1 applied to sets in $`S.`$

###### Proof.

Direct straightforward reduction to sets in $`S`$ shows that $`X(A)`$ is even Borel in $`S`$ in a similar sense. The most essential part of the reduction is to express the inclusion $`A(x)A`$ by the formula

$$sSk\left(xD_{sk}rA(r=𝚙𝚛𝚏𝚕f_{sk}(x))\right),$$

to avoid a universal quantifier over the equivalence class $`[x]_𝖤.`$

On the other hand, the class of all sets countably determined in a fixed countable collection $`S`$ of internal sets is closed under any unions (as well as under complements and intersections): just take the set theoretic union of the “bases” $`B`$ in the assumption that the assignment of sets in $`S`$ to indices is fixed once and for all. (Note that the class of all CD sets is closed only under countable unions and intersections !)  (Theorem D)

###### Corollary 6.3.

The equivalence relation $`x_{𝙲𝙳}y`$ on $`^{}`$ admits a countably determined transversal.

###### Proof.

Recall that $`x_{𝙲𝙳}y`$ iff $`0<𝚜𝚝\frac{x}{y}<+\mathrm{},`$ Proposition 2.2. It follows that the set $`\{2^x:xX\},`$ where $`X`$ is any CD transversal for the countable relation $`x𝖤_{}y`$ iff $`|xy|,`$ is as required.

On the contrary, the relation $`x_𝙱y`$ iff $`𝚜𝚝\frac{x}{y}=1`$ does not have a CD transversal. Indeed, suppose that $`X`$ is a CD transversal for $`_𝙱`$ restricted to the set $`D=[c,2c],`$ where $`c`$ is a fixed infinitely large hyperinteger. Note that, for $`x,yD,`$ $`x_𝙱y`$ is equivalent to $`𝚜𝚝\frac{x}{c}=𝚜𝚝\frac{y}{c}`$ so that $`X`$ yields a CD transversal for the equivalence relation of “having the same standard part $`𝚜𝚝r`$” on the set of hyperrationals $`A=\{r=\frac{x}{z}:xD\},`$ known to be impossible \[8, 2.6\]. In fact “the same standard part” ER is not CD-smooth and even not $`_{𝙲𝙳}`$-reducible to any $`\mathrm{\Sigma }_1^0`$ ER; this can be derived from our result in Part 2 of Section 11.

## 7 Silver – Burgess dichotomy

It is known from Henson  (see also Proposition 2.5 in ) that any countably determined set $`X^{}`$ is countable or else contains an infinite internal subset. The following is a slight generalization.

###### Lemma 7.1.

Let $`X^{}`$ be a countably determined set and $`U^{}`$ an additive cut of countable cofinality.

1. Either $`X_{𝙲𝙳}U`$ or $`X`$ contains an internal subset $`Y`$ with $`\mathrm{\#}YU`$.
2. Either $`X`$ is bounded (i.e., $`Xh`$ for some $`h^{}`$) or $`X`$ contains an unbounded internal subset.

###### Proof.

444 The result follows from Theorem B, but we prefer to present a short direct proof.

(i) Suppose that $`X=_{fF}_nX_{fn},`$ where $`F{}_{}{}^{}2`$ and $`X_s`$ are as in () of Section 1. Let $`S`$ consist of all $`s{}_{}{}^{<\omega }2`$ with $`\mathrm{\#}X_sU.`$ If there is $`fF`$ such that $`fnS`$ for all $`n`$ then by Saturation $`_nX_{fn}`$ contains an internal subset $`Y`$ with $`\mathrm{\#}YU.`$ Otherwise we have the “either” case.

(ii) A similar argument, with $`S`$ being the set of all $`s{}_{}{}^{<\omega }2`$ such that $`X_s`$ is unbounded in $`^{}`$.

Quotient structures $`^{}/𝖤,`$ where $`𝖤`$ is a CD equivalence relation, normally consist of non-internal elements, hence, do not contain internal subsets, but we can consider internal pairwise $`𝖤`$-inequivalent sets (i.e., sets of pairwise $`𝖤`$-inequivalent elements) instead. This leads us to the following theorem, saying that, given a countably determined ER $`𝖤,`$ either the number of equivalence classes is somehow restricted or there is a rather big pairwise inequivalent set. Recall that the relation $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ of equality of internally extendable maps $`U2`$ was defined in Section 2.

###### Theorem E.

Let $`𝖤`$ be a CD equivalence relation on $`^{},`$ and $`U`$ a countably cofinal additive cut. Then either $`𝖤_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ or there is an internal pairwise $`𝖤`$-inequivalent set $`Y^{}`$ with $`\mathrm{\#}YU`$.

In particular, either $`𝖤_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{}2)`$ (then $`𝖤`$ has $`𝔠`$-many equivalence classes) or there is an infinite internal pairwise $`𝖤`$-inequivalent set $`Y^{}`$.

It is not clear whether the general case is really a dichotomy and the quantitative characteristics are optimal. Generally, if $`U=_n[0,a_n)`$ is countably cofinal ($`\{a_n\}_n`$ increases) then the equivalence relation $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ has exactly $`_n𝚌𝚊𝚛𝚍(𝒫_{\mathrm{𝚒𝚗𝚝}}([a_n,a_{n+1})))`$ many equivalence classes, which is equal to $`\kappa ^\omega `$ provided all infinite internal sets have the same cardinality $`\kappa `$ and the differences $`a_{n+1}a_n`$ are infinite.

The relation $`\text{D}_{\text{ext}}({}_{}{}^{}2)`$ (the particular case in the theorem) has exactly $`𝔠`$-many equivalence classes and does not admit an infinite internal pairwise inequivalent set (see \[8, 2.6\] on the last claim), hence, the continuum cannot be improved to any smaller cardinal in the particular case.

###### Proof (Theorem E).

Suppose that $`𝖤=_{fF}_mP_{fm},`$ where $`P_s`$ are internal subsets of $`^{}\times ^{}`$ with $`P_tP_s`$ whenever $`st,`$ as in () of Section 1, while $`F{}_{}{}^{}2.`$ We can w. l. o. g. assume that the sets $`P_s`$ are symmetric, i.e., $`P_s=P_s{}_{}{}^{1}:`$ indeed, if this is not the case, then, as $`𝖤`$ itself is symmetric,

$$𝖤=𝖤𝖤^1=_{fF}_m(P_{fm}P_{fm}{}_{}{}^{1}),$$

where the sets $`P_{fm}P_{fm}^1`$ are symmetric.

Since $`𝖤`$ is an equivalence relation, we have

$$fFzm(xP_{fm}zyP_{fm}z)x𝖤y.$$

By Saturation, this can be rewritten as

$$TA(F)sTz(xP_szyP_sz)x𝖤y,$$
(1)
where $`A(F)`$ is the collection of all sets $`T\{fm:fFm\}`$ such that $`T\{fm:m\}\mathrm{}`$ for each $`fF`$.

Now let $`\{a_n\}_n`$ be an increasing sequence cofinal in $`U.`$ Suppose that there is no internal pairwise $`𝖤`$-inequivalent set $`Y`$ with $`\mathrm{\#}YU,`$ more formally,

$$Y𝒫_{\mathrm{𝚒𝚗𝚝}}(^{})\left(k(\mathrm{\#}Y>a_k)xyYfFm(xP_{fm}y)\right)$$

where $`𝒫_{\mathrm{𝚒𝚗𝚝}}(^{})=\{Y^{}:Y\text{is internal}\}.`$ The expression to the right of $``$ can be consecutively transformed (using Saturation and the fact that $`P_tP_s`$ provided $`st`$) to $`fFmxyY(xP_{fm}y),`$ and then to

$$TA(F)sTxyY(xP_sy),$$

which leads us to the following, for every $`TA(F)`$:

$$\begin{array}{c}Y𝒫_{\mathrm{𝚒𝚗𝚝}}(^{})\left(k(\mathrm{\#}Y>a_k)sTxyY(xP_sy)\right).\hfill \end{array}$$

Applying Saturation once again, we obtain, for any set $`TA(F),`$ a number $`k(T)`$ and a finite set $`T^{}T`$ such that

$$Y𝒫_{\mathrm{𝚒𝚗𝚝}}(^{})\left(\mathrm{\#}Y>a_{k(T)}sT^{}xyY(xP_sy)\right).$$

Since the sets $`P_s`$ are assumed to be symmetric, we conclude that for any $`TA(F)`$ there exists an internal set $`Z_T^{}`$ satisfying $`\mathrm{\#}Z_Ta_{k(T)}`$ and

$$x^{}zZ_TsT^{}(xP_sz).$$
(2)
Yet (2), as a property of $`Z_T,`$ depends only on $`T^{},`$ a finite subset of $`{}_{}{}^{<\omega }2,`$ not on $`T`$ itself, hence, we can choose sets $`Z_T`$ so that there are only countably many different among them. As $`U`$ is an additive cut, the set $`Z=_{TA(F)}Z_T^{}`$ admits, by Saturation, an internally extendable (see Section 2) injection $`\phi :ZU,`$ moreover, the cartesian product $`Z\times {}_{}{}^{<\omega }2`$ also admits an internally extendable injection in $`U,`$ hence, it suffices to prove that $`𝖤_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{Z\times {}_{}{}^{<\omega }2}2)`$.

Let $`H`$ be any internal set with $`Z\times {}_{}{}^{<\omega }2H.`$ Put, for any $`x^{},`$ $`\vartheta _x=\{z,sH:xP_sz\},`$ where $`P_s`$ is uniformly defined via an arbitrary internal extension of the external map $`sP_s`$ defined on $`{}_{}{}^{<\omega }2.`$ We have to show that, for $`x,y^{},`$ $`\vartheta _x=\vartheta _y`$ implies $`x𝖤y.`$ Assuming that $`\vartheta _x=\vartheta _y,`$ fix $`TA(F).`$ Choose, by (2), $`zZ`$ and $`sT`$ with $`xP_sz`$ — then $`z,s\vartheta _x=\vartheta _y,`$ hence, we also have $`yP_sz.`$ It remains to refer to (1).

Equivalence relations of class $`\mathrm{\Sigma }_1^0`$ admit the following special result:

###### Lemma 7.2.

Assume that $`𝖤`$ is a $`\mathrm{\Sigma }_1^0`$ equivalence relation on a subset of $`^{},`$ and $`X𝚍𝚘𝚖𝖤.`$ Then$`:`$

1. if $`X`$ is $`\mathrm{\Pi }_1^0`$ then either the quotient $`X/𝖤`$ is finite or there is an infinite internal pairwise $`𝖤`$-inequivalent set $`CX;`$
2. if $`X`$ is countably determined then either $`X/𝖤`$ is at most countable or there is an infinite pairwise $`𝖤`$-inequivalent internal set $`CX.`$

###### Proof.

(i) Let $`X=_nX_n`$ and $`𝖤=_nE_n,`$ all $`X_n`$ and $`E_n`$ being internal and $`X_{n+1}X_n,`$ $`E_nE_{n+1}`$ for all $`n.`$ If $`X/𝖤`$ is infinite then, for any $`n,`$ there is an internal set $`CX_n`$ with $`\mathrm{\#}Cn,`$ such that $`x,yE_n`$ for any two elements $`xy`$ of $`C.`$ It remains to apply Saturation.

(ii) Let $`X=_{fF}_mX_{fm},`$ where $`F`$ and $`X_s`$ are as in () of Section 1. If for any $`fF`$ there is a number $`m_f`$ such that $`X_{fm_f}/𝖤`$ is finite then $`X/𝖤`$ is at most countable. Otherwise there is $`fF`$ such that $`X_{fm}/𝖤`$ is infinite for all $`m,`$ and, arguing as in (i), we obtain an infinite pairwise $`𝖤`$-inequivalent internal subset of $`X_f=_mX_{fm}`$.

## 8 Monadic equivalence relations

Any additive cut $`U^{}`$ defines a monadic equivalence relation $`x𝖬_Uy`$ iff $`|xy|U`$ on $`^{}.`$ (If $`U`$ is not additive then $`𝖬_U`$ may not be a ER.) Classes of $`𝖬_U`$-equivalence, that is, sets of the form $`[x]_U=\{y:|xy|U\},x^{},`$ are called $`U`$-monads, all of them are convex subsets of $`^{}.`$

It follows from Lemma 1.1 that there are two types of countably determined monadic ERs $`𝖬_U:`$ countably cofinal and countably coinitial, according to the type of the cut $`U.`$ (The only exceptions are $`𝖬_{\mathrm{}},`$ the equality on $`^{},`$ and $`𝖬_{^{}},`$ the relation which makes all elements of $`^{}`$ equivalent.) It turns out that the relations between monadic ERs in terms of $`_{𝙲𝙳}`$ are determined by the relative rate of growth or decrease of corresponding cofinal or coinitial sequences.

To distinct cuts of lowest possible rate, say that additive countably cofinal cuts of the form $`c,c^{}`$ and countably coinitial cuts of the form $`c/,c^{})`$ are slow, while other additive countably cofinal or coinitial cuts are fast. For instance, $``$ is a slow cut. The following is easy:

###### Lemma 8.1.

A countably cofinal additive cut $`U`$ is slow iff $`U=\mathbf{}\{2^{r+n}\}`$ for some $`r^{},`$ and is fast iff there is an increasing sequence $`\{a_n\}_n`$ in $`^{}`$ such that $`U=\mathbf{}\{2^{a_n}\}`$ and $`a_{n+1}a_n`$ infinite for any $`n.`$

A countably coinitial additive cut $`U`$ is slow iff $`U=\mathbf{}\{2^{rn}\}`$ for some $`r^{},`$ and is fast iff there is a decreasing sequence $`\{a_n\}`$ in $`^{}`$ such that $`U=\mathbf{}\{2^{a_n}\}`$ and $`a_na_{n+1}`$ infinite for any $`n.`$

(Recall that $`\mathbf{}\{p_n\}=_n[0,p_n)`$ and $`\mathbf{}\{p_n\}=_n[0,p_n).`$)

Fast cuts admit further analysis. If $`\{a_n\}`$ and $`\{b_k\}`$ are increasing sequences of hyperintegers, then define $`\{a_n\}\{b_k\}`$ (meaning: $`\{b_k\}`$ increases faster) iff

$$knn^{}>nk^{}>k\left(a_n^{}a_nb_k^{}b_k\right).$$
(3)
Note that the negation of (3) has the form

$$knn^{}>nk^{}>k\left(a_n^{}a_n>b_k^{}b_k\right).$$
($`\neg \mathrm{\hspace{0.25em}3}`$)
Accordingly, if $`\{a_n\}`$ and $`\{b_k\}`$ are decreasing sequences of hyperintegers, then we define $`\{b_k\}\{a_n\}`$ (meaning: $`\{b_k\}`$ decreases faster) if and only if

$$knn^{}>nk^{}>k\left(a_na_n^{}b_kb_k^{}\right).$$
(4)
Finally, if $`U,V`$ are countably cofinal additive cuts, then $`UV`$ means that there are increasing sequences $`\{a_n\}\{b_k\}`$ with $`U=\mathbf{}\{2^{a_n}\},V=\mathbf{}\{2^{b_k}\}.`$ Similarly, if $`U,V`$ are countably coinitial additive cuts, then $`UV`$ means that there are decreasing sequences $`\{a_n\}\{b_k\}`$ with $`U=\mathbf{}\{2^{a_n}\},V=\mathbf{}\{2^{b_k}\}.`$

###### Remark 8.2.

If $`U,V`$ are both countably cofinal or both countably coinitial additive cuts, and $`U`$ is slow, then $`UV`$ by Lemma 8.1.

###### Theorem F.

Suppose that $`U,V`$ are additive countably determined cuts in $`^{}`$ other than $`\mathrm{}`$ and $`^{}.`$ Then $`\text{D}(^{})_𝙱𝖬_U.`$ In addition,

1. if both $`U,V`$ are countably cofinal or both are countably coinitial then $`𝖬_U`$ and $`𝖬_V`$ are $`_𝙱`$-comparable, and $`𝖬_U_𝙱𝖬_V`$ iff $`𝖬_U_{𝙲𝙳}𝖬_V`$ iff $`UV,`$ in particular, if $`U`$ is slow then $`𝖬_U_{𝙲𝙳}𝖬_V`$ (see Remark 8.2);
2. if $`U`$ is countably cofinal and $`V`$ countably coinitial then $`𝖬_V_{𝙲𝙳}𝖬_U`$ and $`𝖬_U_𝙱𝖬_V,`$ while $`𝖬_U_{𝙲𝙳}𝖬_V`$ holds iff $`U`$ is slow;
3. $`𝖬_U`$ is not B-smooth, and $`𝖬_U`$ is CD-smooth if and only if $`U`$ is countably cofinal and slow;
4. for any countable sequence of countably cofinal fast cuts $`U_n`$ there are countably cofinal fast cuts $`U,V`$ with $`𝖬_U<_𝙱𝖬_{U_n}<_𝙱𝖬_V,n,`$ and the same for countably coinitial cuts.

This theorem, which explains the $`_{𝙲𝙳}`$-structure of monadic equivalence relations, will be the focal point in the remainder. According to the theorem, countably determined monadic ERs form two distinct linearly $`_{𝙲𝙳}`$-(pre) ordered domains, one of which contains countably cofinal and the other one countably coinitial ERs, each has slow ERs as the $`_{𝙲𝙳}`$-least element, and there is no $`_{𝙲𝙳}`$-connection between them except that any slow countably cofinal ER (it is necessarily CD-smooth) is $`_{𝙲𝙳}`$-reducible to any countably coinitial ER. In addition, each of the domains is neither countably $`_{𝙲𝙳}`$-cofinal nor countably $`_{𝙲𝙳}`$-coinitial in its fast part. (It can be shown that each of the domains is also dense and countably saturated, i.e., contains no gaps of countable character.)

The proof begins with a couple of auxiliary results.

## 9 Two preliminary facts

The first result will be a connection between monadic ERs and certain natural equivalence relations on dyadic sequences. Let $`𝕊`$ be the (internal) set of all internal sequences $`\phi {}_{}{}^{^{}}2`$ such that the set $`\{a:\phi (a)=1\}`$ is hyperfinite.

Consider an additive cut $`\mathrm{}U^{}.`$ Then $`\mathrm{log}U=\{a^{}:2^aU\}`$ is still a cut ( not necessarily additive). Define the equivalence relation $`𝖱_{\mathrm{log}U}`$ on $`𝕊`$ as follows: $`\phi 𝖱_{\mathrm{log}U}\psi `$ iff $`\phi (^{}\mathrm{log}U)=\psi (^{}\mathrm{log}U).`$ The relation $`𝖱_{\mathrm{log}U}`$ can be viewed as the restriction of $`\text{D}_{\text{ext}}({}_{}{}^{^{}\mathrm{log}U}2)`$ (Section 2) to $`𝕊.`$

###### Proposition 9.1.

In this case, $`𝖬_U_𝙱𝖱_{\mathrm{log}U}`$.

###### Proof.

For any $`x^{}`$ there is a unique $`\sigma =\sigma _x𝕊`$ with $`x=_z^{}2^z\sigma (z)`$ in $`^{}.`$ (The essential domain of summability here is a hyperfinite set because $`\sigma 𝕊.`$) The map $`x\sigma _x`$ is not yet a reduction of $`𝖬_U`$ to $`𝖱_{\mathrm{log}U}`$ because of a little discrepancy. Let $`𝕊_{\mathrm{log}U}`$ be the set of all $`\sigma 𝕊`$ which are not eventually $`1`$ in $`\mathrm{log}U,`$ i.e., the set $`\{a\mathrm{log}U:\sigma (a)=0\}`$ is cofinal in $`\mathrm{log}U.`$ Let $`\mathrm{\Omega }_{\mathrm{log}U}`$ be the set of all $`x^{}`$ such that $`\sigma _x𝕊_{\mathrm{log}U}.`$

We assert that $`x𝖬_Ux^{}\sigma _x𝖱_{\mathrm{log}U}\sigma _x^{}`$ for all $`x,x^{}\mathrm{\Omega }_{\mathrm{log}U}.`$ (Consider any $`x<x^{}`$ in $`\mathrm{\Omega }_{\mathrm{log}U}.`$ If $`d=x^{}xU`$ then $`d<2^a`$ for some $`a\mathrm{log}U.`$ As $`\sigma _x𝕊_{\mathrm{log}U},`$ there is $`b\mathrm{log}U,b>a,`$ with $`\sigma _x(b)=0.`$ But easily $`\sigma _x(z)=\sigma _x^{}(z)`$ for any $`z>b,`$ hence, $`\sigma _x𝖱_{\mathrm{log}U}\sigma _x^{}.`$ The converse is obvious.)

Yet for any $`x\mathrm{\Omega }_{\mathrm{log}U}`$ there is $`\stackrel{~}{x}\mathrm{\Omega }_{\mathrm{log}U}`$ with $`|x\stackrel{~}{x}|U:`$ put $`\stackrel{~}{x}=x+2^{a+1},`$ where $`a`$ is the largest number in $`\mathrm{log}U`$ with $`\sigma _x(a)=0.`$ For $`x\mathrm{\Omega }_{\mathrm{log}U}`$ put $`\stackrel{~}{x}=x.`$ The map $`\vartheta (x)=\sigma _{\stackrel{~}{x}}`$ is a Borel reduction of $`𝖬_U`$ to $`𝖱_{\mathrm{log}U}.`$

Finally, the map $`f(\sigma )=_z^{}2^{2z}\sigma (z)`$ is a reduction of $`𝖱_{\mathrm{log}U}`$ to $`𝖬_U.`$ (The factor $`2`$ in $`2z`$ helps to avoid the trouble with values $`\mathrm{\Omega }_{\mathrm{log}U}.`$)

###### Remark 9.2.

Choose $`d\mathrm{log}U.`$ A slight modification of the same argument proves that $`𝖬_U_𝙱\text{D}_{\text{ext}}({}_{}{}^{dU}2)\times \text{D}(^{}).`$ ($`d=[0,d),`$ as usual.)

An obvious case when $`\{a_n\}\{b_k\}`$ for increasing sequences is when $`a_{n+1}a_nb_{n+1}b_n`$ for all $`n.`$ The following result shows that this case essentially exhausts all cases of $`\{a_n\}\{b_k\}.`$ Say that two increasing sequences $`\{a_n\}`$ and $`\{\alpha _n\}`$ are cofinally equivalent if $`\mathbf{}\{a_n\}=\mathbf{}\{\alpha _n\}.`$ Say that two decreasing sequences $`\{a_n\}`$ and $`\{\alpha _n\}`$ are coinitially equivalent if $`\mathbf{}\{a_n\}=\mathbf{}\{\alpha _n\}.`$

###### Proposition 9.3.

Any two increasing sequences $`\{a_n\},\{b_k\}`$ are $``$-comparable, in addition, if $`\{a_n\}\{b_k\}`$ then there are sequences $`\{\alpha _n\},\{\beta _k\},`$ cofinally equivalent to, resp., $`\{a_n\},\{b_k\},`$ with $`\beta _{n+1}\beta _n\alpha _{n+1}\alpha _n`$ for all $`n.`$

Similarly, any two decreasing sequences $`\{a_n\},\{b_k\}`$ are $``$-comparable, in addition, if $`\{a_n\}\{b_k\}`$ then there are sequences $`\{\alpha _n\},\{\beta _k\},`$ coinitially equivalent to resp. $`\{a_n\},\{b_k\},`$ such that $`\beta _n\beta _{n+1}\alpha _n\alpha _{n+1}`$ for all $`n.`$

###### Proof.

We concentrate on the case of increasing sequences, the case of decreasing sequences is similar. The conjunction of two symmetric forms of ($`\neg \mathrm{\hspace{0.25em}3}`$) is obviously contradictory, which implies the $``$-comparability assertion.

Put $`k_0=0`$ and choose $`n_0`$ in accordance with (3), thus,

$$n^{}>n_0k^{}>k_0\left(a_n^{}a_{n_0}b_k^{}b_{k_0}\right).$$
($`5.0`$)
If (Case 1) we also have $`k^{}>k_0n^{}>n_0\left(a_n^{}a_{n_0}b_k^{}b_{k_0}\right),`$ then the sequences $`\{a_{n_0+i}\}_i`$ and $`\{a_{n_0}+b_{k_0+i}b_{k_0}\}_i`$ are cofinally equivalent, hence, $`\alpha _i=a_{n_0}+b_{k_0+i}b_{k_0}`$ and $`\beta _i=b_{k_0+i}`$ prove the lemma. Otherwise (Case 2) there is $`k_1>k_0`$ such that $`a_n^{}a_{n_0}<b_{k_1}b_{k_0}`$ for all $`n^{}>n_0.`$ Choose $`n_1>n_0`$ so that, by (3),

$$n^{}>n_1k^{}>k_1\left(a_n^{}a_{n_1}b_k^{}b_{k_1}\right).$$
($`5.1`$)
If we have now Case 1, i.e., symmetrically, $`k^{}>k_1n^{}>n_1\left(a_n^{}a_{n_1}b_k^{}b_{k_1}\right),`$ then, as above, the lemma holds immediately. Thus, we can assume that there is $`k_2>k_1`$ with $`a_n^{}a_{n_1}<b_{k_2}b_{k_1}`$ for all $`n^{}>n_1.`$ Choose $`n_2>n_1`$ following (3). And so on.

In the course of this construction, either the required result comes up just at some step, or we obtain increasing sequences $`\{n_i\}`$ and $`\{k_i\}`$ such that $`a_n^{}a_{n_i}b_{k_{i+1}}b_{k_i}`$ for all $`n^{}>n_i`$ and $`i.`$ Let $`\alpha _i=a_{n_i},\beta _i=b_{k_i}`$.

## 10 Countably cofinal monadic relations

The goal of this section is to prove the part of (i) of Theorem F related to countably cofinal cuts and associated monadic equivalence relations.

Choose increasing sequences $`\{a_n\},\{b_k\}`$ in $`^{}`$ with $`U=\mathbf{}\{2^{a_n}\}`$ and $`V=\mathbf{}\{2^{b_k}\}.`$ (Note that $`\mathrm{log}U=\mathbf{}\{a_n\}`$ and $`\mathrm{log}V=\mathbf{}\{b_k\}.`$) We are going to prove that $`𝖬_U_{𝙲𝙳}𝖬_V`$ iff $`𝖬_U_𝙱𝖬_V`$ iff $`UV;`$ the $`_𝙱`$-comparability of $`𝖬_U,𝖬_V`$ then immediately follows from Proposition 9.3.

Part 1. Suppose that $`𝖬_U_{𝙲𝙳}𝖬_V.`$ Then $`𝖱_{\mathrm{log}U}_{𝙲𝙳}𝖱_{\mathrm{log}V}`$ by Proposition 9.1. Let $`\vartheta :𝕊𝕊`$ be a CD reduction of $`𝖱_{\mathrm{log}U}`$ to $`𝖱_{\mathrm{log}V},`$ thus, $`\phi 𝖱_{\mathrm{log}U}\phi ^{}`$ iff $`\vartheta (\phi )𝖱_{\mathrm{log}V}\vartheta (\phi ^{})`$ for all $`\phi ,\phi ^{}𝕊.`$ The graph of $`\vartheta `$ has the form $`_{fF}C_f,`$ where $`F{}_{}{}^{}2`$ and $`C_f=_mC_{fm}`$ for any $`f{}_{}{}^{}2,`$ sets $`C_s,s{}_{}{}^{<\omega }2,`$ are internal, and $`C_tC_s𝕊\times 𝕊`$ for $`st,`$ as in () of Section 1.

Suppose, towards the contrary, that $`\{a_n\}\preccurlyeq ̸\{b_k\},`$ hence, we have ($`\neg \mathrm{\hspace{0.25em}3}`$).

Suppose that $`fF.`$ Then $`C_f`$ is a subset of the graph of $`\vartheta ,`$ hence, by the choice of $`\vartheta ,`$ for any $`k`$ we have, for all $`\phi ,\phi ^{},\psi ,\psi ^{}𝕊,`$

$$m(\phi C_{fm}\psi \phi ^{}C_{fm}\psi ^{})\psi _{b_k}=\psi ^{}_{b_k}n(\phi _{a_n}=\phi ^{}_{a_n}),$$

where $`\sigma _c=\sigma (^{}[0,c))`$ for $`\sigma 𝕊`$ and $`c^{}.`$ Then, by Saturation,

$$\begin{array}{c}knm\phi ,\phi ^{},\psi ,\psi ^{}𝕊:\hfill \\ \hfill \phi C_{fm}\psi \phi ^{}C_{fm}\psi ^{}\psi _{b_k}=\psi ^{}_{b_k}\phi _{a_n}=\phi ^{}_{a_n}.\end{array}$$
(6)
A similar (symmetric) argument also yields the following:

$$\begin{array}{c}nkm\phi ,\phi ^{},\psi ,\psi ^{}𝕊:\hfill \\ \hfill \phi C_{fm}\psi \phi ^{}C_{fm}\psi ^{}\phi _{a_n}=\phi ^{}_{a_n}\psi _{b_k}=\psi ^{}_{b_k}.\end{array}$$
(7)
To derive a contradiction to ($`\neg \mathrm{\hspace{0.25em}3}`$), note first of all that $`\mathbf{}\{a_n\}`$ is a fast cut assuming ($`\neg \mathrm{\hspace{0.25em}3}`$), thus, we can suppose that $`a_{n+1}a_n`$ is infinitely large for all $`n`$ (Lemma 8.1). Now, let $`k`$ witness ($`\neg \mathrm{\hspace{0.25em}3}`$). Let $`n,m`$ be numbers defined for this $`k`$ by (6). Choose $`n^{}>n`$ according to ($`\neg \mathrm{\hspace{0.25em}3}`$): then $`a_n^{}a_n>b_k^{}b_k`$ for any $`k^{}>k,`$ hence, in fact, $`a_n^{}a_n>\mathrm{}+b_k^{}b_k`$ for any $`m^{}>m`$ and any $`\mathrm{}.`$ Finally, choose $`k^{}>k`$ and $`m^{}>m`$ according to (7) but w. r. t. $`n^{}.`$ Put $`C(f)=C_{fm^{}}.`$ Then we have, for all $`\phi ,\psi ,\phi ^{},\psi ^{}`$ in $`C(f):`$

$$\begin{array}{ccccc}\psi _{b_k}=\psi ^{}_{b_k}& & \phi _{a_n}=\phi ^{}_{a_n}& ,& \text{and}\\ \psi _{b_k^{}}\psi ^{}_{b_k^{}}& & \phi _{a_n^{}}\phi ^{}_{a_n^{}}& & \end{array}\}.$$
(8)
We have $`𝕊=𝚍𝚘𝚖\vartheta =_{fF}X(f),`$ hence, by Saturation, there is a finite set $`F^{}F`$ such that still $`𝕊=_{fF^{}}X(f).`$ On the other hand, let us show that all sets $`X(f)`$ are too small for a finite union of them to cover $`𝕊.`$ Call an internal set $`X𝕊`$ small iff

1. there is a number $`h^{}`$ such that, for any internal map $`\sigma {}_{}{}^{^{}[0,h)}2`$ the set $`X_\sigma =\{\phi X:\phi _h=\tau \}`$ satisfies $`2^h\mathrm{\#}X_\sigma 0.`$

###### Proposition 10.1.

$`𝕊`$ is not a union of finitely many small internal sets.

It remains to show that any set $`X(f)`$ is small, with $`h=a_n^{}`$ in the notation above. (Note that $`a_n^{}`$ depends on $`f,`$ of course.) Take any $`\phi ,\psi C(f)`$ and let $`\sigma =\phi _{a_n^{}},\tau =\psi _{b_k^{}}.`$ By (8), each $`\phi ^{},\psi ^{}C(f)`$ with $`\phi ^{}_{a_n^{}}=\sigma `$ satisfies $`\psi ^{}_{b_k^{}}=\tau .`$ Let us divide the domain $`\mathrm{\Psi }=\{\psi ^{}𝕊:\psi ^{}_{b_k^{}}=\tau \}`$ onto subsets $`\mathrm{\Psi }_w=\{\psi ^{}\mathrm{\Psi }:\psi ^{}[b_k,b_k^{})=w\},`$ where $`w{}_{}{}^{[b_k,b_k^{})}2`$ (i.e., $`w`$ is an internal map $`[b_k,b_k^{})2`$), totally $`2^{b_k^{}b_k}`$ of the sets $`\mathrm{\Psi }_w.`$ For any such $`\mathrm{\Psi }_w,`$ the set $`\mathrm{\Phi }_w=\{\phi ^{}:\psi ^{}\mathrm{\Psi }_w\phi ^{},\psi ^{}C(f)\}`$ contains at most $`2^{a_n}`$ elements by the first implication in (8), therefore, the whole set $`X(f)_\sigma =\{\phi ^{}X(f):\phi ^{}_{a_n^{}}=\sigma \}`$ contains at most $`2^{a_n+b_k^{}b_k}`$ elements of the set $`X(f),`$ which is less than $`2^{a_n^{}\mathrm{}}`$ for any $`\mathrm{},`$ hence, $`X(f)`$ is small, as required.

Part 2. Suppose that $`\{a_n\}\{b_k\},`$ i.e., (3), and derive $`𝖱_{\mathrm{log}U}_𝙱𝖱_{\mathrm{log}V}.`$ We can assume, by Proposition 9.3, that $`a_{n+1}a_nb_{n+1}b_n`$ for all $`n.`$ By Robinson’s lemma, there is a number $`N^{}`$ and internal extensions $`\{a_\nu \}_{\nu N}`$ and $`\{b_\nu \}_{\nu N}`$ of sequences $`\{a_n\}_n`$ and $`\{b_n\}_n,`$ both being increasing hyperfinite sequences satisfying $`a_{\nu +1}a_\nu b_{\nu +1}b_\nu `$ for all $`\nu <N.`$ Now we are ready to define a Borel reduction $`\vartheta `$ of $`𝖱_{\mathrm{log}U}`$ to $`𝖱_{\mathrm{log}V}`$.

If $`\phi 𝕊`$ then define $`\vartheta (\phi )=\psi 𝕊`$ as follows:

1. $`\psi [0,b_0)`$ is constant $`0`$ (not important);
2. $`\psi (b_\nu +h)=\phi (a_\nu +h)`$ whenever $`\nu <N`$ and $`h<a_{\nu +1}a_\nu `$;
3. $`\psi [b_\nu +a_{\nu +1}a_\nu ,b_{\nu +1})`$ is constant $`0`$ for any $`\nu <N`$;
4. $`\psi (b_N+z)=\phi (a_N+z)`$ for all $`z^{}`$.

Thus, to define $`\psi ,`$ we move each piece $`\phi [a_\nu ,a_{\nu +1})`$ of $`\phi `$ so that it begins with $`b_\nu `$-th position in $`\psi ,`$ and fill the rest of $`[b_\nu ,b_{\nu +1})`$ by 0s; in addition, $`\psi [b_N,\mathrm{})`$ is a shift of $`\phi [p_N,\mathrm{}).`$ That $`\vartheta `$ is a Borel reduction of $`𝖱_{\mathrm{log}U}`$ to $`𝖱_{\mathrm{log}V}`$ is a matter of routine verification.

## 11 Countably coinitial monadic relations

That the double equivalence $`𝖬_U_𝙱𝖬_V𝖬_U_{𝙲𝙳}𝖬_VUV`$ of (i) of Theorem F holds for any pair of countably coinitial cuts can be verified the same way as for countably cofinal cuts in Section 10 (with rather obvious amendments which account for the fact that now decreasing rather than increasing sequences $`\{a_n\},\{b_k\}`$ are considered). We leave this to the reader, and concentrate, in this section, on (ii) (the incomparability between countably cofinal and countably coinitial ERs), except for its Borel part.

Suppose that $`U=\mathbf{}\{2^{a_n}\}`$ and $`V=\mathbf{}\{2^{b_k}\},`$ where $`\{a_n\}`$ and $`\{b_k\}`$ are resp. (strictly) increasing and decreasing sequences of hyperintegers. Note that then $`\mathrm{log}U=\mathbf{}\{a_n\}`$ and $`\mathrm{log}V=\mathbf{}\{b_k\}`$.

Part 1. Assuming that $`\{a_n\}`$ is fast, prove that $`𝖬_U_{𝙲𝙳}𝖬_V.`$ We have a more general result: $`𝖬_U_{𝙲𝙳}𝖤`$ for any $`\mathrm{\Pi }_1^0`$ equivalence relation $`𝖤`$ on $`^{}.`$ It suffices (Proposition 9.1) to show that $`𝖱_{\mathrm{log}U}_{𝙲𝙳}𝖤.`$ Suppose, towards the contrary, that $`\vartheta :𝕊^{}`$ is a CD reduction of $`𝖱_{\mathrm{log}U}`$ to $`𝖤,`$ so that $`\phi 𝖱_{\mathrm{log}U}\phi ^{}\vartheta (\phi )𝖤\vartheta (\phi ^{})`$ for all $`\phi ,\phi ^{}𝕊.`$ The graph of $`\vartheta `$ has the form $`_{fF}C_f,`$ where $`F{}_{}{}^{}2`$ and $`C_f=_mC_{fm}`$ for any $`f,`$ all sets $`C_s,s{}_{}{}^{<\omega }2,`$ are internal, and $`C_tC_s𝕊\times ^{}`$ whenever $`st.`$ Let $`𝖤=_kE_k,`$ where $`E_k`$ are internal sets and $`E_{k+1}E_k`$ for all $`k.`$ As $`\{a_n\}`$ is fast, we can assume that $`a_{n+1}a_n`$ is infinitely large for any $`n`$ (Lemma 8.1).

By the choice of $`\vartheta ,`$ for any $`fF`$ we have:

$$\begin{array}{c}\phi ,\phi ^{}𝕊x,x^{}^{}:m(\phi C_{fm}x\phi ^{}C_{fm}x^{})\hfill \\ \hfill (n(\phi _{a_n}=\phi ^{}_{a_n})k(xE_kx^{})).\end{array}$$
(9)
Applying Saturation here, with the implication $``$ in the equivalence in the second line, we obtain numbers $`m,n,k`$ (which depend on $`f`$) such that

$$\phi C_{fm}x\phi ^{}C_{fm}x^{}xE_kx^{}\phi _{a_n}=\phi ^{}_{a_n}$$

for all $`\phi ,\phi ^{}𝕊`$ and $`x,x^{}^{}.`$ Further, applying Saturation to (9) with the implication $``$ in the second line, with fixed numbers $`k`$ and $`n+1,`$ we find $`m^{}(f)m`$ such that, for all $`\phi ,\phi ^{}𝕊`$ and $`x,x^{}^{},`$

$$\phi C_{fm^{}(f)}x\phi ^{}C_{fm^{}(f)}x^{}\phi _{a_{n+1}}=\phi ^{}_{a_{n+1}}xE_kx^{}.$$

Let $`X(f)=𝚍𝚘𝚖C_{fm^{}(f)}.`$ It follows from the choice of $`m^{}(f)`$ that

$$\phi ,\phi ^{}X(f):\phi _{a_{n+1}}\phi ^{}_{a_{n+1}}\phi _{a_n}=\phi ^{}_{a_n},$$

therefore, $`X(f)`$ is small (see the definition before Proposition 10.1) because $`a_{n(f)+1}a_{n(f)}`$ is infinitely large. This leads to a contradiction as in Section 10.

Part 2. Prove that $`𝖬_V_{𝙲𝙳}𝖬_U`$ in any case. First of all, we can assume that $`V`$ is a slow countably coinitial cut, because if $`V`$ is such while $`V^{}`$ any countably coinitial cut then $`𝖬_V_{𝙲𝙳}𝖬_V^{}`$ by (i) of Theorem F. Thus, let $`V=\mathbf{}\{2^{dk}\}=_k[0,2^{dk}),`$ where $`d^{};`$ then $`\mathrm{log}V=\mathbf{}\{b_k\}=_k[0,dk).`$ It suffices to prove that $`𝖱_{\mathrm{log}V}_{𝙲𝙳}𝖬_U`$ (Proposition 9.1). We show that, even more, $`𝖱_{\mathrm{log}V}_{𝙲𝙳}𝖤`$ for any $`\mathrm{\Sigma }_1^0`$ equivalence relation $`𝖤`$ on $`^{}.`$

Suppose, on the contrary, that $`𝖱_{\mathrm{log}V}_{𝙲𝙳}𝖤.`$

Consider an auxiliary equivalence relation $`𝖱,`$ defined on $`\mathrm{\Xi }={}_{}{}^{d}2`$ (all internal maps $`d=[0,d)2`$) as follows: $`\sigma 𝖱\tau `$ iff $`\sigma d\mathrm{log}V=\tau d\mathrm{log}V.`$ 555 Thus, $`𝖱`$ is $`\text{D}_{\text{ext}}({}_{}{}^{\{dk:k\}}2),`$ see Section 2, which is isomorphic to just $`\text{D}_{\text{ext}}({}_{}{}^{}2)`$ on $`\mathrm{\Xi }`$ via the bijection $`\{i_z\}_{z<d}\{i_{d1z}\}_{z<d}`$ of $`\mathrm{\Xi }.`$ In terms of this bijection, the partition of $`\mathrm{\Xi }`$ into $`𝖱`$-classes is equal to the partition onto into $`d`$-monads $`M_g^d`$ as in Section 5. For any $`\sigma \mathrm{\Xi }`$ let $`\stackrel{~}{\sigma }𝕊`$ be its extension by 0s. The map $`\sigma \stackrel{~}{\sigma }`$ is a reduction of $`𝖱`$ to $`𝖱_{\mathrm{log}V},`$ hence, in our assumptions, $`𝖱_{𝙲𝙳}𝖤.`$ Let $`\vartheta :\mathrm{\Xi }^{}`$ be a CD reduction of $`𝖤`$ to $`𝖱_{\mathrm{log}U}.`$ Then $`\vartheta =_{fF}_mC_{fm},`$ where $`F{}_{}{}^{}2`$ while $`C_s,s{}_{}{}^{<\omega }2,`$ are internal subsets of $`\mathrm{\Xi }\times ^{}`$ with $`C_sC_t`$ whenever $`ts.`$ Finally, let $`𝖤=_nE_n,`$ where $`E_n^{}\times ^{}`$ are internal sets and $`E_nE_{n+1},n`$.

For any $`fF,`$ we have, by the choice of $`\vartheta ,`$

$$\begin{array}{c}\sigma ,\sigma ^{}\mathrm{\Xi }x,x^{}^{}:\hfill \\ \hfill m(\sigma C_{fm}x\sigma ^{}C_{fm}x^{})k(\sigma _{dk}=\sigma ^{}_{dk})n(xE_nx^{}),\end{array}$$
(10)
where $`\sigma _{dk}=\sigma [dk,d).`$ Using Saturation, we obtain numbers $`k=k(f),n=n(f),m=m(f)`$ such that

$$\sigma C_{fm}x\sigma ^{}C_{fm}x^{}\sigma _{dk(f)}=\sigma ^{}_{dk(f)}xE_nx^{}.$$
(11)
We put $`C(f)=C_{fm(f)}`$ and $`R(f)=𝚛𝚊𝚗C(f).`$ It follows from (11) that the set $`R(f)`$ can contain at most $`2^{k(f)},`$ a finite number, of pairwise $`𝖤`$-inequivalent elements (because so is the number of all restrictions $`\sigma _{dk(f)},\sigma \mathrm{\Xi }`$). On the other hand, since the graph of $`\vartheta `$ is covered by countably many sets of the form $`C(f),`$ the full image $`𝚛𝚊𝚗\vartheta =\{\vartheta (\sigma ):\sigma \mathrm{\Xi }\}`$ is covered by countably many sets of the form $`R(f)`$ (even if $`F`$ itself is uncountable), so that $`𝚛𝚊𝚗\vartheta `$ contains only countably many pairwise $`𝖤`$-inequivalent elements. Yet $`𝖱`$ admits continuum-many pairwise $`𝖱`$-inequivalent elements in $`\mathrm{\Xi },`$ contradiction.

## 12 Remaining parts of the theorem on monadic ERs

To check that $`\text{D}(^{})_𝙱𝖬_U`$ for any additive countably determined cut $`U,`$ choose a number $`cU;`$ then $`xxc`$ is a Borel reduction of $`\text{D}(^{})`$ to $`𝖬_U,`$ in other words, $`x=x^{}`$ iff $`xc𝖬_Ux^{}c.`$ This argument works for both countably cofinal and countably coinitial cuts $`U.`$

We continue with the following result, which proves the $`_𝙱`$-statement in (ii) of Theorem F and ends the proof of (ii) of Theorem F in general.

###### Lemma 12.1.

If $`U`$ is an additive countably cofinal cut and $`𝖤`$ a $`\mathrm{\Pi }_1^0`$ equivalence relation then $`𝖬_U_𝙱𝖤`$.

It follows that $`𝖬_U_𝙱𝖬_V`$ provided $`V`$ is any countably coinitial cut.

###### Proof.

We know that $`U`$ (Remark 8.2), hence, it can be assumed that $`U=.`$ Let $`𝖤=_nE_n,`$ each $`E_n^{}`$ internal and $`E_{n+1}E_n,n.`$ Fix $`c^{}`$ and let $`\vartheta :[0,c)^{}`$ be a Borel reduction of $`𝖬_{}[0,c)`$ to $`𝖤.`$ As any Borel (generally, any analytic) set, the graph of $`\vartheta `$ has the form $`_f{}_{}{}^{}_mC_{fm},`$ where $`{}_{}{}^{}`$ is the set of all $`\omega `$-sequences of natural numbers, all sets $`C_u[0,c)\times ^{},u{}_{}{}^{<\omega },`$ are internal, $`{}_{}{}^{<\omega }=`$ all finite sequences of natural numbers, and $`C_vC_u`$ whenever $`uv`$ (see ).

Applying a simple measure-theoretic argument, we can find a sequence of numbers $`\{j_m\}_m`$ in $``$ such that the set $`X=𝚍𝚘𝚖\vartheta ^{}`$ has Loeb measure $`\frac{1}{2},`$ where $`\vartheta ^{}=_{fF}_mC_{fm}`$ and $`F=\{f{}_{}{}^{}:m(f(m)j_m\}.`$ By Koenig’s lemma, $`\vartheta ^{}=_mC_m,`$ where $`C_m=_uC_u,`$ where the union is taken over all sequences $`u`$ of length $`m`$ such that $`u(k)j_k`$ for all $`k<m,`$ so that each $`C_m`$ is internal and (the graph of) $`\vartheta ^{}`$ is a $`\mathrm{\Pi }_1^0`$ set. Also, $`\vartheta ^{}=\vartheta X,`$ where $`X[0,c)`$ is a Borel set of Loeb measure $`\frac{1}{2}`$.

Since $`\vartheta `$ is a reduction (and $`\vartheta ^{}`$ a partial one), we have

$$\begin{array}{c}x,x^{}Xy,y^{}^{}:\hfill \\ \hfill m(xC_myx^{}C_my^{})(k(|xx^{}|<k)n(yE_ny^{})).\end{array}$$
(12)
Applying Saturation with $``$ instead of $``$ in the second line, we find numbers $`m,n,k`$ such that

$$x,x^{}Xy,y^{}^{}:xC_myx^{}C_my^{}yE_ny^{}|xx^{}|<k.$$

Applying Saturation with $``$ instead of $`,`$ and fixed numbers $`n`$ and $`4k,`$ we find a number $`m^{}m`$ such that

$$x,x^{}Xy,y^{}^{}:xC_m^{}yx^{}C_m^{}y^{}|xx^{}|<4kyE_ny^{}.$$

It follows that $`|xx^{}|<k|xx^{}|4k`$ holds for all $`x,x^{}X,`$ which contradicts the assumption that $`X`$ has measure $`\frac{1}{2}`$.

(iii) of Theorem F. Note that every CD-smooth ER is $`_{𝙲𝙳}`$-reducible to $`𝖬_{}`$ because $`\text{D}(^{})_𝙱𝖬_{},`$ see above. It follows, by (ii) of Theorem F already proved, that $`𝖬_V`$ is not CD-smooth (hence, not B-smooth), provided $`V`$ is an additive countably coinitial cut.

Let $`U=c`$ be a slow additive countably cofinal cut. Note that $`𝖬_{}`$ has a countably determined transversal $`A`$ by Theorem D. Then $`B=\{ac:aA\}`$ is obviously a CD transversal for $`𝖬_U,`$ hence, $`𝖬_U`$ is CD-smooth (use the map sending any $`x`$ to the only element of $`B`$ equivalent to $`x`$). If a countably cofinal cut $`U`$ is fast then $`U\preccurlyeq ̸`$ (say, by Lemma 8.1), the non-CD-smoothness of $`𝖬_U`$ follows as above for countably coinitial cuts.

That $`𝖬_U`$ is not B-smooth for any additive countably cofinal cut $`U`$ follows from Lemma 12.1.

Finally, (iv) of Theorem F. It suffices, by (i), to prove the following:

###### Lemma 12.2.

Suppose that, for any $`n,`$ $`\{a_k^n\}_k`$ is a fast increasing sequence. Then there are fast increasing sequences $`\{a_k\}`$ and $`\{b_k\}`$ such that $`\{a_k\}\{a_k^n\}_k\{b_k\}`$ for any $`n.`$ The same for fast decreasing sequences.

Here $`\{c_k\}\{d_k\}`$ means that $`\{c_k\}\{d_k\}`$ but $`\{d_k\}\preccurlyeq ̸\{c_k\}.`$

###### Proof.

In the case of increasing sequences, we can assume that $`d_k^n=a_{k+1}^na_k^n`$ is infinitely large for all $`n,k.`$ By countable Saturation, there are numbers $`a,b^{}`$ such that $`a<d_k^n<b`$ for all $`n,k.`$ Put $`a_k=k\sqrt{a}`$ and $`b_k=kb.`$

(Theorem F)

## 13 An upper bound for countably cofinal relations

In classical descriptive set theory, the equivalence relation $`𝖤_0,`$ defined on $`{}_{}{}^{}2`$ so that $`x𝖤_0y`$ iff $`x(n)=y(n)`$ for all but finite $`n,`$ plays a distinguished role in the structure of Borel ERs, in particular, because it is the least, in the sense of Borel reducibility, non-smooth Borel equivalence relation. It would be a rather bold prediction to expect any analogous result in the “nonstandard” setting, yet a reasonable nonstandard version of $`𝖤_0`$ attracts some interest, giving a natural upper bound for countably cofinal monadic ERs.

For $`\xi ,\eta 𝕊`$ define: $`\xi 𝖥𝖣\eta `$ iff $`\xi (x)=\eta (x)`$ for all but finite $`x^{}.`$ ($`𝖥𝖣`$ from “finite difference”.)

###### Lemma 13.1.

If $`U^{}`$ is an additive countably cofinal cut then $`𝖬_U_𝙱𝖥𝖣.`$ If $`V^{}`$ is an additive countably coinitial cut then $`𝖬_V_{𝙲𝙳}𝖥𝖣`$.

###### Proof.

That $`𝖬_V_{𝙲𝙳}𝖥𝖣`$ follows from the argument in Part 2 of Section 11 because $`𝖥𝖣`$ is obviously a $`\mathrm{\Sigma }_1^0`$ relation. As for the first statement, suppose that $`U=\mathbf{}\{2^{a_n}\},`$ where $`\{a_n\}`$ is an increasing sequence in $`^{};`$ accordingly, $`\mathrm{log}U=\mathbf{}\{a_n\}=_n[0,a_n).`$ It suffices to prove that $`𝖱_{\mathrm{log}U}_𝙱𝖥𝖣.`$

The sequence $`\{a_n\}`$ admits an internal $``$-extension $`\{a_\nu \}_{\nu N},`$ where $`N^{},`$ still an increasing hypersequence of elements of $`^{}.`$ Let, for any $`\phi 𝕊,`$ $`\vartheta (\phi )`$ be the (internal, hyperfinite) set of all restricted maps $`\phi [a_\nu ,\mathrm{}),\nu N,`$ where $`[a,\mathrm{})=^{}[0,a).`$ By definition, $`\phi 𝖱_{\mathrm{log}U}\psi `$ iff the symmetric difference $`\vartheta (\phi )\Delta \vartheta (\psi )`$ is finite. Yet $`\vartheta `$ takes values in the set of all hyperfinite subsets of a certain internal hyper-countable set (because $`𝕊`$ itself is hyper-countable) which can be identified with $`^{}`$.

###### Corollary 13.2.

If $`U`$ is as in the lemma then $`𝖬_U<_𝙱𝖥𝖣`$.

###### Proof.

Use the lemma and (iv) of Theorem F.

We don’t know whether $`𝖥𝖣`$ is an exact upper bound for countably cofinal monadic ERs, but still the lower $`_𝙱`$-cone of $`𝖥𝖣`$ contains many ERs not reducible to countably cofinal monadic ones, at least, all hyperfinite restrictions of $`𝖥𝖣`$ are such. For any hyperfinite set $`D^{}`$ let $`𝖥𝖣D`$ be the restriction of $`𝖥𝖣`$ to the domain $`({}_{}{}^{D}2){}_{\text{int}}{}^{},`$ so that $`\xi 𝖥𝖣D\eta `$ iff $`\{dD:\xi (d)\eta (d)\}`$ is finite. Easily $`𝖥𝖣D_𝙱𝖥𝖣,`$ moreover, $`𝖥𝖣D<_𝙱𝖥𝖣`$ because any possible CD reduction of $`𝖥𝖣`$ to $`𝖥𝖣D`$ must be a bijection on any set $`X𝕊`$ of pairwise $`𝖥𝖣`$-inequivalent elements, but we can take $`X`$ to be internal and hyper-infinite, which leads to contradiction because there is no CD injection from a hyper-infinite (internal) set in a hyperfinite set (say, by Lemma 4.1).

###### Theorem G.

If $`D`$ is an infinite hyperfinite set and $`U`$ an additive countably cofinal cut then $`𝖥𝖣D_{𝙲𝙳}𝖬_U`$.

###### Proof.

In the cource of the proof, it is more convenient to view $`𝖥𝖣D`$ as an equivalence on $`𝒫_{\mathrm{𝚒𝚗𝚝}}(D)`$ defined so that $`u𝖥𝖣Dv`$ iff $`u\Delta v`$ is finite. Let, on the contrary, $`\vartheta :𝒫_{\mathrm{𝚒𝚗𝚝}}(D)^{}`$ be a countably determined reduction of $`𝖥𝖣D`$ to $`𝖬_U.`$ Assume that $`D=[0,K)`$ for some $`K^{}.`$ The graph of $`\vartheta `$ has the form $`_{fF}_mP_{fm},`$ where $`F{}_{}{}^{}2`$ and $`P_s𝒫_{\mathrm{𝚒𝚗𝚝}}(D)\times ^{}`$ are as in () of Section 1. Let $`X_s=𝚍𝚘𝚖P_s`$ and $`X_f=𝚍𝚘𝚖P_f,`$ where $`P_f=_mP_{fm}`$.

Applying countable Saturation, we find a number $`\nu ^{}`$ which is less than $`K`$ and moreover, $`{}_{}{}^{}\rho (\nu )<K`$ for any standard recursive function $`\rho .`$ Say that a set $`Z𝒫_{\mathrm{𝚒𝚗𝚝}}(D)`$ is large if there is an internal set $`ID`$ such that $`\mathrm{\#}I=2\nu `$ and $`[I]^\nu Z,`$ where $`[I]^\nu `$ is the set of all internal subsets $`YI`$ with $`\mathrm{\#}Y=\nu .`$ Then it is a consequence of the Ramsey theorem (in the nonstandard domain) that, for any $`k`$ and any internal partition $`𝒫_{\mathrm{𝚒𝚗𝚝}}(D)=Z_1\mathrm{}Z_k`$ at least one of the sets $`Z_i`$ is large.

We observe that there is $`fF`$ such that all sets $`X_{fm}`$ are large. (Otherwise let $`X_{fm_f}`$ be non-large for any $`fF.`$ Since $`𝚍𝚘𝚖\vartheta =𝒫_{\mathrm{𝚒𝚗𝚝}}(D),`$ it follows from Saturation that $`𝒫_{\mathrm{𝚒𝚗𝚝}}(D)`$ is a finite union of non-large sets of the form $`X_{fm_f},`$ contradiction with the above.) Then, by Saturation, $`X_f`$ itself is large, so that there is an internal set $`IX_f`$ such that $`\mathrm{\#}I=2\nu `$ and $`[I]^\nu X_f.`$

Note that $`P_f\vartheta ,`$ hence, $`P_f`$ is a function, actually, $`P_f=\vartheta X_f.`$ In addition, by Saturation, there is $`n`$ such that $`\phi =P_{fn}`$ is already a function (internal). Then clearly $`P_f=\phi X_f,`$ therefore, $`\vartheta [I]^\nu =\phi [I]^\nu ,`$ which implies that $`\vartheta [I]^\nu `$ is an internal map. Use this fact to derive a contradiction.

Let $`I=\{a_1,\mathrm{},a_{2\nu }\}`$ in the increasing order. For any $`z=1,\mathrm{},\nu ,`$ let $`u_z=\{a_z,\mathrm{},a_{z+\nu 1}\}`$ and $`u_{\nu +z}=\{a_1,\mathrm{},a_{z1},a_{\nu +z},\mathrm{},a_{2\nu }\}`$ (in particular, $`u_{\nu +1}=\{a_{\nu +1},\mathrm{},a_{2\nu }\}`$). Put $`h_z=\vartheta (u_z).`$ Easily the sets $`u_z`$ are internal and $`\mathrm{\#}u_z=\nu `$ for all $`z,`$ moreover, $`\mathrm{\#}(u_z\Delta u_{z+1})=2,`$ hence, $`u_z𝖥𝖣Du_{z+1}`$ for each $`z<2\nu ,`$ so that $`|h_zh_{z+1}|U`$ because $`\vartheta `$ is a reduction, and, by the same reasons, $`|h_{2\nu }h_1|U.`$ On the other hand, $`\mathrm{\#}(u_1\Delta u_{\nu +1})=2\nu ,`$ hence, $`|h_1h_{\nu +1}|U.`$

To conclude, we have two hyperintegers $`h_1`$ and $`h_{\nu +1},`$ with $`|h_1h_{\nu +1}|U,`$ connected by two internal chains, $`h_1,h_2,\mathrm{},h_\nu ,r_{\nu +1}`$ and $`h_{\nu +1},\mathrm{},h_{2\nu },h_1,`$ in which each link has length in $`U.`$ Obviously there is an index $`z,\mathrm{\hspace{0.25em}1}<z\nu ,`$ such that $`|h_zh_{\nu +z}|U.`$ However by definition $`\mathrm{\#}(u_z\Delta u_{\nu +z})=2\nu ,`$ hence, $`|h_zh_{\nu +z}|U`$ for any $`z,`$ contradiction.

Thus, we have the following two classes of countably determined equivalence relations strictly $`_𝙱`$-below $`𝖥𝖣:`$ 1) ERs of the form $`𝖬_U,`$ where $`U^{}`$ is an additive countably cofinal cut, 2) ERs of the form $`𝖥𝖣[0,c),`$ where $`c^{}.`$ It follows from our analysis that there is no ER in the first class $`_{𝙲𝙳}`$-compatible with a ER in the second class. Is there anything below $`𝖥𝖣`$ essentially different from these two classes ?

## 14 Final remarks and problems

This final Section contains few scattered remarks and questions, mainly implied by analogies with “Polish” descriptive set theory.

Back to CD-cardinalities. Problem 5.1 (Section 5) is, perhaps, the most interesting. Our analysis in the end of Section 5 shows that, for $`M_G^d`$ to satisfy $`M_G^d_{𝙲𝙳}c/`$ it is necessary and sufficient that $`G{}_{}{}^{}2`$ is a set of Lebesgue measure $`0.`$ It is an interesting problem to find a reasonable necessary and sufficient condition for $`M_G^d`$ to satisfy $`M_G^d_{𝙲𝙳}c_{𝙲𝙳}[0,c).`$ Can $`M_G^d_{𝙲𝙳}[0,c)`$ hold in the case when $`\mathrm{}_0<𝚌𝚊𝚛𝚍G<2^\mathrm{}_0\mathrm{?}`$ Do these problems depend on the basic properties of the (standard) continuum in essential way ?

How many $`_𝙱`$-classes of Borel subsets of $`^{}`$ do exist ? 666 This question can be addressed to $`_{𝙲𝙳}`$-classes of CD sets as well, but perhaps it is premature to search for an answer until Problem 5.1 is solved. To answer such a question in the spirit of modern descriptive set theory, one has to define an equivalence relation, say, $`𝖤,`$ on $`^{}`$ (in the “Polish” DST, on a Polish space), whose equivalence classes naturally represent $`_𝙱`$-classes of Borel subsets of $`^{},`$ and classify $`𝖤`$ in terms of best known, “canonical” ERs (see ).

It follows from Theorem A that Borel subsets of $`^{}`$ are represented, modulo $`_𝙱,`$ by sets of the following three classes: 1) $`^{}`$ and cuts of the form $`c=[0,c),c^{};`$ 2) additive countably cofinal cuts; 3) additive countably coinitial cuts.

The first class naturally leads to $`_𝙱^{},`$ i.e., the relation on $`^{}`$ defined so that $`x_𝙱y`$ iff there is a Borel bijection of $`[0,x)`$ onto $`[0,y)`$ iff $`\frac{x}{y}1.`$ Can it be characterized in terms of exponential equalities $`\text{D}_{\text{ext}}({}_{}{}^{D}2),D^{}`$? We conjecture that the relation $`_𝙱^{}`$ is $`_𝙱`$-equivalent to $`\text{D}(^{})\times \text{D}_{\text{ext}}({}_{}{}^{}2).`$

To approach the second class, fix $`d^{}`$ and let $`D`$ be the set of all increasing internal maps $`\xi :d^{}`$ satisfying $`\xi (x+1)x\xi (x)`$ for all $`x<d1,`$ so that any additive countably cofinal cut $`U`$ has the form $`U=U(\xi )=_n\xi (n)`$ for some (not unique) $`\xi D.`$ Define $`\xi 𝖤\eta `$ iff $`U(\xi )=U(\eta ).`$ This is a $`\mathrm{\Pi }_2^0`$ equivalence; can it be described in terms of relations of the form $`\text{D}(X)`$ and $`\text{D}_{\text{ext}}({}_{}{}^{x}2)`$? Third class can be studied similarly, but with decreasing sequences and $`\xi (x+1)\xi (x)/x`$ for all $`x,`$ but does this lead to an equivalence relation $`_𝙱`$-equivalent to $`𝖤`$?

Exponential equalities. Recall that $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ is the equivalence relation of equality of internally extendable maps $`X2,`$ Section 2. This class of ERs contains, for instance, all monadic ERs (Proposition 9.1, it suffices to take complements of CD cuts as sets $`X`$), hence, study of its properties in terms of $`_{𝙲𝙳}`$ appears interesting and important. When $`\text{D}_{\text{ext}}({}_{}{}^{X}2)_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{Y}2)`$? The results for monadic ERs show that the answer has little to do with, for instance, the inclusion $`XY.`$ Our study of monadic equivalence relations can be rather routinely generalized on ERs $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ for sets $`X^{}`$ of classes $`\mathrm{\Sigma }_1^0`$ and $`\mathrm{\Pi }_1^0`$ (generalization of resp. countably coinitial and countably cofinal monadic ERs). For instance, it turns out that $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ is not CD-smooth for any non-internal $`\mathrm{\Sigma }_1^0`$ set $`X^{},`$ as well as for any non-internal $`\mathrm{\Pi }_1^0`$ set $`X^{}`$ not of the form $`HC,`$ where $`H`$ is internal and $`C`$ is countable. Is it true that $`\text{D}_{\text{ext}}({}_{}{}^{X}2)`$ is not CD-smooth for any set $`X^{}`$ not in $`\mathrm{\Pi }_1^0`$?

A hyperfinite continuum-hypothesis. Theorem B implies that, given $`c^{},`$ there is no regular (see Section 5) CD-cardinalities strictly between those of $`c/`$ and $`c`$ (it is a question whether there are singular ones there). Are there any other similar pairs in the $`_{𝙲𝙳}`$-structure ? A natural analogy with the continuum-hypothesis leads to the following question. Let $`U`$ be an additive CD cut in $`^{}.`$ (Or, generally, any CD subset of $`^{},`$ but then the problem is most likely more difficult.) Does there exist any countably determined ER $`𝖤`$ with $`\text{D}(U)<_{𝙲𝙳}𝖤<_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2)`$? Since $`\text{D}(U)`$ is the equality on $`U`$ while $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ is the equality of internally extendable maps $`U2,`$ the double inequality can be seen to represent the fact that the CD-cardinality of the quotient space of $`𝖤`$ is strictly between the CD-cardinality of $`U`$ and its natural “power cardinality”. This question deserves a brief consideration.

Let $`d^{}U,`$ so that $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ can be seen as the relation on $`{}_{}{}^{d}2`$ defined so that $`\xi \text{D}_{\text{ext}}({}_{}{}^{U}2)\eta `$ iff $`\xi U=\eta U.`$ That $`\text{D}(U)_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ can be witnessed by the map $`x\xi _x,`$ where $`\xi _x{}_{}{}^{d}2`$ is the characterictic function of the singleton $`\{x\}.`$ If $`U=HC,`$ where $`H`$ is internal while $`C`$ countable, then we can prove, using Lemma 4.1, that, paradoxically, $`\text{D}(U)_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2).`$ Otherwise (see a remark above) $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ is not CD-smooth, hence, $`\text{D}(U)<_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2)`$ strictly. Further, if there is $`cU`$ with $`2^cU`$ then easily there are plenty of numbers $`a<2^c,aU`$ with $`\text{D}(U)<_{𝙲𝙳}\text{D}(a)<_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2),`$ thus, the “continuum-hypothesis” fails.

Now suppose that $`U`$ is exponentially closed, so that $`cU2^cU.`$ Then (Lemma 4.1 applied) there is no CD set $`X^{}`$ with $`\text{D}(U)<_{𝙲𝙳}\text{D}(X)<_{𝙲𝙳}\text{D}_{\text{ext}}({}_{}{}^{U}2),`$ but is there any other countably determined ER $`𝖤`$ strictly $`_{𝙲𝙳}`$-between $`\text{D}(U)`$ and $`\text{D}_{\text{ext}}({}_{}{}^{U}2)`$?

Another family of equivalence relations. For any cut $`\mathrm{}U^{},`$ take $`cU`$ and define, for (internal) $`\xi ,\eta {}_{}{}^{c}2,`$ $`\xi 𝖥_U\eta `$ iff there are numbers $`aU`$ and $`bU,bc`$ such that $`\xi [a,b)=\eta [a,b).`$ If $`U`$ is countably determined then it belongs to $`\mathrm{\Sigma }_1^0\mathrm{\Pi }_2^0,`$ subsequently, $`𝖥_U`$ can be transformed to $`\mathrm{\Sigma }_2^0`$ using Saturation. Anything about the $`_{𝙲𝙳}`$-structure of this family ?

Smoothness and transversals. Our general method to establish smoothness was to find a suitable transversal. Recall, in this context, that $`𝖬_{}`$ admits a countably determined transversal by Theorem D, hence, is CD-smooth, but is not B-smooth (Lemma 12.1), hence, does not admit a Borel transversal. However the existence of a transversal is not a necessary condition for the smoothness. Indeed, there exist Borel and B-smooth equivalence relations which do not admit even a countably determined transversal ! An example can be easily extracted from the observation made in \[8, 4.8\] that there is a $`\mathrm{\Pi }_2^0`$ set in $`^{}\times ^{}`$ which does not admit a CD uniformization.

“Fine structure” of equivalence relations. Is the ER $`𝖥𝖣`$ defined in Section 13 in any sense $`_{𝙲𝙳}`$-minimal over countably cofinal monadic ERs ?

Is there any result analogous to the Glimm – Effros dichotomy (see  or ) of “Polish” descriptive set theory, in the same way as our Theorem E is analogous to the Silver – Burgess dichotomy ? We conjecture that any Borel equivalence relation $`𝖤`$ on $`^{}`$ is either B-smooth or satisfies $`𝖬_{}[0,c)_𝙱𝖤`$ for some $`c^{}`$ or satisfies $`\text{D}_{\text{ext}}({}_{}{}^{}2)_𝙱𝖤`$.

Theorem D says that any countable CD equivalence relation is CD-smooth. What is the $`_𝙱`$-structure of countable Borel ERs ?

Ergodic theory. Let $`c^{}.`$ The relation $`𝖬_{}[0,c)`$ on $`[0,c)`$ has certain similarities with the Vitali equivalence $`x𝖵𝖨𝖳y`$ iff $`xy`$ is rational on $`,`$ for instance, Borel non-smoothness, the nonexistence of Borel transversals, perhaps, the $`_𝙱`$-minimality amongst all non-smooth ERs. However $`𝖬_{}[0,c)`$ lacks the following relevant property of $`𝖵𝖨𝖳:`$ while every $`𝖵𝖨𝖳`$-invariant Borel subset of $``$ has Lebesgue measure $`0`$ or its complement has measure $`0,`$ there exist plenty of $`𝖬_{}`$-invariant Borel subsets of $`[0,c)`$ having Loeb measure, for instance, $`1/2:`$ just take the $`𝖬_{}`$-saturation of $`[0,\frac{c}{2}).`$ (We consider the Loeb measure associated with the counting measure $`\mu (X)=\frac{\mathrm{\#}X}{c}`$ for internal subsets of $`[0,c).`$) Are there naturally defined “nonstandard” ERs which, unlike $`𝖬_{},`$ satisfy this property ? Henson and Ross \[3, 2.3\] ask whether there exists a bijection$`f:[0,c)\stackrel{\mathrm{onto}}{}[0,c)`$ ergodic in the sense that for any Loeb measurable set $`X[0,c)`$ such that $`X\Delta f\text{}X`$ has Loeb measure $`0,`$ the set $`X`$ itself has Loeb measure either $`0`$ or $`1;`$ they prove that Borel bijections (i.e., with a Borel graph, as usual) are not ergodic.

Domain-independent version. Define $`𝖤_𝙱^{}𝖥`$ if $`𝖤\times \text{D}(^{})_𝙱𝖤\times \text{D}(^{}).`$ With this definition, we have, for instance, $`\text{D}(X)_𝙱^{}\text{D}(Y)`$ for any infinite hyperfinite $`X,Y,`$ and $`𝖬_{}a_𝙱^{}𝖬_{}b_𝙱^{}𝖬_{}`$ for any $`a,b^{},`$ leading to structures less contaminated by the dependence on the size of the domain.

There is another possible way to the same goal. Unlike the case of Polish spaces, it is not true in the nonstandard domain that any Borel-measurable function (i.e., here, it means that all preimages of internal sets are Borel) is Borel in the sense that its graph is Borel. It is known that, for rather good nonstandard universes, for instance, those satisfying the Isomorphism Property, for any two infinite hyperfinite sets $`X,Y`$ there is a bijection $`f:X\stackrel{\mathrm{onto}}{}Y`$ such that the images and preimages of internal sets are Borel. (Such a bijection cannot be even countably determined unless the fraction $`\frac{\mathrm{\#}X}{\mathrm{\#}Y}`$ is neither infinitesimal nor infinitely large.) As mentioned in , such a bijection induces an isomorphism of the entire structure of Borel and countably determined sets.

This naturally leads to the reducibility via Borel-measurable maps. Is $`𝖬_{}`$ Borel-measurable reducible to $`\text{D}(^{})`$ in a nonstandard universe satisfying the Isomorphism Property ?