1
$\begingroup$

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!

  • 1
    Put `$` around the $\LaTeX$.2012-12-10

3 Answers 3

3

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.

  • 0
    @John: Yes, you can always add one sentence at a time to see if you are still with a consistent set. But note that it is possible that all sentences are simply false, so only the empty set is a consistent subset; and more importantly you only asked for an example (which I assumed meant a nontrivial one, i.e. a non-empty example) for a consistent subset.2012-12-10
3

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.

  • 0
    Sure - but you might not get very far. For example if $\Gamma$ consists only of tautologically false sentences! I've also just made an edit to my post.2012-12-11
3

The empty set.${}{}{}{}{}{}{}{}$