# Non-magnetic layers with a single Dirac cone at high-symmetry point of the
Brillouin zone

Vladimir Damljanović<EMAIL_ADDRESS>Institute of Physics Belgrade,
University of Belgrade, Pregrevica 118, 11000 Belgrade, Serbia

(February 2020)

It is well known that a single Dirac cone at high-symmetry point (HSP) of a
Brillouin zone, akin to the one in graphenes’ band structure, can not appear
as the only quasiparticle at the Fermi level in two-dimensional (2D), non-
magnetic materials. Here we found two layer groups with time-reversal
symmetry, among all possible both without- and with spin-orbit coupling, that
host one Dirac cone at HSP and we show which additional dispersions appear: a
pair of Dirac lines on opposite BZ edges and a pair of Dirac cones that can be
moved but not removed by symmetry preserving perturbations, on the other two
BZ edges. We illustrate our theory by a tight-binding band structure and
discuss real 2D materials that belong to one of the two symmetry groups.
Finally, we single out inconsistencies in the literature showing that it is
better to focus scientist attention to a research topics itself, instead to
group of authors only (_e.g._ from one university, country etc.) dealing with
the same topics. On the other hand, repetitions of other scientist results
without due citation, destroys the spirit of science itself.

##  I Introduction

Two dimensional (2D) materials became focal point of intensive research due to
their mechanical and electrical properties suitable both for fundamental
research and applications. Materials’ 2D Brillouin zone (BZ) allows
application of topology in explanation of their physical properties. Electron
wave functions near band contacts, like Dirac cones in graphene, gain
additional significance when a 2D material is placed in the vertical magnetic
field. The absence of back-scattering and the high electron conductivity near
materials edges giving rise to Quantum Hall effect are some of the examples
[1, 2].

The crystal- and time reversal symmetry (TRS) explain both band contacts and
dispersion in their vicinity. Group theoretical methodology relies on tables
of irreducible (co)representations ((co)reps) of underlying symmetry groups.
For dispersions in three-dimensional (3D) crystals, space group
representations are firstly used for prediction of bulk chiral fermions [3],
and finalized in complete list of excitations near high-symmetry point (HSPs)
and lines (HSLs) in gray and black-and-white space groups [4, 5, 6, 7].

Regarding subperiodic groups, computer program POLSym [8] contains (co)reps
for all families of line- and layer groups and was used by [9, 10, 11] to
develop spin-group theory for quasi one-dimensional systems. On the other
hand, all types of (co)reps of all gray and ordinary layer groups are
available recently [12]. Dispersions near all HSPs and HSLs in non-magnetic 2D
materials are reported in [13], which explained published numerical and
experimental band structures (_e.g._ in [14, 15]), and can be used as a
starting point in designing new 2D materials with physical properties given in
advance. Magnetic layer- and rod groups are treated in [16], which was
published at about the same time as [13].

Topological laws forbid one Dirac cone, like those in band structure of
graphene without spin-orbit coupling (SOC), to be the only feature at a given
energy (including the Fermi level) in non-magnetic 2D materials [17, 18].
Question arises: in a given symmetry group, if it imposes Dirac cone at one BZ
HSP, what other band contacts must appear? Are those contacts essential
degeneracies or there are also accidental band contacts (ABCs)? If so, are
these ABCs protected by topology or are they truly accidental (can be gaped by
symmetry preserving perturbations)? Present paper aims to give answers to
these questions.

##  II Method

List of UNPs and UNLs is given in [13], for spinless and spinfull electrons in
the presence of TRS. The position of UNPs and UNLs is given by the
dimensionality of allowed correp of the little group. The matrices of correps
can be used to find effective Hamiltonian in the vicinity of UNPs and UNLs,
and hence the dispersions (Hamiltonian eigenvalues). We search band structures
near unmovable nodal points published in [13], to identify layer groups having
one Dirac cone in the BZ. Next, additional dispersions near UNPs and UNLs that
must be present are identified. For investigation of accidental band contacts
the non-crossing rule is applied [19, 20, 21]. For the tight-binding model, we
use the fine structure Hamiltonian $\hat{H}_{\mathrm{fs}}(\mathbf{r})$,
obtained from Dirac equation by expansion up to $(1/c)^{2}$ [22]. More
precisely, the following symmetry properties are used [23]:
$\hat{H}_{\mathrm{fs}}(g^{-1}\mathbf{r})=\hat{u}^{\dagger}(g_{0})\hat{H}_{\mathrm{fs}}(\mathbf{r})\hat{u}(g_{0})$,
where $\hat{u}(g_{0})$ represents the rotational part of layer symmetry
element $g$ in the spin space and can be found at Bilbao Crystallographic
Server [24]. In addition, TRS implies:
$\hat{H}^{*}_{\mathrm{fs}}(\mathbf{r})=\hat{\sigma}_{2}\hat{H}_{\mathrm{fs}}(\mathbf{r})\hat{\sigma}_{2}$,
with $\hat{\sigma}_{2}$ being the Pauli matrix. These symmetry properties of
$\hat{H}_{\mathrm{fs}}(\mathbf{r})$ significantly simplify tight-binding
Hamiltonian in highly symmetric layers, allowing analytical solution of
eigenvalues problem.

##  III Results

Closer look at dispersions near all HSPs and HSLs [13] for SOC case, gives
that centrosymmetric layer double groups $43^{D}$ ($p\ 2/b\ 2_{1}/a\ 2/a$) and
$45^{D}$ ($p\ 2_{1}/b\ 2_{1}/m\ 2/a$) host one Dirac point at BZ HSP. To these
groups corresponds the following space groups: $54^{D}$ ($P\ 2_{1}/c\ 2/c\
2/a$; $y=0$) and $57^{D}$ ($P\ 2/b\ 2_{1}/c\ 2_{1}/m$; $x=0$), respectively
(plane parallel to diperiodic one is also given, notation for layer- and space
groups is according to [25] and [26], respectively). Besides Dirac point there
is also a Dirac line at one edge of the BZ for each of the two groups [13].

We next investigate if additional band contacts are possible or even
unavoidable. We use allowed, extra irreps from Bilbao Crystallographic Server
[24] for corresponding space groups. For group $57^{D}$, high-symmetry line
$H$ has four one dimensional irreps being paired by TRS in the following way:
$(\overline{H}_{2},\overline{H}_{5})$ and
$(\overline{H}_{4},\overline{H}_{3})$. Screw axis of order two is represented
by $(-ie^{i\pi u},ie^{i\pi u})$ for both pairs of irreps ($u=1/2$ corresponds
to BZ corner). Near end points of line $H$ both pairs are $(-i,i)$ and
$(1,-1)$, respectively. However, at the point $Y$ ($u=0$) irreps
($\overline{Y}_{3},\overline{Y}_{4}$) are $(-2i,2i)$, while those at the BZ
corner are $(\overline{T}_{3},\overline{T}_{4})=(0,0)$. Since compatibility
relations near point $Y$ are not satisfied, two double degenerate zones must
touch an odd number of times somewhere on the line $H$ (most probably once).
For the remaining parts of the Brillouin zone, accidental band contacts are
forbidden by the non-crossing rule. Similar analysis applies to space group
$54^{D}$ with the same result. The main conclusion of this paragraph is that,
for layer groups $43^{D}$ and $45^{D}$, there are $2(2n-1)$ additional Dirac
cones somewhere at the BZ edge (the one that does not host the Dirac line),
with $n$ most probably being one. These additional Dirac cones can be moved
along the BZ edge, but cannot be gaped by symmetry preserving perturbations.

We illustrate our findings using a tight-binding example on the structure
having symmetry $45^{D}$, shown in the Figure 1 (visualization by VESTA [27]).
Eight-dimensional tight-binding Hamiltonian in the basis of $s$-orbitals and
up and down spinors
$\left\\{\left|s_{1}\uparrow\right\rangle,\left|s_{2}\uparrow\right\rangle,\left|s_{3}\uparrow\right\rangle,\left|s_{4}\uparrow\right\rangle,\left|s_{1}\downarrow\right\rangle,\left|s_{2}\downarrow\right\rangle,\left|s_{3}\downarrow\right\rangle,\left|s_{4}\downarrow\right\rangle\right\\}$,
is:

Figure 1:  Upper panel: crystal structure adopted for the tight-binding model.
Black (white) nuclei are above (below) the drawing plane. Lover panels: areas
in the reciprocal space (indicated in red color) where $E_{2}-E_{1}<0.6$ eV
(left panel; the same picture is for $E_{4}-E_{3}<0.6$ eV), _i.e._
$E_{3}-E_{2}<0.6$ eV (right panel). Black rectangles denote BZ. Parameters
$f_{0}$, $f_{1}$, $f_{2}$, $c_{1}$, $c_{2}$ are equal to $2.1$, $1.6$, $1.1$,
$1.4$, $0.9$ $\mathrm{eV}$, respectively.

$\hat{H}(\mathbf{k})=\left(\begin{array}[c]{cc}\hat{A}(\mathbf{k})&\hat{B}(\mathbf{k})\\\
\hat{B}^{\dagger}(\mathbf{k})&\hat{A}(\mathbf{k})\end{array}\right),$ (1)

with

$\hat{A}(\mathbf{k})=\left(\begin{array}[c]{cccc}f_{0}&f_{1}\left(1+e^{-i\mathbf{k}\cdot\mathbf{a}}\right)&0&f_{2}\left(1+e^{-i\mathbf{k}\cdot\mathbf{b}}\right)\\\
f_{1}\left(1+e^{i\mathbf{k}\cdot\mathbf{a}}\right)&f_{0}&f_{2}\left(1+e^{-i\mathbf{k}\cdot\mathbf{b}}\right)&0\\\
0&f_{2}\left(1+e^{i\mathbf{k}\cdot\mathbf{b}}\right)&f_{0}&f_{1}\left(1+e^{i\mathbf{k}\cdot\mathbf{a}}\right)\\\
f_{2}\left(1+e^{i\mathbf{k}\cdot\mathbf{b}}\right)&0&f_{1}\left(1+e^{-i\mathbf{k}\cdot\mathbf{a}}\right)&f_{0}\end{array}\right),$
(2)
$\hat{B}(\mathbf{k})=\left(\begin{array}[c]{cccc}0&c_{1}\left(1+e^{-i\mathbf{k}\cdot\mathbf{a}}\right)&0&ic_{2}\left(1-e^{-i\mathbf{k}\cdot\mathbf{b}}\right)\\\
-c_{1}\left(1+e^{i\mathbf{k}\cdot\mathbf{a}}\right)&0&-ic_{2}\left(1-e^{-i\mathbf{k}\cdot\mathbf{b}}\right)&0\\\
0&ic_{2}\left(1-e^{i\mathbf{k}\cdot\mathbf{b}}\right)&0&c_{1}\left(1+e^{i\mathbf{k}\cdot\mathbf{a}}\right)\\\
-ic_{2}\left(1-e^{i\mathbf{k}\cdot\mathbf{b}}\right)&0&-c_{1}\left(1+e^{-i\mathbf{k}\cdot\mathbf{a}}\right)&0\end{array}\right),$
(3)

and $f_{0}$, $f_{1}$, $f_{2}$ being real hoping parameters between zeroth, the
first, the second neighbors (parallel spins), _i.e._ $c_{1}$, $c_{2}$ being
real hoping parameters between the first, the second neighbors (antiparallel
spins). The electronic band structure, within this model is:

$E_{1,2,3,4}=f_{0}\\\ \pm
2\sqrt{c_{1}^{2}\mathrm{cos}^{2}\left(\frac{\mathbf{k}\cdot\mathbf{a}}{2}\right)+\left[\sqrt{c_{2}^{2}\mathrm{sin}^{2}\left(\frac{\mathbf{k}\cdot\mathbf{b}}{2}\right)+f_{1}^{2}\mathrm{cos}^{2}\left(\frac{\mathbf{k}\cdot\mathbf{a}}{2}\right)}\pm\left|f_{2}\mathrm{cos}\left(\frac{\mathbf{k}\cdot\mathbf{b}}{2}\right)\right|\right]^{2}},$
(4)

with each of the four bands from (4) being doubly degenerate, as expected from
Kramer’s theorem for centrosymmetric systems with SOC. Four doubly degenerate
bands are obtained by four possible combinations of $+$ and $-$ in (4). Bands
$E_{1}$, $E_{2}$, $E_{3}$, $E_{4}$ are ordered according to non-decreasing
energy for each $\mathbf{k}$ in the following way:
$(-,+)\leq(-,-)\leq(+,-)\leq(+,+)$. The four-fold degeneracy is obtained for:

$c_{2}^{2}\mathrm{sin}^{2}(\mathbf{k}\cdot\mathbf{b})+4f_{1}^{2}\mathrm{cos}^{2}\left(\frac{\mathbf{k}\cdot\mathbf{a}}{2}\right)\mathrm{cos}^{2}\left(\frac{\mathbf{k}\cdot\mathbf{b}}{2}\right)=0,$
(5)

which is valid at $\mathbf{k}\cdot\mathbf{b}=\pm\pi$ (unmovable Dirac lines).

Along lines $\mathbf{k}\cdot\mathbf{a}=\pm\pi$ dispersions (4) become:

