3
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    I have edited my proof to address this possibility could you please take a look?2011-08-07
  • 0
    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.2011-08-07
  • 1
    @Mark: I don't immediately see the argument from monotonicity -- could you spell that out?2011-08-07
  • 0
    @joriki: I believe monotonicity states if both $\sigma$ and $\gamma$ are consistent then $\sigma \cup \gamma$ is consistent.2011-08-07
  • 0
    @gary: so what do you think, is there a gap?2011-08-07
  • 0
    @Mark: No, monotonicity doesn't state that. For any atomic $\alpha$, both $\{\alpha\}$ and $\{\neg\alpha\}$ are consistent, but $\{\alpha\}\cup\{\neg\alpha\}=\{\alpha,\neg\alpha\}$ isn't.2011-08-07
  • 0
    Well, if I understood your argument, you wanted to show (A or B)$\rightarrow C$, by showing that ~C $\rightarrow $ (~B and ~A), but I think you only showed ~C $\rightarrow $ ~B (~ means negation; let me look up the tex for negation )2011-08-07
  • 0
    @joriki: I can't find the wikipedia page for monotonicity do you have an link I can read?2011-08-07
  • 0
    @gary: The command is `\neg`; you can right/ctrl-click on any $\TeX$ output you see here and select "Show Source" to see the source for it.2011-08-07
  • 0
    @Mark: If you mean monotonicity of entailment, there's not very much on that in Wikipedia: http://en.wikipedia.org/wiki/Monotonicity_of_entailment. If you mean something else, you'd have to explain what you mean.2011-08-07
  • 0
    @joriki: Oh sorry I cited the wrong theorem. I guess a better argument would be: since $\sigma \cup \gamma \not\vdash \neg\alpha$ because $\gamma \not\vdash \neg\alpha$ and $\sigma \not\vdash \neg\alpha$ then by monotonicity and definition of consistency $\sigma \cup \gamma$ is consistent.2011-08-07
  • 0
    Sorry for my interloping; my background is obviously not strong-enough at this point to really help.2011-08-07
  • 0
    Do I understand correctly that you're trying to deduce $\sigma \cup \gamma \not\vdash \neg\alpha$ from $\gamma \not\vdash \neg\alpha$ and $\sigma \not\vdash \neg\alpha$? That's not valid; e.g., that $n=2$ follows neither from $n$ being even nor from $n$ being prime, but it does follow from $n$ being even and prime.2011-08-07
  • 0
    @joriki: How should I fill this gap then? I think I need to show that there is something $\sigma \cup \gamma$ can not prove.2011-08-07
  • 1
    @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.2011-08-07
  • 0
    @joriki: isn't there a theorm that states if two sets are consistent then their unions are consistent? I remember something like this being mention but is unable to find it.2011-08-07
  • 0
    @Mark: No, you can easily adapt my example with $2$ above to show that that's not true. The sets $\{n\text{ even},n\neq2\}$ and $\{n\text{ prime},n\neq2\}$ are both consistent, but their union $\{n\text{ even},n\text{ prime},n\neq2\}$ isn't. (By the way, there is only one union of two sets.)2011-08-07
  • 0
    @joriki: I found this problem online: Prove that if $\sigma \cup \gamma$ is inconsistent if and only if $\sigma \vdash \alpha$ and $\gamma \vdash \not\alpha$ http://www.student.cs.uwaterloo.ca/~cs798/2011Finalr1.pdf problem 2 d2011-08-07
  • 0
    @joriki: do you think I can adapt this problem for my proof?2011-08-07
  • 0
    @Mark: I don't think you can, at least not directly. You left out an important part of the statement in the problem; it says "if and only if *there exists* a formula $\alpha$". Since you're trying to show the negation, that $\sigma\cup\gamma$ is consistent, you'd have to show that there's no such formula, not just that the particular $\alpha$ you already have doesn't have that property. I suggest to take a strong look at how you/your book/your course define consistency, and what theorems you already proved about that; it might be quite straightforward from there.2011-08-07
  • 0
    @joriki: I don't have a book, but from what I took from lectures it seems the professor said a set is consistent if there is something it can not prove.2011-08-07
  • 0
    @Mark: Yes, that's correct; you can prove anything from inconsistent assumptions. So you'd need to somehow show that there's something that $\sigma\cup\gamma$ can't prove...2011-08-07
  • 0
    @joriki: I just digged through the notes I took in class. I found this Claim: A set of propositions Σ is maximally consistent if and only if for every proposition α, if Σ $\not\vdash$ α then Σ ∪ {α} is inconsistent. Since by my assumption Σ is not maximally consistent and Σ $\not\vdash$ α therefore Σ ∪ {α} is consistent. What do you think?2011-08-07
  • 0
    @joriki: I also found this lemma: For every set of propositions Σ and every proposition α, if Σ $\not\vdash$ $\alpha$ then Σ ∪ {(¬α)} is consistent. Using the lemma for my proof: Since Σ $\not\vdash$ $\neg\alpha$, Σ ∪ {(α)} is consistent by the lemma.2011-08-07
  • 0
    @joriki: I provide a proof of the lemma according to my notes.2011-08-07
  • 1
    @Mark: Your proof looks OK to me now.2011-08-08
  • 0
    @joriki: Wow, thanks for the help I sure have bothered you a lot.2011-08-08
  • 0
    @Mark: You're welcome.2011-08-08