compat=1.0.0

UMN-TH-4127/22

FTPI-MINN-22-18

Reevaluation of heavy-fermion-induced
electron EDM at three loops

Yohei Emaa, Ting Gaob, Maxim Pospelova,b

a | _William I. Fine Theoretical Physics Institute, School of Physics and Astronomy,_
---|---
| _University of Minnesota, Minneapolis, MN 55455, USA_
b | _School of Physics and Astronomy, University of Minnesota, Minneapolis, MN 55455, USA_

###### Abstract

Motivated by improved limits on electric dipole moments (EDMs), we revisit the
three-loop light-by-light mechanism that transmits $CP$ violation from a heavy
fermion to a light one. Applying it to the electron EDM induced by EDMs of
heavier flavors, we find additional contributions at the order $m_{e}/m_{\mu}$
or $m_{e}/m_{\tau}$ that were missing before and that make the result 1.4
times larger. Consequently we improve bounds on the tau EDM, and update
indirect limits on the muon EDM as well as charm and bottom quark color EDMs.

##  1 Introduction

Searches for electric dipole moments (EDMs) have been a powerful probe of
fundamental symmetry violation since the first proposal by Purcell and Ramsey
in the 1950s[1]. While a nonzero EDM of elementary particles has not yet been
detected, one can expect new EDM experiments to continue improving
sensitivity, eventually reaching benchmark values suggested by the Standard
Model (SM) (see e.g. recent reevaluation in Ref. [2]). This situation makes
EDM experiments sensitive to new physics, and specifically to new sources of
CP violation beyond the SM.

In the lepton sector, the electron EDM has been in the focus of experimental
and theoretical attention for several decades. The stable nature of electrons
makes it possible to probe its EDM directly in paramagnetic atoms and
molecules[3]. There is also rising interest to muon EDM due to the muon $g-2$
anomaly [4, 5, 6]. Muon EDM can be directly measured in storage ring
experiments[7, 8, 9, 10, 11], and indirectly constrained [12] using atomic and
molecular EDM experiments [13, 3].

Direct measurement of tau-lepton EDM is difficult due to its short lifetime,
so the knowledge of tau EDM mostly comes from measurements of tau pair-
production. At present the best constraint is inferred from the CP-violating
effects in $e^{+}e^{-}\to\tau^{+}\tau^{-}$ at the Belle Collaboration[14]

$\displaystyle\text{Re}(d_{\tau})=\left(1.15\pm 1.70\right)\times
10^{-17}e\,\text{cm},$ (1) $\displaystyle\text{Im}(d_{\tau})=\left(-0.83\pm
0.86\right)\times 10^{-17}e\,\text{cm}.$

More details on the current status of tau EDM search can be found in [15] and
references therein.

A non-zero heavy fermion EDM, through loops, can induce EDMs of lighter
fermions. It is first shown by Grozin, Khriplovich, and Rudenko in [16] that
heavy leptons (muon and tau lepton) can induce electron EDM at
$\alpha_{\text{EM}}^{3}$ order. (Here the subscript EM stands for
electromagnetic.) In this way [16] puts indirect constraints on heavy lepton
EDM based on electron EDM experiments. The purpose of this paper is to revisit
this calculation and to correct an omission made in the previous work [16].
Specifically, we will show that there is a contribution from the same set of
diagrams in [16] that was missing before, and this new term enhances the
previous result by $\sim 40\%$. Based on this updated calculation and the
improved precision of paramagnetic EDM experiments, we provide a new indirect
limit on tau EDM. As a by-product of this calculation, we also update our
previous constraints on muon EDM [12] and provide constraints on heavy quark
color EDM (CEDM) based on light quark EDM.

##  2 Evaluation of EDM light-by-light diagrams

In this section we reevaluate the heavy lepton induced electron EDM at three-
loop. A total number of 24 diagrams contributes, including the diagrams in
Fig. 1 and their permutations.

Figure 1: Examples of three-loop QED diagram for heavy lepton EDM contribution
to electron EDM. The upper fermion line represents the electron and the lower
fermion loop is formed by the heavy lepton. The crossed dot is the EDM vertex
and replaces one of the 4 regular EM vertices on the heavy lepton loop. The
three photon lines connecting the heavy lepton loop and electron line have 6
possible permutations. Figure 2: An example of related diagrams.

To get the EDM operator we expand the amplitude up to linear order in the
external photon momentum $q$. While full expression for arbitrary mass
hierarchy can be found following [17], in practice we would like to explore
the smallness of electron mass compared to a fermion mass inside the closed
loop. Thus, observing that $m_{l}/m_{L}\ll 1$, where $l=e$ refers to the
electron, and $L=\mu,\tau$ refers to heavy leptons, we evaluate the amplitude
up to leading order in $m_{l}/m_{L}$. Noticing that on account of Dirac
equation $\left(\not{p}-m_{l}\right)l(p)=0$, the expansion in $m_{l}$ needs to
be accompanied with an expansion in $p$. So most generally, after the
expansion one would get an expression of the following form:

$\mathcal{M}=-im_{l}q^{\alpha}A^{\beta}\bar{l}S_{\alpha\beta}^{(1)}l-ip^{\rho}q^{\alpha}A^{\beta}\bar{l}S_{\alpha\beta\rho}^{(2)}l.$
(2)

This expression contains two structures. While it is possible to convert one
structure to the other with the help of the Dirac equation, we will keep both
structures for later clarity, in order to compare our result with the previous
one. The EDM operator can be written as

$\mathcal{M}_{\text{EDM}}=-\frac{id_{l}}{2}\epsilon_{\mu\nu\alpha\beta}q^{\alpha}A^{\beta}\bar{l}\sigma^{\mu\nu}l=-\frac{id_{l}}{4m_{l}}p^{\rho}\epsilon_{\mu\nu\alpha\beta}q^{\alpha}A^{\beta}\bar{l}\\{\sigma^{\mu\nu},\gamma_{\rho}\\}l,$
(3)

where $q$ is the incoming photon momentum as in Fig. 1. Comparing Eqs. (2) and
(3), we see
$S_{\alpha\beta}^{(1)}\propto\epsilon_{\mu\nu\alpha\beta}\sigma^{\mu\nu}$ and
$S_{\alpha\beta\rho}^{(2)}\propto\epsilon_{\mu\nu\alpha\beta}\\{\sigma^{\mu\nu},\gamma_{\rho}\\}$.
Using completeness of Dirac matrices and properties of the Levi-Civita tensor,
we find

$\displaystyle
S_{\alpha\beta}^{(1)}=-\frac{1}{8d(d-1)(d-2)(d-3)}\text{Tr}\left[S_{\gamma\delta}^{(1)}\epsilon^{\gamma\delta\kappa\lambda}\sigma_{\kappa\lambda}\right]\times\epsilon_{\mu\nu\alpha\beta}\sigma^{\mu\nu},$
(4) $\displaystyle
S_{\alpha\beta\rho}^{(2)}=-\frac{1}{32d(d-1)(d-2)^{2}(d-3)}\text{Tr}\left[S_{\gamma\delta\eta}^{(2)}\epsilon^{\gamma\delta\kappa\lambda}\\{\sigma_{\kappa\lambda},\gamma^{\eta}\\}\right]\times\epsilon_{\mu\nu\alpha\beta}\\{\sigma^{\mu\nu},\gamma_{\rho}\\}.$

This expression is generalized to arbitrary dimension $d$ for the later using
inside the dimensionally-regularized loop expressions. By writing
$S_{\alpha\beta}^{(1)}$ and $S_{\alpha\beta\rho}^{(2)}$ in the form of Eq.
(4), we can focus on the scalar integral inside the trace, rather than a
complicated integral with open tensor and Dirac indices. The scalar vacuum
integral has a simple topology described by $B_{M}$ in [18] and can be reduced
to two master integrals by repeated use of integration by parts [19, 20, 21,
22, 23]. One of the master integral is simply the product of three one-loop
integrals, and the other is a three-loop integral corresponding to
$\textbf{E}(0,0,x,x)$ in [23]. We use the FIRE6 [24] package to perform the
integration-by-parts reduction and use the analytical expressions of master
integrals in [23]. Divergences and gauge dependencies in the two structures
cancel out separately and leave with us a finite result. Using the same
notation as [16], we get

$\Delta d_{l}=a\frac{m_{l}}{m_{L}}\left(\frac{\alpha}{\pi}\right)^{3}d_{L},$
(5)

with

$\displaystyle a^{(1)}_{1}=\frac{3}{2}\zeta(3)-\frac{19}{12},\quad
a^{(1)}_{2}=\frac{9}{4}\zeta(3)-1,\quad
a^{(1)}=a^{(1)}_{1}+a^{(1)}_{2}=\frac{15}{4}\zeta(3)-\frac{31}{12}\approx
1.924,$ (6) $\displaystyle a^{(2)}_{1}=\frac{1}{2}\zeta(3)-\frac{1}{6},\quad
a^{(2)}_{2}=\frac{1}{2}\zeta(3)-\frac{5}{24},\quad
a^{(2)}=a^{(2)}_{1}+a^{(2)}_{2}=\zeta(3)-\frac{3}{8}\approx 0.827,$
$\displaystyle a=a^{(1)}+a^{(2)}=\frac{19}{4}\zeta(3)-\frac{71}{24}\approx
2.751,$

where $\zeta(s)$ is the Riemann zeta function with $\zeta(3)\approx 1.202$.
The contribution from expansion in $m_{l}/m_{L}$ is labeled by the upper index
$``(1)"$, and the contribution from expansion in $p/m_{L}$ is labeled by the
upper index $``(2)"$. The lower index indicates which set of diagram the
result comes from, with $``1"$ representing the diagram (a) (and its
permutations), and $``2"$ representing the sum of diagrams (b), (c), (d) (and
their permutations). Note that the correct expression for the (a)-type of
diagrams with a heavy quark EDM source and three intermediate gluons have been
reported by us in our previous publication [25].

We note in passing a couple of observations that reduce the amount of
calculation. First, the CP-odd light-by-light operator induced by the heavy
lepton loop vanishes at $q=0$ limit due to the Ward identity. This tells us
that we need to keep $q$ at linear order in the heavy lepton part, so $q$
dependence on the photon propagator and light lepton part can be neglected, as
long as we fix the momentum assignment of the photons. Second, not all 24
diagrams are independent. For example, the two diagrams in Fig. 2 are the same
(or in the general SU(N) case, differs only by a color factor). Similar
relations hold for other diagrams and reduce the number of diagrams we need to
calculate by a half.

Comparing with [16], we see that their result corresponds to our $a^{(1)}$,
while the contribution from $a^{(2)}$ is not included. This means they
expanded the amplitude in $m_{e}/m_{\tau}$ but missed the expansion in
$p/m_{\tau}$. Our calculation shows both expansions contribute to the electron
EDM at the same order. Numerically our result is $\sim 40\%$ larger than [16].
Throughout the calculation, we have assumed the “contact” nature of the EDM
source, that is no $q^{2}$ dependence of $d_{L}$ within the relevant range of
momenta, $|q^{2}|\lesssim m_{L}^{2}$.

As a double-check, we also reevaluated the leading order contribution to
electron $g-2$ from light-by-light scattering induced by muon loop [17, 26].
The same procedure reproduces the known result correctly, and both expansions
in $m_{e}/m_{\mu}$ and in $p/m_{\mu}$ need to be included to get the correct
result.

With the reevaluation of heavy lepton EDM contribution to light lepton EDM,
and improved experimental accuracy for $d_{e}$[3], we update the constraint on
tau EDM:

$\left|{d_{\tau}}\right|<1.1\times
10^{-18}e\;\text{cm}\quad(90\%\text{C.L.}).$ (7)

While on the theoretical side there is only a small change from the previous
work, the accuracy of paramagnetic experiments has improved by two orders of
magnitude since the time [16] is published, and pushed the constraint on
$d_{\tau}$ from $d_{e}$ tighter than the one from
$e^{+}e^{-}\to\tau^{+}\tau^{-}$ by the Belle experiment. The Belle-II
experiment plans to measure $d_{\tau}$, again by
$e^{+}e^{-}\to\tau^{+}\tau^{-}$, with an accuracy of
$|\mathrm{Re}\,d_{\tau}|,|\mathrm{Im}\,d_{\tau}|<10^{-18}\mathchar
45\relax\mathchar 45\relax 10^{-19}\,e\,\mathrm{cm}$ [27]. Therefore the
indirect constraint (7) provides an important benchmark for the Belle-II
experiment, even though the relevant energy scale is slightly different. We
note that the studies of the tau-lepton electromagnetic form factors will
greatly benefit from the proposed addition of the longitudinal polarization to
the electron beam [28], and several orders of magnitude improvements are
possible [29, 30].

