atom from S has negative occurrences in G outside the scope of negation; consequently, by the induction hypothesis (claim (b)), Y |= GX . On the other hand, Y |= (G → H)
X , so that Y |= HX. Since no atom from S has positive occurrences in H outside the scope of negation, we can conclude that Y \ S |= HX by induction hypothesis (claim (a)).

Proposition 9 (Completion Lemma) Let Γ *be any propositional theory, and* Q a set of atoms that have positive occurrences in Γ only in the scope of negation. For each q ∈ Q*, let* Def(q) be a formula such that all negative occurrences of atoms from Q in Def(q) *are in the scope of negation. Then* Γ ∪ {Def(q) → q : q ∈ Q} and Γ ∪ {Def(q) ↔ q : q ∈ Q} *have the same stable models.*
Proof. Let Γ1 be Γ ∪ {Def(q) → q : q ∈ Q} and let Γ2 be Γ1 ∪ {q →
Def(q) : q ∈ Q}. We want to prove that a set X of atoms is a stable model of both theories or for none of them. Since Γ
X
1 ⊆ Γ
X
2
, Γ
X
2entails Γ
X
1
. If the opposite entailment holds also then we clearly have that Γ
X
2and Γ
X
1are satisfied by the same subsets of X, and the claim immediately follows. Otherwise, for some Y ⊆ X, Y 6|= ΓX
2and Y |= ΓX
1
. First of all, that means that X |= Γ1, so that Γ
X 1 is equivalent to Γ
X ∪ {Def(q)
X → q : q ∈ Q ∩ X}.

Secondly, set Y is one of the sets Y
′ having the following properties:
(i) Y
′ \ Q = Y \ Q, and
(ii) Y
′|= Def(q)
X → q for all q ∈ Q ∩ X.

Let Z be the intersection of such sets Y
′, and let ∆ be {q → Def(q)
X : q ∈
Q ∩ X}. Set Z has the following properties:
(a) Z ⊆ Y ,
(b) Z |= ΓX
1
, and
(c) Z |= ∆.

Indeed, claim (a) holds since Y is one of the elements Y
′ of the intersection. To prove (b), first of all, we observe that Z \ Q = Y \ Q, so that, by (a), there is a set S ⊆ Q such that Z = Y \ S; as Y |= ΓX and Γ has all positive occurrences of atoms from S ⊆ Q in the scope of negation, it follows that Z |= ΓX by Lemma 9(a). It remains to show that, for any q, if Z |= Def(q)
X then q ∈ Z.

Assume that Z |= Def(q)
X. Then, since Def(q) has all negative occurrences of