I’m doing an introduction to propositional logic course and am stuck on finding a proof for that s statement Let $\Sigma \subseteq L$. Suppose $\Sigma$ is truth-consistent. Show that there exists a set $\Gamma \subseteq L$ such that $\Gamma$ is truth-consistent, $\Sigma \subseteq \Gamma$ and, for all $Q \in L$, $\Gamma \models Q$ or $\Gamma \models \neg Q$.
How do you prove this?
 A: I will assume that by truth-consistent you simply mean consistent: that is, for no formula $\varphi$ one has both $\Sigma\vDash\varphi$ and $\Sigma\vDash\neg\varphi$. Then, as Mauro ALLEGRANZA mentions in a comment, this is the existence of a maximally consistent set of formulas.
You define $\Gamma$ by transfinite induction: assume $\{\varphi_{n} : n\in\mathbb{N}\}$ is an enumeration of $L$ (you usually assume the number of connectives and propositional variables is at most enumerable, so this is a reasonable request). Then:

*

*define $\Gamma_{0}=\Sigma$;

*if $\Gamma_{n}\cup \{\varphi_{n}\}$ is consistent, define $\Gamma_{n+1}=\Gamma_{n}\cup\{\varphi_{n}\}$; if the union is inconsistent, then define $\Gamma_{n+1}=\Gamma_{n}$.

Notice, and this is very important, that $\Gamma_{n}$ is always consistent: $\Gamma_{0}$ is consistent, and if $\Gamma_{n}$ is consistent, either $\Gamma_{n}\cup\{\varphi_{n}\}$ is consistent and thus so is $\Gamma_{n+1}=\Gamma_{n}\cup\{\varphi_{n}\}$; or $\Gamma_{n}\cup\{\varphi_{n}\}$ is inconsistent, $\Gamma_{n+1}=\Gamma_{n}$ is consistent given our induction hypothesis.
We finally define $\Gamma=\bigcup_{n\in\mathbb{N}}\Gamma_{n}$: it certainly satisfies $\Sigma=\Gamma_{0}\subseteq \Gamma$. We see that $\Gamma$ is consistent by compactness: suppose, otherwise, that $\Gamma\vDash \varphi$ and $\Gamma\vDash \neg\varphi$; by the compactness theorem, there exist $\alpha_{1}, ... , \alpha_{n}, \beta_{1}, ... , \beta_{m}\in \Gamma$ such that
$$\alpha_{1}, ... , \alpha_{n}\vDash\varphi\quad\text{and}\quad\beta_{1}, ... , \beta_{m}\vDash\neg\varphi.$$
Since $\{\varphi_{n} : n\in\mathbb{N}\}$ is an enumeration of $L$, there exist $i_{1}, ... , i_{n}, j_{1}, ... , j_{m}\in\mathbb{N}$ such that $\alpha_{1}=\varphi_{i_{1}}, ... , \alpha_{n}=\varphi_{i_{n}}, \beta_{1}=\varphi_{j_{1}}, ... , \beta_{m}=\varphi_{j_{m}}$, and by taking $N=\max\{i_{1}, ... , i_{n}, j_{1}, ... , j_{m}\}$, you can see that $\alpha_{1}, ... , \alpha_{n}, \beta_{1}, ... , \beta_{m}\in \Gamma_{N}$, what implies $\Gamma_{N}\vDash\varphi$ and $\Gamma_{N}\vDash\neg\varphi$, contradicting the aforementioned result that all $\Gamma_{n}$ are consistent! $\Gamma$ must then be also consistent.
The final step is proving $\Gamma$ is maximal, meaning that, for any formula $\psi\notin \Gamma$, $\Gamma\cup\{\psi\}$ is inconsistent. Since $\{\varphi_{n} : n\in\mathbb{N}\}$ is an enumeration of $L$, there must exist $n\in\mathbb{N}$ such that $\varphi_{n}=\psi$; now, $\Gamma_{n}\cup\{\varphi_{n}\}$ must be inconsistent, since otherwise we would have $\varphi_{n}\in \Gamma_{n+1}\subseteq \Gamma$, and therefore $\Gamma\cup\{\varphi_{n}\}\supseteq\Gamma_{n}\cup\{\varphi_{n}\}$ must also be inconsistent. So, for any formula $\psi$, if one has $\Gamma\not\vDash\psi$ and $\Gamma\not\vDash\neg\psi$, $\psi, \neg\psi\notin\Gamma$, and so both $\Gamma\cup\{\psi\}$ and $\Gamma\cup\{\neg\psi\}$ are inconsistent, and therefore $\Gamma\cup\{\psi\vee\neg\psi\}$ is inconsistent, what is absurd given $\Gamma$ is consistent and $\psi\vee\neg\psi$ is an axiom.