We also make an update to the indirect constraint on muon EDM derived from
paramagnetic EDM experiment in [12]:

$\left|{d_{\mu}}\right|<1.7\times 10^{-20}e\;\text{cm}\quad(90\%\text{C.L.}).$
(8)

This is slightly better than the one provided in [12], but is not a
significant change since the semi-leptonic $CP$-odd operator $C_{S}$ is more
important there. In the case of tau EDM, this operator is suppressed since it
scales as $C_{S}\propto m_{L}^{-3}$, and $d_{e}$ induced by $d_{\tau}$
dominates.

We can also generalize our calculation to other $CP$-odd sources. Previously
we have computed [25] heavy quark EDM inducing light quark EDM via the three-
gluon exchange, which, apart from color factors, corresponds to diagram (a) in
Fig. 1. Diagrams (b), (c), (d) in Figure 1, with photon propagators replaced
by gluons and light/heavy leptons replaced by light/heavy quarks, also induce
light quark EDMs from heavy quark CEDMs. Our result still applies here, with a
slight modification to account for the color factor and the heavy quark
electric charge:

$\displaystyle\frac{\Delta d_{q}}{e}$
$\displaystyle=-\frac{Q_{Q}}{48}d^{abc}d^{abc}\times(a_{2}^{(1)}+a_{2}^{(2)})\frac{m_{q}}{m_{Q}}\left(\frac{\alpha_{s}}{\pi}\right)^{3}\tilde{d}_{Q}$
(9)
$\displaystyle=-\frac{5Q_{Q}}{18}\times\left[\frac{11}{4}\zeta(3)-\frac{29}{24}\right]\frac{m_{q}}{m_{Q}}\left(\frac{\alpha_{s}}{\pi}\right)^{3}\tilde{d}_{Q},$

where $q$ and $Q$ stand for light and heavy quarks, respectively, $Q_{Q}$ is
the electric charge of the heavy quark (i.e. $Q_{c}=2/3$ and $Q_{b}=-1/3$),
$d^{abc}$ is the symmetric structure constant of the SU(3) group generator,
and $\tilde{d}_{Q}$ is the heavy quark CEDM. For $m_{q}$ and $\alpha_{s}$ we
use their values at the heavy quark mass scale $m_{c}=1.27\,\mathrm{GeV}$ and
$m_{b}=4.18\,\mathrm{GeV}$, with $m_{u}(m_{c})=2.5\,\text{MeV}$,
$m_{d}(m_{c})=5.4\,\text{MeV}$, $\alpha_{s}(m_{c})=0.38$,
$m_{u}(m_{b})=1.8\,\text{MeV}$, $m_{d}(m_{b})=4.0\,\text{MeV}$,
$\alpha_{s}(m_{b})=0.223$. We use $d_{n}=(4d_{d}-d_{u})/3$[31, 32, 33] and
$|d_{n}|<1.8\times 10^{-26}e\,\text{cm}$[34] to put constraints on heavy quark
CEDM:

$\displaystyle|\tilde{d}_{c}|<5.2\times
10^{-21}\,\text{cm}\quad(90\%\text{C.L.}),$ (10)
$\displaystyle|\tilde{d}_{b}|<2.3\times
10^{-19}\,\text{cm}\quad(90\%\text{C.L.}).$

This is weaker than the constraint from the Weinberg three-gluon operator [35,
36, 37, 38, 39, 40] that will be induced by heavy quark CEDMs at one-loop
order (see e.g. [39, 41]).

##  3 Conclusion

In this paper we have reevaluated the three-loop heavy lepton EDM contribution
to the electron EDM. We have shown that expansions in electron mass and
external electron momentum contribute to the tree-loop EDM diagrams at the
same order in $m_{e}/m_{L}$, and accounting for both contributions enhances
the previous result by $40\%$. With this result we have updated the indirect
limits of several CP-violating observables. Eq. (7) shows that the constraint
derived from paramagnetic EDM experiments on the tau-lepton EDM is more than
an order of magnitude better than other constraints on the same form factor
[42]. Eq. (8) updates the constraint on muon EDM from paramagnetic EDM
experiments with a slight improvement. Eq. (10) provides constraints on charm
and bottom quark CEDMs based on neutron EDM experiments. The constraint is
weaker than the one derived from the Weinberg operator but provides a
complement to the existing limit.

### Acknowledgements

Y.E. and M.P. are supported in part by U.S. Department of Energy Grant No. de-
sc0011842. Y.E. and M.P. would like to thank Perimeter Institute for the
hospitality extended to them during the completion of this work. Y.E. would
like to thank Yukinari Sumino for holding a spring school on multi-loop
computation at Tohoku University in 2017. M.P. would like to thank Dr. K.
Melnikov for the advice in evaluating loop contributions. The Feynman diagrams
in this paper are generated by TikZ-Feynman [43].

##  Appendix A Convention

We use the following conventions in our paper

$\displaystyle e=|e|,$ (11) $\displaystyle
g_{\mu\nu}=\text{diag}(1,-1,-1,-1),\quad\epsilon^{0123}=+1,\quad\sigma_{\mu\nu}=\frac{i}{2}[\gamma_{\mu},\gamma_{\nu}],$
$\displaystyle\tilde{F}^{\mu\nu}=\frac{1}{2}\epsilon^{\mu\nu\alpha\beta}F_{\alpha\beta}.$

To avoid the issue of $\gamma^{5}$ in $d$-dimension, we use the following
(orthogonal but not normalized) basis for $4\times 4$ gamma matrices

$\\{1,\>\gamma^{\mu},\>\sigma^{\mu\nu},\>\\{\sigma^{\mu\nu},\gamma^{\rho}\\},\>\gamma^{[\mu}\gamma^{\nu}\gamma^{\rho}\gamma^{\sigma]}\\}.$
(12)

The EDM and CEDM operators are defined as

$\displaystyle\mathcal{L}_{\text{EDM}}=\frac{d}{2}\bar{\psi}\sigma^{\mu\nu}\tilde{F}_{\mu\nu}\psi,$
(13)
$\displaystyle\mathcal{L}_{\text{CEDM}}=\frac{g_{s}\tilde{d}}{2}\bar{\psi}\sigma^{\mu\nu}\tilde{G}^{a}_{\mu\nu}T^{a}\psi.$

The SU(3) generator $T^{a}$ is normalized as

$\text{tr}_{c}[T^{a}T^{b}]=\frac{\delta^{ab}}{2}.$ (14)

## References

  * [1] E. M. Purcell and N. F. Ramsey, “On the Possibility of Electric Dipole Moments for Elementary Particles and Nuclei,” Phys. Rev. 78 (1950) 807–807.
  * [2] Y. Ema, T. Gao, and M. Pospelov, “Standard Model prediction for paramagnetic EDMs,” arXiv:2202.10524 [hep-ph].
  * [3] ACME Collaboration, V. Andreev et al., “Improved limit on the electric dipole moment of the electron,” Nature 562 no. 7727, (2018) 355–360.
  * [4] A. Crivellin, M. Hoferichter, and P. Schmidt-Wellenburg, “Combined explanations of $(g-2)_{\mu,e}$ and implications for a large muon EDM,” Phys. Rev. D 98 no. 11, (2018) 113002, arXiv:1807.11484 [hep-ph].
  * [5] T. Aoyama et al., “The anomalous magnetic moment of the muon in the Standard Model,” Phys. Rept. 887 (2020) 1–166, arXiv:2006.04822 [hep-ph].
  * [6] Muon g-2 Collaboration, B. Abi et al., “Measurement of the Positive Muon Anomalous Magnetic Moment to 0.46 ppm,” Phys. Rev. Lett. 126 no. 14, (2021) 141801, arXiv:2104.03281 [hep-ex].
  * [7] Y. K. Semertzidis et al., “Sensitive search for a permanent muon electric dipole moment,” in KEK International Workshop on High Intensity Muon Sources (HIMUS 99), pp. 81–96.  12, 1999.  arXiv:hep-ph/0012087.
  * [8] Muon (g-2) Collaboration, G. W. Bennett et al., “An Improved Limit on the Muon Electric Dipole Moment,” Phys. Rev. D 80 (2009) 052008, arXiv:0811.1207 [hep-ex].
  * [9] H. Iinuma, H. Nakayama, K. Oide, K.-i. Sasaki, N. Saito, T. Mibe, and M. Abe, “Three-dimensional spiral injection scheme for the g-2/EDM experiment at J-PARC,” Nucl. Instrum. Meth. A 832 (2016) 51–62.
  * [10] M. Abe et al., “A New Approach for Measuring the Muon Anomalous Magnetic Moment and Electric Dipole Moment,” PTEP 2019 no. 5, (2019) 053C02, arXiv:1901.03047 [physics.ins-det].
  * [11] A. Adelmann et al., “Search for a muon EDM using the frozen-spin technique,” arXiv:2102.08838 [hep-ex].
  * [12] Y. Ema, T. Gao, and M. Pospelov, “Improved Indirect Limits on Muon Electric Dipole Moment,” Phys. Rev. Lett. 128 no. 13, (2022) 131803, arXiv:2108.05398 [hep-ph].
  * [13] B. Graner, Y. Chen, E. G. Lindahl, and B. R. Heckel, “Reduced Limit on the Permanent Electric Dipole Moment of Hg199,” Phys. Rev. Lett. 116 no. 16, (2016) 161601, arXiv:1601.04339 [physics.atom-ph]. [Erratum: Phys.Rev.Lett. 119, 119901 (2017)].
  * [14] Belle Collaboration, K. Inami et al., “Search for the electric dipole moment of the tau lepton,” Phys. Lett. B 551 (2003) 16–26, arXiv:hep-ex/0210066.
  * [15] W. Bernreuther, L. Chen, and O. Nachtmann, “Electric dipole moment of the tau lepton revisited,” Phys. Rev. D 103 no. 9, (2021) 096011, arXiv:2101.08071 [hep-ph].
  * [16] A. G. Grozin, I. B. Khriplovich, and A. S. Rudenko, “Electric dipole moments, from e to tau,” Phys. Atom. Nucl. 72 (2009) 1203–1205, arXiv:0811.1641 [hep-ph].
  * [17] S. Laporta and E. Remiddi, “The Analytical value of the electron light-light graphs contribution to the muon (g-2) in QED,” Phys. Lett. B 301 (1993) 440–446.
  * [18] D. J. Broadhurst, “Three loop on-shell charge renormalization without integration: Lambda-MS (QED) to four loops,” Z. Phys. C 54 (1992) 599–606.
  * [19] L. V. Avdeev, “Recurrence relations for three loop prototypes of bubble diagrams with a mass,” Comput. Phys. Commun. 98 (1996) 15–19, arXiv:hep-ph/9512442.
  * [20] M. Steinhauser, “MATAD: A Program package for the computation of MAssive TADpoles,” Comput. Phys. Commun. 134 (2001) 335–364, arXiv:hep-ph/0009029.
  * [21] K. G. Chetyrkin and F. V. Tkachov, “Integration by Parts: The Algorithm to Calculate beta Functions in 4 Loops,” Nucl. Phys. B 192 (1981) 159–204.
  * [22] F. V. Tkachov, “A Theorem on Analytical Calculability of Four Loop Renormalization Group Functions,” Phys. Lett. B 100 (1981) 65–68.
  * [23] S. P. Martin and D. G. Robertson, “Evaluation of the general 3-loop vacuum Feynman integral,” Phys. Rev. D 95 no. 1, (2017) 016008, arXiv:1610.07720 [hep-ph].
  * [24] A. V. Smirnov and F. S. Chuharev, “FIRE6: Feynman Integral REduction with Modular Arithmetic,” Comput. Phys. Commun. 247 (2020) 106877, arXiv:1901.07808 [hep-ph].
  * [25] Y. Ema, T. Gao, and M. Pospelov, “Improved indirect limits on charm and bottom quark EDMs,” arXiv:2205.11532 [hep-ph].
  * [26] J. H. Kuhn, A. I. Onishchenko, A. A. Pivovarov, and O. L. Veretin, “Heavy mass expansion, light by light scattering and the anomalous magnetic moment of the muon,” Phys. Rev. D 68 (2003) 033018, arXiv:hep-ph/0301151.
  * [27] Belle-II Collaboration, W. Altmannshofer et al., “The Belle II Physics Book,” PTEP 2019 no. 12, (2019) 123C01, arXiv:1808.10567 [hep-ex]. [Erratum: PTEP 2020, 029201 (2020)].
  * [28] J. M. Roney, “Electroweak Physics with Polarized Beams at SuperKEKB Upgrade,” PoS LeptonPhoton2019 (2019) 109, arXiv:1907.03503 [hep-ex].
  * [29] J. Bernabeu, G. A. Gonzalez-Sprinberg, J. Papavassiliou, and J. Vidal, “Tau anomalous magnetic moment form-factor at super B/flavor factories,” Nucl. Phys. B 790 (2008) 160–174, arXiv:0707.2496 [hep-ph].
  * [30] A. Crivellin, M. Hoferichter, and J. M. Roney, “Towards testing the magnetic moment of the tau at one part per million,” arXiv:2111.10378 [hep-ph].
  * [31] M. Pospelov and A. Ritz, “Neutron EDM from electric and chromoelectric dipole moments of quarks,” Phys. Rev. D 63 (2001) 073015, arXiv:hep-ph/0010037.
  * [32] M. Pospelov and A. Ritz, “Electric dipole moments as probes of new physics,” Annals Phys. 318 (2005) 119–169, arXiv:hep-ph/0504231.
  * [33] J. Hisano, J. Y. Lee, N. Nagata, and Y. Shimizu, “Reevaluation of Neutron Electric Dipole Moment with QCD Sum Rules,” Phys. Rev. D 85 (2012) 114044, arXiv:1204.2653 [hep-ph].
  * [34] C. Abel et al., “Measurement of the Permanent Electric Dipole Moment of the Neutron,” Phys. Rev. Lett. 124 no. 8, (2020) 081803, arXiv:2001.11966 [hep-ex].
  * [35] S. Weinberg, “Larger Higgs Exchange Terms in the Neutron Electric Dipole Moment,” Phys. Rev. Lett. 63 (1989) 2333.
  * [36] D. Chang, W.-Y. Keung, C. S. Li, and T. C. Yuan, “QCD Corrections to CP Violation From Color Electric Dipole Moment of $b$ Quark,” Phys. Lett. B 241 (1990) 589–592.
  * [37] G. Boyd, A. K. Gupta, S. P. Trivedi, and M. B. Wise, “Effective Hamiltonian for the Electric Dipole Moment of the Neutron,” Phys. Lett. B 241 (1990) 584–588.
  * [38] M. Dine and W. Fischler, “Constraints on New Physics From Weinberg’s Analysis of the Neutron Electric Dipole Moment,” Phys. Lett. B 242 (1990) 239–244.
  * [39] D. A. Demir, M. Pospelov, and A. Ritz, “Hadronic EDMs, the Weinberg operator, and light gluinos,” Phys. Rev. D 67 (2003) 015007, arXiv:hep-ph/0208257.
  * [40] F. Sala, “A bound on the charm chromo-EDM and its implications,” JHEP 03 (2014) 061, arXiv:1312.2589 [hep-ph].
  * [41] U. Haisch and G. Koole, “Beautiful and charming chromodipole moments,” JHEP 09 (2021) 133, arXiv:2106.01289 [hep-ph].
  * [42] Particle Data Group Collaboration, R. Workman et al., “Review of Particle Physics,”.
  * [43] J. Ellis, “TikZ-Feynman: Feynman diagrams with TikZ,” Comput. Phys. Commun. 210 (2017) 103–123, arXiv:1601.05437 [hep-ph].


