[proofplan]
We must show: every formula provable from $S$ is a semantic consequence of $S$. Fix an arbitrary valuation $v$ satisfying $v(s) = 1$ for all $s \in S$. We show by induction on the length of a proof $t_1, \ldots, t_n = t$ of $t$ from $S$ that $v(t_i) = 1$ for every line $t_i$. There are three ways a line may appear: as an axiom (the axioms (A1)–(A3) are tautologies, so $v$ sends them to $1$), as a hypothesis in $S$ (value $1$ by assumption on $v$), or by modus ponens from earlier lines (the truth-table for $\Rightarrow$ forces the conclusion to have value $1$). Taking $i = n$ gives $v(t) = 1$, and since $v$ was arbitrary, $S \models t$.
[/proofplan]
[step:Fix an arbitrary valuation satisfying $S$ and set up the induction]
Recall that $S \models t$ means: for every valuation $v: L \to \{0,1\}$, if $v(s) = 1$ for all $s \in S$, then $v(t) = 1$.
Fix such a valuation $v$ — that is, any valuation with $v(s) = 1$ for all $s \in S$. Let $t_1, t_2, \ldots, t_n = t$ be a formal proof of $t$ from $S$. We show by induction on $i \in \{1, \ldots, n\}$ that
\begin{align*}
v(t_i) &= 1.
\end{align*}
Each line $t_i$ in the proof is justified in exactly one of the following ways:
1. $t_i$ is an axiom of propositional calculus (an instance of (A1), (A2), or (A3));
2. $t_i \in S$;
3. $t_i$ follows by modus ponens from two earlier lines $t_j$ and $t_k$ with $j, k < i$ and $t_k = (t_j \Rightarrow t_i)$.
We handle each case.
[/step]
[step:Verify case (1) — axioms are tautologies, so every valuation sends them to $1$]
The axioms of propositional calculus are the schemata
\begin{align*}
\text{(A1)} &\quad a \Rightarrow (b \Rightarrow a), \\
\text{(A2)} &\quad [a \Rightarrow (b \Rightarrow c)] \Rightarrow [(a \Rightarrow b) \Rightarrow (a \Rightarrow c)], \\
\text{(A3)} &\quad ((a \Rightarrow \bot) \Rightarrow \bot) \Rightarrow a,
\end{align*}
for any $a, b, c \in L$. We claim each instance is a tautology, i.e., every valuation assigns it the value $1$. This is a finite truth-table verification, using the valuation rule
\begin{align*}
v(x \Rightarrow y) &= \begin{cases} 0 & \text{if } v(x) = 1, v(y) = 0, \\ 1 & \text{otherwise,} \end{cases}
\end{align*}
and $v(\bot) = 0$.
**(A1).** For any valuation $v$, consider $v(a \Rightarrow (b \Rightarrow a))$. If $v(a) = 0$, the outer implication has false antecedent, hence value $1$. If $v(a) = 1$, then the consequent $b \Rightarrow a$ satisfies $v(b \Rightarrow a) = 1$ (since the consequent $a$ has value $1$), so the outer implication has value $1$. Hence $v(a \Rightarrow (b \Rightarrow a)) = 1$ in all cases.
**(A2).** Let $A := v(a)$, $B := v(b)$, $C := v(c)$. If the outer antecedent $a \Rightarrow (b \Rightarrow c)$ has value $0$, the outer implication is $1$. Otherwise $v(a \Rightarrow (b \Rightarrow c)) = 1$, and we must check $v((a \Rightarrow b) \Rightarrow (a \Rightarrow c)) = 1$. Suppose toward contradiction this equals $0$: then $v(a \Rightarrow b) = 1$ and $v(a \Rightarrow c) = 0$. From $v(a \Rightarrow c) = 0$, we get $A = 1$ and $C = 0$. From $v(a \Rightarrow b) = 1$ with $A = 1$, we get $B = 1$. But then $v(b \Rightarrow c) = 0$ (since $B = 1$, $C = 0$), and with $A = 1$, we get $v(a \Rightarrow (b \Rightarrow c)) = 0$, contradicting our assumption. Hence (A2) is a tautology.
**(A3).** We must show $v(((a \Rightarrow \bot) \Rightarrow \bot) \Rightarrow a) = 1$. If $v(a) = 1$, the outer implication has true consequent, hence value $1$. If $v(a) = 0$, then $v(a \Rightarrow \bot) = 1$ (since $v(\bot) = 0$ and $v(a) = 0$, the antecedent is false, so the implication is $1$); then $v((a \Rightarrow \bot) \Rightarrow \bot) = 0$ (since $v(a \Rightarrow \bot) = 1$ and $v(\bot) = 0$, the outer is $0$); the outermost implication has antecedent $0$, hence value $1$. So (A3) is a tautology.
Therefore, if $t_i$ is any instance of (A1), (A2), or (A3), then $v(t_i) = 1$.
[/step]
[step:Verify case (2) — hypotheses in $S$ have value $1$ by assumption]
If $t_i \in S$, then by the choice of $v$ (a valuation with $v(s) = 1$ for all $s \in S$), we have
\begin{align*}
v(t_i) &= 1.
\end{align*}
[/step]
[step:Verify case (3) — modus ponens preserves truth under $v$]
Suppose $t_i$ is obtained by modus ponens from earlier lines $t_j$ and $t_k$ with $j, k < i$ and $t_k = (t_j \Rightarrow t_i)$. By the induction hypothesis applied to $j$ and $k$,
\begin{align*}
v(t_j) &= 1, \\
v(t_j \Rightarrow t_i) &= 1.
\end{align*}
Apply the valuation rule
\begin{align*}
v(t_j \Rightarrow t_i) &= \begin{cases} 0 & \text{if } v(t_j) = 1 \text{ and } v(t_i) = 0, \\ 1 & \text{otherwise.} \end{cases}
\end{align*}
Since $v(t_j) = 1$ and $v(t_j \Rightarrow t_i) = 1$, the first case is excluded: we cannot have $v(t_i) = 0$, so $v(t_i) = 1$.
[/step]
[step:Conclude by taking $i = n$ and observing $v$ was arbitrary]
By induction on $i$, $v(t_i) = 1$ for all $i \in \{1, \ldots, n\}$. Taking $i = n$ and using $t_n = t$, we get $v(t) = 1$.
Since $v$ was an arbitrary valuation satisfying $v(s) = 1$ for all $s \in S$, we have shown that every such valuation satisfies $v(t) = 1$. By definition, this is $S \models t$.
[/step]
