Consider the propositional language $L$ with denumerably many sentence letters $S_1,S_2,S_3,\ldots$ and the two connectives $\lnot,\lor$. Suppose that the set of sentences $\Gamma$ is a formal theory in $L$ and that for each sentence letter $S_i$, either $S_i\in\Gamma$ or $\lnot S_i\in\Gamma$. Prove by induction on structural complexity that $\Gamma$ is complete.

I'm familiar with how proof by induction on structural complexity works, but I'm unsure how to apply it in this context so I'm having trouble getting started.


Let $\varphi$ be some sentence in the language you just described. We prove by induction on the complexity of $\varphi$ that either $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.

The base case is just atomic sentences. That is, $\varphi$ is of the form $S_i$ for some $i$ (or maybe $\top$ or $\bot$, depending on your definitions). So this case is covered by the assumption that either $S_i \in \Gamma$ or $\neg S_i \in \Gamma$, which translates into $\Gamma \vdash S_i$ or $\Gamma \vdash \neg S_i$.

If you want to try the rest of the induction for yourself, you may want to consider to stop reading here.

There are two induction steps: one where $\varphi$ is of the form $\neg \psi$ and one where $\varphi$ is of the form $\psi_1 \lor \psi_2$. Let us consider each case.

If $\varphi$ is of the form $\neg \psi$, then by induction hypothesis we have $\Gamma \vdash \psi$ or $\Gamma \vdash \neg \psi$. In the first case we thus have $\Gamma \vdash \neg \varphi$, and in the second case we find $\Gamma \vdash \varphi$. So again, either $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.

If $\varphi$ is of the form $\psi_1 \lor \psi_2$, we can again use the induction hypothesis to find a two different cases. The first case is that $\Gamma \vdash \psi_1$ or $\Gamma \vdash \psi_2$ (or both), which gives us $\Gamma \vdash \varphi$. The other case is that $\Gamma \vdash \neg \psi_1$ and $\Gamma \vdash \neg \psi_2$, which means that $\Gamma \vdash \neg \varphi$. Once more concluding that indeed $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg \varphi$.

This completes the induction, and so we can conclude that $\Gamma$ is complete.


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.