$E_{1,2,3,4}=f_{0}\pm
2\left|\left|f_{2}\mathrm{cos}\left(\frac{\mathbf{k}\cdot\mathbf{b}}{2}\right)\right|\pm\left|c_{2}\mathrm{sin}\left(\frac{\mathbf{k}\cdot\mathbf{b}}{2}\right)\right|\right|,$
(6)

which gives $\mathbf{k}\cdot\mathbf{b}=0$ (unmovable Dirac points) and
$\mathbf{k}\cdot\mathbf{b}=\pm 2\mathrm{arctg}(f_{2}/c_{2})$, as positions of
movable Dirac points from touching of two inner, doubly degenerate bands.

To investigate dispersions near touching points closer, we write
$\mathbf{k}=\mathbf{k}_{0}+\mathbf{q}$ and expand (4) for small
$|\mathbf{q}|$. Dispersions become:

$E_{1,2,3,4}(\mathbf{q})\approx f_{0}\pm
2|f_{2}|\pm\sqrt{f_{1}^{2}(\mathbf{q}\cdot\mathbf{a})^{2}+c_{2}^{2}(\mathbf{q}\cdot\mathbf{b})^{2}},$
(7)

near unmovable Dirac points, _i.e._ :

$E_{3,2}(\mathbf{q})\approx
f_{0}\pm\sqrt{c_{1}^{2}(\mathbf{q}\cdot\mathbf{a})^{2}+(c_{2}^{2}+f_{2}^{2})(\mathbf{q}\cdot\mathbf{b})^{2}},$
(8)

near movable Dirac points. The absence of other contacts between bands across
the reciprocal space is illustrated in Figure 1, which is in accordance with
the non-crossing rule. It also follows from Figure 1 that all four, doubly
degenerate bands are tangled together so that an insulator with such a band
structure must have total number of electrons per primitive cell divisible by
eight (unless it is strongly correlated). This is in accordance with filling
factor for layer group $45^{D}$ [28], _i.e._ it’s corresponding space group
[29, 30]. The same filling factor is reported for layer group $43^{D}$ [28,
29, 30].

##  IV Discussion and conclusions

We discuss our results in relations to the existing literature and in a
broader context of this research area. The positions of movable nodal points
and lines published for 3D hexagonal [31], orthorhombic [32] and tetragonal
[33] space groups could be used for layer groups too, via corresponding space
groups. Movable band contacts for groups $43^{D}$ and $45^{D}$ found here are
reported for their 3D analogs $54^{D}$ and $57^{D}$ [32]. When the third
dimension to _k_ -space is added, the band contacts remain point-like for
$54^{D}$, but become part of a movable nodal line for $57^{D}$ [32].

Using tight-binding model, authors of [17] classify band touchings in non-
magnetic materials into four possible cases. All four cases are obtained by
breaking symmetry elements in layer group $64^{D}$ [17]. Groups $43^{D}$ and
$45^{D}$ arise by further breaking symmetry of case I (two symmetry equivalent
Dirac points), from [17]. Group-subgroup chain is $43^{D}<48^{D}<64^{D}$ and
$45^{D}<48^{D}<64^{D}$, so these groups are not maximal subgroups of $64^{D}$
[34, 35]. This case is not included into classification of [17]. The same
holds for centrosymmetric, non-symmorphic groups $40^{D}$, $44^{D}$ and
$63^{D}$, hosting Dirac lines instead of cones.

For experimental realization of materials belonging to layer groups given in
advance, one can search database of 2D materials [36, 37] and layered 3D
materials which were synthesized in the past [38]. Material
$\mathrm{KAsO_{2}}$ belongs to layer group $45$, with synthesis of it’s 3D
layered analog described before [39]. The 2D version is non-magnetic insulator
with a band gap of around $4$eV [36]. Further investigations would be
necessary to show if it would be possible to shift it’s Fermi level by _e.g._
doping. On the other hand, band connectivity of groups $43^{D}$ and $45^{D}$
(and their common subgroup $33^{D}$), which is the highest among all layer
groups, forbids their realization by small deformations of a material
belonging to any of their supergroups. Deformations, however small they may
be, are supposed to close a finite gap at some BZ point, which we think is
unlikely.

Groups $40^{D}$, $43^{D}$ and $45^{D}$ are reported [40] to host semi-Dirac
fermions (SDF), which disperse linearly in one direction in _k_ -space and
quadratically in the orthogonal direction. Indeed, tight binding dispersions
(4) become $E_{1,2,3,4}\approx
h_{\pm}+h_{1}^{\pm}(\mathbf{q}\cdot\mathbf{a})^{2}\pm
h_{2}|(\mathbf{q}\cdot\mathbf{b})|$, with $h_{\pm}=f_{0}\pm
2\sqrt{c_{1}^{2}+c_{2}^{2}+f_{1}^{2}}$,
$h_{1}^{\pm}=\mp(c_{1}^{2}+f_{1}^{2})/(4\sqrt{c_{1}^{2}+c_{2}^{2}+f_{1}^{2}})$,
$h_{2}=|f_{2}|\sqrt{c_{2}^{2}+f_{1}^{2}}/\sqrt{c_{1}^{2}+c_{2}^{2}+f_{1}^{2}}$
(near points $(0,\pm\pi/b)$), _i.e._ $h_{\pm}=f_{0}\pm 2|c_{2}|$,
$h_{1}^{\pm}=\pm(c_{1}^{2}+f_{1}^{2})/(4|c_{2}|)$, $h_{2}=|f_{2}|$ (near
points $(\pm\pi/a,\pm\pi/b)$); only upper (only lower) signs are combined in
$h_{\pm}$, $h_{1}^{\pm}$. However, list of groups and BZ points hosting SDF in
[40] is incomplete. As shown in [13], SDFs appear also at the midpoints of BZ
borders of groups $44^{D}$ and $63^{D}$ and at the BZ corners of group
$43^{D}$. Also, the symmetry adapted low energy Hamiltonian derived in [40],
gives point-like, instead of line-like degeneracies required by symmetry. The
term SDF is used for line-nodes extrema (like found in [41]), which differs
from semi-Dirac dispersion around point-like degeneracy as introduced in [42,
43].

When SOC is neglected, the hoping parameters between states with opposite
spins vanish, while those with the parallel spins slightly change. The
dispersions (4) become $\widetilde{E}_{1,2,3,4}=\widetilde{f}_{0}\pm
2\left||\widetilde{f}_{1}\mathrm{cos}(\mathbf{k}\cdot\mathbf{a}/2)|\pm|\widetilde{f}_{2}\mathrm{cos}(\mathbf{k}\cdot\mathbf{b}/2)|\right|$,
which give fortune teller states (FT) near BZ corners
$\widetilde{E}_{1,2,3,4}=\widetilde{f}_{0}\pm\left||\widetilde{f}_{1}(\mathbf{q}\cdot\mathbf{a})|\pm|\widetilde{f}_{2}(\mathbf{q}\cdot\mathbf{b})|\right|$,
as predicted before for layer (single) groups $33$, $43$ and $45$ [44]. Non-
zero density of states (DOS) of
$2/\left(\pi\mathrm{max}\left\\{b|\widetilde{f}_{1}|,a|\widetilde{f}_{2}|\right\\}\right)$
near bands contact, distinguish FT dispersion from other linear dispersions.
The formula for DOS presented here does not include doubly degeneracy of bands
and corrects inessential numerical error in [44]. Eight-fold spinfull
degeneracy for electrons (_i.e._ four-fold degeneracy for _e.g._ phonons) at
BZ corners, together with FT dispersion, is guaranteed by mere belonging of a
2D material to one of these three groups [44]. Later it was pointed out that
in some layer single groups, four-fold degeneracy (eight-fold, for electrons
with spin) might appear also on some high-symmetry lines [45, 46] by truly
accidental band contacts (TABC). Although being an interesting idea, such TABC
can be destroyed by symmetry preserving perturbations and are assumed to
appear rarely in real materials in [44]. In other words, even if present by
chance, TABC could be gaped by change of temperature, pressure, humidity _etc_
, which could cause a potential device designed by use of TABC to malfunction.
The absence of TABC on BZ edges in our tight-binding model without SOC, in _ab
initio_ band structure of a silicone monolayer in [44] and measured by ARPES
[47], are another confirmations of our statements. Note that part of Table I
of [48] (apart from materials mentioned in it) that deals with Dirac phonons
at HSPs, repeats group-theoretical results published five years before in
Table I of [44] for unmovable, four-fold (spinless) degenerate band contacts.
The other part (Dirac phonons on HSLs [48]), contains seven groups that might
host TABC, six of which being reported and one originally omitted in [45, 46].

Some errors found in the literature could have been avoided, had the authors
red (and consequently, cited) previous publications on the same or similar
topic. Reference [49] study phonons in $\mathrm{PtI_{4}}$ and
$\mathrm{LiBiO_{2}}$ monolayers belonging to layer groups $33$ and $45$,
respectively. The $\mathbf{k}\cdot\mathbf{p}$ Hamiltonian derived in [49]
around the BZ corner of group $45$, does not reduce to zero at BZ corner and
has four real parameters, instead of three required by symmetry [44]. The
number of real independent parameters in a low-energy Hamiltonian derived from
symmetry is invariant, unlike it’s form which depends on the basis, and could
be used as a crosscheck. Group theory was used for finding which gray layer
groups host Dirac cones both without and with SOC [50]. Group $73$ is missing
in results of [50], as can be seen by comparing cases with and without SOC in
[13]. Gray layer groups without SOC hosting Dirac cones listed much earlier in
[51, 52], might be a useful starting point of analysis performed in [50]. Here
we add that eleven groups being main group-theoretical result summarized in
Table I of [53], are the exact eleven groups published seven years before in
[51, 52]. Group theoretical treatment of Dirac points of electrons without SOC
(treated in [51, 52]) and linear Weyl points of phonons (treated in [53]) is
identical. Similarly, the group-theoretical results of [54], reporting
electronic dispersions near four-fold degeneracies in non-centrosymmetric
materials with SOC, are repeated in [55]. The $\mathbf{k}\cdot\mathbf{p}$
Hamiltonian near $\overline{M}$ point of wallpaper group $\mathrm{p4g}$ (which
is also layer group $56$) has two real parameters and lead to doubly-
degenerate bands as if the group was centrosymmetric [56]. This is not in
accordance with earlier publication [54], where the Hamiltonian near BZ
corners of layer group $56$ has three parameters and gives doubly degeneracy
only along HSLs, as required by symmetry. These examples show that it is not
good to limit attention to a group of authors only (_e.g._ from one
university, country etc.), instead to a topic of research itself. Also,
repetition of previous results of other authors without due citation, destroys
the spirit of science itself.

Finally, we mention that our group theoretical treatment of dispersions holds
for fixed nuclei and should not be transferred directly to dynamical
Hamiltonians, such as the electron-phonon Hamiltonian relevant for explanation
of conventional superconductivity. For dynamical problems, symmetry analysis
of phonons (like the one for graphene [57]), could be useful. Also, a single
Dirac cone at HSP as the only quasiparticle at the Fermi level, appears in
some black-and-white layer groups describing antiferromagnetic ordering [58],
where time reversal alone is not a symmetry.

###  IV.1 Acknowledgments

Author acknowledges funding by the Ministry of Science, Technological
Development and Innovation of the Republic of Serbia provided by the Institute
of Physics Belgrade.

