1.10: Logical Implication

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$.]