# Counterexamples to "Transitive Regret"

Yuan<EMAIL_ADDRESS>
Shuo Li<EMAIL_ADDRESS>
(June 10, 2024)

###### Abstract

Theorem 1 in Bikhchandani & Segal (2011) suggests that a complete, transitive,
monotonic, and continuous preference is regret based if and only if it is
expected utility. Their Proposition 1 suggests that transitivity and
continuity of a regret-based preference implies an equivalence condition: if
random variables
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y$ have the
same distribution, then
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\sim Y$. We
give counterexamples to Proposition 1. ††We are in debt to Jingni Yang for
comments. All errors are ours.

##  1 Notations

Let $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}L$ be
the set of real finite-valued random variables over
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(S,\Sigma,P)$
with
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S=[0,1]$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Sigma$
being the Borel
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sigma$-algebra,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}P$ being the
Lebesgue measure, and the set of outcomes being the bounded interval
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\underline{x},\bar{x}]$.
The decision maker has a preference relation
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\succsim$
over $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}L$.
Denote events by
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S_{i}$.

Definition 1. The continuous function
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi:[\underline{x},\bar{x}]\times[\underline{x},\bar{x}]\rightarrow\mathbb{R}$
is a regret function if for all
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,x)=0$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,y)$
is strictly increasing in
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x$ and
strictly decreasing in
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}y$.

If in some event
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X$ yields
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y$ yields
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}y$, then
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,y)$
is a measure of the decision maker’s ex post feelings about the choice of
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X$ over
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y$. This
leads to the next definition.

Definition 2. Let
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y\in L$,
where
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X=(x_{1},S_{1};\ldots;x_{n},S_{n})$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y=(y_{1},S_{1};\ldots;y_{n},S_{n})$.
The regret lottery evaluating the choice of
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X$ over
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y$ is

$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Psi(X,Y)=(\psi(x_{1},y_{1}),p_{1};\ldots;\psi(x_{n},y_{n}),p_{n}),$

where
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p_{i}=P(S_{i})$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}i=1,\ldots,n$.

Refer to
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Psi$ as a
regret function and a regret lottery. The main model follows.

Definition 3. The preference relation
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\succsim$ is
regret based if there exists a regret function
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi$ and a
continuous functional
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V$ that is
defined over regret lotteries such that for any
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y\in L$,

$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\succsim
Y\text{ if and only if }V(\Psi(X,Y))\geq 0.$

##  2 Counterexamples

######  Proposition 1 (Bikhchandani & Segal 2011).

Let
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\succsim$ be
transitive, continuous, and regret based. For all
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y$, if they
have the same cumulative distribution with respect to
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}P$, then
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\sim Y$.

One difference between Theorem 1 and Proposition 1 in Bikhchandani& Segal
(2011) is that Proposition 1 drops two axioms: monotonicity and completeness.
The following counterexamples imply that the assumptions for Proposition 1 is
too weak due to the lack of completeness axiom.

Assume
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,y)=x-y$,
a continuous regret function.

Counterexample 1:  Under the constant representation
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))=-1$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\not\succsim
Y$ if $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y$
have the same distribution.

It will be proven that
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V$ satisfies
transitivity, continuity, and regret-based.

###### Proof.

First, observe
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))=-1$
for any regret lotteries.
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V$ is
regret-based because a constant function is continuous and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,y)=x-y$
is a continuous regret function.

Transitivity will be proven by contradiction. Assume transitivity does not
hold; then, there must exist
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y,Z$ such
that
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\succsim
Y$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y\succsim
Z$, and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\not\succsim
Z$. However,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))<0$
implies
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\not\succsim
Y$, a contradiction! So transitivity holds.

Since for all
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y:$
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V\not\geq
0$, we have
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\not\succsim
Y$ for any
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y$. The
upper contour sets and lower contour sets of
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\succsim$
are all empty sets and thus closed sets, satisfying continuity. ∎

Counterexample 2: Under the representation
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))=-\sum_{i}|\psi(x_{i},y_{i})p_{i}|$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\not\succsim
Y$ if $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X,Y$
have the same distribution and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\neq Y$.

###### Proof.

First, observe that
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-\sum_{i}|\psi(x_{i},y_{i})p_{i}|$
is regret-based because the sum of absolute value functions is continuous and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x,y)=x-y$
is a continuous regret function.

Assume
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\succsim Y$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y\succsim
Z$. Observe that
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}-\sum_{i}|\psi(x_{i},y_{i})p_{i}|\leq
0$ and the equality holds if
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\psi(x_{i},y_{i})=0$
for all $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}i$.
Since
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\succsim Y$
implies
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))\geq
0$, we have
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}V(\Psi(X,Y))=0$.
Thus,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}x_{i}=y_{i}$
for all $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}i$
and $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X=Y$.
Similarly,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y=Z$.
Therefore,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X\succsim
Z$. Transitivity holds.

Observe that the upper contour set
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\\{X:X\succsim
Y\\}=\\{X\\}$ is a singleton and that the lower contour set is also a
singleton. Therefore, the upper contour sets and the lower contour sets of
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\succsim$
are singleton sets and therefore closed sets, satisfying continuity. ∎

Proposition 1 is the first step in Bikhchandani& Segal (2011)’s proof (page
98) for Theorem 1, and is applied in their Section 3.3, page 100.

## References

  * [1] Sushil Bikhchandani and Uzi Segal  “Transitive regret”  In _Theoretical Economics_ 6.1 Wiley Online Library, 2011, pp. 95–108


# On the complexity of the theory of a computably presented metric structure