## References

  * Feng  _et al._ [2021] X. Feng, J. Zhu, W. Wu, and S. A. Yang, Two-dimensional topological semimetals, Chinese Physics B 30, 107304 (2021).
  * Armitage  _et al._ [2018] N. P. Armitage, E. J. Mele, and A. Vishwanath, Weyl and $\mathrm{Dirac}$ semimetals in three-dimensional solids, Rev. Mod. Phys. 90, 015001 (2018).
  * Mañes [2012] J. L. Mañes, Existence of bulk chiral fermions and crystal symmetry, Phys. Rev. B 85, 155118 (2012).
  * Tang and Wan [2021] F. Tang and X. Wan, Exhaustive construction of effective models in 1651 magnetic space groups, Phys. Rev. B 104, 085137 (2021).
  * Yu  _et al._ [2022] Z.-M. Yu, Z. Zhang, G.-B. Liu, W. Wu, X.-P. Li, R.-W. Zhang, S. A. Yang, and Y. Yao, Encyclopedia of emergent particles in three-dimensional crystals, Science Bulletin 67, 375 (2022).
  * Liu  _et al._ [2022] G.-B. Liu, Z. Zhang, Z.-M. Yu, S. A. Yang, and Y. Yao, Systematic investigation of emergent particles in type-$\mathrm{III}$ magnetic space groups, Phys. Rev. B 105, 085117 (2022).
  * Zhang  _et al._ [2022] Z. Zhang, G.-B. Liu, Z.-M. Yu, S. A. Yang, and Y. Yao, Encyclopedia of emergent particles in type-$\mathrm{IV}$ magnetic space groups, Phys. Rev. B 105, 104426 (2022).
  * Damnjanović and Milošević [2015] M. Damnjanović and I. Milošević, Full symmetry implementation in condensed matter and molecular physics—modified group projector technique, Physics Reports 581, 1 (2015).
  * Lazić  _et al._ [2013] N. Lazić, M. Milivojević, and M. Damnjanović, Spin line groups, Acta Crystallographica Section A 69, 611 (2013), https://onlinelibrary.wiley.com/doi/pdf/10.1107/S0108767313022642 .
  * Lazić and Damnjanović [2014] N. Lazić and M. Damnjanović, Spin ordering in $\mathrm{RKKY}$ nanowires: Controllable phases in ${}^{13}\mathrm{C}$ nanotubes, Phys. Rev. B 90, 195447 (2014).
  * Lazić [2016] N. Lazić,  _QUASI-CLASSICAL GROUND STATES AND MAGNONS IN MONOPERIODIC SPIN SYSTEMS_ , Ph.D. thesis, Faculty of Physics, University of Belgrade (2016).
  * Nikolić  _et al._ [2022] B. Nikolić, I. Milošević, T. Vuković, N. Lazić, S. Dmitrović, Z. Popović, and M. Damnjanović, Irreducible and site-symmetry-induced representations of single/double ordinary/grey layer groups, Acta Crystallographica Section A 78, 107 (2022).
  * Damljanović and Lazić [2023] V. Damljanović and N. Lazić, Electronic structures near unmovable nodal points and lines in two-dimensional materials, Journal of Physics A: Mathematical and Theoretical 56, 215201 (2023).
  * Kowalczyk  _et al._ [2020] P. J. Kowalczyk, S. A. Brown, T. Maerkl, Q. Lu, C.-K. Chiu, Y. Liu, S. A. Yang, X. Wang, I. Zasada, F. Genuzio, T. O. Menteş, A. Locatelli, T.-C. Chiang, and G. Bian, Realization of symmetry-enforced two-dimensional $\mathrm{Dirac}$ fermions in nonsymmorphic $\alpha$-$\mathrm{B}$ismuthene, ACS Nano 14, 1888 (2020), pMID: 31971774, https://doi.org/10.1021/acsnano.9b08136 .
  * Liu  _et al._ [2019] Z. Liu, P. Wang, Q. Cui, G. Yang, S. Jin, and K. Xiong, Theoretical prediction of $\mathrm{HfB}_{2}$ monolayer, a two-dimensional $\mathrm{Dirac}$ cone material with remarkable $\mathrm{Fermi}$ velocity, RSC Adv. 9, 2740 (2019).
  * Zhang  _et al._ [2023] Z. Zhang, W. Wu, G.-B. Liu, Z.-M. Yu, S. A. Yang, and Y. Yao, Encyclopedia of emergent particles in 528 magnetic layer groups and 394 magnetic rod groups, Phys. Rev. B 107, 075405 (2023).
  * Young and Kane [2015] S. M. Young and C. L. Kane, Dirac semimetals in two dimensions, Phys. Rev. Lett. 115, 126803 (2015).
  * Wieder  _et al._ [2018] B. J. Wieder, B. Bradlyn, Z. Wang, J. Cano, Y. Kim, H.-S. D. Kim, A. M. Rappe, C. L. Kane, and B. A. Bernevig, Wallpaper fermions and the nonsymmorphic $\mathrm{Dirac}$ insulator, Science 361, 246 (2018), https://science.sciencemag.org/content/361/6399/246.full.pdf .
  * Landau and Lifshitz [1981] L. D. Landau and E. M. Lifshitz,  _Quantum Mechanics_ (Butterworth-Heinemann, Oxford, 1981).
  * Neumann and Wigner [1929] J. v. Neumann and E. Wigner, $\mathrm{U}$eber das $\mathrm{V}$erhalten von $\mathrm{E}$igenwerten bei adiabatischen $\mathrm{P}$rozessen, Physikalische Zeitschrift 30, 467 (1929).
  * Neumann and Wigner [2000] J. v. Neumann and E. Wigner, On the behaviour of eigenvalues in adiabatic processes, in  _Quantum Chemistry: Classic Scientific Papers_ , edited by H. Hettema (World Scientific, Singapore, 2000) pp. 25–31.
  * Berestetskii  _et al._ [1982] V. B. Berestetskii, E. M. Lifshitz, and L. P. Pitaevskii,  _Quantum Electrodynamics_ (Butterworth-Heinemann, Oxford, 1982).
  * Cornwell [1984] J. F. Cornwell,  _Group Theory in Physics Volume 1_ (Academic Press, London, 1984).
  * Elcoro  _et al._ [2017] L. Elcoro, B. Bradlyn, Z. Wang, M. G. Vergniory, J. Cano, C. Felser, B. A. Bernevig, D. Orobengoa, G. de la Flor, and M. I. Aroyo, Double crystallographic groups and their representations on the Bilbao Crystallographic Server, Journal of Applied Crystallography 50, 1457 (2017).
  * Kopsky and Litvin [2002] V. Kopsky and D. B. Litvin,  _International Tables of Crystallography Volume E: Subperiodic Groups_ (Kluwer Academic Publishers, Dordrecht, 2002).
  * Hahn [2005] T. Hahn,  _International Tables of Crystallography Volume A: Space-Group Symmetry_ (Springer, Dordrecht, 2005).
  * Momma and Izumi [2011] K. Momma and F. Izumi, VESTA3 for three-dimensional visualization of crystal, volumetric and morphology data, Journal of Applied Crystallography 44, 1272 (2011).
  * Wieder and Kane [2016] B. J. Wieder and C. L. Kane, Spin-orbit semimetals in the layer groups, Phys. Rev. B 94, 155108 (2016).
  * Watanabe  _et al._ [2016] H. Watanabe, H. C. Po, M. P. Zaletel, and A. Vishwanath, Filling-enforced gaplessness in band structures of the 230 space groups, Phys. Rev. Lett. 117, 096404 (2016).
  * Watanabe  _et al._ [2015] H. Watanabe, H. C. Po, A. Vishwanath, and M. Zaletel, Filling constraints for spin-orbit coupled insulators in symmorphic and nonsymmorphic crystals, Proceedings of the National Academy of Sciences 112, 14551 (2015), https://www.pnas.org/doi/pdf/10.1073/pnas.1514665112 .
  * Zhang  _et al._ [2018] J. Zhang, Y.-H. Chan, C.-K. Chiu, M. G. Vergniory, L. M. Schoop, and A. P. Schnyder, Topological band crossings in hexagonal materials, Phys. Rev. Materials 2, 074201 (2018).
  * Leonhardt  _et al._ [2021] A. Leonhardt, M. M. Hirschmann, N. Heinsdorf, X. Wu, D. H. Fabini, and A. P. Schnyder, Symmetry-enforced topological band crossings in orthorhombic crystals: Classification and materials discovery, Phys. Rev. Materials 5, 124202 (2021).
  * Hirschmann  _et al._ [2021] M. M. Hirschmann, A. Leonhardt, B. Kilic, D. H. Fabini, and A. P. Schnyder, Symmetry-enforced band crossings in tetragonal materials: Dirac and $\mathrm{Weyl}$ degeneracies on points, lines, and planes, Phys. Rev. Materials 5, 054202 (2021).
  * Ivantchev  _et al._ [2000] S. Ivantchev, E. Kroumova, G. Madariaga, J. M. Pérez-Mato, and M. I. Aroyo, SUBGROUPGRAPH: a computer program for analysis of group–subgroup relations between space groups, Journal of Applied Crystallography 33, 1190 (2000).
  * de la Flor  _et al._ [2021] G. de la Flor, B. Souvignier, G. Madariaga, and M. I. Aroyo, Layer groups: Brillouin-zone and crystallographic databases on the Bilbao Crystallographic Server, Acta Crystallographica Section A 77, 559 (2021).
  * Haastrup  _et al._ [2018] S. Haastrup, M. Strange, M. Pandey, T. Deilmann, P. S. Schmidt, N. F. Hinsche, M. N. Gjerding, D. Torelli, P. M. Larsen, A. C. Riis-Jensen, J. Gath, K. W. Jacobsen, J. J. Mortensen, T. Olsen, and K. S. Thygesen, The computational 2$\mathrm{D}$ materials database: high-throughput modeling and discovery of atomically thin crystals, 2D Materials 5, 042002 (2018).
  * Gjerding  _et al._ [2021] M. N. Gjerding, A. Taghizadeh, A. Rasmussen, S. Ali, F. Bertoldo, T. Deilmann, N. R. Knøsgaard, M. Kruse, A. H. Larsen, S. Manti, T. G. Pedersen, U. Petralanda, T. Skovhus, M. K. Svendsen, J. J. Mortensen, T. Olsen, and K. S. Thygesen, Recent progress of the computational 2$\mathrm{D}$ materials database ($\mathrm{C2DB}$), 2D Materials 8, 044002 (2021).
  * Mounet  _et al._ [2018] N. Mounet, M. Gibertini, P. Schwaller, D. Campi, A. Merkys, A. Marrazzo, T. Sohier, I. E. Castelli, A. Cepellotti, G. Pizzi, and N. Marzari, Two-dimensional materials from high-throughput computational exfoliation of experimentally known compounds, Nature Nanotechnology 13, 246 (2018).
  * Emmerling and Röhr [2003] F. Emmerling and C. Röhr, Die neuen $\mathrm{O}$xoarsenate($\mathrm{III}$) $\mathrm{AAsO_{2}}$ ($\mathrm{A=Na,K,Rb}$) und $\mathrm{Cs_{3}As_{5}O_{9}}$. $\mathrm{D}$arstellung, $\mathrm{K}$ristallstrukturen und $\mathrm{R}$aman-$\mathrm{S}$pektren / $\mathrm{T}$he $\mathrm{N}$ew $\mathrm{O}$xoarsenates($\mathrm{III}$) $\mathrm{AAsO_{2}}$ ($\mathrm{A=Na,K,Rb}$) and $\mathrm{Cs_{3}As_{5}O_{9}}$. $\mathrm{S}$ynthesis, $\mathrm{C}$rystal $\mathrm{S}$tructures and $\mathrm{R}$aman $\mathrm{S}$pectra, Zeitschrift für Naturforschung B 58, 620 (2003).
  * Meng  _et al._ [2023] W. Meng, Y. Liu, X. Zhang, Z. He, W.-W. Yu, H. Zhang, L. Tian, and G. Liu, Nonsymmorphic symmetry protected spin-orbit semi-$\mathrm{D}$irac fermions in two dimensions, Phys. Rev. B 107, 115167 (2023).
  * Damljanović and Gajić [2017] V. Damljanović and R. Gajić, Existence of $\mathrm{semi-Dirac}$ cones and symmetry of two-dimensional materials, Journal of Physics: Condensed Matter 29, 185503 (2017).
  * Pardo and Pickett [2009] V. Pardo and W. E. Pickett, Half-metallic semi-$\mathrm{D}$irac-point generated by quantum confinement in $\mathrm{TiO_{2}}$/$\mathrm{VO_{2}}$ nanostructures, Phys. Rev. Lett. 102, 166803 (2009).
  * Banerjee  _et al._ [2009] S. Banerjee, R. R. P. Singh, V. Pardo, and W. E. Pickett, Tight-binding modeling and low-energy behavior of the semi-$\mathrm{D}$irac point, Phys. Rev. Lett. 103, 016402 (2009).
  * Damljanović  _et al._ [2017] V. Damljanović, I. Popov, and R. Gajić, Fortune teller fermions in two-dimensional materials, Nanoscale 9, 19337 (2017).
  * Guo  _et al._ [2021] P.-J. Guo, Y.-W. Wei, K. Liu, Z.-X. Liu, and Z.-Y. Lu, Eightfold degenerate fermions in two dimensions, Phys. Rev. Lett. 127, 176401 (2021).
  * Guo  _et al._ [2022] P.-J. Guo, Y.-W. Wei, K. Liu, Z.-X. Liu, and Z.-Y. Lu, Erratum: Eightfold degenerate fermions in two dimensions [$\mathrm{Phys.Rev.Lett.}$ 127, 176401 (2021)], Phys. Rev. Lett. 129, 049901(E) (2022).
  * Kopciuszyński  _et al._ [2020] M. Kopciuszyński, M. Krawiec, L. Żurawek, and R. Zdyb, Experimental evidence of a new class of massless fermions, Nanoscale Horiz. 5, 679 (2020).
  * Gong  _et al._ [2022] J. Gong, J. Wang, H. Yuan, Z. Zhang, W. Wang, and X. Wang, Dirac phonons in two-dimensional materials, Phys. Rev. B 106, 214317 (2022).
  * Wang  _et al._ [2023] C. Wang, W.-W. Yu, Y. Liu, X. Zhang, L. Jin, C. Liu, and G. Liu, Two-dimensional $\mathrm{D}$irac phonons without/with inversion symmetry, Journal of Physics: Condensed Matter 35, 425702 (2023).
  * Luo  _et al._ [2020] W. Luo, J. Ji, J. Lu, X. Zhang, and H. Xiang, Two-dimensional topological semimetals protected by symmorphic symmetries, Phys. Rev. B 101, 195111 (2020).
  * Damljanović and Gajić [2016a] V. Damljanović and R. Gajić, Existence of $\mathrm{Dirac}$ cones in the $\mathrm{Brillouin}$ zone of diperiodic atomic crystals according to group theory, Journal of Physics: Condensed Matter 28, 085502 (2016a).
  * Damljanović and Gajić [2016b] V. Damljanović and R. Gajić, Addendum to ‘$\mathrm{Existence}$ of $\mathrm{Dirac}$ cones in the $\mathrm{Brillouin}$ zone of diperiodic atomic crystals according to group theory’, Journal of Physics: Condensed Matter 28, 439401 (2016b).
  * Zhong  _et al._ [2023] M. Zhong, H. Liu, J. Wang, C. Xie, H. Yuan, Z. Zhang, G. Ding, X. Wang, and G. Zhang, Complete list of valley linear $\mathrm{W}$eyl point phonons in two dimensions, Phys. Rev. B 107, 205406 (2023).
  * Damljanović  _et al._ [2020] V. Damljanović, N. Lazić, A. Šolajić, J. Pešić, B. Nikolić, and M. Damnjanović, Peculiar symmetry-protected electronic dispersions in two-dimensional materials, Journal of Physics: Condensed Matter 32, 485501 (2020).
  * Meng  _et al._ [2022] W. Meng, Y. Liu, W.-W. Yu, X. Zhang, and G. Liu, Spin-orbital robust $\mathrm{D}$irac points in two-dimensional systems, Materials Today Physics 27, 100774 (2022).
  * Mao  _et al._ [2022] N. Mao, H. Wang, Y. Dai, B. Huang, and C. Niu, Third-order topological insulators with wallpaper fermions in $\mathrm{Tl_{4}PbTe_{3}}$ and $\mathrm{Tl_{4}SnTe_{3}}$, npj Computational Materials 8, 154 (2022).
  * Dresselhaus  _et al._ [2007] M. S. Dresselhaus, G. Dresselhaus, and A. Jorio,  _Group Theory_ (Springer, Berlin, 2007).
  * Young and Wieder [2017] S. M. Young and B. J. Wieder, Filling-enforced magnetic $\mathrm{D}$irac semimetals in two dimensions, Phys. Rev. Lett. 118, 186401 (2017).


