$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.1: Naïvely

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

We are at a point in our explorations where we have established a particular deductive system, consisting of the logical axioms and rules of inference that we set out in the last chapter. The Soundness Theorem showed that our deductive system preserves truth, in the sense that if there is a deduction of $$\phi$$ from $$\Sigma$$, then $$\phi$$ is true in any model of $$\Sigma$$. The Completeness Theorem, the first major result of this chapter, gives us the converse to the Soundness Theorem. So, when the two results are combined, we will have this equivalence:

$\Sigma \models \phi \: \text{if and only if} \: \Sigma \vdash \phi.$

We have already made a big point of the fact that we would like to be sure that if our deductive system allows us to prove a statement, we would like that statement to be true. Certainly, the content of the Soundness Theorem is exactly that. If $$\vdash \phi$$, if there is a deduction of $$\phi$$ from only the logical axioms without any additional assumptions, then we know that $$\models \phi$$, so $$\phi$$ is true in every structure with every assignment function. To the extent that the informal mathematical practice of everyday proofs is modeled by our formal system of deduction, we can be sure that the things that we prove mathematically are true.

If life were peaches and cream, we would also like to know that we can prove anything that is true. The Completeness Theorem is the result that asserts that our deductive system is that strong. So you would be tempted to conclude that, for example, we are able to prove any statement of first-order logic that is a true statement about the natural numbers.

Unfortunately, this conclusion is based upon a misreading of the statement of the Completeness Theorem. What we will prove is that our deductive system is complete, in the sense of this definition.

Definition 3.1.1. A deductive system consisting of a collection of logical axioms $$\Lambda$$ and a collection of rules of inference is said to be complete if for every set of nonlogical axioms $$\Sigma$$ and every $$\mathcal{L}$$-formula $$\phi$$,

$\text{If} \: \Sigma \models \phi, \: \text{then} \: \Sigma \vdash \phi.$

What this says is that if $$\phi$$ is an $$\mathcal{L}$$-formula that is true in every model of $$\Sigma$$, then there will be a deduction from $$\Sigma$$ of $$\phi$$. So our ability to prove $$\phi$$ depends on $$\phi$$ being true in every model of $$\Sigma$$. Thus if we want to be able to use $$\Sigma$$ to prove every true statement about the natural numbers, we have to be able to find a set of nonlogical axioms $$\Sigma$$ such that $$\Sigma \models \phi$$ if and only if $$\phi$$ is a true statement about the natural numbers. We will have much more to say about that problem in Chapters 4, 5,6, and 7.

The second part of the chapter concerns the Compactness Theorem and the Löwenheim-Skolem Theorems. We will use these results to investigate various types of mathematical structures, including structures that are quite surprising.

In some sense, we have spent a lot of time in the first couple chapters of this book developing a lot of vocabulary and establishing some basic results. Now we will roll up our sleeves and get a couple of worthwhile theorems. It is time to start showing some of the beauty and the power, as well as the limitations, of first-order logic.