Caleb Camrud  Department of Mathematics
Iowa State University
Ames, Iowa 50011<EMAIL_ADDRESS>,  Isaac Goldbring  Department of
Mathematics
University of California, Irvine
340 Rowland Hall (Bldg.# 400)
Irvine, CA 92697-3875<EMAIL_ADDRESS>and  Timothy H. McNicholl
Department of Mathematics
Iowa State University
Ames, Iowa 50011<EMAIL_ADDRESS>
###### Abstract.

We consider the complexity (in terms of the arithmetical hierarchy) of the
various quantifier levels of the diagram of a computably presented metric
structure. As the truth value of a sentence of continuous logic may be any
real in $[0,1]$, we introduce two kinds of diagrams at each level: the
_closed_ diagram, which encapsulates weak inequalities of the form
$\phi^{\mathcal{M}}\leq r$, and the _open_ diagram, which encapsulates strict
inequalities of the form $\phi^{\mathcal{M}}<r$. We show that the closed and
open $\Sigma_{N}$ diagrams are $\Pi^{0}_{N+1}$ and $\Sigma_{N}$ respectively,
and that the closed and open $\Pi_{N}$ diagrams are $\Pi^{0}_{N}$ and
$\Sigma^{0}_{N+1}$ respectively. We then introduce effective infinitary
formulas of continuous logic and extend our results to the hyperarithmetical
hierarchy. Finally, we demonstrate that our results are optimal.

Goldbring was partially supported by NSF grant DMS-2054477.

##  1\. Introduction

Suppose $\mathcal{A}$ is a _computably presented_ countable structure, that
is, we have numbered the elements of its domain so that the resulting
operations and relations on the natural numbers are computable. A longstanding
and ongoing line of inquiry in computable model theory is to study the
complexity of the elementary (i.e. complete) diagram of such models at the
various quantifier levels. In particular, such a model is said to be _$N$
-decidable_ if the set of the $\Sigma_{N}$-sentences of its elementary diagram
is computable. A seminal result in this direction is the theorem of Moses and
Chisholm that there is a computable linear order that is $n$-decidable for all
$n$ yet not decidable [4]. More recently, Fokina et. al. have investigated
index sets of $n$-decidable models; i.e. the complexity of classifying such
models [7]. More results along these lines can be found in the survey by
Fokina, Harizanov, and Melnikov [8].

Here, we wish to initiate a similar program for metric structures in the
context of continuous logic as expounded in [2]. We use the framework for
studying the computability of metric structures that has evolved over
approximately the past decade (see e.g. [10], [9] ). There are two
difficulties that must be confronted at the outset. One difficulty is that for
a sentence $\phi$ of continuous logic, the truth value of $\phi$ can be any
real in $[0,1]$, with $0$ representing truth and $1$ representing falsity.
Another difficulty is that the domain of a typical metric structure is
uncountable, whence the inclusion of parameters in our sentences would
immediately pose complications for a computability-theoretic analysis. Our
solution to the first difficulty is to study two kinds of diagrams: _closed_
diagrams, corresponding to inequalities of the form $\phi^{\mathcal{M}}\leq
r$, and _open_ diagrams, corresponding to inequalities of the form
$\phi^{\mathcal{M}}<r$. (Here $\phi^{\mathcal{M}}$ is the truth-value of
$\phi$ in the model $\mathcal{M}$.) We leave consideration of possible
solutions of the second obstacle for future work. Consequently, we only
consider parameter-free sentences.

In the classical case, the complexity of the levels of a diagram of a
computably presented model is very straightforward: the collection of true
$\Sigma_{N}$ sentences is $\Sigma^{0}_{N}$ and the collection of true
$\Pi_{N}$ sentences is $\Pi^{0}_{N}$. True arithmetic demonstrates that these
bound are optimal. We find, however, that in the context of continuous logic,
the relation is not so straightforward. For example, in our first main result
(Theorem 4.2), we show that the closed $\Sigma_{N}$ diagram is
$\Pi^{0}_{N+1}$, so that we obtain neither the expected quantifier nor the
expected level of complexity. This result may seem surprising at first due to
its dissonance with the classical case. However, some reflection on the nature
of computation with real numbers will likely reveal it is the only answer
possible. Nevertheless, in our second main result (Theorem 5.1), we show that
our upper bounds in the finite case are indeed optimal.

We then extend our results to infinitary continuous logic. In this context, we
use the hyperarithmetical hierarchy to gauge complexity. The theory of
infinitary continuous logic has been previously studied in [3] and [6]. To the
best of our knowledge, this is the first paper to consider effective
infinitary logic for metric structures. As might be expected, our results for
infinitary logic (Theorems 6.1 and 6.2), parallel our findings for finitary
logic. However, the availability of infinite disjunctions yields simpler
demonstrations of the lower bounds.

The paper is organized as follows. Section 2 covers relevant background from
computability theory, computable analysis, and continuous logic. Section 3
lays out the framework for effective infinitary continuous logic as well as
some combinatorial results which support our work on finitary logic. Upper and
lower bounds for the finitary case as presented in Sections 4 and 5
respectively. The upper and lower bounds for the infinitary case are
demonstrated in Section 6. Finally, Section 7 summarizes our findings and
presents some avenues for further investigation.

##  2\. Background

###  2.1. Background from continuous Logic

We generally follow the framework of [2]. However, we limit our connectives to
$\neg$, $\frac{1}{2}$, and  . $-$ . The universal and existential quantifiers
are replaced by ‘$\sup$’ and ‘$\inf$’ respectively. In the following, by
_language_ , we mean a signature for a metric structure. A language in this
sense includes a modulus of uniform continuity for each predicate symbol and
each function symbol. When $\mathcal{M}$ is an $L$-structure, we denote the
domain of $\mathcal{M}$ as $|\mathcal{M}|$.

The $\Sigma_{N}$ and $\Pi_{N}$ wff’s of a language $L$ are defined as in the
classical case. For example, if $\phi$ is a quantifier-free wff of $L$, then
$\inf_{x_{1}}\sup_{x_{2}}\phi$ is a $\Sigma_{2}$ wff of $L$.

The language $L_{\omega_{1}\omega}$ is considered in the sense of Eagle in [6]
as opposed to the language given by Ben-Yaacov and Iovino in [3]. The key
distinction is that $L_{\omega_{1}\omega}$ in [6] does not require every
infinitary formula to have a modulus of uniform convergence, while the
language of [3] does. Adding this extra condition complicates the effective
encoding of the computable infinitary formulas. However, as we shall see
later, our results will hold in any reasonable effectivization of the
framework of Ben-Yaacov and Iovino.

A key terminological difference with classical infinitary logic is that
$\operatorname*{\bigvee\mkern-15.0mu\bigvee}$ is used for infinite conjunction
and $\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}$ for infinite
disjunction. That is, $\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{n}$ is
interpreted as $\sup_{n}$ and
$\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}_{n}$ is interpreted as
$\inf_{n}$. The reasons for this are clear when considering the ordered set of
real numbers as a lattice.

###  2.2. Background from computability theory

Familiarity with standard computability-theoretic concepts like computable
enumerability, oracle computability, the arithmetical hierarchy, and the
relationship between each of these is assumed. A thorough treatment of these
subjects can be found in [12], [5]. For background on the hyperarithmetical
hierarchy, see [1] and [11].

Let $\mathcal{O}$ denote Kleene’s system of notations for the computable
ordinals. If $\alpha<\omega_{1}^{\operatorname{CK}}$, then
$\langle\alpha\rangle$ denotes the set of all notations for $\alpha$.

A real number $r$ is _computable_ if there is an effective procedure which,
given $k\in\mathbb{N}$, produces a rational number $q$ such that
$|r-q|<2^{-k}$. A sequence $(r_{n})_{n\in\mathbb{N}}$ of reals is computable
if it is computable uniformly in $n$. By an _index_ of such a sequence we mean
an index of a Turing machine that computes it.

Suppose $(M,d)$ and $(M^{\prime},d^{\prime})$ are metric spaces, and let
$\Gamma:M\rightarrow M^{\prime}$. A map
$\Delta:\mathbb{N}\rightarrow\mathbb{N}$ is called a _modulus of continuity_
for $\Gamma$ if $d(a,b)\leq 2^{-\Delta(k)}$ whenever
$d^{\prime}(\Gamma(a),\Gamma(b))\leq 2^{-k}$. A map $\Gamma:M\to M^{\prime}$
is called _effectively uniformly continuous_ if it has a computable modulus of
uniform continuity.

In the following, $L$ denotes an effectively numbered language with uniformly
computable moduli of uniform continuity. That is, there is an algorithm that
given a number assigned to a predicate or function symbol $\phi$ computes the
modulus function of $\phi$. Moreover, unless otherwise mentioned, every
structure will be assumed to be an $L$-structure.

Our framework for the computability of metric structures is essentially that
in [9]. Given a structure $\mathcal{M}$ and $A\subseteq|\mathcal{M}|$, we
define the _algebra generated by_ $A$ to be the smallest subset of
$|\mathcal{M}|$ containing $A$ that is closed under every function of
$\mathcal{M}$. A pair $(\mathcal{M},g)$ is called a _presentation_ of
$\mathcal{M}$ if $g:\mathbb{N}\to|\mathcal{M}|$ is a map such that the algebra
generated by $\operatorname{ran}(g)$ is dense. We use $\mathcal{M}^{\sharp}$
to denote presentations of a structure $\mathcal{M}$. Given a presentation
$\mathcal{M}^{\sharp}=(\mathcal{M},g)$, every $a\in\operatorname{ran}(g)$ is
called a _distinguished point_ of $\mathcal{M}^{\sharp}$, and each point in
the algebra generated by the distinguished points is called a _rational point_
of $\mathcal{M}^{\sharp}$. The set of all rational points of
$\mathcal{M}^{\sharp}$ is denoted $\mathbb{Q}(\mathcal{M}^{\sharp})$. By an
_open rational ball_ of $\mathcal{M}^{\sharp}$ we mean an open ball of
$\mathcal{M}$ whose radius is rational and whose center is a rational point of
$\mathcal{M}^{\sharp}$. By a _rational cover_ of $\mathcal{M}^{\sharp}$ we
mean a finite set of rational balls of $\mathcal{M}^{\sharp}$ that covers
$|\mathcal{M}|$.

A presentation $\mathcal{M}^{\sharp}$ is _computable_ if the predicates of
$\mathcal{M}$ are uniformly computable on the rational points of
$\mathcal{M}^{\sharp}$. Since the metric is a binary predicate on
$\mathcal{M}$, this entails that the distance between any two rational points
is uniformly computable. We say that a metric structure is _computably
presentable_ if it has a computable presentation. We say that a presentation
$\mathcal{M}^{\sharp}$ is _computably compact_ if the set of its rational
covers is computably enumerable. Lastly, we define an _index_ of a computable
presentation $\mathcal{M}^{\sharp}$ to be a code of a Turing machine that
computes the predicates of $\mathcal{M}$ on the rational points of
$\mathcal{M}^{\sharp}$.

##  3\. Preliminaries

###  3.1. Preliminaries from classical logic and computability

We begin with some relational notation which will facilitate the statements of
many of our results and their proofs.

######  Definition 3.1.

Let $N\in\mathbb{N}$, and suppose $R\subseteq\mathbb{N}^{N+1}$.

  1. (1)

$\neg R=\mathbb{N}^{N+1}-R$.

  2. (2)

$\vec{\exists}R=\\{n\in\mathbb{N}\ :\ \exists x_{1}\forall x_{2}\ldots Qx_{N}\
R(n,x_{1},\ldots,x_{N})\\}$.

  3. (3)

$\vec{\forall}R=\\{n\in\mathbb{N}\ :\ \forall x_{1}\exists x_{2}\ldots Qx_{N}\
R(n,x_{1},\ldots,x_{N})\\}$.

In Definition 3.1.2, $Q$ denotes the quantifier $\forall$ if $N$ is even and
$\exists$ if $N$ is odd. Similarly, in Definition 3.1.3, $Q$ denotes the
quantifier $\forall$ if $N$ is odd and $\exists$ if $N$ is even. We will
follow these conventions in the sequel.

Given $R\subseteq\mathbb{N}^{N+1}$, we also set

$R^{*}=\\{(n,x_{1},\ldots,x_{N})\ \in\mathbb{N}^{N+1}\ :\ \forall
x_{1}^{\prime}\leq x_{1}\exists x_{2}^{\prime}\leq x_{2}\ldots
Qx_{N}^{\prime}\leq x_{N}\ R(n,x_{1}^{\prime},\ldots,x_{N}^{\prime})\\}.$

Note that $R\equiv_{\rm T}R^{*}$. Finally, let $\chi_{R}$ denote the
characteristic (indicator) function of $R$.

We fix a uniformly computable family $(R_{N})_{N\in\mathbb{N}}$ of relations
so that for each $N\in\mathbb{N}$, $R_{2N}\cup
R_{2N+1}\subseteq\mathbb{N}^{N+2}$, $\vec{\forall}R_{2N}$ is
$\Pi^{0}_{N+1}$-complete, and $\vec{\exists}R_{2N+1}$ is
$\Sigma^{0}_{N+1}$-complete.

###  3.2. Preliminaries from continuous logic

We begin by formally defining the open and closed diagrams of a metric
structure.

######  Definition 3.2.

Let $\mathcal{M}$ be an $L$-structure. In the following, $\phi$ ranges over
sentences of $L$ and $q$ ranges over $[0,1]\cap\mathbb{Q}$.

  1. (1)

The _closed (resp. open) quantifier-free diagram of $\mathcal{M}$_ is the set
of all pairs $(\phi,q)$ so that $\phi$ is quantifier-free and
$\phi^{\mathcal{M}}\leq q$ (resp. $\phi^{\mathcal{M}}<q$).

  2. (2)

For every positive integer $N$, the _closed (resp. open) $\Pi_{N}$ diagram of
$\mathcal{M}$_ is the set of all pairs $(\phi,q)$ so that $\phi$ is $\Pi_{N}$
and $\phi^{\mathcal{M}}\leq q$ (resp. $\phi^{\mathcal{M}}<q$). The closed and
open $\Sigma_{N}$ diagrams are defined similarly.

We now define the computable wff’s of $L_{\omega_{1}\omega}$ and their codes
by effective transfinite induction. We follow the development of the classical
case in [1]. We presume an effective enumeration of the quantifier-free wff’s
of $L$. We also presume effective codings of the following.

  1. (1)

All pairs of the form $(j,\overline{z})$, where $j\in\mathbb{N}$ and
$\overline{z}$ is a tuple of variables.

  2. (2)

All quadruples of the form $(X,a,\overline{x},e)$, where
$X\in\\{\Sigma,\Pi\\}$, $a,e\in\mathbb{N}$, and $\overline{x}$ is a tuple of
variables.

When $\xi$ is a tuple of either of the above types, we let $\overline{\xi}$
denote the code of $\xi$.

For every $X\in\\{\Sigma,\Pi\\}$ and $a\in\mathcal{O}$, we first define the
index set $S_{a}^{X}$ in such a way that if $a\in\langle\alpha\rangle$, then
every formula with indices in $S_{a}^{X}$ will be $X_{\alpha}$.

