I've recently learnt Lindenbaum's Lemma in propositional logic:

Suppose $\Gamma$ is a consistent set of $L$-formulas. Then there exists a consistent set $\Gamma'$ of $L$-formulas containing $\Gamma$, such that for every $L$-formula $Q$, either $\Gamma' \vdash Q$ or $\Gamma' \vdash \neg Q$.

I've the following questions:

  1. In class we used this lemma and the assumption that the empty set is consistent to prove the Completeness Theorem for propositional logic. Is it considered to be completely trivial that the empty set is consistent? What would be a quick acceptable line of reasoning for this?
  2. Could somebody exhibit an example of any (consistent) $\Gamma$, perhaps the empty set, together with an $L$-formula $P$ such that NEITHER $\Gamma \vdash P$ NOR $\Gamma \vdash \neg P$?

Remark For 2, the Lindenbaum lemma would certainly guarantee some larger $\Gamma'$ from which there is a deduction of either $P$ or $\neg P$ for any $P$, but I'm curious for more context. What kind of set $\Gamma$ is such that neither $P$ nor $\neg P$ is deducible from it?)

| cite | improve this question | | | | |
  1. A set of formulas $\Gamma$ is consistent if and only if there is no formula $\varphi$ such that both $\varphi \in \Gamma$ and $\neg \varphi \in \Gamma$. Since there are no formulas at all in $\emptyset$, this vacuously holds.
  2. Consider two propositional variables $p$ and $q$. If $\Gamma = \{p\}$, then clearly $\Gamma$ is consistent. However, neither $\Gamma \vdash q$ nor $\Gamma \vdash \neg q$, simply because $p$ in itself does not give us enough information to say anything about $q$.
| cite | improve this answer | | | | |
  • 1
    $\begingroup$ 1. Ah, my lecturer defined consistency differently: A set of formulas Γ is consistent if and only if there is no formula φ such that both Γ⊢φ and Γ⊢¬φ. Can our definitions be shown to be equivalent? 2. That's great, thanks. A side question, if in your example I let Γ={p, ¬p} then I would have an inconsistent set Γ with neither Γ⊢q nor Γ⊢¬q, correct? Thanks for replying so quickly! $\endgroup$ – SSF Oct 23 '17 at 10:59
  • $\begingroup$ @Tangent in that case, you would have to assume that your axioms are consistent. $\emptyset \vdash \varphi$ means exactly that $\varphi$ can be deduced from only the axioms, so consistency of $\emptyset$ amounts to saying that your axioms are consistent. $\endgroup$ – mrp Oct 23 '17 at 11:10
  • $\begingroup$ @Tangent for the second point, not quite. Since $p$ and $\neg p$ gives you a contradiction, if you assume $p$ and $\neg p$, you can derive anything, thanks to the principle of explosion. $\endgroup$ – mrp Oct 23 '17 at 11:11
  • $\begingroup$ Thanks very much. Also, I've decided that our definitions of consistency aren't exactly the same; mine implies yours but yours doesn't imply mine. For example I could have φ be ¬(p→p), then let Q={φ}. Then according to your definition, Q is consistent, but according to mine it's not since I could deduce anything from Q (by your 'principle of explosion' and the fact that (p→p) is a theorem). $\endgroup$ – SSF Oct 23 '17 at 12:21
  • 3
    $\begingroup$ The definition @Tangent gives is the right one - treating e.g. $\{\varphi, \neg\varphi\wedge\neg\varphi\}$ as consistent is clearly inappropriate. $\endgroup$ – Noah Schweber Oct 23 '17 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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