Proof. The definition of ϕ
−(c) is {a ∈ Asn | ϕAsn(a) ∈ c}. Hence, |ϕ
−(c)**| ≤ |**c|. Similarly, we know that |ϕ(c)| = |c|. From p(ϕ(d)) ⊂ ϕ(d), it follows that |p(ϕ(d))| <
|ϕ(d)|. Together, this yields |ϕb(p)(d)| < |ϕ(d)| = |d|. We have seen in Proposition 1 that ϕb(p)(d) ⊆ d, so we can conclude that ϕb(p)(d) ⊂ d.

## 3.3 Completeness Of Derived Propagators

Ideally, a propagator derived from a domain- or bounds-complete propagator should inherit its completeness. It turns out to not generally be true for all notions of completeness and all views. This section first shows how bounds(Z) completeness is inherited, and then generalizes this result to the other notions.

The key insight is that bounds(Z) completeness of propagators derived using a view ϕ depends on whether ϕ and ϕ
− commute with the hull operator, as defined below.

Definition 8 A constraint c is a ϕ*-constraint* for a view ϕ if and only if for all a ∈ c, there is a b ∈ Asn such that a = ϕAsn(b). A view ϕ is *hull-injective* if and only if ϕ
−(hull(dom(c))) = hull(dom(ϕ
−(c))) for all ϕ-constraints c. It is *hull-surjective* if and only if ϕ(hull(d)) = hull(ϕ(d)) for all domains d. It is *hull-bijective* if and only if it is hull-injective and hull-surjective. ∗
The proofs rely on the additional fact that views commute with set intersection.

Lemma 1 For any view ϕ, the equation ϕ
−(c1 ∩c2) = ϕ
−(c1)∩ϕ
−(c2) holds. ∗
Proof. By definition of ϕ
−, we have ϕ
−(c1 ∩c2) = {a ∈ Asn | ϕAsn(a) ∈ c1 ∧ϕAsn(a) ∈ c2}
As ϕAsn is a function, this is equal to
{a ∈ Asn | ϕAsn(a) ∈ c1**} ∩ {**a ∈ Asn | ϕAsn(a) ∈ c2} = ϕ
−(c1)∩ϕ
−(c2)
Theorem 1 (Bounds(Z) **completeness)** Let p be a bounds(Z)-complete propagator.

For any hull-bijective view ϕ, the propagator ϕb(p) is bounds(Z)-complete. ∗
Proof. From Proposition 2, we know that ϕb(p) induces the constraint ϕ
−(cp). By monotonicity of ϕ
− (with P1) and bounds(Z) completeness of p, we know that ϕ
− ◦ p ◦ϕ(d) ⊆ ϕ
−(hull(dom(cp ∩hull(ϕ(d)))))
We now use the fact that both ϕ
− and ϕ commute with hull(·) and set intersection:
ϕ
−(hull(dom(cp ∩hull(ϕ(d)))))

| −(hull(dom(cp ∩ϕ(hull(d)))))                      | (hull-surjective)   |                  |
|---------------------------------------------------|---------------------|------------------|
| = ϕ                                               | −(cp ∩ϕ(hull(d))))) | (hull-injective) |
| = hull(dom(ϕ = hull(dom(ϕ −(cp)∩ϕ −(ϕ(hull(d))))) | (commute with ∩)    |                  |
| = hull(dom(ϕ −(cp)∩hull(d)))                      | (P2)                |                  |

The second step uses hull injectivity, so it requires cp∩ϕ(hull(d)) to be a ϕ-constraint.

All assignments in a ϕ-constraint have to be the image of some assignment under