# Generalized effective completeness for continuous logic

Caleb Camrud  Department of Mathematics
Iowa State University

Carver Hall
411 Morrill Rd.
Ames, IA 50014
USA<EMAIL_ADDRESS>https://cmhcamrud.org

###### Abstract.

In this paper, we present a generalized effective completeness theorem for
continuous logic. The primary result is that any continuous theory is
satisfied in a structure which admits a presentation of the same Turing
degree. It then follows that any decidable theory is satisfied by a computably
presentable structure. This modifies and extends previous partial effective
completeness theorems for continuous logic given by Calvert and Didehvar,
Ghasemloo, and Pourmahdian.

##  1\. Introduction

Completeness results relate theories to structures. _Effective_ completeness
results relate _decidable_ theories to _computable_ structures. The first such
result was given by Millar in [9]. But the method provided in that manuscript
only applies to classical logic and classically computable structures, and
hence cannot be directly applied to continuous logic and uncountable
structures.

In [1], Ben Yaacov et al. developed a model theory for metric structures using
continuous first-order logic, and a completeness result was proven in [2].
Calvert then extended this result to an effective version of completeness,
relating decidable theories in continuous logic to probabilistically decidable
structures.

######  Theorem 1 (Theorem 4.5, [5]).

Let $T$ be a complete, decidable, continuous first-order theory. Then there is
a probablistically decidable, continuous weak structure $\mathfrak{M}$ such
that $\mathfrak{M}\vDash T$.

In the last decade, however, computable presentations rather than
probabilistic decidability have become standard for the study of effectivity
on metric structures (see, _e.g._ , [4] and [7]). We therefore sought to
answer the following question: “Is there an effective completeness theorem for
continuous logic and _computable presentations_?”

Didehvar, Ghasemloo, and Pourmahdian provided a partial answer to this
question in [6], implicitly with respect to computable presentations. The
result proven was a qualified effective completeness result for the first-
order rational Pavelka logic ($\mathbf{RPL}\forall$).

######  Theorem 2 (Theorem 3.5, [6]).

Every consistent, linear-complete, computably axiomatizable Henkin theory in
$\mathbf{RPL}\forall$ has a decidable model.

Notably, the continuous logic of [1] is a fragment of $\mathbf{RPL}\forall$,
so the above theorem applies to continuous logic, as well.

Our primary result can be considered as a generalization and strengthening of
the above theorem: there is an effective procedure which, given a name of a
continuous theory, produces a presentation of a metric structure which models
that theory. It follows that the presentation is Turing reducible to the given
name. Hence if the theory is decidable, the presentation is computable.

The result has four major upshots in comparison to the previous effective
completeness results.

  1. (i)

The given (name of a) continuous theory does not need to be either _complete_
or _linear-complete_. Through the process described in Lemma 4, any continuous
theory may be effectively extended to a complete theory (though, as a _caveat_
, this extension is not unique).

  2. (ii)

The given (name of a) continuous theory need not be _decidable_. The
generalized effective completeness theorem applies to any name of a continuous
theory, and produces a presentation which is Turing reducible to that name.

  3. (iii)

The generalized effective completeness theorem relates continuous theories to
_presentations_ of metric structures, which have become the default for the
study of effectivity on metric structures, rather than _probabilistic
decidability_.

  4. (iv)

The generalized effective completeness theorem relates continuous theories to
presentations of genuine metric _structures_ , rather than _weak structures_ ,
so the assumption of a countable universe may be dropped.

This paper is organized as follows. In Section 2, we introduce continuous
logic, metric structures, and computable presentations. Section 3 recalls
previous results in the model theory of metric structures. These results are
then extended to important preliminary model-theoretic propositions in Section
4.1. Section 4.2 follows to include our primary lemma, allowing us to
uniformly effectively extend theories to complete theories. We then prove our
main theorem, a generalized version of effective completeness, in Section 4.3.
Standard effective completeness then follows from this as a corollary.

##  2\. Background

###  2.1. Continuous logic

The _logical symbols_ of continuous logic consist of the following.

  * •

$($ and $)$ are the _parentheses_.

  * •

$x,y,z,...$ are the _variable symbols_ ($\mathcal{V}$).

  * •

$\neg$, $\frac{1}{2}$, and $\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$ are the _connectives_.

  * •

$\sup$ and $\inf$ are the _quantifiers_.

######  Remark 1.

In some versions of continuous logic, the set of connectives contains a
distinguished symbol $\underline{u}$ for each continuous map
$u:[0,1]^{\eta(u)}\to[0,1]$. The resulting set of well-formed formulas for
such a logic is, however, uncountable and thus fails to perform effectively.
Our choice of $\neg$, $\frac{1}{2}$, and $\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}$ as the connectives was made for four reasons.

  1. (1)

$\neg$ plays precisely the role of classical negation ($\neg$) and
$\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ of reverse
implication ($\leftarrow$). The interpretation of the $\frac{1}{2}$ operator
is similarly intuitive, as will be shown in the following subsection.

  2. (2)

In [3], it was shown that after interpretation, $\neg$, $\frac{1}{2}$, and
$\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ are dense in
the set of all continuous maps on $[0,1]$. Thus finitary well-formed formulas
in these connectives can approximate those in the wider set of connectives
arbitrarily well. Such an approximation is, moreover, sufficient for
completeness (as seen in [2]).

  3. (3)

When a signature is effectively numbered, the sentences and well-formed
formulas of that signature may be effectively enumerated.

  4. (4)

Because of 1, 2, and 3, $\neg$, $\frac{1}{2}$, and
$\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}$ have become a
somewhat canonical set of connectives for continuous logic.

A _signature_ is a quintuple
$L=\big{(}\mathcal{P},\mathcal{F},\mathcal{C},\Delta,\eta\big{)}$ such that
each of the following hold.

  * •

$\mathcal{P}$, $\mathcal{F}$, and $\mathcal{C}$ are mutually disjoint, and
contain no logical symbols.

  * •

$\Delta:\mathcal{P}\cup\mathcal{F}\to\mathbb{N}^{\mathbb{N}}$.

  * •

$\eta:\mathcal{P}\cup\mathcal{F}\to\mathbb{N}\setminus\\{0\\}$.

  * •

There is some $\underline{d}\in\mathcal{P}$ such that
$\Delta(\underline{d})=\mathrm{id}_{\mathbb{N}}$ and $\eta(\underline{d})=2$.

$\mathcal{P}$ is the set of _predicate symbols_ , $\mathcal{F}$ the set of
_function symbols_ , and $\mathcal{C}$ the set of _constant symbols_. $\Delta$
is the _modulus map_ and $\eta$ the _arity map_. Each predicate (or function)
symbol $F$ is an _$\eta(F)$ -ary_ predicate (or function) symbol.

For the remainder of this chapter, unless stated otherwise, we will assume we
have a fixed signature $L$. The construction of _terms_ and _well-formed
formulas_ (wffs) is straightforward. As are the definitions of _free
variables_ and _sentences_. Explicit definitions can be found in [1]. A
_theory_ is a set of sentences. Note, now, that the following syntax maps will
be used as shorthand.

