A propositional theory Γ over A+ ∪ A−, where A+ and A− are sets of propositional variables, is called an A+-A−*-theory* if every formula in Γ has positive occurrences of atoms from A+, and negative occurrences of atoms from A−, only. Note that ⊥ is always allowed to appear both, positively and negatively. An A+-A−-theory is called *extended*, if additionally factual formulas over A+ are permitted.

By means of these notions, relativized hyperequivalence for propositional theories can be expressed as follows, which is a proper generalization of the logic programming setting. Definition 7 Two propositional theories Γ1, Γ2 over L are called *relativized hyperequivalent wrt.* A+
and A−, symbolically Γ1 A
+
A−≡ Γ2, iff for any A+-A−-theory Γ over L
′ ⊇ L, Γ1 ∪ Γ and Γ2 ∪ Γ are answer-set equivalent.

Towards a characterization of relativized hyperequivalence, our goal is to follow the same methodology that we used to characterize uniform equivalence, i.e., resorting to HTcountermodels and respective closure conditions. However, while in the logic programming setting such closure conditions may be obtained from certain monotonicity properties of the program reduct, we first have to establish corresponding properties for theories. A
first property in this respect is the following. Note that although the next result is stated for extended A+-A−-theories (for reasons which will become clear later), it trivially also holds for any (non-extended) A+-A−-theory.

Proposition 4 Consider an extended propositional A+-A−-theory Γ, and an HT-interpretation (**X, Y** ).

Then, (**X, Y** ) |= Γ implies (X′, Y ) |= Γ, for all X′ ⊆ Y such that X|A+ ⊆ X′|A+ and X′|A− ⊆ X|A− .

Proof Consider any A+-A−-formula φ in Γ, i.e., any formula that has positive occurrences of atoms from A+, and negative occurrences of atoms from A−, only. We show by induction on the formula structure of φ, that for all X′ ⊆ Y such that X|A+ ⊆ X′|A+ and X′|A− ⊆
X|A−:
(a) (**X, Y** ) |= φ implies (X′, Y ) |= φ if φ is a positive occurrence; and (b) (**X, Y** ) 6|= φ implies (X′, Y ) |= φ if φ is a negative occurrence.

For the base case, consider any atomic formula φ, and suppose first that (a) the occurrence of φ is a positive occurrence. Then, (**X, Y** ) |= φ implies that φ is not ⊥, and thus is an atom a from A+ such that a ∈ X. Since X|A+ ⊆ X′|A+ for all X′ under consideration, we conclude that a ∈ X′. Hence, (X′, Y ) |= φ. Suppose (b) φ is a negative occurrence. If
(**X, Y** ) 6|= φ, then either φ is ⊥, and (X′, Y ) 6|= φ follows trivially. Otherwise, φ is an atom b from A−, such that b 6∈ X|A−. Since X′|A− ⊆ X|A− for all X′ under consideration, we conclude that b 6∈ X′, i.e., (X′, Y ) 6|= φ. This proves (a) and (b) for atomic formulas.

For the induction step, assume that (a) and (b) hold for any A+-A−-formula of connective nesting depth n−1, and let φ be a formula of connective nesting depth n. Consider the case where φ is of the form φ1 ∧ φ2, respectively φ1 ∨ φ2. If φ is a positive occurrence (a),
then so are φ1 and φ2, both of connective nesting depth depth n − 1. From (**X, Y** ) |= φ we