# Comparing the Reasoning Capabilities of Equilibrium Theories and Answer Set Programs
## Appendix A Proofs of Results
Let us denote by  
\[D(Z)=\{Z^{\prime}\subseteq At\mid Z^{\prime}\cap(A\cup B)=Z\cap(A\cup B)\text{ and }[\,]\
eq[\,\Pi_{2}\,]^{Z^{\prime}}\text{ is }A\|-\|feasible\}\]  
Take  
\[\mathcal{S}=\{(X^{\prime},Z^{\prime})\mid Z^{\prime}\in D(Z)\text{ and }X^{\prime}\cap A\in[\,\Pi_{2}\,]_{A}^{Z^{\prime}}\cap \overline{[\,\Pi_{1}\,]_{A}^{Z}}\}\cup\{(X,Z)\mid X\cap A\in\overline{[\,\Pi_{ 1}\,]_{A}^{Z}}\}\]  
Notice that \((Z,Z)\in\mathcal{S}\) and \((X^{\prime},Z^{\prime})\in\mathcal{S}\) implies \((Z^{\prime},Z^{\prime})\in\mathcal{S}\). Then, \(\mathcal{S}\) is a total-closed set of interpretations (A set \(\mathcal{S}\) of \(\mathbf{HT}\) interpretations is total-closed if for any \(\langle H,T\rangle\in\mathcal{S}\), \(\langle T,T\rangle\in\mathcal{S}\)). Denote by \(\Pi^{\prime}\) the program with signature in \(A\) such that models of \(\Pi^{\prime}\) correspond to interpretations in \(\mathcal{S}|A\). First of all, we have that \(Z\in E(\Pi_{1}\cup\Pi^{\prime})\) because \((Z\cap A,Z\cap A)\in\mathcal{S}|A\), so \(Z\cap A\models\Pi^{\prime}\) or \(Z\models\Pi^{\prime}\). Moreover, take \(X\subseteq Z\) such that \(\langle X,Z\rangle\models\Pi_{1}\cup\Pi^{\prime}\). Then, \(\langle X\cap A,Z\cap A\rangle\models\Pi^{\prime}\) so \(X\cap A\in\overline{[\,\Pi_{1}\,]_{A}^{Z}}\cap[\,\Pi_{1}\,]_{A}^{Z}\) which implies that \(X\cap A=Z\cap A\) and \(X=Z\) because \([\,\Pi_{1}\,]^{Z}\) is \(A\)-feasible. Now \(T\cap B=Z\cap B\in E(\Pi_{1}\cup\Pi^{\prime})|B\subseteq E(\Pi_{2}\cup\Pi^{ \prime})|B\), so there exists \(\tilde{Z}\in E(\Pi_{2}\cup\Pi^{\prime})\) such that \(\tilde{Z}\cap B=Z\cap B\). Because \(\tilde{Z}\models\Pi^{\prime}\), we know that \((\tilde{Z},\tilde{Z})\in\mathcal{S}\) so \(\tilde{Z}\in D(Z)\). We are going to show that \([\,\Pi_{2}\,]_{A}^{\tilde{Z}}\subseteq[\,\Pi_{1}\,]_{A}^{Z}\) or equivalently \([\,\Pi_{1}\,]_{A}^{Z}\preceq[\,\Pi_{2}\,]_{A}^{\tilde{Z}}\in\langle\!\langle\, \Pi_{2}\,]_{A,B}^{T}\). On the contrary, suppose that \(X^{\prime}\cap A\
ot\in[\,\Pi_{1}\,]_{A}^{Z}\) with \(X^{\prime}\in[\,\Pi_{2}\,]_{A}^{Z}\cap[\,\Pi_{1}\,]_{A}^{Z}\) so \((X^{\prime}\cap A,\tilde{Z}\cap A)\in\mathcal{S}|A\). Because: \(\langle X^{\prime},\tilde{Z}\rangle\models\Pi_{2}\cup\Pi^{\prime}\), we can deduce that \(X^{\prime}=\tilde{Z}\) because \(\tilde{Z}\in E(\Pi_{2}\cup\Pi^{\prime})\). Finally, \(X^{\prime}\cap A=\tilde{Z}\cap A=Z\cap A\in[\,\Pi_{1}\,]_{A}^{Z}\). Proof of Theorem 4.: (Left to right)  
Take \(Y\subseteq A\cup B\) and \(\mathcal{H}_{A}\in\langle\!\langle\,F\,\rangle\!\rangle_{A,B}^{Y}\), where \(\mathcal{H}\in\langle\!\langle\,F\,\rangle\!\rangle^{Z}\) is \(A\)-feasible and \(Z\cap(A\cup B)=Y\). We will denote by  
\[D(Y)=\{Z^{\prime}\subseteq At\mid Z^{\prime}\cap(A\cup B)=Y\}.\]  
Let us consider the following \(Y\cap A\)-support \(\mathcal{H}_{0}\):  
\[\mathcal{H}_{0}=\overline{\mathcal{H}_{A}}\cap\bigcup\{\mathcal{H}^{\prime}_{ A}\mid\mathcal{H}^{\prime}\in\langle\!\langle\,C\,\rangle\!\rangle^{Z^{\prime}}\text{ with }\mathcal{H}^{\prime}A-\text{ feasible and }Z^{\prime}\in D(Y)\}\]  
By Lemma 3, we know that there exists a formula \(\varphi\in\mathcal{L}_{A}\) such that \(\llbracket\,\varphi\,\rrbracket^{Y\cap A}=\mathcal{H}_{0}\) and \(\llbracket\,\varphi\,\rrbracket^{T}=\,\lfloor\,\rfloor\), for any \(T\subseteq A\) with \(T\
eq Y\cap A\). Let us prove that \(Z\in E(F\wedge\varphi)\) by showing that:  
\[[Z]=\mathcal{H}\cap\llbracket\,\varphi\,\rrbracket^{Z}\in\langle\!\langle\,F \wedge\varphi\,\rangle\!\rangle^{Z}.\]  
Suppose that \(H\in\mathcal{H}\cap\llbracket\,\varphi\,\rrbracket^{Z}\). Then:  
\[ \begin{array}{ll}H\cap A\in\mathcal{H}_{A}\cap\llbracket\,\varphi\, \rrbracket^{Z}_{A}&\text{implies}\\ H\cap A\in\mathcal{H}_{A}\cap\mathcal{H}_{0}&\text{implies}\\ H\cap A\in\mathcal{H}_{A}\cap\overline{\mathcal{H}_{A}}&\text{implies}\\ H\cap A=Z\cap A&\text{implies}\\ H=Z&\end{array} \]  
Consequently \(Y\cap B=Z\cap B\in E(F\wedge\varphi)|B\subseteq E(G\wedge\varphi)|B\), so there exists \(\tilde{Z}\in E(G\wedge\varphi)\) verifying that \(Z\cap B=\tilde{Z}\cap B\).