Shorthand | String
---|---
$\varphi\vee\psi$ | $\neg\big{(}(\neg\varphi)\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi\big{)}$
$\varphi\wedge\psi$ | $\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}(\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi)$
$\varphi\leftrightarrow\psi$ | $(\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\vee(\psi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)$
$\vec{x}$ | $(x_{0},...,x_{n})$
$\sup_{x_{0},...,x_{n}}\varphi$ | $\sup_{x_{0}}\dots\sup_{x_{n}}\varphi$
$\inf_{x_{0},...,x_{n}}\varphi$ | $\inf_{x_{0}}\dots\inf_{x_{n}}\varphi$
$\underline{0}$ | $\sup_{x}\underline{d}(x,x)$
$\underline{1}$ | $\neg\ \underline{0}$
$\varphi\dotplus\psi$ | $\neg\big{(}(\underline{1}\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\big{)}$
$m\varphi$ | $\underbrace{\big{(}...(\varphi\dotplus\varphi)\dotplus\dots\dotplus\varphi\big{)}}_{\text{$m$-many}}$
$\underline{2^{-k}}$ | $\underbrace{\frac{1}{2}\dots\frac{1}{2}}_{\text{ $k$-many}}\ \underline{1}$
$\underline{\frac{\ell}{2^{k}}}$ | $\underbrace{\big{(}...(\underline{2^{-k}}\dotplus\underline{2^{-k}})\dotplus\dots\dotplus\underline{2^{-k}}\big{)}}_{\text{$\ell$-many}}$

Some of the above syntax may seem loaded; this is for good reason, as will be
noted in 2.2.

We present a simplified list of _axiom schemata_ for continuous logic, which
are more parsimonious for effective constructions. In each of the following,
$\varphi$, $\psi$, and $\theta$ range over arbitrary wffs. The first four
schemata correspond to the classical propositional axioms.

  1. I.

$(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi.$

  2. II.

$\big{(}(\theta\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\theta\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi).$

  3. III.

$\big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\big{(}\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\big{)}$

  4. IV.

$(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\neg\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\neg\varphi).$

The next four correspond to the classical first-order axiom schemata. For
every $x\in\mathcal{V}$ and term $t$,

  1. V.

$(\sup_{x}\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\sup_{x}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\sup_{x}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi).$

  2. VI.

$\varphi[t/x]\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\sup_{x}\varphi$, when this substitution is
correct.

  3. VII.

$\sup_{x}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi$, when $x$ is not free in $\varphi$.

  4. VIII.

$\inf_{x}\varphi\leftrightarrow\neg(\sup_{x}\neg\varphi)$.

These two define the $\frac{1}{2}$ connective.

  1. IX.

$\frac{1}{2}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\frac{1}{2}\varphi).$

  2. X.

$(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\frac{1}{2}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\frac{1}{2}\varphi.$

The following define the predicate symbol $\underline{d}$. For every
$x,y,z\in\mathcal{V}$,

  1. XI.

$\underline{d}(x,x).$

  2. XII.

$\underline{d}(x,y)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{d}(y,x).$

  3. XIII.

$\big{(}\underline{d}(x,z)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{d}(x,y)\big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{d}(y,z).$

The next schema defines interaction between $\underline{d}$ and function
symbols. For every $f\in\mathcal{F}$, $n\in\mathbb{N}$, (possibly empty)
tuples of terms $\vec{t_{0}},\vec{t_{1}}$, and $x,y\in\mathcal{V}$,

  1. XIV.

$\big{(}\underline{2^{-\Delta(f;n)}}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{d}(x,y)\big{)}\wedge\big{(}\underline{d}\big{(}f(\vec{t_{0}},x,\vec{t_{1}}),f(\vec{t_{0}},y,\vec{t_{1}})\big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-n}}\big{)}.$

Lastly, the following defines interaction between $\underline{d}$ and other
predicate symbols. For every $P\in\mathcal{P}$, $n\in\mathbb{N}$, (possibly
empty) tuples of terms $\vec{t_{0}},\vec{t_{1}}$, and $x,y\in\mathcal{V}$,

  1. XV.

$\big{(}\underline{2^{-\Delta(P;n)}}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{d}(x,y)\big{)}\wedge\big{(}\big{(}P(\vec{t_{0}},x,\vec{t_{1}})\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(\vec{t_{0}},y,\vec{t_{1}})\big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-n}}\big{)}.$

The _rules of inference_ of continuous logic are as follows, where $\varphi$
and $\psi$ are wffs and $x$ is a variable symbol.

  * •

_Modus ponens_

$\frac{\varphi,\ \psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi}{\psi}$

  * •

_Generalization_

$\frac{\varphi}{\sup_{x}\varphi}$

The set of _provable_ wffs, _consistency_ , _inconsistency_ , and
_consequences_ are each defined as in the classical setting. Again, we direct
the reader toward [1] for explicit definitions.

###  2.2. Metric structures

Nearly every structure in mathematical analysis extends either a psuedometric
or metric space. Continuous logic was developed with the purpose of describing
such structures. On this note, a signature must be able to speak about the
continuity of maps on such structures.

######  Definition 1.

Let $(|\mathfrak{M}|,d)$ and $(|\mathfrak{M}^{\prime}|,d^{\prime})$ be
pseudometric spaces of diameter $1$ and let
$f:|\mathfrak{M}|\to|\mathfrak{M}^{\prime}|$. A map
$\Delta(f):\mathbb{N}\to\mathbb{N}$ is called a _modulus of continuity_ for
$f$ if for every $a,b\in|\mathfrak{M}|$, $d(a,b)<2^{-\Delta(f;n)}$ implies
that $d^{\prime}\big{(}f(a),f(b)\big{)}\leq 2^{-n}$.

An _interpretation_ of $L$ is a map $\cdot^{\mathfrak{M}}$ with domain
$\mathcal{P}\cup\mathcal{F}\cup\mathcal{C}$ such that for some _universe_
$|\mathfrak{M}|$, each of the following hold.

  * •

For every predicate symbol $P$,
$P^{\mathfrak{M}}:|\mathfrak{M}|^{\eta(P)}\to[0,1]$.

  * •

For every function symbol $f$,
$f^{\mathfrak{M}}:|\mathfrak{M}|^{\eta(f)}\to|\mathfrak{M}|$.

  * •

For every constant symbol $c$, $c^{\mathfrak{M}}\in|\mathfrak{M}|$.

$\cdot^{\mathfrak{M}}$ is a _continuous interpretation_ if, moreover, each of
the following hold.

  * •

$\underline{d}^{\mathfrak{M}}:=d$ is a pseudometric.

  * •

For every predicate symbol $P$, $\Delta(P)$ is a modulus of continuity for
$P$.111Here the domain of $P^{\mathfrak{M}}$ is considered as the pseudometric
space
$\big{(}|\mathfrak{M}|^{\eta(P)},(\underline{d}^{\mathfrak{M}})^{\eta(P)}\big{)}$
and the range the metric space $\big{(}[0,1],|\cdot|\big{)}$.

  * •

For every function symbol $f$, $\Delta(f)$ is a modulus of continuity for $f$.

When $\cdot^{\mathfrak{M}}$ is an interpretation, the quintuple

$\mathfrak{M}=\big{(}|\mathfrak{M}|,d,\big{\\{}P^{\mathfrak{M}}:P\in\mathcal{P}\setminus\\{\underline{d}\\}\big{\\}},\big{\\{}f^{\mathfrak{M}}:f\in\mathcal{F}\big{\\}},\big{\\{}c^{\mathfrak{M}}:c\in\mathcal{C}\big{\\}}\big{)}$

is an _$L$ -pre-structure_. Moreover, if $\cdot^{\mathfrak{M}}$ is a
continuous interpretation, $\mathfrak{M}$ is a _continuous_ $L$-pre-structure.
Lastly, if $\cdot^{\mathfrak{M}}$ is a continuous interpretation and
$\big{(}|\mathfrak{M}|,d\big{)}$ is a complete metric space, then
$\mathfrak{M}$ is an _$L$ -structure_. If $|\mathfrak{M}|$ is countable,
$\mathfrak{M}$ is called _weak_.

When $\mathfrak{M}$ is an $L$-pre-structure, $\mathcal{P}^{\mathfrak{M}}$ is
the set of _predicates_ of $\mathfrak{M}$, $\mathcal{F}^{\mathfrak{M}}$ the
set of _functions_ of $\mathfrak{M}$, and $\mathcal{C}^{\mathfrak{M}}$ the set
of _distinguished points_ of $\mathfrak{M}$.

At times, the language of _non_ -continuous pre-structures is dropped, and
every pre-structure is assumed to be continuous. Also what were given here as
“$L$-structures” are often designated as “metric $L$-structures”. In this
manuscript, however, we will assume every structure is interpreting a
continuous signature, so we drop the prefix “metric”.

######  Example 1.

The following are examples of structures (for some related signature).

  * •

A complete metric space of diameter $1$ with no additional structure.

  * •

The natural numbers with the discrete metric and addition and multiplication
as binary functions.

  * •

The unit ball of a Banach space over $\mathbb{R}$ or $\mathbb{C}$, the norm as
the metric, as functions all binary maps of the form

$f_{\alpha,\beta}(x,y)=\alpha x+\beta y$

where $|\alpha|+|\beta|\leq 1$ are scalars, and the additive identity $0$ is a
distinguished point.

  * •

The unit ball of a $C^{*}$-algebra with the standard norm as the metric, and
multiplication and the $*$-map included as functions.

  * •

When $(\Omega,\mathcal{B},\mu)$ is a probability space, let $M$ be its measure
algebra and $d$ the measure of symmetric difference. Then $(M,d)$ along with
$\mu$ as a predicate, $\cap$, $\cup$, and $\cdot^{c}$ as functions, and $0$
and $1$ as distinguished points is a structure.

When $\mathfrak{M}$ is a structure, an _assignment_ (on $\mathfrak{M}$) is a
map $\sigma:\mathcal{V}\to|\mathfrak{M}|$. When $\sigma$ is an assignment,
$x\in\mathcal{V}$, and $a\in|\mathfrak{M}|$, the assignment $\sigma(x\mapsto
a)$ is defined as follows.

$\sigma(x\mapsto a;\ y):=\begin{cases}a&\text{ if }y=x,\\\ \sigma(y)&\text{
otherwise.}\end{cases}$

Given a term $t$, the _interpretation_ of $t$ in $\mathfrak{M}$ with $\sigma$
($t^{\mathfrak{M},\sigma}$) is defined recursively as follows.

  * •

If $t\in\mathcal{C}$, then $t^{\mathfrak{M},\sigma}:=t^{\mathfrak{M}}$.

  * •

If $t\in\mathcal{V}$, then $t^{\mathfrak{M},\sigma}:=\sigma(t)$.

  * •

If $t=f(t_{0},...,t_{n})$, then
$t^{\mathfrak{M},\sigma}:=f^{\mathfrak{M}}\big{(}t_{0}^{\mathfrak{M},\sigma},...,t_{n}^{\mathfrak{M},\sigma}\big{)}$.

For every $L$-pre-structure $\mathfrak{M}$, assignment $\sigma$, and wff
$\varphi$, the _value_ (or _truth value_) of $\varphi$ in $\mathfrak{M}$ with
$\sigma$ ($\varphi^{\mathfrak{M},\sigma}$) is defined recursively as follows.

  * •

$\big{(}P(t_{0},...,t_{n})\big{)}^{\mathfrak{M},\sigma}:=P^{\mathfrak{M}}\big{(}t_{0}^{\mathfrak{M},\sigma},...,t_{n}^{\mathfrak{M},\sigma}\big{)}$.

  * •

$(\neg\varphi)^{\mathfrak{M},\sigma}:=1-\varphi^{\mathfrak{M},\sigma}$.

  * •

$\big{(}\frac{1}{2}\varphi\big{)}^{\mathfrak{M},\sigma}:=\frac{1}{2}\cdot\varphi^{\mathfrak{M},\sigma}$.

  * •

$(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)^{\mathfrak{M},\sigma}:=\max\big{\\{}\varphi^{\mathfrak{M},\sigma}-\psi^{\mathfrak{M},\sigma},0\big{\\}}$.

  * •

$\big{(}\sup_{x}\varphi\big{)}^{\mathfrak{M},\sigma}:=\sup_{a\in|\mathfrak{M}|}\varphi^{\mathfrak{M},\sigma(x\mapsto
a)}$.

  * •

$\big{(}\inf_{x}\varphi\big{)}^{\mathfrak{M},\sigma}:=\inf_{a\in|\mathfrak{M}|}\varphi^{\mathfrak{M},\sigma(x\mapsto
a)}$.

When $\varphi^{\mathfrak{M},\sigma}=0$, $\mathfrak{M}$ with $\sigma$
_satisfies_ $\varphi$ ($\mathfrak{M},\sigma\vDash\varphi$). Also if $\varphi$
is a wff with free variables $\vec{x}$ and $\mathfrak{M}$ an $L$-structure,
$\varphi^{\mathfrak{M}}(\vec{a})$ means
$\varphi^{\mathfrak{M},\sigma(\vec{x}\mapsto\vec{a})}$ for any assignment
$\sigma$.

######  Remark 2.

Instead of beginning with a signature and discussing the structures over that
signature, one may begin with a structure and define the signature _of_ that
structure. This is done as in the classical case, though normally the set of
constants is assumed to be at most countable. Thus the interpretations of the
constants are _not_ the entire universe.

The following interpretations of shorthand sentences can be easily verified by
direct computation.

  1. (a)

$(\varphi\vee\psi)^{\mathfrak{M}}=\max\big{\\{}\varphi^{\mathfrak{M}},\psi^{\mathfrak{M}}\big{\\}}$.

  2. (b)

$(\varphi\wedge\psi)^{\mathfrak{M}}=\min\big{\\{}\varphi^{\mathfrak{M}},\psi^{\mathfrak{M}}\big{\\}}$.

  3. (c)

$(\varphi\leftrightarrow\psi)^{\mathfrak{M}}=\big{|}\varphi^{\mathfrak{M}}-\psi^{\mathfrak{M}}\big{|}$.

  4. (d)

$\underline{0}^{\mathfrak{M}}=0$.

  5. (e)

$\underline{1}^{\mathfrak{M}}=1$.

  6. (f)

$\varphi\dotplus\psi=\min\big{\\{}\varphi^{\mathfrak{M}}+\psi^{\mathfrak{M}},1\big{\\}}$.

  7. (g)

$m\varphi=\min\big{\\{}m\cdot\varphi^{\mathfrak{M}},1\big{\\}}$.

  8. (h)

$\big{(}\underline{\frac{\ell}{2^{k}}}\big{)}^{\mathfrak{M}}=\frac{\ell}{2^{k}}$.

Note that all of the above also hold for wffs when interpreted along with an
assignment.

It is also important to note when one structure embeds into another.

######  Definition 2.

Let $\mathfrak{M}$ and $\mathfrak{N}$ be continuous $L$-pre-structures.
$\iota:|\mathfrak{M}|\to|\mathfrak{N}|$ is an _$L$ -morphism_ if each of the
following hold.

  * •

For every $f\in\mathcal{F}$ and $a_{0},...,a_{\eta(f)-1}\in|\mathfrak{M}|$,

$\iota\big{(}f^{\mathfrak{M}}(a_{0},...,a_{\eta(f)-1})\big{)}=f^{\mathfrak{N}}\big{(}\iota(a_{0}),...,\iota(a_{\eta{f}-1})\big{)}.$

  * •

For every $P\in\mathcal{P}$ and $a_{0},...,a_{\eta(P)-1}\in|\mathfrak{M}|$,

$\iota\big{(}P^{\mathfrak{M}}(a_{0},...,a_{\eta(P)-1})\big{)}=P^{\mathfrak{N}}\big{(}\iota(a_{0}),...,\iota(a_{\eta{P}-1})\big{)}.$

$\iota$ is an _elementary_ $L$-morphism if, moreover, for every
$\mathfrak{M}$-assignment $\sigma$,
$\varphi^{\mathfrak{M},\sigma}=\varphi^{\mathfrak{N},\iota\circ\sigma}$.

###  2.3. Computable analysis and presentations

Computable analysis is summarized well in [10]. For our purposes, however, we
need only mention the definition of a computable real number.

######  Definition 3.

A real number $r$ is _computable_ if there is an effective procedure which,
given $k\in\mathbb{N}$, outputs a rational $q\in\mathbb{Q}$ such that

$|r-q|<2^{-k}.$

When $A$ is a countable set, a map $f:A\to\mathbb{R}$ is then _computable_ if
there is an effective procedure which, given $a\in A$ and $k\in\mathbb{N}$,
outputs a rational $q\in\mathbb{Q}$ such that

$|f(r)-q|<2^{-k}.$

Since metric structures often have uncountable domains, so a method for
discussing effectivity on such structures was introduced by [8], recently also
seen in [7]. An effectively numbered signature is necessary for this method.

######  Definition 4.

A signature $L$ is _effectively numbered_ if there is an effective mapping of
the natural numbers onto $\mathcal{P}\cup\mathcal{F}\cup\mathcal{C}$ and,
moreover, an effective procedure which, given the code of a predicate or
function symbol, outputs that symbol’s arity and an index of a Turing machine
which serves as a modulus of continuity for that symbol.

We now introduce computable presentations. From here we will assume we are
working under a fixed effectively numbered signature $L$.

######  Definition 5.

Given an $L$-structure $\mathfrak{M}$ and $A\subseteq|\mathfrak{M}|$, the
_algebra generated by_ $A$ is the smallest subset of $|\mathfrak{M}|$
containing $A$ that is closed under every function of $\mathfrak{M}$.

A pair $(\mathfrak{M},g)$ is called a _presentation_ of $\mathfrak{M}$ if
$g:\mathbb{N}\to|\mathfrak{M}|$ is a map such that the algebra generated by
$\mathrm{ran}(g)$ is dense. A presentation of $\mathfrak{M}$ is denoted
$\mathfrak{M}^{\sharp}$. Every point in $\mathrm{ran}(g)$ is called a
_distinguished point_ of the presentation, and each point in the algebra
generated by the distinguished points is called a _rational point_ of the
presentation ($\mathbb{Q}(\mathfrak{M}^{\sharp})$).

Notably, $\mathrm{ran}(g)$ need not be dense, but the _algebra_ it generates
does.

######  Definition 6.

A presentation $\mathfrak{M}^{\sharp}$ is _computable_ if the predicates of
$\mathfrak{M}$ are uniformly computable on the rational points of
$\mathfrak{M}^{\sharp}$.222Since the metric is a binary predicate on
$\mathfrak{M}$, this entails that the distance between any two rational points
is uniformly computable.

An _index_ of a computable presentation $\mathfrak{M}^{\sharp}$ is an index of
a Turing machine which, given a code of $P\in\mathcal{P}$, codes of
$a_{0},...,a_{\eta(P)-1}\in\mathbb{Q}(\mathfrak{M}^{\sharp})$, and
$k\in\mathbb{N}$, outputs a code of a rational $q$ such that

$\big{|}P^{\mathfrak{M}}(a_{0},...,a_{\eta(P)-1})-q\big{|}<2^{-k}.$

######  Example 2.

Let $\mathfrak{X}$ be the metric structure consisting of the unit ball of a
finite-dimensional Banach space over $\mathbb{R}$, its norm as the metric, as
functions all binary maps of the form

$f_{p,q}(x,y)=px+qy$

where $p,q\in\mathbb{Q}$ and $|p|+|q|\leq 1$, and $0$ as the only
distinguished point. Let $N$ be the dimension of $|\mathfrak{X}|$. Then define
$g:\mathbb{N}\to|\mathfrak{X}|$ as $g(n)=e_{n}$ for every $n\leq N-1$ and
$g(n)=e_{N-1}$ for every $n\geq N$. Clearly the algebra generated by
$\mathrm{ran}(g)$ is dense in $|\mathfrak{X}|$. Moreover, with a bit of
careful calculation, one may see that this presentation is computable.

##  3\. Previous completeness results

We now recall many results related to completeness which were proven in [2].
We have altered some of the notation in order to make these results more
applicable to our work, but the results proven remain the same. Important to
this work is the introduction of the formal notion of dyadic numerals.

######  Definition 7.

The _dyadic numerals_ ($\mathrm{Dyad}$) are all sentences of the form
$\underline{\frac{\ell}{2^{k}}}$ for $\ell,k\in\mathbb{N}$. When
$\underline{p}\in\mathrm{Dyad}$, by $p$ we mean the real number such that for
every $L$-pre-structure $\mathfrak{M}$, $\underline{p}^{\mathfrak{M}}=p$.

Maximal consistency is defined similarly to the classical case, but with an
extra condition concerning limiting behavior.

######  Definition 8.

A set of wffs $\Gamma$ is _maximally consistent_ if for every pair of wffs
$\varphi$ and $\psi$, the following hold.

  1. (i)

If $\Gamma\vdash\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-k}}$ for every $k\in\mathbb{N}$,
then $\varphi\in\Gamma$.

  2. (ii)

Either $\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi\in\Gamma$ or
$\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi\in\Gamma$.

Notably, without condition (i), we would not gain the intuitive property that
if $\Gamma$ is maximally consistent, then for every $\varphi\notin\Gamma$,
$\Gamma\cup\\{\varphi\\}$ is inconsistent. Ben Yaacov and Pedersen implement a
continuous version of a Henkin construction to prove their completeness
theorem. To accomplish this, Henkin witnesses must be added to the signature.

######  Definition 9.

Given a signature $L$, the _Henkin extended signature of $L$_ ($L^{+}$) is the
smallest signature that extends $L$ and that, for every combination of
$L^{+}$-wff $\varphi$, variable symbol $x$, and
$\underline{p},\underline{q}\in\mathrm{Dyad}$, contains a unique constant
symbol $c_{\varphi,x,\underline{p},\underline{q}}$.

When $\Gamma$ is a set of $L^{+}$-wffs, we say it is _Henkin complete_ if for
every $L^{+}$-wff $\varphi$, every variable symbol $x$, and every
$\underline{p},\underline{q}\in\mathrm{Dyad}$,

$\big{(}\sup_{x}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{q}\big{)}\wedge\big{(}\underline{p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi[c_{\varphi,x,\underline{p},\underline{q}}/x]\big{)}\in\Gamma.$

We now note a relevant lemma and theorem from Ben Yaacov and Pedersen.

######  Lemma 1 ((ii) of Lemma 8.5, [2]).

Let $T$ be an $L$-theory. Then for every pair of $L$-wffs $\varphi$ and
$\psi$, either $T\cup\\{\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi\\}$ or
$T\cup\\{\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi\\}$ is consistent.

######  Theorem 3 (From Theorem 8.10 and Proposition 9.2, [2]).

Let $T$ be an $L$-theory. Then there exists a maximally consistent, Henkin
complete set of $L^{+}$-wffs $\Gamma$ which extends $T$.

In what follows, the original Henkin model created will be a continuous
$L^{+}$-pre-structure. To make the move to a genuine $L^{+}$-structure, the
following theorem is needed.

######  Theorem 4 (Theorem 6.9, [2]).

Let $\mathfrak{M}^{\prime}$ be a continuous $L$-pre-structure. Then there is
an $L$-structure $\mathfrak{M}$ and an elementary $L$-morphism of
$\mathfrak{M}^{\prime}$ into $\mathfrak{M}$.

We now summarize the construction of the Henkin model in [2]. Completeness
follows.

######  Definition 10.

Let $\Gamma$ be a maximally consistent, Henkin complete set of $L^{+}$-wffs.
Define the _Henkin continuous $L^{+}$-pre-structure over $\Gamma$_
($\mathfrak{M}_{\Gamma}^{\prime}$) as follows.

  * •

$|\mathfrak{M}_{\Gamma}^{\prime}|$ is the set of all terms of $L^{+}$.

  * •

For every constant symbol $c$ of $L^{+}$,
$c^{\mathfrak{M}_{\Gamma}^{\prime}}:=c$.

  * •

For every function symbol $f$ of $L^{+}$, define
$f^{\mathfrak{M}_{\Gamma}^{\prime}}$ for each
$t_{0},...,t_{\eta(f)-1}\in|\mathfrak{M}_{\Gamma}^{\prime}|$ as

$f^{\mathfrak{M}_{\Gamma}^{\prime}}\big{(}t_{0},...,t_{\eta(f)-1}\big{)}:=f(t_{0},...,t_{\eta(f)-1}).$

  * •

For every predicate symbol $P$ of $L^{+}$, define
$P^{\mathfrak{M}_{\Gamma}^{\prime}}$ for each
$t_{0},...,t_{\eta(P)-1}\in|\mathfrak{M}_{\Gamma}^{\prime}|$ as

$P^{\mathfrak{M}_{\Gamma}^{\prime}}\big{(}t_{0},...,t_{\eta(P)-1}\big{)}:=\sup\big{\\{}p\in[0,1]:\underline{p}\in\mathrm{Dyad}\text{
and }\underline{p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(t_{0},...,t_{\eta(P)-1})\in\Gamma\big{\\}}.$

The _basic assignment_ on $\mathfrak{M}_{\Gamma}^{\prime}$ is defined as
$\sigma(x):=x$ for every variable symbol $x$ of $L^{+}$. By a slight abuse of
notation, when $\mathfrak{M}_{\Gamma}^{\prime}$ is a Henkin continuous
$L^{+}$-pre-structure, by $\varphi^{\mathfrak{M}_{\Gamma}^{\prime}}$ we mean
$\varphi^{\mathfrak{M}_{\Gamma}^{\prime},\sigma}$, and by
$\mathfrak{M}_{\Gamma}^{\prime}\vDash\varphi$ we mean
$\mathfrak{M}_{\Gamma}^{\prime},\sigma\vDash\varphi$, where $\sigma$ is the
basic assignment.

The _Henkin $L^{+}$-structure over $\Gamma$_ ($\mathfrak{M}_{\Gamma}$) is the
structure induced by the metric completion of
$\big{(}|\mathfrak{M}_{\Gamma}^{\prime}|,\underline{d}^{\mathfrak{M}_{\Gamma}^{\prime}}\big{)}$
and the elementary morphism given in Theorem 4.

######  Theorem 5 (Theorem 9.4, [2]).

Let $\Gamma$ be a maximally consistent, Henkin complete set of $L^{+}$-wffs.
Then $\mathfrak{M}_{\Gamma}\vDash\Gamma$.

######  Corollary 1 (Completeness of Continuous Logic, Theorem 9.5, [2]).

A set of $L$-wffs is consistent if and only if it is (completely) satisfiable.

Ben Yaacov and Pedersen then introduce important maps from sets of $L$-wffs
into $[0,1]$. These maps serve as upper bounds on relative provability and
interpretation of sentences following from those sets of $L$-wffs.

######  Definition 11.

Let $\Gamma$ be a set of $L$-wffs. The _degree of truth with respect to
$\Gamma$_ ($\ \cdot\text{ }^{\circ}_{\Gamma}$) is a map from wffs to $[0,1]$,
defined as

$\varphi_{\Gamma}^{\circ}:=\sup\big{\\{}\varphi^{\mathfrak{M},\sigma}:\mathfrak{M},\sigma\vDash\Gamma\big{\\}}.$

The _degree of provability with respect to $\Gamma$_ ($\ \cdot\text{
}^{\circledcirc}_{\Gamma}$) is a similar map, defined as

$\varphi_{\Gamma}^{\circledcirc}:=\inf\big{\\{}p\in[0,1]:\underline{p}\in\mathrm{Dyad}\text{
and }\Gamma\vdash\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{p}\big{\\}}.$

The Completeness Theorem then implies that these maps are the same.

######  Corollary 2 (Corollary 9.8, [2]).

For any $L^{+}$-wff $\varphi$ and set of $L$-wffs $\Gamma$,
$\varphi_{\Gamma}^{\circ}=\varphi_{\Gamma}^{\circledcirc}$.

######  Definition 12.

A set of $L$-wffs $\Gamma$ is _complete_ if there is a structure
$\mathfrak{M}$ and assignment $\sigma$ such that for every $L$-wff $\varphi$,

$\varphi^{\circ}_{T}=\varphi^{\mathfrak{M},\sigma}.$

$\Gamma$ is _incomplete_ if it is not complete.

In contrast to the classical case, even if a theory is complete, its set of
consequences may not be maximally consistent. This is due to the limiting
behavior condition discussed in Definition 8. The Deduction Theorem for
continuous logic encounters a similar issue.

######  Theorem 6 (Deduction Theorem, Theorem 8.1, [2]).

Let $\Gamma$ be a set of $L$-wffs. Then for every $L$-wff $\psi$,
$\Gamma\cup\\{\psi\\}\vdash\varphi$ if and only if
$\Gamma\vdash\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}m\psi$, for some $m\in\mathbb{N}$.

We also note the Generalization Theorem, which will be useful in future work.

######  Lemma 2 (Generalization Theorem, Lemma 8.2, [2]).

Let $\Gamma$ be a set of $L^{+}$-wffs and $\varphi$ an $L^{+}$-wff. If $x$
does not appear freely in $\Gamma$ and $\Gamma\vdash\varphi$, then
$\Gamma\vdash\sup_{x}\varphi$.

And lastly, we note the following lemma of Calvert’s.

######  Lemma 3 (Lemma 4.6, [5]).

There is an effective procedure which extends $L$ to its Henkin extended
signature $L^{+}$.

##  4\. Main result

###  4.1. Model-theoretic preliminaries

There are four important model-theoretic propositions which extend the results
of [2] and are useful for the construction of the effective completeness
theorem.

######  Proposition 1.

Let $\Gamma$ be a set of $L$-wffs and $B$ a finite set of $L$-wffs. Then for
every $L$-wff $\varphi$,

$\varphi_{\Gamma\cup
B}^{\circ}\leq\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}_{\Gamma}^{\circ}.$

###### Proof.

Fix an $L$-wff $\varphi$. If $\varphi^{\circ}_{\Gamma\cup B}=0$, the result
follows trivially. Thus suppose $\varphi^{\circ}_{\Gamma\cup B}>0$. Notably,
this implies that $\Gamma\cup B$ is consistent. Fix $p\in\mathrm{Dyad}_{L}$
such that $\overline{p}<\varphi_{\Gamma\cup B}^{\circ}$. Then there is some
$L$-structure $\mathfrak{M}$ and assignment $\sigma$ such that
$\mathfrak{M},\sigma\vDash\Gamma\cup B$ while
$\varphi^{\mathfrak{M},\sigma}>\overline{p}$. But, clearly, since
$\mathfrak{M},\sigma\vDash B$, $\Big{(}\bigvee_{\theta\in
B}\theta\Big{)}^{\mathfrak{M},\sigma}=0$. Hence,
$\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}^{\mathfrak{M},\sigma}>\overline{p}$. Then since
$\mathfrak{M},\sigma\vDash\Gamma$, this implies that
$\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}^{\circ}_{\Gamma}>\overline{p}$. Since this is true for every
$\overline{p}<\varphi_{\Gamma\cup B}^{\circ}$, we have that
$\varphi_{\Gamma\cup
B}^{\circ}\leq\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}_{\Gamma}^{\circ}$.

