# Lindenbaum's Lemma in Propositional Logic

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. 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$.
• @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. – mrp Oct 23 '17 at 11:10
• @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. – mrp Oct 23 '17 at 11:11
• The definition @Tangent gives is the right one - treating e.g. $\{\varphi, \neg\varphi\wedge\neg\varphi\}$ as consistent is clearly inappropriate. – Noah Schweber Oct 23 '17 at 13:02