RWTH Aachen University<EMAIL_ADDRESS>RWTH Aachen
University<EMAIL_ADDRESS>Erich Grädel, Lovro Mrkonjić
Theory of Computation Finite Model Theory

# Elementary equivalence versus isomorphism in semiring semantics

Erich Grädel  Lovro Mrkonjić

###### Abstract

We study the first-order axiomatisability of finite semiring interpretations
or, equivalently, the question whether elementary equivalence and isomorphism
coincide for valuations of atomic facts over a finite universe into a
commutative semiring. Contrary to the classical case of Boolean semantics,
where every finite structure can obviously be axiomatised up to isomorphism by
a first-order sentence, the situation in semiring semantics is rather
different, and strongly depends on the underlying semiring. We prove that for
a number of important semirings, including min-max semirings, and the
semirings of positive Boolean expressions, there exist finite semiring
interpretations that are elementarily equivalent but not isomorphic. The same
is true for the polynomial semirings $\mathbb{S}[X]$, $\mathbb{B}[X]$ and
$\mathbb{W}[X]$ that are universal for the classes of absorptive, idempotent,
and fully idempotent semirings, respectively. On the other side, we prove that
for other, practically relevant, semirings such as the Viterby semiring
$\mathbb{V}$, the tropical semiring $\mathbb{T}$, the natural semiring
${\mathbb{N}}$ and the universal polynomial semiring ${\mathbb{N}}[X]$, all
finite semiring interpretations are first-order axiomatisable (and thus
elementary equivalence implies isomorphism), although some of the
axiomatisations that we exhibit use an infinite set of axioms.

###### keywords:

semiring semantics, elementary equivalence, axiomatisability

##  1 Introduction

Semiring semantics is based on the idea to evaluate logical statements not
just by _true_ or _false_ , but by values in some commutative semiring
$(K,+,\cdot,0,1)$. In this context, the standard semantics appears as the
special case when the Boolean semiring
$\mathbb{B}=(\\{\bot,\top\\},\lor,\land,\bot,\top)$ is used. Valuations in
other semirings provide additional information, beyond the truth or falsity of
a statement: the Viterbi-semiring
$\mathbb{V}=([0,1]_{\mathbb{R}},\max,\cdot,0,1)$ models _confidence scores_ ,
the tropical semiring $\mathbb{T}=(\mathbb{R}_{+}^{\infty},\min,+,\infty,0)$
is used for _cost analysis_ , and min-max-semirings $(K,\max,\min,a,b)$ for a
totally ordered set $(K,<)$ can model, for instance, different _access
levels_. More generally, semirings of polynomials, such as ${\mathbb{N}}[X]$,
$\mathbb{W}[X]$ or $\mathbb{B}[X]$, allow us to track the role of specific
atomic facts for the evaluation of a logical statement, to describe evaluation
strategies for a formula, and to determine which combinations of literals
prove the truth of a formula.

Some of the motivation for the study of semiring semantics comes from the
successful development of semiring provenance in database theory and related
fields (see e.g. [5, 6, 8, 13, 14, 17, 18, 19]), and the fact that the typical
applications of provenance analysis, such as confidence scores, cost analysis,
proof counting, and the understanding of evaluation strategies are of
importance in many other areas of logic as well. However, semiring provenance
analysis for database queries had originally been largely confined to positive
query languages, such as conjunctive queries, positive relational algebra, and
Datalog, and the treatment of negation poses non-trivial algebraic problems.
Only recently, semiring semantics has been extended to logics with negation,
and in particular to full first-order logic [11, 12], by means of new
algebraic constructions based on quotient semirings. Semiring semantics has
also been studied for other logics, including modal logics, description
logics, guarded logics, and fixed-point logic [1, 2, 3, 4], and this paper is
part of a larger project devoted to a systematic study of semiring semantics
for various logics. An important objective in this context is the
understanding of the _model theory of semiring semantics_ , and the
development of model-theoretic methods for semiring interpretations.

It turns out that this is much more involved and diverse than for Boolean
semantics. In the standard semantics, a model ${\mathfrak{A}}$ assigns to each
(instantiated) atomic formula a Boolean value, whereas $K$-interpretations
$\pi$, for a suitable semiring $K$, generalise this by assigning to each
literal a semiring value in $K$, where $0$ is interpreted as _false_ and all
other semiring values as _nuances of true_. Interpreting disjunction by $+$
and conjunction by $\cdot$, we can extend $\pi$ to provide semiring valuations
$\pi\llbracket\varphi\rrbracket\in K$ for all first-order sentences $\varphi$,
written in negation normal form. Semiring semantics thus gives a finer
distinction of logical statements, and formulae that are equivalent in the
Boolean sense (i.e. in the Boolean semiring) may have different valuations in
other semirings. As a consequence, standard facts of classical (finite) model
theory may lead to interesting and sometimes rather difficult questions in
semiring semantics, and the answer may strongly depend on algebraic properties
of the underlying semiring. Specific such questions that we study here concern
the first-order axiomatisability of finite $K$-interpretations or, what
amounts to the same, the relationship between isomorphism and elementary
equivalence in this context.

It is a rather trivial fact of finite model theory that every finite structure
${\mathfrak{A}}$ (with a finite vocabulary $\tau$) can be axiomatised, up to
isomorphism, by a first-order sentence $\chi_{\mathfrak{A}}$. In particular,
two finite $\tau$-structures ${\mathfrak{A}}$ and ${\mathfrak{B}}$ are
isomorphic if, and only if, they are elementarily equivalent, in short
${\mathfrak{A}}\equiv{\mathfrak{B}}$, which means that they cannot be
distinguished by any first-order sentence. Is this also the case for semiring
interpretations? Notice that standard notions such as isomorphism and
elementary equivalence generalise in a natural way from $\tau$-structures to
semiring interpretations, which raises, for any given semiring $K$, the
following

######  Questions.

  1. 1.

Are elementary equivalent finite $K$-interpretations always isomorphic?

  2. 2.

Is every finite $K$-interpretation $\pi_{A}$ first-order axiomatisable, in the
sense that there is a set of axioms $\Phi_{A}\subseteq{\rm FO}$ such that
whenever
$\pi_{B}\llbracket\varphi\rrbracket=\pi_{A}\llbracket\varphi\rrbracket$ for
all $\varphi\in\Phi_{A}$, then $\pi_{B}\cong\pi_{A}$?

  3. 3.

Does every finite $K$-interpretation admit an axiomatisation by a _finite_ set
of axioms?

  4. 4.

Can every finite $K$-interpretation be axiomatised by a single first-order
sentence?

Clearly, the first two questions are equivalent, and a positive answer to the
third question implies also positive ones to the first two. The converse is
not necessarily true, because a first-order axiomatisation of a finite
semiring interpretation might require an infinite collection of sentences,
and, contrary to the Boolean case, it is a priori also not clear that an
axiomatisation by a finite set of sentences implies an axiomatisation by a
single sentence, because from the value of a conjunction we cannot necessary
infer the values of its components.

We shall prove that the answers to these questions strongly depend on the
chosen semiring. There are in fact rather simple semirings, such as min-max
semirings with at least three elements, for which one can construct examples
of non-isomorphic $K$-interpretations which are, however, elementarily
equivalent. The standard method for proving elementary equivalence in model
theory, the Ehrenfeucht–Fraïssé method, seems not really available in semiring
semantics, an aspect that we shall discuss at the end of this paper. To
establish elementary equivalence, we shall hence develop new methods based on
classes of semiring homomorphisms and reduction arguments. Elementarily
equivalent but non-isomorphic semiring interpretations also exist for powerful
polynomial semirings, such as $\mathbb{S}[X]$, $\mathbb{B}[X]$ and
$\mathbb{W}[X]$ which are universal for the classes of absorptive, idempotent,
and fully idempotent semirings, respectively. On the other side, there are
practically relevant semirings, such as the Viterby semring $\mathbb{V}$, the
tropical semiring $\mathbb{T}$, the natural semiring ${\mathbb{N}}$ and the
universal polynomial semiring ${\mathbb{N}}[X]$, for which any finite
$K$-interpretation is first-order axiomatisable, thus elementary equivalence
does indeed imply isomorphism. At least for $\mathbb{V}$ and $\mathbb{T}$,
finite axiomatisations are always possible, but not axiomatisations by a
single sentence, so there exist semirings where the answers to questions (3)
and (4) are different.

##  2 Semiring interpretations

We briefly summarise semiring semantics for first-order logic, as introduced
in [11].

######  Definition  (Semiring).

A commutative semiring ${\mathbb{K}}=(K,+,\cdot,0,1)$ is an algebraic
structure with two binary operations such that $(K,+,0)$ and $(K,\cdot,1)$ are
commutative monoids, multiplication distributes over addition and
multiplication with zero annihilates elements. We refer to commutative
semirings as semirings and identify ${\mathbb{K}}$ with its universe $K$ if
the operations are clear from the context.

Let $\tau$ denote a finite relational vocabulary. We write
$\operatorname{\mathrm{Lit}}_{n}(\tau)$ for the set of atoms $R\overline{z}$
and negated atoms $\neg R\overline{z}$ with $R\in\tau$ and where
$\overline{z}$ is any tuple of variables taken from $\\{x_{1},\dots,x_{n}\\}$.
For a universe $A$, we write $\operatorname{\mathrm{Lit}}_{A}(\tau)$ for the
set of _instantiated_ $\tau$-literals $R\overline{a}$ and $\neg R\overline{a}$
with $\overline{a}\in A^{\operatorname{arity}(R)}$.

######  Definition  ($K$-interpretation).

For a semiring $K$, a mapping
$\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$ is called a
$K$-_interpretation_ over the universe $A$ with signature $\tau$. We call
$\pi$ _model-defining_ if exactly one of the values $\pi(L)$ and
$\pi(\overline{L})$ is zero for all pairs of opposing literals
$L,\overline{L}\in\operatorname{\mathrm{Lit}}_{A}(\tau)$. In that case, $\pi$
_induces_ the classical model $\mathfrak{A}_{\pi}$ with
$\mathfrak{A}_{\pi}\models L$ if, and only if, $\pi(L)\neq 0$.

######  Definition  (Isomorphism).

$K$-interpretations $\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$
and $\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to K$ are _isomorphic_
, denoted as $\pi_{A}\mathrel{\cong}\pi_{B}$, if there is a bijective mapping
$\sigma\colon A\to B$ such that

$\pi_{A}(L)=\pi_{B}(\sigma(L))\quad\text{for all
}L\in\operatorname{\mathrm{Lit}}_{A}(\tau),$

where $\sigma(L)\in\operatorname{\mathrm{Lit}}_{B}(\tau)$ is defined by
replacing each $a\in A$ occurring in $L$ with $\sigma(a)\in B$. The mapping
$\sigma$ is called an _isomorphism_ , denoted as
$\sigma\colon\pi_{A}\xrightarrow{\sim}\pi_{B}$.

Given a $K$-interpretation $\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to
K$, a formula $\varphi(\overline{x})\in{\rm FO}(\tau)$ in negation normal form
and an assignment $\overline{a}\subseteq A$, the semiring semantics
$\pi\llbracket\varphi(\overline{a})\rrbracket$ is straightforwardly defined by
induction on ${\rm FO}(\tau)$. We first extend $\pi$ by mapping equalities and
inequalities to their truth values by

$\pi\llbracket a=b\rrbracket\coloneqq\begin{cases}1&\text{ if }a=b\\\ 0&\text{
if }a\neq b\end{cases}\quad\text{and}\quad\pi\llbracket a\neq
b\rrbracket\coloneqq\begin{cases}0&\text{ if }a=b\\\ 1&\text{ if }a\neq
b\end{cases},$

and by interpreting disjunctions and existential quantifiers as sums, and
conjunctions and universal quantifiers as products:

$\displaystyle\pi\llbracket\psi(\overline{a})\lor\vartheta(\overline{a})\rrbracket$
$\displaystyle\coloneqq\pi\llbracket\psi(\overline{a})\rrbracket+\pi\llbracket\vartheta(\overline{a})\rrbracket$
$\displaystyle\quad\quad\quad\pi\llbracket\psi(\overline{a})\land\vartheta(\overline{a})\rrbracket$
$\displaystyle\coloneqq\pi\llbracket\psi(\overline{a})\rrbracket\cdot\pi\llbracket\vartheta(\overline{a})\rrbracket$
$\displaystyle\pi\llbracket\exists x\vartheta(\overline{a},x)\rrbracket$
$\displaystyle\coloneqq\sum_{a\in
A}\pi\llbracket\vartheta(\overline{a},a)\rrbracket$
$\displaystyle\quad\quad\quad\pi\llbracket\forall
x\vartheta(\overline{a},x)\rrbracket$ $\displaystyle\coloneqq\prod_{a\in
A}\pi\llbracket\vartheta(\overline{a},a)\rrbracket.$

Our goal is to analyse model-theoretic concepts from classical model theory
under semiring semantics.

######  Definition  (Elementary Equivalence).

Let $\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$ and
$\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to K$ be two
$K$-interpretations, $\overline{a}\in A^{k}$ and $\overline{b}\in B^{k}$ be
$k$-tuples and $k\in\mathbb{N}$. The pairs $\pi_{A},\overline{a}$ and
$\pi_{B},\overline{b}$ are _elementarily equivalent_ , denoted as
$\pi_{A},\overline{a}\equiv\pi_{B},\overline{b}$, if

$\pi_{A}\llbracket\varphi(\overline{a})\rrbracket=\pi_{B}\llbracket\varphi(\overline{b})\rrbracket\quad\text{for
all }\varphi(\overline{x})\in{\rm FO}(\tau)\text{ with }k\text{ free
variables.}$

They are $m$-_equivalent_ with $m\in\mathbb{N}$, denoted as
$\pi_{A},\overline{a}\equiv_{m}\pi_{B},\overline{b}$, if the above holds for
all suitable $\varphi(\overline{x})$ with quantifier rank at most $m$.

Clearly, the notions of isomorphism and elementary equivalence of
$K$-interpretations are natural generalisations of the corresponding
definitions for $\tau$-structures. Further, it is obvious that, as in
classical semantics, isomorphism implies elementary equivalence.

######  Lemma 2.1 (Isomorphism Lemma).