We begin by setting $S_{1}^{\Sigma}$ and $S_{1}^{\Pi}$ to be the set of codes
of all quantifier-free, finitary formulas of $\mathcal{L}$. (Recall that $1$
denotes $0$ in Kleene’s $\mathcal{O}$.) For every $a\in\mathcal{O}-\\{1\\}$
and $X\in\\{\Sigma,\Pi\\}$, let $S_{a}^{X}$ be the set of codes of all
quadruples of the form $(X,a,\overline{x},e)$, where $\overline{x}$ is a
finite tuple of variable symbols, and $e\in\mathbb{N}$.

Now for every $a\in\mathcal{O}$, $X\in\\{\Sigma,\Pi\\}$, and tuple of variable
symbols $\overline{x}$, we define $P(X,a,\overline{x})$ to be the set of all
codes of pairs $(j,\overline{z})$, where $j$ codes a quadruple
$(X,b,\overline{y},e^{\prime})$ with $b<_{\mathcal{O}}a$ and $\overline{z}$ is
a finite sequence of variable symbols of $\overline{y}$ not contained in
$\overline{x}$.

For each $i\in S^{\Sigma}_{a}\cup S^{\Pi}_{a}$, we define an infinitary wff
$\phi_{i}$ as follows:

  1. (1)

If $a=1$, then $\phi_{i}$ is the quantifier-free finitary wff indexed by $i$.

  2. (2)

Suppose $a>1$ and $i=\overline{(X,a,\overline{x},e)}$.

    1. (a)

If $X=\Sigma$, then

$\phi_{i}=\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}_{\overline{(j,\overline{z})}\in
W_{e}\cap P(\Pi,a,\overline{x})}\inf_{\overline{z}}\phi_{j}.$

    2. (b)

If $X=\Pi$, then

$\phi_{i}=\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{\overline{(j,\overline{z})}\in
W_{e}\cap P(\Sigma,a,\overline{x})}\sup_{\overline{z}}\phi_{j}.$

For every computable ordinal $\alpha$, we let $\Sigma^{c}_{\alpha}$ denote the
set of all formulas $\phi_{i}$ where
$i\in\bigcup_{a\in\langle\alpha\rangle}S^{\Sigma}_{a}$. Similarly,
$\Pi^{c}_{\alpha}$ denotes the set of all formulas $\phi_{i}$ where
$i\in\bigcup_{a\in\langle\alpha\rangle}S^{\Pi}_{a}$. If $\psi=\phi_{i}$, then
we say that $i$ is a _code_ of $\psi$. By a _computable infinitary formula_ ,
we mean an element of $\Sigma_{\alpha}^{c}\cup\Pi_{\alpha}^{c}$ for some
computable ordinal $\alpha$.

It is fairly routine to verify that all logical operations can be performed
effectively via this coding system. For example, from an $i$ that codes an
infinitary wff $\phi$, it is possible to compute a code of $\sup_{x}\phi$.

###  3.3. Combinatorial preliminaries

We introduce here some results that will support our demonstration of lower
bounds. Among these, our main result (Theorem 3.5) is a principle for
representing $\Sigma^{0}_{N}$ and $\Pi^{0}_{N}$ sets as solutions of
inequalities involving infinite series. We believe this connection is
sufficiently novel to merit consideration on its own.

We begin with the following lemma which is easily verified by simultaneous
induction on $N$. Note that the suprema and infima range over $\mathbb{N}$.

######  Lemma 3.3.

For $R\subseteq\mathbb{N}^{N+1}$ and $n\in\mathbb{N}$, we have:

  1. (1)

$n\in\vec{\forall}R$ if and only if $\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}\chi_{R}(n,x_{1},\ldots,x_{N})=1$.

  2. (2)

$n\in\vec{\exists}R$ if and only if $\sup_{x_{1}}\inf_{x_{2}}\ldots
Q_{x_{N}}\chi_{R}(n,x_{1},\ldots,x_{N})=1$.

To state our main theorem of this section, we need the following.

######  Definition 3.4.

For $K,N\in\mathbb{N}$ and $f:\mathbb{N}^{N+1}\rightarrow\mathbb{R}$ a bounded
function, set:

$\displaystyle\Gamma_{K}(f;x_{1},\ldots,x_{N})$ $\displaystyle=$
$\displaystyle\sum_{x_{0}=0}^{K}2^{-(x_{0}+1)}f(x_{0},\ldots,x_{N})$
$\displaystyle\Gamma(f;x_{1},\ldots,x_{N})$ $\displaystyle=$
$\displaystyle\sum_{x_{0}=0}^{\infty}2^{-(x_{0}+1)}f(x_{0},\ldots,x_{N}).$

We define $\Gamma(f):\mathbb{N}^{N}\to\mathbb{R}$ by setting
$\Gamma(f)(x_{1},\ldots,x_{N})=\Gamma(f;x_{1},\ldots,x_{N})$. We note that
$\Gamma(f)$ is computable if $f$ is computable and, in this case, an index of
$\Gamma(f)$ can be computed from an index of $f$ and a bound on $f$.

We are now ready to state and prove the key result of this section. In what
follows, we view elements of $\mathbb{N}^{N+2}$ as being of the form
$(x_{0},x_{1},\ldots,x_{N},n)$.

######  Theorem 3.5.

Let $R\subseteq\mathbb{N}^{N+2}$, and let $n\in\mathbb{N}$.

  1. (1)

$n\in\vec{\forall}R$ if and only if

$\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}\Gamma(1-\frac{1}{2}\chi_{R^{*}};x_{1},\ldots,x_{N},n)\leq\frac{1}{2}.$

  2. (2)

$n\in\vec{\exists}R$ if and only if

$\sup_{x_{1}}\inf_{x_{2}}\ldots Q_{x_{N}}\Gamma(\frac{1}{2}\chi_{(\neg
R)^{*}};x_{1},\ldots,x_{N},n)<\frac{1}{2}.$

The proof of the previous theorem requires a few preparatory lemmas. For the
first lemma, note that if $f:\mathbb{N}\to\mathbb{R}$ is a bounded function,
then $\Gamma_{K}(f)$ is simply a real number (i.e. a constant).

######  Lemma 3.6.

If $f:\mathbb{N}\rightarrow\\{\frac{1}{2},1\\}$, then for every
$K\in\mathbb{N}$, $\Gamma_{K}(f)\leq\frac{1}{2}$ if and only if
$f(m)=\frac{1}{2}$ for all $m<K$.

###### Proof sketch.

Fix $K\in\mathbb{N}$. Consider the given sum in base $2$. Any $m<K$ for which
$f(m)=1$ leads to a ‘carry’ operation so that the $\frac{1}{2}$-position
becomes $1$. Adding $f(K)$ would then force the value to be greater than
$\frac{1}{2}$. ∎

######  Lemma 3.7.

Suppose $R\subseteq\mathbb{N}^{N+1}$. Then
$\vec{\forall}(R^{*})=\vec{\forall}R$.

###### Proof sketch.

The proof that $\vec{\forall}(R^{*})\subseteq\vec{\forall}R$ is
straightforward. The other inclusion is demonstrated via Skolemization. ∎

######  Lemma 3.8.

Fix $R\subseteq\mathbb{N}^{N+2}$ and $1\leq J\leq N$. Then for every
$x_{1},\ldots,x_{J-1},n\in\mathbb{N}$ and every $K\in\mathbb{N}$, we have:

  1. (1)

