See George Tourlakis, Mathematical Logic (2008), page 93 :
3.2.1 Metatheorem (Post's Tautology Theorem) : If $\Gamma \vDash_{TAUT} A$, then $\Gamma \vdash A$.
Proof. It is most convenient to prove the contrapositive, namely, if $\Gamma \nvdash A$, , then $\Gamma \nvDash_{TAUT} A$
Some facts are needed :
Claim One. There is an enumeration $G_0,G_1, \ldots$ of all formulae of propositional logic.
See page 95 :
Assume the hypothesis side, $\Gamma \nvdash A$.
We next construct a set of formulae, $\Delta$, which is as large as possible with the
properties that it includes $\Gamma$, but also
$\Delta \nvdash A$.
We build $\Delta$ by stages, $\Delta_0, \Delta_1, \ldots$ by an inductive definition, adding no more than one formula at each step.
The $\Delta_n$ sequence is:
$\Delta_0 = \Gamma$
For $n \ge 0$ :
$\Delta_{n+1} = \Delta_n \cup \{ G_n \}$, if $\Delta_n \cup \{ G_n \} \nvdash A$
$\Delta_{n+1} = \Delta_n \cup \{ \lnot G_n \}$, if $\Delta_n \cup \{ \lnot G_n \} \nvdash A$
$\Delta_n$, else.
Thus, at each stage we add to the set that we are constructing at most one formula, which is a member or a negation of a member of the sequence $\{ G_n \}$.
We define $\Delta = \bigcup_{n \ge 0} \Delta_n$, forming $\Delta$ as the set of all the members found in all the $\Delta_n$.
Several facts follow :
Claim Two. $\Gamma \subseteq \Delta$.
Claim Three. For $n \ge 0, \Delta_n \nvdash A$. This follows by induction on $n$.
Claim Five. $\Delta \nvdash A$.
Claim Six. For every formula $B$, either $B \in \Delta$, or $\lnot B \in \Delta$, but not both.
Claim Seven. $\Delta$ is deductively closed, that is, if $\Delta \vdash B$, then $B \in \Delta$.
Now we can define a valuation $v$ that verifies $\Gamma \nvDash A$.
Define a valuation $v$ by setting, for each variable $p$, $v(p) = t$ iff $p \in \Delta$.
Main Claim. For all formulae $B, v(B) = t$ iff $B \in \Delta$.
The proof is by induction on the complexity of $B$. We have the following cases:
(i) $B$ is a variable : by definition of $v$.
Then, check all cases according to the inductive definition of formula.
After that, we can easily conclude the proof as follows: By the Main Claim, every
formula $B \in \Delta$ — and hence every formula $B \in \Gamma$ since $\Gamma \subseteq \Delta$ — satisfies $v(B) = t$.
On the other hand, as $\Delta \nvdash A$ it must be $A \notin \Delta$; thus, again via the Main Claim, $v(A) = f$. Therefore $\Gamma \nvDash_{TAUT} A$.
See page 99 :
3.2.2 Corollary. If $\vDash B$, then $\vdash B$.
Proof. Case of $\Gamma = \emptyset$.
Note
A different kind of proof of the Completeness Theorem for propositional logic (due to Kalmar, 1935) can be found in Elliott Mendelson, Introduction to mathematical logic (4ed - 1997), page 42; also in this case it is required the proof of a lemma by induction on the complexity of the formula.
