In case (2), since skel(s) = ∅**, according to Definition 13 (page 16), there exists a**
set of rules S = {r1} ∪ {si| 1 ≤ i 6= j ≤ n} ⊆ (C¯ ∪ Q**) such that:**
r1 : ρ(s)Pj ← l ≤ \#count{K : (g(s))(K)Pj, K 6= j } ≤ h si : (g(s))(i)Pj ←Vb∈content(s)
bPi(1 ≤ i 6= j ≤ n).

Moreover, for each r ∈ (C¯ ∪ Q) \ S **and for each** t ∈ S, head(r ) 6= head(t).

Now, since ρ(s)Pj 6∈ M , body(r1) is false w.r.t. M **. Since** body(r1) = l ≤ \#count{K :
(g(s))(K)Pj, K 6= j } ≤ h, according to the definition of aggregate functions (Dell'Armi et al. **2003),**
for each D ⊆ {i | 1 ≤ i 6= j ≤ n} (l ≤ |D| ≤ h), there exists k **s.t. 1** ≤ k 6=
j ≤ n and (g(s))(k)Pjis false w.r.t. M **. Thus, there exists a rule** sk ∈ C¯ ∪ Q
s.t. sk : (g(s))(k)Pj ←Vb∈content(s)
bPk and head(sk ) is false w.r.t. M **. Since** ∀r ∈
(C¯ ∪Q)\ {sk }, head(r ) 6= head((sk ), body(sk ) is false w.r.t. M **, i.e.** Vb∈content(s)
bPk is false w.r.t. M **. Now, since** ¯I ⊆ M ,Vb∈content(s)
bPk is false w.r.t. ¯I.

Thus, we have proven that for each set D ⊆ {i | 1 ≤ i 6= j ≤ n} s.t. l ≤ |D| ≤ h, there exists some k ∈ D and some x ∈ content(s) s.t. x is false for Pk w.r.t. ¯I**. This**
result, according to item (2) of Definition 8 (page 11), contradicts **the hypothesis**
that s is true for Pk w.r.t. ¯I**. Now we have concluded the proof of of the basis of**
the induction.

(Induction**). Assume that the statement holds for** maxs
′∈N (s){depth(s
′)} = d > 0 and consider the case maxs
′∈N (s){depth(s
′)} = d + 1. First, observe that s **is not**
simple, because skel(s) 6= ∅. Since s **is well-formed,** cond(s) = [l, h**]. Thus, according**
to Definition 13 (page 16), there exists a set of rules S = {r1**} ∪ {**si| 1 ≤ i 6= j ≤
n} ⊆ (C¯ ∪ Q**) s.t.:**

$$(1\leq i\neq j\leq n)$$

r1 : ρ(s)Pj ← l ≤ \#count{K : (g(s))(K)Pj, K 6= j } ≤ h si : (g(s))(i)Pj ←Vb∈content(s)
bPi ∧Vs
′∈**skel**(s)
ρ(s
′
)Pj(1 ≤ i 6= j ≤ n)
Now, observe that:
(1) For each s
′ ∈ skel(s), maxσ∈N (s
′){depth(σ)} = d**, and**
(2) Since s is true for Pk w.r.t. ¯I**, according to Definition 8 (page 11), for each**
s
′ ∈ skel(s), s
′is true for Pj **w.r.t.** ¯I.

On the basis of the above observations and the induction hypothesis, it holds that for each s
′ ∈ skel(s), ρ(s
′)Pj ∈ M .

Since s is true for Pj w.r.t. ¯I and cond(s) = [l, h**], according to Definition 8**
(page 11) there exists D ⊆ SP \ {Pj } s.t. l ≤ |D| ≤ h and ∀a ∈ **content**(s),
∀P ∈ D, a is true for P **w.r.t.** ¯I.

Thus, it holds that, for each 1 ≤ i ≤ n such that both i 6= j and Pi ∈ D, Vb∈content(s)
bPi ∧Vs
′∈**skel**(s)
ρ(s
′)Pjis true w.r.t. M , as ¯I ⊆ M . Since M **is a stable**
model of C¯ ∪ Q, according to the definition of the set S **(given at the beginning of**
the part (Induction)), for each i s.t. 1 ≤ i 6= j ≤ n and s.t. Pi ∈ D, (g(s))(i)Pjis true w.r.t. M .

Since l ≤ |D| ≤ h, there exists a set of literals D′ = {(g(s))(i)Pj| 1 ≤ i 6= j ≤ n}
s.t. l ≤ |D′| ≤ h and s.t. for each element d ∈ D′, d **is true w.r.t.** M .

Now, according to the definition of aggregate functions (Dell'Armi et al. 2003),
body(r1) is true w.r.t. M and, since M **is a stable model of** C¯ ∪ Q, head(r1) is true