∎

######  Proposition 2.

Let $\Gamma$ be a set of $L$-wffs and $B$ a finite set of $L$-wffs such that
$\Gamma\cup B$ is consistent. Then there are infinitely many $L$-wffs
$\varphi$ such that

$\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}_{\Gamma}^{\circ}=1.$

###### Proof.

Recall that $\Gamma\cup B$ is consistent if and only if there is some $L$-wff
$\varphi$ such that $\Gamma\cup B\nvdash\varphi$. By Corollary 2,
$\varphi_{\Gamma\cup B}^{\circ}>\frac{1}{M}$, for some $M\in\mathbb{N}$. It
follows that for every $m\geq M$, $(m\varphi)_{\Gamma\cup B}^{\circ}=1$.
Hence, by Proposition 1, $\Big{(}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{\theta\in
B}\theta\Big{)}_{\Gamma}^{\circ}=1$, for every $m\geq M$. ∎

######  Proposition 3.

Let $L$ be a signature, $T$ an $L$-theory, and $\varphi$ an $L$-wff with free
variables $\vec{x}$. Then

$\varphi^{\circ}_{T}=\big{(}\sup_{\vec{x}}\varphi\big{)}^{\circ}_{T}.$

###### Proof.

Fix a signature $L$, an $L$-theory $T$, and an $L$-wff $\varphi$ with free
variables $\vec{x}$. Notice that since $T$ contains only $L$-sentences, none
of $\vec{x}$ appear freely in $T$. It follows via Corollary 2 and the
Generalization Theorem that

