β ∈ Y+ \ X+. Therefore, (**Y, Y** ) |= Γ1 ∪ Γ. Towards a contradiction, assume that there exists X′ ⊂ Y such that (X′, Y ) |= Γ1 ∪ Γ. From (X′, Y ) |= Γ, we conclude that either X′+ = Y+, or that X+ ⊆ X′+ ⊂ Y+ and X′− ⊆ X−. In both cases, (X′, Y ) 6|= Γ1. In the former case because (**Y, Y** ) is A+-total, i.e., (Y+, Y ) is closed in Es(Γ1). In the latter case, it is a consequence of the fact that (**X, Y** ) ∈ EA
+
A− (Γ1), which implies (X′, Y ) 6|= Γ1 by A+-closure. This contradicts our assumption concerning the existence of X′ ⊂ Y such that (X′, Y ) |= Γ1 ∪ Γ, and proves that Y is an answer set of Γ1 ∪ Γ. However, Y is not an answer set of Γ2 ∪ Γ. To wit, since (**X, Y** ) 6∈ EA
+
A− (Γ2), there exists X′ ⊂ Y such that X+ ⊆ X′+, X′− ⊆ X−, and (X′, Y ) |= Γ2. Moreover, (X′, Y ) is an HT-model of Γ. Observe that X′− ⊆ X− implies that (X′, Y ) is an HT-model of every formula of the form α → β in Γ. Hence, (X′, Y ) |= Γ2 ∪ Γ, and since X′ ⊂ Y , it follows that Y is not an answer set of Γ2 ∪ Γ. Note that Γ is an A+-A−-theory, which contradicts Γ1 A
+
A−≡ Γ2.

This proves EA
+
A− (Γ1) = EA
+
A− (Γ2).

For the if direction, suppose EA
+
A− (Γ1) = EA
+
A− (Γ2) and towards a contradiction assume that Γ1 A
+
A− 6≡ Γ2. W.l.o.g. let Y be an answer set of Γ1 ∪ Γ for some A+-A−-theory Γ,
such that Y is not an answer set of Γ2 ∪Γ (the other case is symmetric). Then, (**Y, Y** ) is an equivalence interpretation of both, Γ1 and Γ, and (Y+, Y ) is closed in Es(Γ1 ∪ Γ), which implies (taking Proposition 5 into account) that (**Y, Y** ) is A+-total for Γ1 and (Y |A, Y ) is in EA
+
A− (Γ1). Therefore, (Y |A, Y ) is also in EA
+
A− (Γ2), with the consequence that (**Y, Y** ) is in Es(Γ2), and thus (**Y, Y** ) ∈ Es(Γ2 ∪ Γ). Since by assumption Y is not an answer set of Γ2 ∪ Γ, there exists X ⊂ Y such that (**X, Y** ) 6∈ Es(Γ2 ∪ Γ), i.e., (**X, Y** ) |= Γ2 ∪ Γ. Since
(Y |A, Y ) ∈ EA
+
A− (Γ2), it holds that X|A ⊂ Y |A. Moreover, X+ ⊂ Y+ due to A+-totality of (**Y, Y** ). Clearly, (X|A, Y ) is not in EA
+
A− (Γ2) as witnessed by (**X, Y** ) |= Γ2, and thus
(X|A, Y ) 6∈ EA
+
A− (Γ1) since EA
+
A− (Γ1) = EA
+
A− (Γ2). From (X|A, Y ) 6∈ EA
+
A− (Γ1), we conclude that there exists X′ ⊆ Y , such that X+ ⊆ X′+, X′− ⊆ X−, and (X′, Y ) 6∈ Es(Γ1),
i.e., X′ ⊂ Y and (X′, Y ) |= Γ1. By Proposition 4, (**X, Y** ) |= Γ implies (X′, Y ) |= Γ. Consequently, (X′, Y ) |= Γ1 ∪ Γ, and since X′ ⊂ Y , this contradicts our assumption that Y is an answer set of Γ1 ∪ Γ, and proves Γ1 A
+
A−≡ Γ2.

Like in the logic programming setting, the framework obtained by the consideration of relativized hyperequivalence interpretations provides a general unified characterization of semantic characterizations of equivalence notions. In other words, the notions of equivalence considered in the previous subsection are obtained as special cases. For this purpose, one needs to refer to the universal alphabet (respectively signature), denoted by A, explicitely. Then, by definition, setting A+ = A− = ∅ amounts to answer-set equivalence, A+ = A− = A yields strong equivalence, and A+ = A, A− = ∅ characterizes uniform equivalence. The latter is not by definition but follows from two simple observations: every set of facts over A is a A-∅-theory, and every A-∅-theory is a factual theory modulo formulas of the form ⊥ → φ, which are tautologies in HT.

Corollary 2 Given two propositional theories Γ1 and Γ2 over **L ⊆ A**, the following propositions are equivalent for e ∈ {**a, s, u**}, A+(a) = A−(a) = ∅, A+(s) = A−(s) = A, A+(u) = A,
and A−(u) = ∅: