# Comparing the Reasoning Capabilities of Equilibrium Theories and Answer Set Programs
## Appendix A Proofs of Results  
**Proof of Proposition 9. ** (Right to left). Clearly, if, for any set of \(A\) formulas \(\Pi\), \(E(\Pi_{1}\cup\Pi)|B=E(\Pi_{2}\cup\Pi)|B\), then these theories answer all \(B\)-queries in the same way and so are strongly inseparable. (Left to right). Suppose that for some \(\Pi\), \(E(\Pi_{1}\cup\Pi)|B\
eq E(\Pi_{2}\cup\Pi)|B\). Then, we can apply Lemma 1(i) to some \(M|B\), say, in \(E(\Pi_{1}\cup\Pi)|B\setminus E(\Pi_{2}\cup\Pi)|B\) and build a \(B\)-sentence \(\bigwedge_{i}\varphi_{i}\) that is true in \(M|B\) but false in all models in \(E(\Pi_{2}\cup\Pi)|B\). Note that the formulas \(\varphi_{i}\) are built as in Lemma 1(i) where now \(U=B\). Likewise for Lemma 1(ii). So, the theories are not strongly \(B,\omega\) inseparable relative to \(A\), for \(\omega\in\{c,s\}\). **Proof of Proposition 10. ** (Right to left). Suppose that \(\Pi_{1}\bigcup_{s}^{s,A}\Pi_{2}\) does not hold and choose a model \(M\in E(\Pi_{1}\cup\Sigma)|B\setminus E(\Pi_{2}\cup\Pi)|B\). Apply Lemma 1(ii), setting \(U=B\), to obtain a \(B\)-formula \(\psi\) satisfied by all models in \(E(\Pi_{2}\cup\Sigma)|B\) but not in \(M\). It follows that  
\[\Pi_{1}\
ot\sim_{s,B}^{s,A}\Pi_{2}\]  
The following lemma will be useful later. **Lemma A1**. : _Given a program \(\Pi\) and sets \(\mathcal{L},Z\subseteq At\), such that \(Z\models\Pi\), for any \(\Sigma\in\mathcal{L}\) the following assertions are equivalent:_  
1. \(Z\in E(\Pi\cup\Sigma)\)__
2. \(\llbracket\,\Pi\,\rrbracket^{Z}\) _is_ \(A\)_-feasible and_ \[\llbracket\,\Pi\,\rrbracket^{Z}_{A}\cap\llbracket\,\Sigma\,\rrbracket^{Z\cap A} =[Z\cap A].\]Proof. : \(1.\Rightarrow\) 2. Take \(Z\in E(\Pi\cup\Sigma)\) and suppose that \(\langle H,Z\rangle\models\Pi\) for some \(H\subseteq Z\) such that \(H\cap A=Z\cap A\). Because  
\[\langle H,Z\rangle\models\Sigma\ \text{iff}\ \langle H\cap A,Z\cap A\rangle \models\Sigma\ \text{iff}\ \langle Z\cap A,Z\cap A\rangle\models\Sigma\ \text{iff}\ \langle Z,Z\rangle\models\Sigma\]  
we have that \(\langle H,Z\rangle\models\Pi\cup\Sigma\) which implies that \(H=Z\). Moreover, if \(X\subseteq Z\) satisfies \(\langle X,Z\rangle\models\Pi\) and \(\langle X\cap A,Z\cap A\rangle\models\Sigma\), then \(\langle X,Z\rangle\models\Pi\cup\Sigma\) and \(X=Z\). Consequently, \(X\cap A=Z\cap A\). 2. \(\Rightarrow\) 1. Suppose that \(\langle H,Z\rangle\models\Pi\cup\Sigma\) for some \(H\subseteq Z\). Then, \(\langle H\cap A,Z\cap A\rangle\models\Sigma\) and \(H\cap A\in[\Pi\,]_{A}^{Z}\cap[\,\Sigma\,]^{Z\cap A}\). Consequently, \(H\cap A=Z\cap A\) and \(H=Z\) because \([\,\Pi\,]^{Z}\) is \(A\)-feasible. Proof of Theorem 1.: (Right to left) Suppose that \(\tilde{Z}=Z\cap B\in E(\Pi_{1}\cup\Sigma)|B\) for some \(\Sigma\in\mathcal{L}_{A}\) and \(Z\in E(\Pi_{1}\cup\Sigma)\). By Lemma A1, we know that \([\,\Pi_{1}\,]^{Z}\) is \(A\)-feasible and  
\[[\,\Pi_{1}\,]_{A}^{Z}\cap[\,\Sigma\,]^{Z\cap A}=[Z\cap A].\]  
Take \(T=Z\cap(A\cup B)\), then \([\,\Pi_{1}\,]_{A}^{Z}\in\langle\!\langle\,\Pi_{1}\,]_{A,B}^{T}\subseteq\langle \!\langle\,\Pi_{2}\,]_{A,B}^{T}\). It follows that there is some \(Z_{2}\subseteq At\) such that \(T=Z_{2}\cap(A\cup B)\) (which implies that \(Z_{2}\cap A=T\cap A=Z\cap A\) and \(Z_{2}\cap B=T\cap B=Z\cap B=\tilde{Z}\)) being \([\,\Pi_{2}\,]^{Z_{2}}\)\(A\)-feasible and \([\,\Pi_{2}\,]_{A}^{Z}\subseteq[\,\Pi_{1}\,]_{A}^{Z}\) (or \([\,\Pi_{1}\,]_{A}^{Z}\preceq[\,\Pi_{2}\,]_{A}^{Z}\)). Notice that \(Z_{2}\models\Sigma\) because \(Z_{2}\cap A=Z\cap A\) and \(Z\models\Sigma\). Moreover:  
\[[\,\Pi_{2}\,]_{A}^{Z_{2}}\cap[\,\Sigma\,]^{Z\cap A}\subseteq[\,\Pi_{1}\,]_{A}^ {Z}\cap[\,\Sigma\,]^{Z\cap A}=[Z\cap A]=[Z_{2}\cap A]\]  
This implies that \(Z_{2}\in E(\Pi_{2}\cup\Sigma)\) and \(\tilde{Z}=Z_{2}\cap B\in E(\Pi_{2}\cup\Sigma)|B\). (Left to right)  
Take \(T\subseteq A\cup B\) and \([\,\Pi_{1}\,]_{A}^{Z}\in\langle\!\langle\,\Pi_{1}\,]_{A,B}^{T}\), for some \(Z\cap(A\cup B)=T\) such that \([\,]\
eq[\,\Pi_{1}\,]^{Z}\) is \(A\)feasible.