$\begin{split}\varphi^{\circ}_{T}&=\inf\big{\\{}\overline{p}:p\in\mathrm{Dyad}_{L}\text{
and }T\vdash\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}p\big{\\}}\\\
&=\inf\big{\\{}\overline{p}:p\in\mathrm{Dyad}_{L}\text{ and
}T\vdash\sup_{\vec{x}}\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}p\big{\\}}\\\
&=\big{(}\sup_{\vec{x}}\varphi\big{)}^{\circ}_{T}.\end{split}$

∎

######  Proposition 4.

Let $T$ be an $L$-theory. Then for every $L^{+}$-wff $\theta$,

$\big{(}\sup_{\vec{x}}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}=\theta^{\circ}_{T},$

where $\vec{c}$ is the tuple of all constants from $L^{+}$, but not in $L$,
appearing in $\theta$.

###### Proof.

Fix an $L$-theory $T$ and an $L^{+}$-wff $\theta$. Recall that no variable
from $\vec{x}$ appears freely in $T$, nor does any constant in $\vec{c}$
appear in $T$, since it is an $L$-theory. Hence for every $L$-structure
$\mathfrak{M}$ such that $\mathfrak{M}\vDash T$, and every tuple
$\vec{a}\in|\mathfrak{M}|$, there is an $L^{+}$-structure
$\mathfrak{M}^{+}_{\vec{a}}$ such that
$\vec{c}^{\mathfrak{M}^{+}_{\vec{a}}}=\vec{a}$ and
$\mathfrak{M}^{+}_{\vec{a}}\upharpoonright_{L}=\mathfrak{M}$. Then

$\begin{split}\big{(}\sup_{\vec{x}}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}&=\sup\Big{\\{}\big{(}\sup_{\vec{x}}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M}}:\mathfrak{M}\vDash
T\Big{\\}}\\\
&=\sup\Big{\\{}\sup_{\\{\sigma(\vec{x}\mapsto\vec{a}):\vec{a}\in|\mathfrak{M}|\\}}\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M},\sigma(\vec{x}\mapsto\vec{a})}:\mathfrak{M}\vDash
T\Big{\\}}\\\
&=\sup\Big{\\{}\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M},\sigma(\vec{x}\mapsto\vec{a})}:\mathfrak{M},\sigma(\vec{x}\mapsto\vec{a})\vDash
T,\ \vec{a}\in|\mathfrak{M}|\Big{\\}}\\\
&\leq\sup\Big{\\{}\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M}^{+}_{\vec{a}},\sigma(\vec{x}\mapsto\vec{a})}:\mathfrak{M}^{+}_{\vec{a}},\sigma(\vec{x}\mapsto\vec{a})\vDash
T,\ \vec{a}\in|\mathfrak{M}|\Big{\\}}\\\
&=\sup\Big{\\{}\theta^{\mathfrak{M}^{+}_{\vec{a}},\sigma}:\mathfrak{M}^{+}_{\vec{a}},\sigma\vDash
T\Big{\\}}\\\
&\leq\sup\Big{\\{}\theta^{\mathfrak{M}^{+},\sigma}:\mathfrak{M}^{+},\sigma\vDash
T\Big{\\}}\\\ &=\theta^{\circ}_{T}.\end{split}$

Now notice that for any $L^{+}$-structure $\mathfrak{M}^{+}$ and assignment
$\sigma$, there is an assignment
$\sigma(\vec{x}\mapsto\vec{c}^{\mathfrak{M}^{+}_{\vec{a}}})$. Then the
$L$-structure $\mathfrak{M}^{+}\upharpoonright_{L}$ is such that
$\theta^{\mathfrak{M}^{+},\sigma}=\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M}^{+}\upharpoonright_{L},\sigma(\vec{x}\mapsto\vec{c}^{\mathfrak{M}^{+}_{\vec{a}}})}$.
It follows that

$\begin{split}\theta^{\circ}_{T}&=\sup\Big{\\{}\theta^{\mathfrak{M}^{+},\sigma}:\mathfrak{M}^{+},\sigma\vDash
T\Big{\\}}\\\
&=\sup\Big{\\{}\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M}^{+}\upharpoonright_{L},\sigma(\vec{x}\mapsto\vec{c}^{\mathfrak{M}^{+}_{\vec{a}}})}:\mathfrak{M}^{+}\upharpoonright_{L},\sigma(\vec{x}\mapsto\vec{c}^{\mathfrak{M}^{+}_{\vec{a}}})\vDash
T\Big{\\}}\\\
&\leq\sup\Big{\\{}\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\mathfrak{M},\sigma}:\mathfrak{M},\sigma\vDash
T\Big{\\}}\\\ &=\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}.\end{split}$

But by Proposition 3,
$\big{(}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}=\big{(}\sup_{\vec{x}}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}$.
Therefore,
$\theta^{\circ}_{T}\leq\big{(}\sup_{\vec{x}}\theta[\vec{x}/\vec{c}]\big{)}^{\circ}_{T}$.
The claim follows. ∎

###  4.2. Effectively extending theories

Since any $L$-theory $T$ has an associated degree of truth map
$\cdot^{\circ}_{T}$, to analyze the effectiveness of a theory we will actually
consider the effectiveness of the related degree of truth map. The following
definition is given in [2].

######  Definition 13.

An $L$-theory $T$ is _decidable_ if $\cdot^{\circ}_{T}$ is a computable map
from the set of wffs to $[0,1]$.

Since there are uncountably-many such maps, we introduce a naming system.

######  Definition 14.

Given an $L$-theory $T$, we say that $X\in\mathbb{N}^{\mathbb{N}}$ is a _name_
of $T$ if the following hold.

  * •

For every $n,k\in\mathbb{N}$, there is some $m\in\mathbb{N}$ such that
$\langle n,k,m\rangle\in\mathrm{ran}(X)$.

  * •

For every $n,k,m\in\mathbb{N}$, if $\langle n,k,m\rangle\in\mathrm{ran}(X)$,
then $q_{m}\in\big{[}\ (\varphi_{n})^{\circ}_{T}-2^{-k}\ ,\
(\varphi_{n})^{\circ}_{T}+2^{-k}\ \big{]}$.

######  Proposition 5.

An $L$-theory is decidable if and only if it has a computable name.

###### Proof.

For the forward direction, suppose $\cdot^{\circ}_{T}$ is computable. Fix a
witness of this computability. For every code of a pair, define $X(\langle
n,k\rangle):=\langle n,k,m\rangle$ where the witness outputs $q_{m}$, given
$\varphi_{n}$ and precision parameter $k$. On every natural number which
doesn’t code a pair, let $X$ be $0$. For the reverse direction, suppose $X$ is
a computable name. Given $\varphi_{n}$ and a precision parameter $k$, begin
computing $\mathrm{ran}(X)$ until a code of a triple of the form $\langle
n,k,m\rangle$ is output. It follows that $q_{m}\in\big{[}\
(\varphi_{n})^{\circ}_{T}-2^{-k}\ ,\ (\varphi_{n})^{\circ}_{T}+2^{-k}\
\big{]}$. ∎

Let $L^{+}$ be the Henkin extended signature effectively given by Lemma 3, and
let $(\theta_{n})_{n\in\mathbb{N}}$ be an effective enumeration of the
$L^{+}$-wffs. The next lemma we present is similar to Lemma 4.7 in [5].
However, in our case, the construction is with respect to any _name_ of an
$L$-theory, $X\in\mathbb{N}^{\mathbb{N}}$. Moreover, careful consideration is
taken with respect to when two $L^{+}$-sentences are provably equivalent with
respect to a given $L^{+}$-theory.

The basic idea of the proof is the following. Given the degree of truth of a
theory $\cdot^{\circ}_{T}$, find the first $L^{+}$-wff of the form
$\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi$
which has a _strictly positive_ degree of truth. It follows that there is some
structure $\mathfrak{M}$ and assignment $\sigma$ such that
$\mathfrak{M},\sigma\vDash T$ while
$\mathfrak{M},\sigma\nvDash\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi$. Hence $\mathfrak{M},\sigma\vDash
T\cup\\{\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi\\}$. Moreover,
$\cdot^{\circ}_{T\cup\\{\psi\mathbin{\mathrm{\ooalign{\raise
3.01389pt\hbox{.}\cr$-$\cr}}}\varphi\\}}$ is shown to be effective in
$\cdot^{\circ}_{T}$. Thus we may effectively complete $T$ as an
$L^{+}$-theory.

######  Lemma 4.

There is an effective procedure which given $X$, a name of an $L$-theory $T$,
outputs $\Phi(X)\subseteq\mathbb{N}$ such that
$T\cup\\{\theta_{n}:n\in\Phi(X)\\}$ is consistent, and for every pair of
$L^{+}$-wffs $\varphi$ and $\psi$, either $\varphi$ and $\psi$ are provably
equivalent with respect to $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$, or exactly one
of $\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi$
or $\psi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\varphi$
is in $\\{\theta_{n}:n\in\Phi(X)\\}$.

###### Proof.

We proceed via partial effective recursion. First define
$\Phi_{0}(X):=\emptyset$, for every $X\in\mathbb{N}^{\mathbb{N}}$. As the
recursive assumption, we suppose that at stage $s$, if $X$ is a name of an
$L$-theory $T$, then $\Phi_{s}(X)$ is defined, finite, and
$T\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}$ is consistent. At stage $s+1$, the
following procedure attempts to construct $\Phi_{s+1}(X)$.

For every pair of $L^{+}$-wffs $\varphi$ and $\psi$, define the real number

$r_{\varphi,\psi,f,s+1}:=\Big{(}\sup_{\vec{x},\vec{y}}\
\sup_{\vec{z}}\Big{(}\Big{(}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}\bigvee_{n\in\Phi_{s}(X)}\theta_{n}\Big{)}\Big{)}[\vec{z}/\vec{c}]\Big{)}\Big{)}_{T}^{\circ},$

where $\vec{x}$ and $\vec{y}$ are the free variables appearing in
$\psi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\varphi$
and $\bigvee_{n\in\Phi_{s}(X)}\theta_{n}$, respectively, $\vec{c}$ is the
(possibly empty) tuple of constants from $L^{+}$ and not in $L$ appearing in
$(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\big{(}\bigvee_{n\in\Phi_{s}(X)}\theta_{n}\big{)}$,
and $\vec{z}$ is a $|\vec{c}|$-tuple of variable symbols distinct from
$\vec{x}$ and $\vec{y}$. Notably, these real numbers are computable in $f$,
uniformly in $\varphi$, $\psi$, and $s$. To see this, notice that each
recursively defined $\Phi_{s}(X)$ is finite, each free variable becomes bound
by the quantifier, and every constant from $L^{+}$ not in $L$ is replaced by a
variable and bound. Hence each formula checked above is actually an
$L$-sentence, so $f$ can compute a rational approximation of
$r_{\varphi,\psi,X,s+1}$ within $2^{-(s+2)}$. Call such a rational
$q_{\varphi,\psi,X,s+1}$. Then search the pairs of $L^{+}$-wffs for the first
pair $\varphi$ and $\psi$ such that $\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi\notin\\{\theta_{n}:n\in\Phi_{s}(X)\\}$ and
$q_{\varphi,\psi,X,s+1}\geq 2^{-(s+1)}$. By Proposition 2, there are
infinitely many $L^{+}$-wffs $\psi$ such that
$r_{\underline{0},\psi,X,s+1}=1$, and hence such that
$q_{\underline{0},\psi,X,s+1}\geq 2^{-(s+1)}$. Thus, when $X$ is a name of an
$L$-theory, the procedure will halt. When such a pair $\varphi$ and $\psi$ is
found, search the effective enumeration of the $L^{+}$-wffs for the index $m$
of $\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi$
and define $\Phi_{s+1}(X):=\Phi_{s}(X)\cup\\{m\\}$. Clearly, if
$\Phi_{s+1}(X)$ is defined, it is also finite, by construction. We now claim
that this $\Phi$ witnesses the lemma. Fix a name of an $L$-theory
$X\in\mathbb{N}^{\mathbb{N}}$.

To see that ${T}\cup\\{\theta_{n}:n\in\Phi(X)\\}$ is consistent, we show that
each ${T}\cup\\{\theta_{n}:n\in\Phi_{s+1}(X)\\}$ is consistent, for every
$s\in\mathbb{N}$. We proceed inductively.

Suppose ${T}\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}$ is consistent and fix
$m\in\Phi_{s+1}(X)\setminus\Phi_{s}(X)$. By construction this $m$ is the index
for $\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi$ where $q_{\varphi,\psi,X,s+1}\geq
2^{-(s+1)}$. It follows by the definition of $q_{\varphi,\psi,X,s+1}$ and
Propositions 3 and 4, Corollary 2, logical equivalence, and the Deduction
Theorem, that we have each of the following.