Let $\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$ and
$\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to K$ be two
$K$-interpretations, $\overline{a}\in A^{k}$ and $\overline{b}\in B^{k}$ be
$k$-tuples and $\sigma\colon\pi_{A}\xrightarrow{\sim}\pi_{B}$ an isomorphism
with $\sigma(\overline{a})=\overline{b}$. Then,
$\pi_{A}\llbracket\varphi(\overline{a})\rrbracket=\pi_{B}\llbracket\varphi(\overline{b})\rrbracket$
holds for all $\varphi(\overline{x})\in{\rm FO}(\tau)$ with $k$ free
variables.

Coarser definitions may be conceivable in semirings $K$ with more than two
elements, such as replacing equality by a congruence relation ${\sim}\subseteq
K\times K$. However, Definition 2 indirectly covers these variants, since any
non-trivial congruence relation $\sim$ on $K$ induces a semiring homomorphism
$h_{\sim}\colon K\to K/{\sim}$, which is compatible with ${\rm FO}$-semantics
as follows [11].

######  Lemma 2.2 (Fundamental Property).

Let $\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$ be a
$K$-interpretation and $h\colon K\to L$ a semiring homomorphism. Then,
$(h\circ\pi)$ is an $L$-interpretation and

$(h\circ\pi)\llbracket\varphi(\overline{a})\rrbracket=h(\pi\llbracket\varphi(\overline{a})\rrbracket)$

holds for all $\varphi(\overline{x})\in{\rm FO}(\tau)$ and
$\overline{a}\subseteq A$. Thus, the following diagram commutes.

${\rm
FO}(\tau)$$K$$L$$\varphi(\overline{a})$$\pi\llbracket\varphi(\overline{a})\rrbracket$$(h\circ\pi)\llbracket\varphi(\overline{a})\rrbracket$$\pi\llbracket\bullet\rrbracket$$h$$(h\circ\pi)\llbracket\bullet\rrbracket$

##  3 Polynomial semirings and the universal property

Semiring homomorphisms and the fundamental property open the possibility to
reduce semiring semantics to the evaluation of polynomials. For a finite set
$X$ of abstract provenance tokens that are used to track atomic facts,
consider the semiring $\mathbb{N}[X]$ of multivariate polynomials with
indeterminates from $X$ and coefficients from $\mathbb{N}$, whose generality
is formalised by the following _universal property_ [13].

######  Lemma 3.1 (Universal Property).

For each commutative semiring $K$, every assignment $e\colon X\to K$ induces a
unique homomorphism $h_{e}\colon\mathbb{N}[X]\to K$ with $h_{e}(x)=e(x)$ for
$x\in X$.

To demonstrate the use of this property, consider the
$\mathbb{V}$-interpretation $\pi_{\mathbb{V}}$ over $A=\\{a,b\\}$ depicted
below on the left and a corresponding $\mathbb{N}[X]$-interpretation $\pi$ on
the right, which maps all the true literals to their own variable in
$X\coloneqq\\{w,x,y,z\\}$.

$\pi_{\mathbb{V}}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0.3$ $0.9$ $0$ $0$
$b$ $0$ $0.5$ $0.4$ $0$ $\quad\quad\quad\pi:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg
Q$ $a$ $x$ $y$ $0$ $0$ $b$ $0$ $z$ $w$ $0$

Given, for example, $\psi\coloneqq\forall x(Px\lor Qx)$, we get
$\pi_{\mathbb{V}}\llbracket\psi\rrbracket=\max\\{0.3,0.9\\}\cdot\max\\{0,0.5\\}=0.45$,
but if we have already computed the polynomial
$p\coloneqq\pi\llbracket\psi\rrbracket=(x+y)\cdot(0+z)=xz+yz$, then plugging
in the values $e\colon x\mapsto 0.3,y\mapsto 0.9,z\mapsto 0.5$ and $w\mapsto
0.4$ induces the homomorphism $h_{e}\colon\mathbb{N}[X]\to\mathbb{V}$, and
evaluating $p$ gives the same value $h_{e}(p)=\max\\{0.3\cdot 0.5,0.9\cdot
0.5\\}=0.45$ by the fundamental property. This approach may be used to save
computation resources if we have several interpretations sharing the same set
of true literals, so that $\pi\llbracket\psi\rrbracket$ is re-usable, but the
universality of $\mathbb{N}[X]$ also makes it relevant for model theory.

Other polynomial semirings can be used to capture smaller classes of
semirings, in the sense of the universal property.

######  Definition 3.2 (Idempotence and Absorption).

A semiring $K$ is called _idempotent_ if $a+a=a$ holds for all $a\in K$, that
is, if addition is idempotent. It is _multiplicatively idempotent_ if $a\cdot
a=a$ for all $a\in K$. If both properties hold, we call $K$ _fully
idempotent_. Finally, a semiring $K$ is _absorptive_ if $a+ab=a$ holds for all
$a,b\in K$.

Note that absorptive semirings are idempotent and if we replace addition with
$\lor$ and multiplication with $\land$, absorption corresponds to the
absorptive law in lattices. In particular, absorptive and fully idempotent
semirings are precisely the semirings induced by distributive lattices [16].

  * •

By dropping coefficients from $\mathbb{N}[X]$, we get the semiring
${\mathbb{B}}[X]$ whose elements are just finite sets of distinct monomials.
It has the universal property for the class of idempotent semirings.

  * •

By dropping also exponents, we get the semiring $\mathbb{W}[X]$ of finite sums
of monomials that are linear in each argument, with the universal property for
fully idempotent semirings. It is sometimes called the Why-semiring.

  * •

For absorptive semirings, we require absorptive polynomials as introduced in
[5]. An absorptive polynomial is a sum of distinct monomials over a finite set
of variables $X$, with absorption among monomials: a monomial $m_{1}$ absorbs
$m_{2}$, denoted $m_{1}\succeq m_{2}$, if it has smaller exponents, i.e. if
$m_{1}(x)\leq m_{2}(x)$ for all $x\in X$, where $m(x)$ denotes the exponent of
$x$ in $m$. Notice that absorption is the _inverse_ pointwise order on the
exponents. For example, $xy^{2}\succeq x^{3}y^{2}$ and $x\succeq xy$, but
$x^{2}y$ and $xy^{2}$ are incomparable. In an absorptive polynomial, we omit
all monomials that would be absorbed, so absorptive polynomials are
$\succeq$-_antichains_ of monomials (which are always finite [12]).
Consequently, addition and multiplication are defined as usual, but afterwards
we drop all monomials that are absorbed. We write $\mathbb{S}[X]$ for the
semiring of absorptive polynomials over the finite variable set $X$ with the
aforementioned operations. The $0$-element is the empty polynomial and $1$
denotes the polynomial consisting just of the monomial $1$ (with all zero
exponents). It is not difficult to verify that this defines an absorptive
semiring which has the universal property for the class of all absorptive
semirings.

  * •

By dropping exponents from $\mathbb{S}[X]$, we obtain yet another polynomial
semiring $\mathsf{PosBool}[X]$, which is universal for the fully idempotent
and absorptive semirings. Incidentally, polynomials from
$\mathsf{PosBool}[X]$, such as $x+yz$, represent all positive Boolean
expressions over the variables $X$ up to equivalence, if we replace addition
by disjunction and multiplication by conjunction, hence the name
$\mathsf{PosBool}[X]$. This is the distributive lattice freely generated by
the set $X$.

The following figure, adapted from [16], shows the relationships between the
aforementioned classes of semirings, together with their respective universal
polynomial semirings.

all commutative semirings: $\mathbb{N}[X]$idempotent semirings:
$\mathbb{B}[X]$distributivelattices:$\mathsf{PosBool}[X]$fully
idempotentsemirings:$\mathbb{W}[X]$absorptivesemirings:$\mathbb{S}[X]$

##  4 Separating elementary equivalence from isomorphism

We shall now, for certain semirings $K$, provide examples of finite, non-
isomorphic $K$-interpretations that are, however, elementarily equivalent. We
thus provide negative answers to Question (1) from the introduction, and hence
also to Questions (2) to (4). For instance, we claim that the following two
$K_{4}$-interpretations over the min-max-semiring with four elements,
$K_{4}=\\{0,1,2,3\\}$, are elementarily equivalent, but not isomorphic.

$\pi_{PQ}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ 1 3 0 0 $b$ 2 1 0 0 $c$ 3 2
0 0 $\quad\quad\quad\pi_{QP}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ 3 1 0 0
$b$ 1 2 0 0 $c$ 2 3 0 0

Observe that $\pi_{QP}$ is obtained from $\pi_{PQ}$ by permuting the relations
$P$ and $Q$, or visually, by permuting the “columns”. Moreover, for both
interpretations, the $Q$-column can be obtained by permuting the $P$-column.
Informally, these properties ensure that the two interpretations are
“sufficiently similar” so that no first-order sentence can distinguish them.

Clearly, $\pi_{PQ}$ is not isomorphic to $\pi_{QP}$, as intended. However, the
only tool we presented so far for proving elementary equivalence under
semiring semantics is the Isomorphism Lemma itself, which is not directly
applicable for obvious reasons. Hence, we shall develop another tool for
proving elementary equivalence that enables the indirect use of the
Isomorphism Lemma after switching to a different semiring via homomorphisms.

###  4.1 Separating pairs of homomorphisms

The central idea of the reduction technique is to “decompose” the semiring $K$
via homomorphisms. Observe that if $\pi_{A}\not\equiv\pi_{B}$, then there is a
witnessing sentence $\psi\in{\rm FO}(\tau)$ with
$\pi_{A}\llbracket\psi\rrbracket\neq\pi_{B}\llbracket\psi\rrbracket$, hence a
pair of distinct elements $a,b\in K$ with
$\pi_{A}\llbracket\psi\rrbracket\eqqcolon a\neq
b\coloneqq\pi_{B}\llbracket\psi\rrbracket$ exists. If we can find two
homomorphisms $h_{A},h_{B}\colon K\to L$ with $h_{A}(a)\neq h_{B}(b)$, but we
are sure that the corresponding $L$-interpretations $(h_{A}\circ\pi_{A})$ and
$(h_{B}\circ\pi_{B})$ are elementarily equivalent, then we can exclude $(a,b)$
as a witness for $\pi_{A}\not\equiv\pi_{B}$. If we are able to provide enough
pairs of homomorphisms so that each distinct pair $(a,b)$ can be excluded,
then $\pi_{A}\equiv\pi_{B}$ must hold. The following definition formalises the
required properties.

######  Definition 4.1 (Separating Homomorphism Pairs).

A set $S\subseteq\operatorname{Hom}^{2}(K,L)$ of homomorphism pairs
$h_{A},h_{B}\colon K\to L$ is called _separating_ if for all $a,b\in K$ with
$a\neq b$, there is a pair $(h_{A},h_{B})\in S$ such that $h_{A}(a)\neq
h_{B}(b)$. $S$ is called _diagonal_ if $h_{A}=h_{B}$ for all pairs
$(h_{A},h_{B})\in S$. In that case, we may write $S$ as a subset of
$\operatorname{Hom}(K,L)$.

Note that a single _injective_ homomorphism $h\colon K\to L$ induces the
diagonal separating set $S\coloneqq\\{(h,h)\\}$ with just one element.
Moreover, some semirings, such as $\mathsf{PosBool}[X]$, can be completely
decomposed into $L\coloneqq\mathbb{B}$ using a diagonal separating set of
semiring homomorphisms as follows. Any subset $Y\subseteq X$ induces a unique
homomorphism $h_{Y}\colon\mathsf{PosBool}[X]\to\mathbb{B}$ by $h_{Y}(x)=\top$
for $x\in Y$ and $h_{Y}(x)=\bot$ for $x\in X\setminus Y$. Clearly, for any
$p\in\mathsf{PosBool}[X]$, we have that $h_{Y}(p)=\top$ if, and only if, $p$
contains a monomial with only variables from $Y$.

######  Lemma 4.2.

The set $S:=\\{h_{Y}\mid Y\subseteq
X\\}\subseteq\operatorname{Hom}(\mathsf{PosBool}[X],\mathbb{B})$ is a diagonal
separating set of homomorphisms.

######  Proof 4.3.

Consider $p,q\in\mathsf{PosBool}[X]$ such that $p\neq q$. Among the monomials
that appear in one of the two polynomials $p,q$ but not in the other, let $m$
be one whose set $Y$ of variables is minimal. By symmetry, we can assume that
$m$ appears in $p$ but not in $q$. It follows that $h_{Y}(p)=\top$. We claim
that $h_{Y}(q)=\bot$. Otherwise $q$ must contain a monomial $m^{\prime}$ with
only variables from $Y$. Since $m^{\prime}$ has less variables than $m$,
$m^{\prime}$ must also be contained in $p$. But $m^{\prime}$ absorbs $m$, so
$m$ does not occur in $p$, a contradiction.

On the other side, $\mathbb{N}[X]$, among other semirings, cannot be
decomposed into $\mathbb{B}$ by a diagonal separating set. For example,
$h(x+xy)=h(x)\lor(h(x)\land h(y))=h(x)$ for all homomorphisms
$h\colon\mathbb{N}[X]\to\mathbb{B}$, but $x+xy\neq x$. The reason why a
decomposition into $\mathbb{B}$ would be useful for model theory is given by
the following reduction technique.

######  Proposition 4.4 (Reduction Technique).

Let $\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to K$ and
$\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to K$ be two
$K$-interpretations, $\overline{a}\in A^{k}$ and $\overline{b}\in B^{k}$ be
$k$-tuples and $S\subseteq\operatorname{Hom}^{2}(K,L)$ a separating set of
homomorphism pairs. Then, for any formula $\varphi(x_{1},\dots,x_{k})\in{\rm
FO}(\tau)$, we have that whenever
$(h_{A}\circ\pi_{A})\llbracket\varphi(\overline{a})\rrbracket=(h_{B}\circ\pi_{B})\llbracket\varphi(\overline{b})\rrbracket$
for all $(h_{A},h_{B})\in S$, then also
$\pi_{A}\llbracket\varphi(\overline{a})\rrbracket=\pi_{B}\llbracket\varphi(\overline{b})\rrbracket$.

######  Proof 4.5.

Suppose that
$\pi_{A}\llbracket\varphi(\overline{a})\rrbracket\neq\pi_{B}\llbracket\varphi(\overline{b})\rrbracket$.
Then, by definition of $S$, there exists a pair $(h_{A},h_{B})\in S$ such that
$h_{A}(\pi_{A}\llbracket\varphi(\overline{a})\rrbracket)\neq
h_{B}(\pi_{B}\llbracket\varphi(\overline{b})\rrbracket)$. Applying the
fundamental property yields
$(h_{A}\circ\pi_{A})\llbracket\varphi(\overline{a})\rrbracket\neq(h_{B}\circ\pi_{B})\llbracket\varphi(\overline{b})\rrbracket$.

