Show that for any formula $\varphi$ in this language, exactly one of $\varphi$ and $\lnot\varphi$ is a logical consequence of $\Gamma$.

Question

Suppose that the language has the set $\{P_i : i \in \mathbb{N}\}$ of propositional variables and let $\Gamma$ be the set $\{Q_i : i \in \mathbb{N}\}$, where $Q_i$ is either $P_i$ or $\neg P_i$ for each $i \in \mathbb{N}$. Show that for any formula $\varphi$ in this language, exactly one of $\varphi$ and $\neg \varphi$ is a logical consequence of $\Gamma$.

This question is related to the propositional calculus in mathematical logic, and all theorems and definitions within the propositional logic are allowed to be used.

Answer 1

The main insight is already explained in the comments by Mauro: there is only one valuation that satisfies $\Gamma$ (maybe you know this under a different term, model, but for propositional logic we usually call it a valuation).

Let me briefly recall what this means. A valuation is a function $v: \{P_i : i \in \mathbb{N}\} \to \{\tt{true}, \tt{false}\}$. This then extends naturally to a function that takes a (propositional) formula as an input and outputs $\tt{true}$ or $\tt{false}$. For a set of formulas $\Gamma$, we say that a valuation $v$ satisfies $\Gamma$ if for every $\phi \in \Gamma$ we have $v(\phi) = \tt{true}$.

So in the situation of your question, the trick is that $\Gamma$ encodes precisely one valuation and that is the only valuation that satisfies $\Gamma$. That is, we define (in the notation of the question): $$ v(P_i) = \begin{cases} \tt{true} & \text{if } Q_i \text{ is } P_i \\ \tt{false} & \text{if } Q_i \text{ is } \neg P_i \end{cases} $$ By construction $v$ satisfies $\Gamma$, and it is clear that no other valuation can satisfy $\Gamma$. So by soundness and completeness (not compactness, as you wrote in your comment) we have that the consequences of $\Gamma$ are precisely the same as the formulas $\phi$ such that $v(\phi) = \tt{true}$. Now the conclusion follows easily: let $\phi$ be any formula, then either $v(\phi) = \tt{true}$ or $v(\phi) = \tt{false}$, in the latter case we have $v(\neg \phi) = \tt{true}$. So either $\phi$ or $\neg \phi$ is a consequence of $\Gamma$, but never both.