$\begin{split}\Big{(}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}&\Big{(}\bigvee_{n\in\Phi_{s}(X)}\theta_{n}\Big{)}\Big{)}_{T}^{\circ}\geq
2^{-(s+2)}\\\ &\implies\ \
\Big{(}\underline{2^{-(s+2)}}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}\bigvee_{n\in\Phi_{s}(X)}\theta_{n}\Big{)}\Big{)}\Big{)}_{T}^{\circ}=0\\\
&\implies\ \
{T}\vdash\Big{(}\underline{2^{-(s+2)}}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}\bigvee_{n\in\Phi_{s}(X)}\theta_{n}\Big{)}\Big{)}\Big{)}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-(s+3)}}\\\ &\implies\ \
{T}\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}\cup\\{\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi\\}\vdash\underline{2^{-(s+3)}}.\end{split}$

Therefore,
${T}\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}\cup\\{\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi\\}$ is inconsistent. It follows by Lemma
1 that $\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi$ is consistent with
${T}\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}$.

We therefore need only show that for every pair of $L^{+}$-wffs $\varphi$ and
$\psi$, either $\varphi$ and $\psi$ are provably equivalent with respect to
$T\cup\\{\theta_{n}:n\in\Phi(X)\\}$, or exactly one of
$\varphi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\psi$ or
$\psi\mathbin{\mathrm{\ooalign{\raise 4.30554pt\hbox{.}\cr$-$\cr}}}\varphi$ is
in $\\{\theta_{n}:n\in\Phi(X)\\}$.

Note that a pair of $L^{+}$-wffs $\varphi$ and $\psi$ is provably equivalent
with respect to $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$ if and only if for every
$s\in\mathbb{N}$, there is some $S\in\mathbb{N}$ such that

$T\cup\\{\theta_{n}:n\in\Phi_{S}(X)\\}\vdash(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-(s+2)}}\ \ \ \ \text{ and }\ \ \ \
T\cup\\{\theta_{n}:n\in\Phi_{s}(X)\\}\vdash(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-(s+2)}}.$

Now fix a pair of $L^{+}$-wffs $\varphi$ and $\psi$ that are not provably
equivalent with respect to $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$. Then there
must be some $s\in\mathbb{N}$ such that for every $S\in\mathbb{N}$, either

$T\cup\\{\theta_{n}:n\in\Phi_{S}(X)\\}\nvdash(\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-(s+2)}}\ \ \ \ \text{ or }\ \ \ \
T\cup\\{\theta_{n}:n\in\Phi_{S}(X)\\}\nvdash(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{2^{-(s+2)}}.$

At least one of these two cases must hold for infinitely many
$S\in\mathbb{N}$. Without loss of generality, since the cases are symmetric,
suppose it is the latter. It follows by Corollary 2 that for every
$S\in\mathbb{N}$, $(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)^{\circ}_{T\cup\\{\theta_{n}:n\in\Phi_{S}(X)\\}}\geq
2^{-(s+2)}.$ Hence by Proposition 1, for every $S\in\mathbb{N}$,

$\Big{(}(\psi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\varphi)\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}\bigvee_{n\in\Phi_{S}(X)}\theta_{n}\Big{)}\Big{)}_{T}^{\circ}\geq
2^{-(s+2)}.$

Then by Propositions 3 and 4, for every $S\in\mathbb{N}$,
$r_{\varphi,\psi,X,S+1}\geq 2^{-(s+2)}$. Thus for some $S\geq s+2$, $\varphi$
and $\psi$ will have to be the first pair such that
$\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi\notin\\{\theta_{n}:n\in\Phi_{S}(X)\\}$ and
$q_{\varphi,\psi,X,S+1}\geq 2^{-(s+3)}\geq 2^{-(S+1)}$. It follows that the
procedure will place the index for $\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi$ into $\Phi_{S+1}(X)$, so
$\varphi\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\psi\in\\{\theta_{n}:n\in\Phi(X)\\}$. ∎

It should be noted that if $T$ is not complete, a name of $T$ does not specify
a _unique_ consistent extension of $T$. The above procedure constructs a
complete extension, which itself has a unique maximally consistent extension,
but the procedure is dependent on the enumeration of the $L^{+}$-wffs. When
that enumeration changes, if $T$ is not a complete theory, the above extension
of $T$ may also change.

###  4.3. Generalized effective completeness

We now come to our main result.

######  Theorem 7 (Generalized Effective Completeness).

There is an effective procedure which, given a name
$X\in\mathbb{N}^{\mathbb{N}}$ of an $L$-theory $T$, produces a presentation of
an $L^{+}$-structure $\mathfrak{M}$ such that $\mathfrak{M}\vDash T$.

###### Proof.

Compute $L^{+}$ as in Lemma 3. Given a name of an $L$-theory
$X\in\mathbb{N}^{\mathbb{N}}$, let $\Phi(X)$ be as in Lemma 4. Then, by
Theorem 3, extend $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$ to a maximally
consistent, Henkin complete $L^{+}$-theory $\Gamma$. By Proposition 5,
$\mathfrak{M}_{\Gamma}\vDash T$.

Since $L^{+}$ is effectively numbered, the set of constants of $L^{+}$ is also
effectively numbered, which we may effectively join to an effective numbering
of the variable symbols. Let $g^{\prime}$ be such an effective numbering.
Then, for every $n\in\mathbb{N}$, define $g(n):=[g^{\prime}(n)]$, the
equivalence class of $g^{\prime}(n)$ in $|\mathfrak{M}_{\Gamma}|$. By
construction, the algebra generated by $\mathrm{ran}(g)$ in
$\mathfrak{M}_{\Gamma}$ is the set of all equivalence classes of terms of
$L^{+}$, that is, equivalence classes of the elements of
$|\mathfrak{M}_{\Gamma}^{\prime}|$. It follows that this algebra is dense in
$|\mathfrak{M}_{\Gamma}|$, since by construction $|\mathfrak{M}_{\Gamma}|$ is
the metric completion of $|\mathfrak{M}_{\Gamma}^{\prime}|$. Thus
$\big{(}\mathfrak{M}_{\Gamma},g\big{)}$ is a presentation of
$\mathfrak{M}_{\Gamma}$. We further claim that
$\big{(}\mathfrak{M}_{\Gamma},g\big{)}$ is a computable presentation.

Fix a code of an $N$-ary predicate symbol $P$, codes of rational points
$[t_{0}],...,[t_{N-1}]$, and a precision parameter $k\in\mathbb{N}$. From
these, use $g^{\prime}$ to decode $L^{+}$-terms $t_{0},...,t_{N-1}$
corresponding to $[t_{0}],...,[t_{N-1}]$. Then execute the following.

Compute the finite set $D=\big{\\{}\underline{p}\in\mathrm{Dyad}:\text{ the
denominator of }p\text{ is less than }2^{k+2}\big{\\}}$. By the construction
of $\Phi(X)$, with access to an oracle that computes $X$ we may compute the
least $M\geq k+2$ such that for all but one $\underline{p}\in D$, exactly one
of $\underline{p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(t_{0},...,t_{N-1})$ or
$P(t_{0},...,t_{N-1})\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\underline{p}$ is in
$\\{\theta_{n}:n\in\Phi_{M+1}(X)\\}$.333It may be that for some
$\underline{p}\in D$, for every $M\in\mathbb{N}$,
$\big{(}P(t_{0},...,t_{N-1})\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\bigvee_{n\in\Phi_{M}(X)}\theta_{n}\big{)}^{\circ}_{T}$
and $p$ differ by less than $2^{-(M+2)}$. This can only occur if
$P(t_{0},...,t_{N-1})$ and $\underline{p}$ are provably equivalent with
respect to $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$, which can happen for at most
one $\underline{p}\in D$, since $T\cup\\{\theta_{n}:n\in\Phi(X)\\}$ is
consistent. Then compute the finite set $E=\big{\\{}\underline{p}\in
D:\underline{p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(t_{0},...,t_{N-1})\in\\{\theta_{n}:n\in\Phi_{M+1}(X)\\}\big{\\}}$.
Notice that by construction

$\underline{\max_{\underline{p}\in E}p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(t_{0},...,t_{N-1})\in\Gamma\ \ \ \ \text{ and
}\ \ \ \ P(t_{0},...,t_{N-1})\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\big{(}\underline{\min_{\underline{p}\in
D\setminus E}p}\dotplus\underline{2^{-(k+2)}}\big{)}\in\Gamma.$

Therefore,

$\mathfrak{M}_{\Gamma}\vDash\underline{\max_{\underline{p}\in
E}p}\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}P(t_{0},...,t_{N-1})\ \ \ \ \text{ and }\ \ \ \
\mathfrak{M}_{\Gamma}\vDash
P(t_{0},...,t_{N-1})\mathbin{\mathrm{\ooalign{\raise
4.30554pt\hbox{.}\cr$-$\cr}}}\Big{(}\underline{\min_{\underline{p}\in
D\setminus E}p}\dotplus\underline{2^{-(k+2)}}\Big{)}.$

It follows that

$\max_{\underline{p}\in E}p\ \leq\
\big{(}P(t_{0},...,t_{N-1})\big{)}^{\mathfrak{M}_{\Gamma}}\ \leq\
\Big{(}\min_{\underline{p}\in D\setminus E}p+2^{-(k+2)}\Big{)}.$

This implies that

$\big{(}P(t_{0},...,t_{N-1})\big{)}^{\mathfrak{M}_{\Gamma}}\ \in\ \Big{[}\
\Big{(}\min_{\underline{p}\in D\setminus E}p-2^{-(k+1)}\Big{)}\ ,\
\Big{(}\min_{\underline{p}\in D\setminus E}p+2^{-(k+1)}\Big{)}\ \Big{]}.$

Note lastly that this procedure was uniform in $X\in\mathbb{N}^{\mathbb{N}}$.
∎

It follows that the presentation given by the above theorem is Turing
reducible to the name input. Hence if the name given is computable (meaning
the theory is decidable), the presentation produced is also computable.
Standard effective completeness then comes as a corollary.

######  Corollary 3 (Effective Completeness of Continuous Logic).

Every decidable theory is modeled by a computably presentable structure.

### Acknowledgement

I would like to thank Timothy H. McNicholl for his generous advice, comments,
critique, and encouragement on the completion of this paper.

## References

  * [1] ItaïBen Yaacov, Alexander Berenstein, C. Ward Henson, and Alexander Usvyatsov.  Model theory for metric structures.  In Model theory with applications to algebra and analysis. Vol. 2, volume 350 of London Math. Soc. Lecture Note Ser., pages 315–427. Cambridge Univ. Press, Cambridge, 2008.
  * [2] Itaï Ben Yaacov and Arthur Paul Pedersen.  A proof of completeness for continuous first-order logic.  The Journal of Symbolic Logic, 75(1):168–190, 2010.
  * [3] Itai Ben Yaacov and Alexander Usvyatsov.  Continuous first-order logic and local stability.  Transactions of the American Mathematical Society, 362:5213–5259, 2010.
  * [4] Tyler A. Brown, Timothy H. McNicholl, and Alexander G. Melnikov.  On the complexity of classifying lebesgue spaces.  Journal of Symbolic Logic, 85(3):1254–1288, 2020.
  * [5] Wesley Calvert.  Metric structures and probabilistic computation.  Theor. Comput. Sci., 412(25):2766–2775, jun 2011.
  * [6] Farzad Didehvar, Kaveh Ghasemloo, and Massoud Pourmahdian.  Effectiveness in rpl, with applications to continuous logic.  Annals of Pure and Applied Logic, 161(6):789–799, 2010.
  * [7] Johanna N. Y. Franklin and Timothy H. McNicholl.  Degrees of and lowness for isometric isomorphism.  J. Log. Anal., 12:Paper No. 6, 23, 2020.
  * [8] Alexander G. Melnikov.  Computably isometric spaces.  J. Symbolic Logic, 78(4):1055–1085, 2013.
  * [9] Terrence Millar.  Foundations of recursive model theory.  Annals of Mathematical Logic, 13:45–72, 1978.
  * [10] Klaus Weihrauch.  Computable analysis.  Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2000.