\documentclass{article}
\newcommand{\proof}{{\bf Proof:~}}
\topmargin -0.5in
\oddsidemargin -0.5in
\evensidemargin -0.5in
\textheight 9.2in
\textwidth 7.5in
\pagestyle{empty}
\begin{document}
\thispagestyle{empty}
\centerline{\small Mathematical Logic I notes; \today}
\vspace{4pt}
\centerline{\LARGE Completeness Theorem for Propositional Logic}
\vspace{4pt}
\centerline
{\footnotesize Compiled by J.~Schlipf, seriously civil yet subtly
sinister host}
\begin{enumerate}
\item {\bf Lemma:}
{\sl Let $A$ be a
set of formulas. For each $\phi\in A$, $A\models\phi$.}
\proof We need to show that the following holds for every truth
assignment $\nu$: if $\nu\models\psi$ for every $\psi\in A$, then
$\nu\models\phi$. But this is trivial: if $\nu\models\psi$ for
every $\psi\in A$, and since $\phi\in A$, then $\nu\models\phi$
by assumption.
\item {\bf Lemma:}
{\sl Let $A$ be a set of formulas. For each $\phi\in A$,
$A\vdash\phi_i$.}
\proof Fix any $\phi\in A$. The following is a natural deduction
proof of $\phi$ from premises $A$:
\[\begin{array}{rcl} 1.&\phi & \mbox{premise} \end{array}\]
\item {\bf Lemma:}
{\sl Let $\phi$ be a formula and $A,B$ be sets of formulas. If
$A\subseteq B$ and $A\models\phi$, then $B\models\phi$.}
\proof We need to show that, for every truth assignment $\nu$, if
$\nu\models B$, then $\nu\models\phi$. So let $\nu$ be any truth
assignment where $\nu\models B$, i.e., $nu\models\psi$ for every
$\psi$ in $B$. But then, since $A\subseteq B$, $nu\models\psi$ for
every $\psi$ in $A$, i.e., $\nu\models A$. So, by hypothesis,
$\nu\models\phi$, as desired.
\item {\bf Lemma:}
{\sl Let $\phi$ be a formula and $A,B$ be sets of formulas. If
$A\subseteq B$ and $A\vdash\phi$, then $B\vdash\phi$.}
\proof Let $P$ be any proof of $\phi$ from premises $A$. That
means that every premise in $P$ is an element of $A$. But then
every premise in $P$ is also in $B$, so $P$ is also a proof of
$\phi$ from premises $B$.
\item {\bf Lemma:}\label{basic-models-lemma}
{\sl Let $\phi,\psi$ be formulas and $A$ be a set of formulas.
$A\models(\phi\rightarrow\psi)$ if and only if
$A\cup\{\phi\}\models\psi$.}
\proof We need to prove both directions of the ``if and only if.''
\begin{description}
\item [``If'':]
{\em We are given that $A\cup\{\phi\}\models\psi$, and we need
to prove that $A\models(\phi\rightarrow\psi)$.} That is, we
need to show that for any truth assignment $\nu$, if $\nu\models
A$, then $\nu\models(\phi\rightarrow\psi)$.
Let $\nu$ by any truth assignment where $\nu\models A$. If
$\nu\not\models\phi$, then $\nu\models(\phi\rightarrow\psi)$
(vacuously). On the other hand, if $\nu\models\phi$, then
$\nu\models A\cup\{\phi\}$, so, by hypothesis, $\nu\models\psi$,
and thus $\nu\models(\phi\rightarrow\psi)$. Thus, in any case,
$\nu\models(\phi\rightarrow\psi)$, as desired.
\item [``Only if'':]
{\em We are given that $A\models(\phi\rightarrow\psi)$,
and we need to prove that $A\cup\{\phi\}\models\psi$.} That is
we need to show that, for any truth assignment $\nu$, if
$\nu\models A\cup\{\phi\}$, then $\nu\models\psi$.
Let $\nu$ be any truth assignment where $\nu\models
A\cup\{\phi\}$. Then $\nu\models A$ also. Hence, by
hypothesis, $\nu\models(\phi\rightarrow\psi)$. But, by the
``truth table'' for $\rightarrow$, since $\nu\models\phi$ and
$\nu\models(\phi\rightarrow\psi)$, it must be that
$\nu\models\psi$.
\end{description}
\item {\bf Lemma:}\label{unsat}
{\sl Let $\phi$ be a formula and $A$ be a set of formulas.
$A\models(\neg\phi)$ if and only if
$A\cup\{\phi\}$ is unsatisfiable.}
\proof This follows from Lemma~\ref{basic-models-lemma} with
$\psi=\bot$ --- for you can easily show that $\neg\phi$ is
logically equivalent to $(\phi\rightarrow\bot)$, and $A\cup\{\phi\}$
is unsatisfiable iff $A\cup\{\phi\}\models\bot$.
\item {\bf Lemma:}\label{induct}
{\sl Let $\phi_1,\phi_2,\ldots,\phi_k,\psi$ be formulas and $A$ be a
set of formulas. Then }
\[A\models(\phi_1\rightarrow(\phi_2\rightarrow(
\cdots\rightarrow(\phi_k\rightarrow\psi))\cdots))) \mbox{ if and
only if } A\cup\{\phi_1,\phi_2,\ldots,\phi_k\}\models\psi.\]
\proof By (ordinary) induction on $k$. The base case, the result
for $k=0$, is trivial. The inductive step is just an instance of
Lemma~\ref{basic-models-lemma}.
\item {\bf Lemma:}\label{basic-proves-lemma}
{\sl Let $\phi,\psi$ be formulas and $A$ be a set of formulas.
$A\vdash(\phi\rightarrow\psi)$ if and only if
$A\cup\{\phi\}\vdash\psi$.}
\proof We need to prove both directions of the ``if and only if.''
Note that here we show how to manipulate proofs: how to convert a
proof of one result into a proof or the other.
\begin{description}
\item [``Only if'' direction:]
{\sl We need to show that if $A\vdash(\phi\rightarrow\psi)$ then
$A\cup\{\phi\}\vdash\psi$.} So suppose the former. Let $P$ be a
natural deduction proof of $(\phi\rightarrow\psi)$ from $A$.
Let $k$ be the line number of the last line of $P$ --- so that
the formula appearing in line $k$ is $(\phi\rightarrow\psi)$.
So the following is a proof of $\psi$ from $A\cup\{\phi\}$:
\[\begin{array}{rcl}
\multicolumn{3}{c}{P} \\
k+1. &\phi&\mbox{premise} \\
k+2. &\psi&\rightarrow\mbox{-elim. $k$, $k+1$.}
\end{array}\]
For you can check that $P$ itself obeys all the rules of being
a natural deduction proof and that the two additional steps
keep the proof legal.
\item [``If'' direction:]
{\sl We need to show that if $A\cup\{\phi\}\vdash\psi$ then
$A\vdash(\phi\rightarrow\psi)$.} So suppose the former. Let $P$
be a natural deduction proof of $A\cup\{\phi\}\vdash\psi$.
Let $k$ be the number of steps in $P$, and form $P^\prime$ be $P$
as follows: (i) delete the line numbers on the lines, (ii)
whenever $\phi$ appears in $P$, but not inside a subproof, with
justification ``premise'', change that justification to ``copy
1'', and (iii) add 1 to all the line numbers used in justification
within $P$.
The formula on the last line of $P$ must be $\psi$, and that
cannot be inside any subproofs. So the following is a proof of
$(\phi\rightarrow\psi)$ from $A$:
\[\begin{array}{rcclll}\\\cline{3-4}
1. & | & \phi & \mbox{assumption} & | \\
2. & | & \multicolumn{2}{c}{\vdots} & | \\
\vdots & | &\multicolumn{2}{c}{P^\prime} & | \\
k+1. & | & \multicolumn{2}{c}{\vdots} & | \\\cline{3-4}
k+2. & \multicolumn{2}{l}{(\phi\rightarrow\psi)}
& \multicolumn{2}{l}{\rightarrow\mbox{-intro. 2 - }k+1.}
\end{array}\]
There is some fussy checking involved to making sure that the
result is indeed the proof I claim it is --- but I leave all that
checking to you.
\end{description}
\item {\bf Lemma:}
{\sl Let $\phi$ be a formula and $A$ be a set of formulas.
$A\vdash(\neg\phi)$ if and only if
$A\cup\{\phi\}\vdash\bot$.}
\proof Like the proof of Lemma~\ref{unsat}, with
Lemma~\ref{basic-proves-lemma} replacing
Lemma~\ref{basic-models-lemma}.
\item {\bf Lemma:}
{\sl Let $\phi_1,\phi_2,\ldots,\phi_k,\psi$ be formulas and $A$ be a
set of formulas. Then }
\[A\vdash(\phi_1\rightarrow(\phi_2\rightarrow(
\cdots\rightarrow(\phi_k\rightarrow\psi))\cdots))) \mbox{ if and
only if } A\cup\{\phi_1,\phi_2,\ldots,\phi_k\}\vdash\psi.\]
\proof Like the proof of Lemma~\ref{induct}, with
Lemma~\ref{basic-proves-lemma} replacing
Lemma~\ref{basic-models-lemma}.
\item {\bf Lemma:}
{\sl Let $A$ be any set of formulas and $\phi,\psi$ be any formulas. Then:
\begin{enumerate}
\item If $A\vdash\phi$ and $A\vdash\psi$, then $A\vdash(\phi\wedge\psi)$.
\item If $A\vdash\neg\phi$ or $A\vdash\neg\psi$, then
$A\vdash\neg(\phi\wedge\psi)$.
\item If $A\vdash\phi$ or $A\vdash\psi$, then $A\vdash(\phi\vee\psi)$
\item If $A\vdash\neg\phi$ and $A\vdash\neg\psi$, then
$A\vdash\neg(\phi\vee\psi)$
\item If $A\vdash\neg\phi$ or $A\vdash\psi$ then
$A\vdash(\phi\rightarrow\psi)$.
\item If $A\vdash\phi$ and $A\vdash\neg\psi$, then
$A\vdash\neg(\phi\rightarrow\psi)$.
\end{enumerate}
}
\proof All parts can be proved similarly to Lemma~\ref{basic-proves-lemma}.
\item {\bf N.B.} Nowhere above did we assume that $A$ is finite.
The {\em only} place so far that we have used the finiteness of $A$ is
in asserting that it is decidable, given a candidate proof $P$,
whether $P$ really is a proof from premises $A$.
{\bf Defn:} A set $A$ of formulas is {\em inconsistent} if
$A\vdash\bot$. (By comparison, $A$ is {\em unsatisfiable} if
$A\models\bot$. These two are equivalent --- {\em but} we haven't
prove that yet.)
{\bf Lemma:} {\em Suppose a set of formula $A$ is inconsistent. Then
some finite $A_0\subseteq A$ is inconsistent.}
\proof Let $P$ be a proof of $\bot$ from $A$. Since $P$ is a
finite sequence of numbered lines (ending with a line with formula
$\bot$), only finitely many formulas in $A$ can appear in $P$ as
premises. Let $A_0$ be exactly that set of formula in $A$.
\end{enumerate}
\noindent
\end{document}