Splitting and Updating Hybrid Knowledge Bases (Extended Version) 25

(1) The direct implication follows from Proposition 27. We will prove the converse implication. Suppose M[U] ⊇ N[U]and I ∈ N. We immediately obtain I
[U] ∈ M[U]
and since M is saturated relative to U, we can conclude that I ∈ M.

(2) For the direct implication suppose that M ( N. Then there is some I ∈ N such that I /∈ M. Since M is saturated relative to U, we obtain that I
[U] ∈/ M[U]. Consequently, M[U]is a proper subset of N[U]. The converse implication is a cosequence of Proposition 27(3).
Proposition 31 Let U be a set of predicate symbols and M, N ∈ M be such that N is saturated relative to U. Then:
(1) M ⊆ N if and only if M[U] ⊆ N[U].

(2) If M[U] ( N[U], then M ( N.

Proof
(1) The direct implication follows from Proposition 27(1). We will prove the converse implication. Suppose M[U] ⊆ N[U]and I ∈ M. We immediately obtain I
[U] ∈
M[U], hence also I
[U] ∈ N[U]. Since N is saturated relative to U, we can conclude that I ∈ N. Consequently, M ⊆ N.

(2) This is a consequence of (1) and Proposition 27(3).

Corollary 32 Let U be a set of predicate symbols and **M, N** be MKNF interpretations that are both saturated relative to U. Then the following equivalences hold:
(1) M ⊆ N if and only if M[U] ⊆ N[U].

(2) M = N if and only if M[U] = N[U].

(3) M ( N if and only if M[U] ( N[U].

Proof
(1) Follows from Proposition 31(1).

(2) This is a consequence of (1).

(3) This is a consequence of (1) and (2).

Definition 33 Let U be a set of predicate symbols and M ∈ M. Then we introduce the following notation:
σ(**M, U**) = nI ∈ I
I
[U] ∈ M[U]o Proposition 34 Let U be a set of predicate symbols and M, N ∈ M. Then the following conditions are equivalent:
1. N = σ(**M, U**);
2. N coincides with M on U and is saturated relative to U.

3. N is the greatest among all N′ ∈ M coinciding with M on U;
Furthermore, if N satisfies one of the conditions above, then M ⊆ N.

Proof