Given an Inconsistent Set, find a Consistent Subset I'm a student learning first-order logic, so forgive me if this is elementary.
If I'm given an inconsistent set (that is, a set $\Sigma$ that can be used to show $\phi$ and $\lnot\phi$), is it possible to form a set $\Gamma$ of out of its elements such that $\Gamma$ is consistent?
$\Gamma$ need not be maximally-consistent, as I'm told that is impossible to prove. Just looking for a general algorithm to do this. I feel like it involves resolution (as we've been taught resolution), but I'm not sure.
Thanks!
 A: Hint: Consider the case where $\Gamma$ is just a single sentence which is provably false (e.g. $\varphi\land\lnot\varphi$ for any sentence $\varphi$). If we require that the consistent subset is non-empty, then there is only one possible subset.
A: Here are two easy observations:
Given any set of sentences $\Gamma$, the empty theory is a consistent subset of $\Gamma$.
If $\Gamma$ consists entirely of tautologically false sentences (for example, sentences of the form $\phi\land\lnot\phi$) then every nonempty subset of $\Gamma$ is inconsistent.
Edit: I've noticed that in your question, you're looking for an algorithm to find a consistent subset of $\Gamma$. This is impossible in general, because you can't even algorithmically recognize a consistent set of first-order sentences when you're handed one. In a sufficiently complicated first-order language (and you don't need much - a binary relation symbol or a binary function symbol is already enough), the set of tautologies, and hence the set of inconsistent sentences, is undecidable.
On the other hand, you can use Zorn's Lemma and compactness to show that $\Gamma$ has maximally consistent subtheories.
A: The empty set.${}{}{}{}{}{}{}{}$
