Lindenbaum's Lemma in Propositional Logic

1.2k Views Asked by At

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?)

1

There are 1 best solutions below

5
On BEST ANSWER
  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$.