$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.9: Logical Implication

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

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

At first glance it seems that a large portion of mathematics can be broken down into answering questions of the form: If I know this statement is true, is it necessarily the case that this other statement is true? In this section we will formalize that question.

Definition 1.9.1. Suppose that $$\Delta$$ and $$\Gamma$$ are sets of $$\mathcal{L}$$-formulas. We will say that $$\Delta$$ logically implies $$\Gamma$$ and write $$\Delta \models \Gamma$$ if for every $$\mathcal{L}$$-structure $$\mathfrak{A}$$, if $$\mathfrak{A} \models \Delta$$, then $$\mathfrak{A} \models \Gamma$$.

This definition is a little bit tricky. It says that if $$\Delta$$ is true in $$\mathfrak{A}$$, then $$\Gamma$$ is true in $$\mathfrak{A}$$. Remember, for $$\Delta$$ to be true in $$\mathfrak{A}$$, it must be the case that $$\mathfrak{A} \models \Delta \left[ s \right]$$ for every assignment function $$s$$. See Exercise 4.

If $$\Gamma = \{ \gamma \}$$ is a set consisting of a single formula, we will write $$\Delta \models \gamma$$ rather than the official $$\Delta \models \{ \gamma \}$$.

Definition 1.9.2. An $$\mathcal{L}$$-formula $$\phi$$ is said to be valid if $$\emptyset \models \phi$$, in other words, if $$\phi$$ is true in every $$\mathcal{L}$$-structure with every assignment function $$s$$. In this case, we will write $$\models \phi$$.

Chaff: It doesn't seem like it would be easy to check whether $$\Delta \models \Gamma$$. To do so directly would mean that we would have to examine every possible $$\mathcal{L}$$-structure and every possible assignment function $$s\, of which there will be many. I'm also sure that you've noticed that this double turnstyle symbol, \(\models$$, is getting a lot of use. Just remember that if there is a structure on the left, $$\mathfrak{A} \models \sigma$$, we are discussing truth in a single structure. If there is a set of sentences on the left, $$\Gamma \models \sigma$$, then we are discussing logical implication.

Example 1.9.3. Let $$\mathcal{L}$$ be the language consisting of a single binary relation symbol, $$P$$, and let $$\sigma$$ be the sentence $$\left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right)$$. We show that $$\sigma$$ is valid.

So let $$\mathfrak{A}$$ be any $$\mathcal{L}$$-structure and let $$s : Vars \rightarrow A$$ be any assignment function. We must show that

$\mathfrak{A} \models \left[ \left( \exists y \forall x P \left( x, y \right) \right) \rightarrow \left( \forall x \exists y P \left( x, y \right) \right) \right] \left[ s \right].$

Assume that $$\mathfrak{A} \models \left( \exists y \forall x P \left( x, y \right) \right) \left[ s \right]$$, we know that there is an element of the universe, $$A$$, such that $$\mathfrak{A} \models \forall x P \left( x, y \right) \left[s \left[ y | a \right] \right]$$. And so, again by the definition of satisfaction, we know that if $$b$$ is any element of $$A$$, $$\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ y | a \right] \right) \left[ x | b \right] \right]$$. If we chase through the definition of satisfaction (Definition 1.7.4) and of the various assignment functions, this means that for our one fixed $$a$$, the ordered pair $$\left( b, a \right) \in P^\mathfrak{A}$$ for any choice of $$b \in A$$.

We have to prove that $$\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]$$. As the statement of interest is universal, we must show that, if $$c$$ is an arbitrary element of $$A$$, $$\mathfrak{A} \models \exists y P \left( x, y \right) \left[ s \left[ x | c \right] \right]$$, which means that we must produce an element of the universe, $$d$$, such that $$\mathfrak{A} \models P \left( x, y \right) \left[ \left( s \left[ x | c \right] \right) \left[ y | d \right] \right]$$. Again, from the definition of satisfaction this means that we must find a $$d \in A$$ such that $$\left( c, d \right) \in P^\mathfrak{A}$$. Fortunately, we have such a $$d$$ in hand, namely $$a$$. As we know, $$\left( c, a \right) \in P^\mathfrak{A}$$, we have shown $$\mathfrak{A} \models \left( \forall x \exists y P \left( x, y \right) \right) \left[ s \right]$$, and we are finished.

### Exercises

1. Show that $$\{ \alpha, \alpha \rightarrow \beta \} \models \beta$$ for any formulas $$\alpha$$ and $$\beta$$. Translate this result into everyday English. Or Norwegian, if you prefer.
2. Show that the formula $$x = x$$ is valid. Show that the formula $$x = y$$ is not valid. What can you prove about the formula $$\neg x = y$$ in terms of validity?
3. Suppose that $$\phi$$ is an $$\mathcal{L}$$-formula and $$x$$ is a variable. Prove that $$\phi$$ is valid if and only if $$\left( \forall x \right) \left( \phi \right)$$ is valid. Thus, if $$\phi$$ has free variables $$x$$, $$y$$, and $$z$$, $$\phi$$ will be valid if and only if $$\forall x \forall y \forall z \phi$$ is valid. The sentence $$\forall x \forall y \forall z \phi$$ is called the universal closure of $$\phi$$.
4. (a) Assume that $$\models \left( \phi \rightarrow \psi \right)$$. Show that $$\phi \models \psi$$.
(b) Suppose that $$\phi$$ is $$x < y$$ and $$\psi$$ is $$z < w$$. Show that $$\phi \models \psi$$ but $$\not\models \left( \phi \rightarrow \psi \right)$$. (The slash through $$\models$$ means "does not logically imply.")

[This exercise shows that the two possible ways to define logical equivalence are not equivalent. The strong form of the definition says that $$\phi$$ and $$\psi$$ are logically equivalent if $$\models \left( \phi \rightarrow \psi \right)$$ and $$\models \left( \psi \rightarrow \phi \right)$$. The weak form of the definition states that $$\phi$$ and $$\psi$$ are logically equivalent if $$\phi \models \psi$$ and $$\psi \models \phi$$.]