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.

Let $\sigma$ be a consistent set of propositions such that for every set $\gamma$, either $\sigma$ is proofwise stronger than $\gamma$ that is {$\alpha : \sigma \vdash \alpha$} $\supseteq$ {$\alpha : \gamma \vdash \alpha$} or $\sigma \cup \gamma$ is not consistent. Prove that in that case $\sigma$ is maximally consistent.

My proof:

Suppose $\sigma$ is not maximally consistent then there exist a proposition $\alpha$ such that $\sigma \not\vdash \alpha$ and $\sigma \not\vdash \neg\alpha$. In this case, let $\gamma$ = {$\alpha$}. Since $\sigma \not\vdash \alpha$ that means $\sigma$ is not proofwise stronger than $\gamma$, and $\sigma \cup \gamma$ is consistent (by Lemma below) , which contradicts our assumption.

Lemma: For every set of propositions Σ and every proposition α, if Σ $\not\vdash$ α then Σ ∪ {(¬α)} is consistent.

Proof of the lemma: Assume, by way of contradiction, that Σ∪{(¬α)} is not consistent. Then it proves every proposition, in particular Σ ∪ {(¬α)} $\vdash$ α. By the deduction theorem we therefor get Σ $\vdash$ ((¬)α → α). However, $\vdash$(((¬)α → α) → α), for every proposition α. Now, applying MP we get Σ $\vdash$ α, which contradicts our initial assumption.

Is there a gap in my proof?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Yes, there's a gap in your proof because the assumption is not that $\sigma$ is proofwise stronger than $\gamma$, but that either $\sigma$ is proofwise stronger than $\gamma$ or $\sigma\cup\gamma$ is not consistent; so you have to address that second possibility, too.

share|improve this answer
I have edited my proof to address this possibility could you please take a look? –  Mark Aug 7 '11 at 5:56
I don't know if we should call it a possibility; the statement is of the form $A\/B \rightarrow C)$, and you are using contraposition, so that one should then show ~$C \rightarrow$ ~$A^ $~$B $ , so that both non-maximality and non-consistency should follow for contraposition to hold. –  gary Aug 7 '11 at 6:02
@Mark: I don't immediately see the argument from monotonicity -- could you spell that out? –  joriki Aug 7 '11 at 6:03
@Mark: Intuitively speaking, if $\sigma \not\vdash \neg\alpha$, then $\sigma \cup\{\alpha\}$ can't be inconsistent. How to prove this formally may depend on what your exact definition of consistency is and what you've already proved and might be able to use. –  joriki Aug 7 '11 at 7:14
@Mark: Your proof looks OK to me now. –  joriki Aug 8 '11 at 8:26
show 23 more comments

Your Answer


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.