######  Corollary 4.6.

With $S$ as above,
$(h_{A}\circ\pi_{A}),\overline{a}\equiv(h_{B}\circ\pi_{B}),\overline{b}$ for
all $(h_{A},h_{B})\in S$ implies that
$\pi_{A},\overline{a}\equiv\pi_{B},\overline{b}$. Moreover, for each
$m\in\mathbb{N}$,
$(h_{A}\circ\pi_{A}),\overline{a}\equiv_{m}(h_{B}\circ\pi_{B}),\overline{b}$
for all $(h_{A},h_{B})\in S$ implies
$\pi_{A},\overline{a}\equiv_{m}\pi_{B},\overline{b}$.

If we choose the target semiring $L\coloneqq\mathbb{B}$, then the corollary
shows that proving equivalence in $K$ may be reduced to proving equivalence in
$\mathbb{B}$, which allows us to re-use results from standard semantics.

###  4.2 Applications to $\mathsf{PosBool}[X]$ and $\mathbb{W}[X]$

Consider the following two $\mathsf{PosBool}[X]$-interpretations
$\pi_{xy},\pi_{yx}$ with $X\coloneqq\\{x,y\\}$ over the universe
$A\coloneqq\\{a,b,c,d\\}$ with four elements and a signature
$\tau\coloneqq\\{P,Q\\}$ with two unary relation symbols.

$\pi_{xy}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0$ $y$ $x$ $0$ $b$ $x$ $0$
$0$ $y$ $c$ $y$ $x$ $0$ $0$ $d$ $0$ $0$ $y$ $x$
$\quad\quad\quad\pi_{yx}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $y$ $0$ $0$
$x$ $b$ $0$ $x$ $y$ $0$ $c$ $x$ $y$ $0$ $0$ $d$ $0$ $0$ $x$ $y$

Thanks to Lemma 4.2, the four homomorphisms
$S=\\{h_{\varnothing},h_{\\{x\\}},h_{\\{y\\}},h_{\\{x,y\\}}\\}$ induce a
separating set on $\mathsf{PosBool}[X]$ and with Corollary 4.6, it suffices to
show that $(h\circ\pi_{xy})\equiv(h\circ\pi_{yx})$ in $\mathbb{B}$ for all
$h\in S$ in order to prove $\pi_{xy}\equiv\pi_{yx}$ on $\mathsf{PosBool}[X]$.
Indeed, the following tables demonstrate that
$(h\circ\pi_{xy})\mathrel{\cong}(h\circ\pi_{yx})$ holds for all $h\in S$.