$\sup_{x_{J}}\inf_{x_{J+1}}\ldots
Q_{x_{N}}\Gamma_{K}(1-\frac{1}{2}\chi_{R^{*}};x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$
if and only if
$\Gamma_{K}(\sup_{x_{J}}\inf_{x_{J+1}}\ldots
Q_{x_{N}}(1-\frac{1}{2}\chi_{R^{*}});x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$.

  2. (2)

$\inf_{x_{J}}\sup_{x_{J+1}}\ldots
Q_{x_{N}}\Gamma_{K}(1-\frac{1}{2}\chi_{R^{*}};x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$
if and only if
$\Gamma_{K}(\inf_{x_{J}}\sup_{x_{J+1}}\ldots
Q_{x_{N}}(1-\frac{1}{2}\chi_{R^{*}};x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$.

###### Proof.

Set $G=1-\frac{1}{2}\chi_{R^{*}}$ and note that
$\operatorname{ran}(G)\subseteq\\{\frac{1}{2},1\\}$. Thus, in what follows,
all suprema are maxima and all infima are minima. Also, we may assume $K>0$.

We proceed by induction on $N-J$. We begin with the base case for (1), that
is, $J=N-1$. Without loss of generality, we may assume that one of the two
quantities in (1) is no larger than $\frac{1}{2}$. Since
$\Gamma_{K}(\sup_{x_{N}}G;x_{1},\ldots,x_{N-1},n)\geq\sup_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)$,
we may assume $\sup_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$.
By Lemma 3.6, we have that $G(x_{0},x_{1},\ldots,x_{N},n)=\frac{1}{2}$ for all
$x_{N}\in\ N$ and all $x_{0}<K$. By Lemma 3.6 again,
$\Gamma_{K}(\sup_{x_{N}}G;x_{1},\ldots,x_{N-1},n)\leq\frac{1}{2}$.

We now consider the base case for (2). Again, we may assume one of the two
quantities in (2) is no larger than $\frac{1}{2}$. Since
$\Gamma_{K}(\inf_{x_{N}}G;x_{1},\ldots,x_{N-1},n)\leq\inf_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)$,
we assume $\Gamma_{K}(\inf_{x_{N}}G;x_{1},\ldots,x_{N-1},n)\leq\frac{1}{2}$.
By Lemma 3.6, $\inf_{x_{N}}G(x_{0},\ldots,x_{N},n)=\frac{1}{2}$ for all
$x_{0}<K$. Consequently, for each $x_{0}<K$, there exists
$\xi_{x_{0}}\in\mathbb{N}$ so that
$G(x_{0},\ldots,x_{N-1},\xi_{x_{0}},n)=\frac{1}{2}$. Let

$\xi=\left\\{\begin{array}[]{cc}\max_{x_{0}<K}\xi_{x_{0}}&\mbox{if $N$ odd}\\\
0&\mbox{otherwise}.\\\ \end{array}\right.$

By the definition of $R^{*}$, it follows that
$G(x_{0},\ldots,x_{N-1},\xi,n)=\frac{1}{2}$ for all $x_{0}<K$. By Lemma 3.6
again, $\inf_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$.

We now perform the inductive step for (1). Suppose that $N-J>1$ and set
$H=\inf_{x_{J+1}}\ldots Q_{x_{N}}G$. By the inductive hypothesis, it suffices
to show that $\sup_{x_{J}}\Gamma_{K}(H;x_{1},\ldots,x_{J},n)\leq\frac{1}{2}$
if and only if
$\Gamma_{K}(\sup_{x_{J}}H;x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$. Without
loss of generality, we assume
$\sup_{x_{J}}\Gamma_{K}(H;x_{1},\ldots,x_{J},n)\leq\frac{1}{2}$ By Lemma 3.6,
for all $x_{J}\in\ N$ and all $x_{0}<K$,
$H(x_{0},x_{1},\ldots,x_{J},n)=\frac{1}{2}$. By Lemma 3.6 again,
$\Gamma_{K}(\sup_{x_{J}}H;x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$.

We now carry out the inductive step for (2). In this case, we consider the
function $H=\sup_{x_{J+1}}\ldots Q_{x_{N}}G(x_{0},\ldots,x_{N},n)$. It
suffices to show that
$\inf_{x_{J}}\Gamma_{K}(H;x_{1},\ldots,x_{J},n)\leq\frac{1}{2}$ if and only if
$\Gamma_{K}(\inf_{x_{J}}H;x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$. Without
loss of generality, we assume
$\Gamma_{K}(\inf_{x_{J}}H;x_{1},\ldots,x_{J-1},n)\leq\frac{1}{2}$. By Lemma
3.6, for every $x_{0}<K$, $\inf_{x_{J}}H(x_{0},\ldots,x_{J},n)=\frac{1}{2}$,
whence, for every $x_{0}<K$, there exists $\xi_{x_{0}}\in\mathbb{N}$ so that
$H(x_{0},\ldots,x_{J-1},\xi_{x_{0}},n)=\frac{1}{2}$. Let

$\xi=\left\\{\begin{array}[]{cc}\max_{x_{0}<K}\xi_{x_{0}}&\mbox{$J$ odd}\\\
0&\mbox{otherwise}.\\\ \end{array}\right.$

By the definition of $R^{*}$,
$H(x_{0},x_{1},\ldots,x_{J-1},\xi,n)=\frac{1}{2}$ for all $x_{0}<K$. By Lemma
3.6, $\Gamma_{K}(\inf_{x_{J}}H;x_{0},\ldots,x_{J-1},n)=\frac{1}{2}$. ∎

We note that while Lemma 3.8 is hardly the key result of this section, it is
nevertheless somewhat surprising. In general, one does not expect to be able
to interchange summation with $\sup$ or $\inf$. It is here that the use of
$R^{*}$ comes in to consideration and provides a path to a weaker conclusion
but one that is just strong enough to effect the rest of the proof.

###### Proof of Theorem 3.5.

It suffices to prove (1); part (2) follows by considering complements. Once
again, set $G=1-\frac{1}{2}\chi_{R^{*}}$.

Suppose $n\in\vec{\forall}R$. It follows from Lemmas 3.3 and 3.7 that

$\sup_{x_{0}}\inf_{x_{1}}\ldots Q_{x_{N}}G(x_{0},\ldots,x_{N},n)=\frac{1}{2}.$

Thus, by Lemma 3.6, $\Gamma_{K}(\inf_{x_{1}}\ldots
Q_{x_{N}}G;n)\leq\frac{1}{2}$. By Lemma 3.8, we have that

$\inf_{x_{1}}\ldots
Q_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}.$

Since $G\leq 1$, it follows that

$\inf_{x_{1}}\ldots
Q_{x_{N}}\Gamma(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}+2^{-(K+1)}$

for all $K\in\mathbb{N}$. Hence, $\sup_{x_{0}}\inf_{x_{1}}\ldots
Q_{x_{N}}\Gamma(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$.

Conversely, suppose $\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}\Gamma(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$. Since $G>0$, for
every $K\in\mathbb{N}$, $\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}\Gamma_{K}(G;x_{1},\ldots,x_{N},n)\leq\frac{1}{2}$. By Lemmas 3.6 and
3.8, for every $x_{0}<K$, $\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}G(x_{0},\ldots,x_{N},n)=\frac{1}{2}$. Thus,
$\sup_{x_{0}}\inf_{x_{1}}\sup_{x_{2}}\ldots
Q_{x_{N}}G(x_{0},\ldots,x_{N},n)=\frac{1}{2}$. It follows from Lemma 3.3 that
$n\in\vec{\forall}R^{*}$. Thus, by Lemma 3.7, $n\in\vec{\forall}R$. ∎

##  4\. Finitary diagram results- upper bounds

We begin by considering the quantifier-free diagrams.

######  Proposition 4.1.

If $\mathcal{M}$ is a computably presentable $L$-structure, then the closed
quantifier-free diagram of $\mathcal{M}$ is $\Pi^{0}_{1}$ and the open
quantifier-free diagram of $\mathcal{M}$ is $\Sigma^{0}_{1}$.

###### Proof.

The proposition follows from the observation that if $\mathcal{M}$ is
computably presentable, then the map $\phi\mapsto\phi^{\mathcal{M}}$ is
computable on the set of quantifier-free sentences of $L$. ∎

We note that the proof of Proposition 4.1 is uniform; that is, from an index
of a presentation of $\mathcal{M}$, it is possible to compute a $\Pi^{0}_{1}$
index of the closed quantifier-free diagram of $\mathcal{M}$ and a
$\Sigma^{0}_{1}$ index of the open quantifier-free diagram of $\mathcal{M}$.

We now consider the higher-level diagrams.

######  Theorem 4.2.

Let $\mathcal{M}$ be a computably presentable $L$-structure, and let $N$ be a
positive integer.

  1. (1)

The closed $\Pi_{N}$ diagram of $\mathcal{M}$ is $\Pi^{0}_{N}$, and the open
$\Pi_{N}$ diagram of $\mathcal{M}$ is $\Sigma^{0}_{N+1}$.

  2. (2)

The closed $\Sigma_{N}$ diagram of $\mathcal{M}$ is $\Pi^{0}_{N+1}$, and the
open $\Sigma_{N}$ diagram of $\mathcal{M}$ is $\Sigma^{0}_{N}$.

Moreover, the results of (1) and (2) hold uniformly in the sense that from $N$
and an index for a computable presentation for $\mathcal{M}$, one can compute
an index for any of the above diagrams.

###### Proof.

Throughout this proof, we fix a computable presentation $\mathcal{M}^{\sharp}$
of $\mathcal{M}$. We proceed by induction on $N$, the base case being true by
Proposition 4.1. We now fix a positive integer $N$ and assume that (1) and (2)
hold uniformly for every $M<N$.

Fix a $\Pi_{N}$ sentence $\phi$ and a rational number $q$. Note that $\phi$
has the form $\sup_{\overline{x}}\psi$, where $\psi$ is a $\Sigma_{N-1}$ wff
of $L$ and $\overline{x}$ is a tuple of variables. Since the rational points
of $\mathcal{M}^{\sharp}$ are dense,
$\sup_{\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp})}\psi^{\mathcal{M}}(\overline{a})=\sup_{\overline{a}\in|\mathcal{M}|}\psi^{\mathcal{M}}(\overline{a})$.
Thus,

$\displaystyle\phi^{\mathcal{M}}\leq q$ $\displaystyle\iff$
$\displaystyle(\forall k\in\mathbb{N})\
(\forall\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp}))\
\psi^{\mathcal{M}}(\overline{a})\leq q+2^{-k}.$

If $N=1$, then by the uniformity of Proposition 4.1, the statement
$\psi^{\mathcal{M}}(\overline{a})\leq q+2^{-k}$ is a $\Pi^{0}_{1}$ condition
on $\phi,\overline{a},k$. If $N>1$, then this statement is a $\Pi^{0}_{N}$
condition since (2) is assumed to hold uniformly for $M<N$. In either case it
then follows that $\phi^{\mathcal{M}}\leq q$ is a $\Pi^{0}_{N}$ condition on
$\phi,q$.

Furthermore,

$\displaystyle\phi^{\mathcal{M}}<q$ $\displaystyle\iff$ $\displaystyle(\exists
k\in\mathbb{N})\ (\forall\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp}))\
\psi^{\mathcal{M}}(\overline{a})\leq q-2^{-k}.$

As before, if $N=1$, then the statement $\psi^{\mathcal{M}}(\overline{a})\leq
q-2^{-k}$ is a $\Pi^{0}_{1}$ condition on $\phi,\overline{a},k$. If $N>1$,
then this statement is a $\Pi^{0}_{N}$ condition since (2) is assumed to hold
uniformly for $M<N$. In either case, it follows that $\phi^{\mathcal{M}}<q$ is
a $\Sigma^{0}_{N+1}$ condition on $\phi,q$.

Now fix a $\Sigma_{N}$ sentence $\phi$ and a rational number $q$. Then $\phi$
has the form $\inf_{\overline{x}}\psi$, where $\psi$ is a $\Pi_{N-1}$ wff of
$L$ and $\overline{x}$ is a tuple of variables. Again, since the rational
points of $\mathcal{M}^{\sharp}$ are dense,
$\inf_{\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp})}\psi^{\mathcal{M}}(\overline{a})=\inf_{\overline{a}\in|\mathcal{M}|}\psi^{\mathcal{M}}(\overline{a})$.
Thus,

$\displaystyle\phi^{\mathcal{M}}\leq q$ $\displaystyle\iff$
$\displaystyle(\forall k\in\mathbb{N})\
(\exists\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp}))\
\psi^{\mathcal{M}}(\overline{a})<q+2^{-k}.$

If $N=1$, then the statement $\psi^{\mathcal{M}}(\overline{a})<q+2^{-k}$ is a
$\Sigma^{0}_{1}$ condition on $\phi,\overline{a},k$. If $N>1$, then this
statement is a $\Sigma^{0}_{N}$ condition since (1) is assumed to hold
uniformly for $M<N$. In either case, it then follows that
$\phi^{\mathcal{M}}\leq q$ is a $\Pi^{0}_{N+1}$ condition on $\phi,q$.

Finally,

$\displaystyle\phi^{\mathcal{M}}<q$ $\displaystyle\iff$ $\displaystyle(\exists
k\in\mathbb{N})\ (\exists\overline{a}\in\mathbb{Q}(\mathcal{M}^{\sharp}))\
\psi^{\mathcal{M}}(\overline{a})<q-2^{-k}.$

If $N=1$, then the statement $\psi^{\mathcal{M}}(\overline{a})<q-2^{-k}$ is a
$\Sigma^{0}_{1}$ condition on $\phi,\overline{a},k$. If $N>1$, then this
statement is a $\Sigma^{0}_{N}$ condition since (1) is assumed to hold
uniformly for $M<N$. In either case, it then follows that
$\phi^{\mathcal{M}}<q$ is a $\Sigma^{0}_{N}$ condition on $\phi,q$.

Finally, we note that these arguments are uniform in the sense described
above. ∎

##  5\. Finitary diagram results- lower bounds

We demonstrate that the results in Section 4 are the best possible by means of
the following.

######  Theorem 5.1.

There is a language $L^{\prime}$ and a computably presentable
$L^{\prime}$-structure $\mathcal{M}$ with the following properties:

  1. (1)

The closed quantifier-free diagram of $\mathcal{M}$ is $\Pi^{0}_{1}$-complete,
and the open quantifier-free diagram of $\mathcal{M}$ is
$\Sigma^{0}_{1}$-complete.

  2. (2)

For every positive integer $N$, the closed $\Pi_{N}$ diagram of $\mathcal{M}$
is $\Pi^{0}_{N}$-complete, and the open $\Pi_{N}$ diagram of $\mathcal{M}$ is
$\Sigma^{0}_{N+1}$-complete.

  3. (3)

For every positive integer $N$, the closed $\Sigma_{N}$ diagram of
$\mathcal{M}$ is $\Pi^{0}_{N+1}$-complete, and the open $\Sigma^{0}_{N}$
diagram of $\mathcal{M}$ is $\Sigma^{0}_{N}$-complete.

###### Proof.

Let $L^{\prime}$ be the metric language that consists of the following.

  1. (1)

A constant symbol $\underline{0}$.

  2. (2)

A family of constant symbols $(c_{n})_{n\in\mathbb{N}}$.

  3. (3)

A family of predicate symbols $(P_{N,n})_{N,n\in\mathbb{N}}$, where $P_{2N,n}$
and $P_{2N+1,n}$ are $(N+1)$-ary.

Here, each predicate symbol is assumed to have modulus of continuity equal to
the constant function $1$.

We now define our $L^{\prime}$-structure $\mathcal{M}$. The underlying metric
space of $\mathcal{M}$ is the set $\mathbb{N}$ of natural numbers equipped
with its discrete metric. We also set $\underline{0}^{\mathcal{M}}=0$. In
order to define the interpretations of the other symbols, we first set

