Theorem 6 Two theories coincide on their QHT-countermodels iff they have the same QHT equivalenceinterpretations, in symbols Cs(Γ1) = Cs(Γ2) iff Es(Γ1) = Es(Γ2).

As a consequence of these two main results, we obtain an elegant, unified formal characterization of the different notions of equivalence for first-order theories under generalized answer-set semantics.

Corollary 5 Given two first-order theories Γ1 and Γ2, the following propositions are equivalent for e ∈ {**c, a, s, u**}: Γ1 ≡e Γ2; Ce(Γ1) = Ce(Γ2); Ee(Γ1) = Ee(Γ2).

Moreover, lifting the characterization of HT-countermodels provided in Proposition 2 to the first-order setting, allows us to prove a property, which simplifies the treatment of extended signatures.

Proposition 7 Let M be a QHT-interpretation over L on U. Then, M ∈ Es(Γ) for a theory Γ iff M |=
Γφ(M) for some φ ∈ Γ, where Γφ(M) = {¬¬ψ | ψ ∈ Γ**} ∪ {**φ → (¬¬a → a) | a ∈
BP,CU }.

For QHT-models it is known that M |= Γ implies M|L |= Γ (cf. e.g., Proposition 3 in (de Bruijn et al. 2007)), hence M|L 6|= Γ implies M 6|= Γ, i.e., M|L ∈ Cs(Γ) implies M ∈ Cs(Γ). The converse direction holds for totality preserving restrictions (the proof appeared in (Fink 2008) and can also be found in (Fink 2009)):
Theorem 7 Let Γ be a theory over L, let L
′ ⊃ L, and let M a QHT-interpretation over L
′
such that M|L is totality preserving. Then, M ∈ Cs(Γ) implies M|L ∈ Cs(Γ).

Note that this property carries over to QHT-models, i.e., M|L |= Γ implies M |= Γ,
if M|L is the restriction of M to L and this restriction is totality preserving. Otherwise, by the above result M 6|= Γ would imply M|L 6|= Γ. We remark that in (Fink 2008) it is erroneously stated informally that this property does not hold for QHT-models, however the counter-example given there is flawed (Example 5 in (Fink 2008)).

## 4.3 Relativized Hyperequivalence For First-Order Theories

In this section we extend the notion of relativized hyperequivalence to first-order theories.

For this purpose, we distinguish positive and negative occurrences of predicates in sentences. More precisely, the occurrence of a predicate p in a sentence φ is called *positive* if φ is implication free, if p occurs in the consequent of an implication in φ, or if φ is of the form (φ1 → φ2) → φ3 and p occurs in φ1. An occurrence of p is called *negative* if p occurs in the antecedent of an implication. The notion of positive and negative occurrence is again extended to (sub-)sentences in the obvious way.

Let Γ be a first-order theory over L = hF, L+ ∪ L
−i, where L
+ and L
− are sets of predicate symbols with an associated arity, such that if a predicate symbol p occurs in both L
+ and L
−, then it is also associated the same arity. We say that Γ is an L
+-L
−*-theory* if