Proposition 6.1. *Suppose* h**α, γ**i : S ⇄ Se is a Galois insertion. Then α is order-preserving if and only if it is a semiring isomorphism. Proof. **The sufficiency part is clear, and we now show the necessity part. Notice** that α, as a Galois connection, is monotonic. On the other hand, given **x, y** ∈ S,
suppose α(x) ≤Se α(y). By Equation 7, we have x ≤S y**. That is to say, for** any x, y ∈ S, α(x) ≤Se α(y) if and only if x ≤S y. In particular, α(x) = α(y)
implies x = y. This means that α **is injective. Moreover, by definition of** Galois insertion, α is also surjective. Therefore α **is an order isomorphism. As**
a consequence, it preserves sums.

We next show α preserves products. For x, y ∈ S, since α **is surjective,**
we have some z ∈ S with α(z) = α(x)×eα(y**). Applying the order-preserving**
property, we have z = x × y, hence α(x × y) = α(z) = α(x)×eα(y**), i.e.** α preserves products. In summary, α **is a semiring isomorphism.**
Theorem 29 of [1] concerns that, given an optimal solution of the abstract problem, how to find a reasonable estimation for an optimal solution of the concrete problem. Let α : S → Se be an abstraction. Given an SCSP P **over** S,
suppose t is an optimal solution of α(P), with semiring value ve in α(P**) and** v in P**. Then [1, Theorem 29] asserts that there exists an optimal solution** t¯ of P,
say with value v**, such that** v ≤ v ≤ γ(ve).

Our Soft Problem 4, however, shows that [1, Theorem 29] is only conditionally true. This is because the quasi-homomorphism α **given there is also an**
abstraction. Since each abstraction is also a quasi-homomorphism, **Theorem 5.2**
holds for any abstraction.

Our Theorem 5.1 corresponds to Theorem 31 of [1], where the authors consider abstractions between totally ordered semirings with idempotent multiplicative operations. By Example 2.1, we know such an abstraction must be a homomorphism. Therefore our result is more general than [1, Theorem 31].

## 6.2 Aggregation Compatible Mapping

There is another abstraction scheme [4] for soft constraints that is closely related to ours, where *valued CSPs* **[14] are abstracted in order to produce good lower**
bounds for the optimal solutions.

Definition 6.4 ([4]). A translation α : S → Se **between two totally ordered**
semirings is said to be *aggregation compatible* if
(1) α is monotonic and α(0) = e0, α(1) = 1e**; and**
(2) For any two sets I1 and I2**, we have**1

$$\alpha(\prod_{x\in I_{1}}x)\leq_{\widetilde{S}}\alpha(\prod_{x\in I_{2}}x)\Rightarrow\widetilde{\prod}_{x\in I_{1}}\alpha(x)\leq_{\widetilde{S}}\widetilde{\prod}_{x\in I_{2}}\alpha(x).\tag{8}$$

1Note that in Equation 8 we replace the two ≥ in Definition 2 of [4] with ≤**. This is because**
we should reverse the order of the valuation set S such that the aggregation operator ⊛ **is a**
product operator.