$f_{N}=\left\\{\begin{array}[]{cc}\Gamma(1-\frac{1}{2}\chi_{R_{N}^{*}})&\mbox{$N$
even}\\\ \Gamma(\frac{1}{2}\chi_{(\neg R_{N})^{*}})&\mbox{otherwise.}\\\
\end{array}\right.$

We can now set

$c_{n}^{\mathcal{M}}=\left\\{\begin{array}[]{cc}f_{0}(n/2)&\mbox{$n$ even}\\\
f_{1}((n-1)/2)&\mbox{otherwise}.\\\ \end{array}\right.$

Finally, set
$P^{\mathcal{M}}_{2N,n}(a_{0},\ldots,a_{N})=f_{2N+2}(a_{0},\ldots,a_{N},n)$,
and let
$P^{\mathcal{M}}_{2N+1,n}(a_{0},\ldots,a_{N})=f_{2N+3}(a_{0},\ldots,a_{N},n)$.

It is clear that $\mathcal{M}$ has a computable presentation. In fact, one may
simply take the $n$-th distinguished point to be $n$.

We first note that the closed atomic diagram of $\mathcal{M}$ is
$\Pi^{0}_{1}$-complete. To see this, let $\phi_{n}$ be the sentence
$d(c_{2n},0)$. Then, by Theorem 3.5, $\phi_{n}^{\mathcal{M}}\leq\frac{1}{2}$
if and only if $n\in\vec{\forall}R_{0}$.

Similarly, the open atomic diagram of $\mathcal{M}$ is
$\Sigma^{0}_{1}$-complete. This time, let $\phi_{n}$ be the sentence
$d(c_{2n+1},0)$. Then, by Theorem 3.5, $\phi_{n}^{\mathcal{M}}<\frac{1}{2}$ if
and only if $n\in\vec{\exists}R_{0}$.

Next fix a positive integer $N$. For each $n\in\mathbb{N}$, let $\phi_{n}$ be
the sentence

$\inf_{x_{1}}\ldots Q_{x_{N}}P_{2N,n}(x_{1},\ldots,x_{N}),$

and let $\psi_{n}$ be the sentence

$\sup_{x_{1}}\ldots Q_{x_{N}}P_{2N+1,n}(x_{1},\ldots,x_{N}).$

By Theorem 3.5, $\phi_{n}^{\mathcal{M}}\leq\frac{1}{2}$ if and only if
$n\in\vec{\forall}R_{2N}$. Thus, the closed $\Sigma_{N}$ diagram of
$\mathcal{M}$ is $\Pi^{0}_{N+1}$-complete. Also by Theorem 3.5,
$\psi_{n}^{\mathcal{M}}<\frac{1}{2}$ if and only if
$n\in\vec{\exists}R_{2N+1}$. Thus, the open $\Pi_{N}$ diagram of $\mathcal{M}$
is $\Sigma^{0}_{N+1}$-complete.

Since the open $\Pi_{N-1}$ diagram of $\mathcal{M}$ is
$\Sigma^{0}_{N}$-complete, it follows that the open $\Sigma_{N}$ diagram of
$\mathcal{M}$ is $\Sigma^{0}_{N}$-complete. It similarly follows that the
closed $\Pi_{N}$ diagram of $\mathcal{M}$ is $\Pi^{0}_{N}$-complete. ∎

We conclude this section with some remarks on the choice of structure in the
above proof. Since structures in continuous logic must be bounded, it might
seem that the unit interval is a natural setting in which to construct these
lower bounds. However, it is well-known that the evaluation of maxima of
computable functions on a computably compact space is a computable operation
(see, e.g. Chapter 6 of [13]). Thus, the closed and open diagrams for a metric
structure with a computably compact presentation are $\Pi^{0}_{1}$ and
$\Sigma^{0}_{1}$ respectively. It is fairly easy to see that the standard
presentation of $[0,1]$ (i.e. the presentation in which the distinguished
points are precisely the rational numbers in $[0,1]$) is computably compact.
On the other hand, the natural numbers under the discrete metric provides the
simplest non-trivial setting that is bounded and not compact.

##  6\. Infinitary results

When formulating our diagram complexity results for infinitary logic, we
actually must eschew the terminology of diagrams. The reason for this is that,
because of the coding of the computable infinitary formulae, these diagrams
are capable of computing $\mathcal{O}$, which itself is
$\Pi^{1}_{1}$-complete. In order to avoid this pitfall, we focus on the
complexity of the right Dedekind cuts of reals of the form
$\phi^{\mathcal{M}}$ where $\phi$ is infinitary. To this end, for
$x\in\mathbb{R}$, we let $D^{>}(x)$ denote the right Dedekind cut of $x$, that
is,

$D^{>}(x)=\\{q\in\mathbb{Q}\ :\ q>x\\}.$

We also set

$D^{\geq}(x)=\\{q\in\mathbb{Q}\ :\ q\geq x\\}.$

Of course, if $x$ is irrational, then $D^{>}(x)=D^{\geq}(x)$. In terms of
evaluating complexity, differences only arise when considering uniformity.

We first prove our infinitary upper bound result which generalizes our bounds
in the finitary case.

######  Theorem 6.1.

Let $\mathcal{M}$ be a computably presentable $L$-structure and let $\phi$ be
a computable infinitary sentence of $L$.

  1. (1)

If $\phi$ is $\Pi^{c}_{\alpha}$, then $D^{>}(\phi^{\mathcal{M}})$ is
$\Sigma^{0}_{\alpha+1}$ uniformly in a code of $\phi$, and
$D^{\geq}(\phi^{\mathcal{M}})$ is $\Pi^{0}_{\alpha}$ uniformly in a code of
$\phi$.

  2. (2)

If $\phi$ is $\Sigma^{c}_{\alpha}$, then $D^{>}(\phi^{\mathcal{M}})$ is
$\Sigma^{0}_{\alpha}$ uniformly in a code of $\phi$, and
$D^{\geq}(\phi^{\mathcal{M}})$ is $\Pi^{0}_{\alpha+1}$ uniformly in a code of
$\phi$.

###### Proof.

Fix a computable presentation $\mathcal{M}^{\sharp}$ of $\mathcal{M}$. Let
$\phi$ be a computable infinitary sentence of $L$.

Suppose $\phi\in\Sigma^{c}_{\alpha}\cup\Pi^{c}_{\alpha}$. A code for $\phi$
yields a notation $a$ for $\alpha$. In the following, all other ordinals
considered are less than $\alpha$. For ease of exposition, we identify each
$\beta\leq\alpha$ with its unique notation in $\\{b\ :\
b\leq_{\mathcal{O}}a\\}$.

We proceed by effective transfinite recursion. Thus, we assume the following
hold uniformly in an index of $\mathcal{M}^{\\#}$.

  1. (1)

From a $\beta<\alpha$ and a code of a $\Pi_{\beta}^{c}$ sentence $\psi$, it is
possible to compute a $\Pi^{0}_{\beta}$ index of
$D^{\geq}(\psi^{\mathcal{M}})$ and a $\Sigma^{0}_{\beta+1}$-index of
$D^{>}(\psi^{\mathcal{M}})$.

  2. (2)

From a $\beta<\alpha$ and a code of a $\Sigma_{\beta}^{c}$ sentence $\psi$, it
is possible to compute a $\Pi^{0}_{\beta+1}$-index of $D^{\geq}(\psi)$ and a
$\Sigma^{0}_{\beta}$-index of $D^{>}(\psi_{i})$.

First suppose that $\phi$ is a $\Pi_{\alpha}^{c}$ sentence. Thus, $\phi$ has
the form $\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{i\in
I}\sup_{\overline{x_{i}}}\phi_{i}$ where $I$ is c.e. and $\phi_{i}$ is
$\Sigma_{\beta_{i}}^{c}$ for some $\beta_{i}<\alpha$. Furthermore, we may
assume $(\beta_{i})_{i\in I}$ is computable. For $q\in\mathbb{Q}$, we have

$q\in D^{\geq}(\phi^{\mathcal{M}})\Leftrightarrow(\forall
k\in\mathbb{N})(\forall i\in
I)(\forall\overline{r}\in\mathbb{Q}(\mathcal{M}^{\\#}))\ q+2^{-k}\in
D^{>}(\phi_{i}^{\mathcal{M}}(\overline{r})).$

As $\emptyset^{(\alpha)}$ computes
$D^{>}(\Phi_{i}^{\mathcal{M}}(\overline{r}))$ uniformly in $i$,
$D^{\geq}(\phi^{\mathcal{M}})$ is co-c.e. in $\emptyset^{(\alpha)}$, that is,
$D^{\geq}(\phi^{\mathcal{M}})$ is $\Pi^{0}_{\alpha}$. At the same time,

$q\in D^{>}(\phi^{\mathcal{M}})\ \iff\ (\exists k\in\mathbb{N})(\forall i\in
I)(\forall\overline{r}\in\mathbb{Q}(\mathcal{M}^{\\#}))\ q-2^{-k}\not\in
D^{>}(\phi_{i}^{\mathcal{M}}(\overline{r}).$

Thus, $D^{>}(\phi^{\mathcal{M}})$ is
$\Sigma^{0}_{2}(\emptyset^{(\alpha)})=\Sigma_{\alpha+1}^{0}$.

Now suppose $\phi$ is a $\Sigma^{c}_{\alpha}$ sentence. Thus, $\phi$ has the
form $\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}_{i\in
I}\inf_{\overline{x_{i}}}\phi_{i}$ where $I$ is c.e. and $\phi_{i}$ is
$\Pi_{\beta_{i}}^{c}$ for some $\beta_{i}<\alpha$ uniformly in $i$. Let
$q\in\mathbb{Q}$. Then,

$q\in D^{\geq}(\phi^{\mathcal{M}})\ \iff\ (\forall k\in\mathbb{N})(\exists
i\in I)(\exists\overline{r}\in\mathbb{Q}(\mathcal{M}^{\\#}))q+2^{-k}\in
D^{>}(\phi_{i}^{\mathcal{M}}(\overline{r})).$

Thus, $D^{\geq}(\phi^{\mathcal{M}})$ is
$\Sigma^{0}_{2}(\emptyset^{(\alpha)})=\Sigma^{0}_{\alpha+1}$. In addition,

$q\in D^{>}(\phi_{i_{0}}^{\mathcal{M}})\ \iff\ (\exists
k\in\mathbb{N})(\exists i\in
I)(\exists\overline{r}\in\mathbb{Q}(\mathcal{M}^{\\#}))\ q-2^{-k}\not\in
D^{>}(\phi_{i}^{\mathcal{M}}(\overline{r})).$

Thus, $D^{>}(\phi^{\mathcal{M}})$ is
$\Sigma^{0}_{1}(\emptyset^{(\alpha)})=\Sigma^{0}_{\alpha}$.

As these arguments are all uniform in an index of $\mathcal{M}^{\\#}$ and a
code for $\phi$, the theorem is proven. ∎

We now demonstrate the optimality of Theorem 6.1 by means of the following.

######  Theorem 6.2.

There is a language $L^{\prime\prime}$ and an $L^{\prime\prime}$-structure
$\mathcal{M}$ so that the following hold for every computable ordinal
$\alpha$.

  1. (1)

There is a computable sequence $(\psi_{i})_{i\in\mathbb{N}}$ of
$\Pi^{c}_{\alpha}$ sentences of $L^{\prime\prime}$ so that $\\{i\ :\
\frac{1}{2}\in D^{\geq}(\psi^{\mathcal{M}}_{\alpha})\\}$ is
$\Pi^{0}_{\alpha}$-complete.

  2. (2)

There is a computable sequence $(\psi_{i})_{i\in\mathbb{N}}$ of
$\Sigma^{c}_{\alpha}$ sentences of $L^{\prime\prime}$ so that $\\{i\ :\
\frac{1}{2}\in D^{>}(\psi^{\mathcal{M}}_{\alpha})\\}$ is
$\Sigma^{0}_{\alpha}$-complete.

  3. (3)

There is a computable sequence $(\psi_{i})_{i\in\mathbb{N}}$ of
$\Pi^{c}_{\alpha}$ sentences of $L^{\prime\prime}$ so that $\\{i\ :\
\frac{1}{2}\in D^{>}(\psi^{\mathcal{M}}_{\alpha})\\}$ is
$\Sigma^{0}_{\alpha+1}$-complete.

  4. (4)

There is a computable sequence $(\psi_{i})_{i\in\mathbb{N}}$ of
$\Sigma^{c}_{\alpha}$ sentences of $L^{\prime\prime}$ so that $\\{i\ :\
\frac{1}{2}\in D^{\geq}(\psi^{\mathcal{M}}_{\alpha})\\}$ is
$\Pi^{0}_{\alpha+1}$-complete.

The remainder of this section is dedicated to the proof of Theorem 6.2. We
begin with the construction of $L^{\prime\prime}$ and $M^{\prime\prime}$.

Let $L_{0}$ be a language consisting of one constant symbol $\underline{q}$
for every $q\in\mathbb{Q}\cap[0,1]$ and let $\mathcal{M}_{0}$ be the
$L_{0}$-structure whose underlying metric space is $[0,1]$ with its usual
metric and which interprets each $\underline{q}$ as $q$. Let
$L^{\prime\prime}$ be the expansion of $L_{0}$ obtained by adding a family
$(c_{N,n,x_{1},\ldots,x_{N+1}})_{N,n,x_{1},\ldots,x_{N+1}\in\mathbb{N}}$ of
constant symbols.

Let $\mathcal{M}$ be the expansion of $\mathcal{M}_{0}$ obtained by setting
$c_{N,n,x_{1},\ldots,x_{N+1}}^{\mathcal{M}}=\frac{1}{2}(1-\chi_{R_{2N+1}}(n,x_{1},\ldots,x_{N+1}))$.
Since $(R_{N})_{N\in\mathbb{N}}$ is computable, it follows that $\mathcal{M}$
is computably presentable.

We now verify that $L^{\prime\prime}$ and $\mathcal{M}$ satisfy the
conclusions of Theorem 6.2. We will need a little additional terminology and
two lemmas.

Suppose $(\psi_{i})_{i\in\mathbb{N}}$ is a sequence of $\Pi^{c}_{\alpha}$
sentences of $L^{\prime\prime}$. We say that a set $S$ is _encoded_ by
$(\psi_{i})_{i\in\mathbb{N}}$ if
$\psi_{i}^{\mathcal{M}}=1-\frac{1}{2}\chi_{S}(i)$ for all $i$.

Similarly, if $(\psi_{i})_{i\in\mathbb{N}}$ is a sequence of
$\Sigma^{c}_{\alpha}$ sentences of $L^{\prime\prime}$, we say that a set $S$
is _encoded_ by $(\psi_{i})_{i\in\mathbb{N}}$ if
$\psi_{i}^{\mathcal{M}}=\frac{1}{2}(1-\chi_{S}(i))$ for all $i$.

######  Lemma 6.3.

Let $\alpha$ be a computable ordinal.

  1. (1)

Every $\Sigma^{0}_{\alpha}$ set is encoded by a computable sequence of
$\Sigma^{c}_{\alpha}$ sentences.

  2. (2)

Every $\Pi^{0}_{\alpha}$ set is encoded by a computable sequence of
$\Pi^{c}_{\alpha}$ sentences.

###### Proof.

We prove (1). Part (2) then follows by considering complements. Suppose $S$ is
$\Sigma^{0}_{\alpha}$.

If $\alpha=0$, then we let

$\psi_{i}=\left\\{\begin{array}[]{cc}d(\underline{0},\underline{0})&i\in S\\\
d(\underline{0},\underline{\frac{1}{2}})&\mbox{otherwise.}\\\
\end{array}\right.$

Next suppose $\alpha=N+1$ where $N\in\mathbb{N}$. Let

$\psi_{n}=\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}_{x_{1}}\operatorname*{\bigvee\mkern-15.0mu\bigvee}_{x_{2}}\ldots\mathcal{C}_{x_{N+1}}d(c_{N,n,x_{1},\ldots,x_{N+1}},\underline{0}).$

Here, $\mathcal{C}$ is $\operatorname*{\bigwedge\mkern-15.0mu\bigwedge}$ if
$N$ is even and $\operatorname*{\bigvee\mkern-15.0mu\bigvee}$ if $N$ is odd.

It follows from Lemma 3.3 that $(\psi_{n})_{n\in\mathbb{N}}$ encodes
$\vec{\exists}R_{2N+1}$. Since $\vec{\exists}R_{2N+1}$ is
$\Sigma_{N+1}^{0}$-complete, it follows that every $\Sigma^{0}_{N+1}$ set is
encoded by a sequence of computable $\Sigma_{N+1}^{c}$ sentences. Furthermore,
the construction of such a sequence from a $\Sigma^{0}_{N+1}$ index is
uniform.

Suppose $\alpha\geq\omega$. Similar to the proof of Theorem 7.9 of [1], we
construct a sequence $(\phi_{n})_{n\in\mathbb{N}}$ of $\Sigma^{0}_{\alpha}$
sentences so that $\phi_{n}^{\mathcal{M}}=1-\chi_{S}(n)$. In particular, we
replace $\top$ and $\bot$ with $d(\underline{0},\underline{0})$ and
$d(\underline{0},\underline{1})$ respectively. Setting
$\psi_{n}=\frac{1}{2}\phi_{n}$ yields the desired formulae. ∎

######  Lemma 6.4.

If $(\psi_{n})_{n\in\mathbb{N}}$ is a computable sequence of
$\Pi^{c}_{\alpha}$ sentences of $L^{\prime\prime}$, then there is a computable
$\Pi^{c}_{\alpha}$ sentence $\phi$ of $L^{\prime\prime}$ so that

$\phi^{\mathcal{M}}=\sum_{n=0}^{\infty}2^{-(n+1)}\psi_{n}^{\mathcal{M}}.$

Furthermore, a code of $\phi$ can be computed from an index of
$(\psi_{n})_{n\in\mathbb{N}}$.

###### Proof.

For $a,b\in[0,1]$, let $\operatorname{avg}(a,b)=\frac{1}{2}(a+b)$. By
inspection,

$\operatorname{avg}(a,b)=\max\\{a\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}\frac{1}{2}(a\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}b),b\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}\frac{1}{2}(b\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}a)\\}.$

Thus, we may regard $\operatorname{avg}$ as a connective. If $\phi,\psi$ are
quantifier-free, then so is $\operatorname{avg}(\phi,\psi)$.

Since $\operatorname{avg}$ is increasing in each variable and continuous, it
follows that
$\operatorname{avg}(\sup_{j}a_{j},\sup_{k}b_{k})=\sup_{j,k}\operatorname{avg}(a_{j},b_{k})$
and
$\operatorname{avg}(\inf_{j}a_{j},\inf_{k}b_{k})=\inf_{j,k}\operatorname{avg}(a_{j},b_{k})$.
From this it follows that $\operatorname{avg}(\phi,\psi)$ is equivalent to a
$\Pi^{c}_{\alpha}$ (resp. $\Sigma^{c}_{\alpha}$) sentence if $\phi$ and $\psi$
are $\Pi^{c}_{\alpha}$ (resp. $\Sigma^{c}_{\alpha}$) sentences.

When $a_{0},\ldots,a_{K+1}\in[0,1]$, note that

$\sum_{n=0}^{K+1}2^{-(n+1)}a_{n}=\operatorname{avg}(\phi_{0},\sum_{n=0}^{K}2^{-(n+1)}\phi_{n+1}).$

Thus, we may regard inner product with $(2^{-(n+1)})_{n=0}^{K}$ as a
connective. Furthermore, a code of $\sum_{n=0}^{K}2^{-(n+1)}\phi_{n}$ can be
computed from codes of $\phi_{0},\ldots,\phi_{K}$.

Finally, when $a_{n}\in[0,1]$, we have

$\sum_{n=0}^{\infty}a_{n}=\sup_{K}\sum_{n=0}^{K}a_{n}.$

The conclusion of the lemma follows. ∎

###### Proof of Theorem 6.2.

Parts (1) and (2) follow directly from Lemma 6.3.

Now suppose $S$ is $\Sigma^{0}_{\alpha+1}$ complete. Take a $\Pi^{0}_{\alpha}$
binary relation $R$ so that $S=\vec{\exists}R$. By Lemma 6.3, there is a
computable family $(\psi_{n,x_{1}})_{n,x_{1}\in\mathbb{N}}$ of
$\Pi^{c}_{\alpha}$ sentences so that for all $n,x_{1}\in\mathbb{N}$,
$\psi_{n,x_{1}}^{\mathcal{M}}=1-\frac{1}{2}\chi_{R}(n,x_{1})$. By Lemma 6.4,
there is a computable sequence $(\phi_{n})_{n\in\mathbb{N}}$ of
$\Pi^{c}_{\alpha}$ sentences so that

$\phi_{n}^{\mathcal{M}}=\sum_{x_{1}=0}^{\infty}2^{-(x_{1}+2)}\psi_{n,x_{1}}^{\mathcal{M}}.$

It then follows that $n\in S$ if and only if $\frac{1}{2}\in
D^{>}(\phi_{n}^{\mathcal{M}})$, establishing (3). Part (4) follows by
considering complements. ∎

Returning to an earlier point, we note that the closed and open quantifier-
free diagrams of $\mathcal{M}$ are $\Pi^{0}_{1}$-complete and
$\Sigma^{0}_{1}$-complete respectively. To see this, fix a $\Sigma^{0}_{1}$
complete set $C$, and let $(c_{s})_{s=0}^{\infty}$ be an effective enumeration
of $C$. Since $C$ is infinite, we may assume this enumeration is one-to-one.
Let

$p_{n}=\begin{cases}\frac{1}{2}-2^{-s}&\text{ if }n=c_{s}\\\
\frac{1}{2}&\text{ otherwise. }\end{cases}$

It is fairly straightforward to show that $(p_{n})_{n\in\mathbb{N}}$ is
computable as a sequence of reals. Furthermore, $p_{n}<\frac{1}{2}$ if and
only if $n\in C$. Since $L^{\prime\prime}$ contains a constant symbol for each
rational number, it follows that the open quantifier-free diagram of
$\mathcal{M}$ is $\Sigma^{0}_{1}$-complete. The $\Pi^{0}_{1}$-completeness of
the closed quantifier-free diagram follows by considering complements.

We also note that while computably compact domains are insufficient for
demonstrating lower bounds in the finitary case, $[0,1]$ works swimmingly in
the infinitary case.

Finally, we note that the infinitary sentences in the above proof are built up
from quantifier-free sentences. Thus, they do not require moduli of
continuity. Therefore, although we have framed our work in an effectivization
of the infinitary continuous logic of Eagle, our results will hold in any
reasonable effectivization of the infinitary continuous logic of Ben-Yaacov
and Iovino.

##  7\. Conclusion

We have introduced a framework for examining the complexity of the quantifier
levels of the finitary and infintary theory of a computably presented metric
space and we have pinned down the complexity at each level in terms of the
hyperarithmetical hierarchy. Our demonstration of the lower bounds in the
finitary case introduces a novel method for encoding $\Sigma_{N}$ and
$\Pi_{N}$ conditions into series inequalities. Our demonstration of the lower
bounds in the infinitary case is mostly straightforward. However, our
supporting result that computable infinitary logic can represent the inner
product with $(2^{-(n+1)})_{n=0}^{\infty}$ from the connectives $\neg$,  . $-$
, $\frac{1}{2}$ appears to be new. Our examples in these demonstrations are
somewhat artificial. We leave open directions such as the analysis of the
theories of specific structures such as Lebesgue spaces or the construction of
examples at different levels of complexity within natural classes such as
Banach spaces or $C^{*}$-algebras.

## References

  * [1] C. J. Ash and J. Knight, _Computable structures and the hyperarithmetical hierarchy_ , Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000.
  * [2] ItaïBen Yaacov, Alexander Berenstein, C. Ward Henson, and Alexander Usvyatsov, _Model theory for metric structures_ , Model theory with applications to algebra and analysis. Vol. 2, London Math. Soc. Lecture Note Ser., vol. 350, Cambridge Univ. Press, Cambridge, 2008, pp. 315–427.
  * [3] Itaï Ben Yaacov and José Iovino, _Model theoretic forcing in analysis_ , Ann. Pure Appl. Logic 158 (2009), no. 3, 163–174.
  * [4] John Chisholm and Michael Moses, _An undecidable linear order that is $n$-decidable for all $n$_, Notre Dame J. Formal Logic 39 (1998), no. 4, 519–526.
  * [5] S. Barry Cooper, _Computability theory_ , Chapman & Hall/CRC, Boca Raton, FL, 2004.
  * [6] Christopher J. Eagle, _Expressive power of infinitary $[0,1]$-logics_, Beyond first order model theory, CRC Press, Boca Raton, FL, 2017, pp. 3–22.
  * [7] E. B. Fokina, S. S. Goncharov, V. Kharizanova, O. V. Kudinov, and D. Turetski, _Index sets of $n$-decidable structures that are categorical with respect to $m$-decidable representations_, Algebra Logika 54 (2015), no. 4, 520–528, 544–545, 547–548.
  * [8] Ekaterina B. Fokina, Valentina Harizanov, and Alexander G. Melnikov, _Computable model theory_ , Turing’s Legacy: Developments from Turing’s Ideas in Logic (Rod Downey, ed.), Cambridge University Press, Cambridge, 2014\.
  * [9] Johanna N. Y. Franklin and Timothy H. McNicholl, _Degrees of and lowness for isometric isomorphism_ , J. Log. Anal. 12 (2020), Paper No. 6, 23\.
  * [10] Alexander G. Melnikov, _Computably isometric spaces_ , J. Symbolic Logic 78 (2013), no. 4, 1055–1085.
  * [11] Gerald E. Sacks, _Higher recursion theory_ , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970 (92a:03062)
  * [12] R.I. Soare, _Recursively enumerable sets and degrees_ , Springer-Verlag, Berling, Heidelberg, 1987.
  * [13] Klaus Weihrauch, _Computable analysis_ , Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.