$\phantom{h_{\\{y\\}}\circ\pi_{xy}:}\mathllap{h_{\varnothing}\circ\pi_{xy}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $\bot$ $\bot$ $\bot$ $\bot$ $b$ $\bot$
$\bot$ $\bot$ $\bot$ $c$ $\bot$ $\bot$ $\bot$ $\bot$ $d$ $\bot$ $\bot$ $\bot$
$\bot$
$\quad\phantom{h_{\\{y\\}}\circ\pi_{yx}:}\mathllap{h_{\varnothing}\circ\pi_{yx}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $\bot$ $\bot$ $\bot$ $\bot$ $b$ $\bot$
$\bot$ $\bot$ $\bot$ $c$ $\bot$ $\bot$ $\bot$ $\bot$ $d$ $\bot$ $\bot$ $\bot$
$\bot$

$\phantom{h_{\\{y\\}}\circ\pi_{xy}:}\mathllap{h_{\\{x\\}}\circ\pi_{xy}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\bot$ $\bot$ $\top$ $\bot$
$b$ $\top$ $\bot$ $\bot$ $\bot$ $c$ $\bot$ $\top$ $\bot$ $\bot$ $d$ $\bot$
$\bot$ $\bot$ $\top$
$\quad\phantom{h_{\\{y\\}}\circ\pi_{yx}:}\mathllap{h_{\\{x\\}}\circ\pi_{yx}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\bot$ $\bot$ $\bot$ $\top$
$b$ $\bot$ $\top$ $\bot$ $\bot$ $c$ $\top$ $\bot$ $\bot$ $\bot$ $d$ $\bot$
$\bot$ $\top$ $\bot$

$\phantom{h_{\\{y\\}}\circ\pi_{xy}:}\mathllap{h_{\\{y\\}}\circ\pi_{xy}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\bot$ $\top$ $\bot$ $\bot$
$b$ $\bot$ $\bot$ $\bot$ $\top$ $c$ $\top$ $\bot$ $\bot$ $\bot$ $d$ $\bot$
$\bot$ $\top$ $\bot$
$\quad\phantom{h_{\\{y\\}}\circ\pi_{yx}:}\mathllap{h_{\\{y\\}}\circ\pi_{yx}:}\;$
$A$ $P$ $Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\top$ $\bot$ $\bot$ $\bot$
$b$ $\bot$ $\bot$ $\top$ $\bot$ $c$ $\bot$ $\top$ $\bot$ $\bot$ $d$ $\bot$
$\bot$ $\bot$ $\top$

$\phantom{h_{\\{y\\}}\circ\pi_{xy}:}\mathllap{h_{X}\circ\pi_{xy}:}\;$ $A$ $P$
$Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\bot$ $\top$ $\top$ $\bot$ $b$
$\top$ $\bot$ $\bot$ $\top$ $c$ $\top$ $\top$ $\bot$ $\bot$ $d$ $\bot$ $\bot$
$\top$ $\top$
$\quad\phantom{h_{\\{y\\}}\circ\pi_{yx}:}\mathllap{h_{X}\circ\pi_{yx}:}\;$ $A$
$P$ $Q$ $\neg P$ $\neg Q$ $X^{X^{X^{X}}}$$a$ $\top$ $\bot$ $\bot$ $\top$ $b$
$\bot$ $\top$ $\top$ $\bot$ $c$ $\top$ $\top$ $\bot$ $\bot$ $d$ $\bot$ $\bot$
$\top$ $\top$

Thus, we conclude that $\pi_{xy}\equiv\pi_{yx}$ and due to
$\pi_{xy}\not\mathrel{\cong}\pi_{yx}$, this shows that for finite
$\mathsf{PosBool}[X]$-interpretations, elementary equivalence does not
necessarily imply isomorphism. Moreover, similar examples can be constructed
for any distributive lattice semiring $K$ thanks to the universal property of
$\mathsf{PosBool}[X]$, by assigning $r,s\in K$ to the variables $x,y$:

$\pi_{rs}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0$ $s$ $r$ $0$ $b$ $r$ $0$
$0$ $s$ $c$ $s$ $r$ $0$ $0$ $d$ $0$ $0$ $s$ $r$
$\quad\quad\quad\pi_{sr}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $s$ $0$ $0$
$r$ $b$ $0$ $r$ $s$ $0$ $c$ $r$ $s$ $0$ $0$ $d$ $0$ $0$ $r$ $s$

Clearly, $\pi_{rs}\equiv\pi_{sr}$ holds as above, and the only requirement for
$\pi_{rs}\not\mathrel{\cong}\pi_{sr}$ is that $r$ and $s$ must be distinct.
This yields the following theorem.

######  Theorem 4.7.

For any distributive lattice semiring $K$ with at least three elements, there
is a pair of finite $K$-interpretations $\pi_{rs},\pi_{sr}$ over a universe
with four elements and a signature with two unary relation symbols such that
$\pi_{rs}\equiv\pi_{sr}$, but $\pi_{rs}\not\mathrel{\cong}\pi_{sr}$.

Note that the two $K_{4}$-interpretations $\pi_{PQ}$ and $\pi_{QP}$ from the
opening example of this section can be shown to be elementarily equivalent
using a similar technique as above. In fact, the above theorem even shows that
the opening example was not minimal and a counterexample with only three
semiring elements in $K_{3}=\\{0,1,2\\}$ exists.

We shall strengthen the result from Theorem 4.7 to the class of all fully
idempotent semirings by simply regarding $\pi_{xy}$ and $\pi_{yx}$ as
$\mathbb{W}[X]$-interpretations instead of
$\mathsf{PosBool}[X]$-interpretations. However, the proof that
$\pi_{xy}\equiv\pi_{yx}$ becomes more involved, since a diagonal separating
set for $\mathbb{W}[X]$ into $\mathbb{B}$ does not exist. Nevertheless, a
suitable separating set can be obtained by exploiting homomorphisms into
$\mathbb{W}[X]$ itself. Consider any permutation $\sigma\colon X\to X$ of the
variables. Surely, it induces an automorphism $h_{\sigma}$ of $\mathbb{W}[X]$.
In the previous example, if $\sigma$ swaps the variables $x$ and $y$, then
applying $h_{\sigma}$ to $\pi_{xy}$ yields an interpretation that is
isomorphic to $\pi_{yx}$, as illustrated below.

$(h_{\sigma}\circ\pi_{xy}):\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0$ $x$
$y$ $0$ $b$ $y$ $0$ $0$ $x$ $c$ $x$ $y$ $0$ $0$ $d$ $0$ $0$ $x$ $y$
$\quad\quad\quad\pi_{yx}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $y$ $0$ $0$
$x$ $b$ $0$ $x$ $y$ $0$ $c$ $x$ $y$ $0$ $0$ $d$ $0$ $0$ $x$ $y$

With this insight, we can construct a suitable separating set
$S\subseteq\operatorname{Hom}^{2}(\mathbb{W}[X],\mathbb{W}[X])$, starting with
the pair $(h_{\sigma},h_{\operatorname{id}})\in S$. This pair alone does not
separate $\mathbb{W}[X]$, since we have $x\neq y$ in $\mathbb{W}[X]$, but
$h_{\sigma}(x)=y=h_{\operatorname{id}}(y)$. Hence, we add more homomorphisms
by annihilating some variables, similarly to the construction for
$\mathsf{PosBool}[X]$ in Lemma 4.2. Fixing a permutation $\sigma\colon X\to
X$, we want to construct a homomorphism $h_{\sigma}^{Y}$ that annihilates all
variables in $X\setminus Y$ and permutes the variables in $Y$. Observe that
for each $x\in Y$ there is a minimal number $r(x)\geq 1$ such that
$\sigma^{r(x)}(x)\in Y$. Formally, we define $\sigma^{Y}\colon X\to
Y\cup\\{0\\}$ by setting $\sigma^{Y}(x)\coloneqq\sigma^{r(x)}(x)$ for $x\in
Y$, and $\sigma^{Y}(x)\coloneqq 0$ for $x\in X\setminus Y$. Note that
$\sigma^{Y}$ induces a homomorphism
$h_{\sigma}^{Y}\colon\mathbb{W}[X]\to\mathbb{W}[X]$.

######  Lemma 4.8.

$S\coloneqq\\{(h_{\sigma}^{Y},h_{\operatorname{id}}^{Y})\mid Y\subseteq
X\\}\subseteq\operatorname{Hom}^{2}(\mathbb{W}[X],\mathbb{W}[X])$ is a
separating set of homomorphism pairs.

######  Proof 4.9.

Suppose that $p\neq q$ for a pair $p,q\in\mathbb{W}[X]$. A monomial in
$\mathbb{W}[X]$ can be identified with the set of its variables. Thus, without
loss of generality, there is some $Y\subseteq X$ with $Y\in p$ and $Y\notin
q$. Surely, $h_{\sigma}^{Y}(p)$ contains the monomial $h_{\sigma}^{Y}(Y)=Y$,
but $h_{\operatorname{id}}^{Y}(q)$ only contains monomials from $q$, hence it
does not contain $Y$ and $h_{\sigma}^{Y}(p)\neq h_{\operatorname{id}}^{Y}(q)$.

Before applying the reduction technique to obtain $\pi_{xy}\equiv\pi_{yx}$
from Corollary 4.6, it only remains to show that
$(h_{\sigma}^{Y}\circ\pi_{xy})\equiv(h_{\operatorname{id}}^{Y}\circ\pi_{yx})$
for all $Y\subseteq X\coloneqq\\{x,y\\}$. Since we have already illustrated
$(h_{\sigma}^{X}\circ\pi_{xy})\mathrel{\cong}(h_{\operatorname{id}}^{X}\circ\pi_{yx})$
above, we only need to consider the cases where $Y\subsetneq X$. But then, at
most one variable is contained in $Y$ and the remaining variables are
annihilated by $h_{\sigma}^{Y}$ and $h_{\operatorname{id}}^{Y}$, thus
$(h_{\sigma}^{Y}\circ\pi_{xy})\mathrel{\cong}(h_{\operatorname{id}}^{Y}\circ\pi_{yx})$
clearly follows. The reduction technique then implies that
$\pi_{xy}\equiv\pi_{yx}$ on $\mathbb{W}[X]$, which can naturally be lifted to
all fully idempotent semirings thanks to the universal property.

######  Theorem 4.10.

For any fully idempotent semiring $K$ with at least three elements, there is a
pair of finite $K$-interpretations $\pi_{rs},\pi_{sr}$ over a universe with
four elements and a signature with two unary relation symbols such that
$\pi_{rs}\equiv\pi_{sr}$, but $\pi_{rs}\not\mathrel{\cong}\pi_{sr}$.

In conclusion, the proof of $\pi_{xy}\equiv\pi_{yx}$ on $\mathsf{PosBool}[X]$
illustrates how elementary equivalence in semiring semantics can be reduced to
elementary equivalence on $\mathbb{B}$ by completely decomposing
$\mathsf{PosBool}[X]$ to $\mathbb{B}$ with homomorphisms. Moreover, the proof
of elementary equivalence on $\mathbb{W}[X]$ shows that it may even pay off to
use separating sets of homomorphisms from $\mathbb{W}[X]$ to $\mathbb{W}[X]$
itself.

##  5 Characteristic sentences

The results of the previous section raise the question whether it is possible
to construct a similar example of non-isomorphic, but elementarily equivalent
interpretations also for the most general semiring $\mathbb{N}[X]$, and lift
it to all commutative semirings with at least three elements. In order to show
that this is not possible, we draw inspiration from classical semantics, where
for each finite $\tau$-structure $\mathfrak{A}$ with universe
$A=\\{a_{1},\dots,a_{n}\\}$ one can construct a _characteristic sentence_
$\chi_{\mathfrak{A}}$ such that $\mathfrak{B}\models\chi_{\mathfrak{A}}$ if,
and only if, $\mathfrak{A}\mathrel{\cong}\mathfrak{B}$. The characteristic
sentence is explicitly defined as

$\displaystyle\chi_{\mathfrak{A}}$ $\displaystyle\coloneqq\exists
x_{1}\ldots\exists
x_{n}(\varphi(\overline{x})\land\psi(\overline{x}))\quad\text{with}$
$\displaystyle\varphi(\overline{x})$ $\displaystyle\coloneqq\bigwedge_{1\leq
i<j\leq n}x_{i}\neq x_{j}\land\forall y\bigvee_{i\leq
n}y=x_{i}\quad\text{and}\quad\psi(\overline{x})\coloneqq\bigwedge\\{L(\overline{x})\in\operatorname{\mathrm{Lit}}_{n}(\tau)\mid\mathfrak{A}\models
L(\overline{a})\\}.$

The subformula $\varphi(\overline{x})$ of this sentence asserts that the
universe has precisely $n$ elements assigned to the variables $\overline{x}$.
Since $\varphi(\overline{x})$ uses only equalities and inequalities it can be
used as-is for semiring semantics in any semiring.

######  Lemma 5.1.

For every $K$-interpretation
$\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to K$ into an arbitrary
semiring $K$ and every tuple $\overline{b}=(b_{1},\dots,b_{n})$, we have that
$\pi_{B}\llbracket\varphi(\overline{b})\rrbracket=1$ if
$B=\\{b_{1},\dots,b_{n}\\}$ and $b_{i}\neq b_{j}$ for $i\neq j$, and
$\pi_{B}\llbracket\varphi(\overline{b})\rrbracket=0$, otherwise.

######  Proof 5.2.

Semiring interpretations evaluate equalities and inequalities to 0 and 1, so

$\pi_{B}\llbracket\varphi(\overline{b})\rrbracket=\prod_{i<j}\pi_{B}\llbracket
b_{i}\neq b_{j}\rrbracket\cdot\prod_{b\in B}\bigl{(}\sum_{i\leq
n}\pi_{B}\llbracket b=b_{i}\rrbracket\bigr{)}$

evaluates to 1 if $b_{1},\dots,b_{n}$ is a distinct enumeration of all
elements of $B$, and to 0 otherwise.

On the other side, $\psi(\overline{a})$ is the conjunction of all true
literals in $\mathfrak{A}$. Since $\mathfrak{A}$ satisfies precisely one
literal out of each pair of opposing literals $L$ and $\overline{L}$, it is
clear that $\psi(\overline{a})$ describes $\mathfrak{A}$ up to isomorphism.
However, this approach does not lift to arbitrary semiring interpretations
$\pi_{A}$, since different literals in $\pi_{A}$ may have different non-zero
values, but conjunctions are interpreted as products, and it is in general
impossible to trace the result back to the contributions of the literals.

###  5.1 The Viterbi semiring

The Viterbi semiring $\mathbb{V}=([0,1]_{\mathbb{R}},\max,\cdot,0,1)$ is used
in confidence analysis, probabilistic parsing, and Hidden Markov Models (see
[7, 9]). It is isomorphic to the tropical semiring
$\mathbb{T}=(\mathbb{R}_{+}^{\infty},\min,+,\infty,0)$, used for instance for
cost analysis and performance evaluation, via $x\mapsto e^{-x}$. Hence, all
results that we establish for the Viterbi semiring also hold for the tropical
semiring. We can illustrate the shortcomings of the characteristic sentences
in their classical form by very simple $\mathbb{V}$-interpretations with one
element.

$\pi_{19}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0.1$ $0.9$ $0$ $0$
$\quad\quad\quad\pi_{91}:\quad$ $A$ $P$ $Q$ $\neg P$ $\neg Q$ $a$ $0.9$ $0.1$
$0$ $0$

They are clearly not isomorphic, but trying to construct $\chi_{19}$ from
$\pi_{19}$ as above would yield $\chi_{19}=\exists x(\varphi(x)\land\psi(x))$
with $\psi(x)=Px\land Qx$, hence
$\pi_{19}\llbracket\chi_{19}\rrbracket=0.1\cdot 0.9=0.9\cdot
0.1=\pi_{91}\llbracket\chi_{19}\rrbracket$.

However, under semiring semantics, and especially on the Viterbi semiring
$\mathbb{V}$, multiplication need not be idempotent; hence we can hope to
distinguish two interpretations by simply repeating one of the literals. In
the given example, we can set $\psi(x)\coloneqq Px\land(Qx)^{2}$, which is
short for $Px\land Qx\land Qx$, to obtain
$\pi_{19}\llbracket\chi_{19}\rrbracket=0.1\cdot 0.9^{2}\neq 0.9\cdot
0.1^{2}=\pi_{91}\llbracket\chi_{19}\rrbracket$. We now generalise this idea to
arbitrary finite $\mathbb{V}$-interpretations. We shall associate with every
finite $\mathbb{V}$-interpretation
$\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ and every
$\varepsilon\in\mathbb{R}^{+}$ a characteristic sentence

$\chi_{\pi_{A},\varepsilon}\coloneqq\exists x_{1}\ldots\exists
x_{n}(\varphi(\overline{x})\land\psi_{\varepsilon}(\overline{x})),$

with $n\coloneqq|A|$ and $\varphi(x)$ as before, but a more involved
construction of $\psi_{\varepsilon}(\overline{x})$:

Let $\overline{a}=(a_{1},\ldots,a_{n})$ be some fixed order on $A$ and
$L_{1}(\overline{a}),\ldots,L_{k}(\overline{a})$ an arbitrary enumeration of
the “true” literals in $\operatorname{\mathrm{Lit}}_{A}(\tau)$ with
$\pi_{A}(L_{i}(\overline{a}))\neq 0$. Further, fix a sequence
$f(1),\dots,f(k)$ of “exponents” in ${\mathbb{N}}$, where $f(1)=1$ and
$f(i+1)$ is chosen large enough so that

$(*)\quad\quad\quad(1-\varepsilon)^{f(i+1)}<\varepsilon^{f(1)+\dots+f(i)}.$

Then, put
$\psi_{\varepsilon}(\overline{x})\coloneqq\bigwedge_{i=1}^{k}L_{i}(\overline{x})^{f(i)}$,
where “exponentiation” denotes repetition of a literal.

The idea is that $\chi_{\pi_{A},\varepsilon}$ should characterise $\pi_{A}$ up
to isomorphism by repeating the literals in $\psi_{\varepsilon}(\overline{x})$
“sufficiently often” so that the contribution of each literal can be
distinguished and changing the value for one literal surely alters the final
value of $\psi_{\varepsilon}(\overline{x})$. Since the elements of
$\mathbb{V}$ are from $[0,1]_{\mathbb{R}}$, the values of the literals can
change by an arbitrarily small amount, hence the “exponents” $f(i)$ must
depend on the “smallest possible change” $\varepsilon$. This intuition is
formalised as follows.

######  Proposition 5.3.

Let $\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ and
$\pi_{B}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to\mathbb{V}$ be two
finite, model-defining $\mathbb{V}$-interpretations, which induce the finite
set of values

$V\coloneqq\\{\pi_{A}(L)\mid
L\in\operatorname{\mathrm{Lit}}_{A}(\tau)\\}\cup\\{\pi_{B}(L)\mid
L\in\operatorname{\mathrm{Lit}}_{B}(\tau)\\}.$

Then, for every $\varepsilon\in\mathbb{R}$ bounded by
$0<\varepsilon\leq\min\\{|r-s|\mid r,s\in V,r\neq s\\}$, we have that
$\pi_{A}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket=\pi_{B}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket$
implies $\pi_{A}\mathrel{\cong}\pi_{B}$.

######  Proof 5.4.

Assume
$\pi_{A}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket=\pi_{B}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket$.
By construction, $\pi_{A}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket>0$, so
$\pi_{B}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket>0$ as well. By Lemma
5.1, together with the fact that the existential quantifiers $\exists
x_{1}\ldots\exists x_{n}$ in $\chi_{\pi_{A},\varepsilon}$ are interpreted as
$\max$ in the Viterbi semiring $\mathbb{V}$, this implies that $|A|=|B|$, and
that we have enumerations $\overline{a}=(a_{1},\ldots,a_{n})$ and
$\overline{b}=(b_{1},\ldots,b_{n})$ of the elements of $A$ and $B$, such that

$\pi_{A}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket=\pi_{A}\llbracket\psi_{\varepsilon}(\overline{a})\rrbracket=\pi_{B}\llbracket\psi_{\varepsilon}(\overline{b})\rrbracket=\pi_{B}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket.$

Recall that
$\pi_{A}\llbracket\psi_{\varepsilon}(\overline{a})\rrbracket=\prod_{i=1}^{k}\pi_{A}(L_{i}(\overline{a}))^{f(i)}>0$,
hence $\pi_{A}(L_{1}(\overline{a})),\dots,\pi_{A}(L_{k}(\overline{a}))$ are
all positive. Accordingly,
$\pi_{B}\llbracket\psi_{\varepsilon}(\overline{b})\rrbracket=\prod_{i=1}^{k}\pi_{B}(L_{i}(\overline{b}))^{f(i)}>0$,
so that $\pi_{B}(L_{1}(\overline{b})),\dots,\pi_{B}(L_{k}(\overline{b}))$ are
positive as well. Given that $\pi_{A}$ and $\pi_{B}$ share the same signature
and universe size, any permutations $\overline{a}$, $\overline{b}$ of their
elements yield the same number of positive literals, which is $k$ by
definition. We infer that all remaining literals in both interpretations are
mapped to zero. Hence, for $i=1,\dots,k$, let
$r_{i}:=\pi_{A}(L_{i}(\overline{a}))>0$ and
$s_{i}:=\pi_{B}(L_{i}(\overline{b}))>0$ be the values of the positive
literals, then it only remains to show that $r_{i}=s_{i}$ for all $i\leq k$ in
order to conclude that $\overline{a}\mapsto\overline{b}$ is indeed an
isomorphism from $\pi_{A}$ to $\pi_{B}$.

Towards a contradiction, assume that this is not the case and let $j$ be the
maximal index among $1,\dots,k$ with $r_{j}\neq s_{j}$. We can assume that
$r_{j}<s_{j}$. Since the difference between the two values is at least
$\varepsilon$ and since $s_{j}\leq 1$ it follows that $r_{j}\leq
s_{j}-\varepsilon\leq s_{j}-\varepsilon s_{j}=(1-\varepsilon)s_{j}$. Further,
we have $\varepsilon\leq s_{i},r_{i}\leq 1$ for all $i$. It follows that

$r_{1}^{f(1)}\cdots r_{j}^{f(j)}\leq
r_{j}^{f(j)}\leq(1-\varepsilon)^{f(j)}s_{j}^{f(j)}\;\stackrel{{\scriptstyle*}}{{<}}\;\varepsilon^{f(1)+\dots+f(j-1)}\cdot
s_{j}^{f(j)}\leq s_{1}^{f(1)}\cdots s_{j}^{f(j)}.$

However, since $r_{i}=s_{i}$ for $i=j+1,\dots,k$, this would imply that

$\pi_{A}\llbracket\psi_{\varepsilon}(\overline{a})\rrbracket=\prod_{i\leq
k}r_{i}^{f(i)}\neq\prod_{i\leq
k}s_{i}^{f(i)}=\pi_{B}\llbracket\psi_{\varepsilon}(\overline{b})\rrbracket$

and hence
$\pi_{A}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket\neq\pi_{B}\llbracket\chi_{\pi_{A},\varepsilon}\rrbracket$.

Notice that none of the sentences $\chi_{\pi_{A},\varepsilon}$ characterises
$\pi_{A}$ alone, but the countable set
$X_{\pi_{A}}\coloneqq\\{\chi_{\pi_{A},\varepsilon}\mid\varepsilon\in\mathbb{Q}^{+}\\}$
does so. No infinite $\mathbb{V}$-interpretation $\pi_{B}$ agrees with
$\pi_{A}$ on any of the $\varepsilon$-characteristic sentences
$\chi_{\pi_{A},\varepsilon}$ due to $\varphi(\overline{x})$, whereas for each
finite $\mathbb{V}$-interpretation $\pi_{B}$, one can calculate an
$\varepsilon\in\mathbb{Q}$ to apply the proposition just proved.

######  Theorem 5.5.

For finite $\mathbb{V}$-interpretations $\pi_{A}$ and $\pi_{B}$,
$\pi_{A}\equiv\pi_{B}$ implies $\pi_{A}\mathrel{\cong}\pi_{B}$.

As a consequence, there are indeed interesting semirings beyond the Boolean
semiring $\mathbb{B}$, where elementary equivalence implies isomorphism on
finite interpretations.

###  5.2 Finite axiomatisability

The characteristic set $X_{\pi_{A}}$ raises the question whether a finite set
of sentences suffices to characterise a $\mathbb{V}$-interpretation $\pi_{A}$.
We will answer this question positively using two observations. By Proposition
5.3, we observe that $\chi_{\pi_{A},\varepsilon}$ characterises $\pi_{A}$ up
to isomorphism inside the class of $\mathbb{V}$-interpretations that only use
values in $V=\\{\pi_{A}(L)\mid L\in\operatorname{\mathrm{Lit}}_{A}(\tau)\\}$,
with $\varepsilon\coloneqq\min\\{|r-s|\mid r,s\in V,r\neq s\\}$. Hence,
$\pi_{A}$ can be characterised by adding sentences to ensure that no values
outside of $V$ are used.

We will show that this is possible by building sentences that fix particular
values $\pi_{A}(L)$.

######  Definition 5.6.

Let $\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ be a finite
$\mathbb{V}$-interpretation over a universe $A$ with $n$ elements and
$\varphi(\overline{x})\in{\rm FO}(\tau)$ a formula with $k\in\mathbb{N}$ free
variables. The sequence $(s_{\pi,\varphi}^{i})_{1\leq i\leq n^{k}}$ is defined
as the non-increasingly sorted sequence of the values
$\pi\llbracket\varphi(\overline{a})\rrbracket$ for $\overline{a}\in A^{k}$.

In particular, $s_{\pi,\varphi}^{1}$ is the largest possible value
$\pi\llbracket\varphi(\overline{a})\rrbracket$; further,
$s_{\pi,\varphi}^{2}\leq s_{\pi,\varphi}^{1}$ is either the second largest
one, or equal to $s_{\pi,\varphi}^{1}$ if the maximal value is shared by two
distinct tuples $\overline{a},\overline{b}\in A^{k}$, and so on. We construct
a series of sentences that fix the values $(s_{\pi,\varphi}^{i})_{1\leq i\leq
n^{k}}$.

######  Lemma 5.7 (Sorting Lemma).

For $\varphi(\overline{x})\in{\rm FO}(\tau)$ with $k$ free variables and
$1\leq i\leq n^{k}$, let

$\psi_{\varphi}^{i}\coloneqq\exists\overline{x}_{1}\ldots\exists\overline{x}_{i}\Bigl{(}\bigwedge_{1\leq
j<\ell\leq
i}\overline{x}_{j}\neq\overline{x}_{\ell}\land\bigwedge_{j=1}^{i}\varphi(\overline{x}_{j})\Bigr{)}$

where $\overline{x}_{1},\ldots\overline{x}_{i}$ are $k$-tuples of variables.
Then, for any $\mathbb{V}$-interpretation
$\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ over a universe
with $n$ elements, we have that

$\pi\llbracket\psi_{\varphi}^{i}\rrbracket=\prod_{1\leq j\leq
i}s_{\pi,\varphi}^{j}\quad\text{for }1\leq i\leq n.$

######  Proof 5.8.

Recall that existential quantifiers are interpreted as $\max$ on $\mathbb{V}$.
Due to monotonicity of multiplication, the maximum
$\pi\llbracket\psi_{\pi,\varphi}^{i}\rrbracket$ is achieved by picking the $i$
pairwise distinct tuples $\overline{a}_{1},\ldots,\overline{a}_{i}$ that yield
the largest values
$\pi\llbracket\varphi(\overline{a}_{j})\rrbracket=s_{\pi,\varphi}^{j}$ and
inserting them for $\overline{x}_{1},\ldots,\overline{x}_{i}$. Clearly, this
yields $\pi\llbracket\psi_{\varphi}^{i}\rrbracket=\prod_{1\leq j\leq
i}s_{\pi,\varphi}^{j}$.

By observing that $\mathbb{V}$ is cancellative, i.e. $ab=ac$ implies $b=c$ for
all $a,b,c\in\mathbb{V}$ with $a\neq 0$, we may disentangle the products
$\prod_{1\leq j\leq i}s_{\pi,\varphi}^{j}$ to draw the following conclusion.

######  Corollary 5.9.

Let $\varphi(\overline{x})$ be as above, and consider two
$\mathbb{V}$-interpretations
$\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ and
$\pi^{\prime}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to\mathbb{V}$ with
$|A|=|B|=n$. If $\pi$ and $\pi^{\prime}$ agree on
$\Psi\coloneqq\\{\psi_{\varphi}^{i}\mid 1\leq i\leq n^{k}\\}$, then
$s_{\pi,\varphi}^{i}=s_{\pi^{\prime},\varphi}^{i}$ for all $1\leq i\leq
n^{k}$. In other words, the values
$\pi\llbracket\varphi(\overline{a})\rrbracket$ for $\overline{a}\in A^{k}$ and
$\pi^{\prime}\llbracket\varphi(\overline{b})\rrbracket$ for $\overline{b}\in
B^{k}$ are the same, up to permutation.

If $R\in\tau$ is a $k$-ary relation, pick $\varphi(\overline{x})\coloneqq
R\overline{x}$ and construct $\Psi_{R}\coloneqq\\{\psi_{R\overline{x}}^{i}\mid
1\leq i\leq n^{k}\\}$ according to the Sorting Lemma. Similarly, construct
$\Psi_{\neg R}$ from $\varphi(\overline{x})\coloneqq\neg R\overline{x}$. Then,
define

$\Psi_{\tau}\coloneqq\bigcup_{R\in\tau}\Psi_{R}\cup\bigcup_{R\in\tau}\Psi_{\neg
R}.$

Clearly, any two $\mathbb{V}$-interpretations over $\tau$ that agree on
$\Psi_{\tau}$ use the same set of values from $\mathbb{V}$. Putting this
together with the characteristic sentences $\chi_{\pi_{A},\varepsilon}$ from
Proposition 5.3 provides a finite axiomatisation of any
$\mathbb{V}$-interpretation.

######  Theorem 5.10.

Let $\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ be a finite
$\mathbb{V}$-interpretation. Then,
$\Psi_{\tau}\cup\\{\chi_{\pi,\varepsilon}\\}$ is a finite axiomatisation of
$\pi$ up to isomorphism, where $\varepsilon\coloneqq\min\\{|r-s|\mid
r,s\in\pi(\operatorname{\mathrm{Lit}}_{A}(\tau)),r\neq s\\}$.

######  Proof 5.11.

Let $\pi^{\prime}\colon\operatorname{\mathrm{Lit}}_{B}(\tau)\to\mathbb{V}$
agree with $\pi$ on all sentences in
$\Psi_{\tau}\cup\\{\chi_{\pi,\varepsilon}\\}$. Due to the construction of
$\chi_{\pi,\varepsilon}$, $\pi^{\prime}$ is finite and $|A|=|B|$. Since
$\pi^{\prime}$ agrees with $\pi$ on $\Psi_{\tau}$, we have $\\{\pi(L)\mid
L\in\operatorname{\mathrm{Lit}}_{A}(\tau)\\}=\\{\pi^{\prime}(L)\mid
L\in\operatorname{\mathrm{Lit}}_{B}(\tau)\\}$. Thus, we can invoke Proposition
5.3 by observing that $V=\pi(\operatorname{\mathrm{Lit}}_{A}(\tau))$ and
conclude that
$\pi\llbracket\chi_{\pi,\varepsilon}\rrbracket=\pi^{\prime}\llbracket\chi_{\pi,\varepsilon}\rrbracket$
implies $\pi\mathrel{\cong}\pi^{\prime}$.

Under classical semantics, any finite axiom system $\Phi\subseteq{\rm
FO}(\tau)$ can be collapsed to a single axiom $\psi\coloneqq\bigwedge\Phi$,
but this is not the case in semiring semantics. To illustrate this, we shall
show that there are $\mathbb{V}$-interpretations that cannot be axiomatised up
to isomorphism by a single sentence.

######  Proposition 5.12.

There exist $\mathbb{V}$-interpretations
$\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ such that, for
every sentence $\psi\in{\rm FO}(\tau)$, there exists an interpretation
$\pi^{\prime}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{V}$ such
that $\pi\not\mathrel{\cong}\pi^{\prime}$, but
$\pi\llbracket\psi\rrbracket=\pi^{\prime}\llbracket\psi\rrbracket$.

######  Proof 5.13.

Take an interpretation with just two atoms $Pa$ and $Qa$ and with values
$\pi(Pa)=p$ and $\pi(Qa)=q$ such that $0<p,q<1$ are multiplicatively
independent real numbers, i.e. there are no solutions $k,\ell\in{\mathbb{Z}}$
to the equation $p^{k}q^{\ell}=1$, except $k=\ell=0$. Let $\pi_{\mathbb{B}}$
be the corresponding $\mathbb{B}[x,y]$-interpretation, with
$\pi_{\mathbb{B}}(Pa)=x$ and $\pi_{\mathbb{B}}(Qa)=y$. A sentence $\psi\in{\rm
FO}$ is evaluated under $\pi_{\mathbb{B}}$ to a polynomial
$\pi_{\mathbb{B}}\llbracket\psi\rrbracket\in\mathbb{B}[x,y]$, and by the
universal property for idempotent semirings, the homomorphism
$h\colon\mathbb{B}[x,y]\to\mathbb{V}$ induced by $h(x)=p$ and $h(y)=q$ maps
$\pi_{\mathbb{B}}\llbracket\psi\rrbracket$ to $\pi\llbracket\psi\rrbracket$.
Writing $\pi_{\mathbb{B}}\llbracket\psi\rrbracket$ as a sum of monomials
$m=x^{i}y^{j}$, we conclude that $\pi\llbracket\psi\rrbracket=p^{i}q^{j}$ is
the maximal value $m(p,q)$ for the monomials $m$ occuring in
$\pi_{\mathbb{B}}\llbracket\psi\rrbracket$. Since $p,q$ are multiplicatively
independent, no other monomial can take the same value, i.e.
$m^{\prime}(p,q)<m(p,q)$ for all other monomials $m^{\prime}$ in
$\pi_{\mathbb{B}}\llbracket\psi\rrbracket$. We now can certainly find a value
$r\neq p$ that is sufficiently close to $p$, and a value $s$ such that
$r^{i}s^{j}=p^{i}q^{j}$, i.e. $m(r,s)=m(p,q)$, but $m^{\prime}(r,s)<m(r,s)$
for all other monomials $m^{\prime}$ in
$\pi_{\mathbb{B}}\llbracket\psi\rrbracket$. For the
$\mathbb{V}$-interpretation $\pi^{\prime}$ with $\pi^{\prime}(Pa)=r$ and
$\pi^{\prime}(Qa)=s$ this implies that
$\pi^{\prime}\llbracket\psi\rrbracket=r^{i}s^{j}=p^{i}q^{j}=\pi\llbracket\psi\rrbracket$,
but clearly, $\pi^{\prime}\not\mathrel{\cong}\pi$.

This result can be strengthened in many directions. It holds, in fact, for
almost all $\mathbb{V}$-interpretations, as long as they do not map all
literals to either 0 or 1. Further, we shall exploit the isomorphism of
$\mathbb{V}$ and $\mathbb{T}$ in order to prove explicit lower bounds on the
number of axioms that are needed to characterise an interpretation, depending
on the number of literals mapped to multiplicatively independent values.

###  5.3 Lower bound for axiomatisations of $\mathbb{T}$\- and
$\mathbb{V}$-interpretations

Recall that $\mathbb{V}=([0,1]_{\mathbb{R}},\max,\cdot,0,1)$ is isomorphic to
$\mathbb{T}=(R_{+}^{\infty},\min,+,\infty,0)$ via isomorphisms
$\sigma_{\mathbb{V}\to\mathbb{T}}(a)=-\log_{b}(a)$ for any fixed base
$b\in\mathbb{R}_{>1}$, and the corresponding inverse isomorphisms
$\sigma_{\mathbb{T}\to\mathbb{V}}(a)=b^{-a}$ for any fixed
$b\in\mathbb{R}_{>1}$. We formulate our result in terms of $\mathbb{T}$.

######  Theorem 5.14.

Let $\pi\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{T}$ be any
finite, model-defining $\mathbb{T}$-interpretation with $|A|=n$ and
$|\operatorname{\mathrm{Lit}}_{A}(\tau)|=2\ell$, such that its finite values
$\pi(\operatorname{\mathrm{Lit}}_{A}(\tau))\setminus\\{\infty\\}$ are linearly
independent over $\mathbb{Q}$. Then, for any set of sentences
$\Psi\subseteq{\rm FO}(\tau)$ with $|\Psi|<\ell$, there is an interpretation
$\pi^{\prime}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{T}$ such
that $\pi\llbracket\psi\rrbracket=\pi^{\prime}\llbracket\psi\rrbracket$ for
all $\psi\in\Psi$, but $\pi\not\mathrel{\cong}\pi^{\prime}$.

######  Proof 5.15.

Since $\pi$ is model-defining, there are $\ell$ literals $L$ in
$\operatorname{\mathrm{Lit}}_{A}(\tau)$ with $\pi(L)\neq\infty$, which we call
the positive literals. Choose $X\coloneqq\\{x_{1},\ldots,x_{\ell}\\}$ and
construct the $\mathbb{B}[X]$-interpretation
$\pi_{\mathbb{B}}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{B}[X]$
by assigning a unique variable to each of the positive literals. Clearly,
there is a homomorphism $h\colon\mathbb{B}[X]\to\mathbb{T}$ with
$h\circ\pi_{\mathbb{B}}=\pi$ induced by mapping each variable to the original
value $\pi(L)$ of the corresponding literal.

Enumerate $\Psi=\\{\psi_{1},\ldots,\psi_{j}\\}$ arbitrarily with $j<\ell$ and
construct the polynomials
$p_{i}\coloneqq\pi_{\mathbb{B}}\llbracket\psi_{i}\rrbracket\in\mathbb{B}[X]$
for $1\leq i\leq j$. By the fundamental property,
$\pi\llbracket\psi_{i}\rrbracket=h(p_{i})$ holds for $1\leq i\leq j$.

We assume without loss of generality that $p_{i}\neq 0$ for all $1\leq i\leq
j$, and we will construct $\pi^{\prime}$ with the same positive literals as
$\pi$. Thus, $p_{i}$ contains a monomial $m_{i}$ so that $h(m_{i})$ is minimal
among $\\{h(m):m\in p_{i}\\}$. This monomial is unique thanks to the linear
independence of the values of $\pi$, which guarantees that $h(m)\neq
h(m^{\prime})$ for $m\neq m^{\prime}$. Suppose for a contradiction that
$h(m)=h(m^{\prime})$. We may write

$h(m)=h\left(\prod_{i=1}^{\ell}x_{i}^{m(x_{i})}\right)=\sum_{i=1}^{\ell}m(x_{i})\cdot
h(x_{i}),$

which implies that $h(m)$ is a linear combination of the values of $\pi$. In
particular, $h(m)=h(m^{\prime})$ implies that $h(m-m^{\prime})=0$, hence
$m(x_{i})-m^{\prime}(x_{i})=0$ for all $1\leq i\leq j$ due to linear
independence.

We conclude that there is a sufficiently small $\varepsilon\in\mathbb{R}_{>0}$
such that changing the numbers $h(x_{i})$ by less than $\varepsilon$ does not
affect the monomial order. In other words, view the values
$\overline{v}\coloneqq(h(x_{1}),\ldots,h(x_{\ell}))\in\mathbb{R}_{\geq
0}^{\ell}$ as a vector and notice that any $\overline{w}\in\mathbb{R}_{\geq
0}^{\ell}$ with $|\overline{v}-\overline{w}|<\varepsilon$ preserves the
monomial order, so that if we construct
$h^{\prime}\colon\mathbb{B}[X]\to\mathbb{T}$ induced by
$h^{\prime}(x_{i})=w_{i}$ for $1\leq i\leq\ell$, we have $h(m)<h(m^{\prime})$
if, and only if, $h^{\prime}(m)<h^{\prime}(m^{\prime})$.

To complete the proof, it remains to ensure that $h^{\prime}(p_{i})=h(p_{i})$
stays the same for all $1\leq i\leq j$. By the above considerations, it
suffices to ensure that $h^{\prime}(m_{i})=h(m_{i})$ for the corresponding
maximal monomials $m_{1},\ldots,m_{j}$. Each of these monomials induces one
condition $h(m_{i})-h^{\prime}(m_{i})=0$, which translates to a linear
equation

$\displaystyle
h(m_{i})-h^{\prime}(m_{i})=\sum_{i=1}^{\ell}m_{i}(x_{i})(h(x_{i})-h^{\prime}(x_{i}))=\sum_{i=1}^{\ell}m_{i}(x_{i})\cdot(v_{i}-w_{i})=0$

on $(\overline{v}-\overline{w})$.

Since there are only $j<\ell$ equations and $\ell$ variables, the solution
space is at least one-dimensional, meaning that we can pick
$\overline{w}\neq\overline{v}$ adequately with
$|\overline{v}-\overline{w}|<\varepsilon$ to satisfy all equations and obtain
$h^{\prime}(p_{i})=h(p_{i})$ for all $1\leq i\leq j$. Note that due to linear
independence, none of the entries from $\overline{v}$ was zero, hence it is
possible to ensure that $\overline{w}$ only has positive entries. We thus can
pick $\pi^{\prime}\coloneqq h^{\prime}\circ\pi_{\mathbb{B}}$ with the desired
properties.

This result translates to $\mathbb{V}$ thanks to isomorphism. Linear
independence of values from $\mathbb{T}$ as $\mathbb{Q}$-vectors translates to
multiplicative independence of the corresponding values from $\mathbb{V}$.

###  5.4 The semirings $\mathbb{N}$ and $\mathbb{N}[X]$

We will now provide a similar analysis of axiomatisablity for the most general
semiring $\mathbb{N}[X]$ by taking a detour via $\mathbb{N}$. For the
construction of the characteristic sentences for $\mathbb{N}$, we shall need
the following combinatorial lemma.

######  Lemma 5.16.

For any two natural numbers $k,c$ with $c>1$, there exists a exponent $e$ such
that, for any two non-decreasing sequences $r_{1}\leq r_{2}\leq\dots\leq
r_{k}$ and $s_{1}\leq s_{2}\leq\dots\leq s_{k}$ of $k$ natural numbers, with
$r_{k},s_{k}<c$, the equation
$r_{1}^{e}+\cdots+r_{k}^{e}=s_{1}^{e}+\cdots+s_{k}^{e}$ implies that the two
sequences are the same, i.e. $r_{i}=s_{i}$ for all $i\leq k$.

######  Proof 5.17.

Choose $e$ large enough so that $(c/(c-1))^{e}>k$. Towards a contradiction,
assume that there are two _distinct_ sequences $r_{1}\leq r_{2}\leq\dots
r_{k}<c$ and $s_{1}\leq s_{2}\leq\dots s_{k}<c$ such that
$r_{1}^{e}+\cdots+r_{k}^{e}=s_{1}^{e}+\cdots+s_{k}^{e}$. Let $j$ be the
maximal index with $r_{j}\neq s_{j}$. Thanks to additive cancellation, we can
remove the summands with index $i>j$ to obtain that
$r_{1}^{e}+\cdots+r_{j}^{e}=s_{1}^{e}+\cdots+s_{j}^{e}$. By symmetry we can
assume that $r_{j}<s_{j}$. Since $s_{j}<c$, it follows that
$s_{j}>(c/(c-1))r_{j}$ and hence $s_{j}^{e}>k\cdot r_{j}^{e}$. But this
implies that

$r_{1}^{e}+\cdots+r_{j}^{e}\leq j\cdot r_{j}^{e}\leq k\cdot
r_{j}^{e}<s_{j}^{e}\leq s_{1}^{e}+\cdots+s_{j}^{e},$

contradicting the equation above.

######  Lemma 5.18.

Let $(r_{1},\ldots r_{k}),(s_{1},\ldots,s_{k})\in\mathbb{N}^{k}$ be strictly
bounded by $c$, that is $r_{i},s_{i}<c$ for all $i\leq k$. Then, there is an
exponent $e$ depending only on $c$ and $k$ such that

$\sum_{i=1}^{k}r_{i}^{e}=\sum_{i=1}^{k}s_{i}^{e}$

implies that there is a permutation $\sigma\in S_{k}$ such that
$r_{i}=s_{\sigma(i)}$ for all $1\leq i\leq k$.

######  Proof 5.19.

Sort both sequences non-decreasingly, that is, permute them with $\rho,\tau\in
S_{k}$ so that $r_{\rho(1)}\leq\ldots\leq r_{\rho(k)}$ and
$s_{\tau(1)}\leq\ldots\leq s_{\tau(k)}$. By the previous Lemma, there is a
suitable $e$ such that $r_{\rho(i)}=s_{\tau(i)}$ for all $i\leq k$. Then,
$\sigma\coloneqq\tau\circ\rho^{-1}$ is the desired permutation.

We are now ready to construct characteristic sentences for finite
$\mathbb{N}$-interpretations
$\pi_{A}\colon\operatorname{\mathrm{Lit}}_{A}(\tau)\to\mathbb{N}$. For
$n=|A|$, let $L_{1}(\overline{x}),\dots,L_{k}(\overline{x})$ be an enumeration
of all literals in $\operatorname{\mathrm{Lit}}_{n}(\tau)$. For any constant
$q\in\mathbb{N}$ we define the _$q$ -characteristic sentence_
$\chi_{\pi_{A},q}$ as

$\chi_{\pi_{A},q}\coloneqq\exists x_{1}\ldots\exists
x_{n}(\varphi(\overline{x})\land\psi_{q}(\overline{x}))^{e},\quad\text{with
}\psi_{q}(\overline{x})\coloneqq\bigvee_{i=1}^{k}q^{i-1}\cdot
L_{i}(\overline{x}),$

with $\varphi(\overline{x})$ as given before and $e$ is an exponent that
depends on $q,n$ and $\tau$, according to Lemma 5.18. The notation
$q^{i-1}\cdot L_{i}(\overline{x})$ denotes a disjunctive repetition of the
literal $L_{i}(\overline{x})$ for $q^{i-1}$ times.

The idea of this construction is similar to the one for the Viterbi semiring.
While $\varepsilon$-characteristic sentences work for
$\mathbb{V}$-interpretations where the differences of two distinct values are
at least $\varepsilon$, $q$-characteristic sentences work for
$\mathbb{N}$-interpretations with values less than $q$. With this in mind, we
can explain the construction of $\psi_{q}(\overline{x})$ as follows. If all
values in $\pi_{A}$ are less than $q$, we can picture the value

$\pi_{A}\llbracket\psi_{q}(\overline{a})\rrbracket=\sum_{i=1}^{k}q^{i-1}\pi_{A}(L_{i}(\overline{a})),$

to be in a number system with radix $q$, hence the values
$\pi_{A}(L_{i}(\overline{a}))$ can be seen as digits. Thus, it is immediately
clear that for any $\mathbb{N}$-interpretation $\pi_{B}$ with universe
enumerated by $\overline{b}$ and values less than $q$,
$\pi_{A}\llbracket\psi_{q}(\overline{a})\rrbracket=\pi_{B}\llbracket\psi_{q}(\overline{b})\rrbracket$
implies that $\overline{a}\xrightarrow{\sim}\overline{b}$ is an isomorphism
between $\pi_{A}$ and $\pi_{B}$, since the corresponding “digits”
$\pi_{A}(L_{i}(\overline{a}))$ and $\pi_{B}(L_{i}(\overline{b}))$ for each
$1\leq i\leq k$ have to be the same.

The only remaining problem is the fact that existential quantifiers $\exists
x_{1}\ldots\exists x_{n}$ from $\chi_{\pi_{A},q}$ are interpreted as a sum in
$\mathbb{N}$. Thus, the value $\pi_{A}\llbracket\chi_{\pi_{A},q}\rrbracket$ is
not induced by a single variable assignment $\overline{a}$. The exponent $e$
is used to separate the contributions of different variable assignments to the
sum on the basis of Lemma 5.18.

######  Theorem 5.20.

Let $\pi_{A}$ and $\pi_{B}$ are finite $\mathbb{N}$-interpretations with
values less than $q$. Then
$\pi_{A}\llbracket\chi_{\pi_{A},q}\rrbracket=\pi_{B}\llbracket\chi_{\pi_{A},q}\rrbracket$
implies that $\pi_{A}\mathrel{\cong}\pi_{B}$.

######  Proof 5.21.

Clearly, $\varphi(\overline{x})$ takes care of the number of elements, hence
we can assume $\overline{a}$ and $\overline{b}$ enumerate the universes of
$\pi_{A}$ and $\pi_{B}$. Now, we have

$\pi_{A}\llbracket\chi_{\pi_{A},q}\rrbracket=\sum_{\sigma\in
S_{n}}\pi_{A}\llbracket\psi_{q}(\sigma(\overline{a}))\rrbracket^{e}=\sum_{\sigma\in
S_{n}}\pi_{B}\llbracket\psi_{q}(\sigma(\overline{b}))\rrbracket^{e}=\pi_{B}\llbracket\chi_{\pi_{A},q}\rrbracket.$

Recall that $\psi_{q}(\overline{x})$ is constructed as a number with $k$
“digits”, where the digits are the values of the literals
$\pi_{A}(L_{i}(\overline{a}))$ and $\pi_{B}(L_{i}(\overline{b}))$, which are
bounded by $q$. Hence,
$\pi_{A}\llbracket\psi_{q}(\sigma(\overline{a}))\rrbracket$ and
$\pi_{B}\llbracket\psi_{q}(\sigma(\overline{b}))\rrbracket$ are less than
$c\coloneqq q^{k}$, which only depends on $q$, $n$ and $\tau$. By Lemma 5.18,
there is a sufficiently large $e$ so that $\sum_{\sigma\in
S_{n}}\pi_{A}\llbracket\psi_{q}(\sigma(\overline{a}))\rrbracket^{e}=\sum_{\sigma\in
S_{n}}\pi_{B}\llbracket\psi_{q}(\sigma(\overline{b}))\rrbracket^{e}$ implies
that both sums share the same summands. In particular, there are permutations
$\sigma_{A},\sigma_{B}\in S_{n}$ such that
$\pi_{A}\llbracket\psi_{c}(\sigma_{A}(\overline{a}))\rrbracket=\pi_{B}\llbracket\psi_{c}(\sigma_{B}(\overline{b}))\rrbracket$.

Thanks to the construction of $\psi_{c}(\overline{x})$, this yields
$\pi_{A}(L_{i}(\sigma_{A}(\overline{a}))=\pi_{B}(L_{i}(\sigma_{B}(\overline{b}))$
for all literals $L_{i}$ of $\operatorname{\mathrm{Lit}}_{n}(\tau)$. Thus,
$\sigma_{B}\circ(\overline{a}\mapsto\overline{b})\circ\sigma_{A}^{-1}$ is an
isomorphism from $\pi_{A}$ to $\pi_{B}$.

We can further use the $q$-characteristic sentences also for
$\mathbb{N}[X]$-interpretations instead of $\mathbb{N}$-interpretations. Let
$X_{k}=\\{x_{1},\ldots,x_{k}\\}$, and let $\mathbb{N}[X_{k}](C,n)$ denote the
set of polynomials $p\in\mathbb{N}[X_{k}]$ with coefficients less than $C$ and
exponents less than $n$. If we choose a suitable variable assignment
$X_{k}\to\mathbb{N}$, we can obtain a homomorphism that assigns unique values
to all polynomials in $\mathbb{N}[X_{k}](C,n)$.

######  Lemma 5.22.

The variable assignment $x_{i}\mapsto C^{n^{i-1}}$ for $1\leq i\leq k$ defines
a homomorphism $h\colon\mathbb{N}[X_{k}]\to\mathbb{N}$ which induces a
bijection from $\mathbb{N}[X_{k}](C,n)$ to
$\\{0,\ldots,c-1\\}\subseteq\mathbb{N}$ where $c\coloneqq C^{n^{k}}$.

######  Proof 5.23.

We proceed by induction on the number of variables $k\in\mathbb{N}$. The base
case $k=0$ is trivial, since
$\mathbb{N}[\varnothing]\mathrel{\cong}\mathbb{N}$ and the empty assignment
induces the corresponding isomorphism. For $k>0$, notice that
$\mathbb{N}[X_{k}]\mathrel{\cong}\mathbb{N}[X_{k-1}][x_{k}]$. Hence, each
$p\in\mathbb{N}[X_{k}](C,n)$ may be written as

$p=\sum_{i=0}^{n-1}q_{i}x_{k}^{i},\quad\text{where
}q_{i}\in\mathbb{N}[X_{k-1}](C,n).$

Thus, applying the induced homomorphism $h$ yields

$h(p)=\sum_{i=0}^{n-1}h(q_{i})h(x_{k})^{i}=\sum_{i=0}^{n-1}h^{\prime}(q_{i})(C^{n^{k-1}})^{i},$

where $h^{\prime}\colon\mathbb{N}[X_{k-1}]\to\mathbb{N}$ is induced by
$x_{i}\mapsto C^{n^{i-1}}$ for $1\leq i<k$. By induction hypothesis the
restriction $h^{\prime}|_{\mathbb{N}[X_{k-1}](C,n)}$ is a bijection from
$\mathbb{N}[X_{k-1}](C,n)$ to $\\{0,\ldots,C^{n^{k-1}}-1\\}$. Clearly, $h(p)$
may be seen as a number with $n$ digits
$h^{\prime}(q_{i})\in\\{0,\ldots,C^{n^{k-1}}-1\\}$ for $0\leq i<n$ in the
number system with radix $C^{n^{k-1}}$. Thus, any number in
$\\{0,\ldots,C^{n^{k}}-1\\}$ can be uniquely represented as $h(p)$ for
$p\in\mathbb{N}[X_{k}](C,n)$, which completes the proof.

######  Corollary 5.24.

For finite $\mathbb{N}[X]$-interpretations $\pi_{A}$ and $\pi_{B}$ whose
values are contained in $\mathbb{N}[X](C,n)$,
$\pi_{A}\llbracket\chi_{\pi_{A},c}\rrbracket=\pi_{B}\llbracket\chi_{\pi_{A},c}\rrbracket$
implies $\pi_{A}\mathrel{\cong}\pi_{B}$ with $c\coloneqq C^{n^{|X|}}$.

######  Proof 5.25.

Transform $\pi_{A}$ and $\pi_{B}$ to $\mathbb{N}$-interpretations
$\pi_{A}^{\prime}\coloneqq h\circ\pi_{A}$ and $\pi_{B}^{\prime}\coloneqq
h\circ\pi_{B}$ by applying the homomorphism from above. The fundamental
property yields
$\pi_{A}^{\prime}\llbracket\chi_{\pi_{A},c}\rrbracket=\pi_{B}^{\prime}\llbracket\chi_{\pi_{A},c}\rrbracket$.
Since $h|_{\mathbb{N}[X](C,n)}$ is a bijection from $\mathbb{N}[X](C,n)$ to
$\\{0,\ldots,c\\}$, the values of $\pi_{A}^{\prime}$ and $\pi_{B}^{\prime}$
are less than $c$, hence we can invoke Theorem 5.20 to conclude
$\pi_{A}^{\prime}\mathrel{\cong}\pi_{B}^{\prime}$. Now, the injectivity of $h$
on $\mathbb{N}[X](C,n)$ yields $\pi_{A}\mathrel{\cong}\pi_{B}$.

Similarly to the implications of Proposition 5.3 on the Viterbi semiring
$\mathbb{V}$, we conclude that finite $\mathbb{N}[X]$-interpretations
$\pi_{A}$ are characterised by a the set
$X_{\pi_{A}}\coloneqq\\{\chi_{\pi_{A},c}\mid c\in\mathbb{N},c>1\\}$ of
characteristic sentences. The obvious consequence is that no counterexamples
exist on $\mathbb{N}[X]$.

######  Theorem 5.26.

For finite $\mathbb{N}[X]$-interpretations $\pi_{A}$ and $\pi_{B}$,
$\pi_{A}\equiv\pi_{B}$ implies $\pi_{A}\mathrel{\cong}\pi_{B}$.

Note that the results from this section provide an insight into the properties
of semirings that facilitate the construction of characteristic sentences. We
shall use these observations to separate elementary equivalence from
isomorphism in semirings that break those properties.

##  6 Cancellation

One of the crucial properties for the characteristic sentences to work is
cancellation. We observe that $\mathbb{N}[X]$ and $\mathbb{N}$ allow additive
and multiplicative cancellation and $\mathbb{V}$ allows multiplicative
cancellation, that is, $ab=ac$ implies $b=c$ for all $a\neq 0$. Looking at
$\psi_{\varepsilon}(\overline{x})$, we notice that cancellation is important
to ensure that the contributions of all literals are preserved in a
conjunction. Our analysis will show that there are non-isomorphic but
elementary equivalent interpretations for a large class of semirings that
break cancellation.

######  Definition 6.1.

Let $K$ be an idempotent semiring. A witness that $K$ breaks cancellation is a
triple $a,b,c\in K\setminus\\{0\\}$ such that

$\displaystyle(1)\quad$ $\displaystyle a+b=a+c=a\quad\text{and}$
$\displaystyle(2)\quad$ $\displaystyle ab=ac,\text{ but }b\neq c.$

For any such triple, we define the following two non-isomorphic
$K$-interpretations.

$\pi_{b}:\quad$ $A$ $R$ $\neg R$ $d$ $a$ $0$ $e$ $b$ $0$
$\quad\quad\quad\pi_{c}:\quad$ $A$ $R$ $\neg R$ $d$ $a$ $0$ $e$ $c$ $0$

######  Lemma 6.2.

The $K$-interpretations $\pi_{b}$ and $\pi_{c}$ are elementarily equivalent.

######  Proof 6.3.

Consider the $\mathbb{B}[X]$ interpretation

$\pi:\quad$ $A$ $R$ $\neg R$ $d$ $x$ $0$ $e$ $y$ $0$

Let $h_{b},h_{c}\colon\mathbb{B}[X]\to K$ be the unique homomorphisms induced
by $x\mapsto a,y\mapsto b$ and $x\mapsto a,y\mapsto c$ respectively.
Obviously, $\pi_{b}=h_{b}\circ\pi$ and $\pi_{c}=h_{c}\circ\pi$, hence, for
each sentence $\psi\in{\rm FO}(\\{R\\})$, the fundamental property yields
$\pi_{b}\llbracket\psi\rrbracket=h_{b}(\pi\llbracket\psi\rrbracket)$ and
$\pi_{c}\llbracket\psi\rrbracket=h_{c}(\pi\llbracket\psi\rrbracket)$. In fact,
if we set $p\coloneqq\pi\llbracket\psi\rrbracket$, we have
$\pi_{b}\llbracket\psi\rrbracket=h_{b}(p)$ and
$\pi_{c}\llbracket\psi\rrbracket=h_{c}(p)$, hence both interpretations
evaluate the same polynomial $p$ under their own homomorphism.

It remains to show that $h_{b}(p)=h_{c}(p)$. The automorphism $\overline{h}$
of $\mathbb{B}[X]$ induced by swapping the variables $x$ and $y$ yields the
$\mathbb{B}[X]$-interpretation

$\overline{h}\circ\pi=\overline{\pi}:\quad$ $A$ $R$ $\neg R$ $d$ $y$ $0$ $e$
$x$ $0$

Clearly, $\pi\mathrel{\cong}\overline{\pi}$ by swapping $d$ and $e$, hence
$p=\pi\llbracket\psi\rrbracket=\overline{\pi}\llbracket\psi\rrbracket=\overline{h}(\pi\llbracket\psi\rrbracket)=\overline{h}(p)$.
In other words, $p$ is invariant under swapping variables, so for each pair
$i,j$ we have that $x^{i}y^{j}\in p$ if, and only if, $x^{j}y^{i}\in p$. In
particular, $x^{i}\in p\Leftrightarrow y^{i}\in p$ $(*)$.

Since $p$ is finite and all exponents are less than some $d\in\mathbb{N}$, we
may write $p$ as

$p=\sum_{i,j<d,x^{i}y^{j}\in p}x^{i}y^{j}=\sum_{i<d,x^{i}\in
p}x^{i}+\sum_{j<d,y^{j}\in p}y^{j}+\sum_{0<i,j<d,x^{i}y^{j}\in p}x^{i}y^{j}.$

Set $I\coloneqq\\{i<d\mid x^{i}\in
p\\}\stackrel{{\scriptstyle*}}{{=}}\\{j<d\mid y^{j}\in p\\}$ and
$M\coloneqq\\{x^{i}y^{j}\mid 0<i,j<d,x^{i}y^{j}\in p\\}$. Then,

$p=\sum_{i\in I}(x^{i}+y^{i})+\sum_{m\in M}m.$

For each $m\in M$, $h_{b}(m)=a^{i}b^{j}=a^{i}c^{j}=h_{c}(m)$ due to condition
(2) and $i>0$. More precisely, if $i>0$, we can invoke (2) inductively to
transform $ab^{j}$ into $ac^{j}$ due to commutativity of multiplication. We
now invoke condition (1) for each $i\in I$. For $z\in\\{b,c\\}$ and using
idempotence of $K$ (i), this yields

$\displaystyle a^{i}+z^{i}$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}(a+z)^{i}+z^{i}=\sum_{j=0}^{i}a^{i-j}z^{j}+z^{i}=\sum_{j=0}^{i-1}a^{i-j}z^{j}+z^{i}+z^{i}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\sum_{j=0}^{i-1}a^{i-j}z^{j}+z^{i}=a^{i}.$

Hence, $h_{b}(x^{i}+y^{i})=a^{i}+b^{i}=a^{i}=a^{i}+c^{i}=h_{c}(x^{i}+y^{i})$
for each $i\in I$ holds as well. Together, we have

$h_{b}(p)=\sum_{i\in I}h_{b}(x^{i}+y^{i})+\sum_{m\in M}h_{b}(m)=\sum_{i\in
I}h_{c}(x^{i}+y^{i})+\sum_{m\in M}h_{c}(m)=h_{c}(p),$

which completes the proof, since $\psi$ was arbitrary and
$\pi_{b}\llbracket\psi\rrbracket=h_{b}(p)=h_{c}(p)=\pi_{c}\llbracket\psi\rrbracket$.

Lemma 6.2 can be applied to many important semirings, such as $\mathbb{B}[X]$
itself and $\mathbb{S}[X]$ with an appropriate choice of $a$, $b$ and $c$.

######  Theorem 6.4.

For $X\supseteq\\{x,y\\}$, there exists a pair of elementarily equivalent, but
non-isomorphic $K$-interpretations in the shape of $\pi_{b}$ and $\pi_{c}$ for
both $K=\mathbb{B}[X]$ and $K=\mathbb{S}[X]$.

######  Proof 6.5.

For $\mathbb{B}[X]$, choose $a\coloneqq x+y+x^{2}+xy+y^{2}$, $b\coloneqq
x^{2}+y^{2}$ and $c\coloneqq x^{2}+xy+y^{2}$ to obtain the following pair of
$\mathbb{B}[X]$-interpretations.

$\pi_{b}:\quad$ $A$ $R$ $\neg R$ $d$ $x+y+x^{2}+xy+y^{2}$ $0$ $e$
$x^{2}+y^{2}$ $0$ $\quad\quad\pi_{c}:\quad$ $A$ $R$ $\neg R$ $d$
$x+y+x^{2}+xy+y^{2}$ $0$ $e$ $x^{2}+xy+y^{2}$ $0$

To prove the desired properties, we only have to check conditions (1) and (2)
from Definition 6.1 and then invoke Lemma 6.2. Condition (1) is obvious, and
for (2), it suffices to expand the products $ab$ and $ac$ to calculate that

$ab=ac=x^{3}+xy^{2}+x^{2}y+y^{3}+x^{4}+x^{3}y+x^{2}y^{2}+xy^{3}+y^{4}.$

An analogous construction works for the semiring of absorptive polynomials
$\mathbb{S}[X]$. Choose $a\coloneqq x+y$, $b\coloneqq x^{2}+y^{2}$ and
$c\coloneqq x^{2}+xy+y^{2}$. Note that this is the same as the counterexample
on $\mathbb{B}[X]$ above after applying absorption, which yields the pair of
$\mathbb{S}[X]$-interpretations depicted below.

$\pi_{b}:\quad$ $A$ $R$ $\neg R$ $d$ $x+y$ $0$ $e$ $x^{2}+y^{2}$ $0$
$\quad\quad\pi_{c}:\quad$ $A$ $R$ $\neg R$ $d$ $x+y$ $0$ $e$ $x^{2}+xy+y^{2}$
$0$

It is easy to verify that $a$, $b$ and $c$ also satisfy (1) and (2), which
completes the proof.

##  7 Conclusion and outlook

Our analysis of first-order axiomatisations and elementary equivalence of
finite semiring interpretations has revealed some remarkable differences
between semiring semantics and classical Boolean semantics. Depending on the
underlying semiring, there may exist finite semiring interpretations that are
elementarily equivalent without being isomorphic. Indeed, this phenomenon
happens already in very simple cases such as for min-max semirings with three
elements. On the other side, there are relevant semirings, used for instance
in provenance analysis in databases such as the tropical semiring or the
Viterbi semiring, where every finite interpretation is first-order
axiomatisable, and in fact even by a finite set of axioms. However, and this
is again an interesting difference to Boolean semantics, a finite
axiomatisation does not imply an axiomatisation by a single axiom.

Also for the semirings of polynomials, fundamental for a general provenance
analysis that reveals which combinations of atomic facts are responsible for
the truth of a logical statement, the picture is not unique. While the most
general semiring ${\mathbb{N}}[X]$, freely generated by $X$, admits
axiomatisations of all finite interpretations, so that elementary equivalence
implies isomorphism, this is not the case for the semirings
$\mathsf{PosBool}[X]$, $\mathbb{S}[X]$, $\mathbb{B}[X]$ and $\mathbb{W}[X]$
which are universal for important subclasses of semirings.

In the study of elementary equivalence for semiring semantics, it turns out
that there is no _straightforward_ adaptation of Ehrenfeucht–Fraïssé games, or
their generalisations such as Hellas bijective pebble game [15], to semiring
interpretations. Whatever the specific protocol of possible moves in such
games may be, they always result in a _localisation_ , in the sense that some
tuples in the two structures are picked that are indistinguishable on the
atomic level. As shown by the very simple example of the interpretations
$\pi_{PQ}$ and $\pi_{QP}$ at the beginning of Sect. 4, this is not possible in
semiring semantics. Although the two interpretations are elementarily
equivalent, no element of the first “looks the same” as any element of the
second, so any kind of localisation would result in a winning play of the
Spoiler. It is an intriguing open question how elementary equivalence of
semiring interpretations can be captured by a different notion of comparison
games or back-and-forth systems à la Fraïssé. This not being available (yet),
we have established elementary equivalence by different methods, based on
homomorphisms, which we believe to be of independent interest.

There are many other model-theoretic issues that deserve to be studied in
semiring semantics. While we have limited ourselves here to _finite_ semiring
interpretations, the study of semiring semantics over infinite universes is of
course very interesting as well. It requires certain restrictions on the
underlying semirings, concerning existence and appropriate algebraic
properties of infinite sums and products, but there are useful semirings
satisfying such properties. A particularly interesting question is what kind
of compactness and preservation results are possible in such contexts.

We finally remark that an altogether different approach to semiring
interpretations would consider them as two-sorted structures, one sort being a
finite or infinite structure (or just a set), the second one consisting of the
semiring, with functions from the first to the second sort giving the semiring
interpretation of the literals. This is very similar to the approach of
metafinite model theory [10], and to get a reasonable logical theory it is
important that the elements of the second sort, here the semiring, are treated
differently than the elements of the first sort. In particular, quantifiers
should range only over the first sort, and operations on the second sort are
just the algebraic semiring operations and their aggregates, together with
equalities between terms. Such an approach is certainly useful for a number of
questions and permits the study of semiring interpretations via classical
Boolean semantics. In particular, once semiring values are directly accessible
in the logic, the construction of characteristic sentences, axiomatising a
finite structure up to isomorphism, can easily be translated into such a
setting. However, such an internalisation of the semiring values, from the
meta-level of truth values into the structures under consideration, does not
really capture the essence of semiring semantics.

## References

  * [1] C. Bourgaux, A. Ozaki, R. Peñaloza, and L. Predoiu.  Provenance for the description logic ELHr.  In Proceedings of IJCAI 2020, pages 1862–1869, 2020.  doi:10.24963/ijcai.2020/258.
  * [2] K. Dannert and E. Grädel.  Provenance analysis: A perspective for description logics?  In C. Lutz et al., editor, Description Logic, Theory Combination, and All That, Lecture Notes in Computer Science Nr. 11560. Springer, 2019.  doi:10.1007/978-3-030-22102-7_12.
  * [3] K. Dannert and E. Grädel.  Semiring provenance for guarded logics.  In Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory through Algebraic Logic, Outstanding Contributions to Logic. Springer, 2020.
  * [4] K. Dannert, E. Grädel, M. Naaf, and V. Tannen.  Semiring provenance for fixed-point logic.  In Proceedings of CSL 2021, 2021.
  * [5] D. Deutch, T. Milo, S. Roy, and V. Tannen.  Circuits for datalog provenance.  In Proc. 17th International Conference on Database Theory ICDT, pages 201–212, 2014.
  * [6] J. Doleschal, B. Kimelfeld, W. Martens, and L. Peterfreund.  Weight annotation in information extraction.  In International Conference on Database Theory, ICDT 2020, 2020\.  doi:10.4230/LIPIcs.ICDT.2020.8.
  * [7] M. Droste and W. Kuich.  Semirings and formal power series.  In Handbook of Weighted Automata, pages 3–28. Springer, 2009.
  * [8] F. Geerts and A. Poggi.  On database query languages for K-relations.  J. Applied Logic, 8(2):173–185, 2010.
  * [9] J. Goodman.  Semiring parsing.  Computational Linguistics, 25:573–605, 1999.
  * [10] E. Grädel and Y. Gurevich.  Metafinite model theory.  Information and Computation, 140:26–81, 1998.
  * [11] E. Grädel and V. Tannen.  Semiring provenance for first-order model checking.  arXiv:1712.01980 [cs.LO], 2017.  URL: http://www.logic.rwth-aachen.de/pub/graedel/ET17.pdf.
  * [12] E. Grädel and V. Tannen.  Provenance analysis for logic and games.  Moscow Journal of Combinatorics and Number Theory, 9(3):203–228, 2020.  doi:10.2140/moscow.2020.9.203.
  * [13] T. Green, G. Karvounarakis, and V. Tannen.  Provenance semirings.  In Principles of Database Systems PODS, pages 31–40, 2007.
  * [14] T. Green and V. Tannen.  The semiring framework for database provenance.  In Proceedings of PODS, pages 93–99, 2017.
  * [15] L. Hella.  Logical hierarchies in PTIME.  In Proceedings of LICS 92, pages 360–368, 1992.
  * [16] M. Naaf.  Semirings for Provenance Analysis of Fixed Point Logics and Games.  Msc thesis, RWTH Aachen University, 2019.
  * [17] A. Ozaki and R. Peñaloza.  Provenance in ontology-based data access.  In Description Logics 2018, volume 2211 of CEUR Workshop Proceedings, 2018.
  * [18] M. Raghothaman, J. Mendelson, D. Zhao, M Naik, and B. Scholz.  Provenance-guided synthesis of datalog programs.  Proc. ACM Program. Lang., 4:62:1–62:27, 2020.  doi:10.1145/3371130.
  * [19] P. Senellart.  Provenance and probabilities in relational databases: From theory to practice.  SIGMOD Record, 46(4):5–15, 2017.


$\displaystyle=\operatorname{{\mathbb{P}}}\left(S_{i,t-1}|\mathcal{Y}^{t-2},\mathcal{Y}_{-\\{j\\},t-1}\right),$
(55)

where $F_{j}$s represent the functional dependency between time series given
in (25), i.e., $Y_{m,t-1}:=F_{m}(\mathcal{Y}^{t-2},S_{m,t-1})$. The above
equality holds due to the third condition. Note that the third condition
implies that states $S_{k,t}$ and $S_{k^{\prime},t^{\prime}}$ are independent
for any pairs $(k,k^{\prime})$ and $(t,t^{\prime})$. Same line of reasoning
implies

$\displaystyle\operatorname{{\mathbb{P}}}\left(S_{i,t-1}|\mathcal{Y}^{t-2},\mathcal{Y}_{-\\{j\\},t-1}\right)=\operatorname{{\mathbb{P}}}\left(S_{i,t-1}|\mathcal{Y}^{t-3},\mathcal{Y}_{-\\{j\\},t-2}^{t-1},F_{j}(\mathcal{Y}^{t-3},S_{j,t-2})\right)$
(56)
$\displaystyle=\operatorname{{\mathbb{P}}}\left(S_{i,t-1}|\mathcal{Y}^{t-3},\mathcal{Y}_{-\\{j\\},t-2}^{t-1}\right)=\cdots=\operatorname{{\mathbb{P}}}\left(S_{i,t-1}|\mathcal{Y}_{-\\{j\\}}^{t-1}\right).$
(57)

Recall that $\mathcal{Y}_{\mathcal{K}}^{t}$ denotes the time series with index
set $\mathcal{K}$ up to time $t$.

### Proof of Proposition 5

Assume that there exists a $\tau$, such that $J_{\tau}>0$, then the $\tau$-th
quantiles of $Y_{t}$ conditional on $Y^{t-1}_{t-p},X^{t-1}_{t-q}$ and
$Y^{t-1}_{t-p}$ are not equal, i.e.,

$\displaystyle Q^{Y}_{\tau}(Y^{t-1}_{t-p},X^{t-1}_{t-q})\neq
Q^{Y}_{\tau}(Y^{t-1}_{t-p}),$ (58)

that is

$\displaystyle\inf\\{y:F(Y_{t}=y|Y^{t-1}_{t-p},X^{t-1}_{t-q})\geq\tau\\}:=y_{1}\neq
y_{2}:=\inf\\{y^{\prime}:F(Y_{t}=y^{\prime}|Y^{t-1}_{t-p})\geq\tau\\}.$ (59)

Without loss of generality, we assume $y_{1}<y_{2}$. Since $F$ is continuous
then there exists a non-zero measure set around $y_{1}$ such that

$\displaystyle\operatorname{{\mathbb{P}}}(Y_{t}\leq
y|Y^{t-1}_{t-p},X^{t-1}_{t-q})\geq\tau>\operatorname{{\mathbb{P}}}(Y_{t}\leq
y|Y^{t-1}_{t-p}).$ (60)

Therefore, the ratio in (2) will differ from one which leads to
$I(X\rightarrow Y)>0$.

##  Appendix D Additional Experimental Results

###  D.1 List of stocks in our experiment

Next table represents the list of 124 stocks from 6 Global Industry
Classification Standard (GICS) sectors: Banks, DivFin, Insurance, REITs,
FinTech, and Crypto.

Table 2:  List of Studied Assets Across Sub-sectors Banks - 4010 |  Diversified Financials - 4020 |  Insurance - 4030
---|---|---
Bank of America Corporation |  Ameriprise Financial, Inc. |  Arch Capital Group Ltd.
Citigroup Inc. |  American Express Company |  Aflac Incorporated
Citizens Financial Group, Inc. |  Franklin Resources, Inc. |  American International Group, Inc.
Comerica Incorporated |  BNY Mellon Corporation |  Assurant, Inc.
Fifth Third Bancorp |  BlackRock, Inc. |  Arthur J. Gallagher & Co.
First Republic Bank |  Berkshire Hathaway Inc. |  Allstate Corporation
Huntington Bancshares Incorporated |  Cboe Global Markets, Inc. |  Aon plc
JPMorgan Chase & Co. |  CME Group Inc. |  Chubb Limited
KeyCorp |  Capital One Financial Corporation |  Cincinnati Financial Corporation
M&T Bank Corporation |  Discover Financial Services |  Globe Life Inc.
The PNC Financial Services Group |  The Goldman Sachs Group, Inc. |  Hartford Financial Services Group
Regions Financial Corporation |  Intercontinental Exchange, Inc. |  Loews Corporation
SVB Financial Group |  Invesco Ltd. |  Lincoln National Corporation
Truist Financial Corporation |  Moody’s Corporation |  MetLife, Inc.
U.S. Bancorp |  MarketAxess Holdings Inc. |  Marsh & McLennan Companies, Inc.
Wells Fargo & Company |  Morgan Stanley |  Principal Financial Group, Inc.
Zions Bancorporation |  MSCI Inc. |  Progressive Corporation
|  Nasdaq, Inc. |  Prudential Financial, Inc.
|  Northern Trust Corporation |  Employers Holdings Inc.
|  Raymond James Financial, Inc. |  Travelers Companies, Inc.
|  The Charles Schwab Corporation |  Unum Group
|  S&P Global Inc. |  W. R. Berkley Corporation
|  State Street Corporation |
|  Synchrony Financial |
|  T. Rowe Price Group Inc. |
REITs - 6010 |  Fintech |  Cryptocurrencies
Aimco |  ACI Worldwide, Inc. |  Cardano to US Dollar
American Tower Corporation |  Broadridge Financial Solutions, Inc. |  Bitcoin Cash to US Dollar
Alexandria Real Estate Equities, Inc. |  CoStar Group, Inc. |  Binance Coin to US Dollar
AvalonBay Communities, Inc. |  Euronet Worldwide, Inc. |  Bitcoin to US Dollar
Boston Properties, Inc. |  Envestnet, Inc. |  Dogecoin to US Dollar
Crown Castle International Corp. |  EVERTEC, Inc. |  Ethereum to US Dollar
CareTrust REIT, Inc. |  Fair Isaac Corporation |  Filecoin to US Dollar
Digital Realty Trust, Inc. |  Fidelity National Information Services |  Litecoin to US Dollar
Equinix, Inc. |  FleetCor Technologies, Inc. |  TRON to US Dollar
Equity Residential |  Global Payments Inc. |  Monero to US Dollar
Essex Property Trust, Inc. |  Jack Henry & Associates, Inc. |  Ripple to US Dollar
Extra Space Storage Inc. |  Mastercard Incorporated |
Federal Realty Investment Trust |  SS&C Technologies Holdings, Inc. |
Host Hotels & Resorts, Inc. |  Thomson Reuters Corporation |
Iron Mountain Incorporated |  Visa Inc. |
Kimco Realty Corporation |  Verisk Analytics, Inc. |
Mid-America Apt. Communities |  WEX Inc. |
Realty Income Corporation |  The Western Union Company |
Healthpeak Properties, Inc. |  |
Prologis, Inc. |  |
Public Storage |  |
Regency Centers Corporation |  |
SBA Communications Corporation |  |
Sabra Health Care REIT, Inc. |  |
SL Green Realty Corp. |  |
Simon Property Group, Inc. |  |
UDR, Inc. |  |
Vornado Realty Trust |  |
Ventas, Inc. |  |
Welltower Inc. |  |
Weyerhaeuser Company |  |

###  D.2 Non-linearity Test

We applied a non-linearity test on the data to determine whether the
underlying structure within the recorded data is linear or nonlinear. The non-
linearity test applied is based on non-linear principle component analysis
(PCA) of Kruger et al. (2008). This test works as follows, the range of
recorded data is divided into smaller disjunct regions; and accuracy bounds
are determined for the sum of the discarded eigenvalues of each region. If
this sum is within the accuracy bounds for each region, the process is assumed
to be linear. Conversely, if at least one of these sums is outside, the
process is assumed to be nonlinear.

More precisely, the second step in this test requires computation of the
correlation matrix for each of the disjunct regions. Since the elements of
this matrix are obtained using a finite dataset, applying $t$-distribution and
$\chi^{2}$-distribution establish confidence bounds for both estimated mean
and variance, respectively. Subsequently, these confidence bounds can be
utilized to determine thresholds for each element in the correlation matrix.
Using these thresholds, the test calculates maximum and minimum eigenvalues
relating to the discarded score variables, which in turn allows the
determination of both a minimum and a maximum accuracy bound for the variance
of the prediction error of the PCA model. This is because the variance of the
prediction error is equal to the sum of the discarded eigenvalues. If this sum
lies inside the accuracy bounds for each disjunct region, a linear PCA model
is then appropriate over the entire region. Alternatively, if at least one of
these sums is outside the accuracy bounds, the error variance of the PCA model
residuals then differs significantly for this disjunct region and hence, a
nonlinear model is required.

(a) Region 1.  (b) Region 2. (c) Region 3.

Figure 12: Benchmarking of the residual variances against accuracy bounds of
each disjunct region.

We divided the operating region into 3 disjunct regions. The accuracy bounds
for each disjuct region and also sum of the discarded eigenvalues were
computed. These bounds were based on thresholds for each element of the
correlation matrix corresponding to confidence level of 95%. The processes
were normalized with respect to the mean and variance of the regions for which
the accuracy bounds were computed. Figure 12 shows the accuracy bounds and the
sum of the discarded eigenvalues. As figures 12-(a) and 12-(b) illustrate, the
recorded data shows nonlinearity between series.

###  D.3 Complete Results of Time-varying Experiment

(a) $X_{0}\rightarrow X_{1}$ (b) $X_{0}\rightarrow X_{2}$ (c)
$X_{0}\rightarrow X_{3}$ (d) $X_{0}\rightarrow X_{4}$ (e) $X_{1}\rightarrow
X_{0}$ (f) $X_{1}\rightarrow X_{2}$ (g) $X_{1}\rightarrow X_{3}$ (h)
$X_{1}\rightarrow X_{4}$ (i) $X_{2}\rightarrow X_{0}$

Figure 13: Estimated DIs of the time-varying experiment.

(a) $X_{2}\rightarrow X_{1}$ (b) $X_{2}\rightarrow X_{3}$ (c)
$X_{2}\rightarrow X_{4}$ (d) $X_{3}\rightarrow X_{0}$ (e) $X_{3}\rightarrow
X_{1}$ (f) $X_{3}\rightarrow X_{2}$ (g) $X_{3}\rightarrow X_{4}$ (h)
$X_{4}\rightarrow X_{0}$ (i) $X_{4}\rightarrow X_{1}$ (j) $X_{4}\rightarrow
X_{2}$ (k) $X_{4}\rightarrow X_{3}$

Figure 14: Estimated DIs of the time-varying experiment.

###  D.4 Complete Results of Estimated DIs Among Industries

Remind that nodes with label $[0,1,2,3,4,5]$ denote industries [Banks,
Diversified Financial, Insurance, Real Estate Investment, Financial
Technology, Crypto], respectively.

Figure 15: Estimated DIs of the time-varying influences between the
industries.