# Prove by induction on structural complexity that the following set is complete

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.