Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Put $ around the $\LaTeX$. –  Asaf Karagila Dec 10 '12 at 8:53
    
Thanks, @AsafKaragila! –  John Fung Dec 10 '12 at 15:09

3 Answers 3

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

share|improve this answer

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.

share|improve this answer
    
That being the empty set? Starting from the empty set, however, can I not keep adding sentences from $\Sigma$ to $\Gamma$ one by one, and then resolving to see if my new set is consistent? –  John Fung Dec 10 '12 at 15:06
    
@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. –  Asaf Karagila Dec 10 '12 at 15:08

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.

share|improve this answer
    
Starting from the empty set, however, can I not keep adding sentences from Σ to Γ one by one, and then resolving to see if my new set is consistent? –  John Fung Dec 10 '12 at 15:08
    
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. –  Alex Kruckman Dec 11 '12 at 9:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.